Home
Downloads
Documentation
Installation
User Guide
man-pages
API Documentation
README
Release Notes
Changes
License
Support
SourceForge Project
Main Page
Related Pages
Namespaces
Classes
Files
File List
File Members
All
Classes
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Friends
Macros
Pages
src
meshTools
indexedOctree
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
>
39
#include <
meshTools/pointIndexHit.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>
69
class
indexedOctree
70
:
71
public
indexedOctreeName
72
{
73
public
:
74
75
// Data types
76
77
//- volume types
78
enum
volumeType
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
94
treeBoundBox
bb_
;
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
100
FixedList<labelBits, 8>
subNodes_
;
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
,
182
DynamicList<labelList>
&
contents
,
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,
190
DynamicList<node>
&
nodes
,
191
DynamicList<labelList>
&
contents
192
)
const
;
193
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
);
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
389
indexedOctree
390
(
391
const
Type&
shapes
,
392
const
List<node>&
nodes
,
393
const
labelListList
&
contents
394
);
395
396
//- Construct from shapes
397
indexedOctree
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
411
autoPtr<indexedOctree<Type>
>
clone
()
const
412
{
413
return
autoPtr<indexedOctree<Type>
>
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.
541
pointIndexHit
findLineAny
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
(
585
prefixOSstream
&,
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: ************************ //