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