Monday, October 18, 2010

data structures, edge loop selection, unfolding

I struggled with the unfolding code for a day, but since then I haven't coded anything.

Anyway, some words about the data structures:

  • vertex list: vertices (I think I will have separate texture coordinates and vertex normals, I'm not sure about this one yet)
  • triangle list: 3 vertices; face normal; polygon ID (for polygon selection); selection flag. Maybe element ID for element selection, I'm using a floodfill-like algorithm for that currently, but it doesn't do well if some polygons are already selected when I want to "add to selection".
  • edge list: 2 indices of the two vertices; edge flag (editable/non editable); selection flag; 2 indices of the two neighbour triangles.
Loop detection: search the 3 other editable edges that meet at one of the vertices of the current edge. The edge to select is the one, that doesn't share polygons with the current edge. Loop until no edges left to be selected. An edge can be selected, if it's not selected yet, or if only 4 editable edges meet at a vertex. Somehow, I didn't get this to work yet. I debugged it for 2 fucking days (debugging included adding new features: convert edge selection to face/vertex).

Unfolding: unfolding will be a recursive function. It's tricky, i haven't finished it yet, and it will be a nightmare to debug. the main issue is that the generated data will be different than the original data: dublicated vertices, duplicated edges. It's too easy to fuck up.

Anyway, the idea (at least an attempt to remember the idea):
1. We have left a triangle, we are on one edge (current edge) of the triangle.
2. Find next triangle (new triangle) (it's easy with the edge structure).
3. Find the opposite corner vertex: the vertex that is on the new triangle but not on the current edge.
4. Transform that vertex to the "unfold space": I'm too tired to explain this one. Converting from the 3D triangle coordinate system to the 2D unfold coordinate system *sigh*
5. create the two edges' data structure (this is the easy-to-fuck-up part), then continue on both edges (recursion).
6. recursion stops when all the triangles are used up. I'll simply use the selection flag to indicate that.

We have to start with an initial triangle. This will be placed in 0,0 position in the unfold space.

The unfold pattern can be controlled by the order of execution of the two edges. This thing will be expandable. I will start off with a simple whatever-edge-has-smaller-index scheme, but later I will add some general schemes: box, spiral, zig-zag, defined-by-edge-selection, whatever, etc.

I wanted to write about something.....

No comments:

Post a Comment