?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
fixed: auto_ptr -> unique_ptr
[opensg.git] / Source / System / NodeCores / Drawables / Nurbs / Internal / OSGParSpaceTrimmer.cpp
blob2a8c1b3d581a4b58de045a8ea5953d2b3b626d40
1 /*---------------------------------------------------------------------------*\
2 * OpenSG NURBS Library *
3 * *
4 * *
5 * Copyright (C) 2001-2006 by the University of Bonn, Computer Graphics Group*
6 * *
7 * http://cg.cs.uni-bonn.de/ *
8 * *
9 * contact: edhellon@cs.uni-bonn.de, guthe@cs.uni-bonn.de, rk@cs.uni-bonn.de *
10 * *
11 \*---------------------------------------------------------------------------*/
12 /*---------------------------------------------------------------------------*\
13 * License *
14 * *
15 * This library is free software; you can redistribute it and/or modify it *
16 * under the terms of the GNU Library General Public License as published *
17 * by the Free Software Foundation, version 2. *
18 * *
19 * This library is distributed in the hope that it will be useful, but *
20 * WITHOUT ANY WARRANTY; without even the implied warranty of *
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
22 * Library General Public License for more details. *
23 * *
24 * You should have received a copy of the GNU Library General Public *
25 * License along with this library; if not, write to the Free Software *
26 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. *
27 * *
28 \*---------------------------------------------------------------------------*/
29 /*---------------------------------------------------------------------------*\
30 * Changes *
31 * *
32 * *
33 * *
34 * *
35 * *
36 * *
37 \*---------------------------------------------------------------------------*/
38 #include "OSGParSpaceTrimmer.h"
39 #ifdef OSG_ADAPTIVE_QUAD_TREE
40 #include "OSGQuadTreeCreator.h"
41 #endif
42 #include "OSGSimplePolygon.h"
43
44 #include "OSGpredicates.h"
45 #include <float.h>
46
47 OSG_USING_NAMESPACE
48
49 #ifdef OSG_WIN32_ICL
50 #pragma warning( disable : 171 )
51 #endif
52
53 #ifdef WIN32
54 #pragma warning (disable : 985)
55 #endif
56
57 #ifdef _DEBUG
58 #ifdef OSG_WIN32
59 #undef THIS_FILE
60 static char THIS_FILE[] = __FILE__;
61 #endif
62 #endif
63
64 #ifdef OSG_USE_SIMPLIFIER
65 #define OSG_SIMPLIFIER_TESS_ERR 0.75
66 #endif
67
68 #define ROUND_EPS 1e-6
69
70 #define OSG_SPLIT_HOLE_CELLS
71
72 bool ParSpaceTrimmer::isOverQuad(DCTPFace *f, Vec2d &p)
73 {
74 #ifdef OSG_UNION_TRI_QUAD
75 /* std::cerr << "isoverface: " << f->orig_face[0]->coords << " "
76 << f->orig_face[1]->coords << " "
77 << f->orig_face[2]->coords << " "
78 << f->orig_face[3]->coords << std::endl;
79 std::cerr << " point: " << p << std::endl;*/
80 if(p[0] >= f->orig_face[0]->coords[0] &&
81 p[0] <= f->orig_face[1]->coords[0] &&
82 p[1] <= f->orig_face[0]->coords[1] &&
83 p[1] >= f->orig_face[3]->coords[1])
84 #else
85 /* std::cerr << "isoverface: " << f->orig_quad[0]->coords << " "
86 << f->orig_quad[1]->coords << " "
87 << f->orig_quad[2]->coords << " "
88 << f->orig_quad[3]->coords << std::endl;
89 std::cerr << " point: " << p << std::endl;*/
90 if(p[0] >= f->orig_quad[0]->coords[0] &&
91 p[0] <= f->orig_quad[1]->coords[0] &&
92 p[1] <= f->orig_quad[0]->coords[1] &&
93 p[1] >= f->orig_quad[3]->coords[1])
94 #endif
95
96
97
98 return true;
99 else
100 return false;
101 }
102
103 bool ParSpaceTrimmer::isNearQuad(DCTPFace *f, Vec2d &p)
104 {
105
106 /* std::cerr << "isoverface: " << f->orig_quad[0]->coords << " "
107 << f->orig_quad[1]->coords << " "
108 << f->orig_quad[2]->coords << " "
109 << f->orig_quad[3]->coords << std::endl;
110 std::cerr << " point: " << p << std::endl;*/
111
112 #ifdef OSG_UNION_TRI_QUAD
113 if( (p[0] - f->orig_face[0]->coords[0] > -DCTP_EPS * 2.0) &&
114 (p[0] - f->orig_face[1]->coords[0] < DCTP_EPS * 2.0) &&
115 (p[1] - f->orig_face[0]->coords[1] < DCTP_EPS * 2.0) &&
116 (p[1] - f->orig_face[3]->coords[1] > -DCTP_EPS * 2.0) )
117 #else
118 if( (p[0] - f->orig_quad[0]->coords[0] > -DCTP_EPS * 2.0) &&
119 (p[0] - f->orig_quad[1]->coords[0] < DCTP_EPS * 2.0) &&
120 (p[1] - f->orig_quad[0]->coords[1] < DCTP_EPS * 2.0) &&
121 (p[1] - f->orig_quad[3]->coords[1] > -DCTP_EPS * 2.0) )
122 #endif
123
124
125
126 return true;
127 else
128 return false;
129 }
130
131 bool ParSpaceTrimmer::isOverFace(DCTPFace *f, Vec2d &p)
132 {
133 return isOverQuad(f, p);
134 }
135
136 void ParSpaceTrimmer::getStartingFace(Vec2d p)
137 {
138 dctpfacevector::iterator fend = mesh->faces.end();
139 dctpfacevector::iterator i;
140
141 if(p[0] < m_clMin[0])
142 p[0] = m_clMin[0];
143 else if(p[0] > m_clMax[0])
144 p[0] = m_clMax[0];
145 if(p[1] < m_clMin[1])
146 p[1] = m_clMin[1];
147 else if(p[1] > m_clMax[1])
148 p[1] = m_clMax[1];
149
150 for(i = mesh->faces.begin(); i != fend; ++i)
151 {
152 if(isOverFace(*i, p) )
153 {
154 state.state = TrimState::OVER_FACE;
155 state.f = *i;
156 return;
157 }
158 } //end for( i
159
160 for(i = mesh->faces.begin(); i != fend; ++i)
161 {
162 if(isNearQuad(*i, p) )
163 {
164 state.state = TrimState::OVER_FACE;
165 state.f = *i;
166 return;
167 }
168 } //end for( i
169
170 //doncha wanna get here
171 std::cerr << "Couldn't find starting face!" << std::endl;
172
173 throw ParSpaceTrimmerError(ERR_NO_STARTING_FACE);
174 }
175
176 bool ParSpaceTrimmer::isOnSection(Vec2d &p1, Vec2d &p2, Vec2d &p)
177 {
178
179 Vec2d norm, t;
180 double dist;
181 double par;
182 double lab = sqrt( (p1[0] - p2[0]) * (p1[0] - p2[0]) +
183 (p1[1] - p2[1]) * (p1[1] - p2[1]) );
184 norm[0] = -(p2[1] - p1[1]) / lab; // This is a normal -> rotated by 90 degrees
185 norm[1] = (p2[0] - p1[0]) / lab;
186
187 t[0] = p[0] - p1[0];
188 t[1] = p[1] - p1[1];
189 dist = t[0] * norm[0] + t[1] * norm[1];
190 if(osgAbs(dist) < DCTP_EPS)
191 {
192 // it is on the line at least, check if it's on the section
193 if(osgAbs(p2[0] - p1[0]) > DCTP_EPS)
194 par = (p[0] - p1[0]) / (p2[0] - p1[0]);
195 else
196 par = (p[1] - p1[1]) / (p2[1] - p1[1]);
197 if(par < -DCTP_EPS || par > (1 + DCTP_EPS) )
198 return false;
199 else
200 return true;
201 }
202 else
203 return false;
204 }
205
206 bool ParSpaceTrimmer::isOnEdge(DCTPEdge *e, Vec2d &p, DCTPVertex* &v)
207 {
208 DCTPVertex *v1, *v2;
209 e->getVertices(v1, v2);
210 Vec2d v1coords(v1->coords[0], v1->coords[1]);
211 Vec2d v2coords(v2->coords[0], v2->coords[1]);
212 if(DCTPVecIsEqual(p, v1coords) )
213 {
214 v = v1;
215 return true;
216 }
217 if(DCTPVecIsEqual(p, v2coords) )
218 {
219 v = v2;
220 return true;
221 }
222 v = NULL;
223 return isOnSection(v1coords, v2coords, p);
224 }
225
226 void *ParSpaceTrimmer::isOnFaceBoundary(DCTPFace *f, Vec2d &p, bool& isedge)
227 //if returned ptr is not NULL,
228 //isedge = false means (void*) points to a vertex
229 //isedge = true means (void*) points to an edge
230 {
231 std::vector<DCTPEdge *>::iterator eend = f->edges.end();
232
233 for(std::vector<DCTPEdge *>::iterator i = f->edges.begin(); i != eend; ++i)
234 {
235 DCTPVertex *v;
236
237 isedge = isOnEdge(*i, p, v);
238 if(isedge)
239 {
240 if(v)
241 {
242 isedge = false;
243 return v;
244 }
245 else
246 {
247 return *i;
248 }
249 }
250 } //end for i
251
252 return NULL;
253 }
254
255 void ParSpaceTrimmer::initializeStartState(bezier2ddeque& tc)
256 {
257 // std::cerr << "initializeStartState: tc.size(): " << tc.size() << std::endl;
258
259 BezierCurve2D & b = tc[0];
260 DCTPVec3dvector &cp = b.getControlPointVector(); //std::cerr << "got control point vector " << std::endl;
261 Vec2d p;
262 p[0] = cp[0][0] / cp[0][2]; // p = first point of the curveseq.
263 p[1] = cp[0][1] / cp[0][2]; // eucl projected.
264 getStartingFace(p); //std::cerr << "got starting face " << std::endl;
265
266 start_face = NULL;
267 bool isedge;
268 void *ptr;
269 if( (ptr = isOnFaceBoundary(state.f, p, isedge) ) )
270 {
271 state.state = TrimState::IN_VERTEX;
272 if(!isedge) //startin' from a vertex
273 {
274 // std::cerr << "start is in edge" << std::endl;
275 state.v = static_cast<DCTPVertex*>(ptr);
276 }
277 else
278 {
279 // std::cerr << "start is on boundary" << std::endl;
280 //starting on an edge: split
281 Vec3d p3d = Vec3d(p);
282 // state.v = mesh->SplitEdge( (DCTPEdge*)ptr, p3d );
283 state.v = mesh->findVertex(p3d);
284 if(state.v == NULL)
285 {
286 state.v = new DCTPVertex;
287 state.v->coords = p3d;
288 state.v->faces = (static_cast<DCTPEdge*>(ptr) )->faces;
289 // std::cerr << "2-" << ptr << " " << state.v << std::endl;
290 state.v->edges.push_back(static_cast<DCTPEdge*>(ptr) );
291 }
292 state.v->vertexinfo = reinterpret_cast<void*>(1);
293 }
294 }
295 else
296 {
297 // std::cerr << "start is in face" << std::endl;
298 //TrimSegment tsg;
299 //tsg.start = NULL;
300 //state.f->trimseg.push_back( tsg );
301 start_face = state.f;
302 }
303
304 }
305
306 void ParSpaceTrimmer::initializeStartState2(unsigned int uiLoop, std::vector<DCTPVertex*> &el)
307 {
308 // std::cerr << "initializeStartState: tc.size(): " << tc.size() << std::endl;
309
310 const unsigned int cui_size = UInt32((*pvccrd)[uiLoop].size());
311 Vec2d & p = (*pvccrd)[uiLoop][cui_size - 1];
312 Vec3d & rcl_s = (*m_pvvclSewed)[uiLoop][cui_size - 1];
313 #ifdef OSG_FORCE_NO_T_VERTICES
314 /* #ifndef OSG_CREATE_NORMAL_MAPS
315 Vec3d &rcl_n = ( *m_pvvclNormals )[ uiLoop ][ cui_size - 1 ];
316 #endif*/
317 #endif
318
319 /* if( p[0] < m_clMin[0] ) p[0] = m_clMin[0];
320 else if( p[0] > m_clMax[0] ) p[0] = m_clMax[0];
321 if( p[1] < m_clMin[1] ) p[1] = m_clMin[1];
322 else if( p[1] > m_clMax[1] ) p[1] = m_clMax[1];*/
323
324 getStartingFace(p); //std::cerr << "got starting face " << std::endl;
325
326 // std::cerr << "init: " << p << " " << rcl_s << std::endl;
327
328 start_face = NULL;
329 bool isedge;
330 void *ptr;
331 if( (ptr = isOnFaceBoundary(state.f, p, isedge) ) )
332 {
333 state.state = TrimState::IN_VERTEX;
334 if(!isedge) //startin' from a vertex
335 {
336 // std::cerr << "start is in vertex" << std::endl;
337 state.v = static_cast<DCTPVertex*>(ptr);
338 }
339 else
340 {
341 // std::cerr << "start is on edge" << std::endl;
342 //starting on an edge: split
343 Vec3d p3d = Vec3d(p);
344 state.v = mesh->SplitEdge(static_cast<DCTPEdge*>(ptr), p3d);
345 // std::cerr << state.v->coords << std::endl;
346 }
347 #ifdef OSG_FORCE_NO_T_VERTICES
348 SPosNorm *pt_s = new SPosNorm;
349 pt_s->clPos = rcl_s;
350 /* #ifndef OSG_CREATE_NORMAL_MAPS
351 pt_s->clNorm = rcl_n;
352 #endif*/
353 #ifdef OSG_KEEP_2D_POINTS
354 pt_s->uiNum = m_uiPosCnt;
355 #endif
356 state.v->vertexinfo = static_cast<void*>(pt_s);
357 #else
358 Vec3d *pcl_s = new Vec3d(rcl_s);
359 state.v->vertexinfo = static_cast<void*>(pcl_s);
360 #endif
361 // std::cerr << state.v->vertexinfo << std::endl;
362 el.push_back(state.v);
363 }
364 else
365 {
366 // std::cerr << "start is in face" << std::endl;
367 start_face = state.f;
368 DCTPVertex *pcl_v = mesh->AddVertex(Vec3d(p) );
369 #ifdef OSG_FORCE_NO_T_VERTICES
370 SPosNorm *pt_s = new SPosNorm;
371 pt_s->clPos = rcl_s;
372 /* #ifndef OSG_CREATE_NORMAL_MAPS
373 pt_s->clNorm = rcl_n;
374 #endif*/
375 #ifdef OSG_KEEP_2D_POINTS
376 pt_s->uiNum = m_uiPosCnt;
377 #endif
378 pcl_v->vertexinfo = ( void* ) pt_s;
379 #else
380 Vec3d *pcl_s = new Vec3d(rcl_s);
381 pcl_v->vertexinfo = pcl_s;
382 #endif
383 // std::cerr << pcl_v->vertexinfo << std::endl;
384 el.push_back(pcl_v);
385 }
386
387 }
388
389 bool ParSpaceTrimmer::setMinIntersectionWithFace(BezierCurve2D &b)
390 {
391 ip = 1.5;
392 bool intersection = false;
393 std::vector<DCTPEdge *>::iterator eend = state.f->edges.end();
394 /*
395 * FIXME: check for degenerate bezier
396 * and throw an exception :- \
397 */
398 DCTPVec3dvector &cptemp = b.getControlPointVector();
399 Vec2d cp0eucl;
400 cp0eucl[0] = cptemp[0][0] / cptemp[0][2];
401 cp0eucl[1] = cptemp[0][1] / cptemp[0][2];
402
403 if(cptemp.size() == 2 && DCTPVecIsEqual(cptemp[0], cptemp[1]) )
404 throw ParSpaceTrimmerError(ERR_DEGENERATE_BEZIER);
405
406
407 /// dumpcontrolpoints( b );
408 /// std::cerr << "Face id: " << state.f->id << std::endl;
409 for(std::vector<DCTPEdge *>::iterator i = state.f->edges.begin();
410 i != eend; ++i)
411 {
412 DCTPdvector res;
413 DCTPVertex *v1, *v2;
414 (*i)->getVertices(v1, v2);
415 Vec2d v1coords(v1->coords[0], v1->coords[1]);
416 Vec2d v2coords(v2->coords[0], v2->coords[1]);
417
418 int err;
419 err = b.intersection(res, v1coords, v2coords);
420 if(err < 0)
421 {
422
423 std::cerr << "Brutal error " << err << " in: " <<
424 "ParSpaceTrimmer::setMinIntersectionWithFace" << std::endl;
425 throw ParSpaceTrimmerError(ERR_SET_MININTERSECTION);
426 }
427 /// std::cerr << " v1: " << v1coords << " v2: " << v2coords << std::endl;
428 /// if ( res.size() ) std::cerr << "minintersection res.size(): " << res.size() << " res[0]: " << res[0] << std::endl;
429 /// else std::cerr <<"minintersection nothing" << std::endl;
430 // we don't store intersections at t=0 because when going from IN_VERTEX->OVER_FACE
431 // we pretend early to be OVER_FACE (when actually still in the vertex)
432 if(res.size() != 0)
433 {
434 // !!!!!!!!!!!!!!!!!
435 const Vec2d ccl_temp = b.computewdeCasteljau(res[0], err);
436 // std::cerr << ccl_temp << cptemp[ 0 ] << res[ 0 ]<< std::endl;
437 if(DCTPVecIsNotEqual(ccl_temp, cp0eucl) && res[0] < ip)
438 {
439 ip = res[0];
440 ie = *i;
441 intersection = true;
442 }
443 // FIXME: akos hackedin
444 else if(res.size() >= 2 && DCTPVecIsEqual(ccl_temp, cp0eucl) && res[1] < ip)
445 {
446 const Vec2d ccl_temp2 = b.computewdeCasteljau(res[0], err);
447 if(DCTPVecIsNotEqual(ccl_temp2, cp0eucl) )
448 {
449 ip = res[1];
450 ie = *i;
451 intersection = true;
452 }
453 }
454 }
455 // FIXME: akos hackedin over
456 }
457
458 return intersection; //true means ip & ie are valid
459 }
460
461 bool ParSpaceTrimmer::setMinIntersectionWithFace2(Vec2d clAct, Vec2d clNext)
462 {
463 ip = 1.5;
464 bool intersection = false;
465 std::vector<DCTPEdge *>::iterator eend = state.f->edges.end();
466 /*
467 * FIXME: bug #n: check for degenerate bezier
468 * and throw an exception :- \
469 */
470 if(DCTPVecIsEqual(clAct, clNext) )
471 throw ParSpaceTrimmerError(ERR_DEGENERATE_BEZIER);
472
473 for(std::vector<DCTPEdge *>::iterator i = state.f->edges.begin();
474 i != eend; ++i)
475 {
476 double res;
477 DCTPVertex *v1, *v2;
478 (*i)->getVertices(v1, v2);
479 Vec2d v1coords(v1->coords[0], v1->coords[1]);
480 Vec2d v2coords(v2->coords[0], v2->coords[1]);
481
482 if(doIntersect(clAct, clNext, v1coords, v2coords, res) )
483 {
484 if( (res - 1.0 < DCTP_EPS) && (res > 1e-16) )
485 {
486 // std::cerr << "intersection: " << res << std::endl;
487 if(res < ip)
488 {
489 ie = *i;
490 ip = res;
491 }
492 intersection = true;
493 }
494 }
495 }
496
497 return intersection; //true means ip & ie are valid
498 }
499
500 bool ParSpaceTrimmer::StoreCurveApproximation(
501 BezierCurve2D & bc,
502 double t,
503 std::vector<DCTPVertex*> &el)
504 {
505 bezier2dvector nc; //new curves
506 bool rest_left;
507 double & norm = state.f->norm;
508 DCTPVec2dvector approx;
509
510 // std::cerr << "StoreCurveApproximation" << std::endl;
511
512 if(1.0 - t < DCTP_EPS)
513 {
514 rest_left = false;
515 DCTPVec3dvector vcp = bc.getControlPointVector();
516 // std::cerr <<vcp.size( ) << " ";
517 // std::cerr << vcp[ 0 ] << " " << vcp[ 1 ] << " ";
518 nc.push_back(bc);
519 vcp = nc[0].getControlPointVector();
520 // std::cerr << vcp.size( ) << std::endl;
521 }
522 else
523 {
524 bc.subDivision(t, nc);
525 bc = nc[1]; //nc[0] holdz da first part
526 rest_left = true;
527 }
528
529 // std::cerr << "norm = " << norm << std::endl;
530
531 nc[0].approximate(approx, norm);
532
533 if(approx.size() >= 2)
534 {
535 DCTPVec2dvector::iterator ae = approx.end();
536
537 for(DCTPVec2dvector::iterator i = approx.begin() + 1; i != ae; ++i)
538 {
539 (*i)[0] = ROUND_EPS * floor( (*i)[0] / ROUND_EPS + 0.5);
540 (*i)[1] = ROUND_EPS * floor( (*i)[1] / ROUND_EPS + 0.5);
541 // std::cerr << "inserting vertex in edge loop " << *i << std::endl;
542 DCTPVertex *pcl_new = mesh->findVertex(Vec3d(*i) );
543 if(pcl_new == NULL)
544 {
545 pcl_new = new DCTPVertex;
546 pcl_new->coords = Vec3d(*i);
547 }
548 // std::cerr << "el.push_back " << ( void* ) pcl_new << std::endl;
549 el.push_back(pcl_new);
550 }
551 }
552
553 return rest_left;
554 }
555
556 /*bool ParSpaceTrimmer::StoreCurveToFace(
557 BezierCurve2D &bc,
558 double t,
559 DCTPVertex *v ) {
560 //v is not NULL if curve ends in a node
561 //in state.f is the face to store into
562 /// std::cerr.precision( DCTP_PRECISION );
563 /// std::cerr << " storecurve: t:" << t << " v: " << (void*)v << std::endl;
564 bezier2dvector nc; //new curves
565 bool rest_left;
566
567 if ( 1.0 - t < DCTP_EPS )
568 {
569 rest_left = false;
570 nc.push_back( bc );
571 }
572 else
573 {
574 bc.subDivision( t, nc );
575 bc = nc[ 1 ];//nc[0] holdz da first part
576 rest_left = true;
577 }
578
579
580 TrimSegment& ts =
581 state.f->trimseg[ state.f->trimseg.size() - 1 ];//should exist!
582 ts.trimbeziers.push_back( nc[ 0 ] );
583 if ( v ) ts.end = v;
584 return rest_left;
585 }*/
586
587 bool ParSpaceTrimmer::goingOutOnEdge(BezierCurve2D &bc,
588 DCTPVertex* &v, bool &feu,
589 std::vector<DCTPVertex*> &el)
590 {
591 // bool on_edge = false;
592 /// std::cerr <<"goingout in..." << std::endl;
593 std::vector<DCTPEdge *>::iterator eend = state.v->edges.end();
594
595 for(std::vector<DCTPEdge *>::iterator i = state.v->edges.begin();
596 i != eend; ++i)
597 {
598 DCTPVertex *v1,*v2;
599 (*i)->getVertices(v1, v2);
600 DCTPdvector res;
601 // std::cerr << "goin'outonedge calling intersection and houston ;)" << std::endl;
602 // dumpcontrolpoints( bc );
603 // std::cerr << "v1: " << v1->coords << " v2: " << v2->coords << std::endl;
604 Vec2d v1coords(v1->coords[0], v1->coords[1]);
605 Vec2d v2coords(v2->coords[0], v2->coords[1]);
606
607 DCTPVec3dvector &cptemp = bc.getControlPointVector();
608 if(cptemp.size() == 2 && DCTPVecIsEqual(cptemp[0], cptemp[1]) )
609 throw ParSpaceTrimmerError(ERR_DEGENERATE_BEZIER);
610
611 int r = bc.intersection(res, v1coords, v2coords);
612 // std::cerr << "intersection result: " << r << "resultvector size: " << res.size() << std::endl;
613 // if ( res.size() ) std::cerr <<"first intersec: " << res[0] << std::endl;
614 if(res.size() == 2)
615 {
616 // std::cerr << res[ 1 ] << std::endl;
617 if( (r == 2) && (res[1] - 1.0 > -DCTP_EPS) )
618 r = 1;
619 }
620 switch(r) {
621 case 1:
622 {
623 DCTPVec3dvector &cp = bc.getControlPointVector();
624 Vec2d cpeucl;
625 cpeucl[0] = cp[cp.size() - 1][0] / cp[cp.size() - 1][2];
626 cpeucl[1] = cp[cp.size() - 1][1] / cp[cp.size() - 1][2];
627 //std::cerr << "cp.size(): " << cp.size() << std::endl;
628 //std::cerr << "cp[0]: " << cp[ 0 ] << "cp[1]: " << cp[ 1] << std::endl;
629 Vec3d cp3d(ROUND_EPS * floor(cpeucl[0] / ROUND_EPS + 0.5),
630 ROUND_EPS * floor(cpeucl[1] / ROUND_EPS + 0.5) );
631 // Vec3d cp3d( cp[ cp.size( ) - 1 ][0], cp[ cp.size( ) - 1 ][1] );
632 // v = mesh->SplitEdge( *i, cp3d );
633 v = mesh->findVertex(cp3d);
634 if(v == NULL)
635 {
636 v = new DCTPVertex;
637 v->coords = cp3d;
638 v->faces = (*i)->faces;
639 v->edges.push_back(*i);
640 // std::cerr << "3-" << *i << " " << v << std::endl;
641 }
642 // std::cerr << "el.push_back 2 " << ( void* ) v << std::endl;
643 el.push_back(v);
644 feu = true;
645 return true;
646 }
647 case 2:
648 {
649 bezier2dvector nc; //new curves
650
651 // std::cerr << "res.size(): " << res.size() << std::endl;
652 // dumpcontrolpoints( bc );
653 // std::cerr << " res[0]: " << res[ 0 ] << " res[1]: " << res[ 1 ] << std::endl;
654 // std::cerr << " lineseg: " << v1coords << " " << v2coords << std::endl;
655
656 bc.subDivision(res[1], nc);
657 bc = nc[1]; //nc[0] holdz da 2nd part
658 ///// DCTPVec3dvector &cp = bc.getControlPointVector();
659 // if ( cp[ 0 ] == v1coords ) v = v1;
660 // else v = v2;
661 // std::cerr << "cp[0]: " << cp[0] << " v1: " << v1c << " v2: " << v2c << std::endl;
662 //FIXME:direct orig edge into v
663 DCTPVec3dvector &cp2 =
664 nc[0].getControlPointVector();
665 Vec2d cpeucl;
666 cpeucl[0] = cp2[0][0] / cp2[0][2];
667 cpeucl[1] = cp2[0][1] / cp2[0][2];
668
669 if(DCTPVecIsEqual(cpeucl, v1coords) )
670 v = v2;
671 else
672 v = v1;
673 // std::cerr << "el.push_back 3 " << ( void* ) v << std::endl;
674 el.push_back(v);
675 // Vec3d cp203d( cp2[ 0 ][0], cp2[ 0 ][1] );
676 /* if ( mesh->directEdge( cp203d, v->coords ) ) {
677 std::cerr << "directEdge ERROR!" << std::endl;
678 throw ParSpaceTrimmerError( ParSpaceTrimmerError::ERR_DIRECTEDGE );
679 }*/
680 feu = false;
681 return true;
682 }
683 }
684 }
685
686 return false;
687 }
688
689 bool ParSpaceTrimmer::goingOutOnEdge2(Vec2d clAct, Vec2d clNext,
690 DCTPVertex* &v, bool &feu,
691 std::vector<DCTPVertex*> &el)
692 {
693 // bool on_edge = false;
694 // std::cerr <<"goingout in..." << std::endl;
695 std::vector<DCTPEdge *>::iterator eend = state.v->edges.end();
696
697 for(std::vector<DCTPEdge *>::iterator i = state.v->edges.begin();
698 i != eend; ++i)
699 {
700 if( (*i)->faces.size() != 0)
701 {
702 DCTPVertex *v1,*v2;
703 (*i)->getVertices(v1, v2);
704 double res;
705 // std::cerr << "goin'outonedge calling intersection and houston ;)" << std::endl;
706 // dumpcontrolpoints( bc );
707 // std::cerr << "v1: " << v1->coords << " v2: " << v2->coords << std::endl;
708 Vec2d v1coords(v1->coords[0], v1->coords[1]);
709 Vec2d v2coords(v2->coords[0], v2->coords[1]);
710
711 if(DCTPVecIsEqual(clAct, clNext) )
712 throw ParSpaceTrimmerError(ERR_DEGENERATE_BEZIER);
713
714 if(doIntersect(clAct, clNext, v1coords, v2coords, res) )
715 {
716 if(res - 1.0 > DCTP_EPS)
717 {
718 Vec3d cp3d(clNext[0], clNext[1]);
719 v = mesh->SplitEdge(*i, cp3d);
720 if(v == NULL)
721 {
722 std::cerr << "SplitEdge Failed!" << std::endl;
723 // FIXME: operator<< deprecated
724 // std::cerr << v1coords << cp3d << v2coords << std::endl;
725 }
726 else
727 {
728 // el.push_back( v );
729 feu = true;
730 return true;
731 }
732 }
733 else if(res - 1.0 < -DCTP_EPS)
734 {
735 Vec3d cp3p = Vec3d(clAct + (clNext - clAct) * res);
736 if( (cp3p - Vec3d(v1coords)).squareLength() <
737 (cp3p - Vec3d(v2coords)).squareLength() )
738 v = v1;
739 else
740 v = v2;
741 // el.push_back( v );
742 feu = (DCTPVecIsEqual(cp3p, Vec3d(clNext) ) );
743 ip = res;
744 return true;
745 }
746 else
747 {
748 Vec3d cp3d(clNext[0], clNext[1]);
749 if( (cp3d - Vec3d(v1coords)).squareLength() <
750 (cp3d - Vec3d(v2coords)).squareLength() )
751 v = v1;
752 else
753 v = v2;
754 // el.push_back( v );
755 feu = true;
756 return true;
757 }
758 }
759 }
760 }
761
762 // std::cerr << "going out..." << std::endl;
763 return false;
764 }
765
766 DCTPFace* ParSpaceTrimmer::getContinuingFace(BezierCurve2D &bc)
767 {
768 //state.v shulda hold the vertex to investigate
769 int err;
770 double high = 1.0, low = 0.0;
771 // std::cerr <<" computing stuph.." << std::endl;
772 const Vec3d &cp0hom = bc.getControlPointVector()[0];
773 Vec2d cp0;
774 cp0[0] = cp0hom[0] / cp0hom[2];
775 cp0[1] = cp0hom[1] / cp0hom[2];
776
777 Vec2d p = bc.computewdeCasteljau(high, err);
778 if(p[0] < m_clMin[0])
779 p[0] = m_clMin[0];
780 else if(p[0] > m_clMax[0])
781 p[0] = m_clMax[0];
782 if(p[1] < m_clMin[1])
783 p[1] = m_clMin[1];
784 else if(p[1] > m_clMax[1])
785 p[1] = m_clMax[1];
786 while(high - low > DCTP_EPS)
787 {
788 // std::cerr << ".";
789 // const double mid = ( high + low ) * 0.5;
790 double mid = 1 * DCTP_EPS / sqrt( (p - cp0).squareLength() );
791 mid = osgMin(0.9, osgMax(0.1, mid) );
792 mid = low + (high - low) * mid;
793 Vec2d ptmp = bc.computewdeCasteljau(mid, err);
794 if(ptmp[0] < m_clMin[0])
795 ptmp[0] = m_clMin[0];
796 else if(ptmp[0] > m_clMax[0])
797 ptmp[0] = m_clMax[0];
798 if(ptmp[1] < m_clMin[1])
799 ptmp[1] = m_clMin[1];
800 else if(ptmp[1] > m_clMax[1])
801 ptmp[1] = m_clMax[1];
802 if(DCTPVecIsEqual(cp0, ptmp) )
803 {
804 if(DCTPVecIsEqual(p, ptmp) )
805 {
806 break;
807 }
808 low = mid;
809 }
810 else
811 {
812 high = mid;
813 p = ptmp;
814 }
815 }
816 // std::cerr << std::endl;
817 // std::cerr << cp0 << state.v->coords << p << std::endl;
818 // std::cerr << " computed stuph: " << k << std::endl;
819 /// dumpcontrolpoints( bc );
820 std::vector<DCTPFace *>::iterator fe = state.v->faces.end(); //faces end
821 std::vector<DCTPFace *>::iterator i;
822
823 // std::cerr <<" state.v->faces.size(): " << state.v->faces.size() << std::endl;
824 for(i = state.v->faces.begin(); i != fe; ++i)
825 {
826 if(isOverFace(*i, p) )
827 return *i;
828 }
829
830 for(i = state.v->faces.begin(); i != fe; ++i)
831 {
832 if(isNearQuad(*i, p) )
833 return *i;
834 }
835
836 // nothing found, so we do a global serach
837 getStartingFace(p);
838 return state.f;
839 }
840
841 DCTPFace* ParSpaceTrimmer::getContinuingFace2(Vec2d clAct, Vec2d clNext)
842 {
843 //state.v shulda hold the vertex to investigate
844 // int err;
845 // double high = 1.0, low = 0.0;
846 // std::cerr <<" computing stuph.." << std::endl;
847
848 if(clAct[0] < m_clMin[0])
849 clAct[0] = m_clMin[0];
850 else if(clAct[0] > m_clMax[0])
851 clAct[0] = m_clMax[0];
852 if(clAct[1] < m_clMin[1])
853 clAct[1] = m_clMin[1];
854 else if(clAct[1] > m_clMax[1])
855 clAct[1] = m_clMax[1];
856 if(clNext[0] < m_clMin[0])
857 clNext[0] = m_clMin[0];
858 else if(clNext[0] > m_clMax[0])
859 clNext[0] = m_clMax[0];
860 if(clNext[1] < m_clMin[1])
861 clNext[1] = m_clMin[1];
862 else if(clNext[1] > m_clMax[1])
863 clNext[1] = m_clMax[1];
864
865 /* Vec2d p = clAct + ( clNext - clAct ) * high;
866
867 while( high - low > DCTP_EPS )
868 {
869 const double mid = ( high + low ) * 0.5;
870 const Vec2d ptmp = clAct + ( clNext - clAct ) * mid;
871 if( clAct == ptmp )
872 {
873 low = mid;
874 }
875 else
876 {
877 high = mid;
878 p = ptmp;
879 }
880 }*/
881
882 Vec2d p;
883
884 p = clNext - clAct;
885 if(osgAbs(p[0]) > DCTP_EPS)
886 {
887 p[0] = DCTP_EPS * p[0] / osgAbs(p[0]);
888 }
889 if(osgAbs(p[1]) > DCTP_EPS)
890 {
891 p[1] = DCTP_EPS * p[1] / osgAbs(p[1]);
892 }
893 p += clAct;
894
895 // std::cerr << " computed stuph: " << k << std::endl;
896 /// dumpcontrolpoints( bc );
897 std::vector<DCTPFace *>::iterator fe = state.v->faces.end(); //faces end
898
899 // std::cerr << clAct << p << clNext << std::endl;
900 // std::cerr <<" state.v: " << state.v->coords << " " << state.v->faces.size() << std::endl;
901 for(std::vector<DCTPFace *>::iterator i = state.v->faces.begin();
902 i != fe; ++i)
903 {
904 /* std::cerr << "isoverface: " << (*i)->orig_quad[0]->coords << " "
905 << (*i)->orig_quad[1]->coords << " "
906 << (*i)->orig_quad[2]->coords << " "
907 << (*i)->orig_quad[3]->coords << std::endl;*/
908 if(isOverFace(*i, p) )
909 return *i;
910 }
911
912 // nothing found, so we do a global serach
913 getStartingFace(p);
914 return state.f;
915 }
916
917 bool ParSpaceTrimmer::StateTransition(BezierCurve2D &b, std::vector<DCTPVertex*> &el)
918 {
919 if(state.state == TrimState::OVER_FACE)
920 {
921 #ifdef OSG_ADAPTIVE_QUAD_TREE
922 if(state.f->norm < DCTP_EPS)
923 {
924 while(m_pclQuadTree->computeApproximationError(state.f) > m_pclQuadTree->error_epsilon)
925 {
926 // std::cerr << "subdivide ";
927 // state.f->dump_triangle( );
928 // std::cerr << "subdividing face " << ( void* ) state.f << " because of error " << m_pclQuadTree->computeApproximationError( state.f ) << std::endl;
929 mesh->SubdivideQuad(state.f);
930 m_pclQuadTree->finishSubdivisions(state.f);
931 const Vec3d &cp0hom = b.getControlPointVector()[0];
932 Vec2d cp0;
933 cp0[0] = cp0hom[0] / cp0hom[2];
934 cp0[1] = cp0hom[1] / cp0hom[2];
935
936 if(!isOverFace(state.f, cp0) )
937 {
938 if(isOverFace(mesh->faces[mesh->faces.size() - 3], cp0) )
939 {
940 state.f = mesh->faces[mesh->faces.size() - 3];
941 }
942 else if(isOverFace(mesh->faces[mesh->faces.size() - 2], cp0) )
943 {
944 state.f = mesh->faces[mesh->faces.size() - 2];
945 }
946 else
947 {
948 state.f = mesh->faces[mesh->faces.size() - 1];
949 }
950 }
951 }
952 state.f->norm = m_pclQuadTree->error_epsilon / m_pclQuadTree->computeBilinearNorm(state.f);
953 // std::cerr << state.f->norm << std::endl;
954 }
955 #endif
956 // std::cerr << " now over face..." << std::endl;
957 //note: setMinIntersection... sets ie & ip member varz
958 if(setMinIntersectionWithFace(b) ) //intersection exists
959 {
960 int err;
961 Vec3d p = Vec3d(b.computewdeCasteljau(ip, err) );
962 // std::cerr << " ip: " << ip << " p: " << p << std::endl;
963 // DCTPVertex *vp = mesh->SplitEdge( ie, p );
964 DCTPVertex *vp = mesh->findVertex(p);
965 if(vp == NULL)
966 {
967 vp = new DCTPVertex;
968 vp->coords = p;
969 vp->faces = ie->faces;
970 vp->edges.push_back(ie);
971 /* std::cerr << "5-" << ie << " " << vp << std::endl;
972 if( ( ( unsigned int ) vp ) == 0x2ec94840 )
973 {
974 std::cerr << p << std::endl;
975 }*/
976 }
977 if(!vp)
978 {
979 std::cerr << "Brutal error I. in: "
980 << "ParSpaceTrimmer::StateTransition"
981 << std::endl;
982 throw ParSpaceTrimmerError(ERR_STATETRANSITION_I);
983 }
984 vp->vertexinfo = reinterpret_cast<void*>(1);
985 state.state = TrimState::IN_VERTEX;
986 state.v = vp;
987 return StoreCurveApproximation(b, ip, el);
988 // el.push_back( vp );
989 }
990 //no intersection
991 /// std::cerr << " no intersection, baby !!! " << std::endl;
992 return StoreCurveApproximation(b, 1.0, el);
993 }
994 else //TrimState::IN_VERTEX state
995 {
996 #ifdef OSG_ADAPTIVE_QUAD_TREE
997 bool b_sub = true;
998 Vec2d cl_v2d;
999 bool b_dummy;
1000 DCTPVertex *pcl_find;
1001
1002 cl_v2d[0] = state.v->coords[0];
1003 cl_v2d[1] = state.v->coords[1];
1004
1005 while(b_sub)
1006 {
1007 b_sub = false;
1008
1009 for(unsigned int ui_face = 0; ui_face < state.v->faces.size(); ++ui_face)
1010 {
1011 DCTPFace *pcl_face = state.v->faces[ui_face];
1012 if(pcl_face->norm < DCTP_EPS)
1013 {
1014 if(m_pclQuadTree->computeApproximationError(pcl_face) > m_pclQuadTree->error_epsilon)
1015 {
1016 // std::cerr << "subdivide ";
1017 // pcl_face->dump_triangle( );
1018 // std::cerr << "subdividing face " << ( void* ) pcl_face << " because of error " << m_pclQuadTree->computeApproximationError( pcl_face ) << std::endl;
1019 mesh->SubdivideQuad(pcl_face);
1020 m_pclQuadTree->finishSubdivisions(pcl_face);
1021 b_sub = true;
1022 if(state.v->edges.size() <= 1)
1023 {
1024 pcl_find = mesh->findVertex(state.v->coords);
1025 if(pcl_find)
1026 {
1027 // std::cerr << "delete vertex1:" << ( void* ) state.v << std::endl;
1028 // delete state.v;
1029 // std::cerr << pcl_find->edges.size( ) << std::endl;
1030 state.v = pcl_find;
1031 }
1032 else
1033 {
1034 // update state.v->faces and state.v->edges
1035 if(!isNearQuad(pcl_face, cl_v2d) )
1036 {
1037 state.v->faces[ui_face] = state.v->faces[state.v->faces.size() - 1];
1038 state.v->faces.pop_back();
1039 --ui_face;
1040 }
1041 else
1042 {
1043 state.v->edges[0] = static_cast<DCTPEdge*>(
1044 isOnFaceBoundary(state.v->faces[ui_face], cl_v2d, b_dummy));
1045 }
1046 if(isNearQuad(mesh->faces[mesh->faces.size() - 3], cl_v2d) )
1047 {
1048 state.v->faces.push_back(mesh->faces[mesh->faces.size() - 3]);
1049 state.v->edges[0] = static_cast<DCTPEdge*>(
1050 isOnFaceBoundary(mesh->faces[mesh->faces.size() - 3], cl_v2d, b_dummy));
1051 }
1052 if(isNearQuad(mesh->faces[mesh->faces.size() - 2], cl_v2d) )
1053 {
1054 state.v->faces.push_back(mesh->faces[mesh->faces.size() - 2]);
1055 state.v->edges[0] = static_cast<DCTPEdge*>(
1056 isOnFaceBoundary(mesh->faces[mesh->faces.size() - 2], cl_v2d, b_dummy));
1057 }
1058 if(isNearQuad(mesh->faces[mesh->faces.size() - 1], cl_v2d) )
1059 {
1060 state.v->faces.push_back(mesh->faces[mesh->faces.size() - 1]);
1061 state.v->edges[0] = static_cast<DCTPEdge*>(
1062 isOnFaceBoundary(mesh->faces[mesh->faces.size() - 1], cl_v2d, b_dummy));
1063 }
1064 }
1065 }
1066 }
1067 else
1068 {
1069 pcl_face->norm = m_pclQuadTree->error_epsilon / m_pclQuadTree->computeBilinearNorm(pcl_face);
1070 // std::cerr << ( void* ) pcl_face << ":" << pcl_face->norm << std::endl;
1071 }
1072 }
1073 }
1074 }
1075 #endif
1076 // std::cerr << " now in vertex..." << std::endl;
1077 //snap startin' control point of outgoin' curve into startin' vertex
1078 DCTPVec3dvector &cp = b.getControlPointVector();
1079 cp[0][0] = state.v->coords[0] * cp[0][2];
1080 cp[0][1] = state.v->coords[1] * cp[0][2];
1081 bool feu; //full edge used
1082 DCTPVertex *v;
1083 unsigned int check;
1084
1085 for(check = 1; check < cp.size(); ++check)
1086 {
1087 if(DCTPVecIsNotEqual(cp[check], cp[0]) )
1088 {
1089 break;
1090 }
1091 }
1092
1093 if(check == cp.size() )
1094 {
1095 return false;
1096 }
1097 // if ( cp.size() == 2 && cp[ 0 ] == cp[ 1 ] )
1098 // return false;
1099 if(goingOutOnEdge(b, v, feu, el) ) //goin' out on edge
1100 { //IN_VERTEX state remains, but...
1101 state.v = v;
1102 //insert edge in edgeloop
1103 // std::cerr << "inserting vertex in edge loop " << state.v->coords << std::endl;
1104 // std::cerr << "el.push_back 4 " << ( void* ) v << std::endl;
1105 // el.push_back( v );
1106 // v->vertexinfo = ( void* ) 1;
1107 if(feu)
1108 return false; //no part of curve remains
1109 return true; //the opposite
1110 }
1111 DCTPFace *f = getContinuingFace(b); //get face curve is above
1112 if(!f)
1113 {
1114 std::cerr << "Brutal error II. in: "
1115 << "ParSpaceTrimmer::StateTransition" << std::endl;
1116 throw ParSpaceTrimmerError(ERR_STATETRANSITION_II);
1117 }
1118 // TrimSegment tsg;
1119 // tsg.start = state.v;
1120 // f->trimseg.push_back( tsg );
1121 //OK - now we can pretend to be in OVER_FACE
1122 state.f = f;
1123 state.state = TrimState::OVER_FACE;
1124 return true; //all of the curve remains
1125 }
1126 }
1127
1128 #ifdef OSG_FORCE_NO_T_VERTICES
1129 // #ifdef OSG_CREATE_NORMAL_MAPS
1130 bool ParSpaceTrimmer::StateTransition2(Vec2d &rclAct, Vec2d clNext, std::vector<DCTPVertex*> &el, Vec3d &rclActS, Vec3d clNextS)
1131 /* #else
1132 bool ParSpaceTrimmer::StateTransition2( Vec2d &rclAct, Vec2d clNext, std::vector< DCTPVertex* > &el, Vec3d &rclActS, Vec3d clNextS, Vec3d &rclActN, Vec3d clNextN )
1133 #endif*/
1134 #else
1135 bool ParSpaceTrimmer::StateTransition2(Vec2d &rclAct, Vec2d clNext, std::vector<DCTPVertex*> &el, Vec3d &rclActS, Vec3d clNextS)
1136 #endif
1137 {
1138 if( (rclAct - clNext).squareLength() < DCTP_EPS)
1139 return false;
1140
1141 // std::cerr << rclAct << " -> " << clNext << std::endl;
1142 // std::cerr << rclActS << " -> " << clNextS << std::endl;
1143
1144 if(state.state == TrimState::OVER_FACE)
1145 {
1146 // std::cerr << " now over face..." << std::endl;
1147 //note: setMinIntersection... sets ie & ip member varz
1148 if(setMinIntersectionWithFace2(rclAct, clNext) )
1149 { //intersection exists
1150 // int err;
1151 Vec3d p = Vec3d(rclAct + (clNext - rclAct) * ip);
1152 // std::cerr << " ip: " << ip << " p: " << p << std::endl;
1153 DCTPVertex *vp = mesh->SplitEdge(ie, p);
1154 // std::cerr << vp->coords << std::endl;
1155 if(vp == NULL)
1156 {
1157 // FIXME: operator<< deprecated
1158 // std::cerr << rclAct << " -> " << clNext << std::endl;
1159 // DCTPVertex *v1, *v2;
1160 // ie->getVertices( v1, v2 );
1161 // std::cerr << v1->coords << " -> " << v2->coords << std::endl;
1162 // std::cerr << " ip: " << ip << " p: " << p << std::endl;
1163 std::cerr << "Brutal error I. in: "
1164 << "ParSpaceTrimmer::StateTransition2"
1165 << std::endl;
1166 // exit( -1 );
1167 throw ParSpaceTrimmerError(ERR_STATETRANSITION_I);
1168 }
1169 rclActS = rclActS + (clNextS - rclActS) * ip;
1170 if(vp->vertexinfo == NULL)
1171 {
1172 #ifdef OSG_FORCE_NO_T_VERTICES
1173 SPosNorm *pt_s = new SPosNorm;
1174 SPosNorm *pt_ps = ( SPosNorm* ) el[el.size() - 1]->vertexinfo;
1175
1176 if( (rclActS - clNextS).squareLength() <= (rclActS - pt_ps->clPos).squareLength() )
1177 {
1178 pt_s->clPos = clNextS;
1179 /* #ifndef OSG_CREATE_NORMAL_MAPS
1180 pt_s->clNorm = clNextN;
1181 #endif*/
1182 #ifdef OSG_KEEP_2D_POINTS
1183 pt_s->uiNum = m_uiPosCnt;
1184 #endif
1185 }
1186 else
1187 {
1188 pt_s->clPos = pt_ps->clPos;
1189 /* #ifndef OSG_CREATE_NORMAL_MAPS
1190 pt_s->clNorm = pt_ps->clNorm;
1191 #endif*/
1192 #ifdef OSG_KEEP_2D_POINTS
1193 pt_s->uiNum = pt_ps->uiNum;
1194 #endif
1195 }
1196 vp->vertexinfo = ( void* ) pt_s;
1197 #else
1198 Vec3d *pcl_s = new Vec3d(rclActS);
1199 vp->vertexinfo = static_cast<void*>(pcl_s);
1200 #endif
1201 }
1202 state.state = TrimState::IN_VERTEX;
1203 state.v = vp;
1204 // if( Vec3d( rclAct ) != vp->coords )
1205 {
1206 mesh->AddEdge(el[el.size() - 1], vp, 1);
1207 // std::cerr << "add edge: " << el[ el.size( ) - 1 ]->coords << "->" << vp->coords << std::endl;
1208 // std::cerr << vp->vertexinfo << std::endl;
1209 el.push_back(vp);
1210 }
1211 rclAct[0] = vp->coords[0];
1212 rclAct[1] = vp->coords[1];
1213 // std::cerr << "rclAct:" << rclAct << std::endl;
1214 // std::cerr << "ip:" << ip << std::endl;
1215 // std::cerr << "rclAct == clNext " << ( rclAct == clNext ) << std::endl;
1216 return !(DCTPVecIsEqual(rclAct, clNext) );
1217 }
1218 //no intersection
1219 // std::cerr << " no intersection, baby !!! " << std::endl;
1220 DCTPVertex *v = mesh->AddVertex(Vec3d(clNext));
1221 if(v->vertexinfo == NULL)
1222 {
1223 #ifdef OSG_FORCE_NO_T_VERTICES
1224 SPosNorm *pt_s = new SPosNorm;
1225 pt_s->clPos = clNextS;
1226 /* #ifndef OSG_CREATE_NORMAL_MAPS
1227 pt_s->clNorm = clNextN;
1228 #endif*/
1229 #ifdef OSG_KEEP_2D_POINTS
1230 pt_s->uiNum = m_uiPosCnt;
1231 #endif
1232 v->vertexinfo = ( void* ) pt_s;
1233 #else
1234 Vec3d *pcl_s = new Vec3d(clNextS);
1235 v->vertexinfo = static_cast<void*>(pcl_s);
1236 #endif
1237 }
1238 mesh->AddEdge(el[el.size() - 1], v, 1);
1239 // std::cerr << "add edge: " << el[ el.size( ) - 1 ]->coords << "->" << v->coords << std::endl;
1240 // std::cerr << v->vertexinfo << std::endl;
1241 el.push_back(v);
1242 // std::cerr << "clNext:" << clNext << std::endl;
1243 return false;
1244 }
1245 else
1246 {
1247 //TrimState::IN_VERTEX state
1248 // std::cerr << " now in vertex..." << std::endl;
1249 bool feu; //full edge used
1250 DCTPVertex *v;
1251 if(DCTPVecIsEqual(rclAct, clNext) )
1252 return false;
1253 if(goingOutOnEdge2(rclAct, clNext, v, feu, el) )
1254 { //goin' out on edge
1255 //IN_VERTEX state remains, but...
1256 if(feu)
1257 {
1258 rclActS = clNextS;
1259 }
1260 else
1261 {
1262 rclActS = rclActS + (clNextS - rclActS) * ip;
1263 }
1264 if(v->vertexinfo == NULL)
1265 {
1266 #ifdef OSG_FORCE_NO_T_VERTICES
1267 SPosNorm *pt_s = new SPosNorm;
1268 SPosNorm *pt_ps = ( SPosNorm* ) el[el.size() - 1]->vertexinfo;
1269
1270 if( (rclActS - clNextS).squareLength() <= (rclActS - pt_ps->clPos).squareLength() )
1271 {
1272 pt_s->clPos = clNextS;
1273 /* #ifndef OSG_CREATE_NORMAL_MAPS
1274 pt_s->clNorm = clNextN;
1275 #endif*/
1276 #ifdef OSG_KEEP_2D_POINTS
1277 pt_s->uiNum = m_uiPosCnt;
1278 #endif
1279 }
1280 else
1281 {
1282 pt_s->clPos = pt_ps->clPos;
1283 /* #ifndef OSG_CREATE_NORMAL_MAPS
1284 pt_s->clNorm = pt_ps->clNorm;
1285 #endif*/
1286 #ifdef OSG_KEEP_2D_POINTS
1287 pt_s->uiNum = pt_ps->uiNum;
1288 #endif
1289 }
1290 v->vertexinfo = ( void* ) pt_s;
1291 #else
1292 Vec3d *pcl_s = new Vec3d(rclActS);
1293 v->vertexinfo = static_cast<void*>(pcl_s);
1294 #endif
1295 }
1296 state.v = v;
1297 //insert edge in edgeloop
1298 // std::cerr << "inserting vertex in edge loop " << state.v->coords << std::endl;
1299 // if( Vec3d( rclAct ) != v->coords )
1300 {
1301 // std::cerr << "direct edge: " << el[ el.size( ) - 1 ]->coords << "->" << v->coords << std::endl;
1302 mesh->directEdge(el[el.size() - 1]->coords, v->coords);
1303 // std::cerr << v->vertexinfo << std::endl;
1304 el.push_back(v);
1305 }
1306 rclAct[0] = v->coords[0];
1307 rclAct[1] = v->coords[1];
1308 // std::cerr << "rclAct:" << rclAct << std::endl;
1309 return (!feu);
1310 }
1311 DCTPFace *f = getContinuingFace2(rclAct, clNext); //get face curve is above
1312 if(f == NULL)
1313 {
1314 std::cerr << "Brutal error II. in: "
1315 << "ParSpaceTrimmer::StateTransition2" << std::endl;
1316 exit(-1);
1317 throw ParSpaceTrimmerError(ERR_STATETRANSITION_II);
1318 }
1319 //OK - now we can pretend to be in OVER_FACE
1320 state.f = f;
1321 state.state = TrimState::OVER_FACE;
1322 return true; //all of the curve remains
1323 }
1324 }
1325
1326 /*void ParSpaceTrimmer::mergeCurve( void ) {
1327 if ( !start_face ) return;
1328 /// std::cerr << "got startface " << std::endl;
1329 std::vector<TrimSegment>::iterator s = NULL, e = NULL;
1330 for( std::vector<TrimSegment>::iterator i = start_face->trimseg.begin();
1331 i != start_face->trimseg.end(); ++i ) {
1332 if ( !i->start ) { s = i; } //std::cerr << "ParSpaceTrimmer::mergeCurve start found: " << std::endl; }
1333 if ( !i->end ) { e = i; } //std::cerr << "ParSpaceTrimmer::mergeCurve end found: " << std::endl; }
1334 }
1335 /// if ( e == s ) std::cerr <<" basszajba, GECZI !!! " << std::endl;
1336 if ( e == NULL ) throw ParSpaceTrimmerError( ParSpaceTrimmerError::ERR_NO_MERGECURVE_START );
1337 if ( s == NULL ) throw ParSpaceTrimmerError( ParSpaceTrimmerError::ERR_NO_MERGECURVE_END );
1338 e->end = s->end;
1339 // std::cerr << "e->trimbeziers.size: " << e->trimbeziers.size() << " s->trimbeziers.size(): " << s->trimbeziers.size() << std::endl;
1340 e->trimbeziers.insert( e->trimbeziers.end(), s->trimbeziers.begin(),
1341 s->trimbeziers.end() );
1342 start_face->trimseg.erase( s );
1343 }*/
1344
1345 void ParSpaceTrimmer::processCurve(bezier2ddeque &tc, std::vector<DCTPVertex*> &el)
1346 {
1347
1348 while(!tc.empty() )
1349 {
1350 BezierCurve2D bc = tc.front();
1351 tc.pop_front();
1352 if(StateTransition(bc, el) )
1353 tc.push_front(bc);
1354 }
1355 }
1356
1357 void ParSpaceTrimmer::processCurve2(unsigned int uiLoop, std::vector<DCTPVertex*> &el)
1358 {
1359 const unsigned int cui_size = UInt32((*pvccrd)[uiLoop].size());
1360 Vec2d cl_act = (*pvccrd)[uiLoop][cui_size - 1];
1361 Vec3d cl_act_s = (*m_pvvclSewed)[uiLoop][cui_size - 1];
1362 #ifdef OSG_FORCE_NO_T_VERTICES
1363 /* #ifndef OSG_CREATE_NORMAL_MAPS
1364 Vec3d cl_act_n = ( *m_pvvclNormals )[ uiLoop ][ cui_size - 1 ];
1365 #endif*/
1366 #endif
1367 unsigned int ui_vertex = 0;
1368 Vec2d cl_next;
1369
1370 // std::cerr.precision( 16 );
1371 // std::cerr << " - " << cl_act << std::endl;
1372
1373 while(ui_vertex < cui_size)
1374 {
1375 cl_next = (*pvccrd)[uiLoop][ui_vertex];
1376 /* if( cl_next[0] < m_clMin[0] ) cl_next[0] = m_clMin[0];
1377 else if( cl_next[0] > m_clMax[0] ) cl_next[0] = m_clMax[0];
1378 if( cl_next[1] < m_clMin[1] ) cl_next[1] = m_clMin[1];
1379 else if( cl_next[1] > m_clMax[1] ) cl_next[1] = m_clMax[1];*/
1380 // std::cerr << cl_act << " -> " << cl_next << std::endl;
1381 #ifdef OSG_FORCE_NO_T_VERTICES
1382 // #ifdef OSG_CREATE_NORMAL_MAPS
1383 if(!StateTransition2(cl_act, cl_next, el,
1384 cl_act_s, (*m_pvvclSewed)[uiLoop][ui_vertex]) )
1385 /* #else
1386 if( !StateTransition2( cl_act, cl_next, el,
1387 cl_act_s, ( *m_pvvclSewed )[ uiLoop ][ ui_vertex ],
1388 cl_act_n, ( *m_pvvclNormals )[ uiLoop ][ ui_vertex ] ) )
1389 #endif*/
1390 #else
1391 if(!StateTransition2(cl_act, cl_next, el,
1392 cl_act_s, (*m_pvvclSewed)[uiLoop][ui_vertex]) )
1393 #endif
1394 {
1395 cl_act = (*pvccrd)[uiLoop][ui_vertex];
1396 cl_act_s = (*m_pvvclSewed)[uiLoop][ui_vertex];
1397 #ifdef OSG_FORCE_NO_T_VERTICES
1398 /* #ifndef OSG_CREATE_NORMAL_MAPS
1399 cl_act_n = ( *m_pvvclNormals )[ uiLoop ][ ui_vertex ];
1400 #endif*/
1401 #ifdef OSG_KEEP_2D_POINTS
1402 ++m_uiPosCnt;
1403 #endif
1404 #endif
1405 ++ui_vertex;
1406 // std::cerr << " - " << cl_act << std::endl;
1407 }
1408 }
1409 }
1410
1411 int ParSpaceTrimmer::PerformTrimming(void)
1412 {
1413 if(tcs3d == NULL)
1414 {
1415 // no 3d trimming curves :-(
1416 #ifdef OSG_USE_SIMPLIFIER
1417 m_pclQuadTree->error_epsilon *= OSG_SIMPLIFIER_TESS_ERR;
1418 terr = m_pclQuadTree->error_epsilon * 3;
1419 #endif
1420 // std::cerr << std::endl;
1421 bezier2ddequevector::iterator tcs_end = tcs->end();
1422 vcel.resize(tcs->size() );
1423 // std::cerr << tcs->size( ) << " trimming loops" << std::endl;
1424 unsigned int i = 0;
1425
1426 for(bezier2ddequevector::iterator bcq = tcs->begin(); bcq != tcs_end; ++bcq)
1427 {
1428 if(!(*bcq).empty() )
1429 {
1430 vcel[i].clear();
1431 initializeStartState(*bcq);
1432 processCurve(*bcq, vcel[i]);
1433 // mergeCurve();
1434 ++i;
1435 }
1436 }
1437
1438 if(i != vcel.size() )
1439 {
1440 vcel.resize(i);
1441 }
1442 // std::cerr << "vcel.size()::: " << vcel.size( );
1443 }
1444 else
1445 {
1446 // ok, we have 3d trimming curves :-)
1447 std::vector<double> params;
1448
1449 #ifdef OSG_USE_SIMPLIFIER
1450 terr *= OSG_SIMPLIFIER_TESS_ERR;
1451 #endif
1452 // bezier2ddequevector::iterator tcs_end = tcs->end();
1453 vcel.resize(tcs->size() );
1454 // std::cerr << tcs->size( ) << " trimming loops" << std::endl;
1455 unsigned int i = 0;
1456 int err;
1457 const unsigned int lc = UInt32(tcs->size());
1458
1459 // bezier3ddequevector::iterator bcq3d = tcs3d->begin( );
1460 // bezier2ddequevector::iterator bcq = tcs->begin( );
1461 for(unsigned int l = 0; l < lc; ++l)
1462 {
1463 if(!(*tcs)[l].empty() )
1464 {
1465 vcel[i].clear();
1466 const unsigned int cc = UInt32((*tcs)[l].size());
1467
1468 for(unsigned int c = 0; c < cc; ++c)
1469 {
1470 // std::cerr << ".";
1471 BezierCurve2D &bc = (*tcs)[l][c];
1472 BezierCurve3D bc3d = (*tcs3d)[l][c];
1473 // bc.write( );
1474 // bc3d.write( );
1475 // std::cerr << std::endl;
1476 params.clear();
1477 // MIDPOINT_SUBDIVISION / ARBITRARY_SUBDIVISION, POINT_DISTANCE / LINE_DISTANCE
1478 bc3d.approximate(params, terr, BezierCurve3D::MIDPOINT_SUBDIVISION | BezierCurve3D::LINE_DISTANCE);
1479
1480 // leave out last point since it is the start of the next curve
1481 for(unsigned int j = 0; j < params.size(); ++j)
1482 {
1483 Vec2d cl_pos;
1484
1485 err = 0;
1486 cl_pos = bc.computewdeCasteljau(params[j], err);
1487 cl_pos[0] = DCTP_EPS * 100.0 * floor(cl_pos[0] / (DCTP_EPS * 100.0) + 0.5);
1488 cl_pos[1] = DCTP_EPS * 100.0 * floor(cl_pos[1] / (DCTP_EPS * 100.0) + 0.5);
1489 vcel[i].push_back(mesh->AddVertex(Vec3d(cl_pos)) );
1490 // std::cerr << bc.computewdeCasteljau( params[ j ], err ) << " ";
1491 }
1492
1493 // std::cerr << std::endl;
1494 }
1495
1496 ++i;
1497 }
1498 }
1499
1500 // std::cerr << "x";
1501 if(i != vcel.size() )
1502 {
1503 vcel.resize(i);
1504 }
1505 // std::cerr << "vcel.size()::: " << vcel.size( );
1506 tcs = NULL;
1507 tcs3d = NULL;
1508 }
1509 // check and fix edge loops...
1510 #ifdef OSG_USE_SIMPLIFIER
1511 unsigned int ui_vert_cnt;
1512 unsigned int ui_vert;
1513 int i_err;
1514 const double cd_error_quad = terr * terr
1515 * (1.0 - OSG_SIMPLIFIER_TESS_ERR) * (1.0 - OSG_SIMPLIFIER_TESS_ERR)
1516 / (OSG_SIMPLIFIER_TESS_ERR * OSG_SIMPLIFIER_TESS_ERR);
1517 // const double cd_error_quad = DBL_MAX;
1518 double d_act_dist;
1519 double d_max_dist;
1520 unsigned int ui_new;
1521
1522 std::vector<SPolySimVertex> vt_vertices;
1523 SPolySimVertexSet vt_sim_sort;
1524 unsigned int ui_first;
1525 unsigned int ui_prev;
1526 unsigned int ui_next;
1527 Vec2d cl_uv;
1528 unsigned int ui_remain_cnt;
1529 unsigned int i;
1530 Vec3d cl_midpos;
1531
1532 /* for( i = 0; i < vcel.size( ); ++i )
1533 {
1534 ui_vert_cnt = vcel[ i ].size( );
1535 if( ui_vert_cnt )
1536 {
1537 for( ui_vert = 0; ui_vert < ui_vert_cnt; ++ui_vert )
1538 {
1539 cl_uv[0] = vcel[ i ][ ui_vert ]->coords[0];
1540 cl_uv[1] = vcel[ i ][ ui_vert ]->coords[1];
1541 std::cerr << cl_uv << m_pclNurbs->compute( cl_uv, i_err ) << std::endl;
1542 }
1543 std::cerr << std::endl;
1544 }
1545 }*/
1546
1547 checkEdgeloops();
1548
1549 for(i = 0; i < vcel.size(); ++i)
1550 {
1551 ui_vert_cnt = UInt32(vcel[i].size());
1552 // std::cerr << ui_vert_cnt << " -> ";
1553 if(ui_vert_cnt)
1554 {
1555 vt_vertices.resize(ui_vert_cnt);
1556
1557 for(ui_vert = 0; ui_vert < ui_vert_cnt; ++ui_vert)
1558 {
1559 i_err = 0;
1560 vt_vertices[ui_vert].uiIndex = ui_vert;
1561 vt_vertices[ui_vert].uiPrev = ui_vert - 1;
1562 vt_vertices[ui_vert].uiNext = ui_vert + 1;
1563 cl_uv[0] = vcel[i][ui_vert]->coords[0];
1564 cl_uv[1] = vcel[i][ui_vert]->coords[1];
1565 vt_vertices[ui_vert].clPos = m_pclNurbs->compute(cl_uv, i_err);
1566 if(i_err)
1567 {
1568 std::cerr << " " << i_err << std::endl;
1569 }
1570 }
1571
1572 vt_vertices[0].uiPrev = ui_vert_cnt - 1;
1573 vt_vertices[ui_vert_cnt - 1].uiNext = 0;
1574 vt_sim_sort.clear();
1575
1576 for(ui_vert = 0; ui_vert < ui_vert_cnt; ++ui_vert)
1577 {
1578 cl_uv[0] = (vcel[i][vt_vertices[ui_vert].uiPrev]->coords[0]
1579 + vcel[i][vt_vertices[ui_vert].uiNext]->coords[0]) * 0.5;
1580 cl_uv[1] = (vcel[i][vt_vertices[ui_vert].uiPrev]->coords[1]
1581 + vcel[i][vt_vertices[ui_vert].uiNext]->coords[1]) * 0.5;
1582 cl_midpos = m_pclNurbs->compute(cl_uv, i_err);
1583 vt_vertices[ui_vert].dSimplifyError =
1584 osgMax(DistToEdge(vt_vertices[ui_vert].clPos,
1585 vt_vertices[vt_vertices[ui_vert].uiPrev].clPos,
1586 vt_vertices[vt_vertices[ui_vert].uiNext].clPos),
1587 DistToEdge(cl_midpos,
1588 vt_vertices[vt_vertices[ui_vert].uiPrev].clPos,
1589 vt_vertices[vt_vertices[ui_vert].uiNext].clPos) );
1590 vt_vertices[ui_vert].dSimplifyError +=
1591 sqrt( (vt_vertices[vt_vertices[ui_vert].uiPrev].clPos
1592 - vt_vertices[vt_vertices[ui_vert].uiNext].clPos).squareLength() ) * 0.00001;
1593 if(vt_vertices[ui_vert].dSimplifyError < cd_error_quad)
1594 {
1595 vt_sim_sort.insert(&vt_vertices[ui_vert]);
1596 }
1597 }
1598
1599 ui_first = 0;
1600 ui_remain_cnt = ui_vert_cnt;
1601 while( (!vt_sim_sort.empty() ) && (ui_remain_cnt > 3) )
1602 {
1603 // remove vertex
1604 ui_vert = (*vt_sim_sort.begin() )->uiIndex;
1605 ui_prev = (*vt_sim_sort.begin() )->uiPrev;
1606 ui_next = (*vt_sim_sort.begin() )->uiNext;
1607 // std::cerr << "remove " << ui_vert << " next: " << ui_next << " prev: " << ui_prev << " err: " << sqrt( ( *vt_sim_sort.begin( ) )->dSimplifyError ) << std::endl;
1608 vt_sim_sort.erase(vt_sim_sort.begin() );
1609 vt_vertices[ui_prev].uiNext = ui_next;
1610 vt_vertices[ui_next].uiPrev = ui_prev;
1611 if(ui_vert == ui_first)
1612 {
1613 ui_first = ui_next;
1614 }
1615 if(!mesh->findVertex(vcel[i][ui_vert]->coords) )
1616 {
1617 // std::cerr << "delete vertex4:" << ui_vert << " " << ( void* ) vcel[ i ][ ui_vert ] << std::endl;
1618 delete vcel[i][ui_vert];
1619 vcel[i][ui_vert] = NULL;
1620 }
1621 // remove prev and next from qeue
1622 if(vt_vertices[ui_prev].dSimplifyError < cd_error_quad)
1623 {
1624 vt_sim_sort.erase(&vt_vertices[ui_prev]);
1625 }
1626 if(vt_vertices[ui_next].dSimplifyError < cd_error_quad)
1627 {
1628 vt_sim_sort.erase(&vt_vertices[ui_next]);
1629 }
1630 // compute new errors
1631 if( (ui_vert != ui_prev) && (ui_vert != ui_next) )
1632 {
1633 cl_uv[0] = (vcel[i][vt_vertices[ui_prev].uiPrev]->coords[0]
1634 + vcel[i][ui_next]->coords[0]) * 0.5;
1635 cl_uv[1] = (vcel[i][vt_vertices[ui_prev].uiPrev]->coords[1]
1636 + vcel[i][ui_next]->coords[1]) * 0.5;
1637 cl_midpos = m_pclNurbs->compute(cl_uv, i_err);
1638 d_max_dist = DistToEdge(cl_midpos,
1639 vt_vertices[vt_vertices[ui_vert].uiPrev].clPos,
1640 vt_vertices[ui_next].clPos);
1641
1642 ui_vert = (vt_vertices[ui_prev].uiPrev + 1) % ui_vert_cnt;
1643 while(ui_vert != ui_next)
1644 {
1645 d_act_dist = DistToEdge(vt_vertices[ui_vert].clPos,
1646 vt_vertices[vt_vertices[ui_prev].uiPrev].clPos,
1647 vt_vertices[ui_next].clPos);
1648 if(d_act_dist > d_max_dist)
1649 {
1650 d_max_dist = d_act_dist;
1651 }
1652 ui_vert = (ui_vert + 1) % ui_vert_cnt;
1653 }
1654 vt_vertices[ui_prev].dSimplifyError = d_max_dist;
1655 vt_vertices[ui_prev].dSimplifyError +=
1656 sqrt( (vt_vertices[vt_vertices[ui_prev].uiPrev].clPos
1657 - vt_vertices[vt_vertices[ui_prev].uiNext].clPos).squareLength() ) * 0.00001;
1658 if(vt_vertices[ui_prev].dSimplifyError < cd_error_quad)
1659 {
1660 vt_sim_sort.insert(&vt_vertices[ui_prev]);
1661 }
1662
1663 cl_uv[0] = (vcel[i][ui_prev]->coords[0]
1664 + vcel[i][vt_vertices[ui_next].uiNext]->coords[0]) * 0.5;
1665 cl_uv[1] = (vcel[i][ui_prev]->coords[1]
1666 + vcel[i][vt_vertices[ui_next].uiNext]->coords[1]) * 0.5;
1667 cl_midpos = m_pclNurbs->compute(cl_uv, i_err);
1668 d_max_dist = DistToEdge(cl_midpos,
1669 vt_vertices[ui_prev].clPos,
1670 vt_vertices[vt_vertices[ui_next].uiNext].clPos);
1671
1672 ui_vert = (ui_prev + 1) % ui_vert_cnt;
1673 while(ui_vert != vt_vertices[ui_next].uiNext)
1674 {
1675 d_act_dist = DistToEdge(vt_vertices[ui_vert].clPos,
1676 vt_vertices[ui_prev].clPos,
1677 vt_vertices[vt_vertices[ui_next].uiNext].clPos);
1678 if(d_act_dist > d_max_dist)
1679 {
1680 d_max_dist = d_act_dist;
1681 }
1682 ui_vert = (ui_vert + 1) % ui_vert_cnt;
1683 }
1684 vt_vertices[ui_next].dSimplifyError = d_max_dist;
1685 vt_vertices[ui_next].dSimplifyError +=
1686 sqrt( (vt_vertices[vt_vertices[ui_next].uiPrev].clPos
1687 - vt_vertices[vt_vertices[ui_next].uiNext].clPos).squareLength() ) * 0.00001;
1688 if(vt_vertices[ui_next].dSimplifyError < cd_error_quad)
1689 {
1690 vt_sim_sort.insert(&vt_vertices[ui_next]);
1691 }
1692 }
1693 --ui_remain_cnt;
1694 }
1695
1696 // setup new loop
1697 vcel[i][0] = vcel[i][ui_first];
1698 ui_new = 1;
1699
1700 for(ui_vert = vt_vertices[ui_first].uiNext; ui_vert != ui_first; ui_vert = vt_vertices[ui_vert].uiNext)
1701 {
1702 vcel[i][ui_new] = vcel[i][ui_vert];
1703 ++ui_new;
1704 }
1705
1706 vcel[i].resize(ui_new);
1707 // std::cerr << "simplified " << ui_vert_cnt << " to " << ui_new << std::endl;
1708 }
1709
1710 // std::cerr << vcel[ i ].size( ) << std::endl;
1711 }
1712
1713 // vpcl_new.clear( );
1714
1715 vt_vertices.clear();
1716 vt_sim_sort.clear();
1717 #endif
1718 checkEdgeloops();
1719 // std::cerr << " -> " << vcel.size( ) << std::endl;
1720
1721 // copy edge loops in array
1722 pvccrd->resize(vcel.size() );
1723
1724 for(unsigned int loop = 0; loop < vcel.size(); ++loop)
1725 {
1726 unsigned int v, /*eid,*/ oid;
1727 unsigned int nid = vcel[loop][vcel[loop].size() - 1]->id;
1728 Vec2d cl_temp_vec;
1729
1730 for(v = 0; v < vcel[loop].size(); ++v)
1731 {
1732 // std::cerr << "edge " << v << std::endl;
1733 oid = nid;
1734 nid = vcel[loop][v]->id;
1735 if(oid != nid)
1736 {
1737 cl_temp_vec[0] = vcel[loop][v]->coords[0];
1738 cl_temp_vec[1] = vcel[loop][v]->coords[1];
1739 // std::cerr << "oid " << oid << ", nid " << nid << std::endl;
1740 // std::cerr << "tvec " << cl_temp_vec << std::endl;
1741 (*pvccrd)[loop].push_back(cl_temp_vec);
1742 }
1743 }
1744
1745 // close loop
1746 (*pvccrd)[loop].push_back( (*pvccrd)[loop][0]);
1747 }
1748
1749 // std::cerr <<"outta here" << std::endl;
1750 return 0;
1751 }
1752
1753 int ParSpaceTrimmer::PerformTrimming2(void)
1754 {
1755 unsigned int ui_tloops = UInt32((*pvccrd).size());
1756 unsigned int ui_i;
1757
1758 m_bDeleteVertexInfo = true; // vertexinfo holds Vec3d*
1759 vcel.resize(ui_tloops);
1760 // m_vbReversed.resize( ui_tloops );
1761 // std::cerr << ui_tloops << " trimming loops" << std::endl;
1762 #ifdef OSG_KEEP_2D_POINTS
1763 m_uiPosCnt = 0;
1764 #endif
1765
1766 #ifdef OSG_SPLIT_HOLE_CELLS
1767
1768 // split cells containing a hole
1769 for(ui_i = 0; ui_i < ui_tloops; ++ui_i)
1770 {
1771 if( ( (*m_pvbUsed)[ui_i]) &&
1772 ( (*m_pvbReversed)[ui_i]) )
1773 {
1774 unsigned int v; //, eid, oid;
1775 Vec2d cl_temp_vec;
1776 DCTPFace *pcl_inside_face;
1777 Vec2d cl_min;
1778 Vec2d cl_max;
1779 double d_ratio;
1780
1781 cl_temp_vec[0] = (*pvccrd)[ui_i][(*pvccrd)[ui_i].size() - 1][0];
1782 cl_temp_vec[1] = (*pvccrd)[ui_i][(*pvccrd)[ui_i].size() - 1][1];
1783 cl_min = cl_max = cl_temp_vec;
1784
1785 getStartingFace(cl_temp_vec);
1786 pcl_inside_face = state.f;
1787
1788 for(v = 0; v < (*pvccrd)[ui_i].size(); ++v)
1789 {
1790 if(pcl_inside_face)
1791 {
1792 cl_temp_vec[0] = (*pvccrd)[ui_i][v][0];
1793 cl_temp_vec[1] = (*pvccrd)[ui_i][v][1];
1794 cl_min[0] = osgMin(cl_min[0], cl_temp_vec[0]);
1795 cl_min[1] = osgMin(cl_min[1], cl_temp_vec[1]);
1796 cl_max[0] = osgMax(cl_max[0], cl_temp_vec[0]);
1797 cl_max[1] = osgMax(cl_max[1], cl_temp_vec[1]);
1798 if(!isOverFace(pcl_inside_face, cl_temp_vec) )
1799 {
1800 pcl_inside_face = NULL;
1801 }
1802 }
1803 }
1804
1805 if(pcl_inside_face)
1806 {
1807 if(cl_max[0] - cl_min[0] > cl_max[1] - cl_min[1])
1808 {
1809 d_ratio = ( (cl_min[0] + cl_max[0]) * 0.5 - pcl_inside_face->orig_face[0]->coords[0])
1810 / (pcl_inside_face->orig_face[1]->coords[0]
1811 - pcl_inside_face->orig_face[0]->coords[0]);
1812
1813 // std::cerr << "x: " << d_ratio << std::endl;
1814
1815 mesh->SubdivideQuadEW(pcl_inside_face, d_ratio);
1816 }
1817 else
1818 {
1819 d_ratio = ( (cl_min[1] + cl_max[1]) * 0.5 - pcl_inside_face->orig_face[3]->coords[1])
1820 / (pcl_inside_face->orig_face[0]->coords[1]
1821 - pcl_inside_face->orig_face[3]->coords[1]);
1822
1823 // std::cerr << "y: " << d_ratio << std::endl;
1824
1825 mesh->SubdivideQuadNS(pcl_inside_face, d_ratio);
1826 }
1827 }
1828 }
1829 }
1830
1831 #endif
1832
1833 for(ui_i = 0; ui_i < ui_tloops; ++ui_i)
1834 {
1835 if( (*m_pvbUsed)[ui_i])
1836 {
1837 // std::cerr << "new curve " << ( *pvccrd )[ ui_i ].size( ) << std::endl;
1838 #ifdef OSG_KEEP_2D_POINTS
1839 m_uiPosCnt += (*pvccrd)[ui_i].size();
1840 #endif
1841 if(isLoopValid(ui_i) )
1842 {
1843 #ifdef OSG_KEEP_2D_POINTS
1844 --m_uiPosCnt;
1845 #endif
1846 initializeStartState2(ui_i, vcel[ui_i]);
1847 #ifdef OSG_KEEP_2D_POINTS
1848 m_uiPosCnt -= (*pvccrd)[ui_i].size();
1849 ++m_uiPosCnt;
1850 #endif
1851 processCurve2(ui_i, vcel[ui_i]);
1852 }
1853 }
1854 }
1855
1856 for(ui_i = 0; ui_i < ui_tloops; ++ui_i)
1857 {
1858 if(vcel[ui_i].size() == 0)
1859 {
1860 // std::cerr << "deleting empty trimming loop" << std::endl;
1861 --ui_tloops;
1862 vcel[ui_i] = vcel[ui_tloops];
1863 vcel.pop_back();
1864 --ui_i;
1865 }
1866 }
1867
1868 // std::cerr << "+++ " << m_uiPosCnt << " +++" << std::endl;
1869
1870 return 0;
1871 }
1872
1873 Vec2d ParSpaceTrimmer::calcNormal(Vec2d &a, Vec2d &b)
1874 {
1875 Vec2d norm(0.0, 0.0);
1876 if(DCTPVecIsEqual(a, b) )
1877 return norm;
1878 double lab = sqrt( (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]) );
1879 norm[0] = -(b[1] - a[1]) / lab; // This is a normal -> rotated 90 degrees
1880 norm[1] = (b[0] - a[0]) / lab;
1881 return norm;
1882 }
1883
1884 bool ParSpaceTrimmer::checkEdgeNormals(DirectedGraph<Vec2d, unsigned char> &sg, int from, int to)
1885 {
1886 if(DCTPVecIsEqual(sg.nodes[from].nodeinfo, sg.nodes[to].nodeinfo) )
1887 return false;
1888 Vec2d norm = calcNormal(sg.nodes[from].nodeinfo, sg.nodes[to].nodeinfo);
1889
1890 //loop through all the edges in both nodes and check if the normal of the
1891 //non-directed edges are not the same
1892 for(unsigned int i = 0; i < sg.nodes[from].edges.size(); ++i)
1893 {
1894 Vec2d a = sg.nodes[sg.edges[sg.nodes[from].edges[i]].from].nodeinfo;
1895 Vec2d b = sg.nodes[sg.edges[sg.nodes[from].edges[i]].to].nodeinfo;
1896 Vec2d n = calcNormal(a, b);
1897 /// std::cerr <<"n: " << n << " norm: " << norm << std::endl;
1898 /// std::cerr << "v1: " << sg.nodes[ from ].nodeinfo << " v2: " <<
1899 /// sg.nodes[ to ].nodeinfo << std::endl;
1900 if(DCTPVecIsEqual(n, norm) )
1901 {
1902 /// std::cerr << "same normal found..." << std::endl;
1903 /// std::cerr << "v1: " << sg.nodes[ from ].nodeinfo << " v2: " <<
1904 /// sg.nodes[ to ].nodeinfo << std::endl;
1905 return true;
1906 }
1907 //if ( !sg.edges[ sg.nodes[ nodeidx ].edges[ i ] ].direction ) return true;
1908 }
1909
1910 return false;
1911 }
1912
1913 #ifdef OSG_FORCE_NO_T_VERTICES
1914 #ifdef OSG_KEEP_2D_POINTS
1915 int ParSpaceTrimmer::buildSurfaceGraph(DirectedGraph<Vec2d, unsigned char> *psg, std::vector<Vec3d> *pvclSewed, std::vector<Vec3d> *pvclNormals, std::vector<unsigned int> *pvuiIdx)
1916 #else
1917 int ParSpaceTrimmer::buildSurfaceGraph(DirectedGraph<Vec2d, unsigned char> *psg, std::vector<Vec3d> *pvclSewed, std::vector<Vec3d> *pvclNormals)
1918 #endif
1919 #else
1920 int ParSpaceTrimmer::buildSurfaceGraph(DirectedGraph<Vec2d, unsigned char> *psg, std::vector<Vec3d> *pvclSewed)
1921 #endif
1922 {
1923 dctpvertexset::iterator ve = mesh->vertices.end();
1924 dctpvertexset::iterator i;
1925 std::vector<DCTPVertex*> vpcl_added_from;
1926 std::vector<DCTPVertex*> vpcl_added_to;
1927
1928 // copy all sewed points with 3d pos
1929 #ifdef OSG_FORCE_NO_T_VERTICES
1930 if(pvclNormals)
1931 pvclNormals->clear();
1932 #endif
1933 #ifdef OSG_KEEP_2D_POINTS
1934 if(pvuiIdx)
1935 pvuiIdx->clear();
1936 #endif
1937 if(pvclSewed)
1938 pvclSewed->clear();
1939 psg->nodes.clear();
1940 psg->edges.clear();
1941
1942 for(i = mesh->vertices.begin(); i != ve; ++i)
1943 {
1944 if( (*i)->vertexinfo)
1945 {
1946 Vec2d v2dtemp( (*i)->coords[0], (*i)->coords[1]);
1947 // std::cerr << "coords: " << v2dtemp << std::endl;
1948 (*i)->node_id = psg->AddNode(v2dtemp);
1949 // std::cerr << ( Vec3d* ) ( *i )->vertexinfo;
1950 // std::cerr << "sewed: " << *( ( Vec3d* ) ( *i )->vertexinfo ) << std::endl;
1951 // std::cerr << "ids: " << pvclSewed->size( ) << " " << ( *i )->node_id << std::endl;
1952 #ifdef OSG_FORCE_NO_T_VERTICES
1953 if(pvclSewed)
1954 pvclSewed->push_back( ( (SPosNorm*)(*i)->vertexinfo)->clPos);
1955 /* #ifndef OSG_CREATE_NORMAL_MAPS
1956 if( pvclNormals ) pvclNormals->push_back( ( ( SPosNorm* ) ( *i )->vertexinfo )->clNorm );
1957 #endif*/
1958 #ifdef OSG_KEEP_2D_POINTS
1959 // std::cerr << pvuiIdx->size( ) << ": " << ( ( SPosNorm* ) ( *i )->vertexinfo )->uiNum << std::endl;
1960 if(pvuiIdx)
1961 pvuiIdx->push_back( ( (SPosNorm*)(*i)->vertexinfo)->uiNum);
1962 #endif
1963 #else
1964 if(pvclSewed)
1965 pvclSewed->push_back(*(static_cast<Vec3d*>((*i)->vertexinfo)) );
1966 #endif
1967 }
1968 }
1969
1970 #ifdef OSG_KEEP_2D_POINTS
1971 // add empty entries to have space for trimming loop vertices
1972 if(pvclSewed->size() < m_uiPosCnt)
1973 {
1974 Vec2d cl_dummy(0.0, 0.0);
1975 const unsigned int cui_idx_cnt = m_uiPosCnt - pvclSewed->size();
1976
1977 for(unsigned int ui_idx = 0; ui_idx < cui_idx_cnt; ++ui_idx)
1978 {
1979 psg->AddNode(cl_dummy);
1980 }
1981
1982 if(pvclSewed)
1983 pvclSewed->resize(m_uiPosCnt);
1984 if(pvclNormals)
1985 pvclNormals->resize(m_uiPosCnt);
1986 }
1987 #endif
1988
1989 // copy all inner points without 3d pos
1990 for(i = mesh->vertices.begin(); i != ve; ++i)
1991 {
1992 if( (*i)->vertexinfo == NULL)
1993 {
1994 Vec2d v2dtemp( (*i)->coords[0], (*i)->coords[1]);
1995 // std::cerr << "coords: " << v2dtemp << std::endl;
1996 (*i)->node_id = psg->AddNode(v2dtemp);
1997 }
1998 }
1999
2000 #ifdef OSG_NO_EDGE_SET
2001 dctpedgevector::iterator ee = mesh->edges.end();
2002 #else
2003 dctpedgeset::iterator ee = mesh->edges.end();
2004 #endif
2005 unsigned char dummy = 0;
2006
2007 #ifdef OSG_NO_EDGE_SET
2008
2009 for(dctpedgevector::iterator e = mesh->edges.begin(); e != ee; ++e)
2010 #else
2011
2012 for(dctpedgeset::iterator e = mesh->edges.begin(); e != ee; ++e)
2013 #endif
2014 {
2015 DCTPVertex *v1, *v2;
2016 bool orient;
2017
2018 (*e)->getVertices(v1, v2);
2019 if( (*e)->orientation < 0)
2020 {
2021 DCTPVertex *tmpv;
2022 tmpv = v1;
2023 v1 = v2;
2024 v2 = tmpv;
2025 orient = true;
2026 }
2027 else if( (*e)->orientation > 0)
2028 {
2029 orient = true;
2030 }
2031 else
2032 {
2033 orient = false;
2034 }
2035
2036 // if( orient ) std::cerr << "adding edge " << v1->node_id << ", " << v2->node_id << std::endl;
2037 dummy = orient ? 1 : 0; // set edgeinfo if edge belongs to trimming
2038 psg->AddEdge(dummy, v1->node_id, v2->node_id, orient);
2039 if(abs( (*e)->orientation) > 1)
2040 {
2041 for(int i_idx = 1; i_idx < abs( (*e)->orientation); ++i_idx)
2042 {
2043 psg->AddEdge(dummy, v1->node_id, v2->node_id, orient);
2044 }
2045 }
2046 }
2047
2048 /* dctpfacevector::iterator fe = mesh->faces.end();
2049 for( dctpfacevector::iterator i = mesh->faces.begin();
2050 i != fe; ++i ) {
2051 //FIXME sometime - whole trimming curve inside polygon
2052 //is not yet handled
2053 std::vector< TrimSegment >::iterator te = (*i)->trimseg.end();
2054 for( std::vector< TrimSegment >::iterator j = (*i)->trimseg.begin();
2055 j != te; ++j ) {
2056 bezier2dvector::iterator ce = j->trimbeziers.end();
2057 int sn = j->start->node_id; //start node id
2058 for( bezier2dvector::iterator k =
2059 j->trimbeziers.begin(); k != ce; ++k )
2060 insertBezierApproximation( *k, sn,
2061 *i,
2062 ( k == ce - 1 ),
2063 *psg );
2064 //gecc'
2065 if ( !(void*)j->end ) {
2066 std::cerr << "Null end node..." << std::endl;
2067 throw ParSpaceTrimmerError( ParSpaceTrimmerError::ERR_NULL_END_NODE );
2068 }
2069 /// std::cerr << "end node: " << (void*) j->end;
2070 /// std::cerr << " end node id: " << j->end->node_id;
2071 // std::cerr << "inserting end node " << sn << ", " << j->end->node_id << std::endl;
2072 psg->AddEdge( dummy, sn, j->end->node_id, true );
2073 }//trimsegment cyc over face
2074 }//all face cyc*/
2075
2076 #ifndef OSG_SPLIT_HOLE_CELLS
2077
2078 // add two edges for each hole in a single tree cell
2079 for(unsigned int loop = 0; loop < vcel.size(); ++loop)
2080 {
2081 // std::cerr << "edge loop " << loop << " of " << vcel.size( ) << " (" << vcel[ loop ].size( ) << ")" << std::endl;
2082 unsigned int v; //, eid, oid;
2083 // std::cerr << "adr:" << vcel[ loop ][ vcel[ loop ].size( ) - 1 ] << std::endl;
2084 unsigned int nid = vcel[loop][vcel[loop].size() - 1]->node_id;
2085 Vec2d cl_temp_vec;
2086 DCTPFace *pcl_inside_face;
2087
2088 cl_temp_vec[0] = vcel[loop][vcel[loop].size() - 1]->coords[0];
2089 cl_temp_vec[1] = vcel[loop][vcel[loop].size() - 1]->coords[1];
2090 if( (*m_pvbReversed)[loop])
2091 {
2092 getStartingFace(cl_temp_vec);
2093 pcl_inside_face = state.f;
2094
2095 for(v = 0; v < vcel[loop].size(); ++v)
2096 {
2097 // std::cerr << "edge " << v << std::endl;
2098 // oid = nid;
2099 // nid = vcel[ loop ][ v ]->node_id;
2100 if(pcl_inside_face)
2101 {
2102 cl_temp_vec[0] = vcel[loop][v]->coords[0];
2103 cl_temp_vec[1] = vcel[loop][v]->coords[1];
2104 if(vcel[loop][vcel[loop].size() - 1]->faces.size() ) // intersects a face edge
2105 // if( !isOverFace( pcl_inside_face, cl_temp_vec ) )
2106 {
2107 pcl_inside_face = NULL;
2108 }
2109 }
2110 // if( oid != nid )
2111 // {
2112 // std::cerr << "oid " << oid << ", nid " << nid << std::endl;
2113 // std::cerr << "tvec " << tvec << std::endl;
2114 // std::cerr << "inserted in loop." << std::endl;
2115 /* eid = psg->FindEdge( oid, nid );
2116 if( eid == -1 )
2117 {
2118 // std::cerr << "adding edge to graph: from " << oid << " to " << nid << std::endl;
2119 psg->AddEdge( dummy, oid, nid, true );
2120 }
2121 else
2122 {
2123 // std::cerr << "directing edge in graph: from " << oid << " to " << nid << std::endl;
2124 psg->setEdgeDirection( eid, nid );
2125 }
2126 }*/
2127 }
2128
2129 if(pcl_inside_face)
2130 {
2131 // loop is completely inside face
2132 // => find the nearest points to the upper left and lower right
2133 // edge of the face which don't intersect the trimming loop
2134 // and construct two undirected edges with these
2135 double d_qdist_ul = -1.0;
2136 double d_qdist_lr = -1.0;
2137 double d_act_dist;
2138 #ifdef OSG_UNION_TRI_QUAD
2139 DCTPVertex *pcl_upper_left = pcl_inside_face->orig_face[0];
2140 DCTPVertex *pcl_lower_right = pcl_inside_face->orig_face[2];
2141 #else
2142 DCTPVertex *pcl_upper_left = pcl_inside_face->orig_quad[0];
2143 DCTPVertex *pcl_lower_right = pcl_inside_face->orig_quad[2];
2144 #endif
2145 DCTPVertex *pcl_nearest_ul;
2146 DCTPVertex *pcl_nearest_lr;
2147 DCTPVertex *pcl_act_point;
2148 unsigned int ui_check;
2149 bool b_ok;
2150 unsigned int ui_exit;
2151
2152 dummy = 1; // edges don't belong to the tree
2153
2154 for(v = 0; v < vcel[loop].size(); ++v)
2155 {
2156 pcl_act_point = vcel[loop][v];
2157 d_act_dist = (Vec2d(pcl_act_point->coords - pcl_upper_left->coords) ).squareLength();
2158 if( (d_qdist_ul < -0.5) || (d_act_dist - d_qdist_ul < DCTP_EPS) )
2159 {
2160 d_qdist_ul = d_act_dist;
2161 pcl_nearest_ul = pcl_act_point;
2162 }
2163 d_act_dist = (Vec2d(pcl_act_point->coords - pcl_lower_right->coords) ).squareLength();
2164 if( (d_qdist_lr < -0.5) || (d_act_dist - d_qdist_lr < DCTP_EPS) )
2165 {
2166 d_qdist_lr = d_act_dist;
2167 pcl_nearest_lr = pcl_act_point;
2168 }
2169 }
2170
2171 // check edge1
2172 b_ok = false;
2173 ui_exit = 1000;
2174 while( (!b_ok) && (--ui_exit > 0) )
2175 {
2176 // std::cerr << "check " << pcl_nearest_ul->coords << " " << pcl_upper_left->coords << std::endl;
2177 b_ok = true;
2178
2179 // check if there is an intersection with other loops!
2180 for(ui_check = 0; ui_check < vcel.size(); ++ui_check)
2181 {
2182 if(ui_check != loop)
2183 {
2184 pcl_act_point = intersectsLoop(pcl_nearest_ul, pcl_upper_left, ui_check);
2185 if(pcl_act_point)
2186 {
2187 pcl_upper_left = pcl_act_point;
2188 ui_check = vcel.size();
2189 b_ok = false;
2190 ///std::cerr << "o=> " << pcl_nearest_ul->coords << " " << pcl_upper_left->coords << std::endl;
2191 }
2192 }
2193 }
2194
2195 // check if there is an intersection with this loop!
2196 pcl_act_point = intersectsLoop(pcl_upper_left, pcl_nearest_ul, loop);
2197 if(pcl_act_point)
2198 {
2199 pcl_nearest_ul = pcl_act_point;
2200 b_ok = false;
2201 ///std::cerr << "t=> " << pcl_nearest_ul->coords << " " << pcl_upper_left->coords << std::endl;
2202 }
2203
2204 // check if there is an intersection with existing connect edges
2205 for(ui_check = 0; ui_check < vpcl_added_from.size(); ++ui_check)
2206 {
2207 if( (pcl_nearest_ul != vpcl_added_from[ui_check]) &&
2208 (pcl_nearest_ul != vpcl_added_to[ui_check]) &&
2209 (pcl_upper_left != vpcl_added_from[ui_check]) &&
2210 (pcl_upper_left != vpcl_added_to[ui_check]) )
2211 {
2212 if(doIntersect(vpcl_added_from[ui_check]->coords, vpcl_added_to[ui_check]->coords,
2213 pcl_nearest_ul->coords, pcl_upper_left->coords, d_act_dist) )
2214 {
2215 if(d_act_dist <= 1.0)
2216 {
2217 if(d_act_dist < 0.5)
2218 {
2219 pcl_upper_left = vpcl_added_from[ui_check];
2220 }
2221 else
2222 {
2223 pcl_upper_left = vpcl_added_to[ui_check];
2224 }
2225 b_ok = false;
2226 ui_check = vpcl_added_from.size();
2227 ///std::cerr << "e=> " << pcl_nearest_ul->coords << " " << pcl_upper_left->coords << std::endl;
2228 }
2229 }
2230 }
2231 }
2232
2233 if(pcl_upper_left == pcl_nearest_ul)
2234 {
2235 b_ok = true;
2236 }
2237 }
2238 // save edge1
2239 if(pcl_upper_left != pcl_nearest_ul)
2240 {
2241 vpcl_added_from.push_back(pcl_upper_left);
2242 vpcl_added_to.push_back(pcl_nearest_ul);
2243 psg->AddEdge(dummy, pcl_upper_left->node_id,
2244 pcl_nearest_ul->node_id, false);
2245 }
2246 ///std::cerr << "ok 1" << std::endl;
2247
2248 // check edge2
2249 b_ok = false;
2250 ui_exit = 1000;
2251 while( (!b_ok) && (--ui_exit > 0) )
2252 {
2253 // std::cerr << "check " << pcl_nearest_lr->coords << " " << pcl_lower_right->coords << std::endl;
2254 b_ok = true;
2255
2256 // check if there is an intersection with other loops!
2257 for(ui_check = 0; ui_check < vcel.size(); ++ui_check)
2258 {
2259 if(ui_check != loop)
2260 {
2261 pcl_act_point = intersectsLoop(pcl_nearest_lr, pcl_lower_right, ui_check);
2262 if(pcl_act_point)
2263 {
2264 pcl_lower_right = pcl_act_point;
2265 ui_check = vcel.size();
2266 b_ok = false;
2267 ///std::cerr << "o=> " << pcl_nearest_lr->coords << " " << pcl_lower_right->coords << std::endl;
2268 }
2269 }
2270 }
2271
2272 // check if there is an intersection with this loop!
2273 pcl_act_point = intersectsLoop(pcl_lower_right, pcl_nearest_lr, loop);
2274 if(pcl_act_point)
2275 {
2276 pcl_nearest_lr = pcl_act_point;
2277 b_ok = false;
2278 ///std::cerr << "t=> " << pcl_nearest_lr->coords << " " << pcl_lower_right->coords << std::endl;
2279 }
2280
2281 // check if there is an intersection with existing connect edges
2282 for(ui_check = 0; ui_check < vpcl_added_from.size(); ++ui_check)
2283 {
2284 if( (pcl_nearest_lr != vpcl_added_from[ui_check]) &&
2285 (pcl_nearest_lr != vpcl_added_to[ui_check]) &&
2286 (pcl_lower_right != vpcl_added_from[ui_check]) &&
2287 (pcl_lower_right != vpcl_added_to[ui_check]) )
2288 {
2289 if(doIntersect(vpcl_added_from[ui_check]->coords, vpcl_added_to[ui_check]->coords,
2290 pcl_nearest_lr->coords, pcl_lower_right->coords, d_act_dist) )
2291 {
2292 if(d_act_dist <= 1.0)
2293 {
2294 if(d_act_dist < 0.5)
2295 {
2296 pcl_lower_right = vpcl_added_from[ui_check];
2297 }
2298 else
2299 {
2300 pcl_lower_right = vpcl_added_to[ui_check];
2301 }
2302 b_ok = false;
2303 ui_check = vpcl_added_from.size();
2304 ///std::cerr << "e=> " << pcl_nearest_lr->coords << " " << pcl_lower_right->coords << std::endl;
2305 }
2306 }
2307 }
2308 }
2309
2310 if(pcl_lower_right == pcl_nearest_lr)
2311 {
2312 b_ok = true;
2313 }
2314 }
2315 // save edge2
2316 if(pcl_lower_right != pcl_nearest_lr)
2317 {
2318 vpcl_added_from.push_back(pcl_lower_right);
2319 vpcl_added_to.push_back(pcl_nearest_lr);
2320 psg->AddEdge(dummy, pcl_lower_right->node_id,
2321 pcl_nearest_lr->node_id, false);
2322 }
2323 ///std::cerr << "ok 2" << std::endl;
2324 }
2325 }
2326 }
2327
2328 #endif
2329 return 0;
2330 }
2331
2332 #ifndef OSG_FORCE_NO_T_VERTICES
2333 void ParSpaceTrimmer::getTrimmingLoops(std::vector<std::vector<Vec2d> > &rvvclTrimmingLoops)
2334 {
2335 rvvclTrimmingLoops.resize(vcel.size() );
2336
2337 for(unsigned int loop = 0; loop < vcel.size(); ++loop)
2338 {
2339 rvvclTrimmingLoops[loop].resize(vcel[loop].size() - 1);
2340
2341 for(unsigned int v = 0; v < vcel[loop].size() - 1; ++v)
2342 {
2343 rvvclTrimmingLoops[loop][v] = Vec2d(vcel[loop][v]->coords);
2344 }
2345 }
2346 }
2347 #endif
2348
2349 void ParSpaceTrimmer::checkEdgeloops()
2350 {
2351 std::vector<SScanLineEdge*> vpt_start;
2352 std::vector<SScanLineEdge*> vpt_end;
2353 // std::vector< SScanLineEdge* > vpt_edges;
2354 ScanLineEventSet spt_events;
2355 unsigned int ui_loop;
2356 unsigned int ui_vertex;
2357 unsigned int ui_last;
2358 unsigned int ui_size;
2359 unsigned int ui_loop2;
2360 SScanLineEdge *pt_act_edge;
2361 SScanLineEntry *pt_scan_line = NULL;
2362 SScanLineEntry *pt_act_entry;
2363 SScanLineEntry *pt_next_entry;
2364 ScanLineEventSet::iterator ispt_act_event;
2365 SScanLineEvent *pt_act_event;
2366 int i_inside;
2367 bool b_valid;
2368 Vec3d cl_p;
2369 Vec3d cl_pp;
2370
2371 // create scan line edges and sort them
2372 for(ui_loop = 0; ui_loop < vcel.size(); ++ui_loop)
2373 {
2374 ui_size = UInt32(vcel[ui_loop].size());
2375 // ui_last = ui_size - 1;
2376 cl_p = vcel[ui_loop][ui_size - 1]->coords;
2377
2378 unsigned int ui_new_num = 0;
2379 std::vector<DCTPVertex*> vpcl_new_points(ui_size); // waste some memory to have linear time
2380
2381 for(ui_vertex = 0; ui_vertex < ui_size; ++ui_vertex)
2382 {
2383 cl_pp = cl_p;
2384 cl_p = vcel[ui_loop][ui_vertex]->coords;
2385
2386 // check for double vertices
2387 if(DCTPVecIsNotEqual(cl_p, cl_pp) )
2388 {
2389 // if( vcel[ ui_loop ][ ui_vertex ]->vertexinfo )
2390 {
2391 vpcl_new_points[ui_new_num] = mesh->AddVertex(cl_p);
2392 // std::cerr << ( void* ) vpcl_new_points[ ui_new_num ] << std::endl;
2393 if(vpcl_new_points[ui_new_num] != vcel[ui_loop][ui_vertex])
2394 {
2395 // std::cerr << ( void* ) vpcl_new_points[ ui_new_num ] << " ";
2396 // std::cerr << vcel[ ui_loop ][ ui_vertex ]->edges.size( ) << " ";
2397 // std::cerr << "delete vertex2:" << ( void* ) vcel[ ui_loop ][ ui_vertex ] << std::endl;
2398 // std::cerr << vpcl_new_points[ ui_new_num ]->coords << " ";
2399 // delete vcel[ ui_loop ][ ui_vertex ];
2400 // std::cerr << vpcl_new_points[ ui_new_num ]->coords << std::endl;
2401 }
2402 // std::cerr << vpcl_new_points[ ui_new_num ]->coords << std::endl;
2403 ++ui_new_num;
2404 // ui_last = ui_vertex;
2405 }
2406 /* else
2407 {
2408 const Vec3d ccl_pn = vcel[ ui_loop ][ ( ui_vertex + 1 ) % ui_size ]->coords;
2409 double d_d1[ 2 ], d_d2[ 2 ], d_d3[ 2 ];
2410
2411 d_d1[ 0 ] = ccl_pp[0];
2412 d_d1[ 1 ] = ccl_pp[1];
2413 d_d2[ 0 ] = ccl_p[0];
2414 d_d2[ 1 ] = ccl_p[1];
2415 d_d3[ 0 ] = ccl_pn[0];
2416 d_d3[ 1 ] = ccl_pn[1];
2417
2418 if( orient2d( d_d1, d_d2, d_d3 ) != 0.0 )
2419 {
2420 vpcl_new_points[ ui_new_num ] = vcel[ ui_loop ][ ui_vertex ];
2421 ++ui_new_num;
2422 ui_last = ui_vertex;
2423 }
2424 }*/
2425 }
2426 else
2427 {
2428 if(!mesh->findVertex(cl_p) )
2429 {
2430 // std::cerr << "delete vertex3:" << ( void* ) vcel[ ui_loop ][ ui_vertex ] << std::endl;
2431 delete vcel[ui_loop][ui_vertex];
2432 }
2433 }
2434 }
2435
2436 // copy new points
2437 // if( ui_new_num != ui_size )
2438 {
2439 ui_size = ui_new_num;
2440 vcel[ui_loop].resize(ui_size);
2441
2442 for(ui_vertex = 0; ui_vertex < ui_size; ++ui_vertex)
2443 {
2444 vcel[ui_loop][ui_vertex] = vpcl_new_points[ui_vertex];
2445 // std::cerr << vpcl_new_points[ ui_vertex ]->coords << std::endl;
2446 }
2447 }
2448
2449 // loops of size 2 are degenerate...
2450 if(ui_size > 2)
2451 {
2452 ui_last = ui_size - 1;
2453
2454 for(ui_vertex = 0; ui_vertex < ui_size; ++ui_vertex)
2455 {
2456 if(vcel[ui_loop][ui_last]->id != vcel[ui_loop][ui_vertex]->id)
2457 {
2458 // insert edge and events
2459 // std::cerr << "new edge " << vcel[ ui_loop ][ ui_last ]->id << " " << vcel[ ui_loop ][ ui_vertex ]->id << std::endl;
2460 pt_act_edge = new SScanLineEdge;
2461 pt_act_edge->pclFromVertex = vcel[ui_loop][ui_last];
2462 pt_act_edge->pclToVertex = vcel[ui_loop][ui_vertex];
2463 // std::cerr << pt_act_edge->pclFromVertex << " ";
2464 // std::cerr << pt_act_edge->pclToVertex << std::endl;
2465 pt_act_edge->ptPrev = NULL;
2466 pt_act_edge->ptNext = NULL;
2467 pt_act_edge->ptEntry = NULL;
2468 // pt_act_edge->uiOrigNum = vpt_edges.size( );
2469 pt_act_edge->bInvalid = false;
2470 if(insertScanLineEvents(pt_act_edge, spt_events) )
2471 {
2472 // vpt_edges.push_back( pt_act_edge );
2473 }
2474 ui_last = ui_vertex;
2475 }
2476 }
2477 }
2478 }
2479
2480 // we don't need the old edges any more...
2481 vcel.clear();
2482 // std::cerr << "after clear: " << vcel.size() << std::endl;
2483
2484 // construct new edge loops
2485 while(!spt_events.empty() )
2486 {
2487 ispt_act_event = spt_events.begin();
2488 pt_act_event = *ispt_act_event;
2489 // std::cerr << "erase act event ";
2490 spt_events.erase(ispt_act_event);
2491 // std::cerr << "ok" << std::endl;
2492 // std::cerr << "pos is: " << pt_act_event->clPos << std::endl;
2493 // std::cerr << "other is: " << pt_act_event->clOther << std::endl;
2494 // std::cerr << "start is: " << pt_act_event->bStart << std::endl;
2495
2496 // get actual edge
2497 // std::cerr << "event is: " << pt_act_event;
2498 pt_act_edge = pt_act_event->ptEdge;
2499 // std::cerr << " edge is: " << pt_act_edge << std::endl;
2500 // if( pt_act_event->bStart )
2501 if(pt_act_edge->ptEntry == NULL)
2502 {
2503 // create new scan line entry
2504 pt_act_entry = new SScanLineEntry;
2505 pt_act_entry->ptEdge = pt_act_edge;
2506 pt_act_edge->ptEntry = pt_act_entry;
2507 // std::cerr << pt_act_edge->ptEntry << " ";
2508 // sort into scan line
2509 // std::cerr << "scanline was: " << pt_scan_line << std::endl;
2510 pt_scan_line = insertInScanLine(pt_act_entry, pt_scan_line);
2511 // std::cerr << "scanline is: " << pt_scan_line << std::endl;
2512 // check if there is an intersection and split lines if there is one
2513 checkSLIntersection(pt_act_entry, spt_events);
2514 // std::cerr << pt_act_edge->ptEntry << std::endl;
2515 }
2516 else
2517 {
2518 // check if edge is valid
2519 i_inside = 0;
2520 // std::cerr << pt_act_edge->ptEntry << std::endl;
2521 if(!pt_act_edge->bInvalid)
2522 {
2523 pt_act_entry = pt_act_edge->ptEntry->ptNext;
2524 while(pt_act_entry)
2525 {
2526 /* std::cerr << pt_act_entry << std::endl;
2527 std::cerr << pt_act_entry->ptEdge->pclFromVertex->coords << " -> ";
2528 std::cerr << pt_act_entry->ptEdge->pclToVertex->coords << std::endl;*/
2529 if(DCTPVecIsGreater(pt_act_entry->ptEdge->pclFromVertex->coords, pt_act_entry->ptEdge->pclToVertex->coords) )
2530 {
2531 // std::cerr << "+";
2532 // edge goes down => right is inside
2533 ++i_inside;
2534 }
2535 else
2536 {
2537 // std::cerr << "-";
2538 // edge goes up => right is outside
2539 --i_inside;
2540 }
2541 pt_act_entry = pt_act_entry->ptNext;
2542 }
2543 }
2544 // remove it from the scanline
2545 pt_act_entry = pt_act_edge->ptEntry;
2546 pt_next_entry = pt_act_entry->ptNext;
2547 if(pt_act_entry->ptNext)
2548 pt_act_entry->ptNext->ptPrev = pt_act_entry->ptPrev;
2549 if(pt_act_entry->ptPrev)
2550 pt_act_entry->ptPrev->ptNext = pt_act_entry->ptNext;
2551 else
2552 pt_scan_line = pt_act_entry->ptNext;
2553 delete pt_act_entry;
2554 if(!pt_act_edge->bInvalid)
2555 {
2556 if(DCTPVecIsGreater(pt_act_edge->pclFromVertex->coords, pt_act_edge->pclToVertex->coords) )
2557 {
2558 // edge goes down => must be closed
2559 // std::cerr << "inside = " << i_inside << ", should be -1" << std::endl;
2560 b_valid = (i_inside == -1);
2561 }
2562 else
2563 {
2564 // edge goes up => rest must be ok
2565 // std::cerr << "inside = " << i_inside << ", should be 0" << std::endl;
2566 b_valid = (i_inside == 0);
2567 }
2568 if(b_valid)
2569 {
2570 // append edge to polyline
2571 ui_size = UInt32(vpt_start.size());
2572
2573 for(ui_loop = 0; ui_loop < ui_size; ++ui_loop)
2574 {
2575 if(pt_act_edge->pclToVertex == vpt_start[ui_loop]->pclFromVertex)
2576 {
2577 // std::cerr << "appending edge to polyline " << ui_loop << std::endl;
2578 pt_act_edge->ptNext = vpt_start[ui_loop];
2579 vpt_start[ui_loop]->ptPrev = pt_act_edge;
2580 vpt_start[ui_loop] = pt_act_edge;
2581 break;
2582 }
2583 if(pt_act_edge->pclFromVertex == vpt_end[ui_loop]->pclToVertex)
2584 {
2585 // std::cerr << "appending edge to polyline " << ui_loop << std::endl;
2586 pt_act_edge->ptPrev = vpt_end[ui_loop];
2587 vpt_end[ui_loop]->ptNext = pt_act_edge;
2588 vpt_end[ui_loop] = pt_act_edge;
2589 break;
2590 }
2591 }
2592
2593 if(ui_loop < ui_size)
2594 {
2595 // check if polyline is closed
2596 if(vpt_start[ui_loop]->pclFromVertex == vpt_end[ui_loop]->pclToVertex)
2597 {
2598 // save closed polyline to vcel
2599 // std::cerr << "closing polyline " << ui_loop << std::endl;
2600 saveLoop(vpt_start[ui_loop]);
2601 if(ui_loop != ui_size - 1)
2602 {
2603 vpt_start[ui_loop] = vpt_start[ui_size - 1];
2604 vpt_end[ui_loop] = vpt_end[ui_size - 1];
2605 }
2606 vpt_start.resize(ui_size - 1);
2607 vpt_end.resize(ui_size - 1);
2608 }
2609 else
2610 {
2611 // check if two polylines join
2612 for(ui_loop2 = 0; ui_loop2 < ui_size; ++ui_loop2)
2613 {
2614 if(ui_loop != ui_loop2)
2615 {
2616 if(vpt_start[ui_loop]->pclFromVertex == vpt_end[ui_loop2]->pclToVertex)
2617 {
2618 // std::cerr << "joining polylines." << std::endl;
2619 vpt_start[ui_loop]->ptPrev = vpt_end[ui_loop2];
2620 vpt_end[ui_loop2]->ptNext = vpt_start[ui_loop];
2621 vpt_start[ui_loop] = vpt_start[ui_loop2];
2622 break;
2623 }
2624 if(vpt_start[ui_loop2]->pclFromVertex == vpt_end[ui_loop]->pclToVertex)
2625 {
2626 // std::cerr << "joining polylines." << std::endl;
2627 vpt_start[ui_loop2]->ptPrev = vpt_end[ui_loop];
2628 vpt_end[ui_loop]->ptNext = vpt_start[ui_loop2];
2629 vpt_end[ui_loop] = vpt_end[ui_loop2];
2630 break;
2631 }
2632 }
2633 }
2634
2635 if(ui_loop2 < ui_size)
2636 {
2637 // std::cerr << "removing old polyline " << ui_loop2 << std::endl;
2638 if(ui_loop2 != ui_size - 1)
2639 {
2640 vpt_start[ui_loop2] = vpt_start[ui_size - 1];
2641 vpt_end[ui_loop2] = vpt_end[ui_size - 1];
2642 }
2643 vpt_start.resize(ui_size - 1);
2644 vpt_end.resize(ui_size - 1);
2645 }
2646 }
2647 }
2648 else
2649 {
2650 // std::cerr << "starting new polyline " << ui_loop << std::endl;
2651 // start new polyline
2652 vpt_start.push_back(pt_act_edge);
2653 vpt_end.push_back(pt_act_edge);
2654 }
2655 }
2656 else
2657 {
2658 // std::cerr << "delete edge " << pt_act_edge->pclFromVertex->id << " " << pt_act_edge->pclToVertex->id << std::endl;
2659 delete pt_act_edge;
2660 }
2661 }
2662 else
2663 {
2664 // std::cerr << "delete edge " << pt_act_edge->pclFromVertex->id << " " << pt_act_edge->pclToVertex->id << std::endl;
2665 delete pt_act_edge;
2666 }
2667 if( (pt_next_entry) && (pt_next_entry->ptPrev) )
2668 {
2669 if( (!pt_next_entry->ptEdge->bInvalid) &&
2670 (!pt_next_entry->ptPrev->ptEdge->bInvalid) )
2671 {
2672 // std::cerr << pt_next_entry << ", " << pt_next_entry->ptPrev << std::endl;
2673 ScanLineIntersect(pt_next_entry->ptPrev, pt_next_entry, spt_events);
2674 if(pt_next_entry->ptEdge->bInvalid)
2675 {
2676 removeSLEntry(pt_next_entry->ptPrev, spt_events);
2677 removeSLEntry(pt_next_entry, spt_events);
2678 }
2679 }
2680 }
2681 // std::cerr << std::endl;
2682 }
2683
2684 delete pt_act_event;
2685 }
2686
2687 /* if( vpt_start.size( ) > 0 )
2688 {
2689 std::cerr.precision( 24 );
2690 std::cerr << vpt_start[ 0 ]->pclFromVertex->coords << " <-> " << vpt_end[ 0 ]->pclToVertex->coords << std::endl;
2691 // exit( -1 );
2692 }*/
2693 ui_size = UInt32(vpt_start.size());
2694
2695 for(ui_loop = 0; ui_loop < ui_size; ++ui_loop)
2696 {
2697 // check if polyline is closed
2698 // if( vpt_start[ ui_loop ]->pclFromVertex->coords == vpt_end[ ui_loop ]->pclToVertex->coords )
2699 {
2700 // save closed polyline to vcel
2701 // std::cerr << "closing polyline " << ui_loop << std::endl;
2702 saveLoop(vpt_start[ui_loop]);
2703 }
2704 }
2705 }
2706
2707 bool ParSpaceTrimmer::insertScanLineEvents(SScanLineEdge *ptEdge, ScanLineEventSet &rsptEvents, char cWhich)
2708 {
2709 SScanLineEvent *pt_new_event;
2710 std::pair<ScanLineEventSet::iterator, bool> pr_insert;
2711 Vec2d min;
2712 Vec2d max;
2713 /* int i_select = 0;
2714
2715 if( ptEdge->pclFromVertex->coords[1] < ptEdge->pclToVertex->coords[1] ) i_select = 1;
2716 else if( ptEdge->pclFromVertex->coords[1] > ptEdge->pclToVertex->coords[1] ) i_select = -1;
2717 else if( ptEdge->pclFromVertex->coords[0] < ptEdge->pclToVertex->coords[0] ) i_select = 1;
2718 else if( ptEdge->pclFromVertex->coords[0] > ptEdge->pclToVertex->coords[0] ) i_select = -1;*/
2719
2720 if(DCTPVecIsLesser(ptEdge->pclFromVertex->coords, ptEdge->pclToVertex->coords) )
2721 // if( i_select == 1 )
2722 {
2723 min[0] = ptEdge->pclFromVertex->coords[0];
2724 min[1] = ptEdge->pclFromVertex->coords[1];
2725 max[0] = ptEdge->pclToVertex->coords[0];
2726 max[1] = ptEdge->pclToVertex->coords[1];
2727 }
2728 else if(DCTPVecIsEqual(ptEdge->pclFromVertex->coords,
2729 ptEdge->pclToVertex->coords) )
2730 // else if( i_select == 0 )
2731 {
2732 return false;
2733 }
2734 else
2735 {
2736 min[0] = ptEdge->pclToVertex->coords[0];
2737 min[1] = ptEdge->pclToVertex->coords[1];
2738 max[0] = ptEdge->pclFromVertex->coords[0];
2739 max[1] = ptEdge->pclFromVertex->coords[1];
2740 }
2741
2742 if(cWhich != 1)
2743 {
2744 pt_new_event = new SScanLineEvent;
2745 pt_new_event->ptEdge = ptEdge;
2746 pt_new_event->bStart = true;
2747 pt_new_event->clPos = min;
2748 pt_new_event->clOther = max;
2749
2750 /* std::cerr << "scan line event: edge = " << pt_new_event->ptEdge;
2751 std::cerr << " start = " << pt_new_event->bStart;
2752 std::cerr << " pos = " << pt_new_event->clPos;
2753 std::cerr << " other = " << pt_new_event->clOther << std::endl;*/
2754 // std::cerr << " num = " << pt_new_event->ptEdge->uiOrigNum << std::endl;
2755
2756 pr_insert = rsptEvents.insert(pt_new_event);
2757 if(!pr_insert.second)
2758 {
2759 std::cerr << "Scan line event exists! aborting." << std::endl;
2760 exit(-1);
2761 }
2762 }
2763
2764 if(cWhich != 0)
2765 {
2766 pt_new_event = new SScanLineEvent;
2767 pt_new_event->ptEdge = ptEdge;
2768 pt_new_event->bStart = false;
2769 pt_new_event->clPos = max;
2770 pt_new_event->clOther = min;
2771
2772 /* std::cerr << "scan line event: edge = " << pt_new_event->ptEdge;
2773 std::cerr << " start = " << pt_new_event->bStart;
2774 std::cerr << " pos = " << pt_new_event->clPos;
2775 std::cerr << " other = " << pt_new_event->clOther << std::endl;*/
2776 // std::cerr << " num = " << pt_new_event->ptEdge->uiOrigNum << std::endl;
2777
2778 pr_insert = rsptEvents.insert(pt_new_event);
2779 if(!pr_insert.second)
2780 {
2781 std::cerr << "Scan line event exists! aborting." << std::endl;
2782 exit(-1);
2783 }
2784 }
2785
2786 return true;
2787 }
2788
2789 SScanLineEntry *ParSpaceTrimmer::insertInScanLine(SScanLineEntry *ptActEntry, SScanLineEntry *ptScanLine)
2790 {
2791 SScanLineEntry *pt_prev_entry = NULL;
2792 SScanLineEntry *pt_next_entry;
2793
2794 pt_next_entry = ptScanLine;
2795 while(pt_next_entry)
2796 {
2797 if(isSLEntryLess(ptActEntry->ptEdge, pt_next_entry->ptEdge) )
2798 break;
2799 pt_prev_entry = pt_next_entry;
2800 pt_next_entry = pt_next_entry->ptNext;
2801 }
2802 ptActEntry->ptPrev = pt_prev_entry;
2803 ptActEntry->ptNext = pt_next_entry;
2804 if(pt_next_entry)
2805 pt_next_entry->ptPrev = ptActEntry;
2806 if(pt_prev_entry)
2807 pt_prev_entry->ptNext = ptActEntry;
2808 else
2809 return ptActEntry;
2810 return ptScanLine;
2811 }
2812
2813 void ParSpaceTrimmer::saveLoop(SScanLineEdge *ptEdge)
2814 {
2815 SScanLineEdge *pt_del;
2816 std::vector<DCTPVertex*> vpcl_cel;
2817
2818 if(ptEdge == NULL)
2819 {
2820 return;
2821 }
2822
2823 while(ptEdge)
2824 {
2825 vpcl_cel.push_back(ptEdge->pclFromVertex);
2826 pt_del = ptEdge;
2827 ptEdge = ptEdge->ptNext;
2828 // std::cerr << "delete edge " << pt_del->pclFromVertex->id << " " << pt_del->pclToVertex->id << std::endl;
2829 delete pt_del;
2830 }
2831
2832 if(vpcl_cel.size() == 1)
2833 {
2834 return;
2835 }
2836
2837 // closed polylines have the same first and last vertex
2838 vpcl_cel.push_back(vpcl_cel[0]);
2839
2840 vcel.push_back(vpcl_cel);
2841 }
2842
2843 void ParSpaceTrimmer::checkSLIntersection(SScanLineEntry *ptActEntry, ScanLineEventSet &rsptEvents)
2844 {
2845 SScanLineEntry *pt_prev_entry = ptActEntry->ptPrev;
2846 SScanLineEntry *pt_next_entry = ptActEntry->ptNext;
2847 // DCTPVertex *pcl_split_vertex;
2848
2849 if(pt_prev_entry)
2850 {
2851 ScanLineIntersect(ptActEntry, pt_prev_entry, rsptEvents);
2852 if(ptActEntry->ptEdge->bInvalid)
2853 {
2854 removeSLEntry(ptActEntry->ptPrev, rsptEvents);
2855 removeSLEntry(ptActEntry, rsptEvents);
2856 return;
2857 }
2858 }
2859 if(pt_next_entry)
2860 {
2861 ScanLineIntersect(ptActEntry, pt_next_entry, rsptEvents);
2862 if(ptActEntry->ptEdge->bInvalid)
2863 {
2864 removeSLEntry(ptActEntry, rsptEvents);
2865 removeSLEntry(ptActEntry->ptNext, rsptEvents);
2866 }
2867 }
2868 }
2869
2870 void ParSpaceTrimmer::ScanLineIntersect(SScanLineEntry *ptEntry1, SScanLineEntry *ptEntry2, ScanLineEventSet &rsptEvents)
2871 {
2872 SScanLineEdge *pt_edge1 = ptEntry1->ptEdge;
2873 SScanLineEdge *pt_edge2 = ptEntry2->ptEdge;
2874 SScanLineEdge *pt_new_edge;
2875 DCTPVertex *pcl_split_vertex;
2876
2877 /* if( ( pt_edge1->pclFromVertex == pt_edge2->pclFromVertex ) ||
2878 ( pt_edge1->pclFromVertex == pt_edge2->pclToVertex ) ||
2879 ( pt_edge1->pclToVertex == pt_edge2->pclFromVertex ) ||
2880 ( pt_edge1->pclToVertex == pt_edge2->pclToVertex ) )
2881 {
2882 return;
2883 }*/
2884
2885 /* if( ( pt_edge1->bInvalid ) || ( pt_edge2->bInvalid ) )
2886 {
2887 std::cerr << pt_edge1 << " " << pt_edge2 << std::endl;
2888 exit( -1 );
2889 }*/
2890
2891 // std::cerr.precision( 12 );
2892
2893 double ad_s1[2];
2894 double ad_e1[2];
2895 double ad_s2[2];
2896 double ad_e2[2];
2897
2898 ad_s1[0] = pt_edge1->pclFromVertex->coords[0];
2899 ad_s1[1] = pt_edge1->pclFromVertex->coords[1];
2900 ad_e1[0] = pt_edge1->pclToVertex->coords[0];
2901 ad_e1[1] = pt_edge1->pclToVertex->coords[1];
2902 ad_s2[0] = pt_edge2->pclFromVertex->coords[0];
2903 ad_s2[1] = pt_edge2->pclFromVertex->coords[1];
2904 ad_e2[0] = pt_edge2->pclToVertex->coords[0];
2905 ad_e2[1] = pt_edge2->pclToVertex->coords[1];
2906
2907 const double cd_r1 = orient2d(ad_s1, ad_s2, ad_e2);
2908 const double cd_r2 = orient2d(ad_e1, ad_s2, ad_e2);
2909 if( ( (cd_r1 < 0.0) && (cd_r2 < 0.0) ) ||
2910 ( (cd_r1 > 0.0) && (cd_r2 > 0.0) ) )
2911 {
2912 return;
2913 }
2914
2915 const double cd_r3 = orient2d(ad_s2, ad_s1, ad_e1);
2916 const double cd_r4 = orient2d(ad_e2, ad_s1, ad_e1);
2917
2918 double cd_v1x = ad_e1[0] - ad_s1[0];
2919 double cd_v1y = ad_e1[1] - ad_s1[1];
2920 double cd_v2x = ad_e2[0] - ad_s2[0];
2921 double cd_v2y = ad_e2[1] - ad_s2[1];
2922
2923 double cd_b = cd_v1x * cd_v2y - cd_v1y * cd_v2x;
2924
2925 if( ( (cd_r3 < 0.0) && (cd_r4 < 0.0) ) ||
2926 ( (cd_r3 > 0.0) && (cd_r4 > 0.0) ) )
2927 {
2928 return;
2929 }
2930
2931 if( ((cd_r1 == 0.0) && (cd_r2 == 0.0) &&
2932 (cd_r3 == 0.0) && (cd_r4 == 0.0) ) ||
2933 osgAbs(cd_b) < 1e-32 //prevent strange roundoff error later
2934 //(this shouldn't be needed in an ideal world...)
2935 )
2936 {
2937 // edges are coliniear
2938 DCTPVertex *pcl_ip1;
2939 DCTPVertex *pcl_ip2;
2940 bool b_down1;
2941 bool b_down2;
2942
2943 // std::cerr <<"collinear edges..."<<std::endl;
2944
2945 /* if ( osgAbs(cd_b) < 1e-32 &&
2946 ( cd_r1 != 0.0 || cd_r1 != 0.0 ||
2947 cd_r3 != 0.0 || cd_r4 != 0.0 ) )
2948 std::cerr <<"collinear because of cd_b" << cd_b <<std::endl;*/
2949
2950 b_down1 = DCTPVecIsLesser(pt_edge1->pclFromVertex->coords, pt_edge1->pclToVertex->coords);
2951 b_down2 = DCTPVecIsLesser(pt_edge2->pclFromVertex->coords, pt_edge2->pclToVertex->coords);
2952 pcl_ip1 = b_down1 ? pt_edge1->pclFromVertex : pt_edge1->pclToVertex;
2953 pcl_ip2 = b_down2 ? pt_edge2->pclFromVertex : pt_edge2->pclToVertex;
2954
2955 if(DCTPVecIsEqual(pcl_ip1->coords, pcl_ip2->coords) )
2956 {
2957 // edges are colinear and start in the same point.
2958 // => mark them as invalid if they have opposite directions
2959 // and use the end points
2960 if( ( (b_down1) && !(b_down2) ) || (!(b_down1) && (b_down2) ) )
2961 {
2962 // std::cerr << "edges become invalid." << std::endl;
2963 pt_edge1->bInvalid = true;
2964 pt_edge2->bInvalid = true;
2965 }
2966 pcl_ip1 = b_down1 ? pt_edge1->pclToVertex : pt_edge1->pclFromVertex;
2967 pcl_ip2 = b_down2 ? pt_edge2->pclToVertex : pt_edge2->pclFromVertex;
2968
2969 pcl_split_vertex = DCTPVecIsLesser(pcl_ip1->coords, pcl_ip2->coords) ?
2970 pcl_ip1 : pcl_ip2;
2971 }
2972 else
2973 {
2974 pcl_split_vertex = DCTPVecIsGreater(pcl_ip1->coords, pcl_ip2->coords) ?
2975 pcl_ip1 : pcl_ip2;
2976 }
2977 }
2978 else
2979 {
2980 // we have an intersection => find point
2981 // const double cd_v1x = ad_e1[ 0 ] - ad_s1[ 0 ];
2982 // const double cd_v1y = ad_e1[ 1 ] - ad_s1[ 1 ];
2983 // const double cd_v2x = ad_e2[ 0 ] - ad_s2[ 0 ];
2984 // const double cd_v2y = ad_e2[ 1 ] - ad_s2[ 1 ];
2985
2986 if( (cd_v1x * cd_v1x + cd_v1y * cd_v1y) < (cd_v2x * cd_v2x + cd_v2y * cd_v2y) )
2987 {
2988 const double cd_ppx = ad_s2[0] - ad_s1[0];
2989 const double cd_ppy = ad_s2[1] - ad_s1[1];
2990 const double cd_a = cd_ppx * cd_v2y - cd_ppy * cd_v2x;
2991 // const double cd_b = cd_v1x * cd_v2y - cd_v1y * cd_v2x;
2992 double d_q = cd_a / cd_b;
2993 // std::cerr << cd_a << " / " << cd_b << " = " << d_q;
2994 // std::cerr << cd_r1 << " " << cd_r2 << " " << cd_r3 << " " << cd_r4 << std::endl;
2995
2996 if(d_q < DCTP_EPS)
2997 {
2998 pcl_split_vertex = pt_edge1->pclFromVertex;
2999 }
3000 else if(1.0 - d_q < DCTP_EPS)
3001 {
3002 pcl_split_vertex = pt_edge1->pclToVertex;
3003 }
3004 else
3005 {
3006 Vec3d cl_ip;
3007
3008 cl_ip[0] = pt_edge1->pclFromVertex->coords[0] + cd_v1x * d_q;
3009 cl_ip[1] = pt_edge1->pclFromVertex->coords[1] + cd_v1y * d_q;
3010 // cl_ip[0] = 1e-7 * floor( ( pt_edge1->pclFromVertex->coords[0] + cd_v1x * d_q ) / 1e-7 );
3011 // cl_ip[1] = 1e-7 * floor( ( pt_edge1->pclFromVertex->coords[1] + cd_v1y * d_q ) / 1e-7 );
3012 cl_ip[2] = 0.0;
3013 pcl_split_vertex = mesh->AddVertex(cl_ip);
3014 }
3015 }
3016 else
3017 {
3018 const double cd_ppx = ad_s1[0] - ad_s2[0];
3019 const double cd_ppy = ad_s1[1] - ad_s2[1];
3020 const double cd_a = cd_ppx * cd_v1y - cd_ppy * cd_v1x;
3021 const double cd_b_ = cd_v2x * cd_v1y - cd_v2y * cd_v1x;
3022 double d_q = cd_a / cd_b_;
3023 // std::cerr << cd_a << " / " << cd_b_ << " = " << d_q;
3024 // std::cerr << cd_r1 << " " << cd_r2 << " " << cd_r3 << " " << cd_r4 << std::endl;
3025
3026 if(d_q < DCTP_EPS)
3027 {
3028 pcl_split_vertex = pt_edge2->pclFromVertex;
3029 }
3030 else if(1.0 - d_q < DCTP_EPS)
3031 {
3032 pcl_split_vertex = pt_edge2->pclToVertex;
3033 }
3034 else
3035 {
3036 Vec3d cl_ip;
3037
3038 cl_ip[0] = pt_edge2->pclFromVertex->coords[0] + cd_v2x * d_q;
3039 cl_ip[1] = pt_edge2->pclFromVertex->coords[1] + cd_v2y * d_q;
3040 // cl_ip[0] = 1e-7 * floor( ( pt_edge2->pclFromVertex->coords[0] + cd_v2x * d_q ) / 1e-7 );
3041 // cl_ip[1] = 1e-7 * floor( ( pt_edge2->pclFromVertex->coords[1] + cd_v2y * d_q ) / 1e-7 );
3042 cl_ip[2] = 0.0;
3043 pcl_split_vertex = mesh->AddVertex(cl_ip);
3044 }
3045 }
3046 }
3047
3048 // std::cerr << "intersection at " << pcl_split_vertex->coords << std::endl;
3049 // std::cerr << "edge1: " << pt_edge1->pclFromVertex->coords << " - " << pt_edge1->pclToVertex->coords << std::endl;
3050 // std::cerr << "edge2: " << pt_edge2->pclFromVertex->coords << " - " << pt_edge2->pclToVertex->coords << std::endl;
3051
3052 // now we have the point => split edges
3053 if( (pcl_split_vertex != pt_edge1->pclFromVertex) &&
3054 (pcl_split_vertex != pt_edge1->pclToVertex) )
3055 {
3056 // split edge1
3057 // std::cerr << "spliting edge1: " << pt_edge1->pclFromVertex->coords << " - " << pt_edge1->pclToVertex->coords << std::endl;
3058 pt_new_edge = new SScanLineEdge;
3059 if(DCTPVecIsLesser(pt_edge1->pclFromVertex->coords, pt_edge1->pclToVertex->coords) )
3060 {
3061 pt_new_edge->pclFromVertex = pt_edge1->pclFromVertex;
3062 if(pt_edge1->bInvalid)
3063 pt_new_edge->pclToVertex = pt_edge1->pclToVertex;
3064 else
3065 pt_new_edge->pclToVertex = pcl_split_vertex;
3066 pt_edge1->pclFromVertex = pcl_split_vertex;
3067 }
3068 else
3069 {
3070 pt_new_edge->pclToVertex = pt_edge1->pclToVertex;
3071 if(pt_edge1->bInvalid)
3072 pt_new_edge->pclFromVertex = pt_edge1->pclFromVertex;
3073 else
3074 pt_new_edge->pclFromVertex = pcl_split_vertex;
3075 pt_edge1->pclToVertex = pcl_split_vertex;
3076 }
3077 pt_new_edge->ptPrev = pt_edge1->ptPrev;
3078 if(pt_new_edge->ptPrev)
3079 pt_new_edge->ptPrev->ptNext = pt_new_edge;
3080 pt_new_edge->ptNext = pt_edge1->ptNext;
3081 if(pt_new_edge->ptNext)
3082 pt_new_edge->ptNext->ptPrev = pt_new_edge;
3083 pt_new_edge->ptEntry = pt_edge1->ptEntry;
3084 pt_new_edge->ptEntry->ptEdge = pt_new_edge;
3085 // pt_new_edge->uiOrigNum = pt_edge1->uiOrigNum;
3086 pt_new_edge->bInvalid = pt_edge1->bInvalid;
3087 pt_edge1->ptPrev = NULL;
3088 pt_edge1->ptNext = NULL;
3089 pt_edge1->ptEntry = NULL;
3090 pt_edge1->bInvalid = false;
3091 insertScanLineEvents(pt_new_edge, rsptEvents, 1); // first event was this
3092 insertScanLineEvents(pt_edge1, rsptEvents, 0); // second event already exists
3093 // std::cerr << "new edge1: " << pt_edge1->pclFromVertex->coords << " - " << pt_edge1->pclToVertex->coords << std::endl;
3094 // std::cerr << "new edge: " << pt_new_edge->pclFromVertex->coords << " - " << pt_new_edge->pclToVertex->coords << std::endl;
3095 pcl_split_vertex->vertexinfo = reinterpret_cast<void*>(1);
3096 }
3097 if( (pcl_split_vertex != pt_edge2->pclFromVertex) &&
3098 (pcl_split_vertex != pt_edge2->pclToVertex) )
3099 {
3100 // split edge2
3101 // std::cerr << "spliting edge2: " << pt_edge2->pclFromVertex->coords << " - " << pt_edge2->pclToVertex->coords << std::endl;
3102 pt_new_edge = new SScanLineEdge;
3103 if(DCTPVecIsLesser(pt_edge2->pclFromVertex->coords, pt_edge2->pclToVertex->coords) )
3104 {
3105 pt_new_edge->pclFromVertex = pt_edge2->pclFromVertex;
3106 if(pt_edge2->bInvalid)
3107 pt_new_edge->pclToVertex = pt_edge2->pclToVertex;
3108 else
3109 pt_new_edge->pclToVertex = pcl_split_vertex;
3110 pt_edge2->pclFromVertex = pcl_split_vertex;
3111 }
3112 else
3113 {
3114 pt_new_edge->pclToVertex = pt_edge2->pclToVertex;
3115 if(pt_edge2->bInvalid)
3116 pt_new_edge->pclFromVertex = pt_edge2->pclFromVertex;
3117 else
3118 pt_new_edge->pclFromVertex = pcl_split_vertex;
3119 pt_edge2->pclToVertex = pcl_split_vertex;
3120 }
3121 pt_new_edge->ptPrev = pt_edge2->ptPrev;
3122 if(pt_new_edge->ptPrev)
3123 pt_new_edge->ptPrev->ptNext = pt_new_edge;
3124 pt_new_edge->ptNext = pt_edge2->ptNext;
3125 if(pt_new_edge->ptNext)
3126 pt_new_edge->ptNext->ptPrev = pt_new_edge;
3127 pt_new_edge->ptEntry = pt_edge2->ptEntry;
3128 pt_new_edge->ptEntry->ptEdge = pt_new_edge;
3129 // pt_new_edge->uiOrigNum = pt_edge2->uiOrigNum;
3130 pt_new_edge->bInvalid = pt_edge2->bInvalid;
3131 pt_edge2->ptPrev = NULL;
3132 pt_edge2->ptNext = NULL;
3133 pt_edge2->ptEntry = NULL;
3134 pt_edge2->bInvalid = false;
3135 insertScanLineEvents(pt_new_edge, rsptEvents, 1); // first event was this
3136 insertScanLineEvents(pt_edge2, rsptEvents, 0); // second event already exists
3137 // std::cerr << "new edge2: " << pt_edge2->pclFromVertex->coords << " - " << pt_edge2->pclToVertex->coords << std::endl;
3138 // std::cerr << "new edge: " << pt_new_edge->pclFromVertex->coords << " - " << pt_new_edge->pclToVertex->coords << std::endl;
3139 pcl_split_vertex->vertexinfo = reinterpret_cast<void*>(1);
3140 }
3141 }
3142
3143 bool ParSpaceTrimmer::isSLEntryLess(SScanLineEdge *ptEdge1, SScanLineEdge *ptEdge2)
3144 {
3145 Vec2d top1;
3146 Vec2d bottom1;
3147 Vec2d top2;
3148 Vec2d bottom2;
3149
3150 /* std::cerr << ptEdge1 << " " << ptEdge2 << std::endl;
3151 std::cerr << ptEdge1->pclFromVertex << " " << ptEdge1->pclToVertex << std::endl;
3152 std::cerr << ptEdge2->pclFromVertex << " " << ptEdge2->pclToVertex << std::endl;*/
3153
3154 if(DCTPVecIsLesser(ptEdge1->pclFromVertex->coords, ptEdge1->pclToVertex->coords) )
3155 {
3156 top1[0] = ptEdge1->pclFromVertex->coords[0];
3157 top1[1] = ptEdge1->pclFromVertex->coords[1];
3158 bottom1[0] = ptEdge1->pclToVertex->coords[0];
3159 bottom1[1] = ptEdge1->pclToVertex->coords[1];
3160 }
3161 else
3162 {
3163 top1[0] = ptEdge1->pclToVertex->coords[0];
3164 top1[1] = ptEdge1->pclToVertex->coords[1];
3165 bottom1[0] = ptEdge1->pclFromVertex->coords[0];
3166 bottom1[1] = ptEdge1->pclFromVertex->coords[1];
3167 }
3168 if(DCTPVecIsLesser(ptEdge2->pclFromVertex->coords, ptEdge2->pclToVertex->coords) )
3169 {
3170 top2[0] = ptEdge2->pclFromVertex->coords[0];
3171 top2[1] = ptEdge2->pclFromVertex->coords[1];
3172 bottom2[0] = ptEdge2->pclToVertex->coords[0];
3173 bottom2[1] = ptEdge2->pclToVertex->coords[1];
3174 }
3175 else
3176 {
3177 top2[0] = ptEdge2->pclToVertex->coords[0];
3178 top2[1] = ptEdge2->pclToVertex->coords[1];
3179 bottom2[0] = ptEdge2->pclFromVertex->coords[0];
3180 bottom2[1] = ptEdge2->pclFromVertex->coords[1];
3181 }
3182 if(DCTPVecIsNotEqual(top1, top2) )
3183 {
3184 double ad_s1[2];
3185 // double ad_e1[ 2 ];
3186 double ad_s2[2];
3187 double ad_e2[2];
3188
3189 ad_s1[0] = top1[0];
3190 ad_s1[1] = top1[1];
3191 // ad_e1[ 0 ] = bottom1[0];
3192 // ad_e1[ 1 ] = bottom1[1];
3193 ad_s2[0] = top2[0];
3194 ad_s2[1] = top2[1];
3195 ad_e2[0] = bottom2[0];
3196 ad_e2[1] = bottom2[1];
3197
3198 const double cd_orient = orient2d(ad_s2, ad_e2, ad_s1);
3199 if(cd_orient != 0.0)
3200 {
3201 return (cd_orient > 0.0);
3202 }
3203 }
3204
3205 // check directions
3206 Vec2d dir1 = bottom1 - top1;
3207 Vec2d dir2 = bottom2 - top2;
3208
3209 if(osgAbs(dir1[1]) < DCTP_EPS)
3210 {
3211 if(osgAbs(dir2[1]) < DCTP_EPS)
3212 {
3213 return (dir1[0] < dir2[0]);
3214 }
3215 return (dir1[0] < 0.0); // this can't be zero!
3216 }
3217 if(osgAbs(dir2[1]) < DCTP_EPS)
3218 {
3219 return (dir2[0] > 0.0); // this can't be zero!
3220 }
3221
3222 const double r1 = dir1[0] / dir1[1];
3223 const double r2 = dir2[0] / dir2[1];
3224
3225 if(osgAbs(r1 - r2) >= DCTP_EPS)
3226 {
3227 return (r1 < r2);
3228 }
3229
3230 // this can only be false for both ways, if it is the same edge!
3231 return ptEdge1 <ptEdge2;
3232 }
3233
3234 void ParSpaceTrimmer::removeSLEntry(SScanLineEntry *ptEntry, ScanLineEventSet &rsptEvents)
3235 {
3236 SScanLineEvent *pt_new_event;
3237 std::pair<ScanLineEventSet::iterator, bool> pr_insert;
3238 Vec2d min;
3239 Vec2d max;
3240
3241 if(DCTPVecIsLesser(ptEntry->ptEdge->pclFromVertex->coords, ptEntry->ptEdge->pclToVertex->coords) )
3242 {
3243 min[0] = ptEntry->ptEdge->pclFromVertex->coords[0];
3244 min[1] = ptEntry->ptEdge->pclFromVertex->coords[1];
3245 max[0] = ptEntry->ptEdge->pclToVertex->coords[0];
3246 max[1] = ptEntry->ptEdge->pclToVertex->coords[1];
3247 }
3248 else if(DCTPVecIsEqual(ptEntry->ptEdge->pclFromVertex->coords,
3249 ptEntry->ptEdge->pclToVertex->coords) )
3250 {
3251 return;
3252 }
3253 else
3254 {
3255 min[0] = ptEntry->ptEdge->pclToVertex->coords[0];
3256 min[1] = ptEntry->ptEdge->pclToVertex->coords[1];
3257 max[0] = ptEntry->ptEdge->pclFromVertex->coords[0];
3258 max[1] = ptEntry->ptEdge->pclFromVertex->coords[1];
3259 }
3260
3261 // remove old event
3262 pt_new_event = new SScanLineEvent;
3263 pt_new_event->ptEdge = ptEntry->ptEdge;
3264 pt_new_event->bStart = false;
3265 pt_new_event->clPos = max;
3266 pt_new_event->clOther = min;
3267
3268 /* std::cerr << "remove scan line event: edge = " << pt_new_event->ptEdge;
3269 std::cerr << " start = " << pt_new_event->bStart;
3270 std::cerr << " pos = " << pt_new_event->clPos;
3271 std::cerr << " other = " << pt_new_event->clOther << std::endl;*/
3272 // std::cerr << " num = " << pt_new_event->ptEdge->uiOrigNum << std::endl;
3273
3274 unsigned int ui_old_size = UInt32(rsptEvents.size());
3275 // std::cerr << "remove scan line entry ";
3276 rsptEvents.erase(pt_new_event);
3277 // std::cerr << "ok";
3278 delete pt_new_event;
3279
3280 if(rsptEvents.size() == ui_old_size)
3281 {
3282 // std::cerr << "Event not found! searching: " << ptEntry->ptEdge << std::endl;
3283 for(ScanLineEventSet::iterator i = rsptEvents.begin(); i != rsptEvents.end(); ++i)
3284 {
3285 /* if( (*i)->bStart == 0 )
3286 std::cerr << (*i)->ptEdge << std::endl;*/
3287 if(/*( ( *i )->bStart == 0 ) &&*/ ( (*i)->ptEdge == ptEntry->ptEdge) )
3288 {
3289 rsptEvents.erase(i);
3290 break;
3291 }
3292 }
3293
3294 // exit( -1 );
3295 // return;
3296 }
3297
3298 // insert new event to delete edge instantly
3299 pt_new_event = new SScanLineEvent;
3300 pt_new_event->ptEdge = ptEntry->ptEdge;
3301 pt_new_event->bStart = false;
3302 pt_new_event->clPos = min;
3303 pt_new_event->clPos[1] -= 1.0;
3304 pt_new_event->clOther = min;
3305
3306 /* std::cerr << "replace scan line event: edge = " << pt_new_event->ptEdge;
3307 std::cerr << " start = " << pt_new_event->bStart;
3308 std::cerr << " pos = " << pt_new_event->clPos;
3309 std::cerr << " other = " << pt_new_event->clOther << std::endl;*/
3310 // std::cerr << " num = " << pt_new_event->ptEdge->uiOrigNum << std::endl;
3311 pr_insert = rsptEvents.insert(pt_new_event);
3312 if(!pr_insert.second)
3313 {
3314 std::cerr << "Scan line event exists! aborting." << std::endl;
3315 exit(-1);
3316 }
3317
3318 }
3319
3320 DCTPVertex *ParSpaceTrimmer::intersectsLoop(DCTPVertex *pclVertex1, DCTPVertex *pclVertex2, unsigned int uiLoop)
3321 {
3322 unsigned int ui_vertex;
3323 unsigned int ui_size = UInt32(vcel[uiLoop].size());
3324 DCTPVertex *pcl_prev_vertex;
3325 DCTPVertex *pcl_act_vertex = vcel[uiLoop][ui_size - 1];
3326 Vec3d cl_old;
3327
3328 for(ui_vertex = 0; ui_vertex < ui_size; ++ui_vertex)
3329 {
3330 pcl_prev_vertex = pcl_act_vertex;
3331 pcl_act_vertex = vcel[uiLoop][ui_vertex];
3332
3333 if( (DCTPVecIsNotEqual(pclVertex1->coords, pcl_prev_vertex->coords) ) &&
3334 (DCTPVecIsNotEqual(pclVertex1->coords, pcl_act_vertex->coords) ) &&
3335 (DCTPVecIsNotEqual(pclVertex2->coords, pcl_prev_vertex->coords) ) &&
3336 (DCTPVecIsNotEqual(pclVertex2->coords, pcl_act_vertex->coords) ) )
3337 {
3338
3339 double ad_s1[2];
3340 double ad_e1[2];
3341 double ad_s2[2];
3342 double ad_e2[2];
3343
3344 ad_s1[0] = pclVertex1->coords[0];
3345 ad_s1[1] = pclVertex1->coords[1];
3346 ad_e1[0] = pclVertex2->coords[0];
3347 ad_e1[1] = pclVertex2->coords[1];
3348 ad_s2[0] = pcl_prev_vertex->coords[0];
3349 ad_s2[1] = pcl_prev_vertex->coords[1];
3350 ad_e2[0] = pcl_act_vertex->coords[0];
3351 ad_e2[1] = pcl_act_vertex->coords[1];
3352
3353 const double cd_r1 = orient2d(ad_s1, ad_e1, ad_s2);
3354 const double cd_r2 = orient2d(ad_s1, ad_e1, ad_e2);
3355 if( ( (cd_r1 >= 0.0) || (cd_r2 >= 0.0) ) &&
3356 ( (cd_r1 <= 0.0) || (cd_r2 <= 0.0) ) )
3357 {
3358
3359 const double cd_r3 = orient2d(ad_s2, ad_e2, ad_s1);
3360 const double cd_r4 = orient2d(ad_s2, ad_e2, ad_e1);
3361 if( ( (cd_r3 >= 0.0) || (cd_r4 >= 0.0) ) &&
3362 ( (cd_r3 <= 0.0) || (cd_r4 <= 0.0) ) )
3363 {
3364 if( (cd_r1 == 0.0) && (cd_r2 == 0.0) && (cd_r3 == 0.0) && (cd_r4 == 0.0) )
3365 {
3366 const Vec3d ccl_v12 = pclVertex2->coords - pclVertex1->coords;
3367 const double cd_prod_a = ccl_v12.dot(pcl_act_vertex->coords - pclVertex1->coords);
3368 const double cd_prod_p = ccl_v12.dot(pcl_prev_vertex->coords - pclVertex1->coords);
3369 const double cd_qsize = ccl_v12.squareLength();
3370
3371 if( (cd_prod_a >= 0.0) && (cd_prod_a <= cd_qsize) )
3372 {
3373 if( (cd_prod_p >= 0.0) && (cd_prod_p <= cd_prod_a) )
3374 {
3375 return pcl_prev_vertex;
3376 }
3377 else
3378 {
3379 return pcl_act_vertex;
3380 }
3381 }
3382 else if( (cd_prod_p >= 0.0) && (cd_prod_p <= cd_qsize) )
3383 {
3384 return pcl_prev_vertex;
3385 }
3386 }
3387 else
3388 {
3389 // std::cerr << pclVertex1->coords << "->" << pclVertex2->coords << std::endl;
3390 // std::cerr << pcl_prev_vertex->coords << "->" << pcl_act_vertex->coords << std::endl;
3391 cl_old = pclVertex1->coords - pclVertex2->coords;
3392 if( (Vec2d(pclVertex1->coords - pcl_prev_vertex->coords) ).dot(Vec2d(cl_old) ) -
3393 (Vec2d(pclVertex1->coords - pcl_act_vertex->coords) ).dot(Vec2d(cl_old) ) < DCTP_EPS)
3394 {
3395 // std::cerr << "=>" << pcl_prev_vertex->coords << std::endl;
3396 return pcl_prev_vertex;
3397 }
3398 // std::cerr << "=>" << pcl_act_vertex->coords << std::endl;
3399 return pcl_act_vertex;
3400 }
3401 }
3402 }
3403 }
3404 }
3405
3406 return NULL;
3407 }
3408
3409 bool ParSpaceTrimmer::doIntersect(Vec2d clV1, Vec2d clV2, Vec2d clV3, Vec2d clV4, double &rdParam)
3410 {
3411 if(DCTPVecIsEqual(clV1, clV3) || DCTPVecIsEqual(clV1, clV4) )
3412 {
3413 if(DCTPVecIsEqual(clV1, clV3) )
3414 {
3415 clV3 = clV4;
3416 }
3417 const Vec2d v = clV3 - clV1;
3418 const Vec2d w = clV2 - clV1;
3419 const double c1 = v.dot(w);
3420 const double c2 = w.squareLength();
3421
3422 // std::cerr.precision( 10 );
3423 // std::cerr << clV1 << "->" << clV2 << "," << clV3;
3424
3425 // std::cerr << ":" << c2 << "," << c1 << std::endl;
3426
3427 if(c1 <= 0.0)
3428 {
3429 return false; // other direction
3430 }
3431 else if(c1 < c2)
3432 {
3433 if(DCTPVecIsNotEqual(clV1 + (w * (c1 / c2) ), clV3) )
3434 return false; // too far away
3435 }
3436 else
3437 {
3438 if(DCTPVecIsNotEqual(clV2, (clV1 + v * (c2 / c1) ) ) )
3439 return false; // too far away
3440 }
3441 rdParam = c1 / c2;
3442 if(rdParam < DCTP_EPS)
3443 {
3444 return false;
3445 }
3446 return true;
3447 }
3448
3449 double ad_s1[2];
3450 double ad_e1[2];
3451 double ad_s2[2];
3452 double ad_e2[2];
3453
3454 ad_s1[0] = clV1[0];
3455 ad_s1[1] = clV1[1];
3456 ad_e1[0] = clV2[0];
3457 ad_e1[1] = clV2[1];
3458 ad_s2[0] = clV3[0];
3459 ad_s2[1] = clV3[1];
3460 ad_e2[0] = clV4[0];
3461 ad_e2[1] = clV4[1];
3462
3463 const double cd_r3 = orient2d(ad_s2, ad_s1, ad_e1);
3464 const double cd_r4 = orient2d(ad_e2, ad_s1, ad_e1);
3465 if( ( (cd_r3 < 0.0) && (cd_r4 < 0.0) ) ||
3466 ( (cd_r3 > 0.0) && (cd_r4 > 0.0) ) )
3467 {
3468 return false;
3469 }
3470
3471 const double cd_r1 = orient2d(ad_s1, ad_s2, ad_e2);
3472 const double cd_r2 = orient2d(ad_e1, ad_s2, ad_e2);
3473 if( ( (cd_r1 < 0.0) && (cd_r2 < 0.0) ) ||
3474 ( (cd_r1 > 0.0) && (cd_r2 > 0.0) ) )
3475 {
3476 const Vec2d v = clV4 - clV3;
3477 const Vec2d w = clV2 - clV3;
3478 const double c1 = v.dot(w);
3479 const double c2 = v.squareLength();
3480 if(c1 <= 0.0)
3481 {
3482 if(DCTPVecIsNotEqual(clV2, clV3) )
3483 return false;
3484 }
3485 else if(c1 > c2)
3486 {
3487 if(DCTPVecIsNotEqual(clV2, clV4) )
3488 return false;
3489 }
3490 else
3491 {
3492 if(DCTPVecIsNotEqual(clV2, (clV3 + v * (c1 / c2) ) ) )
3493 return false;
3494 // std::cerr << clV2 << "<->" << ( clV3 + v * ( c1 / c2 ) ) << " (" << ( c1 / c2 ) << ")" << std::endl;
3495 }
3496 // std::cerr << "end near edge" << std::endl;
3497 rdParam = 1.0;
3498 return true;
3499 }
3500
3501 // std::cerr << clV1 << "->" << clV2 << std::endl;
3502 // std::cerr << clV3 << "->" << clV4 << std::endl;
3503 // std::cerr << cd_r1 << " " << cd_r2 << " " << cd_r3 << " " << cd_r4 << std::endl;
3504
3505 if( (cd_r1 == 0.0) && (cd_r2 == 0.0) &&
3506 (cd_r3 == 0.0) && (cd_r4 == 0.0) )
3507 {
3508 // std::cerr.precision( 12 );
3509 // edges are coliniear
3510 double d_tmp;
3511
3512 rdParam = -1.0;
3513 d_tmp = ( (clV4[0] - clV1[0]) * (clV2[0] - clV1[0])
3514 + (clV4[1] - clV1[1]) * (clV2[1] - clV1[1]) )
3515 / (clV2 - clV1).squareLength();
3516 // std::cerr << d_tmp << " ";
3517 if(d_tmp > DCTP_EPS)
3518 rdParam = d_tmp;
3519 d_tmp = ( (clV3[0] - clV1[0]) * (clV2[0] - clV1[0])
3520 + (clV3[1] - clV1[1]) * (clV2[1] - clV1[1]) )
3521 / (clV2 - clV1).squareLength();
3522 // std::cerr << d_tmp << std::endl;
3523 if(d_tmp > DCTP_EPS)
3524 {
3525 if( (rdParam < -0.5) || (d_tmp < rdParam) )
3526 rdParam = d_tmp;
3527 }
3528 // std::cerr << rdParam << std::endl;
3529
3530 return ( (rdParam > -0.5) && (rdParam <= 1.0) );
3531 }
3532
3533 if(cd_r1 == 0.0)
3534 {
3535 // intersection was in start point...
3536 return false;
3537 }
3538
3539 // we have an intersection => find point
3540 const double cd_v1x = ad_e1[0] - ad_s1[0];
3541 const double cd_v1y = ad_e1[1] - ad_s1[1];
3542 const double cd_v2x = ad_e2[0] - ad_s2[0];
3543 const double cd_v2y = ad_e2[1] - ad_s2[1];
3544 const double cd_ppx = ad_s2[0] - ad_s1[0];
3545 const double cd_ppy = ad_s2[1] - ad_s1[1];
3546 const double cd_a = cd_ppx * cd_v2y - cd_ppy * cd_v2x;
3547 const double cd_b = cd_v1x * cd_v2y - cd_v1y * cd_v2x;
3548
3549 rdParam = cd_a / cd_b;
3550 // std::cerr << cd_a << " / " << cd_b << " = " << rdParam << std::endl;
3551
3552 if(rdParam <= 0.0)
3553 {
3554 rdParam = 0.0;
3555 // intersection was in start point...
3556 // std::cerr << "int at start " << cd_r1 << std::endl;
3557 // return false;
3558 }
3559 if(rdParam >= 1.0)
3560 {
3561 rdParam = 1.0;
3562 }
3563 return true;
3564 }
3565
3566 void ParSpaceTrimmer::deleteVertexInfo()
3567 {
3568 dctpvertexset::iterator itspcl_end;
3569 dctpvertexset::iterator itspcl_v;
3570
3571 itspcl_end = mesh->vertices.end();
3572
3573 for(itspcl_v = mesh->vertices.begin(); itspcl_v != itspcl_end; ++itspcl_v)
3574 {
3575 if( (*itspcl_v)->vertexinfo)
3576 {
3577 #ifdef OSG_FORCE_NO_T_VERTICES
3578 delete (SPosNorm*)(*itspcl_v)->vertexinfo;
3579 #else
3580 delete static_cast<Vec3d*>((*itspcl_v)->vertexinfo);
3581 #endif
3582 (*itspcl_v)->vertexinfo = NULL;
3583 }
3584 }
3585 }
3586
3587
3588 bool ParSpaceTrimmer::isLoopValid(const unsigned int cuiLoop)
3589 {
3590 const unsigned int cui_loop_cnt = UInt32((*pvccrd).size());
3591 unsigned int ui_loop;
3592 unsigned int ui_edge_cnt;
3593 unsigned int ui_vertex_cnt;
3594 unsigned int ui_vertex;
3595 // SimplePolygon cl_check;
3596 Vec2d cl_ray_start;
3597 Vec2d cl_ray_end;
3598
3599 ui_vertex_cnt = UInt32((*pvccrd)[cuiLoop].size());
3600 /* cl_check.vertices.resize( ui_vertex_cnt );
3601 for( ui_vertex = 0; ui_vertex < ui_vertex_cnt; ++ui_vertex )
3602 {
3603 cl_check.vertices[ ui_vertex ] = ui_vertex;
3604 }
3605 if( cl_check.isReversed( ( *pvccrd )[ cuiLoop ] ) )
3606 {
3607 // std::cerr << "loop is reversed" << std::endl;
3608 ui_edge_cnt = 1;
3609 m_vbReversed[ cuiLoop ] = true;
3610 }
3611 else
3612 {
3613 // std::cerr << "loop is normal" << std::endl;
3614 ui_edge_cnt = 0;
3615 m_vbReversed[ cuiLoop ] = false;
3616 }*/
3617
3618 if( (*m_pvbReversed)[cuiLoop])
3619 {
3620 ui_edge_cnt = 1;
3621 }
3622 else
3623 {
3624 ui_edge_cnt = 0;
3625 }
3626
3627 cl_ray_start = ( (*pvccrd)[cuiLoop][0] + (*pvccrd)[cuiLoop][1]) * 0.5;
3628 // cl_ray_end[0] = -DBL_MAX;
3629 cl_ray_end[0] = -FLT_MAX;
3630 cl_ray_end[1] = cl_ray_start[1];
3631
3632 // std::cerr << "ray: " << cl_ray_start << " -> " << cl_ray_end << std::endl;
3633
3634 for(ui_loop = 0; ui_loop < cui_loop_cnt; ++ui_loop)
3635 {
3636 if(ui_loop != cuiLoop)
3637 {
3638 ui_vertex_cnt = UInt32((*pvccrd)[ui_loop].size());
3639
3640 for(ui_vertex = 0; ui_vertex < ui_vertex_cnt; ++ui_vertex)
3641 {
3642 // std::cerr << "check: " << ( *pvccrd )[ ui_loop ][ ui_vertex ] << " -> " << ( *pvccrd )[ ui_loop ][ ( ui_vertex + 1 ) % ui_vertex_cnt ] << std::endl;
3643 if(intersectsRay( (*pvccrd)[ui_loop][ui_vertex],
3644 (*pvccrd)[ui_loop][(ui_vertex + 1) % ui_vertex_cnt],
3645 cl_ray_start, cl_ray_end) )
3646 {
3647 // std::cerr << "intersect" << std::endl;
3648 ++ui_edge_cnt;
3649 }
3650 }
3651 }
3652 }
3653
3654 if( (ui_edge_cnt & 1) != 0)
3655 {
3656 // std::cerr << "loop is removed" << std::endl;
3657 }
3658
3659 return ( (ui_edge_cnt & 1) == 0);
3660 }
3661
3662
3663 bool ParSpaceTrimmer::intersectsRay(const Vec2d cclV1, const Vec2d cclV2, const Vec2d cclStart, const Vec2d cclEnd)
3664 {
3665 double ad_v1[2];
3666 double ad_v2[2];
3667 double ad_start[2];
3668 double ad_end[2];
3669
3670 if(DCTPVecIsLesser(cclV1, cclV2) )
3671 {
3672 ad_v1[0] = cclV1[0];
3673 ad_v1[1] = cclV1[1];
3674 ad_v2[0] = cclV2[0];
3675 ad_v2[1] = cclV2[1];
3676 }
3677 else
3678 {
3679 ad_v1[0] = cclV2[0];
3680 ad_v1[1] = cclV2[1];
3681 ad_v2[0] = cclV1[0];
3682 ad_v2[1] = cclV1[1];
3683 }
3684 ad_start[0] = cclStart[0];
3685 ad_start[1] = cclStart[1];
3686 ad_end[0] = cclEnd[0];
3687 ad_end[1] = cclEnd[1];
3688
3689 const double cd_c1 = orient2d(ad_start, ad_end, ad_v1);
3690
3691 if(cd_c1 == 0.0)
3692 {
3693 return false; // not at start of edge
3694 }
3695
3696 const double cd_c2 = orient2d(ad_start, ad_end, ad_v2);
3697
3698 if( ( (cd_c1 < 0.0) && (cd_c2 < 0.0) ) || ( (cd_c1 > 0.0) && (cd_c2 > 0.0) ) )
3699 {
3700 return false;
3701 }
3702
3703 const double cd_c3 = orient2d(ad_v1, ad_v2, ad_start);
3704 const double cd_c4 = orient2d(ad_v1, ad_v2, ad_end);
3705
3706 if( ( (cd_c3 < 0.0) && (cd_c4 < 0.0) ) || ( (cd_c3 > 0.0) && (cd_c4 > 0.0) ) )
3707 {
3708 return false;
3709 }
3710
3711 return true;
3712 }
3713
3714
3715 #ifdef OSG_USE_SIMPLIFIER
3716 double ParSpaceTrimmer::DistToEdge(const Vec3d cclPoint, const Vec3d cclLine1, const Vec3d cclLine2) const
3717 {
3718 const Vec3d ccl_v = cclLine2 - cclLine1;
3719 const Vec3d ccl_w = cclPoint - cclLine1;
3720
3721 const double cd_c1 = ccl_v[0] * ccl_w[0] + ccl_v[1] * ccl_w[1] + ccl_v[2] * ccl_w[2];
3722
3723 if(cd_c1 <= 0.0)
3724 {
3725 return (cclPoint - cclLine1).squareLength();
3726 }
3727
3728 const double cd_c2 = ccl_v.squareLength();
3729
3730 if(cd_c1 >= cd_c2)
3731 {
3732 return (cclPoint - cclLine2).squareLength();
3733 }
3734
3735 return (cclPoint - (cclLine1 + ccl_v * (cd_c1 / cd_c2) ) ).squareLength();
3736 }
3737 #endif