Developer Documentation

BSPImplT_impl.hh
1 /*===========================================================================*\
2 * *
3 * OpenFlipper *
4 * Copyright (c) 2001-2015, RWTH-Aachen University *
5 * Department of Computer Graphics and Multimedia *
6 * All rights reserved. *
7 * www.openflipper.org *
8 * *
9 *---------------------------------------------------------------------------*
10 * This file is part of OpenFlipper. *
11 *---------------------------------------------------------------------------*
12 * *
13 * Redistribution and use in source and binary forms, with or without *
14 * modification, are permitted provided that the following conditions *
15 * are met: *
16 * *
17 * 1. Redistributions of source code must retain the above copyright notice, *
18 * this list of conditions and the following disclaimer. *
19 * *
20 * 2. Redistributions in binary form must reproduce the above copyright *
21 * notice, this list of conditions and the following disclaimer in the *
22 * documentation and/or other materials provided with the distribution. *
23 * *
24 * 3. Neither the name of the copyright holder nor the names of its *
25 * contributors may be used to endorse or promote products derived from *
26 * this software without specific prior written permission. *
27 * *
28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *
29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
30 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
31 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
32 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, *
33 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, *
34 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR *
35 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF *
36 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING *
37 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS *
38 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
39 * *
40 \*===========================================================================*/
41
42
43
44
45 //=============================================================================
46 //
47 // CLASS BSPImplT
48 //
49 //=============================================================================
50
51 #define BSPIMPLT_C
52
53 //== INCLUDES =================================================================
54
55
56 #include "BSPImplT.hh"
57 #include <cfloat>
58 #include <cmath>
59
60 //== CLASS DEFINITION =========================================================
61 #include <vector>
62 #include <stdexcept>
63 #include <limits>
64
65 template <class BSPCore>
66 typename BSPImplT<BSPCore>::NearestNeighbor
67 BSPImplT<BSPCore>::
68 nearest(const Point& _p) const
69 {
70 NearestNeighborData data;
71 data.ref = _p;
72 data.dist = infinity_;
73 if (this->root_ == 0)
74 throw std::runtime_error("It seems like the BSP hasn't been built, yet. Did you call build(...)?");
75 _nearest(this->root_, data);
76 return NearestNeighbor(data.nearest, sqrt(data.dist));
77 }
78
79
80 //-----------------------------------------------------------------------------
81
82
83 template <class BSPCore>
84 void
85 BSPImplT<BSPCore>::
86 _nearest(Node* _node, NearestNeighborData& _data) const
87 {
88 // terminal node
89 if (!_node->left_child_)
90 {
91 Scalar dist(0);
92 for (HandleIter it=_node->begin(); it!=_node->end(); ++it)
93 {
94 dist = this->traits_.sqrdist(*it, _data.ref);
95 if (dist < _data.dist)
96 {
97 _data.dist = dist;
98 _data.nearest = *it;
99 }
100 }
101 }
102
103 // non-terminal node
104 else
105 {
106 Scalar dist = _node->plane_.distance(_data.ref);
107 if (dist > 0.0)
108 {
109 _nearest(_node->left_child_, _data);
110 if (dist*dist < _data.dist)
111 _nearest(_node->right_child_, _data);
112 }
113 else
114 {
115 _nearest(_node->right_child_, _data);
116 if (dist*dist < _data.dist)
117 _nearest(_node->left_child_, _data);
118 }
119 }
120 }
121
122 //-----------------------------------------------------------------------------
123
124 template <class BSPCore>
125 typename BSPImplT<BSPCore>::RayCollision
126 BSPImplT<BSPCore>::
127 raycollision(const Point& _p, const Point& _r) const
128 {
129 // Prepare the struct for returning the data
130 RayCollisionData data;
131 data.ref = _p;
132 data.ray = _r;
133 data.hit_handles.clear();
134
135 _raycollision_non_directional(this->root_, data);
136
137 std::sort(data.hit_handles.begin(), data.hit_handles.end(), less_pair_second<Handle,Scalar>());
138 return RayCollision(data.hit_handles);
139 }
140
141 template <class BSPCore>
142 typename BSPImplT<BSPCore>::RayCollision
143 BSPImplT<BSPCore>::
144 directionalRaycollision(const Point& _p, const Point& _r) const {
145
146 // Prepare the struct for returning the data
147 RayCollisionData data;
148 data.ref = _p;
149 data.ray = _r;
150 data.hit_handles.clear();
151
152 _raycollision_directional(this->root_, data);
153
154 std::sort(data.hit_handles.begin(), data.hit_handles.end(), less_pair_second<Handle,Scalar>());
155 return RayCollision(data.hit_handles);
156
157 }
158
159 template <class BSPCore>
160 typename BSPImplT<BSPCore>::RayCollision
161 BSPImplT<BSPCore>::
162 nearestRaycollision(const Point& _p, const Point& _r) const {
163
164 // Prepare the struct for returning the data
165 RayCollisionData data;
166 data.ref = _p;
167 data.ray = _r;
168 data.hit_handles.clear();
169
170 _raycollision_nearest_directional(this->root_, data);
171
172 return RayCollision(data.hit_handles);
173 }
174
175 template<class BSPCore>
176 template<class Callback>
177 void
178 BSPImplT<BSPCore>::
179 intersectBall(const Point &_c, Scalar _r, Callback _callback) const
180 {
181 _intersect_ball(*(this->root_), _c, _r, _callback);
182 }
183
184
185 //-----------------------------------------------------------------------------
186
187
188 template <class BSPCore>
189 void
190 BSPImplT<BSPCore>::
191 _raycollision_non_directional(Node* _node, RayCollisionData& _data) const
192 {
193 // terminal node
194 if (!_node->left_child_)
195 {
196 Scalar dist;
197 Point v0, v1, v2;
198 Scalar u, v;
199
200 for (HandleIter it=_node->begin(); it!=_node->end(); ++it)
201 {
202 this->traits_.points(*it, v0, v1, v2);
203 if (ACG::Geometry::triangleIntersection(_data.ref, _data.ray, v0, v1, v2, dist, u, v)) {
204 // face intersects with ray.
205 _data.hit_handles.push_back(std::pair<Handle,Scalar>(*it,dist));
206 }
207 }
208 }
209
210 // non-terminal node
211 else
212 {
213 Scalar tmin, tmax;
214 if ( _node->left_child_ && ACG::Geometry::axisAlignedBBIntersection( _data.ref, _data.ray, _node->left_child_->bb_min, _node->left_child_->bb_max, tmin, tmax)) {
215 _raycollision_non_directional(_node->left_child_, _data);
216 }
217 if ( _node->right_child_ && ACG::Geometry::axisAlignedBBIntersection( _data.ref, _data.ray, _node->right_child_->bb_min, _node->right_child_->bb_max, tmin, tmax)) {
218 _raycollision_non_directional(_node->right_child_, _data);
219 }
220 }
221 }
222
223 //-----------------------------------------------------------------------------
224
225
226 template <class BSPCore>
227 void
228 BSPImplT<BSPCore>::
229 _raycollision_directional(Node* _node, RayCollisionData& _data) const
230 {
231 // terminal node
232 if (!_node->left_child_)
233 {
234 Scalar dist;
235 Point v0, v1, v2;
236 Scalar u, v;
237
238 for (HandleIter it=_node->begin(); it!=_node->end(); ++it)
239 {
240 this->traits_.points(*it, v0, v1, v2);
241 if (ACG::Geometry::triangleIntersection(_data.ref, _data.ray, v0, v1, v2, dist, u, v)) {
242 if (dist > 0.0){
243 _data.hit_handles.push_back(std::pair<Handle,Scalar>(*it,dist));
244 }
245 }
246 }
247 }
248
249 // non-terminal node
250 else
251 {
252 Scalar tmin, tmax;
253 if ( _node->left_child_ && ACG::Geometry::axisAlignedBBIntersection( _data.ref, _data.ray, _node->left_child_->bb_min, _node->left_child_->bb_max, tmin, tmax)) {
254 _raycollision_directional(_node->left_child_, _data);
255 }
256 if ( _node->right_child_ && ACG::Geometry::axisAlignedBBIntersection( _data.ref, _data.ray, _node->right_child_->bb_min, _node->right_child_->bb_max, tmin, tmax)) {
257 _raycollision_directional(_node->right_child_, _data);
258 }
259 }
260 }
261
262 //-----------------------------------------------------------------------------
263
264
265 template <class BSPCore>
266 void
267 BSPImplT<BSPCore>::
268 _raycollision_nearest_directional(Node* _node, RayCollisionData& _data) const
269 {
270 // terminal node
271 if (!_node->left_child_)
272 {
273 Scalar dist;
274 Point v0, v1, v2;
275 Scalar u, v;
276
277 for (HandleIter it=_node->begin(); it!=_node->end(); ++it)
278 {
279 this->traits_.points(*it, v0, v1, v2);
280 if (ACG::Geometry::triangleIntersection(_data.ref, _data.ray, v0, v1, v2, dist, u, v)) {
281 if (dist > 0.0){
282 _data.hit_handles.push_back(std::pair<Handle,Scalar>(*it, dist));
283 }
284 }
285 }
286 // only return the closest hit
287 if(!_data.hit_handles.empty()) {
288 std::partial_sort(_data.hit_handles.begin(), _data.hit_handles.begin() + 1, _data.hit_handles.end(), less_pair_second<Handle, Scalar>());
289 _data.hit_handles.resize(1);
290 }
291 }
292
293 // non-terminal node
294 else
295 {
296 // determine order of traversal
297 Node* first_node = _node->left_child_, *second_node = _node->right_child_;
298 if (!_node->plane_(_data.ref)) {
299 std::swap(first_node, second_node);
300 }
301
302 Scalar tmin, tmax;
303 if ( first_node && ACG::Geometry::axisAlignedBBIntersection( _data.ref, _data.ray, first_node->bb_min, first_node->bb_max, tmin, tmax) ) {
304 _raycollision_nearest_directional(first_node, _data);
305 }
306 // if the second node is further away than the closeset hit skip it
307 Scalar dist = ACG::NumLimitsT<Scalar>::max();
308 if(!_data.hit_handles.empty()) {
309 dist = _data.hit_handles.front().second;
310 }
311 if ( second_node && ACG::Geometry::axisAlignedBBIntersection( _data.ref, _data.ray, second_node->bb_min, second_node->bb_max, tmin, tmax) && (tmin < dist) ) {
312 _raycollision_nearest_directional(second_node, _data);
313 }
314 }
315 }
316 template<class BSPCore>
317 template<class Callback>
318 void BSPImplT<BSPCore>::
319 _intersect_ball(const Node &_node,
320 const Point &_c,
321 Scalar _r,
322 Callback _callback) const
323 {
324 // terminal node
325 if (!_node.left_child_)
326 {
327 const double r_sqr = _r * _r;
328 for (const auto &fh: _node) {
329 const double dist = this->traits_.sqrdist(fh, _c);
330 if (dist < r_sqr) {
331 _callback(fh);
332 }
333 }
334 }
335 else // non-terminal node
336 {
337 const Scalar dist = _node.plane_.distance(_c);
338 const Node &left = *_node.left_child_;
339 const Node &right = *_node.right_child_;
340
341 if (dist > -_r){
342 _intersect_ball(left, _c, _r, _callback);
343 }
344 if (dist < _r) {
345 _intersect_ball(right, _c, _r, _callback);
346 }
347 }
348 }
349
350
351 //=============================================================================
352
ACG::NumLimitsT::max
static Scalar max()
Return the maximum absolte value a scalar type can store.
Definition: NumLimitsT.hh:98
BSPImplT::raycollision
RayCollision raycollision(const Point &_p, const Point &_r) const
intersect mesh with ray
Definition: BSPImplT_impl.hh:127
BSPImplT::nearest
NearestNeighbor nearest(const Point &_p) const
Return handle of the nearest neighbor face.
Definition: BSPImplT_impl.hh:68
BSPImplT::_raycollision_directional
void _raycollision_directional(Node *_node, RayCollisionData &_data) const
recursive part of directionalRaycollision()
Definition: BSPImplT_impl.hh:229
BSPImplT::nearestRaycollision
RayCollision nearestRaycollision(const Point &_p, const Point &_r) const
intersect mesh with ray
Definition: BSPImplT_impl.hh:162
BSPImplT::_raycollision_non_directional
void _raycollision_non_directional(Node *_node, RayCollisionData &_data) const
recursive part of raycollision()
Definition: BSPImplT_impl.hh:191
BSPImplT
Definition: BSPImplT.hh:64
ACG::Geometry::axisAlignedBBIntersection
bool axisAlignedBBIntersection(const Vec &_o, const Vec &_dir, const Vec &_bbmin, const Vec &_bbmax, typename Vec::value_type &tmin, typename Vec::value_type &tmax)
Intersect a ray and an axis aligned bounding box.
Definition: Algorithms.cc:1359
BSPImplT::RayCollision
std::vector< std::pair< Handle, Scalar > > RayCollision
Store nearest neighbor information.
Definition: BSPImplT.hh:95
ACG::Geometry::triangleIntersection
bool triangleIntersection(const Vec &_o, const Vec &_dir, const Vec &_v0, const Vec &_v1, const Vec &_v2, typename Vec::value_type &_t, typename Vec::value_type &_u, typename Vec::value_type &_v)
Intersect a ray and a triangle.
Definition: Algorithms.cc:1307
BSPImplT::directionalRaycollision
RayCollision directionalRaycollision(const Point &_p, const Point &_r) const
intersect mesh with ray
Definition: BSPImplT_impl.hh:144
BSPImplT::NearestNeighbor
Store nearest neighbor information.
Definition: BSPImplT.hh:86
BSPImplT::intersectBall
void intersectBall(const Point &_c, Scalar _r, Callback _callback) const
intersect mesh with open ball
Definition: BSPImplT_impl.hh:179