vtkVoronoiCore3D.h

Go to the documentation of this file.

// SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
// SPDX-License-Identifier: BSD-3-Clause
#ifndef vtkVoronoiCore3D_h
#define vtkVoronoiCore3D_h

#include "vtkLocatorInterface.h"   // Interface to spatial locators
#include "vtkPoints.h"             // for input points
#include "vtkSMPTools.h"           // SMP parallel processing
#include "vtkShellBinIterator.h"   // Iteration over the bins of the locator
#include "vtkStaticPointLocator.h" // for locating nearby points
#include "vtkVoronoiCore.h"        // Core includes
#include "vtkVoronoiHull.h"        // Generate Voronoi convex hulls

VTK_ABI_NAMESPACE_BEGIN

struct vtkVoronoiClassifier3D
{
  // Optional regions ids for point classification.
  const int* Regions;

  // Constructors
  vtkVoronoiClassifier3D()
    : Regions(nullptr)
  {
  }
  vtkVoronoiClassifier3D(const int* regions)
    : Regions(regions)
  {
  }

  // Method required by vtkVoronoiCore3D.
  void Initialize(vtkVoronoiClassifier3D* c)
  {
    if (c)
    {
      this->Regions = c->Regions;
    }
  }

  // Method required by vtkVoronoiCore3D.
  const vtkVoronoiSpoke* AddAdjacencyInformation(vtkVoronoiHull& hull, vtkVoronoiWheelsType& wheels,
    vtkVoronoiSpokesType& spokes, int& numSpokes, int& maxPoints, int& maxFaces);

  // Method required by vtkVoronoiCore3D. By default, any region id >= 0 is
  // considered a valid inside region (<0 region values are reserved for
  // algorithm use). If no region ids have been specified, than the point
  // ptId is inside an interior region.
  bool IsInsideRegion(vtkIdType ptId)
  {
    if (!this->Regions)
    {
      return (ptId >= 0);
    }
    else
    {
      return (ptId >= 0 && this->Regions[ptId] >= 0);
    }
  }

  // Method required by vtkVoronoiCore3D. Determine if the two points
  // ptId and neiId (which form a spoke) are in the same region. It is
  // assumed that both (ptId,neiId >= 0), i.e., inside.
  bool IsSameRegion(vtkIdType ptId, vtkIdType neiId)
  {
    return (!this->Regions || this->Regions[ptId] == this->Regions[neiId]);
  }
}; // vtkVoronoiClassifier3D

template <class TCompositor, class TClassifier>
struct vtkVoronoi3DLocalData
{
  vtkIdType ThreadId;                         // assign a thread id [0,NumThreadsUsed)
  int MaxPoints;                              // the maximum number of points in any hull
  int MaxFaces;                               // the maximum number of faces in any hull
  int NumPrunes;                              // total number of pruning operations
  vtkBatchIdsType LocalBatches;               // list of batches processed by this thread
  vtkVoronoiSpokesType LocalSpokes;           // connecting edges/spokes for each hull
  vtkShellBinIterator SIter;                  // iterator over static point locator bins
  vtkVoronoiHull Hull;                        // computational 3D Voronoi hull algorithm
  typename TCompositor::LocalData Compositor; // gather data from compositing operations
  TClassifier Classifier;                     // Used to classify spokes (based on regions)

  vtkVoronoi3DLocalData()
    : ThreadId(-1)
    , MaxPoints(0)
    , MaxFaces(0)
    , NumPrunes(0)
  {
    this->LocalBatches.reserve(2048);
    this->LocalSpokes.reserve(2048);
  }
}; // vtkVoronoi3DLocalData

template <class TCompositor, class TClassifier>
using ThreadMapType = std::vector<vtkVoronoi3DLocalData<TCompositor, TClassifier>*>;

