vtkSurfaceNets3DNonManifoldCases.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 vtkSurfaceNets3DNonManifoldCases_h
#define vtkSurfaceNets3DNonManifoldCases_h

#include "vtkFiltersCoreModule.h"
#include "vtkSetGet.h"

#include <array>
#include <cstddef>
#include <cstdint>

VTK_ABI_NAMESPACE_BEGIN
#define VTK_SURFACE_NETS_3D_ALWAYS_SPLIT_CASES_1_3
// #define VTK_SURFACE_NETS_3D_SUPPORT_ALL_SOLVABLE_VARIATIONS_FOR_CASE_8
class VTKFILTERSCORE_EXPORT vtkSurfaceNets3DNonManifoldCases
{
public:
#ifdef VTK_SURFACE_NETS_3D_SUPPORT_ALL_SOLVABLE_VARIATIONS_FOR_CASE_8
  static constexpr uint8_t MaxTableIndex = 9;
#else
  static constexpr uint8_t MaxTableIndex = 8;
#endif
  using NonManifoldCaseType = unsigned char;
  using EdgeCaseType = unsigned short;
  using VoxelCaseType = unsigned char;

  struct NonManifoldCaseMetadata
  {
    NonManifoldCaseType NonManifoldCase = 0;
    VoxelCaseType VoxelCase = 0;
    bool IsHomogeneous = true;
    std::array<int8_t, 12> PointIndices;
    std::array<VoxelCaseType, 4> SubVoxelCases;
    std::array<EdgeCaseType, 4> SubEdgeCases;
  };
  template <class T>
  struct VoxelNeighborhood
  {
    EdgeCaseType EdgeCase;
    VoxelCaseType VoxelCase;
    std::array<T, 8> Labels;
  };

  enum TableIndexValues : int8_t
  {
    EmptyIndex = -3,
    ManifoldIndex = -2,
    NonManifoldIndexUnsolvable = -1,
    NonManifoldIndex0 = 0,
    NonManifoldIndex1 = 1,
    NonManifoldIndex2 = 2, // Used only by NonManifoldCase 8
    NonManifoldIndex3 = 3, // Used only by NonManifoldCase 8
    NonManifoldIndex4 = 4, // Used only by NonManifoldCase 8
    NonManifoldIndex5 = 5, // Used only by NonManifoldCase 8
    NonManifoldIndex6 = 6, // Used only by NonManifoldCase 8
    NonManifoldIndex7 = 7, // Used only by NonManifoldCase 8
    NonManifoldIndex8 = 8, // Used only by NonManifoldCase 8
#ifdef VTK_SURFACE_NETS_3D_SUPPORT_ALL_SOLVABLE_VARIATIONS_FOR_CASE_8
    NonManifoldIndex9 = 9, // Used only by NonManifoldCase 8
#endif
  };

  template <class T>
  static auto GetNonManifoldTableIndex(const VoxelNeighborhood<T>& voxelNeighborhood) -> int8_t;

  static VTK_ALWAYS_INLINE auto GetNumberOfNonManifoldCases(EdgeCaseType edgeCase) -> uint8_t
  {
    return EdgeCaseOffsets[edgeCase + 1] - EdgeCaseOffsets[edgeCase];
  }

  static VTK_ALWAYS_INLINE auto GetNonManifoldCase(
    EdgeCaseType edgeCase, int8_t tableIndex) -> NonManifoldCaseType
  {
    if (tableIndex < 0 || tableIndex >= GetNumberOfNonManifoldCases(edgeCase))
    {
      return 0; // manifold case
    }
    return NonManifoldMetadata[EdgeCaseOffsets[edgeCase] + tableIndex].NonManifoldCase;
  }

  static VTK_ALWAYS_INLINE auto GetNonManifoldBasicVoxelCase(
    EdgeCaseType edgeCase, int8_t tableIndex) -> VoxelCaseType
  {
    return NonManifoldMetadata[EdgeCaseOffsets[edgeCase] + tableIndex].VoxelCase;
  }

