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
BSP_test.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 * BSP_test.cc
44 *
45 * Created on: 31.07.2012
46 * Author: moebius
47 */
48
49 #include <gtest/gtest.h>
50
51 #include <OpenMesh/Core/Mesh/TriMesh_ArrayKernelT.hh>
52 #include <ACG/Geometry/bsp/TriangleBSPT.hh>
53 #include <ACG/Geometry/Algorithms.hh>
54
55
56 struct CustomTraits : public OpenMesh::DefaultTraits {
57 };
58
59 typedef OpenMesh::TriMesh_ArrayKernelT<CustomTraits> Mesh;
60
61 typedef OpenMeshTriangleBSPT< Mesh > BSP;
62
63 class BSP_CUBE_BASE : public testing::Test {
64
65 protected:
66
67 // This function is called before each test is run
68 virtual void SetUp() {
69
70 mesh_.clear();
71
72 // Add some vertices
73 Mesh::VertexHandle vhandle[8];
74 vhandle[0] = mesh_.add_vertex(Mesh::Point(-1, -1, 1));
75 vhandle[1] = mesh_.add_vertex(Mesh::Point( 1, -1, 1));
76 vhandle[2] = mesh_.add_vertex(Mesh::Point( 1, 1, 1));
77 vhandle[3] = mesh_.add_vertex(Mesh::Point(-1, 1, 1));
78 vhandle[4] = mesh_.add_vertex(Mesh::Point(-1, -1, -1));
79 vhandle[5] = mesh_.add_vertex(Mesh::Point( 1, -1, -1));
80 vhandle[6] = mesh_.add_vertex(Mesh::Point( 1, 1, -1));
81 vhandle[7] = mesh_.add_vertex(Mesh::Point(-1, 1, -1));
82
83 // Add six faces to form a cube
84 std::vector<Mesh::VertexHandle> face_vhandles;
85
86 face_vhandles.clear();
87 face_vhandles.push_back(vhandle[0]);
88 face_vhandles.push_back(vhandle[1]);
89 face_vhandles.push_back(vhandle[3]);
90 mesh_.add_face(face_vhandles);
91
92 face_vhandles.clear();
93 face_vhandles.push_back(vhandle[1]);
94 face_vhandles.push_back(vhandle[2]);
95 face_vhandles.push_back(vhandle[3]);
96 mesh_.add_face(face_vhandles);
97
98 //=======================
99
100 face_vhandles.clear();
101 face_vhandles.push_back(vhandle[7]);
102 face_vhandles.push_back(vhandle[6]);
103 face_vhandles.push_back(vhandle[5]);
104 mesh_.add_face(face_vhandles);
105
106 face_vhandles.clear();
107 face_vhandles.push_back(vhandle[7]);
108 face_vhandles.push_back(vhandle[5]);
109 face_vhandles.push_back(vhandle[4]);
110 mesh_.add_face(face_vhandles);
111
112 //=======================
113
114 face_vhandles.clear();
115 face_vhandles.push_back(vhandle[1]);
116 face_vhandles.push_back(vhandle[0]);
117 face_vhandles.push_back(vhandle[4]);
118 mesh_.add_face(face_vhandles);
119
120 face_vhandles.clear();
121 face_vhandles.push_back(vhandle[1]);
122 face_vhandles.push_back(vhandle[4]);
123 face_vhandles.push_back(vhandle[5]);
124 mesh_.add_face(face_vhandles);
125
126 //=======================
127
128 face_vhandles.clear();
129 face_vhandles.push_back(vhandle[2]);
130 face_vhandles.push_back(vhandle[1]);
131 face_vhandles.push_back(vhandle[5]);
132 mesh_.add_face(face_vhandles);
133
134 face_vhandles.clear();
135 face_vhandles.push_back(vhandle[2]);
136 face_vhandles.push_back(vhandle[5]);
137 face_vhandles.push_back(vhandle[6]);
138 mesh_.add_face(face_vhandles);
139
140
141 //=======================
142
143 face_vhandles.clear();
144 face_vhandles.push_back(vhandle[3]);
145 face_vhandles.push_back(vhandle[2]);
146 face_vhandles.push_back(vhandle[6]);
147 mesh_.add_face(face_vhandles);
148
149 face_vhandles.clear();
150 face_vhandles.push_back(vhandle[3]);
151 face_vhandles.push_back(vhandle[6]);
152 face_vhandles.push_back(vhandle[7]);
153 mesh_.add_face(face_vhandles);
154
155 //=======================
156
157 face_vhandles.clear();
158 face_vhandles.push_back(vhandle[0]);
159 face_vhandles.push_back(vhandle[3]);
160 face_vhandles.push_back(vhandle[7]);
161 mesh_.add_face(face_vhandles);
162
163 face_vhandles.clear();
164 face_vhandles.push_back(vhandle[0]);
165 face_vhandles.push_back(vhandle[7]);
166 face_vhandles.push_back(vhandle[4]);
167 mesh_.add_face(face_vhandles);
168
169
170 // Test setup:
171 //
172 //
173 // 3 ======== 2
174 // / \ /
175 // / \ / |
176 // / \ / |
177 // / \ / |
178 // 0 ======== 1 |
179 // | / | |
180 // | / | 6 z
181 // | / | / | y
182 // | / | / | /
183 // | / | / | /
184 // | / |/ |/
185 // 4 ======== 5 -------> x
186 //
187
188
189 // x ======== x
190 // / \ /
191 // / \ 1 / |
192 // / 0 \ / |
193 // / \ / |
194 // x ======== x |
195 // | / | |
196 // | 4 / | x z
197 // | / | / | y
198 // | / 5 | / | /
199 // | / | / | /
200 // | / |/ |/
201 // x ======== x -------> x
202 //
203
204 // create Triangle BSP
205 bsp_ = new BSP( mesh_ );
206
207 // build Triangle BSP
208 bsp_->reserve(mesh_.n_faces());
209
210 Mesh::FIter f_it = mesh_.faces_begin();
211 Mesh::FIter f_end = mesh_.faces_end();
212
213 for (; f_it!=f_end; ++f_it)
214 bsp_->push_back(*f_it);
215
216 bsp_->build(10, 100); //max vertices per leaf 10, max depth 100
217
218 }
219
220 // This function is called after all tests are through
221 virtual void TearDown() {
222
223 // Do some final stuff with the member data here...
224 }
225
226 // This member will be accessible in all tests
227 Mesh mesh_;
228
229 //This will be the tree
230 BSP* bsp_;
231 };
232
233
234 /* Basic check if the test mesh is setup correctly
235 */
236 TEST_F(BSP_CUBE_BASE, CheckCubeConstruction) {
237
238 // Check setup of the mesh
239 EXPECT_EQ(8u, mesh_.n_vertices() ) << "Wrong number of vertices";
240 EXPECT_EQ(12u, mesh_.n_faces() ) << "Wrong number of faces";
241
242 }
243
244 /* Basic check if the bsp can be setup
245 */
246 TEST_F(BSP_CUBE_BASE, SetupBSPfromCube ) {
247
248 EXPECT_FALSE(bsp_->empty()) << "BSP should not be empty !";
249 EXPECT_EQ(12u, bsp_->size()) << "Wrong number of triangles in BSP after construction";
250
251 }
252
253 /* Nearest neighbor check
254 */
255 TEST_F(BSP_CUBE_BASE, NearestNeighbour_OnSurface_1 ) {
256
257 // (-1,1) (1,1)
258 // x ======== x
259 // | / | y = -1 plane
260 // | 4 / | z
261 // | / | |
262 // | / 5 | |
263 // | / | |
264 // | / | |
265 // x ======== x -------> x
266 // (-1,-1) (1,-1)
267
268
269 // Point close to face 5
270 // (-1,1) (1,1)
271 // x ======== x
272 // | / |
273 // | / |
274 // | / |
275 // | / p |
276 // | / |
277 // | / |
278 // x ======== x
279 // (-1,-1) (1,-1)
280 Mesh::Point p1(0.75,-1.0,0.0);
281 BSP::NearestNeighbor nn = bsp_->nearest(p1);
282
283 EXPECT_EQ(5, nn.handle.idx()) << "Wrong Handle on closest face";
284 }
285
286 TEST_F(BSP_CUBE_BASE, NearestNeighbour_OnSurface_2 ) {
287 // Point close to face 4
288 // (-1,1) (1,1)
289 // x ======== x
290 // | / |
291 // | / |
292 // | / |
293 // | p / |
294 // | / |
295 // | / |
296 // x ======== x
297 // (-1,-1) (1,-1)
298 Mesh::Point p1(-0.75,-1.0,0.0);
299 BSP::NearestNeighbor nn = bsp_->nearest(p1);
300 EXPECT_EQ(4, nn.handle.idx()) << "Wrong Handle on closest face";
301 }
302
303 TEST_F(BSP_CUBE_BASE, NearestNeighbour_OnSurface_3 ) {
304 // Point close to face 4
305 // (-1,1) (1,1)
306 // x ======== x
307 // | p / |
308 // | / |
309 // | / |
310 // | / |
311 // | / |
312 // | / |
313 // x ======== x
314 // (-1,-1) (1,-1)
315 Mesh::Point p1(-0.75,-1.0,0.75);
316 BSP::NearestNeighbor nn = bsp_->nearest(p1);
317 EXPECT_EQ(4, nn.handle.idx()) << "Wrong Handle on closest face";
318 }
319
320 TEST_F(BSP_CUBE_BASE, NearestNeighbour_OnSurface_4 ) {
321
322 // Point close to face 5
323 // (-1,1) (1,1)
324 // x ======== x
325 // | / |
326 // | / |
327 // | / |
328 // | / |
329 // | / |
330 // | / p |
331 // x ======== x
332 // (-1,-1) (1,-1)
333 Mesh::Point p1(0.75,-1.0,-0.75);
334 BSP::NearestNeighbor nn = bsp_->nearest(p1);
335 EXPECT_EQ(5, nn.handle.idx()) << "Wrong Handle on closest face";
336
337 }
338
339 TEST_F(BSP_CUBE_BASE, RayIntersectionAboveSurface_NonDirectionalFunction_1 ) {
340
341
342 // ==============================================
343 // Test some Rays
344 // ==============================================
345
346 // Shoot through face 4 in y direction
347 // Start point is not on face 4
348 // x ======== x
349 // / \ /
350 // / \ 1 / |
351 // / 0 \ / |
352 // / \ / |
353 // x ======== x |
354 // | / | |
355 // | 4 / | x z
356 // | / | / | y
357 // | p / 5 | / | /
358 // | / | / | /
359 // | / |/ |/
360 // x ======== x -------> x
361
362 Mesh::Point yDirection(0.0,1.0,0.0);
363 Mesh::Point p1(-0.5,-2.0,0.0);
364 BSP::RayCollision rc;
365 rc = bsp_->raycollision(p1,yDirection);
366
367 EXPECT_EQ(2u, rc.size() ) << "Wrong number of hit faces in ray collision test 1";
368 if ( rc.size() == 2u ) { // Don't crash on wrong size
369 EXPECT_EQ(4, rc[0].first.idx() ) << "Wrong handle of first face in ray collision test 1";
370 EXPECT_EQ(9, rc[1].first.idx() ) << "Wrong handle of second face in ray collision test 1";
371 }
372
373 }
374
375 TEST_F(BSP_CUBE_BASE, RayIntersectionAboveSurface_NonDirectionalFunction_NegativeDirection_1 ) {
376 // ==============================================
377 // Test some Rays
378 // ==============================================
379
380 // Shoot through face 4 in negative y direction
381 // Start point is not on face 4
382 // x ======== x
383 // / \ /
384 // / \ 1 / |
385 // / 0 \ / |
386 // / \ / |
387 // x ======== x |
388 // | / | |
389 // | 4 / | x z
390 // | / | / | y
391 // | p / 5 | / | /
392 // | / | / | /
393 // | / |/ |/
394 // x ======== x -------> x
395
396 Mesh::Point nyDirection(0.0,-1.0,0.0);
397 Mesh::Point p1(-0.5,-2.0,0.0);
398 BSP::RayCollision rc;
399 rc = bsp_->raycollision(p1,nyDirection);
400
401 EXPECT_EQ(2u, rc.size() ) << "Wrong number of hit faces in ray collision test 1";
402 if ( rc.size() == 2u ) { // Don't crash on wrong size
403 EXPECT_EQ(4, rc[0].first.idx() ) << "Wrong handle of first face in ray collision test 1";
404 EXPECT_EQ(9, rc[1].first.idx() ) << "Wrong handle of second face in ray collision test 1";
405 }
406 }
407
408 TEST_F(BSP_CUBE_BASE, RayIntersectionAboveSurface_NonDirectionalFunction_2 ) {
409 // Shoot through face 5 in y direction
410 // Start point is not on face 5
411 // x ======== x
412 // / \ /
413 // / \ 1 / |
414 // / 0 \ / |
415 // / \ / |
416 // x ======== x |
417 // | / | |
418 // | 4 / | x z
419 // | / | / | y
420 // | p / 5 | / | /
421 // | / | / | /
422 // | / |/ |/
423 // x ======== x -------> x
424
425 Mesh::Point yDirection(0.0,1.0,0.0);
426 Mesh::Point p1(0.5,-2.0,0.0);
427 BSP::RayCollision rc;
428 rc = bsp_->raycollision(p1,yDirection);
429
430 EXPECT_EQ(2u, rc.size() ) << "Wrong number of hit faces in ray collision test 2";
431 if ( rc.size() == 2u ) { // Don't crash on wrong size
432 EXPECT_EQ(5, rc[0].first.idx() ) << "Wrong handle of first face in ray collision test 2";
433 EXPECT_EQ(8, rc[1].first.idx() ) << "Wrong handle of second face in ray collision test 2";
434 }
435
436 }
437
438 TEST_F(BSP_CUBE_BASE, RayIntersectionAboveSurface_NonDirectionalFunction_NegativeDirection_2 ) {
439
440 // Shoot through face 5 in negative y direction
441 // Start point is not on face 5
442 // x ======== x
443 // / \ /
444 // / \ 1 / |
445 // / 0 \ / |
446 // / \ / |
447 // x ======== x |
448 // | / | |
449 // | 4 / | x z
450 // | / | / | y
451 // | p / 5 | / | /
452 // | / | / | /
453 // | / |/ |/
454 // x ======== x -------> x
455
456 Mesh::Point nyDirection(0.0,-1.0,0.0);
457 Mesh::Point p1(0.5,-2.0,0.0);
458 BSP::RayCollision rc;
459 rc = bsp_->raycollision(p1,nyDirection);
460
461 EXPECT_EQ(2u, rc.size() ) << "Wrong number of hit faces in ray collision test 2";
462 if ( rc.size() == 2u ) { // Don't crash on wrong size
463 EXPECT_EQ(5, rc[0].first.idx() ) << "Wrong handle of first face in ray collision test 2";
464 EXPECT_EQ(8, rc[1].first.idx() ) << "Wrong handle of second face in ray collision test 2";
465 }
466
467 }
468
469
470
471 TEST_F(BSP_CUBE_BASE, RayIntersectionAboveSurface_DirectionalFunction_1 ) {
472
473
474 // ==============================================
475 // Test some Rays
476 // ==============================================
477
478 // Shoot through face 4 in y direction
479 // Start point is not on face 4
480 // x ======== x
481 // / \ /
482 // / \ 1 / |
483 // / 0 \ / |
484 // / \ / |
485 // x ======== x |
486 // | / | |
487 // | 4 / | x z
488 // | / | / | y
489 // | p / 5 | / | /
490 // | / | / | /
491 // | / |/ |/
492 // x ======== x -------> x
493
494 Mesh::Point yDirection(0.0,1.0,0.0);
495 Mesh::Point origin(-0.5,-2.0,0.0);
496 BSP::RayCollision rc;
497 rc = bsp_->directionalRaycollision(origin,yDirection);
498
499 EXPECT_EQ(2u, rc.size() ) << "Wrong number of hit faces in ray collision test 1";
500 if ( rc.size() == 2u ) { // Don't crash on wrong size
501 EXPECT_EQ(4, rc[0].first.idx() ) << "Wrong handle of first face in ray collision test 1";
502 EXPECT_EQ(9, rc[1].first.idx() ) << "Wrong handle of second face in ray collision test 1";
503
504
505 // Some intersection test to see, if we really have something usefull here:
506 Mesh::FaceVertexIter fv_it = Mesh::FaceVertexIter(mesh_, rc[0].first);
507
508 float distance,u,v;
509 Mesh::Point p1 = mesh_.point(*fv_it);
510 Mesh::Point p2 = mesh_.point(*(++fv_it));
511 Mesh::Point p3 = mesh_.point(*(++fv_it));
512
513 ACG::Geometry::triangleIntersection(origin,
514 yDirection,
515 p1,
516 p2,
517 p3,
518 distance,
519 u,
520 v);
521
522 EXPECT_EQ(1.0f, distance ) << "Wrong distance";
523 EXPECT_EQ(0.25f, u ) << "Wrong u";
524 EXPECT_EQ(0.5f , v ) << "Wrong v";
525
526 }
527
528 }
529
530 TEST_F(BSP_CUBE_BASE, RayIntersectionAboveSurface_DirectionalFunction_NegativeDirection_1 ) {
531 // ==============================================
532 // Test some Rays
533 // ==============================================
534
535 // Shoot through face 4 in negative y direction
536 // Start point is not on face 4
537 // x ======== x
538 // / \ /
539 // / \ 1 / |
540 // / 0 \ / |
541 // / \ / |
542 // x ======== x |
543 // | / | |
544 // | 4 / | x z
545 // | / | / | y
546 // | p / 5 | / | /
547 // | / | / | /
548 // | / |/ |/
549 // x ======== x -------> x
550
551 Mesh::Point nyDirection(0.0,-1.0,0.0);
552 Mesh::Point p1(-0.5,-2.0,0.0);
553 BSP::RayCollision rc;
554 rc = bsp_->directionalRaycollision(p1,nyDirection);
555
556 EXPECT_EQ(0u, rc.size() ) << "Wrong number of hit faces in ray collision test 1";
557
558 }
559
BSPImplT< TriangleBSPCoreT< OpenMeshTriangleBSPTraits< Mesh > > >::RayCollision
std::vector< std::pair< Handle, Scalar > > RayCollision
Store nearest neighbor information.
Definition: BSPImplT.hh:105
TriangleBSPCoreT::reserve
void reserve(size_t _n)
Reserve memory for _n entries.
Definition: TriangleBSPCoreT.hh:105
OpenMesh::PolyMeshT::Point
Kernel::Point Point
Coordinate type.
Definition: PolyMeshT.hh:115
OpenMesh::PolyMeshT::add_vertex
VertexHandle add_vertex(const Point &_p)
Alias for new_vertex(const Point&).
Definition: PolyMeshT.hh:236
OpenMesh::TriMesh_ArrayKernelT< CustomTraits >
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
OpenMeshTriangleBSPT
Definition: TriangleBSPT.hh:206
OpenMesh::PolyMeshT::VertexHandle
Kernel::VertexHandle VertexHandle
Handle for referencing the corresponding item.
Definition: PolyMeshT.hh:139
BSP_CUBE_BASE
Definition: BSP_test.cc:63
OpenMesh::PolyMeshT::FaceVertexIter
Kernel::FaceVertexIter FaceVertexIter
Circulator.
Definition: PolyMeshT.hh:170
CustomTraits
Definition: BSP_test.cc:56
TriangleBSPCoreT::push_back
void push_back(Handle _h)
Add a handle to the BSP.
Definition: TriangleBSPCoreT.hh:107
OpenMesh::DefaultTraits
Definition: Traits.hh:126
TriangleBSPCoreT::build
void build(unsigned int _max_handles, unsigned int _max_depth)
Definition: TriangleBSPCoreT.cc:72