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 //=============================================================================
OpenMesh::TriMesh_ArrayKernelT< CustomTraits >
TriangleBSPCoreT::size
size_t size()
Definition: TriangleBSPCoreT.hh:107
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
OVMOMCommonTriangleBSPTraits::y_sort
Definition: TriangleBSPT.hh:175
TriangleBSPT
Definition: TriangleBSPT.hh:64
OMSpecificTriangleBSPTraits
Definition: TriangleBSPT.hh:183
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
OpenVolumeMesh::HandleT
Definition: OpenVolumeMeshHandle.hh:93
BSPImplT
Definition: BSPImplT.hh:64
OVMOMCommonTriangleBSPTraits::x_sort
Definition: TriangleBSPT.hh:174
TreeNode
Definition: BSPTreeNode.hh:63
OVMOMCommonTriangleBSPTraits::calculateBoundingBox
void calculateBoundingBox(Node *_node, Point &median, int &axis)
Definition: TriangleBSPT.hh:96
OVMOMCommonTriangleBSPTraits::z_sort
Definition: TriangleBSPT.hh:176
OVMOMCommonTriangleBSPTraits
Definition: TriangleBSPT.hh:76
OpenMeshTriangleBSPT
Definition: TriangleBSPT.hh:212