Developer Documentation

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
PolyLinePluginT.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 #define POLYLINEPLUGIN_CC
43
44 #include "PolyLinePlugin.hh"
45 #include <queue>
46
47 //------------------------------------------------------------------------------
48
49
50 template< class MeshT >
51 bool cutted(MeshT& _mesh, typename MeshT::HalfedgeHandle _he, const ACG::Vec3d _planeNormal, const ACG::Vec3d _planePoint, ACG::Vec3d* _point = 0) {
52
53 //get intersection point with plane
54 typename MeshT::Point p0 = _mesh.point( _mesh.from_vertex_handle(_he) );
55 typename MeshT::Point p1 = _mesh.point( _mesh.to_vertex_handle(_he) );
56
57 typename MeshT::Point u = p1 - p0;
58 typename MeshT::Point w = p0 - _planePoint;
59
60 double D = (_planeNormal | u);
61 double N = - (_planeNormal | w);
62
63 // compute intersect parameter
64 double sI = N / D;
65
66 if ( _point ) {
67 *_point = p0 + sI * u;
68 }
69 return (sI >= 0.0 && sI <= 1.0 );
70 }
71
72 //------------------------------------------------------------------------------
73
83 template< class MeshT >
84 std::vector< ACG::Vec3d > getIntersectionLoop( MeshT* _mesh,
85 uint _fh,
86 ACG::Vec3d _planeNormal,
87 ACG::Vec3d _planePoint,
88 bool& _closed ) {
89
90 OpenMesh::HPropHandleT< bool > cut;
91 _mesh->get_property_handle(cut,"Plane Cut Property" );
92
93 typename MeshT::FaceHandle fh ( _fh );
94
95 typename MeshT::FaceHandle current_face = typename MeshT::FaceHandle(_fh);
96
97 bool stop = false;
98 bool nothingFound = true;
99 int expansionLevel = 0;
100 bool flip_dir = false;
101 _closed = true;
102
103 std::vector< ACG::Vec3d > linePoints;
104
105 std::vector< typename MeshT::FaceHandle > startCandidates;
106 std::vector< typename MeshT::FaceHandle > expandable;
107 expandable.push_back( fh );
108
109 while (!stop) {
110 stop = true;
111
112 // First check the face we are in
113 for ( typename MeshT::FaceHalfedgeIter fhe_it( *_mesh, current_face ); fhe_it.is_valid(); ++fhe_it){
114 if ( _mesh->property(cut,*fhe_it) )
115 continue;
116
117 typename MeshT::Point p0 = _mesh->point( _mesh->from_vertex_handle(*fhe_it) );
118 typename MeshT::Point p1 = _mesh->point( _mesh->to_vertex_handle(*fhe_it) );
119
120 typename MeshT::Point u = p1 - p0;
121 typename MeshT::Point w = p0 - _planePoint;
122
123 double D = (_planeNormal | u);
124 double N = - (_planeNormal | w);
125
126 // compute intersect param
127 double sI = N / D;
128 if (sI < 0.0 || sI > 1.0 ) // intersection on ray, but not within line segment
129 continue;
130
131 nothingFound = false;
132
133 stop = false;
134 _mesh->property(cut,*fhe_it) = true;
135 _mesh->property(cut,_mesh->opposite_halfedge_handle(*fhe_it)) = true;
136 current_face = _mesh->face_handle(_mesh->opposite_halfedge_handle(*fhe_it));
137
138 if (!current_face.is_valid())
139 stop = true;
140
141 typename MeshT::Point cutPoint = p0 + sI * u;
142
143 // add new point
144 if ( !flip_dir )
145 linePoints.push_back(cutPoint);
146 else {
147 linePoints.insert( linePoints.begin() , cutPoint );
148 _closed = false;
149 }
150
151 break;
152 }
153
154 if ( stop ){
155 if ( nothingFound ){
156 if ( startCandidates.empty() ){
157
158 if (expansionLevel > 3 )
159 std::cerr << "Expanded" << expansionLevel << "rings but still nothing found!" << std::endl;
160 else{
161
162 //add the "expansionLevel"-ring of the start-face to the start candidates
163 for (uint i=0; i < expandable.size(); i++)
164 for( typename MeshT::FaceFaceIter ff_it(*_mesh, expandable[i]); ff_it.is_valid(); ++ff_it )
165 startCandidates.push_back( *ff_it );
166
167 expandable.clear();
168 expansionLevel++;
169 }
170 }
171
172 if ( !startCandidates.empty() ){
173 fh = startCandidates.back();
174 expandable.push_back( fh );
175 startCandidates.pop_back();
176 stop = false;
177 }
178
179 }else if (! flip_dir ){
180 flip_dir = true;
181 stop = false;
182 }
183
184 current_face = fh;
185 }
186 }
187
188 return linePoints;
189
190 }
191
192 //------------------------------------------------------------------------------
193
203 template< class MeshT >
204 std::vector< ACG::Vec3d > PolyLinePlugin::getIntersectionPoints( MeshT* _mesh,
205 uint _fh,
206 ACG::Vec3d _planeNormal,
207 ACG::Vec3d _planePoint,
208 bool& _closed ) {
209 OpenMesh::HPropHandleT< bool > cut;
210 _mesh->add_property(cut,"Plane Cut Property" );
211
212 typename MeshT::HalfedgeIter e_it, e_end = _mesh->halfedges_end();
213 for( e_it = _mesh->halfedges_begin(); e_it != e_end; ++e_it )
214 _mesh->property( cut, *e_it ) = false;
215
216 std::vector< ACG::Vec3d > linePoints = getIntersectionLoop(_mesh,_fh,_planeNormal,_planePoint,_closed);
217
218 _mesh->remove_property( cut );
219
220 return linePoints;
221 }
222
223 //------------------------------------------------------------------------------
224
232 template< class MeshT >
233 typename MeshT::EdgeHandle
234 PolyLinePlugin::getCuttedEdge(MeshT& _mesh, ACG::Vec3d& _planeNormal, ACG::Vec3d& _planePoint) {
235
236 typename MeshT::EdgeIter e_it;
237 typename MeshT::EdgeIter e_end = _mesh.edges_end();
238
239 typename MeshT::Scalar minDistance = FLT_MAX;
240 typename MeshT::EdgeHandle minEdge(-1);
241
242 for (e_it = _mesh.edges_begin(); e_it != e_end; ++e_it){
243
244 typename MeshT::HalfedgeHandle hh = _mesh.halfedge_handle(*e_it, 0);
245
246 //get intersection point with plane
247 typename MeshT::Point p0 = _mesh.point( _mesh.from_vertex_handle(hh) );
248 typename MeshT::Point p1 = _mesh.point( _mesh.to_vertex_handle(hh) );
249
250 typename MeshT::Point u = p1 - p0;
251 typename MeshT::Point w = p0 - _planePoint;
252
253 double D = (_planeNormal | u);
254 double N = - (_planeNormal | w);
255
256 // compute intersect param
257 double sI = N / D;
258
259 if (sI >= 0.0 && sI <= 1.0 ){
260
261 typename MeshT::Point cutPoint = p0 + sI * u;
262
263 typename MeshT::Scalar dist = (cutPoint - _planePoint).sqrnorm();
264
265 if ( dist < minDistance ){
266
267 minDistance = dist;
268 minEdge = *e_it;
269 }
270 }
271 }
272
273 return minEdge;
274 }
275
276
277
278
286 template< class MeshT >
287 std::vector< std::vector<ACG::Vec3d> > PolyLinePlugin::getMultipleIntersectionPoints( MeshT* _mesh,
288 ACG::Vec3d _planeNormal,
289 ACG::Vec3d _planePoint) {
290
291 std::vector< std::vector<ACG::Vec3d> > lines;
292
293 OpenMesh::HPropHandleT< bool > cut;
294 _mesh->add_property(cut,"Plane Cut Property" );
295
296 std::queue< typename MeshT::EdgeHandle > queue;
297
298 // Mark all edges as not cut, and remember cutted edges as starting points if we get multiple unconnected cuts
299 for( typename MeshT::EdgeIter e_it = _mesh->edges_begin(); e_it != _mesh->edges_end(); ++e_it ) {
300
301 // Remember cutted edge
302 if ( cutted(*_mesh, _mesh->halfedge_handle(*e_it, 0),_planeNormal, _planePoint, 0) ) {
303 queue.push(*e_it);
304 }
305
306 //Initialize halfedge Property
307 _mesh->property( cut, _mesh->halfedge_handle(*e_it, 0) ) = false;
308 _mesh->property( cut, _mesh->halfedge_handle(*e_it, 1) ) = false;
309
310 }
311
312
313 // Used to catch all connected components
314 while( !queue.empty() ) {
315
316 // Get next element from queue
317 typename MeshT::HalfedgeHandle hh = _mesh->halfedge_handle( queue.front() , 0);
318 queue.pop();
319
320 // Already visited so skip this one
321 if ( _mesh->property(cut,hh) )
322 continue;
323
324 // Get the adjacent face
325 typename MeshT::FaceHandle fh = _mesh->face_handle(hh);
326
327 // If we are at a boundary, get next
328 if ( !fh.is_valid() ) {
329 fh = _mesh->face_handle(_mesh->opposite_halfedge_handle(hh));
330 }
331
332 // No face anywhere at this edge? This should not happen, so we just skip the edge
333 if ( !fh.is_valid() )
334 continue;
335
336
337 bool closed = false;
338
339 // Compute the polyline from current face
340 lines.push_back(getIntersectionLoop(_mesh,fh.idx(),_planeNormal,_planePoint,closed) );
341
342 }
343
344 // Cleanup
345 _mesh->remove_property( cut );
346
347 return lines;
348
349 }
350
351
352
OpenMesh::HPropHandleT
Definition: Property.hh:501
PolyLinePlugin::getMultipleIntersectionPoints
std::vector< std::vector< ACG::Vec3d > > getMultipleIntersectionPoints(MeshT *_mesh, ACG::Vec3d _planeNormal, ACG::Vec3d _planePoint)
get all points from the intersection between mesh and plane
Definition: PolyLinePluginT.cc:287
PolyLinePlugin::getCuttedEdge
MeshT::EdgeHandle getCuttedEdge(MeshT &_mesh, ACG::Vec3d &_planeNormal, ACG::Vec3d &_planePoint)
get an edge of the mesh that is cut by the plane
Definition: PolyLinePluginT.cc:234
PolyLinePlugin::getIntersectionPoints
std::vector< ACG::Vec3d > getIntersectionPoints(MeshT *_mesh, uint _fh, ACG::Vec3d _planeNormal, ACG::Vec3d _planePoint, bool &_closed)
get the points from the closest connected intersection between mesh and plane
Definition: PolyLinePluginT.cc:204
OpenMesh::VectorT
Definition: Vector11T.hh:83