# Building an edge list for arbitrary triangle mesh

10 replies to this topic

### #1 Guest_Eric Lengyel_*

• Guests

Posted 15 November 2005 - 03:00 PM

The following code builds a list of edges for an arbitrary triangle mesh. For algorithmic details, see Mathematics for 3D Game Programming & Computer Graphics, Section 10.3:

struct Edge
{
unsigned short		vertexIndex[2];
unsigned short		triangleIndex[2];
};

struct Triangle
{
unsigned short		index[3];
};

long BuildEdges(long triangleCount,
const Triangle *triangleArray, Edge **edgeArray)
{
// Allocate enough space to hold all edges
*edgeArray = new Edge[triangleCount * 3];

long edgeCount = 0;
Edge *edge = *edgeArray;

// First pass: find edges
const Triangle *triangle = triangleArray;
for (long a = 0; a < triangleCount; a++)
{
long i1 = triangle->index[0];
long i2 = triangle->index[1];
long i3 = triangle->index[2];

if (i1 < i2)
{
edge->vertexIndex[0] = i1;
edge->vertexIndex[1] = i2;
edge->triangleIndex[0] = a;
edge->triangleIndex[1] = a;
edgeCount++;
edge++;
}

if (i2 < i3)
{
edge->vertexIndex[0] = i2;
edge->vertexIndex[1] = i3;
edge->triangleIndex[0] = a;
edge->triangleIndex[1] = a;
edgeCount++;
edge++;
}

if (i3 < i1)
{
edge->vertexIndex[0] = i3;
edge->vertexIndex[1] = i1;
edge->triangleIndex[0] = a;
edge->triangleIndex[1] = a;
edgeCount++;
edge++;
}

triangle++;
}

// Second pass: match triangles to edges
triangle = triangleArray;
for (long a = 0; a < triangleCount; a++)
{
long i1 = triangle->index[0];
long i2 = triangle->index[1];
long i3 = triangle->index[2];

if (i1 > i2)
{
edge = *edgeArray;
for (long b = 0; b < edgeCount; b++)
{
if ((edge->vertexIndex[0] == i2) &&
(edge->vertexIndex[1] == i1) &&
(edge->triangleIndex[0] != edge->triangleIndex[1]))
{
edge->triangleIndex[1] = a;
break;
}

edge++;
}
}

if (i2 > i3)
{
edge = *edgeArray;
for (long b = 0; b < edgeCount; b++)
{
if ((edge->vertexIndex[0] == i3) &&
(edge->vertexIndex[1] == i2) &&
(edge->triangleIndex[0] != edge->triangleIndex[1]))
{
edge->triangleIndex[1] = a;
break;
}

edge++;
}
}

if (i3 > i1)
{
edge = *edgeArray;
for (long b = 0; b < edgeCount; b++)
{
if ((edge->vertexIndex[0] == i1) &&
(edge->vertexIndex[1] == i3) &&
(edge->triangleIndex[0] != edge->triangleIndex[1]))
{
edge->triangleIndex[1] = a;
break;
}

edge++;
}
}

triangle++;
}

return (edgeCount);
}


Visit http://www.terathon.com for information about the book and the C4 Engine.

### #2Reedbeta

DevMaster Staff

• 5308 posts
• LocationSanta Clara, CA

Posted 16 November 2005 - 08:28 PM

Forgive me, but I don't think this is very good code. For one thing, it is O(n^2) in the number of triangles. Using a hash table to store edges and their indices, you could achieve (expected) O(n) time with a single pass through the triangles. Second, you allocate about twice as much space as you need to for the edges; in a 2-manifold mesh, each edge is shared by two triangles. Of course, triangleCount*3 edges would still be needed for a soup of disconnected triangles, but you could control your memory usage much better by using a std::vector or similiar that only expands when it needs to. Which brings me to the third point, that your code is horrible C++; passing double pointers in the parameter, what gives? At the least that should be a reference to a pointer; and better, it should be a reference to a container class, like the aforementioned std::vector. Also, the triplication of code (bad for readability and maintenance) could be solved by judicious use of the % operator. All in all, the algorithm works but it could be written much better.
reedbeta.com - developer blog, OpenGL demos, and other projects

### #3bramz

Valued Member

• Members
• 189 posts

Posted 16 November 2005 - 08:35 PM

I second that!

PS, reedbeta: you bastard! :P
hi, i'm a signature viruz, plz set me as your signature and help me spread :)
Bramz' warehouse | LiAR isn't a raytracer

### #4bramz

Valued Member

• Members
• 189 posts

Posted 16 November 2005 - 08:43 PM

you don't really need the % either ... you can write a loop over the vertex indices as following:


for (size_t k1 = 2, k2 = 0; k2 < 3; k1 = k2++)

{

unsigned short i1 = triangle->vertices[k1];

unsigned short i2 = triangle->vertices[k2];

}



For once, there's actually a practical reason to use a postfix increment in a for loop statement! And the cute thing is, replace 2 and 3 by n-1 and n, and you can use it for n-sided polygons as well!

but i would agree that's a bit less readable than using the %

btw, i'm sure mixing unsigned short and longs causes some warnings?
hi, i'm a signature viruz, plz set me as your signature and help me spread :)
Bramz' warehouse | LiAR isn't a raytracer

