Voronoi 3D Manual

Table of Contents

• About
• Voronoi3DInterface
• CellData
• Example
• Further Reading

About

A Voronoi pattern segments the space into separate cells defined by a list of points. The maxon::Voronoi3DInterface allows to segment 3D space into such Voronoi cells.

Voronoi3DInterface

The maxon::Voronoi3DInterface allows to collect points and to create 3D Voronoi cells around these points.

• maxon::Voronoi3DInterface::Init(): Initializes the Voronoi object for the given volume.

The points stored in the Voronoi object are handled with:

• maxon::Voronoi3DInterface::SetPoints(): Sets the list of points to the given array of point coordinates.
• maxon::Voronoi3DInterface::AddPoint(): Adds the given point.
• maxon::Voronoi3DInterface::AddPoints(): Adds the given array of points.
• maxon::Voronoi3DInterface::SetCellFuseGroup(): The given points will be fused to one cell in generation.
• maxon::Voronoi3DInterface::GetInputPoints(): Returns the internally stored points.

The calculation of Voronoi cells is divided into two steps:

• maxon::Voronoi3DInterface::CalcTetrahedralization(): Calculates tetrahedralization (see Delaunay 3D Manual).
• maxon::Voronoi3DInterface::CalcCells(): Calculates Voronoi cells.
• maxon::Voronoi3DInterface::IsReady(): Returns true if the data structure is ready.
• maxon::Voronoi3DInterface::IsReadyButPendingChanges(): Returns true if the data structure is ready, even through the data might need recalculation.

The created cells are accessed with:

• maxon::Voronoi3DInterface::GetCellCount(): Returns the number of Voronoi cells.
• maxon::Voronoi3DInterface::GetCellDataStructure(): Returns the array of maxon::CellData elements.
• maxon::Voronoi3DInterface::ScaleCell(): Scales the cell with the given index.
• maxon::Voronoi3DInterface::ScaleAllCells(): Scales all cells.
• maxon::Voronoi3DInterface::FuseCells(): Fuses the cell pairs of the given list.
• maxon::Voronoi3DInterface::GetCellHasVolume(): Returns a list of flags with the information if a cell has a volume.
• maxon::Voronoi3DInterface::GetBorderCellFlags(): Returns a list of flags with the information if a cell is a border cell.
• maxon::Voronoi3DInterface::GetVoronoiPointPositions(): Returns an array of point positions.

Further functions are:

• maxon::Voronoi3DInterface::SetForClipping(): Will trigger some extra calculations in the Voronoi algorithm.
• maxon::Voronoi3DInterface::GetDelaunayTetrizer(): Returns the internal Delaunay3D tetrahedralization class. See Delaunay 3D Manual.
• maxon::Voronoi3DInterface::CreateInvertedVoronoiCell(): Inverts the whole Voronoi data structure.
• maxon::Voronoi3DInterface::Flush(): Resets the object for a new calculation.
• maxon::Voronoi3DInterface::CopyFrom(): Copies the data from the given object.

CellData

A maxon::CellData object represents a single Voronoi cell:

• maxon::CellData::GetVertices(): Returns the array of the cell's vertices.
• maxon::CellData::GetEdges(): Returns the array of the cell's edges (maxon::CellEdge).
• maxon::CellData::GetFaces(): Returns the array of the cell's faces. A face is defined by the first edge index.
• maxon::CellData::GetAdjacentCells(): Returns the array of indices of the adjacent cells.
• maxon::CellData::GetBoundingBox(): Returns the bounding box of the cell.

A given cell can be handled with:

• maxon::CellData::ScaleCell(): Scales the cell.
• maxon::CellData::FixGeometry(): Checks the current cell data structure and optimizes it.
• maxon::CellData::CreateCellFaceNormal(): Returns the normal for the given face index.
• maxon::CellData::AddCellData(): Adds the data of the given cell to this one.
• maxon::CellData::IsComplex(): Returns true if the cell is complex.
• maxon::CellData::TestPointWithCell(): Returns true if the given point is within the cell.

Two cells can be merged with:

• maxon::CellData::MergeCells(): Merges the given cell into this one.
• maxon::CellData::FuseCells(): Fuses the given cell into this one.

Further functions are:

• maxon::CellData::CopyFrom(): Copies the data from the given cell.
• maxon::CellData::Reset(): Resets this cell to an empty cell.
• maxon::CellData::Flush(): Resets this cell to an empty cell but keeps memory.

An edge within a cell is defined as a maxon::CellEdge:

• maxon::CellEdge::_start: Index of the edge's start point.
• maxon::CellEdge::_end: Index of the edge's end point.
• maxon::CellEdge::_nextEdgeOfFace: Index of the next edge.
• maxon::CellEdge::_prevEdgeOfFace: Index of the previous edge.

