half edge data structure

[broli]

hello i am trying to implement a hald edge data structure.

In my project, I have to read a file that contains the geometrical
specifications of a 3d object which has been converted into a
triangular mesh. I have specified the format of the file in a previous
thread -

http://groups.google.co.in/group/comp.lang.c/msg/17f95654400d414d
(ignore the program bit just read about the format of file)

^^ I have stored all this information in a vertex list. Sequentially
in the way they occur. After the coordinates, the file specifies 3
indices into the vertex list(which point to 3 vertices) needed to
define a triangle.

Now I'm successfully able to code a program read the data from the
file
with the help of data structures that I created for vertex, object and
But now, I want to implement adjacency queries for which I need half
edge data structure. I do not understand how to create a half edge
data structure from this plethora of information (i.e. vertex list and
triangle list). I looked on flipcode and found some information about
the structures involved -

struct HE_edge
{

HE_vert* vert; // vertex at the end of the half-edge
HE_edge* pair; // oppositely oriented adjacent half-edge
HE_face* face; // face the half-edge borders
HE_edge* next; // next half-edge around the face

};

struct HE_vert
{

float x;
float y;
float z;

HE_edge* edge; // one of the half-edges emantating from the
vertex

};

struct HE_face
{

HE_edge* edge; // one of the half-edges bordering the face

};

Now my main question : How do I fit all this data into the structures
above ?? Do I need to loop through each vertex in the vertex list and
each triangle in triangle list ??

 

[Morris Dovey]

broli wrote:

[edited only to vertically compress]

struct HE_edge
{ HE_vert* vert; // vertex at the end of the half-edge
HE_edge* pair; // oppositely oriented adjacent half-edge
HE_face* face; // face the half-edge borders
HE_edge* next; // next half-edge around the face
};

struct HE_vert
{ float x;
float y;
float z;
HE_edge* edge; // one of the half-edges emantating from the vertex
};

struct HE_face
{ HE_edge* edge; // one of the half-edges bordering the face
};

From previous post:

typedef struct Triangle 3Dstruct /* Data structure for the
Triangle */
{ int v0, v1, v2; /* 3 indices to the vertex list */
} Triangle;

Now my main question : How do I fit all this data into the structures
above ?? Do I need to loop through each vertex in the vertex list and
each triangle in triangle list ??

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.

HTH

 

[broli]

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 ?

 

[Morris Dovey]

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 ?

Eh? Bad Broli! Don't "yabbut" me about optimization without first
providing a clear definition of the final objective.

More seriously, its almost always better to get your application
working before you start worrying about optimization.

My thinking was that if you have the triangle, then you have
direct access to the three sets of vertex coordinates, which
means that you also have the endpoints of all of the edges.

What did I miss?

 

[Ernie Wright]

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

 

[Morris Dovey]

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

I'm relieved that there's someone with some experience with this
stuff so I can bow out of [escape from] the picture.

I had been about to suggest structuring the data more or less as
shown in

http://www.iedu.com/c/plates.c

using cross-linked lists of triangles and vertices, and I wasn't
sure I was pointed in the right direction...

 

[Ernie Wright]

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

I'm relieved that there's someone with some experience with this
stuff so I can bow out of [escape from] the picture.

The OP should probably be asking questions of this kind in a computer
graphics forum, so that he's interacting with a community of folks who
know about this stuff. There's nothing specific to C about this, and
no reason to expect that folks here know anything about his question.

I had been about to suggest structuring the data more or less as
shown in

http://www.iedu.com/c/plates.c

using cross-linked lists of triangles and vertices, and I wasn't
sure I was pointed in the right direction...

That'd work fine. If the model won't be altered by the program, it can
be represented somewhat more conveniently as a set of arrays rather than
linked lists.

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

 

[Morris Dovey]

The OP should probably be asking questions of this kind in a computer
graphics forum, so that he's interacting with a community of folks who
know about this stuff. There's nothing specific to C about this, and
no reason to expect that folks here know anything about his question.

Methinks you're right. The only time I'd ever seen anything like
this was a NASA project modeling airframes on a SGI system (I was
dazzled!)

Can you suggest an appropriate graphics forum?

That'd work fine. If the model won't be altered by the program, it can
be represented somewhat more conveniently as a set of arrays rather than
linked lists.

I wondered about that, but was afraid that might turn out to be
either overly restrictive or memory extravagant.

 

[Bartc]

Methinks you're right. The only time I'd ever seen anything like
this was a NASA project modeling airframes on a SGI system (I was
dazzled!)

Can you suggest an appropriate graphics forum?

Broli has already asked on comp.graphics.algorithms.

But I guess he might come back here with coding details.

 

[Ernie Wright]

Broli has already asked on comp.graphics.algorithms.

Which is probably the best Usenet place to ask. But I'm sure there are
mailing lists and Web-based forums, particularly those concerned with
game programming, that are both more active and more likely to give
pragmatic advice.

I suspect he doesn't need the pretty formalism (and limitations) of a
true half-edge implementation, just a way to answer certain questions
about the connectedness of a mesh, which can be done in a number of
other, conceptually simpler ways.

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

 

[user923005]

hello i am trying to implement a hald edge data structure.

In my project, I have to read a file that contains the geometrical
specifications of a 3d object which has been converted into a
triangular mesh. I have specified the format of the file in a previous
thread -

http://groups.google.co.in/group/comp.lang.c/msg/17f95654400d414d
(ignore the program bit just read about the format of file)

^^ I have stored all this information in a vertex list. Sequentially
in the way they occur. After the coordinates, the file specifies 3
indices into the vertex list(which point to 3 vertices) needed to
define a triangle.

Now I'm successfully able to code a program read the data from the
file
with the help of data structures that I created for vertex, object and
But now, I want to implement adjacency queries for which I need half
edge data structure. I do not understand how to create a half edge
data structure from this plethora of information (i.e. vertex list and
triangle list). I looked on  flipcode and found some information about
the structures involved -

  struct HE_edge
    {

        HE_vert* vert;   // vertex at the end of the half-edge
        HE_edge* pair;   // oppositely oriented adjacent half-edge
        HE_face* face;   // face the half-edge borders
        HE_edge* next;   // next half-edge around the face

    };

  struct HE_vert
    {

        float x;
        float y;
        float z;

        HE_edge* edge;  // one of the half-edges emantating from the
vertex

    };

   struct HE_face
    {

        HE_edge* edge;  // one of the half-edges bordering the face

    };

Now my main question : How do I fit all this data into the structures
above ?? Do I need to loop through each vertex in the vertex list and
each triangle in triangle list ??

You want (especially since I
see that elsethread you are asking about efficiency).