# Problem understanding the edge list generating algorithm

I don’t understand the condition i3 < i1 in the following code segment.

If I draw a simple triangle like the following

``````     i3
/  \
/    \
i1-----i2
``````

where i1, i2 and i3 are indices into the vertex table e.g. i1 = 0, i2 = 1, i3 = 2.

If I try the code on that triangle I end up with two egdes e1 for i1<i2 and e2 for i2<i3 but shouldn’t there be three edges so the e3 for i3 to i1.

This is the code from Eric Lengyels website and book so it should be correct - but could please someone explain to me why there is this condition and I get 2 edges for this triangle instead of what I think would be more correct 3 edges.

Thanks

``````
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;
long i2 = triangle->index;
long i3 = triangle->index;

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

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

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

triangle++;
}

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

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

edge++;
}
}

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

edge++;
}
}

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

edge++;
}
}

triangle++;
}

return (edgeCount);
}
``````

I read the article again and it says that only closed triangle meshes (2 manifolds) are allowed thus a plain triangle does not produce correct results

I read the article again and it says that only closed triangle meshes (2 manifolds) are allowed thus a plain triangle does not produce correct results

I have no idea. Maybe he wants you to buy his book to find out?

“For algorithmic details, see Mathematics for 3D Game Programming & Computer Graphics, Section 10.3.”

Just remove all those if cases and it’ll work better. I asked him and he explained it to me.

The problem was that I forgot the fact that this works on closed meshes - 2manigfolds …

each edge is associated to 2 faces and this won’t work with my 2 triangles anyway I used a slightly different method that works fine.

long i1 = triangle->index;
long i2 = triangle->index;
long i3 = triangle->index;

if (i1 > i2) {
}
if (i2 > i3) {
}
if (i3 > i1) {
}

I don’t understand how the ordering of vertex index relates to a closed mesh?

(i1 > i2) implies there’s something special about how the vertex indices are
ordered. I don’t see the relationship.

here is an algorithm using quicksort. first we define the structures we need:

``````#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct {
float	x, y, z;
int	id; } Node;

typedef struct {
Node	*N;
int	id; } Tria;

typedef struct {
Node	*N;
Tria	*T;
bool	free; } Edge;

Node	N;
Tria	T;
Edge	E;

int	num_trias = 100000, num_free_edges;

``````

now a function which creates 3 edges for each triangle.

``````void GenerateEdges() {

for(int i = 0; i < num_trias; i ++) {

for(int j = 0; j < 3; j ++) {
Node	*N1 = T[i].N[j];
Node	*N2 = T[i].N[(j+1)%3];

E[3*i+j].T = &T[i];

if(N1->id < N2->id) {
E[3*i+j].N = N1;
E[3*i+j].N = N2; }
else {
E[3*i+j].N = N2;
E[3*i+j].N = N1; } } } }
``````

in each edge, N is the node with the lower id and N is the one with the higher id. this makes it easier to find out if two edges are exactly the same:

``````int CompareEdges(const void *v1, const void *v2) {
Edge	*E1 = (Edge*)v1, *E2 = (Edge*)v2;

if(E1->N->id < E2->N->id)
return(-1);

else if(E1->N->id > E2->N->id)
return(1);

if(E1->N->id < E2->N->id)
return(-1);

else if(E1->N->id > E2->N->id)
return(1);

return(0); }
``````

this function sorts all edges by their node ids, compares all edges and marks those which appear twice as ‘not free’ (E[i].free = false)

``````void FindFreeEdges() {

for(int i = 0; i < 3*num_trias; i ++)
E[i].free = true;

qsort(&E, 3*num_trias, sizeof(Edge), CompareEdges);

for(int i = 0; i < 3*num_trias-1; i ++) {
if(CompareEdges((const void*)&E[i], (const void*)&E[i+1]) == 0) {
E[i].free = false;
E[i+1].free = false; } }

num_free_edges = 0;

for(int i = 0; i < 3*num_trias; i ++) {
if(E[i].free == true)
num_free_edges ++; } }
``````

and finally the main program part. it assigns consecutive ids to 255 nodes and assigns random nodes to <num_trias> triangles.

then it creates edges for the trias, finds the free edges and prints them.

``````void PrintEdges() {

for(int i = 0; i < 3*num_trias; i ++) {
if(E[i].free == true)
printf("	F ");
else
printf("	  ");

printf("TRIA %i : NODE %4i x %4i
", i/3, E[i].N->id, E[i].N->id); } }

int main(int argc, char *argv[]) {

for(int i = 0; i < 256; i ++)
N[i].id = i;

for(int i = 0; i < num_trias; i ++) {

T[i].N = &N[random()&0xff];
T[i].N = &N[random()&0xff];
T[i].N = &N[random()&0xff]; }

GenerateEdges();
FindFreeEdges();
PrintEdges();

printf("
%i FREE EDGES FOUND

", num_free_edges); }

``````

I thought I almost understood it, but then I lost it.

What do you mean by ‘free’ edge?

it is meant like this: an object is made up of many triangles, each of them has 3 edges.
so my algorithm creates a list of 3*number_of_triangles edges and sorts them. if an edge
appears more than once in the list, it is shared by at least 2 triangles and thereby not a
“real” edge. but if an edge appears only once it is a “real” edge (which i called
“free” edge; maybe i gave it the wrong name…).
the free edges are the ones you want to find, the others are internal.

Ok, I think I understand now.

You can probably also give each edge a ref_count too instead of flagging them.
That is, increment how many times an edge is referenced by a triangle.