Example

  // This example creates 3D Voronoi cells around the given points.
  // The resulting geometry is copied to PolygonObjects.
 
  // calculate size of the workspace which covers all points
 
  MinMax mm;
  for (maxon::Int i = 0; i != points.GetCount(); ++i)
  {
    mm.AddPoint(points[i]);
  }
 
  maxon::Range<maxon::Vector> workspace;
  const maxon::Vector         buffer(100.0, 100.0, 100.0);
  workspace.minValue = mm.GetMin() - buffer;
  workspace.maxValue = mm.GetMax() + buffer;
 
  // create and init Voronoi3DRef
  const maxon::Voronoi3DRef voronoi = maxon::Voronoi3DRef::Create() iferr_return;
  voronoi.Init(workspace) iferr_return;
 
  // add points
  voronoi.AddPoints(points) iferr_return;
 
  // calculate result
  voronoi.CalcTetrahedralization() iferr_return;
  voronoi.CalcCells() iferr_return;
 
  // check success
  const maxon::Bool voronoiNotReady = !voronoi.IsReady();
  if (MAXON_UNLIKELY(voronoiNotReady))
    return maxon::UnexpectedError(MAXON_SOURCE_LOCATION);
 
  // get cell data
  maxon::BaseArray<maxon::CellData>& curCellData = voronoi.GetCellDataStructure() iferr_return;
 
  // random generator for object color
  maxon::LinearCongruentialRandom<maxon::Float32> randomGen;
 
  // for each cell create a PolygonObject
  for (auto& cell : curCellData)
  {
    // check if the cell does not have "infinite" vertices in case of border cells
    auto CheckCell = [workspace](const maxon::CellData& cellArg) -> maxon::Bool
                     {
                       const auto& vertices = cellArg.GetVertices();
                       for (const maxon::Vector& pos : vertices)
                       {
                         if (!workspace.Contains(pos))
                           return false;
                       }
                       return true;
                     };
 
    // create PolygonObject for the given cells
    if (CheckCell(cell))
    {
      const maxon::BaseArray<maxon::Vector>& vertices = cell.GetVertices();
      const Int32 vertexCount = (Int32)vertices.GetCount();
 
      // allocate PolygonObject
      PolygonObject* const polygonObject = PolygonObject::Alloc(vertexCount, 0);
      if (polygonObject != nullptr)
      {
        // prepare Modeling object to create ngons
        AutoAlloc<Modeling> modeling;
        if (modeling == nullptr)
          return maxon::OutOfMemoryError(MAXON_SOURCE_LOCATION);
 
        modeling->InitObject(polygonObject);
 
        // set points
        for (maxon::Int32 i = 0; i < vertexCount; ++i)
        {
          modeling->SetPoint(polygonObject, i, vertices[i]);
        }
 
        // set ngons
 
        const maxon::BaseArray<Int>& faces = cell.GetFaces();
        const maxon::BaseArray<maxon::CellEdge>& edges = cell.GetEdges();
        const maxon::Int faceCount = faces.GetCount();
 
        // for each face create a ngon
        for (maxon::Int i = 0; i < faceCount; ++i)
        {
          // set start edge
          maxon::Int       currentEdgeIndex = faces[i];
          const maxon::Int startEdgeIndex = currentEdgeIndex;
 
          // array to store the ngon's vertex indices
          maxon::BaseArray<maxon::Int32> ngonIndices;
 
          // loop over all edges of the ngon
          do
          {
            // append first vertex index
            const maxon::CellEdge& edge = edges[currentEdgeIndex];
            ngonIndices.Append((Int32)edge._start) iferr_return;
 
            // get next edge
            currentEdgeIndex = edge._nextEdgeOfFace;
 
          } while (startEdgeIndex != currentEdgeIndex);
 
          // create ngon
          const Int32 ngonIndexCount = (Int32)ngonIndices.GetCount();
          if (ngonIndexCount > 0)
          {
            modeling->CreateNgon(polygonObject, ngonIndices.GetFirst(), ngonIndexCount, MODELING_SETNGON_FLAG_TRIANGULATE);
          }
        }
 
        // finalize polygon object
        modeling->Commit(polygonObject, MODELING_COMMIT_TRINGONS);
 
        // create random color
        auto GetRandomColor = [&randomGen]() -> maxon::Vector
                              {
                                maxon::Vector color;
                                color.x = (randomGen.Get01() * 0.5) + 0.5;
                                color.y = (randomGen.Get01() * 0.5) + 0.5;
                                color.z = (randomGen.Get01() * 0.5) + 0.5;
                                return color;
                              };
 
        // set object color
        polygonObject->SetParameter(ID_BASEOBJECT_USECOLOR, ID_BASEOBJECT_USECOLOR_ALWAYS, DESCFLAGS_SET::NONE);
        polygonObject->SetParameter(ID_BASEOBJECT_COLOR, GetRandomColor(), DESCFLAGS_SET::NONE);
        // insert object into the scene
        doc->InsertObject(polygonObject, nullptr, nullptr);
      }
    }
  }

Further Reading

• Modeling