You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
290 lines
9.8 KiB
C++
290 lines
9.8 KiB
C++
/*=========================================================================
|
|
|
|
Program: Visualization Toolkit
|
|
Module: vtkPolyDataInternals.h
|
|
|
|
Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
|
|
All rights reserved.
|
|
See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
|
|
|
|
This software is distributed WITHOUT ANY WARRANTY; without even
|
|
the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
|
|
PURPOSE. See the above copyright notice for more information.
|
|
|
|
=========================================================================*/
|
|
|
|
/**
|
|
* @class vtkPolyDataInternals
|
|
* @brief Store mapping from vtkPolyData cell ids to internal cell array ids.
|
|
*
|
|
* Optimized data structure for storing internal cell ids and type information
|
|
* for vtkPolyData datasets.
|
|
*
|
|
* Since vtkPolyData only supports a handful of types, the type information
|
|
* is compressed to four bits -- the first two indicate which internal
|
|
* vtkCellArray object a cell is stored in (verts, lines, polys, strips), and
|
|
* the second two bits indicate which type of cell (e.g. lines vs polylines,
|
|
* triangles vs quads vs polygons, etc), as well as whether or not the cell
|
|
* has been deleted from the vtkPolyData.
|
|
*
|
|
* These four bits are stored at the top of a 64 bit index, and the remaining
|
|
* 60 bits store the cell id. This implies that the internal cell arrays cannot
|
|
* store more than 2^60 cells each, a reasonable limit for modern hardware.
|
|
*
|
|
* TaggedCellId structure:
|
|
* 66 66 555555555544444444443333333333222222222211111111110000000000
|
|
* 32 10 987654321098765432109876543210987654321098765432109876543210
|
|
* +--+--+------------------------------------------------------------+
|
|
* |00|00|000000000000000000000000000000000000000000000000000000000000|
|
|
* +^-+^-+^-----------------------------------------------------------+
|
|
* | | |
|
|
* | | |> Bottom 60 bits of cellId
|
|
* | |> Type variant / deleted
|
|
* |> Target cell array
|
|
*
|
|
* The supported cell types are:
|
|
*
|
|
* - VTK_VERTEX
|
|
* - VTK_POLY_VERTEX
|
|
* - VTK_LINE
|
|
* - VTK_POLY_LINE
|
|
* - VTK_TRIANGLE
|
|
* - VTK_QUAD
|
|
* - VTK_POLYGON
|
|
* - VTK_TRIANGLE_STRIP
|
|
*/
|
|
|
|
#ifndef vtkPolyDataInternals_h
|
|
#define vtkPolyDataInternals_h
|
|
|
|
#ifndef __VTK_WRAP__ // Don't wrap this class.
|
|
|
|
#include "vtkCommonDataModelModule.h" // For export macro
|
|
|
|
#include "vtkCellType.h"
|
|
#include "vtkObject.h"
|
|
#include "vtkType.h"
|
|
|
|
#include <cstdlib> // for std::size_t
|
|
#include <vector> // for CellMap implementation.
|
|
|
|
namespace vtkPolyData_detail
|
|
{
|
|
|
|
static constexpr vtkTypeUInt64 CELLID_MASK = 0x0fffffffffffffffull;
|
|
static constexpr vtkTypeUInt64 SHIFTED_TYPE_INDEX_MASK = 0xf000000000000000ull;
|
|
static constexpr vtkTypeUInt64 TARGET_MASK = 0x3ull << 62;
|
|
static constexpr vtkTypeUInt64 TYPE_VARIANT_MASK = 0x3ull << 60;
|
|
|
|
// Enumeration of internal cell array targets.
|
|
enum class Target : vtkTypeUInt64
|
|
{
|
|
Verts = 0x0ull << 62,
|
|
Lines = 0x1ull << 62,
|
|
Polys = 0x2ull << 62,
|
|
Strips = 0x3ull << 62,
|
|
};
|
|
|
|
// Enumeration of type variants.
|
|
enum class TypeVariant : vtkTypeUInt64
|
|
{
|
|
Dead = 0x0ull << 60,
|
|
Var1 = 0x1ull << 60,
|
|
Var2 = 0x2ull << 60,
|
|
Var3 = 0x3ull << 60,
|
|
};
|
|
|
|
// Lookup table to convert a type index (TaggedCellId.GetTypeIndex()) into
|
|
// a VTK cell type.
|
|
// The type index is the highest four bits of the encoded value, eg. the
|
|
// target and type variant information.
|
|
static constexpr unsigned char TypeTable[16] = {
|
|
VTK_EMPTY_CELL, // 0000b | Verts | Dead
|
|
VTK_VERTEX, // 0001b | Verts | Var1
|
|
VTK_POLY_VERTEX, // 0010b | Verts | Var2
|
|
VTK_EMPTY_CELL, // 0011b | Verts | Var3
|
|
VTK_EMPTY_CELL, // 0100b | Lines | Dead
|
|
VTK_LINE, // 0101b | Lines | Var1
|
|
VTK_POLY_LINE, // 0110b | Lines | Var2
|
|
VTK_EMPTY_CELL, // 0111b | Lines | Var3
|
|
VTK_EMPTY_CELL, // 1000b | Polys | Dead
|
|
VTK_TRIANGLE, // 1001b | Polys | Var1
|
|
VTK_QUAD, // 1010b | Polys | Var2
|
|
VTK_POLYGON, // 1011b | Polys | Var3
|
|
VTK_EMPTY_CELL, // 1100b | Strips | Dead
|
|
VTK_TRIANGLE_STRIP, // 1101b | Strips | Var1
|
|
VTK_EMPTY_CELL, // 1110b | Strips | Var2
|
|
VTK_EMPTY_CELL, // 1111b | Strips | Var3
|
|
};
|
|
|
|
// Convenience method to concatenate a target and type variant into the low
|
|
// four bits of a single byte. Used to build the TargetVarTable.
|
|
static constexpr unsigned char GenTargetVar(Target target, TypeVariant var) noexcept
|
|
{
|
|
return static_cast<unsigned char>(
|
|
(static_cast<vtkTypeUInt64>(target) | static_cast<vtkTypeUInt64>(var)) >> 60);
|
|
}
|
|
|
|
// Lookup table that maps a VTK cell type (eg. VTK_TRIANGLE) into a target +
|
|
// type variant byte.
|
|
static constexpr unsigned char TargetVarTable[10] = {
|
|
GenTargetVar(Target::Verts, TypeVariant::Dead), // 0 | VTK_EMPTY_CELL
|
|
GenTargetVar(Target::Verts, TypeVariant::Var1), // 1 | VTK_VERTEX
|
|
GenTargetVar(Target::Verts, TypeVariant::Var2), // 2 | VTK_POLY_VERTEX
|
|
GenTargetVar(Target::Lines, TypeVariant::Var1), // 3 | VTK_LINE
|
|
GenTargetVar(Target::Lines, TypeVariant::Var2), // 4 | VTK_POLY_LINE
|
|
GenTargetVar(Target::Polys, TypeVariant::Var1), // 5 | VTK_TRIANGLE
|
|
GenTargetVar(Target::Strips, TypeVariant::Var1), // 6 | VTK_TRIANGLE_STRIP
|
|
GenTargetVar(Target::Polys, TypeVariant::Var3), // 7 | VTK_POLYGON
|
|
GenTargetVar(Target::Polys, TypeVariant::Var2), // 8 | VTK_PIXEL (treat as quad)
|
|
GenTargetVar(Target::Polys, TypeVariant::Var2), // 9 | VTK_QUAD
|
|
};
|
|
|
|
// Thin wrapper around a vtkTypeUInt64 that encodes a target cell array,
|
|
// cell type, deleted status, and 60-bit cell id.
|
|
struct VTKCOMMONDATAMODEL_EXPORT TaggedCellId
|
|
{
|
|
// Encode a cell id and a VTK cell type (eg. VTK_TRIANGLE) into a
|
|
// vtkTypeUInt64.
|
|
static vtkTypeUInt64 Encode(vtkIdType cellId, VTKCellType type) noexcept
|
|
{
|
|
const size_t typeIndex = static_cast<size_t>(type);
|
|
return ((static_cast<vtkTypeUInt64>(cellId) & CELLID_MASK) |
|
|
(static_cast<vtkTypeUInt64>(TargetVarTable[typeIndex]) << 60));
|
|
}
|
|
|
|
TaggedCellId() noexcept = default;
|
|
|
|
// Create a TaggedCellId from a cellId and cell type (e.g. VTK_TRIANGLE).
|
|
TaggedCellId(vtkIdType cellId, VTKCellType cellType) noexcept : Value(Encode(cellId, cellType)) {}
|
|
|
|
TaggedCellId(const TaggedCellId&) noexcept = default;
|
|
TaggedCellId(TaggedCellId&&) noexcept = default;
|
|
TaggedCellId& operator=(const TaggedCellId&) noexcept = default;
|
|
TaggedCellId& operator=(TaggedCellId&&) noexcept = default;
|
|
|
|
// Get an enum value describing the internal vtkCellArray target used to
|
|
// store this cell.
|
|
Target GetTarget() const noexcept { return static_cast<Target>(this->Value & TARGET_MASK); }
|
|
|
|
// Get the VTK cell type value (eg. VTK_TRIANGLE) as a single byte.
|
|
unsigned char GetCellType() const noexcept { return TypeTable[this->GetTypeIndex()]; }
|
|
|
|
// Get the cell id used by the target vtkCellArray to store this cell.
|
|
vtkIdType GetCellId() const noexcept { return static_cast<vtkIdType>(this->Value & CELLID_MASK); }
|
|
|
|
// Update the cell id. Most useful with the CellMap::InsertNextCell(type)
|
|
// signature.
|
|
void SetCellId(vtkIdType cellId) noexcept
|
|
{
|
|
this->Value &= SHIFTED_TYPE_INDEX_MASK;
|
|
this->Value |= (static_cast<vtkTypeUInt64>(cellId) & CELLID_MASK);
|
|
}
|
|
|
|
// Mark this cell as deleted.
|
|
void MarkDeleted() noexcept { this->Value &= ~TYPE_VARIANT_MASK; }
|
|
|
|
// Returns true if the cell has been deleted.
|
|
bool IsDeleted() const noexcept { return (this->Value & TYPE_VARIANT_MASK) == 0; }
|
|
|
|
private:
|
|
vtkTypeUInt64 Value;
|
|
|
|
// These shouldn't be needed outside of this struct. You're probably looking
|
|
// for GetCellType() instead.
|
|
TypeVariant GetTypeVariant() const noexcept
|
|
{
|
|
return static_cast<TypeVariant>(this->Value & TYPE_VARIANT_MASK);
|
|
}
|
|
std::size_t GetTypeIndex() const noexcept { return static_cast<std::size_t>(this->Value >> 60); }
|
|
};
|
|
|
|
// Thin wrapper around a std::vector<TaggedCellId> to allow shallow copying, etc
|
|
class VTKCOMMONDATAMODEL_EXPORT CellMap : public vtkObject
|
|
{
|
|
public:
|
|
static CellMap* New();
|
|
vtkTypeMacro(CellMap, vtkObject);
|
|
|
|
static bool ValidateCellType(VTKCellType cellType) noexcept
|
|
{
|
|
// 1-9 excluding 8 (VTK_PIXEL):
|
|
return cellType > 0 && cellType <= 10 && cellType != VTK_PIXEL;
|
|
}
|
|
|
|
static bool ValidateCellId(vtkIdType cellId) noexcept
|
|
{
|
|
// is positive, won't truncate:
|
|
return (
|
|
(static_cast<vtkTypeUInt64>(cellId) & CELLID_MASK) == static_cast<vtkTypeUInt64>(cellId));
|
|
}
|
|
|
|
void DeepCopy(CellMap* other)
|
|
{
|
|
if (other)
|
|
{
|
|
this->Map = other->Map;
|
|
}
|
|
else
|
|
{
|
|
this->Map.clear();
|
|
}
|
|
}
|
|
|
|
void SetCapacity(vtkIdType numCells) { this->Map.reserve(static_cast<std::size_t>(numCells)); }
|
|
|
|
TaggedCellId& GetTag(vtkIdType cellId) { return this->Map[static_cast<std::size_t>(cellId)]; }
|
|
|
|
const TaggedCellId& GetTag(vtkIdType cellId) const
|
|
{
|
|
return this->Map[static_cast<std::size_t>(cellId)];
|
|
}
|
|
|
|
// Caller must ValidateCellType first.
|
|
void InsertNextCell(vtkIdType cellId, VTKCellType cellType)
|
|
{
|
|
this->Map.emplace_back(cellId, cellType);
|
|
}
|
|
|
|
// Caller must ValidateCellType and ValidateCellId first.
|
|
// useful for reusing the target lookup from cellType and then calling
|
|
// TaggedCellId::SetCellId later.
|
|
TaggedCellId& InsertNextCell(VTKCellType cellType)
|
|
{
|
|
this->Map.emplace_back(vtkIdType(0), cellType);
|
|
return this->Map.back();
|
|
}
|
|
|
|
vtkIdType GetNumberOfCells() const { return static_cast<vtkIdType>(this->Map.size()); }
|
|
|
|
void Reset() { this->Map.clear(); }
|
|
|
|
void Squeeze()
|
|
{
|
|
this->Map.shrink_to_fit(); // yaaaaay c++11
|
|
}
|
|
|
|
// In rounded-up kibibytes, as is VTK's custom:
|
|
unsigned long GetActualMemorySize() const
|
|
{
|
|
return static_cast<unsigned long>(sizeof(TaggedCellId) * this->Map.capacity() + 1023) / 1024;
|
|
}
|
|
|
|
protected:
|
|
CellMap();
|
|
~CellMap() override;
|
|
|
|
std::vector<TaggedCellId> Map;
|
|
|
|
private:
|
|
CellMap(const CellMap&) = delete;
|
|
CellMap& operator=(const CellMap&) = delete;
|
|
};
|
|
|
|
} // end namespace vtkPolyData_detail
|
|
|
|
#endif // __VTK_WRAP__
|
|
#endif // vtkPolyDataInternals.h
|
|
|
|
// VTK-HeaderTest-Exclude: vtkPolyDataInternals.h
|