9
$\begingroup$

For 2D polygonal meshes, the QuadEdge and HalfEdge data structure representations are sufficient to store and enable efficient query of all topological and incidence information. Are there compact and efficient data structures for 3D polyhedral meshes? I know there has been some recent work on compact representations for tetrahedral meshes, like, for example SOT. I don't know enough about these to know if they generalize to unstructured non-tetrahedral meshes.

I can imagine that half-edges might generalize to half-faces with associated half-edges, but it seems like that is a lot of data to store, and there might be more compact representations. I should add that I really only care about retrieving facet information (like which facets are on the boundary, which facets belong to a certain cell); the edge incidence information is not as useful.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

There is an extension of half-edge in any dimension, called darts in combinatorial maps. There are two packages in CGAL allowing to use these combinatorial maps in any dimension (see here for combinatorialMaps and here for LinearCellComplex).

You can use this data structure to represent any Quasi manifold orientable subdivided 3D object. Quoting from CGAL webpage(section 2.4 Combinatorial Map Properties):

A quasi-manifold object is defined as:

A dD quasi-manifold is an object obtained by taking some isolated d-cells, and allowing to glue d-cells along (d-1)-cells.

and orientable as:

It is orientable if it is possible to embed it in the Euclidean space and to define a global "left" and "right" direction in each point of the embedded object.

Improve this answer
$\endgroup$
3
  • $\begingroup$ How does this compare with Dobkin & Laszlo's FacetEdge representation? That seems to be the only other thing I can find. $\endgroup$
    – Victor Liu
    Commented Dec 20, 2012 at 21:37
  • 1
    $\begingroup$ They are equivalent. In FacetEdge representation, there are mainly 3 functions: clock, Enext and Fnext; and in a 3D combinatorial map, there are 3 functions $\beta_1$, $\beta_2$ and $\beta_3$. $\endgroup$
    – gdamiand
    Commented Dec 21, 2012 at 8:36
  • 1
    $\begingroup$ Note that this site is about computer science, not library implementations. As such, we appreciate answers who contain ideas and concepts, not just references to implementations. $\endgroup$
    – Raphael
    Commented May 28, 2014 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.