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 /*
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
OpenMesh::PolyMeshT::FaceVertexIter
Kernel::FaceVertexIter FaceVertexIter
Circulator.
Definition: PolyMeshT.hh:170
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
OpenMesh::PolyMeshT::VertexHandle
Kernel::VertexHandle VertexHandle
Handle for referencing the corresponding item.
Definition: PolyMeshT.hh:139
OpenMesh::PolyMeshT::add_vertex
VertexHandle add_vertex(const Point &_p)
Alias for new_vertex(const Point&).
Definition: PolyMeshT.hh:236
OpenMesh::PolyMeshT::Point
Kernel::Point Point
Coordinate type.
Definition: PolyMeshT.hh:115