How do we convert efficiently from a polygon soup to a halfedge mesh?
keenan
@HelloWorld It's tough! Actually, that's why we don't ask you do it for your assignment: for the most part, the half edge data structure is super easy to implement and work with. The most annoying part is building up the adjacency information from a more primitive data structure. If you're starting from a real polygon soup (literally no connectivity information) then the rough sketch is:
First, find all vertices with the same (x,y,z) coordinates. The naive algorithm is to check every vertex against every other vertex, but obviously this is quite slow ($O(n^2)$). To speed things up you can use a spatial acceleration data structure like a kd-tree, which we'll talk about in upcoming lectures. One must be also careful since the coordinate values are typically stored in floating point, and depending on how they were computed you may need to make some judgement about which vertices are numerically "close enough."
Next, find all polygons that share a pair of edges. One way to do this is to loop over each polygon, and put each pair of consecutive vertices (i,j) along the polygon boundary into an associative array that maps this pair to the polygon P it came from. The next time you encounter this same pair (i,j) (or (j,i)) in a polygon Q, you'll know that P and Q are adjacent.
...and so on. I won't spell out the full logic here, but you can check out our implementation in the skeleton code if you're really interested. It's a lot of work! :-)
tpan496
How does Winged-edge mesh structure compare to those three?
How do we convert efficiently from a polygon soup to a halfedge mesh?
@HelloWorld It's tough! Actually, that's why we don't ask you do it for your assignment: for the most part, the half edge data structure is super easy to implement and work with. The most annoying part is building up the adjacency information from a more primitive data structure. If you're starting from a real polygon soup (literally no connectivity information) then the rough sketch is:
First, find all vertices with the same (x,y,z) coordinates. The naive algorithm is to check every vertex against every other vertex, but obviously this is quite slow ($O(n^2)$). To speed things up you can use a spatial acceleration data structure like a kd-tree, which we'll talk about in upcoming lectures. One must be also careful since the coordinate values are typically stored in floating point, and depending on how they were computed you may need to make some judgement about which vertices are numerically "close enough."
Next, find all polygons that share a pair of edges. One way to do this is to loop over each polygon, and put each pair of consecutive vertices (i,j) along the polygon boundary into an associative array that maps this pair to the polygon P it came from. The next time you encounter this same pair (i,j) (or (j,i)) in a polygon Q, you'll know that P and Q are adjacent.
...and so on. I won't spell out the full logic here, but you can check out our implementation in the skeleton code if you're really interested. It's a lot of work! :-)
How does Winged-edge mesh structure compare to those three?