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