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