### #5cm_rollo

New Member

• Members
• 6 posts

Posted 17 November 2005 - 02:44 AM

I agree that a hash-table implementation would have been better for large models, but this is a short snippet. It wouldnt have made sense to paste in a large chunk of hashing code since AFAIK there is no standard hash container in the STL yet? I agree on the other points though.

### #6Francois Hamel

Valued Member

• Members
• 86 posts

Posted 17 November 2005 - 03:27 AM

Reedbeta said:

Second, you allocate about twice as much space as you need to for the edges; in a 2-manifold mesh, each edge is shared by two triangles. Of course, triangleCount*3 edges would still be needed for a soup of disconnected triangles, but you could control your memory usage much better by using a std::vector or similiar that only expands when it needs to. Which brings me to the third point, that your code is horrible C++; passing double pointers in the parameter, what gives? At the least that should be a reference to a pointer;

1) Memory VS Speed and in this case Speed seems to be more of a concern (ok, let's not look at the algorithm). Letting a std::vector grows by itself would mean so much more allocations and possibly (gasp!) an even greater array than triangleCount*3 at the end! (but I agree though that resizing the array to fit "edgeCount" edges before returning would have been better)

2) Horrible C++ code? I don't think so. It may not be perfect but looking at the function it looks clear enough for me. I admit that I hate references to pointers and when a parameter can be modified or allocated, I prefer using a pointer is it much more clearer when you see the call to the function afterwards like:


void FooPointer(uint32 inParam, uint32* outParam);

void FooRef(uint32 inParam, uint32& outParam);

//first method

uint32 uiStuff = 1;

uint32 uiResult;

FooPointer(uiStuff,&uiResult);

//versus second method

uint32 uiStuff = 1;

uint32 uiResult;

FooRef(uiStuff,uiResult); //who can tell Result is being modified?



anyway that's just personnal taste maybe, I use references as well, just depend on the particular case. The most important thing for me when writing code is to write code that can be easily read afterwards and understood by a little kid with no programming experience whatsoever. Being a C++ purist to the bone doesn't make you a better programmer to work with.
I post with style, do you?

http://fhamel.blogspot.com/

### #7Reedbeta

DevMaster Staff

• 5308 posts
• LocationSanta Clara, CA

Posted 17 November 2005 - 05:32 AM

Francois Hamel said:

Letting a std::vector grows by itself would mean so much more allocations and possibly (gasp!) an even greater array than triangleCount*3 at the end!

That's true, but the effect can be mitigated by calling the vector's reserve function. Since we can be pretty sure that there will be at least triangleCount*3/2 edges, reserving that much space at the beginning would limit it to a single reallocation, at most (since std::vector grows by doubling, in most implementations).

Quote

I admit that I hate references to pointers and when a parameter can be modified or allocated, I prefer using a pointer is it much more clearer when you see the call to the function afterwards...

This is a matter of taste, but I have to disagree - a variable name like uiResult, or a simple one-line comment can make this clear; also, modern IDEs almost all allow you to mouseover a function call and see the function's signature, and a parameter type of non-const reference should be a sure sign that it is being used for output. Moreover, pointers allow NULL values to be passed in; in some cases this makes sense, but when you don't want to allow this you have to remember to include an assert() or something. References don't allow NULL values and so are instantly recognizable as meaning an output parameter that shouldn't be set to NULL.
reedbeta.com - developer blog, OpenGL demos, and other projects

### #8bramz

Valued Member

• Members
• 189 posts

Posted 17 November 2005 - 10:36 AM

cm_rollo said:

I agree that a hash-table implementation would have been better for large models, but this is a short snippet. It wouldnt have made sense to paste in a large chunk of hashing code since AFAIK there is no standard hash container in the STL yet? I agree on the other points though.

In absence of a hasp_map, you can always use a std::map. It's not as good, but still better than O(N^2). The pretty thing is, if you have hash_map that looks like an STL container (like STLport's), it's a simple subtitution to replace the map with the hash_map.
hi, i'm a signature viruz, plz set me as your signature and help me spread :)
Bramz' warehouse | LiAR isn't a raytracer

### #9bramz

Valued Member

• Members
• 189 posts

Posted 17 November 2005 - 10:41 AM

And because this thread has all the ingredients to become a good old flame on style: you should avoid the hungarian notation. http://www.cuj.com/d...slop/hyslop.htm

/me seeks cover now :)
hi, i'm a signature viruz, plz set me as your signature and help me spread :)
Bramz' warehouse | LiAR isn't a raytracer

### #10Axel

Valued Member

• Members
• 119 posts

Posted 21 November 2005 - 11:19 PM

Or just use boost::hash (http://www.boost.org.../html/hash.html)

### #11elengyel

Member

• Members
• 50 posts

Posted 03 December 2005 - 04:36 AM

Hi -- I just saw that this code had been posted (I didn't post it myself). I agree that this isn't very good code. It was written a long time ago to illustrate a simple way to build the edge list without getting too fancy to get running times down to O(n log n), and it was never meant to be used with large models. The code that I actually use in my engine nowadays stores the edges in a tree structure. I should probably update the code on the website...

#### 1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users