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 
49 struct CustomTraits : public OpenMesh::DefaultTraits {
50 };
51 
52 typedef OpenMesh::TriMesh_ArrayKernelT<CustomTraits> Mesh;
53 
54 typedef OpenMeshTriangleBSPT< Mesh > BSP;
55 
56 class 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  */
229 TEST_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  */
239 TEST_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  */
248 TEST_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 
279 TEST_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 
296 TEST_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 
313 TEST_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 
332 TEST_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 
368 TEST_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 
401 TEST_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 
431 TEST_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 
464 TEST_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 
523 TEST_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 
OpenMesh::PolyMeshT::Point
Kernel::Point Point
Coordinate type.
Definition: PolyMeshT.hh:112
OpenMesh::PolyMeshT::add_vertex
VertexHandle add_vertex(const Point &_p)
Alias for new_vertex(const Point&).
Definition: PolyMeshT.hh:235
OpenMesh::PolyMeshT::FaceVertexIter
Kernel::FaceVertexIter FaceVertexIter
Circulator.
Definition: PolyMeshT.hh:167
OpenMesh::PolyMeshT::VertexHandle
Kernel::VertexHandle VertexHandle
Handle for referencing the corresponding item.
Definition: PolyMeshT.hh:136
BSPImplT< TriangleBSPCoreT< OpenMeshTriangleBSPTraits< Mesh > > >::RayCollision
std::vector< std::pair< Handle, Scalar > > RayCollision
Store nearest neighbor information.
Definition: BSPImplT.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