Formatting
[foam-extend-3.2.git] / src / foam / algorithms / octree / indexedOctree / indexedOctree.H
blob72e918e9cd1bbc02c32c45f4f7e027e40ef0cd6c
1 /*---------------------------------------------------------------------------*\
2   =========                 |
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 -------------------------------------------------------------------------------
8 License
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/>.
24 Class
25     Foam::indexedOctree
27 Description
28     Non-pointer based hierarchical recursive searching
30 SourceFiles
31     indexedOctree.C
33 \*---------------------------------------------------------------------------*/
35 #ifndef indexedOctree_H
36 #define indexedOctree_H
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"
46 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
48 namespace Foam
51 // Forward declaration of classes
52 template<class Type> class indexedOctree;
53 template<class Type> Ostream& operator<<(Ostream&, const indexedOctree<Type>&);
54 class Istream;
57 /*---------------------------------------------------------------------------*\
58                         Class indexedOctreeName Declaration
59 \*---------------------------------------------------------------------------*/
61 TemplateName(indexedOctree);
64 /*---------------------------------------------------------------------------*\
65                            Class indexedOctree Declaration
66 \*---------------------------------------------------------------------------*/
68 template <class Type>
69 class indexedOctree
71     public indexedOctreeName
73 public:
75     // Data types
77         //- volume types
78         enum volumeType
79         {
80             UNKNOWN = 0,
81             MIXED = 1,
82             INSIDE = 2,
83             OUTSIDE = 3
84         };
87     // Tree node. Has up pointer and down pointers.
89         class node
90         {
91         public:
93             //- Bounding box of this node
94             treeBoundBox bb_;
96             //- Parent node (index into nodes_ of tree)
97             label parent_;
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)
103             {
104                 return os << n.bb_ << token::SPACE
105                     << n.parent_ << token::SPACE << n.subNodes_;
106             }
108             friend Istream& operator>> (Istream& is, node& n)
109             {
110                 return is >> n.bb_ >> n.parent_ >> n.subNodes_;
111             }
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             }
121             friend bool operator!=(const node& a, const node& b)
122             {
123                 return !(a == b);
124             }
125         };
128 private:
130     // Static data
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_;
139     // Private data
141         //- Underlying shapes for geometric queries.
142         const Type shapes_;
144         //- List of all nodes
145         List<node> 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)
158         static bool overlaps
159         (
160             const treeBoundBox& parentBb,
161             const direction octant,
162             const scalar nearestDistSqr,
163             const point& sample
164         );
166         // Construction
168             //- Split list of indices into 8 bins according to where they are
169             //  in relation to mid.
170             void divide
171             (
172                 const labelList& indices,
173                 const treeBoundBox& bb,
174                 labelListList& result
175             ) const;
177             //- Subdivide the contents node at position contentI. Appends to
178             //  contents.
179             node divide
180             (
181                 const treeBoundBox& bb,
182                 DynamicList<labelList>& contents,
183                 const label contentI
184             ) const;
186             //- Split any contents node with more than minSize elements.
187             void splitNodes
188             (
189                 const label minSize,
190                 DynamicList<node>& nodes,
191                 DynamicList<labelList>& contents
192             ) const;
194             static label compactContents
195             (
196                 DynamicList<node>& nodes,
197                 DynamicList<labelList>& contents,
198                 const label compactLevel,
199                 const label nodeI,
200                 const label level,
201                 List<labelList>& compactedContents,
202                 label& compactI
203             );
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;
213         // Query
215             //- Find nearest point to line.
216             void findNearest
217             (
218                 const label nodeI,
219                 const linePointRef& ln,
221                 treeBoundBox& tightest,
222                 label& nearestShapeI,
223                 point& linePoint,
224                 point& nearestPoint
225             ) const;
227             //- Return bbox of octant
228             treeBoundBox subBbox
229             (
230                 const label parentNodeI,
231                 const direction octant
232             ) const;
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             );
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             );
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             );
262             ////- Push point on multiple faces away from any corner/edge.
263             //static void checkMultipleFaces
264             //(
265             //    const treeBoundBox& bb,
266             //    const vector& dir,          // end-start
267             //    pointIndexHit& faceHitInfo,
268             //    direction& faceID
269             //);
271             //- Walk to parent of node+octant.
272             bool walkToParent
273             (
274                 const label nodeI,
275                 const direction octant,
277                 label& parentNodeI,
278                 label& parentOctant
279             ) const;
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;
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
298             void traverseNode
299             (
300                 const bool findAny,
301                 const point& treeStart,
302                 const vector& treeVec,
304                 const point& start,
305                 const point& end,
306                 const label nodeI,
307                 const direction octantI,
309                 pointIndexHit& hitInfo,
310                 direction& faceID
311             ) const;
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;
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;
332             //- Find all elements intersecting box.
333             void findBox
334             (
335                 const label nodeI,
336                 const treeBoundBox& searchBox,
337                 labelHashSet& elements
338             ) const;
340         // Other
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
350             (
351                 const label i,
352                 const direction octant
353             )
354             {
355                 return labelBits(-i - 1, octant);
356             }
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             }
368             //- From empty to subNodes_ entry
369             static labelBits emptyPlusOctant
370             (
371                 const direction octant
372             )
373             {
374                 return labelBits(0, octant);
375             }
377 public:
379     // Static functions
381         //- Get the perturbation tolerance
382         static scalar& perturbTol();
385     // Constructors
387         //- Construct null
388         indexedOctree(const Type& shapes);
390         //- Construct from components
391         indexedOctree
392         (
393             const Type& shapes,
394             const List<node>& nodes,
395             const labelListList& contents
396         );
398         //- Construct from shapes
399         indexedOctree
400         (
401             const Type& 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
406                                             // average
407         );
409         //- Construct from Istream
410         indexedOctree(const Type& shapes, Istream& is);
412         //- Clone
413         autoPtr<indexedOctree<Type> > clone() const
414         {
415             return autoPtr<indexedOctree<Type> >
416             (
417                 new indexedOctree<Type>(*this)
418             );
419         }
421     // Member Functions
423         // Access
425             //- Reference to shape
426             const Type& shapes() const
427             {
428                 return shapes_;
429             }
431             //- List of all nodes
432             const List<node>& nodes() const
433             {
434                 return nodes_;
435             }
437             //- List of all contents (referenced by those nodes that are
438             //  contents)
439             const labelListList& contents() const
440             {
441                 return contents_;
442             }
444             //- Top bounding box
445             const treeBoundBox& bb() const
446             {
447                 if (nodes_.empty())
448                 {
449                     FatalErrorIn("indexedOctree<Type>::bb() const")
450                         << "Tree is empty" << abort(FatalError);
451                 }
452                 return nodes_[0].bb_;
453             }
456         // Conversions for entries in subNodes_.
458             static bool isContent(const labelBits i)
459             {
460                 return i.val() < 0;
461             }
463             static bool isEmpty(const labelBits i)
464             {
465                 return i.val() == 0;
466             }
468             static bool isNode(const labelBits i)
469             {
470                 return i.val() > 0;
471             }
473             static label getContent(const labelBits i)
474             {
475                 if (!isContent(i))
476                 {
477                     FatalErrorIn("getContent(const label)")
478                         << abort(FatalError);
479                 }
480                 return -i.val()-1;
481             }
483             static label getNode(const labelBits i)
484             {
485                 if (!isNode(i))
486                 {
487                     FatalErrorIn("getNode(const label)")
488                         << abort(FatalError);
489                 }
490                 return i.val() - 1;
491             }
493             static direction getOctant(const labelBits i)
494             {
495                 return i.bits();
496             }
499         // Queries
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
506             (
507                 const point& sample,
508                 const scalar nearestDistSqr
509             ) const;
511             //- Low level: calculate nearest starting from subnode.
512             void findNearest
513             (
514                 const label nodeI,
515                 const point&,
517                 scalar& nearestDistSqr,
518                 label& nearestShapeI,
519                 point& nearestPoint
520             ) const;
522             //- Find nearest to line. Returns
523             //  - bool : any point found?
524             //  - label: index in shapes
525             //  - point: actual nearest point found
526             //  sets:
527             //  - linePoint : corresponding nearest point on line
528             pointIndexHit findNearest
529             (
530                 const linePointRef& ln,
531                 treeBoundBox& tightest,
532                 point& linePoint
533             ) const;
535             //- Find nearest intersection of line between start and end.
536             pointIndexHit findLine
537             (
538                 const point& start,
539                 const point& end
540             ) const;
542             //- Find any intersection of line between start and end.
543             pointIndexHit findLineAny
544             (
545                 const point& start,
546                 const point& end
547             ) const;
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
565             (
566                 const vector& outsideNormal,
567                 const vector& vec
568             );
570             //- Helper: does bb intersect a sphere around sample? Or is any
571             //  corner point of bb closer than nearestDistSqr to sample.
572             static bool overlaps
573             (
574                 const point& bbMin,
575                 const point& bbMax,
576                 const scalar nearestDistSqr,
577                 const point& sample
578             );
581         // Write
583             //- Print tree. Either print all indices (printContent = true) or
584             //  just size of contents nodes.
585             void print
586             (
587                 prefixOSstream&,
588                 const bool printContents,
589                 const label
590             ) const;
592             bool write(Ostream& os) const;
594     // IOstream Operators
596         friend Ostream& operator<< <Type>(Ostream&, const indexedOctree<Type>&);
601 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
603 } // End namespace Foam
605 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
607 #ifdef NoRepository
608 #   include "indexedOctree.C"
609 #endif
611 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
613 #endif
615 // ************************************************************************* //