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