VTK  9.3.0
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
27VTK_ABI_NAMESPACE_BEGIN
28const int MAX_DIM = 3;
29const int MAX_CHILD = 8;
30
32//
33// Leaf information
34//
36
37class BHLeaf
38{
39public:
40 BHLeaf(int dim, double* loc);
42
43 bool sameAs(int dim, double* loc);
44
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
63class BHNode
64{
65public:
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
81class BHTree
82{
83public:
84 BHTree(int dimension, int numChild,
85 double* minLoc, // Bounding box of tree
86 double* maxLoc); // Bounding box of tree
88
89 int insertLeaf(double* loc);
90 int getChildIndex(BHNode* node, double* loc);
91 void print();
92
93private:
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
106VTK_ABI_NAMESPACE_END
107#endif
const int MAX_CHILD
Definition BHTree.h:29
const int MAX_DIM
Definition BHTree.h:28
bool sameAs(int dim, double *loc)
double location[MAX_DIM]
Definition BHTree.h:45
BHLeaf(int dim, double *loc)
BHNode(int dim, int numChild, double *minLoc, double *maxLoc)
double center[MAX_DIM]
Definition BHTree.h:71
BHNode(int dim, int numChild, BHNode *parent, int child)
double length[MAX_DIM]
Definition BHTree.h:70
int child[MAX_CHILD]
Definition BHTree.h:72
BHTree(int dimension, int numChild, double *minLoc, double *maxLoc)
int insertLeaf(double *loc)
void print()
int getChildIndex(BHNode *node, double *loc)