Vertex reordering

Vertex reordering

Post by Mark Kupp » Sat, 23 May 1992 12:18:15



  Does anyone know of any routines that will take a list of triangles
and reorder their vertices based on the edges shared by all of their
neighbors? This is obviously to obtain a consistent ordering to find
the best possible surface normals. Thanks for any help!

  Also, any input on how this could be optimized for time/space efficiency
would also be much appreciated.

 
 
 

Vertex reordering

Post by Gavin Be » Sun, 24 May 1992 12:00:03



Quote:>  Does anyone know of any routines that will take a list of triangles
>and reorder their vertices based on the edges shared by all of their
>neighbors? This is obviously to obtain a consistent ordering to find
>the best possible surface normals. Thanks for any help!

Ah, finally a question I find interesting (ok, so sue me, I'm not into
converting TIFF files into HPGL...)

The first step is to convert the triangles into a list of vertices and
a list of indices into those vertices, 3 indices per triangle.

This is easy if the vertices of neighboring triangles are always
exactly equal.  If they are, create a hash table (see Graphics Gems I
or II for good ways of hashing floating point numbers), and generate
the indices from the hash table.

Unfortunately, I've found that floating point error seems to creep
into a lot of data sets, so they aren't exactly equal.  In this case,
simply hashing on the floating point number won't work, because you
want vertices that are 'close enough' to each other to be considered
the same vertex.  To do this efficiently, you need to use some kind of
spatial data structure.  I'm fond of K-D trees, myself.  The book "The
Design and Analysis of Spatial Data Structures" by Hanan Samet is a
very good reference for this kind of stuff.

Fortunately, a lot of data is already organized as a list of vertices
and indices into that list, so you might be able to skip all of the
above...

Now the task is to figure out the connections between the triangles so
they can be consistently oriented.  First, note that there are
surfaces for which it is impossible to come up with a consistent
ordering (e.g. mobius strips, klein bottles).  But, assuming that you
can live with an inconsistent ordering in those cases, you can do the
following:

Create an edge data structure that consists of two indices (for the
vertices at either end) and a list of pointers to triangles (if your
data is always a well-behaved and a maximum of 2 triangles will meet
at an edge this can be replaced by two pointers to triangles...).

Create a hash table of edges that support the following two functions:

-- Adds an edge to the hash table, given the vertex indices of the
   edge and a pointer to the triangle it is part of

-- Returns a list of the other triangles around the edge, given a
   pointer to a triangle and the vertex indices of the edge.

You can use the smaller of the two vertex indices as the seed for the
hash function.

Now you just need to iterate through all of your triangles, adding
each edge of each triangle to the hash table.

To orient everything correctly, just mark all triangle's orientations
as UNKNOWN, and somehow determine the orientation of one triangle (or
assume one is correct).  Then correct the orientation of all
neighboring triangles (using the hash-table query function), and
recurse on neighboring triangles whose orientation was still UNKNOWN.

I implemented this for a normal-finding program that is being shipped
with Silicon Graphic's Iris Inventor.  Here's the edge classes I used;
the rest of the code wouldn't be useful to you since it is built on
top of Iris Inventor:

struct Edge
{
    Edge::Edge() { v1 = v2 = (-1); }
    long v1, v2;
    FaceList faces;

Quote:};

class EdgeDict
{
  public:
    EdgeDict(int initial_size = 500);
    ~EdgeDict();

    void Add(Face *, long v1, long v2);

    void OtherFaces(Face *, long v1, long v2, FaceList &result);

  private:

    // Add to hash table.  Will create an entry if necessary.
    Edge *Enter(long v1, long v2);

    // Search for an edge; returns NULL if not found
    Edge *Find(long v1, long v2);

    int HashFunc(long v1, long v2);
    void ReHash(int new_size);

    Edge *hash_table;
    int n_hash; // length of hash table
    int n_edges;        // # of edges added to hash table

Quote:};

--


 
 
 

1. reordering layers

hi,

I would like to know if there is a way to move several layers at one
time so I can reorganize my layers.  I trying to build a template for
a webpage and I would like to keep all of the layers for each button
together or it gets very messy.

my method was to create the layers until I got the effect I wanted the
copy the layer and move the image into place.  with 4 layers for every
button (for mouseovers) and 15 buttons the list gets difficult to
follow.

Or maybe someone has a better suggestion for what I'm doing???

thanks
dave

2. Conference on Virtual Systems and MultiMedia '97 (CFP)

3. polygon modelling reorder??

4. Which G3 for Lightwave?

5. WTB: Digital Disk Reorder (DDR)

6. programming openGL on Windows ?

7. Digital Disk Reorder (DDR)

8. batch rendering won't work

9. reorder objects alphabeticly

10. Reordering a Boned Hierarchy, is it possible?

11. reordering inconsitently oriended triangles in a mesh

12. I reordered Hash..AM and now happy of sorts

13. reordering the atributes in channel box