Developer Documentation
BSPImplT.cc
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 * $Revision: 10745 $ *
45 * $LastChangedBy: moebius $ *
46 * $Date: 2011-01-26 10:23:50 +0100 (Wed, 26 Jan 2011) $ *
47 * *
48 \*===========================================================================*/
49 
50 
51 
52 
53 //=============================================================================
54 //
55 // CLASS BSPImplT
56 //
57 //=============================================================================
58 
59 #define BSPIMPLT_C
60 
61 //== INCLUDES =================================================================
62 
63 
64 #include "BSPImplT.hh"
65 #include <cfloat>
66 
67 
68 //== CLASS DEFINITION =========================================================
69 #include <vector>
70 #include <stdexcept>
71 #include <limits>
72 
73 template <class BSPCore>
76 nearest(const Point& _p) const
77 {
79  data.ref = _p;
80  data.dist = infinity_;
81  if (this->root_ == 0)
82  throw std::runtime_error("It seems like the BSP hasn't been built, yet. Did you call build(...)?");
83  _nearest(this->root_, data);
84  return NearestNeighbor(data.nearest, sqrt(data.dist));
85 }
86 
87 
88 //-----------------------------------------------------------------------------
89 
90 
91 template <class BSPCore>
92 void
94 _nearest(Node* _node, NearestNeighborData& _data) const
95 {
96  // terminal node
97  if (!_node->left_child_)
98  {
99  Scalar dist(0);
100  for (HandleIter it=_node->begin(); it!=_node->end(); ++it)
101  {
102  dist = this->traits_.sqrdist(*it, _data.ref);
103  if (dist < _data.dist)
104  {
105  _data.dist = dist;
106  _data.nearest = *it;
107  }
108  }
109  }
110 
111  // non-terminal node
112  else
113  {
114  Scalar dist = _node->plane_.distance(_data.ref);
115  if (dist > 0.0)
116  {
117  _nearest(_node->left_child_, _data);
118  if (dist*dist < _data.dist)
119  _nearest(_node->right_child_, _data);
120  }
121  else
122  {
123  _nearest(_node->right_child_, _data);
124  if (dist*dist < _data.dist)
125  _nearest(_node->left_child_, _data);
126  }
127  }
128 }
129 
130 //-----------------------------------------------------------------------------
131 
132 template <class BSPCore>
135 raycollision(const Point& _p, const Point& _r) const
136 {
137  // Prepare the struct for returning the data
138  RayCollisionData data;
139  data.ref = _p;
140  data.ray = _r;
141  data.hit_handles.clear();
142 
143  _raycollision_non_directional(this->root_, data);
144 
145  std::sort(data.hit_handles.begin(), data.hit_handles.end(), less_pair_second<Handle,Scalar>());
146  return RayCollision(data.hit_handles);
147 }
148 
149 template <class BSPCore>
152 directionalRaycollision(const Point& _p, const Point& _r) const {
153 
154  // Prepare the struct for returning the data
155  RayCollisionData data;
156  data.ref = _p;
157  data.ray = _r;
158  data.hit_handles.clear();
159 
160  _raycollision_directional(this->root_, data);
161 
162  std::sort(data.hit_handles.begin(), data.hit_handles.end(), less_pair_second<Handle,Scalar>());
163  return RayCollision(data.hit_handles);
164 
165 }
166 
167 template <class BSPCore>
170 nearestRaycollision(const Point& _p, const Point& _r) const {
171 
172  // Prepare the struct for returning the data
173  RayCollisionData data;
174  data.ref = _p;
175  data.ray = _r;
176  data.hit_handles.clear();
177 
178  _raycollision_nearest_directional(this->root_, data);
179 
180  return RayCollision(data.hit_handles);
181 }
182 
183 //-----------------------------------------------------------------------------
184 
185 
186 template <class BSPCore>
187 void
190 {
191  // terminal node
192  if (!_node->left_child_)
193  {
194  Scalar dist;
195  Point v0, v1, v2;
196  Scalar u, v;
197 
198  for (HandleIter it=_node->begin(); it!=_node->end(); ++it)
199  {
200  this->traits_.points(*it, v0, v1, v2);
201  if (ACG::Geometry::triangleIntersection(_data.ref, _data.ray, v0, v1, v2, dist, u, v)) {
202  // face intersects with ray.
203  _data.hit_handles.push_back(std::pair<Handle,Scalar>(*it,dist));
204  }
205  }
206  }
207 
208  // non-terminal node
209  else
210  {
211  Scalar tmin, tmax;
212  if ( _node->left_child_ && ACG::Geometry::axisAlignedBBIntersection( _data.ref, _data.ray, _node->left_child_->bb_min, _node->left_child_->bb_max, tmin, tmax)) {
213  _raycollision_non_directional(_node->left_child_, _data);
214  }
215  if ( _node->right_child_ && ACG::Geometry::axisAlignedBBIntersection( _data.ref, _data.ray, _node->right_child_->bb_min, _node->right_child_->bb_max, tmin, tmax)) {
216  _raycollision_non_directional(_node->right_child_, _data);
217  }
218  }
219 }
220 
221 //-----------------------------------------------------------------------------
222 
223 
224 template <class BSPCore>
225 void
227 _raycollision_directional(Node* _node, RayCollisionData& _data) const
228 {
229  // terminal node
230  if (!_node->left_child_)
231  {
232  Scalar dist;
233  Point v0, v1, v2;
234  Scalar u, v;
235 
236  for (HandleIter it=_node->begin(); it!=_node->end(); ++it)
237  {
238  this->traits_.points(*it, v0, v1, v2);
239  if (ACG::Geometry::triangleIntersection(_data.ref, _data.ray, v0, v1, v2, dist, u, v)) {
240  if (dist > 0.0){
241  _data.hit_handles.push_back(std::pair<Handle,Scalar>(*it,dist));
242  }
243  }
244  }
245  }
246 
247  // non-terminal node
248  else
249  {
250  Scalar tmin, tmax;
251  if ( _node->left_child_ && ACG::Geometry::axisAlignedBBIntersection( _data.ref, _data.ray, _node->left_child_->bb_min, _node->left_child_->bb_max, tmin, tmax)) {
252  _raycollision_directional(_node->left_child_, _data);
253  }
254  if ( _node->right_child_ && ACG::Geometry::axisAlignedBBIntersection( _data.ref, _data.ray, _node->right_child_->bb_min, _node->right_child_->bb_max, tmin, tmax)) {
255  _raycollision_directional(_node->right_child_, _data);
256  }
257  }
258 }
259 
260 //-----------------------------------------------------------------------------
261 
262 
263 template <class BSPCore>
264 void
266 _raycollision_nearest_directional(Node* _node, RayCollisionData& _data) const
267 {
268  // terminal node
269  if (!_node->left_child_)
270  {
271  Scalar dist;
272  Point v0, v1, v2;
273  Scalar u, v;
274 
275  for (HandleIter it=_node->begin(); it!=_node->end(); ++it)
276  {
277  this->traits_.points(*it, v0, v1, v2);
278  if (ACG::Geometry::triangleIntersection(_data.ref, _data.ray, v0, v1, v2, dist, u, v)) {
279  if (dist > 0.0){
280  _data.hit_handles.push_back(std::pair<Handle,Scalar>(*it, dist));
281  }
282  }
283  }
284  // only return the closest hit
285  if(!_data.hit_handles.empty()) {
286  std::partial_sort(_data.hit_handles.begin(), _data.hit_handles.begin() + 1, _data.hit_handles.end(), less_pair_second<Handle, Scalar>());
287  _data.hit_handles.resize(1);
288  }
289  }
290 
291  // non-terminal node
292  else
293  {
294  // determine order of traversal
295  Node* first_node = _node->left_child_, *second_node = _node->right_child_;
296  if (!_node->plane_(_data.ref)) {
297  std::swap(first_node, second_node);
298  }
299 
300  Scalar tmin, tmax;
301  if ( first_node && ACG::Geometry::axisAlignedBBIntersection( _data.ref, _data.ray, first_node->bb_min, first_node->bb_max, tmin, tmax) ) {
302  _raycollision_nearest_directional(first_node, _data);
303  }
304  // if the second node is further away than the closeset hit skip it
305  Scalar dist = ACG::NumLimitsT<Scalar>::max();
306  if(!_data.hit_handles.empty()) {
307  dist = _data.hit_handles.front().second;
308  }
309  if ( second_node && ACG::Geometry::axisAlignedBBIntersection( _data.ref, _data.ray, second_node->bb_min, second_node->bb_max, tmin, tmax) && (tmin < dist) ) {
310  _raycollision_nearest_directional(second_node, _data);
311  }
312  }
313 }
314 
315 
316 //=============================================================================
static Scalar max()
Return the maximum absolte value a scalar type can store.
Definition: NumLimitsT.hh:104
RayCollision directionalRaycollision(const Point &_p, const Point &_r) const
intersect mesh with ray
Definition: BSPImplT.cc:152
std::vector< std::pair< Handle, Scalar > > RayCollision
Store nearest neighbor information.
Definition: BSPImplT.hh:105
RayCollision nearestRaycollision(const Point &_p, const Point &_r) const
intersect mesh with ray
Definition: BSPImplT.cc:170
void _raycollision_non_directional(Node *_node, RayCollisionData &_data) const
recursive part of raycollision()
Definition: BSPImplT.cc:189
void _raycollision_directional(Node *_node, RayCollisionData &_data) const
recursive part of directionalRaycollision()
Definition: BSPImplT.cc:227
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:1317
Store ray collide information.
Definition: BSPImplT.hh:166
Store nearest neighbor information.
Definition: BSPImplT.hh:96
NearestNeighbor nearest(const Point &_p) const
Return handle of the nearest neighbor face.
Definition: BSPImplT.cc:76
RayCollision raycollision(const Point &_p, const Point &_r) const
intersect mesh with ray
Definition: BSPImplT.cc:135
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:1367
Store nearest neighbor information.
Definition: BSPImplT.hh:153