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
octree
octree.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::octree
26
27
Description
28
Octree, templated on type of shapes it refers to.
29
30
Uses the octreeData class, which is a list of 1D, 2D or 3D shapes.
31
Various implementations of octreeData which know about cell&meshes,
32
patches&meshes and points.
33
34
The octree can be used to
35
- find the "nearest" shape to a point
36
- find the shape which contains a point (only sensible for 3D shapes)
37
- find intersections of line with shapes
38
39
The tree consists of
40
- treeNode : holds sub-treeNodes or treeLeaves
41
- treeLeaf : is the one that actually holds data
42
43
The data is stored purely as a list of indices into octreeData.
44
45
The construction on the depth of the tree is:
46
- one can specify a minimum depth
47
(though the tree will never be refined if all leaves contain <=1
48
shapes)
49
- after the minimum depth two statistics are used to decide further
50
refinement:
51
- average number of entries per leaf (leafRatio). Since inside a
52
leaf most algorithms are n or n^2 this value has to be small.
53
- average number of leaves a shape is in. Because of bounding boxes,
54
a single shape can be in multiple leaves. If the bbs are large
55
compared to the leaf size this multiplicity can become extremely
56
large and will become larger with more levels.
57
58
Note: the octree gets constructed with an overall bounding box. If your
59
mesh is regular it is a good idea to make this overall bb a bit wider than
60
the bb of the shapes itself. Otherwise lots of shapes end up exactly on the
61
edge of a bb and hence go into more than one subcube.
62
63
E.g. octree of face centres of lid driven cavity.
64
65
-# bb exact -> total 1457 leaves (every point in 7.1 leaves)
66
-# bb.max incremented by 1% -> total 80 leaves
67
(every point in exactly 1 leaf)
68
69
@par Ideas for parallel implementation:
70
71
The data inserted into the octree (the
72
'octreeData') has to be local to the processor. The data to be looked
73
for (usually a sample point) can be global to the domain.
74
The algorithm:
75
- search for all my points
76
- collect results which have to do with a processor patch
77
- global sum all these. If 0 exit.
78
- exchange data on all processor patches
79
- start again
80
81
So data transfers one processor per iteration. One could think of having
82
an extra search mechanism one level above which does an initial search
83
knowing the average shape of a processor distribution (square/cube for
84
most decomposition methods) and can assign sample points to the (almost)
85
correct processor at once.
86
87
SourceFiles
88
octree.C
89
90
\*---------------------------------------------------------------------------*/
91
92
#ifndef octree_H
93
#define octree_H
94
95
#include "
treeBoundBoxList.H
"
96
#include "
treeLeaf.H
"
97
#include "
pointIndexHit.H
"
98
#include <
OpenFOAM/linePointRef.H
>
99
100
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
101
102
namespace
Foam
103
{
104
105
// Forward declaration of classes
106
template
<
class
Type>
class
treeNode;
107
108
// Forward declaration of friend functions and operators
109
110
template
<
class
Type>
111
Ostream& operator<<(Ostream&, const octree<Type>&);
112
113
114
/*---------------------------------------------------------------------------*\
115
Class octreeName Declaration
116
\*---------------------------------------------------------------------------*/
117
118
TemplateName
(octree);
119
120
121
122
/*---------------------------------------------------------------------------*\
123
Class octree Declaration
124
\*---------------------------------------------------------------------------*/
125
126
template
<
class
Type>
127
class
octree
128
:
129
public
octreeName
130
{
131
// Private data
132
133
//- Top treeNode. Modified by lower levels.
134
treeNode<Type>
* topNode_;
135
136
//- all shapes
137
const
Type shapes_;
138
139
//- Overall bb of octree
140
const
treeBoundBox
octreeBb_;
141
142
//- Refinement crit: size of leaves. Average number of entries per
143
// leaf. Should be fine enough for efficient searching at lowest level.
144
const
scalar maxLeafRatio_;
145
146
//- Refinement crit: multiplicity of entries (so in how many leaves
147
// each shape is mentioned)
148
const
scalar maxShapeRatio_;
149
150
//- Refinement crit: min no. of levels
151
const
label minNLevels_;
152
153
//- Actual depth
154
label deepestLevel_;
155
156
//- Total number of (references to) shapes in octree
157
// (shapes can be stored in more than one treeLeaf)
158
label nEntries_;
159
160
//- Total number of treeNodes
161
label nNodes_;
162
163
//- Total number of treeLeaves
164
label nLeaves_;
165
166
167
// Static data members
168
//- Refinement crit: max number of level
169
static
const
label maxNLevels = 20;
170
171
172
173
// Private Member Functions
174
175
public
:
176
177
// Data types
178
179
//- volume types
180
enum
volumeType
181
{
182
UNKNOWN
,
183
MIXED
,
184
INSIDE
,
185
OUTSIDE
186
};
187
188
189
// Static data members
190
191
//- for debugging:return printable representation of volumeType
192
static
string
volType
(
const
label);
193
194
//- Code the vector with respect to the geometry. geomNormal guaranteed
195
// to point outside.
196
static
label
getVolType
197
(
198
const
vector
& geomNormal,
199
const
vector
& vec
200
);
201
202
// Constructors
203
204
//- Construct from components
205
octree
206
(
207
const
treeBoundBox
&
octreeBb
,
208
const
Type&
shapes
,
209
const
label
minNLevels
,
// minimum number of levels
210
const
scalar
maxLeafRatio
,
// max avg. size of leaves
211
const
scalar
maxShapeRatio
// max avg. duplicity.
212
);
213
214
215
// Destructor
216
217
~octree
();
218
219
220
// Member Functions
221
222
// Access
223
224
const
Type&
shapes
()
const
225
{
226
return
shapes_;
227
}
228
229
const
treeBoundBox
&
octreeBb
()
const
230
{
231
return
octreeBb_;
232
}
233
234
scalar
maxShapeRatio
()
const
235
{
236
return
maxShapeRatio_;
237
}
238
239
scalar
maxLeafRatio
()
const
240
{
241
return
maxLeafRatio_;
242
}
243
244
label
minNLevels
()
const
245
{
246
return
minNLevels_;
247
}
248
249
// After construction: octree statistics
250
251
treeNode<Type>
*
topNode
()
const
252
{
253
return
topNode_;
254
}
255
256
label
deepestLevel
()
const
257
{
258
return
deepestLevel_;
259
}
260
261
label
nEntries
()
const
262
{
263
return
nEntries_;
264
}
265
266
label
nNodes
()
const
267
{
268
return
nNodes_;
269
}
270
271
label
nLeaves
()
const
272
{
273
return
nLeaves_;
274
}
275
276
void
setEntries
(
const
label n)
277
{
278
nEntries_ = n;
279
}
280
281
void
setNodes
(
const
label n)
282
{
283
nNodes_ = n;
284
}
285
286
void
setLeaves
(
const
label n)
287
{
288
nLeaves_ = n;
289
}
290
291
// Queries
292
293
//- Returns type of sample with respect to nearest shape.
294
// Meaning of type is determined by shapes.getSampleType().
295
// Normally based on outwards pointing normal. For e.g.
296
// octreeDataFace returns one of
297
// inside : on other side of normal on nearest face
298
// outside : on same side as normal on nearest face
299
// unknown : not above nearest face; surface probably not
300
// closed.
301
// mixed : should never happen
302
label
getSampleType
(
const
point
& sample)
const
;
303
304
//- Find shape containing point in tree
305
// Returns -1 if not in found. Uses Type::contains.
306
label
find
(
const
point
& sample)
const
;
307
308
//- Calculate tightest fitting bounding box. Uses
309
// Type::findTightest.
310
bool
findTightest
311
(
312
const
point
& sample,
313
treeBoundBox
& tightest
314
)
const
;
315
316
//- Find nearest shape. Returns index of shape or -1 if not found.
317
// tightestDist is both input and output. Uses Type::calcNearest.
318
label
findNearest
319
(
320
const
point
& sample,
321
treeBoundBox
& tightest,
322
scalar& tightestDist
323
)
const
;
324
325
//- Find nearest to line. Returns -1 or index of shape and
326
// sets:
327
// - tightest (is both input and output).
328
// - linePoint : point on line (-GREAT,-GREAT,-GREAT if not found)
329
// - shapePoint : point on shape (GREAT, GREAT, GREAT if not found)
330
// Uses Type::calcNearest.
331
label
findNearest
332
(
333
const
linePointRef
&
ln
,
334
treeBoundBox
& tightest,
335
point
& linePoint,
336
point
& shapePoint
337
)
const
;
338
339
//- Find (in no particular order) indices of all shapes inside or
340
// overlapping bounding box (i.e. all shapes not outside box)
341
labelList
findBox
(
const
boundBox
& bb)
const
;
342
343
//- Find intersected shape along line. pointIndexHit contains index
344
// of nearest shape intersected and the intersection point. Uses
345
// findLeafLine.
346
pointIndexHit
findLine
(
const
point
& start,
const
point
&
end
)
const
;
347
348
//- Like above but just tests whether line hits anything. So
349
// returns first intersection found, not nessecarily nearest.
350
pointIndexHit
findLineAny
(
const
point
& start,
const
point
&
end
)
351
const
;
352
353
//- Find leaf along line. Set leafIntPoint to leave point of
354
// treeLeaf.
355
const
treeLeaf<Type>
*
findLeafLine
356
(
357
const
point
& start,
358
const
point
&
end
,
359
point
& leafIntPoint
360
)
const
;
361
362
363
// Write
364
365
//- Dump graphical representation in .obj format
366
void
writeOBJ
(
Ostream
& os, label& vertNo)
const
;
367
368
//- Print some stats on octree
369
void
printStats
(
Ostream
& os)
const
;
370
371
372
// STL iterator
373
374
class
iterator
;
375
friend
class
iterator
;
376
377
//- An STL iterator for octree
378
class
iterator
379
{
380
// Private data
381
382
//- Reference to the octree this is an iterator for
383
octree
& octree_;
384
385
//- List of pointers to treeLeaves
386
List<treeLeaf<Type>
*> leaves_;
387
388
//- Current treeLeaf index
389
label curLeaf_;
390
391
public
:
392
393
//- Construct for a given octree
394
iterator
(
octree
&);
395
396
//- Contruct for a given octree, at a certain position
397
iterator
(
octree
& oc,
const
label index);
398
399
400
// Member operators
401
402
void
operator=
(
const
iterator
&);
403
404
bool
operator==
(
const
iterator
&)
const
;
405
bool
operator!=
(
const
iterator
&)
const
;
406
407
treeLeaf<Type>
&
operator*
();
408
409
iterator
&
operator++
();
410
iterator
operator++
(
int
);
411
};
412
413
//- iterator set to the begining of the octree
414
iterator
begin
();
415
416
//- iterator set to beyond the end of the octree
417
const
iterator
&
end
();
418
419
420
// STL const_iterator
421
422
class
const_iterator
;
423
friend
class
const_iterator
;
424
425
//- An STL const_iterator for octree
426
class
const_iterator
427
{
428
// Private data
429
430
//- Reference to the list this is an iterator for
431
const
octree
& octree_;
432
433
//- List of treeLeafs
434
List<const treeLeaf<Type>
*> leaves_;
435
436
//- Current treeLeaf index
437
label curLeaf_;
438
439
public
:
440
441
//- Construct for a given octree
442
const_iterator
(
const
octree
&);
443
444
//- Construct for a given octree and index
445
const_iterator
(
const
octree
&, label);
446
447
// Member operators
448
449
void
operator=
(
const
const_iterator
&);
450
451
bool
operator==
(
const
const_iterator
&)
const
;
452
bool
operator!=
(
const
const_iterator
&)
const
;
453
454
const
treeLeaf<Type>
&
operator*
();
455
456
const_iterator
&
operator++
();
457
const_iterator
operator++
(
int
);
458
};
459
460
461
//- const_iterator set to the begining of the octree
462
inline
const_iterator
begin
()
const
;
463
inline
const_iterator
cbegin
()
const
;
464
465
//- const_iterator set to beyond the end of the octree
466
inline
const
const_iterator
&
end
()
const
;
467
inline
const
const_iterator
&
cend
()
const
;
468
469
470
// IOstream Operators
471
472
friend
Ostream
& operator<< <Type>(
Ostream
&,
const
octree<Type>
&);
473
474
475
private
:
476
477
//- iterator returned by end()
478
iterator
endIter_;
479
480
//- const_iterator returned by end()
481
const_iterator
endConstIter_;
482
};
483
484
485
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
486
487
}
// End namespace Foam
488
489
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
490
491
#ifdef NoRepository
492
# include "
octree.C
"
493
#endif
494
495
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
496
497
#endif
498
499
// ************************ vim: set sw=4 sts=4 et: ************************ //