Loading a model into a half-edge data structure from a .PLY file

Question

I am attempting to build a .PLY parser to load 3d models stored as .ply files into a half edge data structure mesh.

Sorry for the huge question, I'm very verbose and I wanted to make sure I laid out all the details. Because of this, I'll restate my ultimate goals immediately, just so users can see can get an idea of what i want before reading the giant block of text to follow.

1) What would be a good hash for memoizing half-edges from a .PLY file's vertex and face list

or

2) Is there a better approach to filling my half-edge structure from the data in a .PLY file?

---

The .PLY file lists the vertices, followed by the faces of the mesh. The obvious solution is to fill in the vertice table first, then generate the edge table using the faces list. The problem is that every edge has a partner edge, so for a quad-mesh, the first quad I load in will require 8 half edges. This isnt initially a problem, simply create the four half-edges for the face and reverse each edge to make their partner half edge. The problem here is that this creates 4 dangling half edges that associate with 4 different faces.

So there are two methods of attack: First generate all edges for the faces, then try to pair up partner edges. I really dont like this approach, it seems programmatically less efficient as it will involve a lot of searching and sorting.

Second: proceed as first stated: start with the first face specified and generate the edges required to create the polygon, and as the edges are created also create their twins. However, we'll memoize the edge list, so all edges will hash into a table. Then, when we generate edges for the other faces, if an edge is already generated (because it's a partner edge for a previous loaded face), we will simply grab the pointer out of the table.

This is where I'm stuck. I need an intelligent hashing function for memoizing my edge list. Collisions need to be minimized to increase efficiency. The scheme that I have in mind right now is to name* edges based on the two vertices that created them, IE edges 01 and 10 are twins. The worst case scenario would create a hash table in which all vertices could possibly be joined, and this would end up being size 2^n where n = number of vertices, which is completely unacceptible. My goal is to have the hash as close to the number of actual edges ( = sum of number of edges per face) while still minimizing collisions.

*Note: because half-edges enforce a "Counter-clockwise ONLY" draw scheme, it is not possible to have a name collision. By naming edges based on the two vertices that draw them, we insure that all names are unique to a single half-edge.

Answer 1

Are you storing indices or references in the edge? If you use incides, wouldn't a trivial hash function like

19 * index0 + 7 * index1

be "good enough"? If your hash was supposed to be symmetric, I'd go for a simple XOR of the two indices, but as half-edges are indeed directed you're probably better off using an asymmetric hash and looking specifically for the paired edge direction.

As actually comparing two edges is a relatively cheap operation (i.e. cheaper than generating a complex hash), collissions are not as aweful as you make them seem.

That is, in my experience. Ready to be burned by real hashing experts here. :-)

As a sidenote: you might want to make sure your hashtable implementation is decent with deletes, as it might pay off to remove any paired edge you find from the table.

Answer 2

I'm very verbose

You might want to to something about that.

A trivial way to has an edge is by the indexes of its two vertices. To make it unique take the smaller index first and the larger index second. Something like this:

uint hash(const Vertex& v1, const Vertex& v2)
{
    int i1 = v1.index;
    int i2 = v2.index;
    if (i1 > i2)
        swap(i1, i2);
    return (i1 | (i2 << 16));
}

In the actual data pointed by this hash table you will probably want to keep track of which pair you've seen already and which pair (the opposite one) you're expecting.