6

I've written a module in my application that creates a mesh from existing coordinate and face data. The number of vertices in the mesh could easily exceed 10 million and the same goes for the faces.

The problem with the raw data is that the faces are defined by the coordinates of their vertices and not the index of the vertices in the vertex data. So the connectivity of face to vertex has to be extracted upon creation o the mesh.

One issue that is very important in this application is smooth rendering of this mesh in OpenGL. for this purpose, I need to detect the "surface" faces of this mesh, because rendering all the faces including the invisible ones makes the rendering process very time consuming and not practical.

In order to detect the outer surface of the mesh, I need to count how many elements each face belongs to. The faces that are only in one element are considered to be the surface faces and will be rendered. So I need to avoid having duplicate faces in the mesh.

Right now, I'm using a Tree with a comparator that sorts the vertices by X, then Y, then Z. Using this tree I can check for existence of each vertex and avoid adding duplicates and assign a unique id to each unique vertex. Another tree sorts the faces by the index of their vertices. This way duplicate faces are not added either. This setup works fine and I can detect the surfaces correctly using the connectivity of faces and elements.

But here's the problem; when the number of vertices and faces reaches 1e6 or more, these two trees can take up to 1~2 gigabytes of memory, which is very undesirable.

My questions are:

  1. Is there a better algorithm to detect the surface faces of a huge mesh?
  2. Is there a better data structure to achieve the desired outcome?
  • 2
    Some unclear points - are the faces triangles? What do you mean by "element"? – Doc Brown Aug 25 '15 at 5:33
  • Hi, By element I mean volume (Tetrahedral, Hexahedral, etc...) – Mostafa Zeinali Aug 25 '15 at 9:18
  • The system is designed to handle any type of face and element, so the faces can be Triangles in which case the elements are most likely Tetrahedrons, and the faces can be quadrilaterals, in which case the elements would be Hexahedral. – Mostafa Zeinali Aug 25 '15 at 9:21
  • In my current case, my faces are quadrilateral and elements are hexahedral. (btw it's bad that Stack's dictionary doesn't recognize hexahedron as a valid word) – Mostafa Zeinali Aug 25 '15 at 9:26
  • 1
    Can you do a rough pass that breaks the mesh into sub meshes? You could then process those individually. – aglassman Aug 28 '15 at 1:44
2

First Tree

[...] these two trees can take up to 1~2 gigabytes of memory, which is very undesirable.

What I recommend here is going to seem odd and dumb, but it's playing to constants more rather than scalability. I've beaten professionally-written K-D trees with this dumb approach in C++ for tens of millions of vertices, but just for this peculiar case of finding duplicates points.

For the first tree (finding which vertex indices are associated to a face), build some NxNxN grid, say 100x100x100. That's going to result in 1,000,000 grid cells which sounds astronomical...

... except each grid cell just stores a single index: 4 megabytes -- phew!

// Don't actually use a class here (wasteful), using it for clarity.
class GridCell
{
    // Index to head node.
    int head;
}

Each cell stores a pointer (index) to a grid node. A grid node looks like this:

// Don't actually use a class here (wasteful), using it for clarity.
class GridNode
{
    // Index to source vertex.
    int vertex;

    // Index to next node.
    int next;
}

This means an overhead of 8 bytes per vertex. At 10 mil vertices, that comes out to 80 megabytes. We're basically modeling a singly-linked list per cell using just indices.

So your actual grid looks like this:

class Grid
{
    // 1,000,000 cells = 4 megabytes
    // Set these initially to -1 to indicate the end of the list.
    private int[][][] cells = new int[100][100][100];

    // 10,000,000 vertices = 40*2 = 80 megabytes
    private int[][] nodes = new int[num_verts][2];

    // Can use this to try inserting a new vertex.
    private int vertex_count = 0;

    // Grid extents (AABB)
    private float[] bmin = new float[3];
    private float[] bmax = new float[3];
}

And that's it, 80 megabytes for 10 mil vertices plus 4 megabytes for a million cells plus 24 bytes for the bounding box (plus a trivial amount of memory for Java object metadata and possible padding for alignment). The total is just a little over 84 megabytes.

Now start off encompassing a bounding box for all the vertices you have. I wasn't sure if you had the vertex positions with the vertices in addition, or only face data. Either way, loop through either of those and compute a bounding box extents that fits everything and initialize your grid.

Next, start inserting each vertex into the grid at the cell it belongs. You can find the cell index for a dimension like so:

int grid_cell_x(float point_x)
{
    // Unit size of grid (bbox size divided by grid dimension).
    float grid_unit_x = (bmax[0] - bmin[0]) / 100.0f;

    // Return point position on grid (truncated to integer: floored).
    return (int)((point_x - bmin[0]) / grid_unit_x);
}

... something like this (and hopefully not duplicated for all 3 dimensions, and with some pre-computed values if necessary to avoid division and stuff -- can micro-tune as needed).

When inserting the vertex, first search through this singly-linked list to see if there's a vertex in the same position. If so, skip and possibly return the index for the existing vertex. If the vertex with the same coordinates doesn't exist, then you can insert it to the list: simply set the next index of the grid node for the vertex to the grid cell head index, and then set the grid cell head index to the grid node index (just singly-linked list insertion using indices).

Pseudocode:

int grid_pos[3] = grid_index(vertex.position)
for each node in cell(grid_pos), n:
    if vertices[n.vertex].position == vertex.position:
        return n.vertex

add new node -- get node_index
node.next = flat_index(grid_pos)
node.vertex = vertex_index
cell(grid_pos).head = node_index

Apologies, that's a really coarse example that leaves a lot to fill in between the lines. But I hope it's enough to fill in the rest. We're basically just searching through a singly-linked list for the grid cell in which a vertex lands looking for duplicated vertices. It only gets roundabout because we're using indices to avoid object overhead and also get a 32-bit size.

And tada -- you have a million-cell grid which only takes 84 megabytes for 10 million vertices. I've found this works better than octrees and k-d trees, including ones that I didn't write myself. It impressed people so much that we ended up replacing a k-d tree implementation with this seemingly-stupid solution in a commercial software. It even fares well for edge cases where you might think it won't, like a mesh with very uneven density (though there could be a really pathological case where these other spatial indexing structures could fare better, like a million vertices all near-coincident with one outlier vertex to mess up the whole thing in which it would almost certainly fare much worse).

You can also adjust the grid size, and it doesn't have to be uniform. 100x100x100 is a decent starting point, and should be pretty quick for even tens of millions of vertices (what I often test around). The solution I use is a little more complex than this adjusting the grid cell count based on mesh density and bounding box size, but it's still pretty simple.

Most of all, it's very predictable -- constant time 3-dimensional chained hash table-like searches, big old array to make it easy how much memory is used (and using very little even with so many cells).

So I'd suggest this. If not, k-d tree or octree works quite well, but you need to tune those (especially octree) and impose max depth limits and such to keep it from using explosive memory like the tree you are currently using.

Second Tree

For the second tree, a considerably better solution is simple. Don't use a tree at all to sort. Just use a big old array and sort that and then do a linear pass checking next elements for consecutive duplicate faces. A balanced BST is very wasteful if all you are going to use it for is to sort data one time and dispose of it.

Anyway, I hope this helps a bit. I glossed over some fine details for brevity, but it should be pretty easy to figure out.

  • 1
    Wow!! Thanks a lot. I need to read this a couple of times, but this seems to be a very very gr8 solution. Thanks for all the time and effort my friend. – Mostafa Zeinali Feb 14 '16 at 6:10
  • 1
    I'll implement this ASAP and get beck to you with the results. – Mostafa Zeinali Feb 14 '16 at 6:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.