Delaunay 3D Manual

Table of Contents

• About
• Delaunay3DInterface
• Tetrahedron
• Example
• Further Reading

About

A Delaunay triangulation connects a set of points with lines so that a given point is connected to its neighbors. The 3D extension maxon::Delaunay3DInterface allows to fill the space between points with tetrahedrons.

Note

This class is used inside the maxon::Voronoi3DInterface, see Voronoi 3D Manual.

Delaunay3DInterface

The maxon::Delaunay3DInterface collects the given points and computes the tetrahedrons filling the space between these points.

An object is initialized with:

• maxon::Delaunay3DInterface::Init(): Initialized the object for the given volume.
• maxon::Delaunay3DInterface::IsInitialized(): Returns true if Init() has been called.

Points are added to the object with:

• maxon::Delaunay3DInterface::AddPointsIntoTetrahedralization(): Adds an array of points.
• maxon::Delaunay3DInterface::AddPointIntoTetrahedralization(): Adds a single point.

The calculation of the tetrahedrons is performed with:

• maxon::Delaunay3DInterface::CalculateDelaunayTetrahedralization(): Performs the final calculation or updates the result if new points have been added.

The resulting geometry data is accessed with:

• maxon::Delaunay3DInterface::GetTetrahedrons(): Returns an array of maxon::Tetrahedron elements.
• maxon::Delaunay3DInterface::GetTetrahedronCopy(): Fills the given array with copies of the maxon::Tetrahedron elements.
• maxon::Delaunay3DInterface::GetTetrahedronCount(): Returns the number of maxon::Tetrahedron elements.
• maxon::Delaunay3DInterface::GetPointCount(): Returns the number of points.
• maxon::Delaunay3DInterface::GetPoints(): Returns an const array of point coordinates.
• maxon::Delaunay3DInterface::GetPointsWrite(): Returns an array of writeable point coordinates.
• maxon::Delaunay3DInterface::GetPointsToTetConnections(): Used by the Voronoi-calculation.

The tetrahedron containing a given point can be obtained with:

• maxon::Delaunay3DInterface::FindTetIndexContainingPoint(): Returns the index of the tetrahedron containing the given point.
• maxon::Delaunay3DInterface::FindTetContainingPoint(): Returns the index of the tetrahedron containing the given point.

Miscellaneous functions are:

• maxon::Delaunay3DInterface::CopyFrom(): Copies the data of the given Delaunay object.
• maxon::Delaunay3DInterface::Reset(): Resets the object.
• maxon::Delaunay3DInterface::Flush(): Flushes all data. Requires an new call of Init() to re-use.

Tetrahedron

A maxon::Tetrahedron object represents a tetrahedron filling the space between the points of the Delaunay object. The class gives access to the tetrahedron's points and faces:

• maxon::Tetrahedron::GetFacePoints(): Gets the points of the given face index.
• maxon::Tetrahedron::GetPointIndexOfTwoPoints(): Returns the point indices of the given global points.
• maxon::Tetrahedron::GetPointIndexOfPoint(): Returns the local point indices of the given global point.
• maxon::Tetrahedron::GetPointOppositeFace(): Returns the index of the point opposite of the given face index.
• maxon::Tetrahedron::GetPointOppositeNeighbour(): Returns the index of the point that is opposite of the face with the given neighbour index.
• maxon::Tetrahedron::GetFacePointsWithNeighbor(): Sets a list of points that build up the face with the given neighbour.
• maxon::Tetrahedron::GetFaceWithPoints(): Returns the face index for the three given points.
• maxon::Tetrahedron::GetFaceIndexSharingTwoPointsButNotInputFace(): Returns the face index for the two given points.
• maxon::Tetrahedron::GetFaceWithNeighbor(): Returns the face index for the given neighbour index.
• maxon::Tetrahedron::GetFaceOppositePoint(): Returns the face index opposing the given point index.

Further functions are:

