Developer Documentation
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 
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 ) {
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 
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 
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
MeshT::EdgeHandle getCuttedEdge(MeshT &_mesh, ACG::Vec3d &_planeNormal, ACG::Vec3d &_planePoint)
get an edge of the mesh that is cut by the plane
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