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.
