On Aug 7, 2:51 pm, "Bartc" <(E-Mail Removed)> wrote:

> Your idea of having a 100-million-million-element set or array is not

> practical to do in a simple way; using sparse arrays or databases (as soscpd

> suggested) is going to slow things down.

>

> How fast do you want this test to be?

>

> Depending on how your triangles are stored, you might as well just examine

> them without building any table. (I take it each triangle is defined as 3

> edge indices, and each edge by 2 vertex indices? Or is the triangle defined

> also by 3 vertices?)

>

> A hash function does not need to give a unique result; only reasonably well

> spread. However even such a table is going to need a lot of memory:

>

> How many entries will there be? I'm guessing 3 entries per triangle (A:B,

> A:C, A) which will include duplicating some information (so there will be

> a B:A in there somewhere). So about 30 million entries. Each entry is 2 ints

> (8 bytes); and with some extra capacity in the table, this will be at least

> 300Mbytes.

>

> My original idea was to store 3 ints per triangle: total cost about

> 120Mbytes. So the options include:

>

> Store no extra info, just analyze your existing data to see if A:B touch;

> cost: 0Mbytes;

> Store touching indices with each triangle; cost: 120Mbytes;

> Hash table: cost: 300Mbytes

> Simple bit-matrix: cost: 12.5million million bytes.

>

> All getting a little faster, or would be if the 12,500 Gbytes was feasible.

>
Hi, I think it should be reasonably fast. Because in my project there

are few pre processing steps to be carried out before the calculation

begins:

- Read mesh file and allocate memory for triangles, vertices etc.

- Traverse the lists to build edge list.

- From the list of edges, determine the list of sharp edges and

corenrs in the object.

Step no 2 takes massive amount of time because of the two passes. If

the mesh is very coarse with large number of vertices and triangles,

the user will have to wait for a huge time before any actual

calculation begins.

The triangle is represented by 3 indices into the vertex array:

v0 v1 v2

v0 to v1 is edge 1

v1 to v2 is edge 2

v2 to v0 is edge 3.

This is my data structure for a edge :

typedef struct

{

size_t triangle_index[2];

size_t vertex_index[2];

}edge;

triangle index will be storing the indices of neighbouring triangles

( exactly 2 in a non manifold mesh) which share this edge. Vertex

index array stores the vertex indices of the end points of the edge.

This is my program for building edge list and you can clearly see the

problem of 2 passes.

void build_edge_list(void)

{

size_t i, j;

size_t iv0, iv1, it0, it1;

node *ptr;

edge *e;

/* PASS 1 ON LIST OF TRIANGLES */

for (i = 0; i < mesh_ptr->ntri; i++)

{

for (j = 0; j < 3; j++)

{

iv0 = mesh_ptr->tri[i].v[j];

iv1 = mesh_ptr->tri[i].v[(j + 1) % 3];

if (iv0 < iv1)

{

add_to_list(&mesh_ptr->edge_list);

mesh_ptr->edge_list->data = malloc(sizeof(edge));

assert(mesh_ptr->edge_list->data != NULL);

e = (edge *)mesh_ptr->edge_list->data;

e->vertex_index[0] = iv0;

e->vertex_index[1] = iv1;

e->triangle_index[0] = i;

e->triangle_index[1] = i;

}

}

}

/* SECOND PASS ON LIST OF TRIANGLES */

for (i = 0; i < mesh_ptr->ntri; i++)

{

for (j = 0; j < 3; j++)

{

iv0 = mesh_ptr->tri[i].v[j];

iv1 = mesh_ptr->tri[i].v[(j + 1) % 3];

if (iv0 > iv1)

{

ptr = mesh_ptr->edge_list;

while (ptr != NULL)

{

e = (edge *)ptr->data;

if (e->vertex_index[0] == iv1)

{

if (e->vertex_index[1] == iv0)

{

if (e->triangle_index[0] == e-

>triangle_index[1])
{

e->triangle_index[1] = i;

}

}

}

ptr = ptr->next;

}

}

}

}

}

Basically what this algorithm does is it traverses list of triangles

and passes through every edge. Edges that satisfy iv0 < iv1 are put

into the list of edges. Its vertex indices are iv0 iv1 in that order

The other corresponding edge is obviously iv1 iv0. Lets call both

those components as half -edges. For this edge, record the same

triangle index for both entries.

In the next pass, we are only interested in edges where iv1 > iv0.

Then we pass linearly through the edge list and compare the vertex

indices with the edge vertex indices. If there is a match, then we

have found the other half edge with opposite orientation. Make the

necessary change in triangle index.