template <class TCompositor, class TClassifier = vtkVoronoiClassifier3D>
class vtkVoronoiCore3D
{
public:
  static std::unique_ptr<vtkVoronoiCore3D<TCompositor, TClassifier>> Execute(vtkAlgorithm* filter,
    unsigned int batchSize, vtkStaticPointLocator* loc, vtkPoints* inPts, double padding,
    vtkIdType maxClips, bool validate, double pruneTol, TCompositor* comp, TClassifier* cl);


  int GetNumberOfThreads() { return this->NumberOfThreads; }
  vtkVoronoi3DLocalData<TCompositor, TClassifier>* GetThreadData(int threadNum)
  {
    return this->ThreadMap[threadNum];
  }


  int GetMaximumNumberOfPoints() { return this->MaximumNumberOfPoints; }
  int GetMaximumNumberOfFaces() { return this->MaximumNumberOfFaces; }
  int GetNumberOfPrunes() { return this->NumberOfPrunes; }

  vtkVoronoiAdjacencyGraph& GetAdjacencyGraph() { return this->Graph; }

  vtkVoronoiCore3D(vtkAlgorithm* filter, vtkVoronoiBatchManager& batcher,
    vtkStaticPointLocator* loc, vtkPoints* inPts, double padding, vtkIdType maxClips, bool validate,
    double pruneTol, TCompositor* comp, TClassifier* c);


  void Initialize();
  void operator()(vtkIdType batchId, vtkIdType endBatchId);
  void Reduce();

  TCompositor Compositor;

  TClassifier Classifier;

  vtkVoronoiBatchManager Batcher;
  ThreadMapType<TCompositor, TClassifier> ThreadMap;

  vtkVoronoiAdjacencyGraph Graph;

  vtkIdType GetNumberOfPoints() { return this->NPts; }
  const double* GetPoints() { return this->Points; }

  vtkAlgorithm* Filter;

private:
  vtkIdType NPts;                 // The number of input points
  vtkPoints* InPoints;            // Input points as data array
  const double* Points;           // Input points as pointer to x-y-z AOS doubles
  vtkStaticPointLocator* Locator; // Used to (quickly) find nearby points
  double Padding;                 // The padding distance around the bounding box
  double Bounds[6];               // locator bounds
  double PaddedBounds[6];         // the domain over which Voronoi is calculated
  vtkIdType MaxClips;             // Limit the number of half-space clips

  // Enable pruning of spokes (equivalent to deletion of a degenerate hull face)
  bool Validate;            // Indicate whether to explicitly validate the mesh
  vtkIdType NumberOfPrunes; // If pruning is on, keep track of the number of prunes
  double PruneTolerance;    // Specify the spoke prune tolerance

  // High-level information captured during processing
  int NumberOfThreads;       // Keep track of the number of threads used durinf processing
  int MaximumNumberOfPoints; // Maximum numper of points in a generated Voronoi hull
  int MaximumNumberOfFaces;  // Maximum number of faces (i.e., spokes) in a generated Voronoi hull

  // Storage local to each thread, as well as working/scratch arrays. We
  // don't want to allocate working arrays on every thread invocation. Thread
  // local storage saves lots of new/delete (e.g. the locator tuples).
  vtkSMPThreadLocal<vtkDist2TupleArray> Dist2Tuples;
  vtkSMPThreadLocal<vtkVoronoi3DLocalData<TCompositor, TClassifier>> LocalData;

  using vtkBinIterator = vtkShellBinIterator;
  bool BuildHull(vtkVoronoiHull& hull, vtkBinIterator* siter, const double* pts, vtkIdType maxClips,
    vtkDist2TupleArray& results, int& numPrunes);

public:
  struct ProduceWheelsAndSpokes
  {
    vtkVoronoiCore3D<TCompositor, TClassifier>* VC;
    ProduceWheelsAndSpokes(vtkVoronoiCore3D<TCompositor, TClassifier>* vc);
    void operator()(vtkIdType threadId, vtkIdType endThreadId);

