Developer Documentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
TriangleBSPT.hh
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 TriangleBSPT
56 //
57 //=============================================================================
58 
59 #ifndef MB_TRIANGLEBSP_HH
60 #define MB_TRIANGLEBSP_HH
61 
62 
63 //== INCLUDES =================================================================
64 
65 #include "BSPTreeNode.hh"
66 #include "TriangleBSPCoreT.hh"
67 #include "BSPImplT.hh"
68 
69 #include <list>
70 //== CLASS DEFINITION =========================================================
71 
72 template <class BSPTraits>
73 class TriangleBSPT : public BSPImplT< TriangleBSPCoreT<BSPTraits> >
74 {
75 public:
76  typedef BSPImplT< TriangleBSPCoreT<BSPTraits> > Base;
77  typedef typename Base::Scalar Scalar;
78  TriangleBSPT(const BSPTraits& _traits,
79  const Scalar& _infinity = std::numeric_limits<Scalar>::infinity()) : Base(_traits, _infinity) {}
80 };
81 
82 //== CLASS DEFINITION =========================================================
83 
84 template <class Mesh, class SpecificTraits>
85 class OVMOMCommonTriangleBSPTraits : public SpecificTraits
86 {
87 public:
88 
89  typedef typename SpecificTraits::Point Point;
90  typedef typename SpecificTraits::Handle Handle;
91  typedef typename Point::value_type Scalar;
92  typedef std::vector<Handle> Handles;
93  typedef typename Handles::iterator HandleIter;
94  typedef TreeNode<SpecificTraits> Node;
95 
96  OVMOMCommonTriangleBSPTraits(const Mesh& _mesh) : SpecificTraits(_mesh) {}
97 
98  Scalar sqrdist(const Handle _h, const Point& _p) const
99  {
100  Point p0, p1, p2, q;
101  this->points(_h, p0, p1, p2);
102  return ACG::Geometry::distPointTriangleSquaredStable(_p, p0, p1, p2, q);
103  }
104 
105  void calculateBoundingBox(Node* _node, Point& median, int& axis)
106  {
107  //determine splitting axis
108  HandleIter it_h;
109  Point p0, p1, p2, bb_min, bb_max;
110  bb_min.vectorize(std::numeric_limits<typename Point::value_type>::infinity());
111  bb_max.vectorize(-std::numeric_limits<typename Point::value_type>::infinity());
112  std::list<Point> vertices;
113 
114  for (it_h = _node->begin(); it_h != _node->end(); ++it_h) {
115  this->points(*it_h, p0, p1, p2);
116  /*
117  bb_min.minimize(p0);
118  bb_min.minimize(p1);
119  bb_min.minimize(p2);
120  bb_max.maximize(p0);
121  bb_max.maximize(p1);
122  bb_max.maximize(p2);*/
123 
124  vertices.push_back(p0);
125  vertices.push_back(p1);
126  vertices.push_back(p2);
127  }
128  bb_min = _node->bb_min;
129  bb_max = _node->bb_max;
130 
131  // split longest side of bounding box
132  Point bb = bb_max - bb_min;
133  Scalar length = bb[0];
134  axis = 0;
135  if (bb[1] > length)
136  length = bb[(axis = 1)];
137  if (bb[2] > length)
138  length = bb[(axis = 2)];
139 
140  //calculate the median value in axis-direction
141  switch (axis) {
142  case 0:
143  vertices.sort(x_sort());
144  break;
145  case 1:
146  vertices.sort(y_sort());
147  break;
148  case 2:
149  vertices.sort(z_sort());
150  break;
151  }
152  vertices.unique();
153 
154  size_t size = vertices.size();
155  typename std::list<Point>::iterator it_v;
156  it_v = vertices.begin();
157  std::advance(it_v, size / 2);
158  median = *it_v;
159 
160  }
161 
162  void calculateBoundingBoxRoot(Node* _node)
163  {
164  HandleIter it;
165  Point p0, p1, p2, bb_min, bb_max;
166  bb_min.vectorize(FLT_MAX);
167  bb_max.vectorize(-FLT_MAX);
168  for (it = _node->begin(); it != _node->end(); ++it) {
169  this->points(*it, p0, p1, p2);
170  bb_min.minimize(p0);
171  bb_min.minimize(p1);
172  bb_min.minimize(p2);
173  bb_max.maximize(p0);
174  bb_max.maximize(p1);
175  bb_max.maximize(p2);
176  }
177  _node->bb_min = bb_min;
178  _node->bb_max = bb_max;
179  }
180 
181 private:
182  //functors for sorting in different directions
183  struct x_sort { bool operator()(const Point& first, const Point& second) { return (first[0] < second[0]); } };
184  struct y_sort { bool operator()(const Point& first, const Point& second) { return (first[1] < second[1]); } };
185  struct z_sort { bool operator()(const Point& first, const Point& second) { return (first[2] < second[2]); } };
186 };
187 
188 
189 //== CLASS DEFINITION =========================================================
190 
191 template <class Mesh>
192 class OMSpecificTriangleBSPTraits
193 {
194 public:
195  typedef typename Mesh::Point Point;
196  typedef typename Mesh::FaceHandle Handle;
197  typedef typename Mesh::VertexHandle VertexHandle;
198  OMSpecificTriangleBSPTraits(const Mesh& _mesh) : mesh_(_mesh) {}
199 
201  inline void points(const Handle &_h, Point& _p0, Point& _p1, Point& _p2) const
202  {
203  const auto &mesh = this->mesh_;
204  typename Mesh::CFVIter fv_it(mesh.cfv_iter(_h));
205  _p0 = mesh.point(*fv_it);
206  ++fv_it;
207  _p1 = mesh.point(*fv_it);
208  ++fv_it;
209  _p2 = mesh.point(*fv_it);
210  }
211 protected:
212  const Mesh& mesh_;
213 };
214 
215 template<class Mesh>
216 using OpenMeshTriangleBSPTraits = OVMOMCommonTriangleBSPTraits<Mesh, OMSpecificTriangleBSPTraits<Mesh>>;
217 
218 
219 //== CLASS DEFINITION =========================================================
220 template <class Mesh>
221 class OpenMeshTriangleBSPT
222  : public TriangleBSPT<OpenMeshTriangleBSPTraits<Mesh> >
223 {
224 public:
225  typedef OpenMeshTriangleBSPTraits<Mesh> Traits;
226  typedef TriangleBSPT<Traits> Base;
227  typedef typename Traits::Scalar Scalar;
228  OpenMeshTriangleBSPT(const Mesh& _mesh,
229  const Scalar& _infinity = std::numeric_limits<Scalar>::infinity())
230  : Base(Traits(_mesh), _infinity) {}
231 };
232 
233 
234 #ifdef ENABLE_OPENVOLUMEMESH
235 
236 namespace OpenVolumeMesh {
237  class VertexHandle;
238  class FaceHandle;
239 }
240 
241 //== CLASS DEFINITION =========================================================
242 
243 // Make sure all faces of the mesh have valence 3.
244 template <class Mesh>
245 class OVMSpecificTriangleBSPTraits
246 {
247 public:
248  typedef typename Mesh::PointT Point;
249  typedef OpenVolumeMesh::FaceHandle Handle;
250  typedef OpenVolumeMesh::VertexHandle VertexHandle;
251  OVMSpecificTriangleBSPTraits(const Mesh& _mesh) : mesh_(_mesh) {}
252 
254  inline void points(const Handle &_h, Point& _p0, Point& _p1, Point& _p2) const
255  {
256  const auto &mesh = this->mesh_;
257  assert(mesh.valence(_h) == 3);
258  auto hfv_it (mesh.hfv_iter(mesh.halfface_handle(_h, 0)));
259  _p0 = mesh.vertex(*hfv_it++);
260  _p1 = mesh.vertex(*hfv_it++);
261  _p2 = mesh.vertex(*hfv_it++);
262  }
263 protected:
264  const Mesh& mesh_;
265 };
266 
267 
268 template<class Mesh>
269 using OpenVolumeMeshTriangleBSPTraits = OVMOMCommonTriangleBSPTraits<Mesh, OVMSpecificTriangleBSPTraits<Mesh>>;
270 
271 //== CLASS DEFINITION =========================================================
272 template <class Mesh>
273 class OpenVolumeMeshTriangleBSPT
274  : public TriangleBSPT<OpenVolumeMeshTriangleBSPTraits<Mesh> >
275 {
276 public:
277  typedef OpenVolumeMeshTriangleBSPTraits<Mesh> Traits;
278  typedef TriangleBSPT<Traits> Base;
279  typedef typename Traits::Scalar Scalar;
280  OpenVolumeMeshTriangleBSPT(const Mesh& _mesh,
281  const Scalar& _infinity = std::numeric_limits<Scalar>::infinity())
282  : Base(Traits(_mesh), _infinity) {}
283 };
284 
285 #endif // ENABLE_OPENVOLUMEMESH
286 
287 
288 //=============================================================================
289 #endif // MB_TRIANGLEBSP_HH defined
290 //=============================================================================
OVMOMCommonTriangleBSPTraits::calculateBoundingBox
void calculateBoundingBox(Node *_node, Point &median, int &axis)
Definition: TriangleBSPT.hh:105
ACG::Geometry::distPointTriangleSquaredStable
Vec::value_type distPointTriangleSquaredStable(const Vec &_p, const Vec &_v0, const Vec &_v1, const Vec &_v2, Vec &_nearestPoint)
squared distance from point _p to triangle (_v0, _v1, _v2)
Definition: Algorithms.cc:476
OMSpecificTriangleBSPTraits::points
void points(const Handle &_h, Point &_p0, Point &_p1, Point &_p2) const
Returns the points belonging to the face handle _h.
Definition: TriangleBSPT.hh:201
OpenMesh::PolyMeshT::Point
Kernel::Point Point
Coordinate type.
Definition: PolyMeshT.hh:115
OpenMesh::PolyMeshT::VertexHandle
Kernel::VertexHandle VertexHandle
Handle for referencing the corresponding item.
Definition: PolyMeshT.hh:139