Velocity Reviews > A suggestion on data structures.

# A suggestion on data structures.

pereges
Guest
Posts: n/a

 08-07-2008
On Aug 7, 4:14 pm, "Bartc" <(E-Mail Removed)> wrote:

> Just to clarify, your input includes all the vertices, and specifies all the
> triangles in terms of those vertices?
>
> So your real problem (the one you were considering the huge 1e7 x 1e7 array
> for) is building the edge table (your struct edge) quickly?

Yes vertices are given by their 3d coordinates(x, y, z)

eg:

vertex 0 5.666788 4.555677 -2.333333
vertex 1 ............................
vertex 2 ............................
........
........
vertex n-1

Triangles are represented as 3 indices into vertex list above:

triangle 0 12 0 1
triangle 1 4 5 6
..........
...........
triangle m-1

I'm just looking for an overall quicker method. Adjacency matrix is
just one idea that I used long back when the mesh was extremely
small(Atmost 50-60 triangles and 25-30 vertices). But this is useless
now as I'm testing bigger meshes.

Bartc
Guest
Posts: n/a

 08-07-2008

"pereges" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> On Aug 7, 4:14 pm, "Bartc" <(E-Mail Removed)> wrote:
>
>> Just to clarify, your input includes all the vertices, and specifies all
>> the
>> triangles in terms of those vertices?
>>
>> So your real problem (the one you were considering the huge 1e7 x 1e7
>> array
>> for) is building the edge table (your struct edge) quickly?

>
> Yes vertices are given by their 3d coordinates(x, y, z)

> I'm just looking for an overall quicker method. Adjacency matrix is
> just one idea that I used long back when the mesh was extremely
> small(Atmost 50-60 triangles and 25-30 vertices). But this is useless
> now as I'm testing bigger meshes.

OK. In your second pass, for each edge of each triangle (ie 30million
times), you seem to be scanning the entire edge list looking for iv0, iv1.

That's clearly inefficient. At least, the edge list can be sorted and a
binary search can be done. Or it can be created as a binary tree in the
first place. (Or as a hash as in earlier suggestions.)

(Simply sorting the edge list will already clump together the duplicate
edges, perhaps simplifying the second pass.)

I don't quite understand the half-edge business. Otherwise I would do this
lookup in the first pass: building the edge list so that it is already
sorted (by iv0:iv1), and only adding new edges if they are not already in
the list. This way there wouldn't be duplicated edges, and you might not
need that second pass.

--
Bartc

soscpd
Guest
Posts: n/a

 08-07-2008
Hello Pereges, List

On Aug 7, 7:35 am, pereges <(E-Mail Removed)> wrote:

> Yes vertices are given by their 3d coordinates(x, y, z)

> vertex 0 5.666788 4.555677 -2.333333

> Triangles are represented as 3 indices into vertex list above:

> triangle 0 12 0 1

I can assume vertex 0 is to triangle 0?

Kinda

typedef struct
{
double vertex[2];
int triangle[2];
} matrix_dot;

Should I assume triangle values to be between 0 and ...? What about
vertex?

Do you have all input's (vertex/triangle) already in a file? No on-
demand data at all?

Rafael

Wolfgang Draxinger
Guest
Posts: n/a

 08-07-2008
pereges wrote:

> You still have to make nv passes here.

No. In the worst case you need malloc(rows * cols). However this
is a first order example of a sparse matrix, for which efficient
memory patterns exist.

http://en.wikipedia.org/wiki/Sparse_matrix

Wolfgang Draxinger
--
E-Mail address works, Jabber: http://www.velocityreviews.com/forums/(E-Mail Removed), ICQ: 134682867

pereges
Guest
Posts: n/a

 08-08-2008
Ok, I managed to do this in another fast way.

For every vertex, now I have a shared triangle list. That is a list of
triangles that share this particular vertex. So when I need to find
out the triangles shared by an edge, all I need to do is :

1. Go to the edge end points v0 and v1.
2. Look in the shared triangle lists of v0 and v1 to find out exactly
two common triangles.

Building a shared triangle list is not at all difficult. While reading
the triangle vertex indices (v0, v1, v2), just go to these individual

This is my vertex structure:

typedef struct
{
size_t index;
vector p;
vector normal;
int corner_flag;
sharing this vertex */
}vertex;

The three vertex indices of some triangle nt given by iv0, iv1, iv2:

iv0 = mesh_ptr->tri[nt].v[0];
iv1 = mesh_ptr->tri[nt].v[1];
iv2 = mesh_ptr->tri[nt].v[2];

Add to list of shared triangles at every vertex :

mesh_ptr->vert[iv0].shared_tri->data = &mesh_ptr->tri[nt];

mesh_ptr->vert[iv1].shared_tri->data = &mesh_ptr->tri[nt];

mesh_ptr->vert[iv2].shared_tri->data = &mesh_ptr->tri[nt];

As you can see, this hardly takes any time because you are doing this
simultaneously as
the triangle vertex indices were being read from the ascii file.

Now the algorithm for building the edge list:

