FreeFOAM The Cross-Platform CFD Toolkit
treeNode.H
Go to the documentation of this file.
1 /*---------------------------------------------------------------------------*\
2  ========= |
3  \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
4  \\ / O peration |
5  \\ / A nd | Copyright (C) 1991-2010 OpenCFD Ltd.
6  \\/ M anipulation |
7 -------------------------------------------------------------------------------
8 License
9  This file is part of OpenFOAM.
10 
11  OpenFOAM is free software: you can redistribute it and/or modify it
12  under the terms of the GNU General Public License as published by
13  the Free Software Foundation, either version 3 of the License, or
14  (at your option) any later version.
15 
16  OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
17  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
18  FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19  for more details.
20 
21  You should have received a copy of the GNU General Public License
22  along with OpenFOAM. If not, see <http://www.gnu.org/licenses/>.
23 
24 Class
25  Foam::treeNode
26 
27 Description
28  Class to implement octree.
29 
30  Holds the pointers to sub-octants. These are either other treeNodes or
31  treeLeafs. The treeLeafs hold the actual data as a list of indices into
32  octreeData.
33 
34 Note
35  To prevent calculation errors all bounding boxes used in octrees are
36  calculated only once.
37 
38  The pointers to either treeNode/treeLeaf are implemented 'by hand'
39  (explicitly marking type) instead of using a proper virtual mechanism
40  to save some space in the treeLeaves.
41 
42 SourceFiles
43  treeNode.C
44 
45 \*---------------------------------------------------------------------------*/
46 
47 #ifndef treeNode_H
48 #define treeNode_H
49 
50 #include "treeBoundBoxList.H"
51 #include "treeElem.H"
52 #include <OpenFOAM/linePointRef.H>
53 #include <OpenFOAM/HashSet.H>
54 
55 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
56 
57 namespace Foam
58 {
59 
60 // class intersection;
61 
62 template<class Type> class octree;
63 template<class Type> class treeLeaf;
64 template<class Type> class treeNode;
65 
66 // Forward declaration of friend functions and operators
67 
68 template<class Type> Istream& operator>>(Istream&, treeNode<Type>&);
69 template<class Type> Ostream& operator<<(Ostream&, const treeNode<Type>&);
70 
71 
72 /*---------------------------------------------------------------------------*\
73  Class treeNodeName Declaration
74 \*---------------------------------------------------------------------------*/
75 
76 TemplateName(treeNode);
77 
78 
79 /*---------------------------------------------------------------------------*\
80  Class treeNode Declaration
81 \*---------------------------------------------------------------------------*/
82 
83 template <class Type>
84 class treeNode
85 :
86  public treeElem<Type>,
87  public treeNodeName
88 {
89  // Private data
90 
91  //- Position of the midpoint
92  const point mid_;
93 
94  //- Type stored in subNodes_
95  unsigned char subNodeTypes_;
96 
97  //- Pointers to sub treeNode or treeLeaf
98  treeElem<Type>* subNodes_[8];
99 
100  //- Constant valid for whole subNode/leaf
101  label volType_;
102 
103  // Static data members
104 
105  //- leaf offset for octant index
106  static const label leafOffset;
107 
108 
109  // Private Member Functions
110 
111  //- mark pointer to subnode as being a treeNode*
112  void setAsNode(const label octant);
113 
114  //- mark pointer to subnode as being a treeLeaf*
115  void setAsLeaf(const label octant);
116 
117  //- Set pointer to sub node
118  void setNodePtr(const label octant, treeElem<Type>* treeNodePtr);
119 
120  //- Set pointer to sub leaf
121  void setLeafPtr(const label octant, treeElem<Type>* treeLeafPtr);
122 
123  //- Set type of octant
124  void setVolType(const label octant, const label type);
125 
126  //- Get type of octant
127  inline label getVolType(const label octant) const;
128 
129  //- Find first leaf on line start-end. Updates start.
130  const treeLeaf<Type>* findLeafLineOctant
131  (
132  const int level,
133  const Type& shapes,
134  const label octant,
135  const vector& direction,
136  point& start,
137  const point& end
138  ) const;
139 
140 
141  //- Print spaces
142  static void space(Ostream&, const label);
143 
144  //- Disallow default bitwise copy construct
145  treeNode(const treeNode&);
146 
147  //- Disallow default bitwise assignment
148  void operator=(const treeNode&);
149 
150 
151 public:
152 
153  // Constructors
154 
155  //- Construct from components
156  treeNode(const treeBoundBox&);
157 
158  //- Construct from Istream
159  treeNode(Istream&);
160 
161 
162  // Destructor
163 
164  ~treeNode();
165 
166 
167  // Member Functions
168 
169  // Access
170 
171  //- The midpoint position
172  inline const point& midpoint() const;
173 
174  //- array of 8 subNodes/leaves
175  inline treeElem<Type>* const* subNodes() const;
176 
177  //- octant contains pointer to treeNode(1) or treeLeaf(0)
178  inline label isNode(const label octant) const;
179 
180  //- Get pointer to sub node
181  inline treeNode<Type>* getNodePtr(const label octant) const;
182 
183  //- Get pointer to sub leaf
184  inline treeLeaf<Type>* getLeafPtr(const label octant) const;
185 
186  // Edit
187 
188  //- Take list of shapes and distribute over the 8 octants
189  void distribute
190  (
191  const label,
192  octree<Type>&,
193  const Type& shapes,
194  const labelList&
195  );
196 
197  //- Distribute at certain level only
198  void redistribute
199  (
200  const label,
201  octree<Type>&,
202  const Type& shapes,
203  const label
204  );
205 
206  //- Set type of subnodes
207  label setSubNodeType
208  (
209  const label level,
210  octree<Type>& top,
211  const Type& shapes
212  );
213 
214  // Search
215 
216  //- Find type of node sample is in. Used for inside/outside
217  // determination
218  label getSampleType
219  (
220  const label level,
221  const octree<Type>& top,
222  const Type& shapes,
223  const point& sample
224  ) const;
225 
226  //- Find index of shape containing sample.
227  label find
228  (
229  const Type& shapes,
230  const point& sample
231  ) const;
232 
233  //- Find tightest bounding box around sample which is guaranteed
234  // to hold at least one cell.
235  // Current best bb in tightest,
236  // returns true if newTightest has changed, 0 otherwise.
237  bool findTightest
238  (
239  const Type& shapes,
240  const point& sample,
241  treeBoundBox& tightest
242  ) const;
243 
244  //- Find nearest shape to sample
245  // Returns true if found nearer shape and updates
246  // tightest, tightestI, tightestDist
247  bool findNearest
248  (
249  const Type& shapes,
250  const point& sample,
251  treeBoundBox& tightest,
252  label& tightestI,
253  scalar& tightestDist
254  ) const;
255 
256  //- Find nearest shape to line
257  // Returns true if found nearer shape and updates nearest and
258  // tightest
259  bool findNearest
260  (
261  const Type& shapes,
262  const linePointRef& ln,
263  treeBoundBox& tightest,
264  label& tightestI, // index of nearest shape
265  point& linePoint, // nearest point on line
266  point& shapePoint // nearest point on shape
267  ) const;
268 
269  //- Find shapes not outside box. Return true if anything found.
270  bool findBox
271  (
272  const Type& shapes,
273  const boundBox& bb,
274  labelHashSet& elements
275  ) const;
276 
277  //- Find treeLeaves intersecting line segment [start..end]
278  // Updates: start
280  (
281  const label level,
282  const Type& shapes,
283  point& start,
284  const point& end
285  ) const;
286 
287 
288  //- Collect all treeLeafs in leafArray. leafIndex points to first
289  // empty slot in leafArray and gets updated.
290  void findLeaves
291  (
292  List<treeLeaf<Type>*>& leafArray,
293  label& leafIndex
294  ) const;
295 
296  //- Same but for const.
297  void findLeaves
298  (
299  List<const treeLeaf<Type>*>& leafArray,
300  label& leafIndex
301  ) const;
302 
303 
304  // Write
305 
306  //- Print contents of node.
307  void printNode
308  (
309  Ostream& os,
310  const label level
311  ) const;
312 
313  //- Write subleafs in OBJ format.
314  void writeOBJ
315  (
316  Ostream& os,
317  const label level,
318  label& vertNo
319  ) const;
320 
321 
322  // IOstream Operators
323 
324  friend Istream& operator>> <Type> (Istream&, treeNode<Type>&);
325  friend Ostream& operator<< <Type> (Ostream&, const treeNode<Type>&);
326 };
327 
328 
329 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
330 
331 } // End namespace Foam
332 
333 
334 #include "treeNodeI.H"
335 
336 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
337 
338 #ifdef NoRepository
339 # include "treeNode.C"
340 #endif
341 
342 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
343 
344 #endif
345 
346 // ************************ vim: set sw=4 sts=4 et: ************************ //