I am curious how the last algorithm is an order of magnitude faster than the one based on sorting. There is no benchmark data, and ideally there should be data for different mesh sizes, as that affects the timing a lot (cache vs RAM).
I work on https://github.com/elalish/manifold which works with triangular meshes, and one of the slowest operations we currently have is halfedge pairing, I am interested in making it faster.
We are already using parallel merge sort for the stable sort, switching to parallel radix sort which works well on random distribution is not helping and I think we are currently bandwidth bound. If building an edge list for each vertex can improve cache locality and reduce bandwidth, that will be very interesting.
I work on https://github.com/elalish/manifold which works with triangular meshes, and one of the slowest operations we currently have is halfedge pairing, I am interested in making it faster. We are already using parallel merge sort for the stable sort, switching to parallel radix sort which works well on random distribution is not helping and I think we are currently bandwidth bound. If building an edge list for each vertex can improve cache locality and reduce bandwidth, that will be very interesting.