FreeFOAM The Cross-Platform CFD Toolkit
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) 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::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 <meshTools/treeBoundBox.H>
40 #include <OpenFOAM/FixedList.H>
41 #include <OpenFOAM/Ostream.H>
42 #include <OpenFOAM/HashSet.H>
43 #include "labelBits.H"
44 #include <OpenFOAM/PackedList.H>
45 
46 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
47 
48 namespace Foam
49 {
50 
51 // Forward declaration of classes
52 template<class Type> class indexedOctree;
53 template<class Type> Ostream& operator<<(Ostream&, const indexedOctree<Type>&);
54 class Istream;
55 
56 
57 /*---------------------------------------------------------------------------*\
58  Class indexedOctreeName Declaration
59 \*---------------------------------------------------------------------------*/
60 
61 TemplateName(indexedOctree);
62 
63 
64 /*---------------------------------------------------------------------------*\
65  Class indexedOctree Declaration
66 \*---------------------------------------------------------------------------*/
67 
68 template <class Type>
70 :
71  public indexedOctreeName
72 {
73 public:
74 
75  // Data types
76 
77  //- volume types
79  {
80  UNKNOWN = 0,
81  MIXED = 1,
82  INSIDE = 2,
83  OUTSIDE = 3
84  };
85 
86 
87  // Tree node. Has up pointer and down pointers.
88 
89  class node
90  {
91  public:
92 
93  //- Bounding box of this node
95 
96  //- parent node (index into nodes_ of tree)
97  label parent_;
98 
99  //- IDs of the 8 nodes on all sides of the mid point
101 
102  friend Ostream& operator<< (Ostream& os, const node& n)
103  {
104  return os << n.bb_ << token::SPACE
105  << n.parent_ << token::SPACE << n.subNodes_;
106  }
107 
108  friend Istream& operator>> (Istream& is, node& n)
109  {
110  return is >> n.bb_ >> n.parent_ >> n.subNodes_;
111  }
112 
113  friend bool operator==(const node& a, const node& b)
114  {
115  return
116  a.bb_ == b.bb_
117  && a.parent_ == b.parent_
118  && a.subNodes_ == b.subNodes_;
119  }
120 
121  friend bool operator!=(const node& a, const node& b)
122  {
123  return !(a == b);
124  }
125  };
126 
127 
128 private:
129 
130  // Static data
131 
132  //- Relative peturbation tolerance. Determines when point is
133  // considered to be close to face/edge of bb of node.
134  // The tolerance is relative to the bounding box of the smallest
135  // node.
136  static scalar perturbTol_;
137 
138 
139  // Private data
140 
141  //- Underlying shapes for geometric queries.
142  const Type shapes_;
143 
144  //- List of all nodes
145  List<node> nodes_;
146 
147  //- List of all contents (referenced by those nodes that are contents)
148  labelListList contents_;
149 
150  //- Per node per octant whether is fully inside/outside/mixed.
151  mutable PackedList<2> nodeTypes_;
152 
153  // Private Member Functions
154 
155  //- Helper: does bb intersect a sphere around sample? Or is any
156  // corner point of bb closer than nearestDistSqr to sample.
157  // (bb is implicitly provided as parent bb + octant)
158  static bool overlaps
159  (
160  const treeBoundBox& parentBb,
161  const direction octant,
162  const scalar nearestDistSqr,
163  const point& sample
164  );
165 
166  // Construction
167 
168  //- Split list of indices into 8 bins according to where they are in
169  // relation to mid.
170  void divide
171  (
172  const labelList& indices,
173  const treeBoundBox& bb,
174  labelListList& result
175  ) const;
176 
177  //- Subdivide the contents node at position contentI. Appends to
178  // contents.
179  node divide
180  (
181  const treeBoundBox& bb,
183  const label contentI
184  ) const;
185 
186  //- Split any contents node with more than minSize elements.
187  void splitNodes
188  (
189  const label minSize,
192  ) const;
193 
194  static label compactContents
195  (
198  const label compactLevel,
199  const label nodeI,
200  const label level,
201  List<labelList>& compactedContents,
202  label& compactI
203  );
204 
205  //- Determine inside/outside per node (mixed if cannot be
206  // determined). Only valid for closed shapes.
207  volumeType calcVolumeType(const label nodeI) const;
208 
209  //- Search cached volume type.
210  volumeType getVolumeType(const label nodeI, const point&) const;
211 
212 
213  // Query
214 
215  //- Find nearest point to line.
216  void findNearest
217  (
218  const label nodeI,
219  const linePointRef& ln,
220 
221  treeBoundBox& tightest,
222  label& nearestShapeI,
223  point& linePoint,
224  point& nearestPoint
225  ) const;
226 
227  //- Return bbox of octant
228  treeBoundBox subBbox
229  (
230  const label parentNodeI,
231  const direction octant
232  ) const;
233 
234  //- Helper: take a point on/close to face of bb and push it
235  // inside or outside of bb.
236  static point pushPoint
237  (
238  const treeBoundBox&,
239  const point&,
240  const bool pushInside
241  );
242 
243  //- Helper: take a point on face of bb and push it
244  // inside or outside of bb.
245  static point pushPoint
246  (
247  const treeBoundBox&,
248  const direction,
249  const point&,
250  const bool pushInside
251  );
252 
253  //- Helper: take point on face(s) of bb and push it away from
254  // edges of face.
255  static point pushPointIntoFace
256  (
257  const treeBoundBox& bb,
258  const vector& dir, // end-start
259  const point& pt
260  );
261 
263  //static void checkMultipleFaces
264  //(
265  // const treeBoundBox& bb,
266  // const vector& dir, // end-start
267  // pointIndexHit& faceHitInfo,
268  // direction& faceID
269  //);
270 
271  //- Walk to parent of node+octant.
272  bool walkToParent
273  (
274  const label nodeI,
275  const direction octant,
276 
277  label& parentNodeI,
278  label& parentOctant
279  ) const;
280 
281  //- Walk tree to neighbouring node. Return false if edge of tree
282  // hit.
283  bool walkToNeighbour
284  (
285  const point& facePoint,
286  const direction faceID, // direction to walk in
287  label& nodeI,
288  direction& octant
289  ) const;
290 
291  //- Debug: return verbose the bounding box faces
292  static word faceString(const direction faceID);
293 
294  //- Traverse a node. If intersects a triangle return first
295  // intersection point.
296  // findAny=true : return any intersection
297  // findAny=false: return nearest (to start) intersection
298  void traverseNode
299  (
300  const bool findAny,
301  const point& treeStart,
302  const vector& treeVec,
303 
304  const point& start,
305  const point& end,
306  const label nodeI,
307  const direction octantI,
308 
309  pointIndexHit& hitInfo,
310  direction& faceID
311  ) const;
312 
313  //- Find any or nearest intersection
314  pointIndexHit findLine
315  (
316  const bool findAny,
317  const point& treeStart,
318  const point& treeEnd,
319  const label startNodeI,
320  const direction startOctantI,
321  const bool verbose = false
322  ) const;
323 
324  //- Find any or nearest intersection of line between start and end.
325  pointIndexHit findLine
326  (
327  const bool findAny,
328  const point& start,
329  const point& end
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  // Other
341 
342  //- Count number of elements on this and sublevels
343  label countElements(const labelBits index) const;
344 
345  //- Dump node+octant to an obj file
346  void writeOBJ(const label nodeI, const direction octant) const;
347 
348  //- From index into contents_ to subNodes_ entry
349  static labelBits contentPlusOctant
350  (
351  const label i,
352  const direction octant
353  )
354  {
355  return labelBits(-i - 1, octant);
356  }
357 
358  //- From index into nodes_ to subNodes_ entry
359  static labelBits nodePlusOctant
360  (
361  const label i,
362  const direction octant
363  )
364  {
365  return labelBits(i + 1, octant);
366  }
367 
368  //- From empty to subNodes_ entry
369  static labelBits emptyPlusOctant
370  (
371  const direction octant
372  )
373  {
374  return labelBits(0, octant);
375  }
376 
377 public:
378 
379  //- Get the perturbation tolerance
380  static scalar& perturbTol();
381 
382 
383  // Constructors
384 
385  //- Construct null
386  indexedOctree(const Type& shapes);
387 
388  //- Construct from components
390  (
391  const Type& shapes,
392  const List<node>& nodes,
393  const labelListList& contents
394  );
395 
396  //- Construct from shapes
398  (
399  const Type& shapes,
400  const treeBoundBox& bb,
401  const label maxLevels, // maximum number of levels
402  const scalar maxLeafRatio, // how many elements per leaf
403  const scalar maxDuplicity // in how many leaves is a shape on
404  // average
405  );
406 
407  //- Construct from Istream
408  indexedOctree(const Type& shapes, Istream& is);
409 
410  //- Clone
412  {
414  (
415  new indexedOctree<Type>(*this)
416  );
417  }
418 
419  // Member Functions
420 
421  // Access
422 
423  //- Reference to shape
424  const Type& shapes() const
425  {
426  return shapes_;
427  }
428 
429  //- List of all nodes
430  const List<node>& nodes() const
431  {
432  return nodes_;
433  }
434 
435  //- List of all contents (referenced by those nodes that are
436  // contents)
437  const labelListList& contents() const
438  {
439  return contents_;
440  }
441 
442  //- Top bounding box
443  const treeBoundBox& bb() const
444  {
445  if (nodes_.empty())
446  {
447  FatalErrorIn("indexedOctree<Type>::bb() const")
448  << "Tree is empty" << abort(FatalError);
449  }
450  return nodes_[0].bb_;
451  }
452 
453 
454  // Conversions for entries in subNodes_.
455 
456  static bool isContent(const labelBits i)
457  {
458  return i.val() < 0;
459  }
460 
461  static bool isEmpty(const labelBits i)
462  {
463  return i.val() == 0;
464  }
465 
466  static bool isNode(const labelBits i)
467  {
468  return i.val() > 0;
469  }
470 
471  static label getContent(const labelBits i)
472  {
473  if (!isContent(i))
474  {
475  FatalErrorIn("getContent(const label)")
476  << abort(FatalError);
477  }
478  return -i.val()-1;
479  }
480 
481  static label getNode(const labelBits i)
482  {
483  if (!isNode(i))
484  {
485  FatalErrorIn("getNode(const label)")
486  << abort(FatalError);
487  }
488  return i.val() - 1;
489  }
490 
491  static direction getOctant(const labelBits i)
492  {
493  return i.bits();
494  }
495 
496 
497  // Queries
498 
499  //- Calculate nearest point on nearest shape. Returns
500  // - bool : any point found nearer than nearestDistSqr
501  // - label: index in shapes
502  // - point: actual nearest point found
503  pointIndexHit findNearest
504  (
505  const point& sample,
506  const scalar nearestDistSqr
507  ) const;
508 
509  //- Low level: calculate nearest starting from subnode.
510  void findNearest
511  (
512  const label nodeI,
513  const point&,
514 
515  scalar& nearestDistSqr,
516  label& nearestShapeI,
517  point& nearestPoint
518  ) const;
519 
520  //- Find nearest to line. Returns
521  // - bool : any point found?
522  // - label: index in shapes
523  // - point: actual nearest point found
524  // sets:
525  // - linePoint : corresponding nearest point on line
526  pointIndexHit findNearest
527  (
528  const linePointRef& ln,
529  treeBoundBox& tightest,
530  point& linePoint
531  ) const;
532 
533  //- Find nearest intersection of line between start and end.
534  pointIndexHit findLine
535  (
536  const point& start,
537  const point& end
538  ) const;
539 
540  //- Find any intersection of line between start and end.
542  (
543  const point& start,
544  const point& end
545  ) const;
546 
547  //- Find (in no particular order) indices of all shapes inside or
548  // overlapping bounding box (i.e. all shapes not outside box)
549  labelList findBox(const treeBoundBox& bb) const;
550 
551  //- Find deepest node (as parent+octant) containing point. Starts
552  // off from starting index in nodes_ (use 0 to start from top)
553  // Use getNode, getOctant to extract info.
554  labelBits findNode(const label nodeI, const point&) const;
555 
556  //- Determine type (inside/outside/mixed) for point. unknown if
557  // cannot be determined (e.g. non-manifold surface)
558  volumeType getVolumeType(const point&) const;
559 
560  //- Helper function to return the side. Returns outside if
561  // outsideNormal&vec >= 0, inside otherwise
562  static volumeType getSide
563  (
564  const vector& outsideNormal,
565  const vector& vec
566  );
567 
568  //- Helper: does bb intersect a sphere around sample? Or is any
569  // corner point of bb closer than nearestDistSqr to sample.
570  static bool overlaps
571  (
572  const point& bbMin,
573  const point& bbMax,
574  const scalar nearestDistSqr,
575  const point& sample
576  );
577 
578 
579  // Write
580 
581  //- Print tree. Either print all indices (printContent = true) or
582  // just size of contents nodes.
583  void print
584  (
586  const bool printContents,
587  const label
588  ) const;
589 
590  bool write(Ostream& os) const;
591 
592  // IOstream Operators
593 
594  friend Ostream& operator<< <Type>(Ostream&, const indexedOctree<Type>&);
595 
596 };
597 
598 
599 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
600 
601 } // End namespace Foam
602 
603 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
604 
605 #ifdef NoRepository
606 # include "indexedOctree.C"
607 #endif
608 
609 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
610 
611 #endif
612 
613 // ************************ vim: set sw=4 sts=4 et: ************************ //