vtkPolyhedronContour.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 vtkPolyhedronContour_h
#define vtkPolyhedronContour_h

#include "vtkCommonDataModelModule.h" // For export macro
#include "vtkType.h"                  // For vtkIdType

#include "vtkSmartPointer.h"              // For vtkSmartPointer
#include "vtkStaticEdgeLocatorTemplate.h" // For vtkStaticEdgeLocatorTemplate

#include <array>         // For array
#include <cstdint>       // For int64_t
#include <unordered_map> // For unordered_map
#include <unordered_set> // For unordered_set
#include <vector>        // For vector

VTK_ABI_NAMESPACE_BEGIN

class vtkCellArray;
class vtkCellData;
class vtkDataArray;
class vtkIdList;
class vtkIncrementalPointLocator;
class vtkPointData;
class vtkPolygon;
class vtkPolyhedron;

class VTKCOMMONDATAMODEL_EXPORT vtkPolyhedronContour
{
public:
  vtkPolyhedronContour() = default;
  ~vtkPolyhedronContour() = default;

  enum class CellClassification
  {
    AllInside,
    AllOutside,
    Intersected
  };

  CellClassification Execute(vtkPolyhedron* cell, vtkDataArray* scalars, double isoValue,
    vtkIncrementalPointLocator* locator, vtkPointData* inPd, vtkPointData* outPd);

  int GetNumberOfIsoPolygons() const { return static_cast<int>(this->Result.IsoPolygons.size()); }

  int GetIsoPolygonSize(int polyIdx) const
  {
    return static_cast<int>(this->Result.IsoPolygons[polyIdx].size());
  }

  vtkIdType GetIsoPolygonVertex(int polyIdx, int vertIdx) const
  {
    return this->Result.IsoVertices[this->Result.IsoPolygons[polyIdx][vertIdx]].OutputPointId;
  }

  void OutputContours(vtkCellArray* polys, vtkCellData* inCd, vtkIdType cellId, vtkCellData* outCd);

  void OutputClip(vtkPolyhedron* cell, vtkCellArray* connectivity,
    vtkIncrementalPointLocator* locator, vtkPointData* inPd, vtkPointData* outPd, vtkCellData* inCd,
    vtkIdType cellId, vtkCellData* outCd, int insideOut, vtkCellArray* outFaces = nullptr,
    vtkCellArray* outFaceLocs = nullptr);

  //
  // Bulk API for integration with threaded filters (vtkContour3DLinearGrid,
  // vtkTableBasedClipDataSet). Operates on raw point coordinates and face
  // streams without instantiating vtkPolyhedron objects.
  //
  // - Contour: single-call ContourCell helper below.
  // - Clip: two-pass CountClip / EmitClip, where CountClip produces the edge
  //   intersection list fed into a shared vtkStaticEdgeLocatorTemplate before
  //   EmitClip writes final geometry with deduplicated iso-vertex IDs.
  //============================================================================

  static void ContourCell(vtkIdType numPointIds, const vtkIdType* pointIds,
    vtkCellArray* polyhedronFaces, vtkDataArray* points, vtkDataArray* scalars, double isoValue,
    bool generateTriangles, std::vector<vtkIdType>& polygonsSize,
    std::vector<EdgeTuple<vtkIdType, double>>& intersectedEdges);

  static void CountClip(vtkIdType numPointIds, const vtkIdType* pointIds,
    vtkCellArray* polyhedronFaces, vtkDataArray* scalars, double isoValue, bool insideOut,
    vtkIdType& numOutputCells, vtkIdType& numOutputCellConnectivity, vtkIdType& numOutputFaces,
    vtkIdType& numOutputFacesConnectivity,
    std::vector<EdgeTuple<vtkIdType, double>>& intersectedEdges);

  static void EmitClip(vtkIdType numPointIds, const vtkIdType* pointIds,
    vtkCellArray* polyhedronFaces, vtkDataArray* scalars, double isoValue, bool insideOut,
    vtkDataArray* pointMap, vtkIdType numberOfKeptPoints,
    const vtkStaticEdgeLocatorTemplate<vtkIdType, double>& edgeLocator, vtkCellArray* outputCells,
    vtkCellArray* outputFaces);

private:
  //============================================================================
  // Data Structures
  //============================================================================

  struct IsoVertex
  {
    vtkIdType OutsideVertex;        
    vtkIdType InsideVertex;         
    int KeyFace;                    
    int OtherFace;                  
    double Weight;                  
    std::array<double, 3> Position; 
    vtkIdType OutputPointId;        
  };

