# Constructing half-edges table from triangle list without hash

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)?