benchmark and optimize Half-Edge implementation
The current implementation of half-edge datastructure is based on index-redirections, i.e.
struct HalfEdge
{
using IndexType = unsigned long int;
// an index representing unset entities or neighbours
static constexpr IndexType invalid = IndexType(-1);
// half edges
IndexType next_ = invalid;
IndexType previous_ = invalid;
IndexType opposite_ = invalid;
// entities
IndexType vertex_ = invalid;
IndexType edge_ = invalid;
IndexType face_ = invalid;
}
Can we reduce some of the fields? Is an implementation based on pointers a better choice?
struct HalfEdge {
HalfEdge* next;
HalfEdge* previous;
HalfEdge* opposite;
EntitySeed vertex;
EntitySeed edge;
EntitySeed face;
};
where EntitySeed
might be a Dune::EntitySeed
type to create real entities from.
What about rewriting an array of structs to a struct of arrays?
A slightly different datastructure is explained in Tyler J. Alumbaugh and Xiangmin Jiao: "Compact Array-Based Mesh Data Structures"
TODO: This needs to be benchmarked. Several implementations should be compared.