VTK  9.3.1
BHTree.h
Go to the documentation of this file.
1 // SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
2 // SPDX-FileCopyrightText: Copyright (c) 2007, Los Alamos National Security, LLC
3 // SPDX-License-Identifier: LicenseRef-BSD-3-Clause-LANL-USGov
4 // .NAME BHTree - Create a Barnes Hut tree from the given points
5 //
6 // .SECTION Description
7 // BHTree takes point locations and distributes them recursively in
8 // a Barnes Hut tree. The tree is a quadtree or octree, dividing on physical
9 // location such that one point or one node appears within a child
10 // so that it is essentially AMR.
11 //
12 // This is used to ensure unique points in the vtk data set and so the
13 // succeeding steps of threading the tree for iteration is not done.
14 //
15 // BHLeaf is the actual point with the index matching the vtkPoints index.
16 // BHNode are negative numbers. This allows a quick recognition of a leaf
17 // or a node. Children numbered with 0 are empty.
18 //
19 
20 #ifndef BHTree_h
21 #define BHTree_h
22 
23 #include "vtkABINamespace.h"
24 
25 #include <vector>
26 
27 VTK_ABI_NAMESPACE_BEGIN
28 const int MAX_DIM = 3;
29 const int MAX_CHILD = 8;
30 
32 //
33 // Leaf information
34 //
36 
37 class BHLeaf
38 {
39 public:
40  BHLeaf(int dim, double* loc);
41  BHLeaf();
42 
43  bool sameAs(int dim, double* loc);
44 
45  double location[MAX_DIM];
46 };
47 
49 //
50 // BH node information
51 //
52 // Barnes Hut octree structure for N-body is represented by vector
53 // of BHNode which divide space into octants which are filled with one
54 // particle or one branching node. As the tree is built the child[8]
55 // array is used. Afterwards the tree is walked linking the nodes and
56 // replacing the child structure with data about the tree. When building
57 // the tree child information is an integer which is the index of the
58 // halo particle which was put into a vector of BHLeaf, or the index
59 // of the BHNode offset by the number of particles
60 //
62 
63 class BHNode
64 {
65 public:
66  BHNode();
67  BHNode(int dim, int numChild, double* minLoc, double* maxLoc);
68  BHNode(int dim, int numChild, BHNode* parent, int child);
69 
70  double length[MAX_DIM]; // Length of octant on each side
71  double center[MAX_DIM]; // Physical center of octant
72  int child[MAX_CHILD]; // Index of leaf or node
73 };
74 
76 //
77 // Barnes Hut Tree
78 //
80 
81 class BHTree
82 {
83 public:
84  BHTree(int dimension, int numChild,
85  double* minLoc, // Bounding box of tree
86  double* maxLoc); // Bounding box of tree
87  ~BHTree();
88 
89  int insertLeaf(double* loc);
90  int getChildIndex(BHNode* node, double* loc);
91  void print();
92 
93 private:
94  int dimension;
95  int numberOfChildren;
96  int leafIndex;
97  int nodeIndex;
98 
99  double minRange[MAX_DIM]; // Physical range of data
100  double maxRange[MAX_DIM]; // Physical range of data
101 
102  std::vector<BHLeaf*> bhLeaf;
103  std::vector<BHNode*> bhNode;
104 };
105 
106 VTK_ABI_NAMESPACE_END
107 #endif
void print()
const int MAX_CHILD
Definition: BHTree.h:29
Definition: BHTree.h:63
double location[MAX_DIM]
Definition: BHTree.h:45
const int MAX_DIM
Definition: BHTree.h:28
BHTree(int dimension, int numChild, double *minLoc, double *maxLoc)
Definition: BHTree.h:37
int getChildIndex(BHNode *node, double *loc)
Definition: BHTree.h:81
double length[MAX_DIM]
Definition: BHTree.h:70
double center[MAX_DIM]
Definition: BHTree.h:71
bool sameAs(int dim, double *loc)
int child[MAX_CHILD]
Definition: BHTree.h:72
int insertLeaf(double *loc)