Developer Documentation

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
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>
74 typename BSPImplT<BSPCore>::NearestNeighbor
75 BSPImplT<BSPCore>::
76 nearest(const Point& _p) const
77 {
78 NearestNeighborData data;
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
93 BSPImplT<BSPCore>::
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>
133 typename BSPImplT<BSPCore>::RayCollision
134 BSPImplT<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>
150 typename BSPImplT<BSPCore>::RayCollision
151 BSPImplT<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>
168 typename BSPImplT<BSPCore>::RayCollision
169 BSPImplT<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
188 BSPImplT<BSPCore>::
189 _raycollision_non_directional(Node* _node, RayCollisionData& _data) const
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
226 BSPImplT<BSPCore>::
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
265 BSPImplT<BSPCore>::
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 //=============================================================================
BSPImplT::RayCollision
std::vector< std::pair< Handle, Scalar > > RayCollision
Store nearest neighbor information.
Definition: BSPImplT.hh:105
BSPImplT::less_pair_second
Definition: BSPImplT.hh:194
BSPImplT
Definition: BSPImplT.hh:74
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:1317
BSPImplT::raycollision
RayCollision raycollision(const Point &_p, const Point &_r) const
intersect mesh with ray
Definition: BSPImplT.cc:135
BSPImplT::_raycollision_directional
void _raycollision_directional(Node *_node, RayCollisionData &_data) const
recursive part of directionalRaycollision()
Definition: BSPImplT.cc:227
BSPImplT::_raycollision_non_directional
void _raycollision_non_directional(Node *_node, RayCollisionData &_data) const
recursive part of raycollision()
Definition: BSPImplT.cc:189
ACG::NumLimitsT::max
static Scalar max()
Return the maximum absolte value a scalar type can store.
Definition: NumLimitsT.hh:104
BSPImplT::directionalRaycollision
RayCollision directionalRaycollision(const Point &_p, const Point &_r) const
intersect mesh with ray
Definition: BSPImplT.cc:152
BSPImplT::nearestRaycollision
RayCollision nearestRaycollision(const Point &_p, const Point &_r) const
intersect mesh with ray
Definition: BSPImplT.cc:170
BSPImplT::RayCollisionData
Store ray collide information.
Definition: BSPImplT.hh:166
BSPImplT::nearest
NearestNeighbor nearest(const Point &_p) const
Return handle of the nearest neighbor face.
Definition: BSPImplT.cc:76
BSPImplT::NearestNeighborData
Store nearest neighbor information.
Definition: BSPImplT.hh:153
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:1367
BSPImplT::NearestNeighbor
Store nearest neighbor information.
Definition: BSPImplT.hh:96