Sunday, October 24, 2010


Finally, I coded the basic unfolding algorithm. I started from scratch, the very clever edge data based approach wasn't clever at all. The fact, that the edges cannot have consistent/meaningful orientation/winding (because edges aren't duplicated) made the whole thing a nightmare. Sucking with the indexing, sucking with the non consistent winding. The whole thing was a debugging nightmare.

New algorithm (which took only about 4-5 hours to code):
Triangles do have consistent winding, so the entire stuff is built upon them. At the moment, the triangle lists in the two spaces (world/unfold) are indexed in the same way.
1. We are on the current triangle. The "unfolded" triangle list has a consistent vertex order: 0-1 is the "bottom" of the triangle (where it is connected to the previously checked triangle). The "world" triangle list doesn't follow this obviously, but it's just a matter of offsetting and warping the indexes. This offset value is passed through the recursion
2. Using the offset value, you can unfold the corner vertex (the vertex that is not on the "bottom"): some cross product/dot product magic. The unfolded vertex goes into the unfolded vertex list, which is a growing list (one new triangle means one new vertex, it's very simple (at the moment)).
3. searching for the right/left neighbour triangle: knowing the offset of the current triangle, it's not a big deal to dig through the world triangles to look for the neighbours (the consistent winding is very handy here). The offsets of the new triangles can be obtained too thanks to the consistent winding (it was a fucking nightmare with the edge structure)
4. if there is a left neighbour triangle and it's not checked yet (I'm using the selection flag of the triangle struct for that) call the function again with the left offset and left triangle index.
5. if there is a right neighbour triangle and it's not checked yet call the function again with theright offset and right triangle index.

We have to start with an initial triangle, and we have to start in 3 directions first (it's not added yet).

The algorithm doesn't check for self intersections yet, and patterns are to be added. But at last the basic algo works well. There are lot of unnecessarily duplicated vertices, but it will be easy to remove them in a post process, or maybe inside the algorithm. but I'm not sure if it's a good thing: with separated triangles (more or less) it will be easier to rearrange the unfold layout, with is a very important feature.

Results in images (note that smoothing groups isn't implemented):

No comments:

Post a Comment