search

BrunoLevy / geogram

a programming library with geometric algorithms
Other
1.9k stars 129 forks source link

Data structure wiki notes feedback #37

Closed Zireael07 closed 2 years ago

Zireael07 commented 2 years ago

Reading through the code and the design notes (because I'm thinking to implement my own AIF structure) and I have some questions that weren't answered in the admittedly amazingly written wiki page.

1) Why the idea of local edge and local vertex? Why not just use the global indices? 2) You claim half edges use more memory, what's the memory footprint of this data structure? Halfedges are 4 pointers (or indices) per edge, 1 per face (the adjacident edge) and 1 per vertex (the incident edge)

BrunoLevy commented 2 years ago

  1. because when you want to find let's say the three vertices of triangle t in a mesh M, you are going to ask for M.facets.vertex(t,0), M.facets.vertex(t,1) and M.facets.vertex(t,2), then 0,1,2 are local indices, and M.facets.vertex() returns the global index it corresponds to. Put differently, a given (global) vertex is shared by all the triangles incident to it;

  2. not only you can use 32-bit indices (whereas pointers are 64-bits), but also halfedge data structures are often allocated element by element, and if you do a new for each element, then the memory allocator makes you pay the "taxes" (several 10th of bytes per allocation !). Well, OK, you can design a specialized allocator (like in CGAL) and gain a bit, but you will also need to have a container with the pointers to all the items. Some folks looove halfedges, because they think that each atomic operation should run in O(1), and I think it is not optimal ! What's important is that a batch of N operations runs in O(N), and you can do that with arrays (with a well-written reordering function). More on this in my Eurographics 2017 keynote presentation.

  3. the early implementation of GEOGRAM (that I wrote in the 2000's) was using halfedges. Then I attended a conference in meshing for finite element modeling (international meshing roundtable), and some folks showed me software that was 10x faster than mine, I asked them what magic data structure they were using, and they answered "no data structure at all, just plain old arrays and indices in FORTRAN77".

  4. with arrays, some operations are extremely simpler:

    • copying a mesh: memcpy()
    • reading a mesh from file: fread()
    • displaying a mesh: glVertexArray(); glDrawArrays();
    • parallel traversal of a mesh: #pragma omp parallel for

Imagine just the nightmare of copying a mesh represented with halfedges allocated as separate elements, then you need a std::map to track the references, not only the code is much more complicated, but also it runs in O(N log(N)) instead of O(N). Same thing for reading a file (well, you can be smarter and chain hafledges incident to each vertex, but again the code is much more complicated than with arrays). Iterating in parallel on a data structure stored as linked lists can be also difficult...

Seeing that I have completely rewritten my "computer graphics 101" course, and it no longer mentions halfedges (except for one task: it is sometimes convenient when you need to walk along the border of a surface, or it can also be used as an abstraction when designing certain algorithms, but to me in most cases I do not want to take them "seriously" as a concrete data structure).