half edge data structure

Discussion in 'C Programming' started by broli, Mar 24, 2008.

  1. broli

    broli Guest

    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 ??
    broli, Mar 24, 2008
    #1
    1. Advertising

  2. broli

    Morris Dovey Guest

    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

    --
    Morris Dovey
    DeSoto Solar
    DeSoto, Iowa USA
    http://www.iedu.com/DeSoto/
    Morris Dovey, Mar 24, 2008
    #2
    1. Advertising

  3. broli

    broli Guest

    On Mar 24, 7:29 pm, Morris Dovey <> 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 ?
    broli, Mar 24, 2008
    #3
  4. broli

    Morris Dovey Guest

    broli wrote:
    >
    > On Mar 24, 7:29 pm, Morris Dovey <> 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 ?


    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?

    --
    Morris Dovey
    DeSoto Solar
    DeSoto, Iowa USA
    http://www.iedu.com/DeSoto/
    Morris Dovey, Mar 24, 2008
    #4
  5. broli

    Ernie Wright Guest

    broli wrote:

    > On Mar 24, 7:29 pm, Morris Dovey <> 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
    Ernie Wright, Mar 24, 2008
    #5
  6. broli

    Morris Dovey Guest

    Ernie Wright wrote:
    >
    > broli wrote:
    >
    > > On Mar 24, 7:29 pm, Morris Dovey <> 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.)


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

    --
    Morris Dovey
    DeSoto Solar
    DeSoto, Iowa USA
    http://www.iedu.com/DeSoto/
    Morris Dovey, Mar 24, 2008
    #6
  7. broli

    Ernie Wright Guest

    Morris Dovey wrote:

    > Ernie Wright wrote:
    >
    >>broli wrote:
    >>
    >>>On Mar 24, 7:29 pm, Morris Dovey <> 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. [...]

    >
    > 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
    Ernie Wright, Mar 24, 2008
    #7
  8. broli

    Morris Dovey Guest

    Ernie Wright wrote:

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

    --
    Morris Dovey
    DeSoto Solar
    DeSoto, Iowa USA
    http://www.iedu.com/DeSoto/
    Morris Dovey, Mar 24, 2008
    #8
  9. broli

    Bartc Guest

    "Morris Dovey" <> wrote in message
    news:...
    > Ernie Wright wrote:
    >
    >> 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?


    Broli has already asked on comp.graphics.algorithms.

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

    --
    Bart
    Bartc, Mar 24, 2008
    #9
  10. broli

    Ernie Wright Guest

    Bartc wrote:

    > "Morris Dovey" <> wrote in message
    > news:...
    >
    >>Ernie Wright wrote:
    >>
    >>>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?

    >
    > 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
    Ernie Wright, Mar 24, 2008
    #10
  11. broli

    user923005 Guest

    On Mar 24, 4:40 am, broli <> wrote:
    > 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 news:comp.graphics.algorithms.algorithms (especially since I
    see that elsethread you are asking about efficiency).
    user923005, Mar 24, 2008
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ferdi Smit
    Replies:
    0
    Views:
    771
    Ferdi Smit
    Oct 10, 2005
  2. trint
    Replies:
    4
    Views:
    692
    =?ISO-8859-1?Q?G=F6ran_Andersson?=
    Sep 11, 2007
  3. denish
    Replies:
    5
    Views:
    5,603
  4. joe chesak
    Replies:
    7
    Views:
    276
    (r.*n){2}
    Sep 23, 2010
  5. Mike Ballard
    Replies:
    6
    Views:
    268
    Dr.Ruud
    Nov 15, 2005
Loading...

Share This Page