vtkHyperTree.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 vtkHyperTree_h
#define vtkHyperTree_h
 
#include "vtkCommonDataModelModule.h" // For export macro
#include "vtkObject.h"
 
#include <cassert> // Used internally
#include <memory>  // std::shared_ptr
 
VTK_ABI_NAMESPACE_BEGIN
class vtkBitArray;
class vtkIdList;
class vtkHyperTreeGridScales;
class vtkTypeInt64Array;
 
//=============================================================================
struct vtkHyperTreeData
{
  // Index of this tree in the hypertree grid
  vtkIdType TreeIndex;
 
  // Number of levels in the tree
  unsigned int NumberOfLevels;
 
  // Number of vertices in this tree (coarse and leaves)
  vtkIdType NumberOfVertices;
 
  // Number of nodes (non-leaf vertices) in the tree
  vtkIdType NumberOfNodes;
 
  // Offset start for the implicit global index mapping fixed by
  // SetGlobalIndexStart after create a tree.
  // If you don't choose implicit global index mapping then this
  // value is -1. Then, you must to descrieb explicit global index
  // mapping by using then SetGlobalIndexFromLocal for each cell
  // in tree.
  // The extra cost is equivalent to the cost of a field of values
  // of cells.
  vtkIdType GlobalIndexStart;
 
  // Storage to record the parent of each tree vertex
  std::vector<unsigned int> ParentToElderChild;
 
  // Storage to record the local to global id mapping
  std::vector<vtkIdType> GlobalIndexTable;
};
 
//=============================================================================
class VTKCOMMONDATAMODEL_EXPORT vtkHyperTree : public vtkObject
{
public:
  static vtkHyperTree* New();
  vtkTypeMacro(vtkHyperTree, vtkObject);
  void PrintSelf(ostream& os, vtkIndent indent) override;

  bool Initialize(unsigned char branchFactor, unsigned char dimension);

  virtual void InitializeForReader(vtkIdType numberOfLevels, vtkIdType nbVertices,
    vtkIdType nbVerticesOfLastLevel, vtkBitArray* isParent, vtkBitArray* isMasked,
    vtkBitArray* outIsMasked);

  virtual void BuildFromBreadthFirstOrderDescriptor(
    vtkBitArray* descriptor, vtkIdType numberOfBits, vtkIdType startIndex = 0);

  virtual void ComputeBreadthFirstOrderDescriptor(unsigned int depthLimiter, vtkBitArray* inputMask,
    vtkTypeInt64Array* numberOfVerticesPerDepth, vtkBitArray* descriptor,
    vtkIdList* breadthFirstIdMap);

  void CopyStructure(vtkHyperTree* ht);


  void SetTreeIndex(vtkIdType treeIndex)
  {
    assert("pre: datas_non_nullptr" && this->Datas != nullptr);
    this->Datas->TreeIndex = treeIndex;
  }
  vtkIdType GetTreeIndex() const
  {
    assert("pre: datas_non_nullptr" && this->Datas != nullptr);
    return this->Datas->TreeIndex;
  }


  unsigned int GetNumberOfLevels() const
  {
    assert("pre: datas_non_nullptr" && this->Datas != nullptr);
    assert("post: result_greater_or_equal_to_one" && this->Datas->NumberOfLevels >= 1);
    return this->Datas->NumberOfLevels;
  }

  vtkIdType GetNumberOfVertices() const
  {
    assert("pre: datas_non_nullptr" && this->Datas != nullptr);
    return this->Datas->NumberOfVertices;
  }

  vtkIdType GetNumberOfNodes() const
  {
    assert("pre: datas_non_nullptr" && this->Datas != nullptr);
    return this->Datas->NumberOfNodes;
  }

  vtkIdType GetNumberOfLeaves() const
  {
    assert("pre: datas_non_nullptr" && this->Datas != nullptr);
    return this->Datas->NumberOfVertices - this->Datas->NumberOfNodes;
  }

  int GetBranchFactor() const { return this->BranchFactor; }

  int GetDimension() const { return this->Dimension; }

  vtkIdType GetNumberOfChildren() const { return this->NumberOfChildren; }


  void GetScale(double s[3]) const;
  double GetScale(unsigned int d) const;

  std::shared_ptr<vtkHyperTreeGridScales> InitializeScales(
    const double* scales, bool reinitialize = false);

  virtual unsigned long GetActualMemorySizeBytes();

  unsigned int GetActualMemorySize()
  {
    // in kilibytes
    return static_cast<unsigned int>(this->GetActualMemorySizeBytes() / 1024);
  }

  virtual bool IsGlobalIndexImplicit();

  virtual void SetGlobalIndexStart(vtkIdType start);

  vtkIdType GetGlobalIndexStart() const
  {
    assert("pre: datas_non_nullptr" && this->Datas != nullptr);
    return this->Datas->GlobalIndexStart;
  }

  virtual void SetGlobalIndexFromLocal(vtkIdType index, vtkIdType global);

  virtual vtkIdType GetGlobalIndexFromLocal(vtkIdType index) const;

  virtual vtkIdType GetGlobalNodeIndexMax() const;

  virtual bool IsLeaf(vtkIdType index) const;

  virtual void SubdivideLeaf(vtkIdType index, unsigned int level);

  virtual bool IsTerminalNode(vtkIdType index) const;

  virtual vtkIdType GetElderChildIndex(unsigned int index_parent) const;

  virtual const unsigned int* GetElderChildIndexArray(size_t& nbElements) const;


  void SetScales(std::shared_ptr<vtkHyperTreeGridScales> scales) { this->Scales = scales; }


  bool HasScales() const { return (this->Scales != nullptr); }


  std::shared_ptr<vtkHyperTreeGridScales> GetScales() const
  {
    assert(this->Scales != nullptr);
    return this->Scales;
  }

 
protected:
  vtkHyperTree();
  ~vtkHyperTree() override = default;
 
private:
  vtkHyperTree(const vtkHyperTree&) = delete;
  void operator=(const vtkHyperTree&) = delete;
 
  bool IsChildLeaf(vtkIdType index_parent, unsigned int ichild) const;

  void ComputeBreadthFirstOrderDescriptorImpl(unsigned int depthLimiter, vtkBitArray* inputMask,
    unsigned int depth, vtkIdType index, std::vector<std::vector<bool>>& descriptorPerDepth,
    std::vector<std::vector<vtkIdType>>& breadthFirstOrderIdMapPerDepth);
 
  //-- Global information
 
  // Branching factor of tree (2 or 3)
  unsigned char BranchFactor;
 
  // Dimension of tree (1, 2, or 3)
  unsigned char Dimension;
 
  // Number of children for coarse cell
  unsigned char NumberOfChildren;
 
  //-- Local information
  std::shared_ptr<vtkHyperTreeData> Datas;
 
  // Storage of pre-computed per-level cell scales
  // In hypertree grid, one description by hypertree.
  // In Uniform hypertree grid, one description by hypertree grid
  // (all cells, different hypertree, are identical by level).
  std::shared_ptr<vtkHyperTreeGridScales> Scales;
};
 
VTK_ABI_NAMESPACE_END
#endif