Re: half edge data structure

broli wrote:

On Mar 24, 7:29 pm, Morris Dovey <mrdo...@xxxxxxxx> wrote:

It appears to me that it should be sufficient to work your way
through the triangles and use the vertex indices to get at the
vertex coordinates.

Yes, but wouldn't it be very inefficient to traverse through say 1200
triangles and then for each triangle prepare list of edges, then
prepare common vertex list, common edge list etc ?

How else can it be done?

I've done this for *much* larger models. It doesn't take long at all.
Sort the edge list by lower-numbered vertex. Duplicate edge records
will be adjacent to each other in the sorted list. Consolidate those to
create a list of unique edges.

With appropriate choices of data structure, each edge record can contain
references to all of the triangles that share it, and each triangle can
contain references to its three edges in the edge list. You can then
find, given a triangle, all the triangles that share any of its three
edges, or given an edge, all the triangles that share that edge. (Note
that if the meshes aren't restricted to two-manifolds, there may be more
than two triangles sharing an edge.)

- Ernie http://home.comcast.net/~erniew
.

Relevant Pages

  • Re: half edge data structure
    ... triangles and then for each triangle prepare list of edges, ... With appropriate choices of data structure, ... contain references to its three edges in the edge list. ... using cross-linked lists of triangles and vertices, ...
    (comp.lang.c)
  • Re: Need help improving algorithm
    ... triangle's t12, t23, and t31 is set to OUTER. ... triangles and enter references in the point entry to each triangle which includes it. ...
    (comp.programming)
  • Re: Decimation Methods
    ... I also thought initially that vertex coordinates would not matter but ... is lets say per fragment limited in this case larger triangles would ... In such cases vertex coordinates would also affect performance. ... It doesn't happen as often as it should, because scientists ...
    (comp.graphics.api.opengl)
  • Re: Decimation Methods
    ... I also thought initially that vertex coordinates would not matter but ... is lets say per fragment limited in this case larger triangles would ... consume larger ... In such cases vertex coordinates would also affect performance. ...
    (comp.graphics.api.opengl)
  • Re: half edge data structure
    ... vertex coordinates. ... triangles and then for each triangle prepare list of edges, ... Bad Broli! ... working before you start worrying about optimization. ...
    (comp.lang.c)