void build_edge_list2()
{
size_t i, j, k;
size_t iv0, iv1, it0, it1;
edge *e;
node *ptr1, *ptr2;

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)
{
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;

ptr1 = mesh_ptr->vert[iv0].shared_tri;
k = 0;

while (ptr1 != NULL)
{
it0 = ((triangle *)ptr1->data)->index;
ptr2 = mesh_ptr->vert[iv1].shared_tri;

while (ptr2 != NULL)
{
it1 = ((triangle *)ptr2->data)->index;

if (it0 == it1) /* Common triangle found*/
{
e->triangle_index[k++] = it0;
break;
}

ptr2 = ptr2->next;
}

if (k == 2)
{
/* No point in traversing the list further
once two
common triangles are found */
break;
}
ptr1 = ptr1->next;
}
}
}
}
}

This approach is incredibly fast as opposed to the previous one. I
clocked the time needed to construct the list and in the first case it
took about 16 seconds and in the second code its less than 1 second.
The most obvious advantage is that the second pass over the list of
triangles is not required nor is the second pass over the edge list
needed. Just one pass and the edge list gets created as we pass
through the list of triangles. The only disadvantage is probably the
extra space needed for storing the link list of shared triangles. But
anyway, I believe it is better to have lists like this for other
calculations like vertex normals where the vertex normal has to be
calculated by taking contribution from all surrounding triangles. If
need arises, then one can delete the linklist after all such
calculations are done to free space in the middle of the program.

pereges
Guest
Posts: n/a

 08-08-2008
Ok, I managed to do this in another fast way.

For every vertex, now I have a shared triangle list. That is a list of
triangles that share this particular vertex. So when I need to find
out the triangles shared by an edge, all I need to do is :

1. Go to the edge end points v0 and v1.
2. Look in the shared triangle lists of v0 and v1 to find out exactly
two common triangles.
3. These two common triangles are the ones shared by the edge between
v0 and v1.

Building a shared triangle list is not at all difficult. While reading
the triangle vertex indices (v0, v1, v2), just go to these individual

This is my vertex structure:

typedef struct
{
size_t index;
vector p;
vector normal;
int corner_flag;
sharing this vertex */

}vertex;

The three vertex indices of some triangle nt given by iv0, iv1, iv2:

iv0 = mesh_ptr->tri[nt].v[0];
iv1 = mesh_ptr->tri[nt].v[1];
iv2 = mesh_ptr->tri[nt].v[2];

Add to list of shared triangles at every vertex :

mesh_ptr->vert[iv0].shared_tri->data = &mesh_ptr->tri[nt];

mesh_ptr->vert[iv1].shared_tri->data = &mesh_ptr->tri[nt];

mesh_ptr->vert[iv2].shared_tri->data = &mesh_ptr->tri[nt];

As you can see, this hardly takes any time because you are doing this
simultaneously as
the triangle vertex indices were being read from the ascii file.

Now the algorithm for building the edge list:

void build_edge_list2()
{
size_t i, j, k;
size_t iv0, iv1, it0, it1;
edge *e;
node *ptr1, *ptr2;

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)
{
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;

ptr1 = mesh_ptr->vert[iv0].shared_tri;
k = 0;

while (ptr1 != NULL)
{
it0 = ((triangle *)ptr1->data)->index;
ptr2 = mesh_ptr->vert[iv1].shared_tri;

while (ptr2 != NULL)
{
it1 = ((triangle *)ptr2->data)->index;

if (it0 == it1) /* Common triangle found*/
{
e->triangle_index[k++] = it0;
break;
}

ptr2 = ptr2->next;
}

if (k == 2)
{
/* No point in traversing the list
after two common triangles are found */
break;
}
ptr1 = ptr1->next;
}
}
}
}
}

This approach is incredibly fast as opposed to the previous one. I
clocked the time needed to construct the list and in the first case it
took about 16 seconds and in the second code its less than 1 second.
The most obvious advantage is that the second pass over the list of
triangles is not required nor is the second pass over the edge list
needed. Just one pass and the edge list gets created as we pass
through the list of triangles. The only disadvantage is probably the
extra space needed for storing the link list of shared triangles. But
anyway, I believe it is better to have lists like this for other
calculations like vertex normals where the vertex normal has to be
calculated by taking contribution from all surrounding triangles. If
need arises, then one can delete the linklist after all such
calculations are done to free space in the middle of the program.

Bartc
Guest
Posts: n/a

 08-08-2008

"pereges" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> Ok, I managed to do this in another fast way.
>
> For every vertex, now I have a shared triangle list. That is a list of
> triangles that share this particular vertex. So when I need to find
> out the triangles shared by an edge, all I need to do is :
>
> 1. Go to the edge end points v0 and v1.
> 2. Look in the shared triangle lists of v0 and v1 to find out exactly
> two common triangles.

> This approach is incredibly fast as opposed to the previous one. I
> clocked the time needed to construct the list and in the first case it
> took about 16 seconds and in the second code its less than 1 second.

I'm surprised searching the entire edge list for each triangle edge is only

Or it's possible that looking at the local set of triangles per vertex is
not as fast as it could be; I'm guessing you're only doing a linear search
here. Apart from having to build the shared triangle list.

I still have a feeling that building the entire edge table during the first
pass, using a fast lookup method of all edges, could also be fast and
possibly faster.

> I believe it is better to have lists like this for other
> calculations like vertex normals where the vertex normal has to be
> calculated by taking contribution from all surrounding triangles.

Yes it would be difficult to create the vertex normal from just the vertex.

--
Bartc