regarding Voronoi:

Voronoi cells are connected.

This means one gets manifolds and the half edge mesh system chokes on that.

Voro++ uses the bag of cells approach. But there is no further relation between
the cells. That's a pity. While constructing the voronoi pattern we gather data
about neigbours. These can be put in a record/struct together with the vertex
and face data of the cell. This makes it possible to traverse through the voroni
cells. The halfe edge datastructure can still be used for the single cell mesh.
Simplified:

VornoiCell = object
  geometry: ConvexPolyhedron  // halfedgemesh or just array of vertices & faces
  seedPoint: Vec3
  neighbors: seq[CellID]     // adjacent cells
  sharedFaces: Table[CellID, FaceID]  // which face is shared with which
neighbour

VoronoiBag = objec
  cells: Table[CellID, VoronoiCell] // if cellId is ordered, seq[VoroinoCell]


Then I thought, what if we transpose the (half) edge to a higher dimension.
That/what would be a half face/facet mesh datastructure. Very implified:

type
  HalfFace = object
    face: Face                   // geometric face (vertices, normal, etc.)
    adjacentCell: CellID         // which cell this half-face belongs to
    twinHalfFace: HalfFaceID     // opposite half-face in neighboring cell
    nextAroundCell: HalfFaceID   // next face around this cell

  VoronoiMesh = object
    halfFaces: List<HalfFace>
    cells: List<Cell>            // each cell references its half-faces


pattern :
1D: vertices bind line segments
2D: edges bind faces
3D: faces bind volumes/cells
4D: volumes would bind 4D regions

Half-edge works for 2D as edges are the boundaries between faces
Half-face makes sense for 3D as faces are the boundaries between cells
Half-volume would work for 4D as volumes are the boundaries between 4D cells?

for n-dimensional mesh elements (n-1)-faces separate n-dimensional regions?


After some searching it is actually something that exists to create 3d connected
mesh' : OpenVolumeMesh
https://www.graphics.rwth-aachen.de/software/openvolumemesh/

The choice depends on the goal,

ingo

Post a reply to this message