1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
|
// Copyright (c) 2008 INRIA Sophia-Antipolis (France), ETH Zurich (Switzerland).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.6-branch/AABB_tree/include/CGAL/AABB_node.h $
// $Id: AABB_node.h 51129 2009-08-07 18:57:08Z palliez $
//
//
// Author(s) : Camille Wormser, Pierre Alliez, Stephane Tayeb
#ifndef CGAL_AABB_NODE_H
#define CGAL_AABB_NODE_H
#include <CGAL/Profile_counter.h>
#include <CGAL/Cartesian_converter.h>
#include <CGAL/intersections.h>
#include <CGAL/Bbox_3.h>
#include <vector>
namespace CGAL {
/**
* @class AABB_node
*
*
*/
template<typename AABBTraits>
class AABB_node
{
public:
typedef typename AABBTraits::Bounding_box Bounding_box;
/// Constructor
AABB_node()
: m_bbox()
, m_p_left_child(NULL)
, m_p_right_child(NULL) { };
/// Non virtual Destructor
/// Do not delete children because the tree hosts and delete them
~AABB_node() { };
/// Returns the bounding box of the node
Bounding_box bbox() const { return m_bbox; }
/**
* @brief Builds the tree by recursive expansion.
* @param first the first primitive to insert
* @param last the last primitive to insert
* @param range the number of primitive of the range
*
* [first,last[ is the range of primitives to be added to the tree.
*/
template<typename ConstPrimitiveIterator>
void expand(ConstPrimitiveIterator first,
ConstPrimitiveIterator beyond,
const int range);
/**
* @brief General traversal query
* @param query the query
* @param traits the traversal traits that define the traversal behaviour
* @param nb_primitives the number of primitive
*
* General traversal query. The traits class allows using it for the various
* traversal methods we need: listing, counting, detecting intersections,
* drawing the boxes.
*/
template<class Traversal_traits, class Query>
void traversal(const Query& query,
Traversal_traits& traits,
const int nb_primitives) const;
private:
typedef AABBTraits AABB_traits;
typedef AABB_node<AABB_traits> Node;
typedef typename AABB_traits::Primitive Primitive;
/// Helper functions
const Node& left_child() const
{ return *static_cast<Node*>(m_p_left_child); }
const Node& right_child() const
{ return *static_cast<Node*>(m_p_right_child); }
const Primitive& left_data() const
{ return *static_cast<Primitive*>(m_p_left_child); }
const Primitive& right_data() const
{ return *static_cast<Primitive*>(m_p_right_child); }
Node& left_child() { return *static_cast<Node*>(m_p_left_child); }
Node& right_child() { return *static_cast<Node*>(m_p_right_child); }
Primitive& left_data() { return *static_cast<Primitive*>(m_p_left_child); }
Primitive& right_data() { return *static_cast<Primitive*>(m_p_right_child); }
private:
/// node bounding box
Bounding_box m_bbox;
/// children nodes, either pointing towards children (if children are not leaves),
/// or pointing toward input primitives (if children are leaves).
void *m_p_left_child;
void *m_p_right_child;
private:
// Disabled copy constructor & assignment operator
typedef AABB_node<AABBTraits> Self;
AABB_node(const Self& src);
Self& operator=(const Self& src);
}; // end class AABB_node
template<typename Tr>
template<typename ConstPrimitiveIterator>
void
AABB_node<Tr>::expand(ConstPrimitiveIterator first,
ConstPrimitiveIterator beyond,
const int range)
{
m_bbox = AABB_traits().compute_bbox_object()(first, beyond);
// sort primitives along longest axis aabb
AABB_traits().sort_primitives_object()(first, beyond, m_bbox);
switch(range)
{
case 2:
m_p_left_child = &(*first);
m_p_right_child = &(*(++first));
break;
case 3:
m_p_left_child = &(*first);
m_p_right_child = static_cast<Node*>(this)+1;
right_child().expand(first+1, beyond, 2);
break;
default:
const int new_range = range/2;
m_p_left_child = static_cast<Node*>(this) + 1;
m_p_right_child = static_cast<Node*>(this) + new_range;
left_child().expand(first, first + new_range, new_range);
right_child().expand(first + new_range, beyond, range - new_range);
}
}
template<typename Tr>
template<class Traversal_traits, class Query>
void
AABB_node<Tr>::traversal(const Query& query,
Traversal_traits& traits,
const int nb_primitives) const
{
// Recursive traversal
switch(nb_primitives)
{
case 2:
traits.intersection(query, left_data());
if( traits.go_further() )
{
traits.intersection(query, right_data());
}
break;
case 3:
traits.intersection(query, left_data());
if( traits.go_further() && traits.do_intersect(query, right_child()) )
{
right_child().traversal(query, traits, 2);
}
break;
default:
if( traits.do_intersect(query, left_child()) )
{
left_child().traversal(query, traits, nb_primitives/2);
if( traits.go_further() && traits.do_intersect(query, right_child()) )
{
right_child().traversal(query, traits, nb_primitives-nb_primitives/2);
}
}
else if( traits.do_intersect(query, right_child()) )
{
right_child().traversal(query, traits, nb_primitives-nb_primitives/2);
}
}
}
} // end namespace CGAL
#endif // CGAL_AABB_NODE_H
|
