dynamicIndexedOctree.H
Go to the documentation of this file.
1 /*---------------------------------------------------------------------------*\
2  ========= |
3  \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
4  \\ / O peration | Website: https://openfoam.org
5  \\ / A nd | Copyright (C) 2011-2020 OpenFOAM Foundation
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::dynamicIndexedOctree
26 
27 Description
28  Non-pointer based hierarchical recursive searching.
29  Storage is dynamic, so elements can be deleted.
30 
31 SourceFiles
32  dynamicIndexedOctree.C
33 
34 \*---------------------------------------------------------------------------*/
35 
36 #ifndef dynamicIndexedOctree_H
37 #define dynamicIndexedOctree_H
38 
39 #include "treeBoundBox.H"
40 #include "pointIndexHit.H"
41 #include "FixedList.H"
42 #include "Ostream.H"
43 #include "HashSet.H"
44 #include "labelBits.H"
45 #include "PackedList.H"
46 #include "volumeType.H"
47 
48 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
49 
50 namespace Foam
51 {
52 
54 
55 // Forward declaration of classes
56 template<class Type> class dynamicIndexedOctree;
57 
58 template<class Type> Ostream& operator<<
59 (
60  Ostream&,
62 );
63 
64 class Istream;
65 
66 
67 /*---------------------------------------------------------------------------*\
68  Class dynamicIndexedOctreeName Declaration
69 \*---------------------------------------------------------------------------*/
70 
72 
73 
74 /*---------------------------------------------------------------------------*\
75  Class dynamicIndexedOctree Declaration
76 \*---------------------------------------------------------------------------*/
77 
78 template<class Type>
80 :
81  public dynamicIndexedOctreeName
82 {
83 public:
84 
85  // Data types
86 
87  //- Tree node. Has up pointer and down pointers.
88  class node
89  {
90  public:
91 
92  //- Bounding box of this node
94 
95  //- Parent node (index into nodes_ of tree)
96  label parent_;
97 
98  //- IDs of the 8 nodes on all sides of the mid point
101  friend Ostream& operator<< (Ostream& os, const node& n)
102  {
103  return os << n.bb_ << token::SPACE
104  << n.parent_ << token::SPACE << n.subNodes_;
105  }
107  friend Istream& operator>> (Istream& is, node& n)
108  {
109  return is >> n.bb_ >> n.parent_ >> n.subNodes_;
110  }
112  friend bool operator==(const node& a, const node& b)
113  {
114  return
115  a.bb_ == b.bb_
116  && a.parent_ == b.parent_
117  && a.subNodes_ == b.subNodes_;
118  }
120  friend bool operator!=(const node& a, const node& b)
121  {
122  return !(a == b);
123  }
124  };
125 
126 
127 private:
128 
129  // Static data
130 
131  //- Relative perturbation tolerance. Determines when point is
132  // considered to be close to face/edge of bb of node.
133  // The tolerance is relative to the bounding box of the smallest
134  // node.
135  static scalar perturbTol_;
136 
137 
138  // Private Data
139 
140  //- Underlying shapes for geometric queries.
141  const Type shapes_;
142 
143  const treeBoundBox bb_;
144 
145  const label maxLevels_;
146 
147  //- Current number of levels in the tree.
148  label nLevelsMax_;
149 
150  const scalar maxLeafRatio_;
151 
152  const label minSize_;
153 
154  const scalar maxDuplicity_;
155 
156  //- List of all nodes
157  DynamicList<node> nodes_;
158 
159  //- List of all contents (referenced by those nodes that are contents)
160  contentListList contents_;
161 
162  //- Per node per octant whether is fully inside/outside/mixed.
163  mutable PackedList<2> nodeTypes_;
164 
165  // Private Member Functions
166 
167  //- Helper: does bb intersect a sphere around sample? Or is any
168  // corner point of bb closer than nearestDistSqr to sample.
169  // (bb is implicitly provided as parent bb + octant)
170  static bool overlaps
171  (
172  const treeBoundBox& parentBb,
173  const direction octant,
174  const scalar nearestDistSqr,
175  const point& sample
176  );
177 
178  // Construction
179 
180  //- Split list of indices into 8 bins
181  // according to where they are in relation to mid.
182  void divide
183  (
184  const autoPtr<DynamicList<label>>& indices,
185  const treeBoundBox& bb,
186  contentListList& result
187  ) const;
188 
189  //- Subdivide the contents node at position contentI.
190  // Appends to contents.
191  node divide
192  (
193  const treeBoundBox& bb,
194  const label contentI,
195  const label parentNodeIndex,
196  const label octantToBeDivided
197  );
198 
199  // Recursively call the divide function
200  void recursiveSubDivision
201  (
202  const treeBoundBox& subBb,
203  const label contentI,
204  const label parentIndex,
205  const label octant,
206  label& nLevels
207  );
208 
209  //- Determine inside/outside per node (mixed if cannot be
210  // determined). Only valid for closed shapes.
211  volumeType calcVolumeType(const label nodeI) const;
212 
213  //- Search cached volume type.
214  volumeType getVolumeType(const label nodeI, const point&) const;
215 
216 
217  // Query
218 
219  //- Find nearest point to line.
220  void findNearest
221  (
222  const label nodeI,
223  const linePointRef& ln,
224 
225  treeBoundBox& tightest,
226  label& nearestShapeI,
227  point& linePoint,
228  point& nearestPoint
229  ) const;
230 
231  //- Return bbox of octant
232  treeBoundBox subBbox
233  (
234  const label parentNodeI,
235  const direction octant
236  ) const;
237 
238  //- Helper: take a point on/close to face of bb and push it
239  // inside or outside of bb.
240  static point pushPoint
241  (
242  const treeBoundBox&,
243  const point&,
244  const bool pushInside
245  );
246 
247  //- Helper: take a point on face of bb and push it
248  // inside or outside of bb.
249  static point pushPoint
250  (
251  const treeBoundBox&,
252  const direction,
253  const point&,
254  const bool pushInside
255  );
256 
257  //- Helper: take point on face(s) of bb and push it away from
258  // edges of face. If pt is not on a face does nothing.
259  static point pushPointIntoFace
260  (
261  const treeBoundBox& bb,
262  const vector& dir, // end-start
263  const point& pt
264  );
265 
266  //- Walk to parent of node+octant.
267  // Return false if top of tree reached.
268  bool walkToParent
269  (
270  const label nodeI,
271  const direction octant,
272 
273  label& parentNodeI,
274  label& parentOctant
275  ) const;
276 
277  //- Walk tree to neighbouring node. Return false if edge of tree
278  // hit.
279  bool walkToNeighbour
280  (
281  const point& facePoint,
282  const direction faceID, // direction to walk in
283  label& nodeI,
284  direction& octant
285  ) const;
286 
287  //- Debug: return verbose the bounding box faces
288  static word faceString(const direction faceID);
289 
290  //- Traverse a node. If intersects a triangle return first
291  // intersection point.
292  // findAny=true : return any intersection
293  // findAny=false: return nearest (to start) intersection
294  void traverseNode
295  (
296  const bool findAny,
297  const point& treeStart,
298  const vector& treeVec,
299 
300  const point& start,
301  const point& end,
302  const label nodeI,
303  const direction octantI,
304 
305  pointIndexHit& hitInfo,
306  direction& faceID
307  ) const;
308 
309  //- Find any or nearest intersection
310  pointIndexHit findLine
311  (
312  const bool findAny,
313  const point& treeStart,
314  const point& treeEnd,
315  const label startNodeI,
316  const direction startOctantI,
317  const bool verbose = false
318  ) const;
319 
320  //- Find any or nearest intersection of line between start and end.
321  pointIndexHit findLine
322  (
323  const bool findAny,
324  const point& start,
325  const point& end
326  ) const;
327 
328  //- Find all elements intersecting box.
329  void findBox
330  (
331  const label nodeI,
332  const treeBoundBox& searchBox,
333  labelHashSet& elements
334  ) const;
335 
336 
337  //- Find all elements intersecting sphere.
338  void findSphere
339  (
340  const label nodeI,
341  const point& centre,
342  const scalar radiusSqr,
343  labelHashSet& elements
344  ) const;
345 
346 
347  template<class CompareOp>
348  static void findNear
349  (
350  const scalar nearDist,
351  const bool okOrder,
352  const dynamicIndexedOctree<Type>& tree1,
353  const labelBits index1,
354  const treeBoundBox& bb1,
355  const dynamicIndexedOctree<Type>& tree2,
356  const labelBits index2,
357  const treeBoundBox& bb2,
358  CompareOp& cop
359  );
360 
361 
362  // Other
363 
364  //- Count number of elements on this and sublevels
365  label countElements(const labelBits index) const;
366 
367  //- Dump node+octant to an obj file
368  void writeOBJ(const label nodeI, const direction octant) const;
369 
370  //- From index into contents_ to subNodes_ entry
371  static labelBits contentPlusOctant
372  (
373  const label i,
374  const direction octant
375  )
376  {
377  return labelBits(-i - 1, octant);
378  }
379 
380  //- From index into nodes_ to subNodes_ entry
381  static labelBits nodePlusOctant
382  (
383  const label i,
384  const direction octant
385  )
386  {
387  return labelBits(i + 1, octant);
388  }
389 
390  //- From empty to subNodes_ entry
391  static labelBits emptyPlusOctant
392  (
393  const direction octant
394  )
395  {
396  return labelBits(0, octant);
397  }
398 
399 public:
400 
401  //- Get the perturbation tolerance
402  static scalar& perturbTol();
403 
404 
405  // Constructors
406 
407  //- Construct from shapes
409  (
410  const Type& shapes,
411  const treeBoundBox& bb,
412  const label maxLevels, // maximum number of levels
413  const scalar maxLeafRatio, // how many elements per leaf
414  const scalar maxDuplicity // in how many leaves is a shape on
415  // average
416  );
417 
418  //- Clone
420  {
422  (
423  new dynamicIndexedOctree<Type>(*this)
424  );
425  }
426 
427 
428  // Member Functions
429 
430  // Access
431 
432  //- Reference to shape
433  const Type& shapes() const
434  {
435  return shapes_;
436  }
437 
438  //- List of all nodes
439  const List<node>& nodes() const
440  {
441  return nodes_;
442  }
443 
444  //- List of all contents (referenced by those nodes that are
445  // contents)
446  const contentListList& contents() const
447  {
448  return contents_;
449  }
450 
451  //- Top bounding box
452  const treeBoundBox& bb() const
453  {
454  if (nodes_.empty())
455  {
457  << "Tree is empty" << abort(FatalError);
458  }
459  return nodes_[0].bb_;
460  }
461 
462 
463  // Conversions for entries in subNodes_.
465  static bool isContent(const labelBits i)
466  {
467  return i.val() < 0;
468  }
470  static bool isEmpty(const labelBits i)
471  {
472  return i.val() == 0;
473  }
475  static bool isNode(const labelBits i)
476  {
477  return i.val() > 0;
478  }
480  static label getContent(const labelBits i)
481  {
482  if (!isContent(i))
483  {
485  << abort(FatalError);
486  }
487  return -i.val()-1;
488  }
490  static label getNode(const labelBits i)
491  {
492  if (!isNode(i))
493  {
495  << abort(FatalError);
496  }
497  return i.val() - 1;
498  }
500  static direction getOctant(const labelBits i)
501  {
502  return i.bits();
503  }
504 
505 
506  // Queries
507 
508  //- Calculate nearest point on nearest shape.
509  // Returns
510  // - bool : any point found nearer than nearestDistSqr
511  // - label: index in shapes
512  // - point: actual nearest point found
513  pointIndexHit findNearest
514  (
515  const point& sample,
516  const scalar nearestDistSqr
517  ) const;
518 
519  //- Low level: calculate nearest starting from subnode.
520  void findNearest
521  (
522  const label nodeI,
523  const point&,
524 
525  scalar& nearestDistSqr,
526  label& nearestShapeI,
527  point& nearestPoint
528  ) const;
529 
530  //- Find nearest to line.
531  // Returns
532  // - bool : any point found?
533  // - label: index in shapes
534  // - point: actual nearest point found
535  // sets:
536  // - linePoint : corresponding nearest point on line
537  pointIndexHit findNearest
538  (
539  const linePointRef& ln,
540  treeBoundBox& tightest,
541  point& linePoint
542  ) const;
543 
544  //- Find nearest intersection of line between start and end.
545  pointIndexHit findLine
546  (
547  const point& start,
548  const point& end
549  ) const;
550 
551  //- Find any intersection of line between start and end.
553  (
554  const point& start,
555  const point& end
556  ) const;
557 
558  //- Find (in no particular order) indices of all shapes inside or
559  // overlapping bounding box (i.e. all shapes not outside box)
560  labelList findBox(const treeBoundBox& bb) const;
561 
562  //- Find (in no particular order) indices of all shapes inside or
563  // overlapping a bounding sphere (i.e. all shapes not outside
564  // sphere)
565  labelList findSphere
566  (
567  const point& centre,
568  const scalar radiusSqr
569  ) const;
570 
571  //- Find deepest node (as parent+octant) containing point. Starts
572  // off from starting index in nodes_ (use 0 to start from top)
573  // Use getNode and getOctant to extract info, or call findIndices.
574  labelBits findNode(const label nodeI, const point&) const;
575 
576  //- Find shape containing point. Only implemented for certain
577  // shapes.
578  label findInside(const point&) const;
579 
580  //- Find the shape indices that occupy the result of findNode
581  const labelList& findIndices(const point&) const;
582 
583  //- Determine type (inside/outside/mixed) for point. unknown if
584  // cannot be determined (e.g. non-manifold surface)
585  volumeType getVolumeType(const point&) const;
586 
587  //- Helper function to return the side. Returns outside if
588  // outsideNormal&vec >= 0, inside otherwise
589  static volumeType getSide
590  (
591  const vector& outsideNormal,
592  const vector& vec
593  );
594 
595  //- Helper: does bb intersect a sphere around sample? Or is any
596  // corner point of bb closer than nearestDistSqr to sample.
597  static bool overlaps
598  (
599  const point& bbMin,
600  const point& bbMax,
601  const scalar nearestDistSqr,
602  const point& sample
603  );
604 
605  //- Find near pairs and apply CompareOp to them.
606  // tree2 can be *this or different tree.
607  template<class CompareOp>
608  void findNear
609  (
610  const scalar nearDist,
611  const dynamicIndexedOctree<Type>& tree2,
612  CompareOp& cop
613  ) const;
614 
615 
616  // Edit
617 
618  //- Insert a new object into the tree.
619  bool insert(label startIndex, label endIndex);
620 
621  bool insertIndex
622  (
623  const label nodIndex,
624  const label index,
625  label& nLevels
626  );
627 
628  //- Remove an object from the tree.
629  bool remove(const label index);
630 
631  label removeIndex(const label nodIndex, const label index);
632 
633 
634  // Write
635 
636  //- Print tree. Either print all indices (printContent = true) or
637  // just size of contents nodes.
638  void print
639  (
641  const bool printContents,
642  const label
643  ) const;
644 
645  bool write(Ostream& os) const;
646 
647  void writeTreeInfo() const;
648 
649 
650  // IOstream Operators
651 
652  friend Ostream& operator<< <Type>
653  (
654  Ostream&,
656  );
657 };
658 
659 
660 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
661 
662 } // End namespace Foam
663 
664 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
665 
666 #ifdef NoRepository
667  #include "dynamicIndexedOctree.C"
668 #endif
669 
670 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
671 
672 #endif
673 
674 // ************************************************************************* //
void divide(FieldField< Field, Type > &f, const FieldField< Field, Type > &f1, const FieldField< Field, scalar > &f2)
TemplateName(blendedSchemeBase)
const labelList & findIndices(const point &) const
Find the shape indices that occupy the result of findNode.
bool empty() const
Return true if the UList is empty (ie, size() is zero)
Definition: UListI.H:325
intWM_LABEL_SIZE_t label
A label is an int32_t or int64_t as specified by the pre-processor macro WM_LABEL_SIZE.
Definition: label.H:59
A line primitive.
Definition: line.H:56
Tree node. Has up pointer and down pointers.
A 1D vector of objects of type <T> with a fixed size <Size>.
Definition: FixedList.H:54
error FatalError
#define FatalErrorInFunction
Report an error message using Foam::FatalError.
Definition: error.H:323
A 1D array of objects of type <T>, where the size of the vector is known and used for subscript bound...
Definition: HashTable.H:59
void print(prefixOSstream &, const bool printContents, const label) const
Print tree. Either print all indices (printContent = true) or.
uint8_t direction
Definition: direction.H:45
An Istream is an abstract base class for all input systems (streams, files, token lists etc)...
Definition: Istream.H:57
label parent_
Parent node (index into nodes_ of tree)
const dimensionedScalar b
Wien displacement law constant: default SI units: [m K].
Definition: createFields.H:27
bool insert(label startIndex, label endIndex)
Insert a new object into the tree.
This class describes the interaction of (usually) a face and a point. It carries the info of a succes...
Definition: PointIndexHit.H:53
DynamicList< autoPtr< DynamicList< label > > > contentListList
static bool isContent(const labelBits i)
FixedList< labelBits, 8 > subNodes_
IDs of the 8 nodes on all sides of the mid point.
static label getContent(const labelBits i)
label removeIndex(const label nodIndex, const label index)
static bool isEmpty(const labelBits i)
A 1D vector of objects of type <T> that resizes itself as necessary to accept the new objects...
Definition: DynamicList.H:56
Version of OSstream which prints a prefix on each line.
friend Ostream & operator<<(Ostream &os, const node &n)
const Type & shapes() const
Reference to shape.
A class for handling words, derived from string.
Definition: word.H:59
direction bits() const
Definition: labelBits.H:102
Non-pointer based hierarchical recursive searching. Storage is dynamic, so elements can be deleted...
treeBoundBox bb_
Bounding box of this node.
errorManip< error > abort(error &err)
Definition: errorManip.H:131
bool ln(const fileName &src, const fileName &dst)
Create a softlink. dst should not exist. Returns true if successful.
Definition: POSIX.C:908
An Ostream is an abstract base class for all output systems (streams, files, token lists...
Definition: Ostream.H:54
friend Istream & operator>>(Istream &is, node &n)
bool insertIndex(const label nodIndex, const label index, label &nLevels)
label facePoint(const int facei, const block &block, const label i, const label j)
friend bool operator==(const node &a, const node &b)
dynamicIndexedOctree(const Type &shapes, const treeBoundBox &bb, const label maxLevels, const scalar maxLeafRatio, const scalar maxDuplicity)
Construct from shapes.
const List< node > & nodes() const
List of all nodes.
static scalar & perturbTol()
Get the perturbation tolerance.
static volumeType getSide(const vector &outsideNormal, const vector &vec)
Helper function to return the side. Returns outside if.
friend bool operator!=(const node &a, const node &b)
pointIndexHit findLineAny(const point &start, const point &end) const
Find any intersection of line between start and end.
autoPtr< dynamicIndexedOctree< Type > > clone() const
Clone.
Standard boundBox + extra functionality for use in octree.
Definition: treeBoundBox.H:87
A 29bits label and 3bits direction packed into single label.
Definition: labelBits.H:51
labelBits findNode(const label nodeI, const point &) const
Find deepest node (as parent+octant) containing point. Starts.
label n
static bool isNode(const labelBits i)
An auto-pointer similar to the STL auto_ptr but with automatic casting to a reference to the type and...
Definition: PtrList.H:52
const contentListList & contents() const
List of all contents (referenced by those nodes that are.
static label getNode(const labelBits i)
label val() const
Definition: labelBits.H:97
label findInside(const point &) const
Find shape containing point. Only implemented for certain.
static direction getOctant(const labelBits i)
bool write(Ostream &os) const
Namespace for OpenFOAM.
const treeBoundBox & bb() const
Top bounding box.