Constructing half-edges table from triangle list without hash

Question

Motivation

I am trying to refine a mesh such that each triangle gets subdivided into 4 triangles, but I want the vertices to be shared. For that purpose I need a half-edge data structure so I can count and address the vertices on the edges properly. The problem below is formulated a bit more generally - it just assumes a given index list, and doesn't even provide the vertices coordinates. The problem is in 3D, so sorting based on angles for DCEL construction will not work.

Problem Statement

I am given an index list $T = [i_{0}, i_{1}, i_{2}, \ldots, i_{3(n-1)}, t_{3(n-1)+1}, t_{3(n-1)+2}]$ of triplets of vertex indices corresponding to a specific triangle. Here $i_{3k+j}$ is the index of the $j$-th vertex in the $k$-th triangle (I have $n$ triangles in the above). I define $n(j) = 3\cdot\lfloor j/3\rfloor + \bigl(((j \text{ mod } 3)+1)\text{ mod }3\bigr)$. This cyclically gives me the next index belonging to the same triangle. For example:

$$n(0) = 1, \,n(1) = 2,\, n(2) = 0,\, n(3) = 4, \, n(4) = 5,\, n(5) = 3, \ldots$$
I want to build a half-edge table: a table such that $(h(j) = k)\land (h(k) = j) \iff (i_j = i_{n(k)})\land (i_{n(j)}=i_k)$. Given a half-edge index $j$ it returns the index corresponding to the half-edge in the opposite triangle. I am trying to avoid using a hash table since I don't have a nice implementation in C and I don't plan to implement my own (though if you have any good suggestions for hash table code I'll gladly have a look, but that's outside the scope of the question really - I will still be curious about suggestions not using a hash table even if I have one).

My Algorithm

What I came up with is to iterate over all triangles and count the number of triangles per vertex (meaning I have an array $nt(i) = \text{# adjacent triangles to vertex $i$}$, for $0\leq i \leq m-1$, where $m$ is the number of vertices). Once I have the count I can allocate a compressed row storage matrix with $nt(i)$ elements per vertex ($row(i) = nt(i-1) + row(i-1)$), and fill a triangle adjacency matrix $A$ with the indices of the adjacent triangles. Then for each vertex in the matrix I can go over pairs of its triangles ($C^{nt(i)}_{2}$ such pairs) and link those that share an edge (in a closed mesh I can even sort them). As long as $n(i)$ is not too large this is not very problematic. For simplicity one may assume that the mesh is manifold (an edge has no more than two adjacent faces) and that it is orientable (no funny Mobius strip stories), although I think the latter is not as important as I don't care about the orientation of the halfedges, I just need face adjacency.

Question

My question is whether someone has any better ideas for an algorithm, or suggestions for improvements of the above (or pointing out a mistake)?

Answer 1

I worked some more on this, and the comparisons complexity can be reduced at the expense of memory. To make this work I made arrays of the indices of the outgoing and incident half-edges for each vertex. Then the array with outgoing half-edges can be sorted according to the indices of the vertices at situated at the heads of the outgoing half-edges, and the array with the incident half-edges can be sorted according to the indices of the vertices at the tails of the incident half-edges. Then for an oriented closed manifold triangulation, the elements with the same index in the two sorted arrays will be twin half-edges. For a non-closed manifold the comparison can be done in linear time.

It seems like a hash is entirely unnecessary.