  static VTK_ALWAYS_INLINE auto IsNonManifoldCaseHomogeneous(
    EdgeCaseType edgeCase, int8_t tableIndex) -> NonManifoldCaseType
  {
    return NonManifoldMetadata[EdgeCaseOffsets[edgeCase] + tableIndex].IsHomogeneous;
  }

  static constexpr VTK_ALWAYS_INLINE auto GetNumberOfPoints(
    NonManifoldCaseType nonManifoldCase) -> uint8_t
  {
    constexpr uint8_t pointsPerNonManifoldCase[12] = {
      1,     // case 0  is manifold, so 1 point (the center vertex) is generated
      2 + 1, // case 1  has 1 duplicate point,  so 2 points + 1 center point = 3 total
      2 + 1, // case 2  has 1 duplicate point,  so 2 points + 1 center point = 3 total
      2 + 1, // case 3  has 1 duplicate point,  so 2 points + 1 center point = 3 total
      3 + 1, // case 4  has 2 duplicate points, so 3 points + 1 center point = 4 total
      2 + 1, // case 5  has 1 duplicate point,  so 2 points + 1 center point = 3 total
      2 + 1, // case 6  has 1 duplicate point,  so 2 points + 1 center point = 3 total
      4 + 1, // case 7  has 3 duplicate points, so 4 points + 1 center point = 5 total
      2 + 1, // case 8  has 1 duplicate point,  so 2 points + 1 center point = 3 total
      2 + 1, // case 9  has 1 duplicate point,  so 2 points + 1 center point = 3 total
      2 + 1, // case 10 has 1 duplicate point,  so 2 points + 1 center point = 3 total
      2 + 1, // case 11 has 1 duplicate point,  so 2 points + 1 center point = 3 total
    };
    return pointsPerNonManifoldCase[nonManifoldCase];
  }

  template <uint8_t QuadId>
  static VTK_ALWAYS_INLINE auto GetNonManiFoldPointIndex(
    EdgeCaseType edgeCase, int8_t tableIndex) -> int8_t
  {
    static_assert(QuadId < 12, "QuadId must be between 0 and 11 (inclusive)");
    return NonManifoldMetadata[EdgeCaseOffsets[edgeCase] + tableIndex].PointIndices[QuadId];
  }

  static constexpr VTK_ALWAYS_INLINE auto GetNumberOfManifoldSubCases(
    NonManifoldCaseType nonManifoldCase) -> uint8_t
  {
    constexpr uint8_t subCasesPerNonManifoldCase[12] = {
      1, // case 0  is manifold, so 1 point (the center vertex) is generated
      2, // case 1  has 1 duplicate point,  so 2 sub cases
      2, // case 2  has 1 duplicate point,  so 2 sub cases
      2, // case 3  has 1 duplicate point,  so 2 sub cases
      3, // case 4  has 2 duplicate points, so 3 sub cases
      2, // case 5  has 1 duplicate point,  so 2 sub cases
      2, // case 6  has 1 duplicate point,  so 2 sub cases
      4, // case 7  has 3 duplicate points, so 4 sub cases
      2, // case 8  has 1 duplicate point,  so 2 sub cases
      2, // case 9  has 1 duplicate point,  so 2 sub cases
      2, // case 10 has 1 duplicate point,  so 2 sub cases
      2  // case 11 has 1 duplicate point,  so 2 sub cases
    };
    return subCasesPerNonManifoldCase[nonManifoldCase];
  }

  static VTK_ALWAYS_INLINE auto GetManifoldSubEdgeCases(
    EdgeCaseType edgeCase, int8_t tableIndex) -> const std::array<EdgeCaseType, 4>&
  {
    static constexpr std::array<EdgeCaseType, 4> Empty{};
    if (tableIndex < 0)
    {
      return Empty;
    }
    return NonManifoldMetadata[EdgeCaseOffsets[edgeCase] + tableIndex].SubEdgeCases;
  }

