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:};

--