1 /*---------------------------------------------------------------------------*\
3 \\ / F ield | foam-extend: Open Source CFD
4 \\ / O peration | Version: 3.2
5 \\ / A nd | Web: http://www.foam-extend.org
6 \\/ M anipulation | For copyright notice see file Copyright
7 -------------------------------------------------------------------------------
9 This file is part of foam-extend.
11 foam-extend is free software: you can redistribute it and/or modify it
12 under the terms of the GNU General Public License as published by the
13 Free Software Foundation, either version 3 of the License, or (at your
14 option) any later version.
16 foam-extend is distributed in the hope that it will be useful, but
17 WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 General Public License for more details.
21 You should have received a copy of the GNU General Public License
22 along with foam-extend. If not, see <http://www.gnu.org/licenses/>.
28 Non-pointer based hierarchical recursive searching
33 \*---------------------------------------------------------------------------*/
35 #ifndef indexedOctree_H
36 #define indexedOctree_H
38 #include "treeBoundBox.H"
39 #include "pointIndexHit.H"
40 #include "FixedList.H"
43 #include "labelBits.H"
44 #include "PackedList.H"
46 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
51 // Forward declaration of classes
52 template<class Type> class indexedOctree;
53 template<class Type> Ostream& operator<<(Ostream&, const indexedOctree<Type>&);
57 /*---------------------------------------------------------------------------*\
58 Class indexedOctreeName Declaration
59 \*---------------------------------------------------------------------------*/
61 TemplateName(indexedOctree);
64 /*---------------------------------------------------------------------------*\
65 Class indexedOctree Declaration
66 \*---------------------------------------------------------------------------*/
71 public indexedOctreeName
87 // Tree node. Has up pointer and down pointers.
93 //- Bounding box of this node
96 //- Parent node (index into nodes_ of tree)
99 //- IDs of the 8 nodes on all sides of the mid point
100 FixedList<labelBits, 8> subNodes_;
102 friend Ostream& operator<< (Ostream& os, const node& n)
104 return os << n.bb_ << token::SPACE
105 << n.parent_ << token::SPACE << n.subNodes_;
108 friend Istream& operator>> (Istream& is, node& n)
110 return is >> n.bb_ >> n.parent_ >> n.subNodes_;
113 friend bool operator==(const node& a, const node& b)
117 && a.parent_ == b.parent_
118 && a.subNodes_ == b.subNodes_;
121 friend bool operator!=(const node& a, const node& b)
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
136 static scalar perturbTol_;
141 //- Underlying shapes for geometric queries.
144 //- List of all nodes
147 //- List of all contents (referenced by those nodes that are contents)
148 labelListList contents_;
150 //- Per node per octant whether is fully inside/outside/mixed.
151 mutable PackedList<2> nodeTypes_;
153 // Private Member Functions
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)
160 const treeBoundBox& parentBb,
161 const direction octant,
162 const scalar nearestDistSqr,
168 //- Split list of indices into 8 bins according to where they are
169 // in relation to mid.
172 const labelList& indices,
173 const treeBoundBox& bb,
174 labelListList& result
177 //- Subdivide the contents node at position contentI. Appends to
181 const treeBoundBox& bb,
182 DynamicList<labelList>& contents,
186 //- Split any contents node with more than minSize elements.
190 DynamicList<node>& nodes,
191 DynamicList<labelList>& contents
194 static label compactContents
196 DynamicList<node>& nodes,
197 DynamicList<labelList>& contents,
198 const label compactLevel,
201 List<labelList>& compactedContents,
205 //- Determine inside/outside per node (mixed if cannot be
206 // determined). Only valid for closed shapes.
207 volumeType calcVolumeType(const label nodeI) const;
209 //- Search cached volume type.
210 volumeType getVolumeType(const label nodeI, const point&) const;
215 //- Find nearest point to line.
219 const linePointRef& ln,
221 treeBoundBox& tightest,
222 label& nearestShapeI,
227 //- Return bbox of octant
230 const label parentNodeI,
231 const direction octant
234 //- Helper: take a point on/close to face of bb and push it
235 // inside or outside of bb.
236 static point pushPoint
240 const bool pushInside
243 //- Helper: take a point on face of bb and push it
244 // inside or outside of bb.
245 static point pushPoint
250 const bool pushInside
253 //- Helper: take point on face(s) of bb and push it away from
255 static point pushPointIntoFace
257 const treeBoundBox& bb,
258 const vector& dir, // end-start
262 ////- Push point on multiple faces away from any corner/edge.
263 //static void checkMultipleFaces
265 // const treeBoundBox& bb,
266 // const vector& dir, // end-start
267 // pointIndexHit& faceHitInfo,
271 //- Walk to parent of node+octant.
275 const direction octant,
281 //- Walk tree to neighbouring node. Return false if edge of tree
285 const point& facePoint,
286 const direction faceID, // direction to walk in
291 //- Debug: return verbose the bounding box faces
292 static word faceString(const direction faceID);
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
301 const point& treeStart,
302 const vector& treeVec,
307 const direction octantI,
309 pointIndexHit& hitInfo,
313 //- Find any or nearest intersection
314 pointIndexHit findLine
317 const point& treeStart,
318 const point& treeEnd,
319 const label startNodeI,
320 const direction startOctantI,
321 const bool verbose = false
324 //- Find any or nearest intersection of line between start and end.
325 pointIndexHit findLine
332 //- Find all elements intersecting box.
336 const treeBoundBox& searchBox,
337 labelHashSet& elements
342 //- Count number of elements on this and sublevels
343 label countElements(const labelBits index) const;
345 //- Dump node+octant to an obj file
346 void writeOBJ(const label nodeI, const direction octant) const;
348 //- From index into contents_ to subNodes_ entry
349 static labelBits contentPlusOctant
352 const direction octant
355 return labelBits(-i - 1, octant);
358 //- From index into nodes_ to subNodes_ entry
359 static labelBits nodePlusOctant
362 const direction octant
365 return labelBits(i + 1, octant);
368 //- From empty to subNodes_ entry
369 static labelBits emptyPlusOctant
371 const direction octant
374 return labelBits(0, octant);
381 //- Get the perturbation tolerance
382 static scalar& perturbTol();
388 indexedOctree(const Type& shapes);
390 //- Construct from components
394 const List<node>& nodes,
395 const labelListList& contents
398 //- Construct from shapes
402 const treeBoundBox& bb,
403 const label maxLevels, // maximum number of levels
404 const scalar maxLeafRatio, // how many elements per leaf
405 const scalar maxDuplicity // in how many leaves is a shape on
409 //- Construct from Istream
410 indexedOctree(const Type& shapes, Istream& is);
413 autoPtr<indexedOctree<Type> > clone() const
415 return autoPtr<indexedOctree<Type> >
417 new indexedOctree<Type>(*this)
425 //- Reference to shape
426 const Type& shapes() const
431 //- List of all nodes
432 const List<node>& nodes() const
437 //- List of all contents (referenced by those nodes that are
439 const labelListList& contents() const
445 const treeBoundBox& bb() const
449 FatalErrorIn("indexedOctree<Type>::bb() const")
450 << "Tree is empty" << abort(FatalError);
452 return nodes_[0].bb_;
456 // Conversions for entries in subNodes_.
458 static bool isContent(const labelBits i)
463 static bool isEmpty(const labelBits i)
468 static bool isNode(const labelBits i)
473 static label getContent(const labelBits i)
477 FatalErrorIn("getContent(const label)")
478 << abort(FatalError);
483 static label getNode(const labelBits i)
487 FatalErrorIn("getNode(const label)")
488 << abort(FatalError);
493 static direction getOctant(const labelBits i)
501 //- Calculate nearest point on nearest shape. Returns
502 // - bool : any point found nearer than nearestDistSqr
503 // - label: index in shapes
504 // - point: actual nearest point found
505 pointIndexHit findNearest
508 const scalar nearestDistSqr
511 //- Low level: calculate nearest starting from subnode.
517 scalar& nearestDistSqr,
518 label& nearestShapeI,
522 //- Find nearest to line. Returns
523 // - bool : any point found?
524 // - label: index in shapes
525 // - point: actual nearest point found
527 // - linePoint : corresponding nearest point on line
528 pointIndexHit findNearest
530 const linePointRef& ln,
531 treeBoundBox& tightest,
535 //- Find nearest intersection of line between start and end.
536 pointIndexHit findLine
542 //- Find any intersection of line between start and end.
543 pointIndexHit findLineAny
549 //- Find (in no particular order) indices of all shapes inside or
550 // overlapping bounding box (i.e. all shapes not outside box)
551 labelList findBox(const treeBoundBox& bb) const;
553 //- Find deepest node (as parent+octant) containing point. Starts
554 // off from starting index in nodes_ (use 0 to start from top)
555 // Use getNode, getOctant to extract info.
556 labelBits findNode(const label nodeI, const point&) const;
558 //- Determine type (inside/outside/mixed) for point. unknown if
559 // cannot be determined (e.g. non-manifold surface)
560 volumeType getVolumeType(const point&) const;
562 //- Helper function to return the side. Returns outside if
563 // outsideNormal&vec >= 0, inside otherwise
564 static volumeType getSide
566 const vector& outsideNormal,
570 //- Helper: does bb intersect a sphere around sample? Or is any
571 // corner point of bb closer than nearestDistSqr to sample.
576 const scalar nearestDistSqr,
583 //- Print tree. Either print all indices (printContent = true) or
584 // just size of contents nodes.
588 const bool printContents,
592 bool write(Ostream& os) const;
594 // IOstream Operators
596 friend Ostream& operator<< <Type>(Ostream&, const indexedOctree<Type>&);
601 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
603 } // End namespace Foam
605 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
608 # include "indexedOctree.C"
611 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
615 // ************************************************************************* //