  static constexpr VTK_ALWAYS_INLINE auto ComputeState(
    uint8_t numPoints, int8_t tableIndex) -> uint8_t
  {
    switch (numPoints)
    {
      case 0:
        return 0;
      case 1:
        return tableIndex == ManifoldIndex ? 1 : 2;
      case 3:
        return 3 + tableIndex; // Indices 0-MaxTableIndex map to 3...
      case 4:
        // If MaxTableIndex is 9, offset is 3 + 10 = 13
        // If MaxTableIndex is 8, offset is 3 + 9 = 12
        return 3 + (MaxTableIndex + 1) + tableIndex;
      case 5:
        // If MaxTableIndex is 9, offset is 13 + 2 = 15
        // If MaxTableIndex is 8, offset is 12 + 2 = 14
        return 3 + (MaxTableIndex + 1) + 2 + tableIndex;
      default:
        return 1;
    }
  }

  struct StateInfo
  {
    // 0 (empty), 1 (manifold or unsolvable), 3, 4, or 5
    uint8_t NumPoints;
    // EmptyIndex, ManifoldIndex, NonManifoldIndexUnsolvable, or [0, MaxTableIndex]
    int8_t TableIndex;
  };

  static constexpr VTK_ALWAYS_INLINE auto GetStateInfo(uint8_t state) -> StateInfo
  {
#ifdef VTK_SURFACE_NETS_3D_SUPPORT_ALL_SOLVABLE_VARIATIONS_FOR_CASE_8
    constexpr StateInfo InfoTable[17] = { { 0, EmptyIndex }, // 0:  Empty
      { 1, ManifoldIndex },                                  // 1:  Manifold
      { 1, NonManifoldIndexUnsolvable },                     // 2:  Non-Manifold (Unsolvable)
      // 3-12: 3-point solvable (tableIndex 0-9)
      { 3, NonManifoldIndex0 }, { 3, NonManifoldIndex1 }, { 3, NonManifoldIndex2 },
      { 3, NonManifoldIndex3 }, { 3, NonManifoldIndex4 }, { 3, NonManifoldIndex5 },
      { 3, NonManifoldIndex6 }, { 3, NonManifoldIndex7 }, { 3, NonManifoldIndex8 },
      { 3, NonManifoldIndex9 },
      // 13-14: 4-point solvable (tableIndex 0-1)
      { 4, NonManifoldIndex0 }, { 4, NonManifoldIndex1 },
      // 15-16: 5-point solvable (tableIndex 0-1)
      { 5, NonManifoldIndex0 }, { 5, NonManifoldIndex1 } };
#else
    constexpr StateInfo InfoTable[16] = { { 0, EmptyIndex }, // 0:  Empty
      { 1, ManifoldIndex },                                  // 1:  Manifold
      { 1, NonManifoldIndexUnsolvable },                     // 2:  Non-Manifold (Unsolvable)
      // 3-11: 3-point solvable (tableIndex 0-8)
      { 3, NonManifoldIndex0 }, { 3, NonManifoldIndex1 }, { 3, NonManifoldIndex2 },
      { 3, NonManifoldIndex3 }, { 3, NonManifoldIndex4 }, { 3, NonManifoldIndex5 },
      { 3, NonManifoldIndex6 }, { 3, NonManifoldIndex7 }, { 3, NonManifoldIndex8 },
      // 12-13: 4-point solvable (tableIndex 0-1)
      { 4, NonManifoldIndex0 }, { 4, NonManifoldIndex1 },
      // 14-15: 5-point solvable (tableIndex 0-1)
      { 5, NonManifoldIndex0 }, { 5, NonManifoldIndex1 } };
#endif
    return InfoTable[state];
  }

private:
  static VTK_ALWAYS_INLINE auto GetManifoldSubVoxelCases(
    EdgeCaseType edgeCase, int8_t tableIndex) -> const std::array<VoxelCaseType, 4>&
  {
    return NonManifoldMetadata[EdgeCaseOffsets[edgeCase] + tableIndex].SubVoxelCases;
  }

  static const std::array<uint16_t, 4097>& EdgeCaseOffsets;
  static const std::array<NonManifoldCaseMetadata, 3736>& NonManifoldMetadata;
};
VTK_ABI_NAMESPACE_END

#endif // vtkSurfaceNets3DNonManifoldCases_h