• maxon::Tetrahedron::ChangePointToOtherPoint(): Changes the point index for one point.
• maxon::Tetrahedron::CalcBarycentricOfPoint(): Returns the barycentric coordinates for a point in relation to this tetrahedron.
• maxon::Tetrahedron::CalcBarycentricOfPoint2(): Returns the barycentric coordinates for a point in relation to this tetrahedron.

Example

  // This example fills the space between the given points with
  // tetrahedron polygons using the Delaunay triangulation.
  // 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 Delaunay3DRef and perform tetrahedralization
  maxon::Delaunay3DRef delaunay3D = maxon::Delaunay3DRef::Create() iferr_return;
  delaunay3D.Init(workspace) iferr_return;
  delaunay3D.AddPointsIntoTetrahedralization(points) iferr_return;
  delaunay3D.CalculateDelaunayTetrahedralization() iferr_return;
 
  // access resulting geometry
  const maxon::BaseArray<maxon::Tetrahedron>& tetrahedrons = delaunay3D.GetTetrahedrons();
  const maxon::BaseArray<Vector>& pointsArray = delaunay3D.GetPoints();
 
  maxon::LinearCongruentialRandom<maxon::Float32> randomGen;  // random generator for object colors
 
  const maxon::Int tetrahedronPoints = 4;
  const maxon::Int tetrahedronFaces  = 4;
 
  // for each tetrahedron create a PolygonObject
  for (const maxon::Tetrahedron& tetrahedron : tetrahedrons)
  {
    // ignore tetrahedron that includes "internal" points (0 - 3)
    auto CheckTetra = [=](const maxon::Tetrahedron& tetra) -> maxon::Bool
                      {
                        const maxon::Int internalVertice = 4;
                        for (maxon::Int i = 0; i < tetrahedronPoints; ++i)
                        {
                          if (tetra.points[i] < internalVertice)
                            return false;
                        }
                        return true;
                      };
 
    // create PolygonObject for the given tetrahedron
    if (CheckTetra(tetrahedron))
    {
      // alloc PolygonObject
      PolygonObject* const polyObject = PolygonObject::Alloc(tetrahedronPoints, tetrahedronFaces);
      if (polyObject != nullptr)
      {
        CPolygon* const polygons = polyObject->GetPolygonW();
        Vector*   const polyPoints = polyObject->GetPointW();
 
        if (polygons && polyPoints)
        {
          // set vertices
          for (maxon::Int i = 0; i < tetrahedronPoints; ++i)
          {
            const maxon::Int pointIndex = tetrahedron.points[i];
            polyPoints[i] = pointsArray[pointIndex];
          }
 
          // set polygons
          for (maxon::Int32 i = 0; i < tetrahedronFaces; ++i)
          {
            // get global face points
            maxon::IntVector32 tetraPoints;
            tetrahedron.GetFacePoints(i, tetraPoints);
            // set local points
            polygons[i].a = tetrahedron.GetPointIndexOfPoint(tetraPoints.x);
            polygons[i].b = tetrahedron.GetPointIndexOfPoint(tetraPoints.y);
            polygons[i].c = tetrahedron.GetPointIndexOfPoint(tetraPoints.z);
            polygons[i].d = tetrahedron.GetPointIndexOfPoint(tetraPoints.z);
          }
        }
 
        // update geometry
        polyObject->Message(MSG_UPDATE);
 
        // 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
        polyObject->SetParameter(ID_BASEOBJECT_USECOLOR, ID_BASEOBJECT_USECOLOR_ALWAYS, DESCFLAGS_SET::NONE);
        polyObject->SetParameter(ID_BASEOBJECT_COLOR, GetRandomColor(), DESCFLAGS_SET::NONE);
        // insert object into the scene
        doc->InsertObject(polyObject, nullptr, nullptr);
      }
    }
  }

Further Reading

• Modeling
• BaseArray Manual
• Vectors