  struct TraceResult
  {
    std::vector<int> VertexTags;

    std::vector<IsoVertex> IsoVertices;

    std::vector<std::vector<int>> FaceIsoVertices;

    std::vector<std::vector<int>> IsoVertexPositionInFace;

    std::vector<std::vector<int>> IsoPolygons;

    std::unordered_map<int64_t, int> EdgeToIsoVert;

    // Assign vertices
    std::vector<bool> Assigned;

    void Clear(vtkIdType nFaces)
    {
      this->VertexTags.clear();
      this->IsoVertices.clear();
      this->FaceIsoVertices.resize(nFaces);
      for (vtkIdType i = 0; i < nFaces; ++i)
      {
        this->FaceIsoVertices[i].clear();
      }
      this->IsoVertexPositionInFace.resize(nFaces);
      for (vtkIdType i = 0; i < nFaces; ++i)
      {
        this->IsoVertexPositionInFace[i].clear();
      }
      this->IsoPolygons.clear();
      this->EdgeToIsoVert.clear();
      this->Assigned.clear();
    }
  };

  TraceResult Result;

  //============================================================================
  // Shared algorithm core (static — used by both the instance path and the
  // bulk static API).
  //============================================================================

  static void ClassifyVertices(TraceResult& result, const std::vector<double>& localScalars,
    double isoValue, int& numInside, int& numOutside);

  static void FindIsoVertices(TraceResult& result, vtkIdType nFaces,
    const vtkIdType* localFaceStream, const std::vector<double>& localScalars, double isoValue);

  static void TraceIsoPolygons(TraceResult& result);

  static void RunLopezTraceInto(TraceResult& result, vtkIdType nFaces,
    const vtkIdType* localFaceStream, const std::vector<double>& localScalars, double isoValue);

  //============================================================================
  // Instance-only helpers
  //============================================================================

  void InterpolatePositionsAndInsertPoints(vtkPolyhedron* cell, vtkIncrementalPointLocator* locator,
    vtkPointData* inPd, vtkPointData* outPd);

  //============================================================================
  // Internal Data structured for ContourCell/CountClip/EmitClip
  //============================================================================

  // Per-cell scratch for the bulk Contour/clip API. Held in a
  // thread_local so allocations amortize across cells processed by the
  // same worker thread. Capacities grow to the largest cell seen and are
  // retained thereafter.
  struct PolyhedronWorkspace
  {
    std::vector<double> LocalScalars;
    std::vector<vtkIdType> LocalFaceStream; // face-stream remap: global ID -> local 0..N-1
    std::unordered_map<vtkIdType, int> GlobalToLocal;
    TraceResult Trace;                           // RunLopezTrace output reused
    std::unordered_set<int64_t> LiveIsoEdgeKeys; // CountClip: edges with non-degenerate iso-verts
    std::vector<vtkIdType> PieceSizes;           // CountClip face-walker scratch
    std::vector<vtkIdType> LocalToOutputId;      // EmitClip: local vertex -> output point ID
    std::vector<vtkIdType> IsoToOutputId;        // EmitClip: iso-vertex index -> output point ID
    std::unordered_map<int64_t, vtkIdType> EdgeToOutputId; // EmitClip face-walker lookup
    std::vector<vtkIdType> CellPts;                        // EmitClip cell-connectivity scratch
    std::vector<std::vector<vtkIdType>> Pieces;            // EmitClip face-walker output pieces
    std::vector<vtkIdType> CurrentPiece;                   // EmitClip face-walker active piece
    std::vector<vtkIdType> CapFace;                        // EmitClip cap-face scratch
    // ContourCell GT=ON ear-clip scratch (allocation-free per polygon).
    std::vector<std::array<double, 3>> EarCoords; // iso-vertex coords, loop order
    std::vector<int> EarPrev;                     // ear-clip linked-list prev
    std::vector<int> EarNext;                     // ear-clip linked-list next
    std::vector<int> EarRing;                     // ear-clip compacted ring
    std::vector<double> EarHeapMeasure;           // quality ear-clip heap keys
    std::vector<int> EarHeapVertex;               // quality ear-clip heap vertex ids
    std::vector<int> EarHeapSlot;                 // quality ear-clip vertex id -> heap slot
  };
};

VTK_ABI_NAMESPACE_END
#endif // vtkPolyhedronContour_h