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[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);
}

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[0];
long i2 = triangle->index[1];
long i3 = triangle->index[2];

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[3];
	int	id; } Tria;

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

Node	N[327680];
Tria	T[327680];
Edge	E[327680];

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[0] = N1;
			E[3*i+j].N[1] = N2; }
		else {
			E[3*i+j].N[0] = N2;
			E[3*i+j].N[1] = N1; } } } } 

in each edge, N[0] is the node with the lower id and N[1] 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[0]->id < E2->N[0]->id)
 	return(-1);

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

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

 else if(E1->N[1]->id > E2->N[1]->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[0]->id, E[i].N[1]->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[0] = &N[random()&0xff];
 	T[i].N[1] = &N[random()&0xff];
 	T[i].N[2] = &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.