Unfold with faces

I finally learned what "runtime error" and "debugger" is. Seems to be pretty useful knowledge.

Anyhoo: I added an unfold layout/pattern/whatever manager to the recursion: it only has the face check now: the first of the three neighbor triangles to continue with is the one, that's on the same face.
I added this simple condition, and I have more pleasant results.
Images:
1. original mesh
2. unfolded mesh: CW neighbor order
3. unfolded mesh: CCW neighbor order

Some screenshots with some primitives

I added self intersection test. The unfold algorithm unfolds faces until there are no faces left to be unfold.
I coloured  the separate unfolded patches with separate colours.

The unfold schemes will be the next big step (or the layout editing). I think if I force faces to be treated as faces (not triangles) the output will be more pleasant. I think the scheme can be controlled by the order of the face checks (left/right/bottom triangle) and the amount of faces to unfold in the branches. At least I hope so.

Unfolding

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):

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.....

Employment, tiredness, some random stuff

I started at a company today. My first ever full-time job. I'm pretty tired (it was boring), I already slept one, I dreamt about green fields and George Bush making a speech, and some other things.

I started to code the unfolding algorithm 2 days ago. It's tough.

I have two view-modes: 3D and 2D. The 2D will be for the unfolded stuff obviously. I don't think I'll have multiple viewports, it will be more like AutoCAD softwares with the "sheet" "3D" or whatever tabs.

So, about 2D: there's a grid, it's very similar to 3d MAX's grid (accidentally...)
So: It's an infinite grid, but it's faked: I calculate the starting and ending line at runtime, so there are always a finite number of lines on the screen. I added a "level of detail effect": if the distance between two lines are smaller than a given value, the grid size will be multiplied by 10.

I did these grids in immediate mode, since the number of lines are controlled, so there will never be too many.
Video (EDIT: I don't know why the aspect ratio is fucked up, it's okay in the application)

Some random screenshots

Grid+little coordinate system:

.obj loaded, vertex normals, lighting. No smoothing groups yet:

 Edge info generated: polygons vs triangles. The editor will be polygon based to preserve the nice edge-flow (select edge loop will be an important feature as it will control the automatic unfolding):

Wireframe mode:

Displaying vertices in vertex selection mode; vertex selection:

Edge and polygon selection:

What I have so far:

I'm thinking about posting ideas about implementation/maths/algorithms too, which are some paint drawings, I don't know if it's useful, I don't want to make a shit tutorial of it, but these may be interesting anyway. I don't know yet.

It's hard to post about the thing afterwards. So I just copy the "devlog":

04.10.2010.
Window, openGL setup.
3D grid, camera: rotation, pan, dolly, zoom

05.10.2010.
Coordinate system icon

06.10.2010.
Displaying probe cube, face normal calculation
Loading .obj file (vertex and face data)
vertex normal calculation
Edge data generation and display
Display modes: wireframe/smooth/smooth+wireframe
Text rendering, statistics display

07.10.2010.
selection mode keyboard and display
display vertices
selection rectangle basics (detecting selection rectangle) and display
projecting vertices to screen, rectangle selection of vertices and selection highlight
add to selection/remove from selection (ctr / shift)
rectangle selection and highlight of lines, click selection of vertices and lines
number of selected vertices/edges displayed
display of highlights fixed

polygon data added
face selection/selection highlight (color materials)
add to selection/remove from selection (ctr / shift)

08.10.2010.
face selection enhanced
click select: sort by depth (vertex/face), line selection: rectangle line check rewritten
selection codes refractored
fixed display highlights and modes (wireframe/mesh)

09.10.2010.
select edge loop started
convert edge selection to face selection
select edge loop debug: unfixed

10.10.2010.
select element.

paper modeller (computer programming project) blog - what for?

Paper models:
Paper models are models made of paper.
I talking about this stuff (my last paper model):


My paper models (I was 12-16) are totally home-made stuff, I didn't know much about the thing that time. They are designed with pen and graph paper then copied to cardboard with carbon paper.

I gave up that hobby and I have a new hobby since then: programming. So I want to make an application to design paper models: unfolding geometry and some other features. I know that there are programs for that already but I don't care. I want to make it handy and fancy, fancy GUI, shiny buttons. I'm coding in C. I'm an animal, so I'll reinvent everything. No engines, no nothing. Custom GUI, because I want to make it cross platform. OpenGL.

So this blog isn't really about paper modelling in general (I think), it's a kind of documentation for the programming project. I have been already working on it for 10 days. I will probably get bored of blogging pretty soon (or won't have time for it), but I try not to. I can't write, I don't speak English.

Ideas, comments about features are welcome, but I won't show source code.