pouët.net

Finding edge loops

category: code [glöplog]
 
Considering bunch of faces which may or may not belong to same group, how do you find outer edge and inner edge (for holes) loops?

I figured out that with simple convex shapes this is really easy as you can just keep dropping vertices with highest valency and you reduce into state where each vertex is connected to just 2 edges.

With concave hulls and holes, things started to go bad.

Currently best suggestion is to mark selected faces as selected and keep left/right face information in edges so that all edges that have both sides as selected is inside edge and can be eliminated.

I'm trying to get my multiface average normal extrude to work and Google: "mesh extrusion" gave me something very horrible.
added on the 2010-11-01 14:28:41 by jalava jalava
If you define an edge as a pair of vertices, uniquely defined by the vertices indices {i0, i1}, ordered so i0<i1, it becomes trivial to figure out whether an edge is on a border: If it is only contained in one triangle, it is on a border.

BB Image
added on the 2010-11-01 14:43:41 by hornet hornet
Push every edge into a list, if that edge is already on the list pop it out. The end result should be the outer edges only.
added on the 2010-11-01 15:23:36 by xernobyl xernobyl
and be aware of edges with more than 2 faces
BB Image when counting. (captain obvious)
added on the 2010-11-01 15:34:02 by the_Ye-Ti the_Ye-Ti
Quote:
may not belong to same group

- if you have split vertex-data (e.g. hard-edges or uv-seams), you will need to create a mesh-representation that knows which vertices are the same. Depending on your source-format, you may need to compare vertex-positions to do this.
added on the 2010-11-01 17:22:01 by hornet hornet
Actually I mean two groups as in two regions in same mesh. I was thinking of traversing polygons recursively and marking polygons to different groups on first pass and only then doing the edge loop selection.

This means that mesh must be seamless for traversing to work correctly.

Actually this is the reason I started to work with extrude. It is the easiest way to create seamless n segment cube by extruding point -> w segment line -> h segment rectangle -> d segment cube.
added on the 2010-11-01 18:24:50 by jalava jalava
Quote:
I'm trying to get my multiface average normal extrude to work and Google: "mesh extrusion" gave me something very horrible.

I made one of those recently. For half-edges.
Quote:
Currently best suggestion is to mark selected faces as selected and keep left/right face information in edges so that all edges that have both sides as selected is inside edge and can be eliminated.

Pretty much the same solution here. Then I generate new triangles, generate edge info for those new triangles. Find vertices that need to be shifted and shift those with average normal.

Although, my code actually works for disjunct sets of faces and I think holes too. Should work for you too.

Quote:
Actually I mean two groups as in two regions in same mesh. I was thinking of traversing polygons recursively and marking polygons to different groups on first pass and only then doing the edge loop selection.

Evidently its not necessary for proper topology but I'm guessing that you want to calculate different average normals for different groups then you should do something like that. I have no working solution for it myself since I havent had the need for it yet. If I want to extrude two different sets with different normals I just mark two times and extrude.

Quote:
Actually this is the reason I started to work with extrude. It is the easiest way to create seamless n segment cube by extruding point -> w segment line -> h segment rectangle -> d segment cube.

Not sure I understand what you're trying to do exactly but in my experience, if I only have a special case like that, I'm better of making specialized code for it.
added on the 2010-11-01 23:53:55 by Yomat Yomat
Had success with splitting faces to individual groups, marking the left and right sides of each edge, selecting only edges with one face and making sure that edge loops rotate always to direction that right side has face and left side doesn't.

BB Image

I think I should be fine for most cases, testcase is not exhaustive though. Thanks everyone for comments.
added on the 2010-11-02 02:40:42 by jalava jalava

login