    // Invoke the production of wheels and spokes
    static void Execute(vtkVoronoiCore3D<TCompositor, TClassifier>* vc);
  }; // ProduceWheelsAndSpokes

  struct TopologicalMerge
  {
    vtkVoronoiCore3D<TCompositor, TClassifier>* VC;
    TopologicalMerge(vtkVoronoiCore3D<TCompositor, TClassifier>* vc);

    vtkMergeTuples3DType MergeTuples; // temporary array for merging points
    vtkMergeMapType MergeMap;         // maps tile/hull point ids to merged point ids
    vtkIdType NumMergedPts;           // after merging, the number of points remaining

    vtkIdType GetNumberOfMergedPoints() { return this->NumMergedPts; }

    // Core Voronoi methods in support of vtkSMPTools
    void Initialize() {}
    void operator()(vtkIdType threadId, vtkIdType endThreadId);
    void Reduce();

    // Execute the topological point merge to produce a merge map.
    static std::unique_ptr<TopologicalMerge> Execute(
      vtkVoronoiCore3D<TCompositor, TClassifier>* vc);
  }; // TopologicalMerge

}; // vtkVoronoiCore3D

struct vtkEmptyVoronoi3DCompositor
{
  void Initialize(vtkIdType vtkNotUsed(numPts), vtkEmptyVoronoi3DCompositor*) {}
  void Finalize() {}

  struct LocalData
  {
    void Initialize(vtkEmptyVoronoi3DCompositor* vtkNotUsed(c)) {}
    void AddData(vtkVoronoiHull& vtkNotUsed(hull), int vtkNotUsed(numSpokes),
      const vtkVoronoiSpoke* vtkNotUsed(spokes))
    {
    }
  };
}; // vtkEmptyVoronoi3DCompositor

// Almost minimal classifier - just records the hull's number of points and faces. It also
// considers regions if any are defined -- this is optional in some cases.
struct vtkEmptyVoronoi3DClassifier
{
  // Optional region ids
  const int* Regions;

  // Constructor
  vtkEmptyVoronoi3DClassifier()
    : Regions(nullptr)
  {
  }
  vtkEmptyVoronoi3DClassifier(const int* regions)
    : Regions(regions)
  {
  }

  // Initialize
  void Initialize(vtkEmptyVoronoi3DClassifier* c)
  {
    if (c)
    {
      this->Regions = c->Regions;
    }
  }

  // Method required by vtkVoronoiCore3D. This vtkEmptyClassifier provides
  // the minimum information needed.
  const vtkVoronoiSpoke* AddAdjacencyInformation(vtkVoronoiHull& hull, vtkVoronoiWheelsType& wheels,
    vtkVoronoiSpokesType& vtkNotUsed(spokes), int& numSpokes, int& maxPoints, int& maxFaces)
  {
    wheels[hull.PtId] = hull.NumFaces; // numFaces == numSpokes
    maxPoints = (hull.NumPts > maxPoints ? hull.NumPts : maxPoints);
    maxFaces = (hull.NumFaces > maxFaces ? hull.NumFaces : maxFaces);
    numSpokes = 0;
    return nullptr;
  }

  // If no region ids are provided, all processed points are inside the same
  // region.
  bool IsInsideRegion(vtkIdType ptId)
  {
    if (!this->Regions)
    {
      return (ptId >= 0);
    }
    else
    {
      return (ptId >= 0 && this->Regions[ptId] >= 0);
    }
  }
  bool IsSameRegion(vtkIdType ptId, vtkIdType neiId)
  {
    return (!this->Regions || this->Regions[ptId] == this->Regions[neiId]);
  }
}; // vtkEmptyVoronoi3DClassifier

VTK_ABI_NAMESPACE_END
#include "vtkVoronoiCore3D.txx"

#endif
// VTK-HeaderTest-Exclude: vtkVoronoiCore3D.h