00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include "OSGParSpaceTrimmer.h"
00039 #ifdef OSG_ADAPTIVE_QUAD_TREE
00040 #include "OSGQuadTreeCreator.h"
00041 #endif
00042 #include "OSGSimplePolygon.h"
00043
00044 #include "OSGpredicates.h"
00045 #include <float.h>
00046
00047 OSG_USING_NAMESPACE
00048
00049 #ifdef OSG_WIN32_ICL
00050 #pragma warning( disable : 171 )
00051 #endif
00052
00053 #ifdef WIN32
00054 #pragma warning (disable : 985)
00055 #endif
00056
00057 #ifdef _DEBUG
00058 #ifdef OSG_WIN32
00059 #undef THIS_FILE
00060 static char THIS_FILE[] = __FILE__;
00061 #endif
00062 #endif
00063
00064 #ifdef OSG_USE_SIMPLIFIER
00065 #define OSG_SIMPLIFIER_TESS_ERR 0.75
00066 #endif
00067
00068 #define ROUND_EPS 1e-6
00069
00070 #define OSG_SPLIT_HOLE_CELLS
00071
00072 bool ParSpaceTrimmer::isOverQuad(DCTPFace *f, Vec2d &p)
00073 {
00074 #ifdef OSG_UNION_TRI_QUAD
00075
00076
00077
00078
00079
00080 if(p[0] >= f->orig_face[0]->coords[0] &&
00081 p[0] <= f->orig_face[1]->coords[0] &&
00082 p[1] <= f->orig_face[0]->coords[1] &&
00083 p[1] >= f->orig_face[3]->coords[1])
00084 #else
00085
00086
00087
00088
00089
00090 if(p[0] >= f->orig_quad[0]->coords[0] &&
00091 p[0] <= f->orig_quad[1]->coords[0] &&
00092 p[1] <= f->orig_quad[0]->coords[1] &&
00093 p[1] >= f->orig_quad[3]->coords[1])
00094 #endif
00095
00096
00097
00098 return true;
00099 else
00100 return false;
00101 }
00102
00103 bool ParSpaceTrimmer::isNearQuad(DCTPFace *f, Vec2d &p)
00104 {
00105
00106
00107
00108
00109
00110
00111
00112 #ifdef OSG_UNION_TRI_QUAD
00113 if( (p[0] - f->orig_face[0]->coords[0] > -DCTP_EPS * 2.0) &&
00114 (p[0] - f->orig_face[1]->coords[0] < DCTP_EPS * 2.0) &&
00115 (p[1] - f->orig_face[0]->coords[1] < DCTP_EPS * 2.0) &&
00116 (p[1] - f->orig_face[3]->coords[1] > -DCTP_EPS * 2.0) )
00117 #else
00118 if( (p[0] - f->orig_quad[0]->coords[0] > -DCTP_EPS * 2.0) &&
00119 (p[0] - f->orig_quad[1]->coords[0] < DCTP_EPS * 2.0) &&
00120 (p[1] - f->orig_quad[0]->coords[1] < DCTP_EPS * 2.0) &&
00121 (p[1] - f->orig_quad[3]->coords[1] > -DCTP_EPS * 2.0) )
00122 #endif
00123
00124
00125
00126 return true;
00127 else
00128 return false;
00129 }
00130
00131 bool ParSpaceTrimmer::isOverFace(DCTPFace *f, Vec2d &p)
00132 {
00133 return isOverQuad(f, p);
00134 }
00135
00136 void ParSpaceTrimmer::getStartingFace(Vec2d p)
00137 {
00138 dctpfacevector::iterator fend = mesh->faces.end();
00139 dctpfacevector::iterator i;
00140
00141 if(p[0] < m_clMin[0])
00142 p[0] = m_clMin[0];
00143 else if(p[0] > m_clMax[0])
00144 p[0] = m_clMax[0];
00145 if(p[1] < m_clMin[1])
00146 p[1] = m_clMin[1];
00147 else if(p[1] > m_clMax[1])
00148 p[1] = m_clMax[1];
00149
00150 for(i = mesh->faces.begin(); i != fend; ++i)
00151 {
00152 if(isOverFace(*i, p) )
00153 {
00154 state.state = TrimState::OVER_FACE;
00155 state.f = *i;
00156 return;
00157 }
00158 }
00159
00160 for(i = mesh->faces.begin(); i != fend; ++i)
00161 {
00162 if(isNearQuad(*i, p) )
00163 {
00164 state.state = TrimState::OVER_FACE;
00165 state.f = *i;
00166 return;
00167 }
00168 }
00169
00170
00171 std::cerr << "Couldn't find starting face!" << std::endl;
00172
00173 throw ParSpaceTrimmerError(ERR_NO_STARTING_FACE);
00174 }
00175
00176 bool ParSpaceTrimmer::isOnSection(Vec2d &p1, Vec2d &p2, Vec2d &p)
00177 {
00178
00179 Vec2d norm, t;
00180 double dist;
00181 double par;
00182 double lab = sqrt( (p1[0] - p2[0]) * (p1[0] - p2[0]) +
00183 (p1[1] - p2[1]) * (p1[1] - p2[1]) );
00184 norm[0] = -(p2[1] - p1[1]) / lab;
00185 norm[1] = (p2[0] - p1[0]) / lab;
00186
00187 t[0] = p[0] - p1[0];
00188 t[1] = p[1] - p1[1];
00189 dist = t[0] * norm[0] + t[1] * norm[1];
00190 if(osgAbs(dist) < DCTP_EPS)
00191 {
00192
00193 if(osgAbs(p2[0] - p1[0]) > DCTP_EPS)
00194 par = (p[0] - p1[0]) / (p2[0] - p1[0]);
00195 else
00196 par = (p[1] - p1[1]) / (p2[1] - p1[1]);
00197 if(par < -DCTP_EPS || par > (1 + DCTP_EPS) )
00198 return false;
00199 else
00200 return true;
00201 }
00202 else
00203 return false;
00204 }
00205
00206 bool ParSpaceTrimmer::isOnEdge(DCTPEdge *e, Vec2d &p, DCTPVertex* &v)
00207 {
00208 DCTPVertex *v1, *v2;
00209 e->getVertices(v1, v2);
00210 Vec2d v1coords(v1->coords[0], v1->coords[1]);
00211 Vec2d v2coords(v2->coords[0], v2->coords[1]);
00212 if(DCTPVecIsEqual(p, v1coords) )
00213 {
00214 v = v1;
00215 return true;
00216 }
00217 if(DCTPVecIsEqual(p, v2coords) )
00218 {
00219 v = v2;
00220 return true;
00221 }
00222 v = NULL;
00223 return isOnSection(v1coords, v2coords, p);
00224 }
00225
00226 void *ParSpaceTrimmer::isOnFaceBoundary(DCTPFace *f, Vec2d &p, bool& isedge)
00227
00228
00229
00230 {
00231 std::vector<DCTPEdge *>::iterator eend = f->edges.end();
00232
00233 for(std::vector<DCTPEdge *>::iterator i = f->edges.begin(); i != eend; ++i)
00234 {
00235 DCTPVertex *v;
00236
00237 isedge = isOnEdge(*i, p, v);
00238 if(isedge)
00239 {
00240 if(v)
00241 {
00242 isedge = false;
00243 return v;
00244 }
00245 else
00246 {
00247 return *i;
00248 }
00249 }
00250 }
00251
00252 return NULL;
00253 }
00254
00255 void ParSpaceTrimmer::initializeStartState(bezier2ddeque& tc)
00256 {
00257
00258
00259 BezierCurve2D & b = tc[0];
00260 DCTPVec3dvector &cp = b.getControlPointVector();
00261 Vec2d p;
00262 p[0] = cp[0][0] / cp[0][2];
00263 p[1] = cp[0][1] / cp[0][2];
00264 getStartingFace(p);
00265
00266 start_face = NULL;
00267 bool isedge;
00268 void *ptr;
00269 if( (ptr = isOnFaceBoundary(state.f, p, isedge) ) )
00270 {
00271 state.state = TrimState::IN_VERTEX;
00272 if(!isedge)
00273 {
00274
00275 state.v = static_cast<DCTPVertex*>(ptr);
00276 }
00277 else
00278 {
00279
00280
00281 Vec3d p3d = Vec3d(p);
00282
00283 state.v = mesh->findVertex(p3d);
00284 if(state.v == NULL)
00285 {
00286 state.v = new DCTPVertex;
00287 state.v->coords = p3d;
00288 state.v->faces = (static_cast<DCTPEdge*>(ptr) )->faces;
00289
00290 state.v->edges.push_back(static_cast<DCTPEdge*>(ptr) );
00291 }
00292 state.v->vertexinfo = reinterpret_cast<void*>(1);
00293 }
00294 }
00295 else
00296 {
00297
00298
00299
00300
00301 start_face = state.f;
00302 }
00303
00304 }
00305
00306 void ParSpaceTrimmer::initializeStartState2(unsigned int uiLoop, std::vector<DCTPVertex*> &el)
00307 {
00308
00309
00310 const unsigned int cui_size = (*pvccrd)[uiLoop].size();
00311 Vec2d & p = (*pvccrd)[uiLoop][cui_size - 1];
00312 Vec3d & rcl_s = (*m_pvvclSewed)[uiLoop][cui_size - 1];
00313 #ifdef OSG_FORCE_NO_T_VERTICES
00314
00315
00316
00317 #endif
00318
00319
00320
00321
00322
00323
00324 getStartingFace(p);
00325
00326
00327
00328 start_face = NULL;
00329 bool isedge;
00330 void *ptr;
00331 if( (ptr = isOnFaceBoundary(state.f, p, isedge) ) )
00332 {
00333 state.state = TrimState::IN_VERTEX;
00334 if(!isedge)
00335 {
00336
00337 state.v = static_cast<DCTPVertex*>(ptr);
00338 }
00339 else
00340 {
00341
00342
00343 Vec3d p3d = Vec3d(p);
00344 state.v = mesh->SplitEdge(static_cast<DCTPEdge*>(ptr), p3d);
00345
00346 }
00347 #ifdef OSG_FORCE_NO_T_VERTICES
00348 SPosNorm *pt_s = new SPosNorm;
00349 pt_s->clPos = rcl_s;
00350
00351
00352
00353 #ifdef OSG_KEEP_2D_POINTS
00354 pt_s->uiNum = m_uiPosCnt;
00355 #endif
00356 state.v->vertexinfo = static_cast<void*>(pt_s);
00357 #else
00358 Vec3d *pcl_s = new Vec3d(rcl_s);
00359 state.v->vertexinfo = static_cast<void*>(pcl_s);
00360 #endif
00361
00362 el.push_back(state.v);
00363 }
00364 else
00365 {
00366
00367 start_face = state.f;
00368 DCTPVertex *pcl_v = mesh->AddVertex(Vec3d(p) );
00369 #ifdef OSG_FORCE_NO_T_VERTICES
00370 SPosNorm *pt_s = new SPosNorm;
00371 pt_s->clPos = rcl_s;
00372
00373
00374
00375 #ifdef OSG_KEEP_2D_POINTS
00376 pt_s->uiNum = m_uiPosCnt;
00377 #endif
00378 pcl_v->vertexinfo = ( void* ) pt_s;
00379 #else
00380 Vec3d *pcl_s = new Vec3d(rcl_s);
00381 pcl_v->vertexinfo = pcl_s;
00382 #endif
00383
00384 el.push_back(pcl_v);
00385 }
00386
00387 }
00388
00389 bool ParSpaceTrimmer::setMinIntersectionWithFace(BezierCurve2D &b)
00390 {
00391 ip = 1.5;
00392 bool intersection = false;
00393 std::vector<DCTPEdge *>::iterator eend = state.f->edges.end();
00394
00395
00396
00397
00398 DCTPVec3dvector &cptemp = b.getControlPointVector();
00399 Vec2d cp0eucl;
00400 cp0eucl[0] = cptemp[0][0] / cptemp[0][2];
00401 cp0eucl[1] = cptemp[0][1] / cptemp[0][2];
00402
00403 if(cptemp.size() == 2 && DCTPVecIsEqual(cptemp[0], cptemp[1]) )
00404 throw ParSpaceTrimmerError(ERR_DEGENERATE_BEZIER);
00405
00406
00409 for(std::vector<DCTPEdge *>::iterator i = state.f->edges.begin();
00410 i != eend; ++i)
00411 {
00412 DCTPdvector res;
00413 DCTPVertex *v1, *v2;
00414 (*i)->getVertices(v1, v2);
00415 Vec2d v1coords(v1->coords[0], v1->coords[1]);
00416 Vec2d v2coords(v2->coords[0], v2->coords[1]);
00417
00418 int err;
00419 err = b.intersection(res, v1coords, v2coords);
00420 if(err < 0)
00421 {
00422
00423 std::cerr << "Brutal error " << err << " in: " <<
00424 "ParSpaceTrimmer::setMinIntersectionWithFace" << std::endl;
00425 throw ParSpaceTrimmerError(ERR_SET_MININTERSECTION);
00426 }
00430
00431
00432 if(res.size() != 0)
00433 {
00434
00435 const Vec2d ccl_temp = b.computewdeCasteljau(res[0], err);
00436
00437 if(DCTPVecIsNotEqual(ccl_temp, cp0eucl) && res[0] < ip)
00438 {
00439 ip = res[0];
00440 ie = *i;
00441 intersection = true;
00442 }
00443
00444 else if(res.size() >= 2 && DCTPVecIsEqual(ccl_temp, cp0eucl) && res[1] < ip)
00445 {
00446 const Vec2d ccl_temp2 = b.computewdeCasteljau(res[0], err);
00447 if(DCTPVecIsNotEqual(ccl_temp2, cp0eucl) )
00448 {
00449 ip = res[1];
00450 ie = *i;
00451 intersection = true;
00452 }
00453 }
00454 }
00455
00456 }
00457
00458 return intersection;
00459 }
00460
00461 bool ParSpaceTrimmer::setMinIntersectionWithFace2(Vec2d clAct, Vec2d clNext)
00462 {
00463 ip = 1.5;
00464 bool intersection = false;
00465 std::vector<DCTPEdge *>::iterator eend = state.f->edges.end();
00466
00467
00468
00469
00470 if(DCTPVecIsEqual(clAct, clNext) )
00471 throw ParSpaceTrimmerError(ERR_DEGENERATE_BEZIER);
00472
00473 for(std::vector<DCTPEdge *>::iterator i = state.f->edges.begin();
00474 i != eend; ++i)
00475 {
00476 double res;
00477 DCTPVertex *v1, *v2;
00478 (*i)->getVertices(v1, v2);
00479 Vec2d v1coords(v1->coords[0], v1->coords[1]);
00480 Vec2d v2coords(v2->coords[0], v2->coords[1]);
00481
00482 if(doIntersect(clAct, clNext, v1coords, v2coords, res) )
00483 {
00484 if( (res - 1.0 < DCTP_EPS) && (res > 1e-16) )
00485 {
00486
00487 if(res < ip)
00488 {
00489 ie = *i;
00490 ip = res;
00491 }
00492 intersection = true;
00493 }
00494 }
00495 }
00496
00497 return intersection;
00498 }
00499
00500 bool ParSpaceTrimmer::StoreCurveApproximation(
00501 BezierCurve2D & bc,
00502 double t,
00503 std::vector<DCTPVertex*> &el)
00504 {
00505 bezier2dvector nc;
00506 bool rest_left;
00507 double & norm = state.f->norm;
00508 DCTPVec2dvector approx;
00509
00510
00511
00512 if(1.0 - t < DCTP_EPS)
00513 {
00514 rest_left = false;
00515 DCTPVec3dvector vcp = bc.getControlPointVector();
00516
00517
00518 nc.push_back(bc);
00519 vcp = nc[0].getControlPointVector();
00520
00521 }
00522 else
00523 {
00524 bc.subDivision(t, nc);
00525 bc = nc[1];
00526 rest_left = true;
00527 }
00528
00529
00530
00531 nc[0].approximate(approx, norm);
00532
00533 if(approx.size() >= 2)
00534 {
00535 DCTPVec2dvector::iterator ae = approx.end();
00536
00537 for(DCTPVec2dvector::iterator i = approx.begin() + 1; i != ae; ++i)
00538 {
00539 (*i)[0] = ROUND_EPS * floor( (*i)[0] / ROUND_EPS + 0.5);
00540 (*i)[1] = ROUND_EPS * floor( (*i)[1] / ROUND_EPS + 0.5);
00541
00542 DCTPVertex *pcl_new = mesh->findVertex(Vec3d(*i) );
00543 if(pcl_new == NULL)
00544 {
00545 pcl_new = new DCTPVertex;
00546 pcl_new->coords = Vec3d(*i);
00547 }
00548
00549 el.push_back(pcl_new);
00550 }
00551 }
00552
00553 return rest_left;
00554 }
00555
00556
00557
00558
00559
00560
00561
00564
00565
00566
00567
00568
00569
00570
00571
00572
00573
00574
00575
00576
00577
00578
00579
00580
00581
00582
00583
00584
00585
00586
00587 bool ParSpaceTrimmer::goingOutOnEdge(BezierCurve2D &bc,
00588 DCTPVertex* &v, bool &feu,
00589 std::vector<DCTPVertex*> &el)
00590 {
00591
00593 std::vector<DCTPEdge *>::iterator eend = state.v->edges.end();
00594
00595 for(std::vector<DCTPEdge *>::iterator i = state.v->edges.begin();
00596 i != eend; ++i)
00597 {
00598 DCTPVertex *v1,*v2;
00599 (*i)->getVertices(v1, v2);
00600 DCTPdvector res;
00601
00602
00603
00604 Vec2d v1coords(v1->coords[0], v1->coords[1]);
00605 Vec2d v2coords(v2->coords[0], v2->coords[1]);
00606
00607 DCTPVec3dvector &cptemp = bc.getControlPointVector();
00608 if(cptemp.size() == 2 && DCTPVecIsEqual(cptemp[0], cptemp[1]) )
00609 throw ParSpaceTrimmerError(ERR_DEGENERATE_BEZIER);
00610
00611 int r = bc.intersection(res, v1coords, v2coords);
00612
00613
00614 if(res.size() == 2)
00615 {
00616
00617 if( (r == 2) && (res[1] - 1.0 > -DCTP_EPS) )
00618 r = 1;
00619 }
00620 switch(r) {
00621 case 1:
00622 {
00623 DCTPVec3dvector &cp = bc.getControlPointVector();
00624 Vec2d cpeucl;
00625 cpeucl[0] = cp[cp.size() - 1][0] / cp[cp.size() - 1][2];
00626 cpeucl[1] = cp[cp.size() - 1][1] / cp[cp.size() - 1][2];
00627
00628
00629 Vec3d cp3d(ROUND_EPS * floor(cpeucl[0] / ROUND_EPS + 0.5),
00630 ROUND_EPS * floor(cpeucl[1] / ROUND_EPS + 0.5) );
00631
00632
00633 v = mesh->findVertex(cp3d);
00634 if(v == NULL)
00635 {
00636 v = new DCTPVertex;
00637 v->coords = cp3d;
00638 v->faces = (*i)->faces;
00639 v->edges.push_back(*i);
00640
00641 }
00642
00643 el.push_back(v);
00644 feu = true;
00645 return true;
00646 }
00647 case 2:
00648 {
00649 bezier2dvector nc;
00650
00651
00652
00653
00654
00655
00656 bc.subDivision(res[1], nc);
00657 bc = nc[1];
00659
00660
00661
00662
00663 DCTPVec3dvector &cp2 =
00664 nc[0].getControlPointVector();
00665 Vec2d cpeucl;
00666 cpeucl[0] = cp2[0][0] / cp2[0][2];
00667 cpeucl[1] = cp2[0][1] / cp2[0][2];
00668
00669 if(DCTPVecIsEqual(cpeucl, v1coords) )
00670 v = v2;
00671 else
00672 v = v1;
00673
00674 el.push_back(v);
00675
00676
00677
00678
00679
00680 feu = false;
00681 return true;
00682 }
00683 }
00684 }
00685
00686 return false;
00687 }
00688
00689 bool ParSpaceTrimmer::goingOutOnEdge2(Vec2d clAct, Vec2d clNext,
00690 DCTPVertex* &v, bool &feu,
00691 std::vector<DCTPVertex*> &el)
00692 {
00693
00694
00695 std::vector<DCTPEdge *>::iterator eend = state.v->edges.end();
00696
00697 for(std::vector<DCTPEdge *>::iterator i = state.v->edges.begin();
00698 i != eend; ++i)
00699 {
00700 if( (*i)->faces.size() != 0)
00701 {
00702 DCTPVertex *v1,*v2;
00703 (*i)->getVertices(v1, v2);
00704 double res;
00705
00706
00707
00708 Vec2d v1coords(v1->coords[0], v1->coords[1]);
00709 Vec2d v2coords(v2->coords[0], v2->coords[1]);
00710
00711 if(DCTPVecIsEqual(clAct, clNext) )
00712 throw ParSpaceTrimmerError(ERR_DEGENERATE_BEZIER);
00713
00714 if(doIntersect(clAct, clNext, v1coords, v2coords, res) )
00715 {
00716 if(res - 1.0 > DCTP_EPS)
00717 {
00718 Vec3d cp3d(clNext[0], clNext[1]);
00719 v = mesh->SplitEdge(*i, cp3d);
00720 if(v == NULL)
00721 {
00722 std::cerr << "SplitEdge Failed!" << std::endl;
00723
00724
00725 }
00726 else
00727 {
00728
00729 feu = true;
00730 return true;
00731 }
00732 }
00733 else if(res - 1.0 < -DCTP_EPS)
00734 {
00735 Vec3d cp3p = Vec3d(clAct + (clNext - clAct) * res);
00736 if( (cp3p - Vec3d(v1coords)).squareLength() <
00737 (cp3p - Vec3d(v2coords)).squareLength() )
00738 v = v1;
00739 else
00740 v = v2;
00741
00742 feu = (DCTPVecIsEqual(cp3p, Vec3d(clNext) ) );
00743 ip = res;
00744 return true;
00745 }
00746 else
00747 {
00748 Vec3d cp3d(clNext[0], clNext[1]);
00749 if( (cp3d - Vec3d(v1coords)).squareLength() <
00750 (cp3d - Vec3d(v2coords)).squareLength() )
00751 v = v1;
00752 else
00753 v = v2;
00754
00755 feu = true;
00756 return true;
00757 }
00758 }
00759 }
00760 }
00761
00762
00763 return false;
00764 }
00765
00766 DCTPFace* ParSpaceTrimmer::getContinuingFace(BezierCurve2D &bc)
00767 {
00768
00769 int err;
00770 double high = 1.0, low = 0.0;
00771
00772 const Vec3d &cp0hom = bc.getControlPointVector()[0];
00773 Vec2d cp0;
00774 cp0[0] = cp0hom[0] / cp0hom[2];
00775 cp0[1] = cp0hom[1] / cp0hom[2];
00776
00777 Vec2d p = bc.computewdeCasteljau(high, err);
00778 if(p[0] < m_clMin[0])
00779 p[0] = m_clMin[0];
00780 else if(p[0] > m_clMax[0])
00781 p[0] = m_clMax[0];
00782 if(p[1] < m_clMin[1])
00783 p[1] = m_clMin[1];
00784 else if(p[1] > m_clMax[1])
00785 p[1] = m_clMax[1];
00786 while(high - low > DCTP_EPS)
00787 {
00788
00789
00790 double mid = 1 * DCTP_EPS / sqrt( (p - cp0).squareLength() );
00791 mid = osgMin(0.9, osgMax(0.1, mid) );
00792 mid = low + (high - low) * mid;
00793 Vec2d ptmp = bc.computewdeCasteljau(mid, err);
00794 if(ptmp[0] < m_clMin[0])
00795 ptmp[0] = m_clMin[0];
00796 else if(ptmp[0] > m_clMax[0])
00797 ptmp[0] = m_clMax[0];
00798 if(ptmp[1] < m_clMin[1])
00799 ptmp[1] = m_clMin[1];
00800 else if(ptmp[1] > m_clMax[1])
00801 ptmp[1] = m_clMax[1];
00802 if(DCTPVecIsEqual(cp0, ptmp) )
00803 {
00804 if(DCTPVecIsEqual(p, ptmp) )
00805 {
00806 break;
00807 }
00808 low = mid;
00809 }
00810 else
00811 {
00812 high = mid;
00813 p = ptmp;
00814 }
00815 }
00816
00817
00818
00820 std::vector<DCTPFace *>::iterator fe = state.v->faces.end();
00821 std::vector<DCTPFace *>::iterator i;
00822
00823
00824 for(i = state.v->faces.begin(); i != fe; ++i)
00825 {
00826 if(isOverFace(*i, p) )
00827 return *i;
00828 }
00829
00830 for(i = state.v->faces.begin(); i != fe; ++i)
00831 {
00832 if(isNearQuad(*i, p) )
00833 return *i;
00834 }
00835
00836
00837 getStartingFace(p);
00838 return state.f;
00839 }
00840
00841 DCTPFace* ParSpaceTrimmer::getContinuingFace2(Vec2d clAct, Vec2d clNext)
00842 {
00843
00844
00845
00846
00847
00848 if(clAct[0] < m_clMin[0])
00849 clAct[0] = m_clMin[0];
00850 else if(clAct[0] > m_clMax[0])
00851 clAct[0] = m_clMax[0];
00852 if(clAct[1] < m_clMin[1])
00853 clAct[1] = m_clMin[1];
00854 else if(clAct[1] > m_clMax[1])
00855 clAct[1] = m_clMax[1];
00856 if(clNext[0] < m_clMin[0])
00857 clNext[0] = m_clMin[0];
00858 else if(clNext[0] > m_clMax[0])
00859 clNext[0] = m_clMax[0];
00860 if(clNext[1] < m_clMin[1])
00861 clNext[1] = m_clMin[1];
00862 else if(clNext[1] > m_clMax[1])
00863 clNext[1] = m_clMax[1];
00864
00865
00866
00867
00868
00869
00870
00871
00872
00873
00874
00875
00876
00877
00878
00879
00880
00881
00882 Vec2d p;
00883
00884 p = clNext - clAct;
00885 if(osgAbs(p[0]) > DCTP_EPS)
00886 {
00887 p[0] = DCTP_EPS * p[0] / osgAbs(p[0]);
00888 }
00889 if(osgAbs(p[1]) > DCTP_EPS)
00890 {
00891 p[1] = DCTP_EPS * p[1] / osgAbs(p[1]);
00892 }
00893 p += clAct;
00894
00895
00897 std::vector<DCTPFace *>::iterator fe = state.v->faces.end();
00898
00899
00900
00901 for(std::vector<DCTPFace *>::iterator i = state.v->faces.begin();
00902 i != fe; ++i)
00903 {
00904
00905
00906
00907
00908 if(isOverFace(*i, p) )
00909 return *i;
00910 }
00911
00912
00913 getStartingFace(p);
00914 return state.f;
00915 }
00916
00917 bool ParSpaceTrimmer::StateTransition(BezierCurve2D &b, std::vector<DCTPVertex*> &el)
00918 {
00919 if(state.state == TrimState::OVER_FACE)
00920 {
00921 #ifdef OSG_ADAPTIVE_QUAD_TREE
00922 if(state.f->norm < DCTP_EPS)
00923 {
00924 while(m_pclQuadTree->computeApproximationError(state.f) > m_pclQuadTree->error_epsilon)
00925 {
00926
00927
00928
00929 mesh->SubdivideQuad(state.f);
00930 m_pclQuadTree->finishSubdivisions(state.f);
00931 const Vec3d &cp0hom = b.getControlPointVector()[0];
00932 Vec2d cp0;
00933 cp0[0] = cp0hom[0] / cp0hom[2];
00934 cp0[1] = cp0hom[1] / cp0hom[2];
00935
00936 if(!isOverFace(state.f, cp0) )
00937 {
00938 if(isOverFace(mesh->faces[mesh->faces.size() - 3], cp0) )
00939 {
00940 state.f = mesh->faces[mesh->faces.size() - 3];
00941 }
00942 else if(isOverFace(mesh->faces[mesh->faces.size() - 2], cp0) )
00943 {
00944 state.f = mesh->faces[mesh->faces.size() - 2];
00945 }
00946 else
00947 {
00948 state.f = mesh->faces[mesh->faces.size() - 1];
00949 }
00950 }
00951 }
00952 state.f->norm = m_pclQuadTree->error_epsilon / m_pclQuadTree->computeBilinearNorm(state.f);
00953
00954 }
00955 #endif
00956
00957
00958 if(setMinIntersectionWithFace(b) )
00959 {
00960 int err;
00961 Vec3d p = Vec3d(b.computewdeCasteljau(ip, err) );
00962
00963
00964 DCTPVertex *vp = mesh->findVertex(p);
00965 if(vp == NULL)
00966 {
00967 vp = new DCTPVertex;
00968 vp->coords = p;
00969 vp->faces = ie->faces;
00970 vp->edges.push_back(ie);
00971
00972
00973
00974
00975
00976 }
00977 if(!vp)
00978 {
00979 std::cerr << "Brutal error I. in: "
00980 << "ParSpaceTrimmer::StateTransition"
00981 << std::endl;
00982 throw ParSpaceTrimmerError(ERR_STATETRANSITION_I);
00983 }
00984 vp->vertexinfo = reinterpret_cast<void*>(1);
00985 state.state = TrimState::IN_VERTEX;
00986 state.v = vp;
00987 return StoreCurveApproximation(b, ip, el);
00988
00989 }
00990
00992 return StoreCurveApproximation(b, 1.0, el);
00993 }
00994 else
00995 {
00996 #ifdef OSG_ADAPTIVE_QUAD_TREE
00997 bool b_sub = true;
00998 Vec2d cl_v2d;
00999 bool b_dummy;
01000 DCTPVertex *pcl_find;
01001
01002 cl_v2d[0] = state.v->coords[0];
01003 cl_v2d[1] = state.v->coords[1];
01004
01005 while(b_sub)
01006 {
01007 b_sub = false;
01008
01009 for(unsigned int ui_face = 0; ui_face < state.v->faces.size(); ++ui_face)
01010 {
01011 DCTPFace *pcl_face = state.v->faces[ui_face];
01012 if(pcl_face->norm < DCTP_EPS)
01013 {
01014 if(m_pclQuadTree->computeApproximationError(pcl_face) > m_pclQuadTree->error_epsilon)
01015 {
01016
01017
01018
01019 mesh->SubdivideQuad(pcl_face);
01020 m_pclQuadTree->finishSubdivisions(pcl_face);
01021 b_sub = true;
01022 if(state.v->edges.size() <= 1)
01023 {
01024 pcl_find = mesh->findVertex(state.v->coords);
01025 if(pcl_find)
01026 {
01027
01028
01029
01030 state.v = pcl_find;
01031 }
01032 else
01033 {
01034
01035 if(!isNearQuad(pcl_face, cl_v2d) )
01036 {
01037 state.v->faces[ui_face] = state.v->faces[state.v->faces.size() - 1];
01038 state.v->faces.pop_back();
01039 --ui_face;
01040 }
01041 else
01042 {
01043 state.v->edges[0] = static_cast<DCTPEdge*>(
01044 isOnFaceBoundary(state.v->faces[ui_face], cl_v2d, b_dummy));
01045 }
01046 if(isNearQuad(mesh->faces[mesh->faces.size() - 3], cl_v2d) )
01047 {
01048 state.v->faces.push_back(mesh->faces[mesh->faces.size() - 3]);
01049 state.v->edges[0] = static_cast<DCTPEdge*>(
01050 isOnFaceBoundary(mesh->faces[mesh->faces.size() - 3], cl_v2d, b_dummy));
01051 }
01052 if(isNearQuad(mesh->faces[mesh->faces.size() - 2], cl_v2d) )
01053 {
01054 state.v->faces.push_back(mesh->faces[mesh->faces.size() - 2]);
01055 state.v->edges[0] = static_cast<DCTPEdge*>(
01056 isOnFaceBoundary(mesh->faces[mesh->faces.size() - 2], cl_v2d, b_dummy));
01057 }
01058 if(isNearQuad(mesh->faces[mesh->faces.size() - 1], cl_v2d) )
01059 {
01060 state.v->faces.push_back(mesh->faces[mesh->faces.size() - 1]);
01061 state.v->edges[0] = static_cast<DCTPEdge*>(
01062 isOnFaceBoundary(mesh->faces[mesh->faces.size() - 1], cl_v2d, b_dummy));
01063 }
01064 }
01065 }
01066 }
01067 else
01068 {
01069 pcl_face->norm = m_pclQuadTree->error_epsilon / m_pclQuadTree->computeBilinearNorm(pcl_face);
01070
01071 }
01072 }
01073 }
01074 }
01075 #endif
01076
01077
01078 DCTPVec3dvector &cp = b.getControlPointVector();
01079 cp[0][0] = state.v->coords[0] * cp[0][2];
01080 cp[0][1] = state.v->coords[1] * cp[0][2];
01081 bool feu;
01082 DCTPVertex *v;
01083 unsigned int check;
01084
01085 for(check = 1; check < cp.size(); ++check)
01086 {
01087 if(DCTPVecIsNotEqual(cp[check], cp[0]) )
01088 {
01089 break;
01090 }
01091 }
01092
01093 if(check == cp.size() )
01094 {
01095 return false;
01096 }
01097
01098
01099 if(goingOutOnEdge(b, v, feu, el) )
01100 {
01101 state.v = v;
01102
01103
01104
01105
01106
01107 if(feu)
01108 return false;
01109 return true;
01110 }
01111 DCTPFace *f = getContinuingFace(b);
01112 if(!f)
01113 {
01114 std::cerr << "Brutal error II. in: "
01115 << "ParSpaceTrimmer::StateTransition" << std::endl;
01116 throw ParSpaceTrimmerError(ERR_STATETRANSITION_II);
01117 }
01118
01119
01120
01121
01122 state.f = f;
01123 state.state = TrimState::OVER_FACE;
01124 return true;
01125 }
01126 }
01127
01128 #ifdef OSG_FORCE_NO_T_VERTICES
01129
01130 bool ParSpaceTrimmer::StateTransition2(Vec2d &rclAct, Vec2d clNext, std::vector<DCTPVertex*> &el, Vec3d &rclActS, Vec3d clNextS)
01131
01132
01133
01134 #else
01135 bool ParSpaceTrimmer::StateTransition2(Vec2d &rclAct, Vec2d clNext, std::vector<DCTPVertex*> &el, Vec3d &rclActS, Vec3d clNextS)
01136 #endif
01137 {
01138 if( (rclAct - clNext).squareLength() < DCTP_EPS)
01139 return false;
01140
01141
01142
01143
01144 if(state.state == TrimState::OVER_FACE)
01145 {
01146
01147
01148 if(setMinIntersectionWithFace2(rclAct, clNext) )
01149 {
01150
01151 Vec3d p = Vec3d(rclAct + (clNext - rclAct) * ip);
01152
01153 DCTPVertex *vp = mesh->SplitEdge(ie, p);
01154
01155 if(vp == NULL)
01156 {
01157
01158
01159
01160
01161
01162
01163 std::cerr << "Brutal error I. in: "
01164 << "ParSpaceTrimmer::StateTransition2"
01165 << std::endl;
01166
01167 throw ParSpaceTrimmerError(ERR_STATETRANSITION_I);
01168 }
01169 rclActS = rclActS + (clNextS - rclActS) * ip;
01170 if(vp->vertexinfo == NULL)
01171 {
01172 #ifdef OSG_FORCE_NO_T_VERTICES
01173 SPosNorm *pt_s = new SPosNorm;
01174 SPosNorm *pt_ps = ( SPosNorm* ) el[el.size() - 1]->vertexinfo;
01175
01176 if( (rclActS - clNextS).squareLength() <= (rclActS - pt_ps->clPos).squareLength() )
01177 {
01178 pt_s->clPos = clNextS;
01179
01180
01181
01182 #ifdef OSG_KEEP_2D_POINTS
01183 pt_s->uiNum = m_uiPosCnt;
01184 #endif
01185 }
01186 else
01187 {
01188 pt_s->clPos = pt_ps->clPos;
01189
01190
01191
01192 #ifdef OSG_KEEP_2D_POINTS
01193 pt_s->uiNum = pt_ps->uiNum;
01194 #endif
01195 }
01196 vp->vertexinfo = ( void* ) pt_s;
01197 #else
01198 Vec3d *pcl_s = new Vec3d(rclActS);
01199 vp->vertexinfo = static_cast<void*>(pcl_s);
01200 #endif
01201 }
01202 state.state = TrimState::IN_VERTEX;
01203 state.v = vp;
01204
01205 {
01206 mesh->AddEdge(el[el.size() - 1], vp, 1);
01207
01208
01209 el.push_back(vp);
01210 }
01211 rclAct[0] = vp->coords[0];
01212 rclAct[1] = vp->coords[1];
01213
01214
01215
01216 return !(DCTPVecIsEqual(rclAct, clNext) );
01217 }
01218
01219
01220 DCTPVertex *v = mesh->AddVertex(Vec3d(clNext));
01221 if(v->vertexinfo == NULL)
01222 {
01223 #ifdef OSG_FORCE_NO_T_VERTICES
01224 SPosNorm *pt_s = new SPosNorm;
01225 pt_s->clPos = clNextS;
01226
01227
01228
01229 #ifdef OSG_KEEP_2D_POINTS
01230 pt_s->uiNum = m_uiPosCnt;
01231 #endif
01232 v->vertexinfo = ( void* ) pt_s;
01233 #else
01234 Vec3d *pcl_s = new Vec3d(clNextS);
01235 v->vertexinfo = static_cast<void*>(pcl_s);
01236 #endif
01237 }
01238 mesh->AddEdge(el[el.size() - 1], v, 1);
01239
01240
01241 el.push_back(v);
01242
01243 return false;
01244 }
01245 else
01246 {
01247
01248
01249 bool feu;
01250 DCTPVertex *v;
01251 if(DCTPVecIsEqual(rclAct, clNext) )
01252 return false;
01253 if(goingOutOnEdge2(rclAct, clNext, v, feu, el) )
01254 {
01255
01256 if(feu)
01257 {
01258 rclActS = clNextS;
01259 }
01260 else
01261 {
01262 rclActS = rclActS + (clNextS - rclActS) * ip;
01263 }
01264 if(v->vertexinfo == NULL)
01265 {
01266 #ifdef OSG_FORCE_NO_T_VERTICES
01267 SPosNorm *pt_s = new SPosNorm;
01268 SPosNorm *pt_ps = ( SPosNorm* ) el[el.size() - 1]->vertexinfo;
01269
01270 if( (rclActS - clNextS).squareLength() <= (rclActS - pt_ps->clPos).squareLength() )
01271 {
01272 pt_s->clPos = clNextS;
01273
01274
01275
01276 #ifdef OSG_KEEP_2D_POINTS
01277 pt_s->uiNum = m_uiPosCnt;
01278 #endif
01279 }
01280 else
01281 {
01282 pt_s->clPos = pt_ps->clPos;
01283
01284
01285
01286 #ifdef OSG_KEEP_2D_POINTS
01287 pt_s->uiNum = pt_ps->uiNum;
01288 #endif
01289 }
01290 v->vertexinfo = ( void* ) pt_s;
01291 #else
01292 Vec3d *pcl_s = new Vec3d(rclActS);
01293 v->vertexinfo = static_cast<void*>(pcl_s);
01294 #endif
01295 }
01296 state.v = v;
01297
01298
01299
01300 {
01301
01302 mesh->directEdge(el[el.size() - 1]->coords, v->coords);
01303
01304 el.push_back(v);
01305 }
01306 rclAct[0] = v->coords[0];
01307 rclAct[1] = v->coords[1];
01308
01309 return (!feu);
01310 }
01311 DCTPFace *f = getContinuingFace2(rclAct, clNext);
01312 if(f == NULL)
01313 {
01314 std::cerr << "Brutal error II. in: "
01315 << "ParSpaceTrimmer::StateTransition2" << std::endl;
01316 exit(-1);
01317 throw ParSpaceTrimmerError(ERR_STATETRANSITION_II);
01318 }
01319
01320 state.f = f;
01321 state.state = TrimState::OVER_FACE;
01322 return true;
01323 }
01324 }
01325
01326
01327
01329
01330
01331
01332
01333
01334
01336
01337
01338
01339
01340
01341
01342
01343
01344
01345 void ParSpaceTrimmer::processCurve(bezier2ddeque &tc, std::vector<DCTPVertex*> &el)
01346 {
01347
01348 while(!tc.empty() )
01349 {
01350 BezierCurve2D bc = tc.front();
01351 tc.pop_front();
01352 if(StateTransition(bc, el) )
01353 tc.push_front(bc);
01354 }
01355 }
01356
01357 void ParSpaceTrimmer::processCurve2(unsigned int uiLoop, std::vector<DCTPVertex*> &el)
01358 {
01359 const unsigned int cui_size = (*pvccrd)[uiLoop].size();
01360 Vec2d cl_act = (*pvccrd)[uiLoop][cui_size - 1];
01361 Vec3d cl_act_s = (*m_pvvclSewed)[uiLoop][cui_size - 1];
01362 #ifdef OSG_FORCE_NO_T_VERTICES
01363
01364
01365
01366 #endif
01367 unsigned int ui_vertex = 0;
01368 Vec2d cl_next;
01369
01370
01371
01372
01373 while(ui_vertex < cui_size)
01374 {
01375 cl_next = (*pvccrd)[uiLoop][ui_vertex];
01376
01377
01378
01379
01380
01381 #ifdef OSG_FORCE_NO_T_VERTICES
01382
01383 if(!StateTransition2(cl_act, cl_next, el,
01384 cl_act_s, (*m_pvvclSewed)[uiLoop][ui_vertex]) )
01385
01386
01387
01388
01389
01390 #else
01391 if(!StateTransition2(cl_act, cl_next, el,
01392 cl_act_s, (*m_pvvclSewed)[uiLoop][ui_vertex]) )
01393 #endif
01394 {
01395 cl_act = (*pvccrd)[uiLoop][ui_vertex];
01396 cl_act_s = (*m_pvvclSewed)[uiLoop][ui_vertex];
01397 #ifdef OSG_FORCE_NO_T_VERTICES
01398
01399
01400
01401 #ifdef OSG_KEEP_2D_POINTS
01402 ++m_uiPosCnt;
01403 #endif
01404 #endif
01405 ++ui_vertex;
01406
01407 }
01408 }
01409 }
01410
01411 int ParSpaceTrimmer::PerformTrimming(void)
01412 {
01413 if(tcs3d == NULL)
01414 {
01415
01416 #ifdef OSG_USE_SIMPLIFIER
01417 m_pclQuadTree->error_epsilon *= OSG_SIMPLIFIER_TESS_ERR;
01418 terr = m_pclQuadTree->error_epsilon * 3;
01419 #endif
01420
01421 bezier2ddequevector::iterator tcs_end = tcs->end();
01422 vcel.resize(tcs->size() );
01423
01424 unsigned int i = 0;
01425
01426 for(bezier2ddequevector::iterator bcq = tcs->begin(); bcq != tcs_end; ++bcq)
01427 {
01428 if(!(*bcq).empty() )
01429 {
01430 vcel[i].clear();
01431 initializeStartState(*bcq);
01432 processCurve(*bcq, vcel[i]);
01433
01434 ++i;
01435 }
01436 }
01437
01438 if(i != vcel.size() )
01439 {
01440 vcel.resize(i);
01441 }
01442
01443 }
01444 else
01445 {
01446
01447 std::vector<double> params;
01448
01449 #ifdef OSG_USE_SIMPLIFIER
01450 terr *= OSG_SIMPLIFIER_TESS_ERR;
01451 #endif
01452 bezier2ddequevector::iterator tcs_end = tcs->end();
01453 vcel.resize(tcs->size() );
01454
01455 unsigned int i = 0;
01456 int err;
01457 const unsigned int lc = tcs->size();
01458
01459
01460
01461 for(unsigned int l = 0; l < lc; ++l)
01462 {
01463 if(!(*tcs)[l].empty() )
01464 {
01465 vcel[i].clear();
01466 const unsigned int cc = (*tcs)[l].size();
01467
01468 for(unsigned int c = 0; c < cc; ++c)
01469 {
01470
01471 BezierCurve2D &bc = (*tcs)[l][c];
01472 BezierCurve3D bc3d = (*tcs3d)[l][c];
01473
01474
01475
01476 params.clear();
01477
01478 bc3d.approximate(params, terr, BezierCurve3D::MIDPOINT_SUBDIVISION | BezierCurve3D::LINE_DISTANCE);
01479
01480
01481 for(unsigned int j = 0; j < params.size(); ++j)
01482 {
01483 Vec2d cl_pos;
01484
01485 err = 0;
01486 cl_pos = bc.computewdeCasteljau(params[j], err);
01487 cl_pos[0] = DCTP_EPS * 100.0 * floor(cl_pos[0] / (DCTP_EPS * 100.0) + 0.5);
01488 cl_pos[1] = DCTP_EPS * 100.0 * floor(cl_pos[1] / (DCTP_EPS * 100.0) + 0.5);
01489 vcel[i].push_back(mesh->AddVertex(Vec3d(cl_pos)) );
01490
01491 }
01492
01493
01494 }
01495
01496 ++i;
01497 }
01498 }
01499
01500
01501 if(i != vcel.size() )
01502 {
01503 vcel.resize(i);
01504 }
01505
01506 tcs = NULL;
01507 tcs3d = NULL;
01508 }
01509
01510 #ifdef OSG_USE_SIMPLIFIER
01511 unsigned int ui_vert_cnt;
01512 unsigned int ui_vert;
01513 int i_err;
01514 const double cd_error_quad = terr * terr
01515 * (1.0 - OSG_SIMPLIFIER_TESS_ERR) * (1.0 - OSG_SIMPLIFIER_TESS_ERR)
01516 / (OSG_SIMPLIFIER_TESS_ERR * OSG_SIMPLIFIER_TESS_ERR);
01517
01518 double d_act_dist;
01519 double d_max_dist;
01520 unsigned int ui_new;
01521
01522 std::vector<SPolySimVertex> vt_vertices;
01523 SPolySimVertexSet vt_sim_sort;
01524 unsigned int ui_first;
01525 unsigned int ui_prev;
01526 unsigned int ui_next;
01527 Vec2d cl_uv;
01528 unsigned int ui_remain_cnt;
01529 unsigned int i;
01530 Vec3d cl_midpos;
01531
01532
01533
01534
01535
01536
01537
01538
01539
01540
01541
01542
01543
01544
01545
01546
01547 checkEdgeloops();
01548
01549 for(i = 0; i < vcel.size(); ++i)
01550 {
01551 ui_vert_cnt = vcel[i].size();
01552
01553 if(ui_vert_cnt)
01554 {
01555 vt_vertices.resize(ui_vert_cnt);
01556
01557 for(ui_vert = 0; ui_vert < ui_vert_cnt; ++ui_vert)
01558 {
01559 i_err = 0;
01560 vt_vertices[ui_vert].uiIndex = ui_vert;
01561 vt_vertices[ui_vert].uiPrev = ui_vert - 1;
01562 vt_vertices[ui_vert].uiNext = ui_vert + 1;
01563 cl_uv[0] = vcel[i][ui_vert]->coords[0];
01564 cl_uv[1] = vcel[i][ui_vert]->coords[1];
01565 vt_vertices[ui_vert].clPos = m_pclNurbs->compute(cl_uv, i_err);
01566 if(i_err)
01567 {
01568 std::cerr << " " << i_err << std::endl;
01569 }
01570 }
01571
01572 vt_vertices[0].uiPrev = ui_vert_cnt - 1;
01573 vt_vertices[ui_vert_cnt - 1].uiNext = 0;
01574 vt_sim_sort.clear();
01575
01576 for(ui_vert = 0; ui_vert < ui_vert_cnt; ++ui_vert)
01577 {
01578 cl_uv[0] = (vcel[i][vt_vertices[ui_vert].uiPrev]->coords[0]
01579 + vcel[i][vt_vertices[ui_vert].uiNext]->coords[0]) * 0.5;
01580 cl_uv[1] = (vcel[i][vt_vertices[ui_vert].uiPrev]->coords[1]
01581 + vcel[i][vt_vertices[ui_vert].uiNext]->coords[1]) * 0.5;
01582 cl_midpos = m_pclNurbs->compute(cl_uv, i_err);
01583 vt_vertices[ui_vert].dSimplifyError =
01584 osgMax(DistToEdge(vt_vertices[ui_vert].clPos,
01585 vt_vertices[vt_vertices[ui_vert].uiPrev].clPos,
01586 vt_vertices[vt_vertices[ui_vert].uiNext].clPos),
01587 DistToEdge(cl_midpos,
01588 vt_vertices[vt_vertices[ui_vert].uiPrev].clPos,
01589 vt_vertices[vt_vertices[ui_vert].uiNext].clPos) );
01590 vt_vertices[ui_vert].dSimplifyError +=
01591 sqrt( (vt_vertices[vt_vertices[ui_vert].uiPrev].clPos
01592 - vt_vertices[vt_vertices[ui_vert].uiNext].clPos).squareLength() ) * 0.00001;
01593 if(vt_vertices[ui_vert].dSimplifyError < cd_error_quad)
01594 {
01595 vt_sim_sort.insert(&vt_vertices[ui_vert]);
01596 }
01597 }
01598
01599 ui_first = 0;
01600 ui_remain_cnt = ui_vert_cnt;
01601 while( (!vt_sim_sort.empty() ) && (ui_remain_cnt > 3) )
01602 {
01603
01604 ui_vert = (*vt_sim_sort.begin() )->uiIndex;
01605 ui_prev = (*vt_sim_sort.begin() )->uiPrev;
01606 ui_next = (*vt_sim_sort.begin() )->uiNext;
01607
01608 vt_sim_sort.erase(vt_sim_sort.begin() );
01609 vt_vertices[ui_prev].uiNext = ui_next;
01610 vt_vertices[ui_next].uiPrev = ui_prev;
01611 if(ui_vert == ui_first)
01612 {
01613 ui_first = ui_next;
01614 }
01615 if(!mesh->findVertex(vcel[i][ui_vert]->coords) )
01616 {
01617
01618 delete vcel[i][ui_vert];
01619 vcel[i][ui_vert] = NULL;
01620 }
01621
01622 if(vt_vertices[ui_prev].dSimplifyError < cd_error_quad)
01623 {
01624 vt_sim_sort.erase(&vt_vertices[ui_prev]);
01625 }
01626 if(vt_vertices[ui_next].dSimplifyError < cd_error_quad)
01627 {
01628 vt_sim_sort.erase(&vt_vertices[ui_next]);
01629 }
01630
01631 if( (ui_vert != ui_prev) && (ui_vert != ui_next) )
01632 {
01633 cl_uv[0] = (vcel[i][vt_vertices[ui_prev].uiPrev]->coords[0]
01634 + vcel[i][ui_next]->coords[0]) * 0.5;
01635 cl_uv[1] = (vcel[i][vt_vertices[ui_prev].uiPrev]->coords[1]
01636 + vcel[i][ui_next]->coords[1]) * 0.5;
01637 cl_midpos = m_pclNurbs->compute(cl_uv, i_err);
01638 d_max_dist = DistToEdge(cl_midpos,
01639 vt_vertices[vt_vertices[ui_vert].uiPrev].clPos,
01640 vt_vertices[ui_next].clPos);
01641
01642 ui_vert = (vt_vertices[ui_prev].uiPrev + 1) % ui_vert_cnt;
01643 while(ui_vert != ui_next)
01644 {
01645 d_act_dist = DistToEdge(vt_vertices[ui_vert].clPos,
01646 vt_vertices[vt_vertices[ui_prev].uiPrev].clPos,
01647 vt_vertices[ui_next].clPos);
01648 if(d_act_dist > d_max_dist)
01649 {
01650 d_max_dist = d_act_dist;
01651 }
01652 ui_vert = (ui_vert + 1) % ui_vert_cnt;
01653 }
01654 vt_vertices[ui_prev].dSimplifyError = d_max_dist;
01655 vt_vertices[ui_prev].dSimplifyError +=
01656 sqrt( (vt_vertices[vt_vertices[ui_prev].uiPrev].clPos
01657 - vt_vertices[vt_vertices[ui_prev].uiNext].clPos).squareLength() ) * 0.00001;
01658 if(vt_vertices[ui_prev].dSimplifyError < cd_error_quad)
01659 {
01660 vt_sim_sort.insert(&vt_vertices[ui_prev]);
01661 }
01662
01663 cl_uv[0] = (vcel[i][ui_prev]->coords[0]
01664 + vcel[i][vt_vertices[ui_next].uiNext]->coords[0]) * 0.5;
01665 cl_uv[1] = (vcel[i][ui_prev]->coords[1]
01666 + vcel[i][vt_vertices[ui_next].uiNext]->coords[1]) * 0.5;
01667 cl_midpos = m_pclNurbs->compute(cl_uv, i_err);
01668 d_max_dist = DistToEdge(cl_midpos,
01669 vt_vertices[ui_prev].clPos,
01670 vt_vertices[vt_vertices[ui_next].uiNext].clPos);
01671
01672 ui_vert = (ui_prev + 1) % ui_vert_cnt;
01673 while(ui_vert != vt_vertices[ui_next].uiNext)
01674 {
01675 d_act_dist = DistToEdge(vt_vertices[ui_vert].clPos,
01676 vt_vertices[ui_prev].clPos,
01677 vt_vertices[vt_vertices[ui_next].uiNext].clPos);
01678 if(d_act_dist > d_max_dist)
01679 {
01680 d_max_dist = d_act_dist;
01681 }
01682 ui_vert = (ui_vert + 1) % ui_vert_cnt;
01683 }
01684 vt_vertices[ui_next].dSimplifyError = d_max_dist;
01685 vt_vertices[ui_next].dSimplifyError +=
01686 sqrt( (vt_vertices[vt_vertices[ui_next].uiPrev].clPos
01687 - vt_vertices[vt_vertices[ui_next].uiNext].clPos).squareLength() ) * 0.00001;
01688 if(vt_vertices[ui_next].dSimplifyError < cd_error_quad)
01689 {
01690 vt_sim_sort.insert(&vt_vertices[ui_next]);
01691 }
01692 }
01693 --ui_remain_cnt;
01694 }
01695
01696
01697 vcel[i][0] = vcel[i][ui_first];
01698 ui_new = 1;
01699
01700 for(ui_vert = vt_vertices[ui_first].uiNext; ui_vert != ui_first; ui_vert = vt_vertices[ui_vert].uiNext)
01701 {
01702 vcel[i][ui_new] = vcel[i][ui_vert];
01703 ++ui_new;
01704 }
01705
01706 vcel[i].resize(ui_new);
01707
01708 }
01709
01710
01711 }
01712
01713
01714
01715 vt_vertices.clear();
01716 vt_sim_sort.clear();
01717 #endif
01718 checkEdgeloops();
01719
01720
01721
01722 pvccrd->resize(vcel.size() );
01723
01724 for(unsigned int loop = 0; loop < vcel.size(); ++loop)
01725 {
01726 unsigned int v, oid;
01727 unsigned int nid = vcel[loop][vcel[loop].size() - 1]->id;
01728 Vec2d cl_temp_vec;
01729
01730 for(v = 0; v < vcel[loop].size(); ++v)
01731 {
01732
01733 oid = nid;
01734 nid = vcel[loop][v]->id;
01735 if(oid != nid)
01736 {
01737 cl_temp_vec[0] = vcel[loop][v]->coords[0];
01738 cl_temp_vec[1] = vcel[loop][v]->coords[1];
01739
01740
01741 (*pvccrd)[loop].push_back(cl_temp_vec);
01742 }
01743 }
01744
01745
01746 (*pvccrd)[loop].push_back( (*pvccrd)[loop][0]);
01747 }
01748
01749
01750 return 0;
01751 }
01752
01753 int ParSpaceTrimmer::PerformTrimming2(void)
01754 {
01755 unsigned int ui_tloops = (*pvccrd).size();
01756 unsigned int ui_i;
01757
01758 m_bDeleteVertexInfo = true;
01759 vcel.resize(ui_tloops);
01760
01761
01762 #ifdef OSG_KEEP_2D_POINTS
01763 m_uiPosCnt = 0;
01764 #endif
01765
01766 #ifdef OSG_SPLIT_HOLE_CELLS
01767
01768
01769 for(ui_i = 0; ui_i < ui_tloops; ++ui_i)
01770 {
01771 if( ( (*m_pvbUsed)[ui_i]) &&
01772 ( (*m_pvbReversed)[ui_i]) )
01773 {
01774 unsigned int v;
01775 Vec2d cl_temp_vec;
01776 DCTPFace *pcl_inside_face;
01777 Vec2d cl_min;
01778 Vec2d cl_max;
01779 double d_ratio;
01780
01781 cl_temp_vec[0] = (*pvccrd)[ui_i][(*pvccrd)[ui_i].size() - 1][0];
01782 cl_temp_vec[1] = (*pvccrd)[ui_i][(*pvccrd)[ui_i].size() - 1][1];
01783 cl_min = cl_max = cl_temp_vec;
01784
01785 getStartingFace(cl_temp_vec);
01786 pcl_inside_face = state.f;
01787
01788 for(v = 0; v < (*pvccrd)[ui_i].size(); ++v)
01789 {
01790 if(pcl_inside_face)
01791 {
01792 cl_temp_vec[0] = (*pvccrd)[ui_i][v][0];
01793 cl_temp_vec[1] = (*pvccrd)[ui_i][v][1];
01794 cl_min[0] = osgMin(cl_min[0], cl_temp_vec[0]);
01795 cl_min[1] = osgMin(cl_min[1], cl_temp_vec[1]);
01796 cl_max[0] = osgMax(cl_max[0], cl_temp_vec[0]);
01797 cl_max[1] = osgMax(cl_max[1], cl_temp_vec[1]);
01798 if(!isOverFace(pcl_inside_face, cl_temp_vec) )
01799 {
01800 pcl_inside_face = NULL;
01801 }
01802 }
01803 }
01804
01805 if(pcl_inside_face)
01806 {
01807 if(cl_max[0] - cl_min[0] > cl_max[1] - cl_min[1])
01808 {
01809 d_ratio = ( (cl_min[0] + cl_max[0]) * 0.5 - pcl_inside_face->orig_face[0]->coords[0])
01810 / (pcl_inside_face->orig_face[1]->coords[0]
01811 - pcl_inside_face->orig_face[0]->coords[0]);
01812
01813
01814
01815 mesh->SubdivideQuadEW(pcl_inside_face, d_ratio);
01816 }
01817 else
01818 {
01819 d_ratio = ( (cl_min[1] + cl_max[1]) * 0.5 - pcl_inside_face->orig_face[3]->coords[1])
01820 / (pcl_inside_face->orig_face[0]->coords[1]
01821 - pcl_inside_face->orig_face[3]->coords[1]);
01822
01823
01824
01825 mesh->SubdivideQuadNS(pcl_inside_face, d_ratio);
01826 }
01827 }
01828 }
01829 }
01830
01831 #endif
01832
01833 for(ui_i = 0; ui_i < ui_tloops; ++ui_i)
01834 {
01835 if( (*m_pvbUsed)[ui_i])
01836 {
01837
01838 #ifdef OSG_KEEP_2D_POINTS
01839 m_uiPosCnt += (*pvccrd)[ui_i].size();
01840 #endif
01841 if(isLoopValid(ui_i) )
01842 {
01843 #ifdef OSG_KEEP_2D_POINTS
01844 --m_uiPosCnt;
01845 #endif
01846 initializeStartState2(ui_i, vcel[ui_i]);
01847 #ifdef OSG_KEEP_2D_POINTS
01848 m_uiPosCnt -= (*pvccrd)[ui_i].size();
01849 ++m_uiPosCnt;
01850 #endif
01851 processCurve2(ui_i, vcel[ui_i]);
01852 }
01853 }
01854 }
01855
01856 for(ui_i = 0; ui_i < ui_tloops; ++ui_i)
01857 {
01858 if(vcel[ui_i].size() == 0)
01859 {
01860
01861 --ui_tloops;
01862 vcel[ui_i] = vcel[ui_tloops];
01863 vcel.pop_back();
01864 --ui_i;
01865 }
01866 }
01867
01868
01869
01870 return 0;
01871 }
01872
01873 Vec2d ParSpaceTrimmer::calcNormal(Vec2d &a, Vec2d &b)
01874 {
01875 Vec2d norm(0.0, 0.0);
01876 if(DCTPVecIsEqual(a, b) )
01877 return norm;
01878 double lab = sqrt( (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]) );
01879 norm[0] = -(b[1] - a[1]) / lab;
01880 norm[1] = (b[0] - a[0]) / lab;
01881 return norm;
01882 }
01883
01884 bool ParSpaceTrimmer::checkEdgeNormals(DirectedGraph<Vec2d, unsigned char> &sg, int from, int to)
01885 {
01886 if(DCTPVecIsEqual(sg.nodes[from].nodeinfo, sg.nodes[to].nodeinfo) )
01887 return false;
01888 Vec2d norm = calcNormal(sg.nodes[from].nodeinfo, sg.nodes[to].nodeinfo);
01889
01890
01891
01892 for(unsigned int i = 0; i < sg.nodes[from].edges.size(); ++i)
01893 {
01894 Vec2d a = sg.nodes[sg.edges[sg.nodes[from].edges[i]].from].nodeinfo;
01895 Vec2d b = sg.nodes[sg.edges[sg.nodes[from].edges[i]].to].nodeinfo;
01896 Vec2d n = calcNormal(a, b);
01900 if(DCTPVecIsEqual(n, norm) )
01901 {
01905 return true;
01906 }
01907
01908 }
01909
01910 return false;
01911 }
01912
01913 #ifdef OSG_FORCE_NO_T_VERTICES
01914 #ifdef OSG_KEEP_2D_POINTS
01915 int ParSpaceTrimmer::buildSurfaceGraph(DirectedGraph<Vec2d, unsigned char> *psg, std::vector<Vec3d> *pvclSewed, std::vector<Vec3d> *pvclNormals, std::vector<unsigned int> *pvuiIdx)
01916 #else
01917 int ParSpaceTrimmer::buildSurfaceGraph(DirectedGraph<Vec2d, unsigned char> *psg, std::vector<Vec3d> *pvclSewed, std::vector<Vec3d> *pvclNormals)
01918 #endif
01919 #else
01920 int ParSpaceTrimmer::buildSurfaceGraph(DirectedGraph<Vec2d, unsigned char> *psg, std::vector<Vec3d> *pvclSewed)
01921 #endif
01922 {
01923 dctpvertexset::iterator ve = mesh->vertices.end();
01924 dctpvertexset::iterator i;
01925 std::vector<DCTPVertex*> vpcl_added_from;
01926 std::vector<DCTPVertex*> vpcl_added_to;
01927
01928
01929 #ifdef OSG_FORCE_NO_T_VERTICES
01930 if(pvclNormals)
01931 pvclNormals->clear();
01932 #endif
01933 #ifdef OSG_KEEP_2D_POINTS
01934 if(pvuiIdx)
01935 pvuiIdx->clear();
01936 #endif
01937 if(pvclSewed)
01938 pvclSewed->clear();
01939 psg->nodes.clear();
01940 psg->edges.clear();
01941
01942 for(i = mesh->vertices.begin(); i != ve; ++i)
01943 {
01944 if( (*i)->vertexinfo)
01945 {
01946 Vec2d v2dtemp( (*i)->coords[0], (*i)->coords[1]);
01947
01948 (*i)->node_id = psg->AddNode(v2dtemp);
01949
01950
01951
01952 #ifdef OSG_FORCE_NO_T_VERTICES
01953 if(pvclSewed)
01954 pvclSewed->push_back( ( (SPosNorm*)(*i)->vertexinfo)->clPos);
01955
01956
01957
01958 #ifdef OSG_KEEP_2D_POINTS
01959
01960 if(pvuiIdx)
01961 pvuiIdx->push_back( ( (SPosNorm*)(*i)->vertexinfo)->uiNum);
01962 #endif
01963 #else
01964 if(pvclSewed)
01965 pvclSewed->push_back(*(static_cast<Vec3d*>((*i)->vertexinfo)) );
01966 #endif
01967 }
01968 }
01969
01970 #ifdef OSG_KEEP_2D_POINTS
01971
01972 if(pvclSewed->size() < m_uiPosCnt)
01973 {
01974 Vec2d cl_dummy(0.0, 0.0);
01975 const unsigned int cui_idx_cnt = m_uiPosCnt - pvclSewed->size();
01976
01977 for(unsigned int ui_idx = 0; ui_idx < cui_idx_cnt; ++ui_idx)
01978 {
01979 psg->AddNode(cl_dummy);
01980 }
01981
01982 if(pvclSewed)
01983 pvclSewed->resize(m_uiPosCnt);
01984 if(pvclNormals)
01985 pvclNormals->resize(m_uiPosCnt);
01986 }
01987 #endif
01988
01989
01990 for(i = mesh->vertices.begin(); i != ve; ++i)
01991 {
01992 if( (*i)->vertexinfo == NULL)
01993 {
01994 Vec2d v2dtemp( (*i)->coords[0], (*i)->coords[1]);
01995
01996 (*i)->node_id = psg->AddNode(v2dtemp);
01997 }
01998 }
01999
02000 #ifdef OSG_NO_EDGE_SET
02001 dctpedgevector::iterator ee = mesh->edges.end();
02002 #else
02003 dctpedgeset::iterator ee = mesh->edges.end();
02004 #endif
02005 unsigned char dummy = 0;
02006
02007 #ifdef OSG_NO_EDGE_SET
02008
02009 for(dctpedgevector::iterator e = mesh->edges.begin(); e != ee; ++e)
02010 #else
02011
02012 for(dctpedgeset::iterator e = mesh->edges.begin(); e != ee; ++e)
02013 #endif
02014 {
02015 DCTPVertex *v1, *v2;
02016 bool orient;
02017
02018 (*e)->getVertices(v1, v2);
02019 if( (*e)->orientation < 0)
02020 {
02021 DCTPVertex *tmpv;
02022 tmpv = v1;
02023 v1 = v2;
02024 v2 = tmpv;
02025 orient = true;
02026 }
02027 else if( (*e)->orientation > 0)
02028 {
02029 orient = true;
02030 }
02031 else
02032 {
02033 orient = false;
02034 }
02035
02036
02037 dummy = orient ? 1 : 0;
02038 psg->AddEdge(dummy, v1->node_id, v2->node_id, orient);
02039 if(abs( (*e)->orientation) > 1)
02040 {
02041 for(int i_idx = 1; i_idx < abs( (*e)->orientation); ++i_idx)
02042 {
02043 psg->AddEdge(dummy, v1->node_id, v2->node_id, orient);
02044 }
02045 }
02046 }
02047
02048
02049
02050
02051
02052
02053
02054
02055
02056
02057
02058
02059
02060
02061
02062
02063
02064
02065
02066
02067
02068
02071
02072
02073
02074
02075
02076 #ifndef OSG_SPLIT_HOLE_CELLS
02077
02078
02079 for(unsigned int loop = 0; loop < vcel.size(); ++loop)
02080 {
02081
02082 unsigned int v;
02083
02084 unsigned int nid = vcel[loop][vcel[loop].size() - 1]->node_id;
02085 Vec2d cl_temp_vec;
02086 DCTPFace *pcl_inside_face;
02087
02088 cl_temp_vec[0] = vcel[loop][vcel[loop].size() - 1]->coords[0];
02089 cl_temp_vec[1] = vcel[loop][vcel[loop].size() - 1]->coords[1];
02090 if( (*m_pvbReversed)[loop])
02091 {
02092 getStartingFace(cl_temp_vec);
02093 pcl_inside_face = state.f;
02094
02095 for(v = 0; v < vcel[loop].size(); ++v)
02096 {
02097
02098
02099
02100 if(pcl_inside_face)
02101 {
02102 cl_temp_vec[0] = vcel[loop][v]->coords[0];
02103 cl_temp_vec[1] = vcel[loop][v]->coords[1];
02104 if(vcel[loop][vcel[loop].size() - 1]->faces.size() )
02105
02106 {
02107 pcl_inside_face = NULL;
02108 }
02109 }
02110
02111
02112
02113
02114
02115
02116
02117
02118
02119
02120
02121
02122
02123
02124
02125
02126
02127 }
02128
02129 if(pcl_inside_face)
02130 {
02131
02132
02133
02134
02135 double d_qdist_ul = -1.0;
02136 double d_qdist_lr = -1.0;
02137 double d_act_dist;
02138 #ifdef OSG_UNION_TRI_QUAD
02139 DCTPVertex *pcl_upper_left = pcl_inside_face->orig_face[0];
02140 DCTPVertex *pcl_lower_right = pcl_inside_face->orig_face[2];
02141 #else
02142 DCTPVertex *pcl_upper_left = pcl_inside_face->orig_quad[0];
02143 DCTPVertex *pcl_lower_right = pcl_inside_face->orig_quad[2];
02144 #endif
02145 DCTPVertex *pcl_nearest_ul;
02146 DCTPVertex *pcl_nearest_lr;
02147 DCTPVertex *pcl_act_point;
02148 unsigned int ui_check;
02149 bool b_ok;
02150 unsigned int ui_exit;
02151
02152 dummy = 1;
02153
02154 for(v = 0; v < vcel[loop].size(); ++v)
02155 {
02156 pcl_act_point = vcel[loop][v];
02157 d_act_dist = (Vec2d(pcl_act_point->coords - pcl_upper_left->coords) ).squareLength();
02158 if( (d_qdist_ul < -0.5) || (d_act_dist - d_qdist_ul < DCTP_EPS) )
02159 {
02160 d_qdist_ul = d_act_dist;
02161 pcl_nearest_ul = pcl_act_point;
02162 }
02163 d_act_dist = (Vec2d(pcl_act_point->coords - pcl_lower_right->coords) ).squareLength();
02164 if( (d_qdist_lr < -0.5) || (d_act_dist - d_qdist_lr < DCTP_EPS) )
02165 {
02166 d_qdist_lr = d_act_dist;
02167 pcl_nearest_lr = pcl_act_point;
02168 }
02169 }
02170
02171
02172 b_ok = false;
02173 ui_exit = 1000;
02174 while( (!b_ok) && (--ui_exit > 0) )
02175 {
02176
02177 b_ok = true;
02178
02179
02180 for(ui_check = 0; ui_check < vcel.size(); ++ui_check)
02181 {
02182 if(ui_check != loop)
02183 {
02184 pcl_act_point = intersectsLoop(pcl_nearest_ul, pcl_upper_left, ui_check);
02185 if(pcl_act_point)
02186 {
02187 pcl_upper_left = pcl_act_point;
02188 ui_check = vcel.size();
02189 b_ok = false;
02191 }
02192 }
02193 }
02194
02195
02196 pcl_act_point = intersectsLoop(pcl_upper_left, pcl_nearest_ul, loop);
02197 if(pcl_act_point)
02198 {
02199 pcl_nearest_ul = pcl_act_point;
02200 b_ok = false;
02202 }
02203
02204
02205 for(ui_check = 0; ui_check < vpcl_added_from.size(); ++ui_check)
02206 {
02207 if( (pcl_nearest_ul != vpcl_added_from[ui_check]) &&
02208 (pcl_nearest_ul != vpcl_added_to[ui_check]) &&
02209 (pcl_upper_left != vpcl_added_from[ui_check]) &&
02210 (pcl_upper_left != vpcl_added_to[ui_check]) )
02211 {
02212 if(doIntersect(vpcl_added_from[ui_check]->coords, vpcl_added_to[ui_check]->coords,
02213 pcl_nearest_ul->coords, pcl_upper_left->coords, d_act_dist) )
02214 {
02215 if(d_act_dist <= 1.0)
02216 {
02217 if(d_act_dist < 0.5)
02218 {
02219 pcl_upper_left = vpcl_added_from[ui_check];
02220 }
02221 else
02222 {
02223 pcl_upper_left = vpcl_added_to[ui_check];
02224 }
02225 b_ok = false;
02226 ui_check = vpcl_added_from.size();
02228 }
02229 }
02230 }
02231 }
02232
02233 if(pcl_upper_left == pcl_nearest_ul)
02234 {
02235 b_ok = true;
02236 }
02237 }
02238
02239 if(pcl_upper_left != pcl_nearest_ul)
02240 {
02241 vpcl_added_from.push_back(pcl_upper_left);
02242 vpcl_added_to.push_back(pcl_nearest_ul);
02243 psg->AddEdge(dummy, pcl_upper_left->node_id,
02244 pcl_nearest_ul->node_id, false);
02245 }
02247
02248
02249 b_ok = false;
02250 ui_exit = 1000;
02251 while( (!b_ok) && (--ui_exit > 0) )
02252 {
02253
02254 b_ok = true;
02255
02256
02257 for(ui_check = 0; ui_check < vcel.size(); ++ui_check)
02258 {
02259 if(ui_check != loop)
02260 {
02261 pcl_act_point = intersectsLoop(pcl_nearest_lr, pcl_lower_right, ui_check);
02262 if(pcl_act_point)
02263 {
02264 pcl_lower_right = pcl_act_point;
02265 ui_check = vcel.size();
02266 b_ok = false;
02268 }
02269 }
02270 }
02271
02272
02273 pcl_act_point = intersectsLoop(pcl_lower_right, pcl_nearest_lr, loop);
02274 if(pcl_act_point)
02275 {
02276 pcl_nearest_lr = pcl_act_point;
02277 b_ok = false;
02279 }
02280
02281
02282 for(ui_check = 0; ui_check < vpcl_added_from.size(); ++ui_check)
02283 {
02284 if( (pcl_nearest_lr != vpcl_added_from[ui_check]) &&
02285 (pcl_nearest_lr != vpcl_added_to[ui_check]) &&
02286 (pcl_lower_right != vpcl_added_from[ui_check]) &&
02287 (pcl_lower_right != vpcl_added_to[ui_check]) )
02288 {
02289 if(doIntersect(vpcl_added_from[ui_check]->coords, vpcl_added_to[ui_check]->coords,
02290 pcl_nearest_lr->coords, pcl_lower_right->coords, d_act_dist) )
02291 {
02292 if(d_act_dist <= 1.0)
02293 {
02294 if(d_act_dist < 0.5)
02295 {
02296 pcl_lower_right = vpcl_added_from[ui_check];
02297 }
02298 else
02299 {
02300 pcl_lower_right = vpcl_added_to[ui_check];
02301 }
02302 b_ok = false;
02303 ui_check = vpcl_added_from.size();
02305 }
02306 }
02307 }
02308 }
02309
02310 if(pcl_lower_right == pcl_nearest_lr)
02311 {
02312 b_ok = true;
02313 }
02314 }
02315
02316 if(pcl_lower_right != pcl_nearest_lr)
02317 {
02318 vpcl_added_from.push_back(pcl_lower_right);
02319 vpcl_added_to.push_back(pcl_nearest_lr);
02320 psg->AddEdge(dummy, pcl_lower_right->node_id,
02321 pcl_nearest_lr->node_id, false);
02322 }
02324 }
02325 }
02326 }
02327
02328 #endif
02329 return 0;
02330 }
02331
02332 #ifndef OSG_FORCE_NO_T_VERTICES
02333 void ParSpaceTrimmer::getTrimmingLoops(std::vector<std::vector<Vec2d> > &rvvclTrimmingLoops)
02334 {
02335 rvvclTrimmingLoops.resize(vcel.size() );
02336
02337 for(unsigned int loop = 0; loop < vcel.size(); ++loop)
02338 {
02339 rvvclTrimmingLoops[loop].resize(vcel[loop].size() - 1);
02340
02341 for(unsigned int v = 0; v < vcel[loop].size() - 1; ++v)
02342 {
02343 rvvclTrimmingLoops[loop][v] = Vec2d(vcel[loop][v]->coords);
02344 }
02345 }
02346 }
02347 #endif
02348
02349 void ParSpaceTrimmer::checkEdgeloops()
02350 {
02351 std::vector<SScanLineEdge*> vpt_start;
02352 std::vector<SScanLineEdge*> vpt_end;
02353
02354 ScanLineEventSet spt_events;
02355 unsigned int ui_loop;
02356 unsigned int ui_vertex;
02357 unsigned int ui_last;
02358 unsigned int ui_size;
02359 unsigned int ui_loop2;
02360 SScanLineEdge *pt_act_edge;
02361 SScanLineEntry *pt_scan_line = NULL;
02362 SScanLineEntry *pt_act_entry;
02363 SScanLineEntry *pt_next_entry;
02364 ScanLineEventSet::iterator ispt_act_event;
02365 SScanLineEvent *pt_act_event;
02366 int i_inside;
02367 bool b_valid;
02368 Vec3d cl_p;
02369 Vec3d cl_pp;
02370
02371
02372 for(ui_loop = 0; ui_loop < vcel.size(); ++ui_loop)
02373 {
02374 ui_size = vcel[ui_loop].size();
02375
02376 cl_p = vcel[ui_loop][ui_size - 1]->coords;
02377
02378 unsigned int ui_new_num = 0;
02379 std::vector<DCTPVertex*> vpcl_new_points(ui_size);
02380
02381 for(ui_vertex = 0; ui_vertex < ui_size; ++ui_vertex)
02382 {
02383 cl_pp = cl_p;
02384 cl_p = vcel[ui_loop][ui_vertex]->coords;
02385
02386
02387 if(DCTPVecIsNotEqual(cl_p, cl_pp) )
02388 {
02389
02390 {
02391 vpcl_new_points[ui_new_num] = mesh->AddVertex(cl_p);
02392
02393 if(vpcl_new_points[ui_new_num] != vcel[ui_loop][ui_vertex])
02394 {
02395
02396
02397
02398
02399
02400
02401 }
02402
02403 ++ui_new_num;
02404
02405 }
02406
02407
02408
02409
02410
02411
02412
02413
02414
02415
02416
02417
02418
02419
02420
02421
02422
02423
02424
02425 }
02426 else
02427 {
02428 if(!mesh->findVertex(cl_p) )
02429 {
02430
02431 delete vcel[ui_loop][ui_vertex];
02432 }
02433 }
02434 }
02435
02436
02437
02438 {
02439 ui_size = ui_new_num;
02440 vcel[ui_loop].resize(ui_size);
02441
02442 for(ui_vertex = 0; ui_vertex < ui_size; ++ui_vertex)
02443 {
02444 vcel[ui_loop][ui_vertex] = vpcl_new_points[ui_vertex];
02445
02446 }
02447 }
02448
02449
02450 if(ui_size > 2)
02451 {
02452 ui_last = ui_size - 1;
02453
02454 for(ui_vertex = 0; ui_vertex < ui_size; ++ui_vertex)
02455 {
02456 if(vcel[ui_loop][ui_last]->id != vcel[ui_loop][ui_vertex]->id)
02457 {
02458
02459
02460 pt_act_edge = new SScanLineEdge;
02461 pt_act_edge->pclFromVertex = vcel[ui_loop][ui_last];
02462 pt_act_edge->pclToVertex = vcel[ui_loop][ui_vertex];
02463
02464
02465 pt_act_edge->ptPrev = NULL;
02466 pt_act_edge->ptNext = NULL;
02467 pt_act_edge->ptEntry = NULL;
02468
02469 pt_act_edge->bInvalid = false;
02470 if(insertScanLineEvents(pt_act_edge, spt_events) )
02471 {
02472
02473 }
02474 ui_last = ui_vertex;
02475 }
02476 }
02477 }
02478 }
02479
02480
02481 vcel.clear();
02482
02483
02484
02485 while(!spt_events.empty() )
02486 {
02487 ispt_act_event = spt_events.begin();
02488 pt_act_event = *ispt_act_event;
02489
02490 spt_events.erase(ispt_act_event);
02491
02492
02493
02494
02495
02496
02497
02498 pt_act_edge = pt_act_event->ptEdge;
02499
02500
02501 if(pt_act_edge->ptEntry == NULL)
02502 {
02503
02504 pt_act_entry = new SScanLineEntry;
02505 pt_act_entry->ptEdge = pt_act_edge;
02506 pt_act_edge->ptEntry = pt_act_entry;
02507
02508
02509
02510 pt_scan_line = insertInScanLine(pt_act_entry, pt_scan_line);
02511
02512
02513 checkSLIntersection(pt_act_entry, spt_events);
02514
02515 }
02516 else
02517 {
02518
02519 i_inside = 0;
02520
02521 if(!pt_act_edge->bInvalid)
02522 {
02523 pt_act_entry = pt_act_edge->ptEntry->ptNext;
02524 while(pt_act_entry)
02525 {
02526
02527
02528
02529 if(DCTPVecIsGreater(pt_act_entry->ptEdge->pclFromVertex->coords, pt_act_entry->ptEdge->pclToVertex->coords) )
02530 {
02531
02532
02533 ++i_inside;
02534 }
02535 else
02536 {
02537
02538
02539 --i_inside;
02540 }
02541 pt_act_entry = pt_act_entry->ptNext;
02542 }
02543 }
02544
02545 pt_act_entry = pt_act_edge->ptEntry;
02546 pt_next_entry = pt_act_entry->ptNext;
02547 if(pt_act_entry->ptNext)
02548 pt_act_entry->ptNext->ptPrev = pt_act_entry->ptPrev;
02549 if(pt_act_entry->ptPrev)
02550 pt_act_entry->ptPrev->ptNext = pt_act_entry->ptNext;
02551 else
02552 pt_scan_line = pt_act_entry->ptNext;
02553 delete pt_act_entry;
02554 if(!pt_act_edge->bInvalid)
02555 {
02556 if(DCTPVecIsGreater(pt_act_edge->pclFromVertex->coords, pt_act_edge->pclToVertex->coords) )
02557 {
02558
02559
02560 b_valid = (i_inside == -1);
02561 }
02562 else
02563 {
02564
02565
02566 b_valid = (i_inside == 0);
02567 }
02568 if(b_valid)
02569 {
02570
02571 ui_size = vpt_start.size();
02572
02573 for(ui_loop = 0; ui_loop < ui_size; ++ui_loop)
02574 {
02575 if(pt_act_edge->pclToVertex == vpt_start[ui_loop]->pclFromVertex)
02576 {
02577
02578 pt_act_edge->ptNext = vpt_start[ui_loop];
02579 vpt_start[ui_loop]->ptPrev = pt_act_edge;
02580 vpt_start[ui_loop] = pt_act_edge;
02581 break;
02582 }
02583 if(pt_act_edge->pclFromVertex == vpt_end[ui_loop]->pclToVertex)
02584 {
02585
02586 pt_act_edge->ptPrev = vpt_end[ui_loop];
02587 vpt_end[ui_loop]->ptNext = pt_act_edge;
02588 vpt_end[ui_loop] = pt_act_edge;
02589 break;
02590 }
02591 }
02592
02593 if(ui_loop < ui_size)
02594 {
02595
02596 if(vpt_start[ui_loop]->pclFromVertex == vpt_end[ui_loop]->pclToVertex)
02597 {
02598
02599
02600 saveLoop(vpt_start[ui_loop]);
02601 if(ui_loop != ui_size - 1)
02602 {
02603 vpt_start[ui_loop] = vpt_start[ui_size - 1];
02604 vpt_end[ui_loop] = vpt_end[ui_size - 1];
02605 }
02606 vpt_start.resize(ui_size - 1);
02607 vpt_end.resize(ui_size - 1);
02608 }
02609 else
02610 {
02611
02612 for(ui_loop2 = 0; ui_loop2 < ui_size; ++ui_loop2)
02613 {
02614 if(ui_loop != ui_loop2)
02615 {
02616 if(vpt_start[ui_loop]->pclFromVertex == vpt_end[ui_loop2]->pclToVertex)
02617 {
02618
02619 vpt_start[ui_loop]->ptPrev = vpt_end[ui_loop2];
02620 vpt_end[ui_loop2]->ptNext = vpt_start[ui_loop];
02621 vpt_start[ui_loop] = vpt_start[ui_loop2];
02622 break;
02623 }
02624 if(vpt_start[ui_loop2]->pclFromVertex == vpt_end[ui_loop]->pclToVertex)
02625 {
02626
02627 vpt_start[ui_loop2]->ptPrev = vpt_end[ui_loop];
02628 vpt_end[ui_loop]->ptNext = vpt_start[ui_loop2];
02629 vpt_end[ui_loop] = vpt_end[ui_loop2];
02630 break;
02631 }
02632 }
02633 }
02634
02635 if(ui_loop2 < ui_size)
02636 {
02637
02638 if(ui_loop2 != ui_size - 1)
02639 {
02640 vpt_start[ui_loop2] = vpt_start[ui_size - 1];
02641 vpt_end[ui_loop2] = vpt_end[ui_size - 1];
02642 }
02643 vpt_start.resize(ui_size - 1);
02644 vpt_end.resize(ui_size - 1);
02645 }
02646 }
02647 }
02648 else
02649 {
02650
02651
02652 vpt_start.push_back(pt_act_edge);
02653 vpt_end.push_back(pt_act_edge);
02654 }
02655 }
02656 else
02657 {
02658
02659 delete pt_act_edge;
02660 }
02661 }
02662 else
02663 {
02664
02665 delete pt_act_edge;
02666 }
02667 if( (pt_next_entry) && (pt_next_entry->ptPrev) )
02668 {
02669 if( (!pt_next_entry->ptEdge->bInvalid) &&
02670 (!pt_next_entry->ptPrev->ptEdge->bInvalid) )
02671 {
02672
02673 ScanLineIntersect(pt_next_entry->ptPrev, pt_next_entry, spt_events);
02674 if(pt_next_entry->ptEdge->bInvalid)
02675 {
02676 removeSLEntry(pt_next_entry->ptPrev, spt_events);
02677 removeSLEntry(pt_next_entry, spt_events);
02678 }
02679 }
02680 }
02681
02682 }
02683
02684 delete pt_act_event;
02685 }
02686
02687
02688
02689
02690
02691
02692
02693 ui_size = vpt_start.size();
02694
02695 for(ui_loop = 0; ui_loop < ui_size; ++ui_loop)
02696 {
02697
02698
02699 {
02700
02701
02702 saveLoop(vpt_start[ui_loop]);
02703 }
02704 }
02705 }
02706
02707 bool ParSpaceTrimmer::insertScanLineEvents(SScanLineEdge *ptEdge, ScanLineEventSet &rsptEvents, char cWhich)
02708 {
02709 SScanLineEvent *pt_new_event;
02710 std::pair<ScanLineEventSet::iterator, bool> pr_insert;
02711 Vec2d min;
02712 Vec2d max;
02713
02714
02715
02716
02717
02718
02719
02720 if(DCTPVecIsLesser(ptEdge->pclFromVertex->coords, ptEdge->pclToVertex->coords) )
02721
02722 {
02723 min[0] = ptEdge->pclFromVertex->coords[0];
02724 min[1] = ptEdge->pclFromVertex->coords[1];
02725 max[0] = ptEdge->pclToVertex->coords[0];
02726 max[1] = ptEdge->pclToVertex->coords[1];
02727 }
02728 else if(DCTPVecIsEqual(ptEdge->pclFromVertex->coords,
02729 ptEdge->pclToVertex->coords) )
02730
02731 {
02732 return false;
02733 }
02734 else
02735 {
02736 min[0] = ptEdge->pclToVertex->coords[0];
02737 min[1] = ptEdge->pclToVertex->coords[1];
02738 max[0] = ptEdge->pclFromVertex->coords[0];
02739 max[1] = ptEdge->pclFromVertex->coords[1];
02740 }
02741
02742 if(cWhich != 1)
02743 {
02744 pt_new_event = new SScanLineEvent;
02745 pt_new_event->ptEdge = ptEdge;
02746 pt_new_event->bStart = true;
02747 pt_new_event->clPos = min;
02748 pt_new_event->clOther = max;
02749
02750
02751
02752
02753
02754
02755
02756 pr_insert = rsptEvents.insert(pt_new_event);
02757 if(!pr_insert.second)
02758 {
02759 std::cerr << "Scan line event exists! aborting." << std::endl;
02760 exit(-1);
02761 }
02762 }
02763
02764 if(cWhich != 0)
02765 {
02766 pt_new_event = new SScanLineEvent;
02767 pt_new_event->ptEdge = ptEdge;
02768 pt_new_event->bStart = false;
02769 pt_new_event->clPos = max;
02770 pt_new_event->clOther = min;
02771
02772
02773
02774
02775
02776
02777
02778 pr_insert = rsptEvents.insert(pt_new_event);
02779 if(!pr_insert.second)
02780 {
02781 std::cerr << "Scan line event exists! aborting." << std::endl;
02782 exit(-1);
02783 }
02784 }
02785
02786 return true;
02787 }
02788
02789 SScanLineEntry *ParSpaceTrimmer::insertInScanLine(SScanLineEntry *ptActEntry, SScanLineEntry *ptScanLine)
02790 {
02791 SScanLineEntry *pt_prev_entry = NULL;
02792 SScanLineEntry *pt_next_entry;
02793
02794 pt_next_entry = ptScanLine;
02795 while(pt_next_entry)
02796 {
02797 if(isSLEntryLess(ptActEntry->ptEdge, pt_next_entry->ptEdge) )
02798 break;
02799 pt_prev_entry = pt_next_entry;
02800 pt_next_entry = pt_next_entry->ptNext;
02801 }
02802 ptActEntry->ptPrev = pt_prev_entry;
02803 ptActEntry->ptNext = pt_next_entry;
02804 if(pt_next_entry)
02805 pt_next_entry->ptPrev = ptActEntry;
02806 if(pt_prev_entry)
02807 pt_prev_entry->ptNext = ptActEntry;
02808 else
02809 return ptActEntry;
02810 return ptScanLine;
02811 }
02812
02813 void ParSpaceTrimmer::saveLoop(SScanLineEdge *ptEdge)
02814 {
02815 SScanLineEdge *pt_del;
02816 std::vector<DCTPVertex*> vpcl_cel;
02817
02818 if(ptEdge == NULL)
02819 {
02820 return;
02821 }
02822
02823 while(ptEdge)
02824 {
02825 vpcl_cel.push_back(ptEdge->pclFromVertex);
02826 pt_del = ptEdge;
02827 ptEdge = ptEdge->ptNext;
02828
02829 delete pt_del;
02830 }
02831
02832 if(vpcl_cel.size() == 1)
02833 {
02834 return;
02835 }
02836
02837
02838 vpcl_cel.push_back(vpcl_cel[0]);
02839
02840 vcel.push_back(vpcl_cel);
02841 }
02842
02843 void ParSpaceTrimmer::checkSLIntersection(SScanLineEntry *ptActEntry, ScanLineEventSet &rsptEvents)
02844 {
02845 SScanLineEntry *pt_prev_entry = ptActEntry->ptPrev;
02846 SScanLineEntry *pt_next_entry = ptActEntry->ptNext;
02847
02848
02849 if(pt_prev_entry)
02850 {
02851 ScanLineIntersect(ptActEntry, pt_prev_entry, rsptEvents);
02852 if(ptActEntry->ptEdge->bInvalid)
02853 {
02854 removeSLEntry(ptActEntry->ptPrev, rsptEvents);
02855 removeSLEntry(ptActEntry, rsptEvents);
02856 return;
02857 }
02858 }
02859 if(pt_next_entry)
02860 {
02861 ScanLineIntersect(ptActEntry, pt_next_entry, rsptEvents);
02862 if(ptActEntry->ptEdge->bInvalid)
02863 {
02864 removeSLEntry(ptActEntry, rsptEvents);
02865 removeSLEntry(ptActEntry->ptNext, rsptEvents);
02866 }
02867 }
02868 }
02869
02870 void ParSpaceTrimmer::ScanLineIntersect(SScanLineEntry *ptEntry1, SScanLineEntry *ptEntry2, ScanLineEventSet &rsptEvents)
02871 {
02872 SScanLineEdge *pt_edge1 = ptEntry1->ptEdge;
02873 SScanLineEdge *pt_edge2 = ptEntry2->ptEdge;
02874 SScanLineEdge *pt_new_edge;
02875 DCTPVertex *pcl_split_vertex;
02876
02877
02878
02879
02880
02881
02882
02883
02884
02885
02886
02887
02888
02889
02890
02891
02892
02893 double ad_s1[2];
02894 double ad_e1[2];
02895 double ad_s2[2];
02896 double ad_e2[2];
02897
02898 ad_s1[0] = pt_edge1->pclFromVertex->coords[0];
02899 ad_s1[1] = pt_edge1->pclFromVertex->coords[1];
02900 ad_e1[0] = pt_edge1->pclToVertex->coords[0];
02901 ad_e1[1] = pt_edge1->pclToVertex->coords[1];
02902 ad_s2[0] = pt_edge2->pclFromVertex->coords[0];
02903 ad_s2[1] = pt_edge2->pclFromVertex->coords[1];
02904 ad_e2[0] = pt_edge2->pclToVertex->coords[0];
02905 ad_e2[1] = pt_edge2->pclToVertex->coords[1];
02906
02907 const double cd_r1 = orient2d(ad_s1, ad_s2, ad_e2);
02908 const double cd_r2 = orient2d(ad_e1, ad_s2, ad_e2);
02909 if( ( (cd_r1 < 0.0) && (cd_r2 < 0.0) ) ||
02910 ( (cd_r1 > 0.0) && (cd_r2 > 0.0) ) )
02911 {
02912 return;
02913 }
02914
02915 const double cd_r3 = orient2d(ad_s2, ad_s1, ad_e1);
02916 const double cd_r4 = orient2d(ad_e2, ad_s1, ad_e1);
02917
02918 double cd_v1x = ad_e1[0] - ad_s1[0];
02919 double cd_v1y = ad_e1[1] - ad_s1[1];
02920 double cd_v2x = ad_e2[0] - ad_s2[0];
02921 double cd_v2y = ad_e2[1] - ad_s2[1];
02922
02923 double cd_b = cd_v1x * cd_v2y - cd_v1y * cd_v2x;
02924
02925 if( ( (cd_r3 < 0.0) && (cd_r4 < 0.0) ) ||
02926 ( (cd_r3 > 0.0) && (cd_r4 > 0.0) ) )
02927 {
02928 return;
02929 }
02930
02931 if( ((cd_r1 == 0.0) && (cd_r2 == 0.0) &&
02932 (cd_r3 == 0.0) && (cd_r4 == 0.0) ) ||
02933 osgAbs(cd_b) < 1e-32
02934
02935 )
02936 {
02937
02938 DCTPVertex *pcl_ip1;
02939 DCTPVertex *pcl_ip2;
02940 bool b_down1;
02941 bool b_down2;
02942
02943
02944
02945
02946
02947
02948
02949
02950 b_down1 = DCTPVecIsLesser(pt_edge1->pclFromVertex->coords, pt_edge1->pclToVertex->coords);
02951 b_down2 = DCTPVecIsLesser(pt_edge2->pclFromVertex->coords, pt_edge2->pclToVertex->coords);
02952 pcl_ip1 = b_down1 ? pt_edge1->pclFromVertex : pt_edge1->pclToVertex;
02953 pcl_ip2 = b_down2 ? pt_edge2->pclFromVertex : pt_edge2->pclToVertex;
02954
02955 if(DCTPVecIsEqual(pcl_ip1->coords, pcl_ip2->coords) )
02956 {
02957
02958
02959
02960 if( ( (b_down1) && !(b_down2) ) || (!(b_down1) && (b_down2) ) )
02961 {
02962
02963 pt_edge1->bInvalid = true;
02964 pt_edge2->bInvalid = true;
02965 }
02966 pcl_ip1 = b_down1 ? pt_edge1->pclToVertex : pt_edge1->pclFromVertex;
02967 pcl_ip2 = b_down2 ? pt_edge2->pclToVertex : pt_edge2->pclFromVertex;
02968
02969 pcl_split_vertex = DCTPVecIsLesser(pcl_ip1->coords, pcl_ip2->coords) ?
02970 pcl_ip1 : pcl_ip2;
02971 }
02972 else
02973 {
02974 pcl_split_vertex = DCTPVecIsGreater(pcl_ip1->coords, pcl_ip2->coords) ?
02975 pcl_ip1 : pcl_ip2;
02976 }
02977 }
02978 else
02979 {
02980
02981
02982
02983
02984
02985
02986 if( (cd_v1x * cd_v1x + cd_v1y * cd_v1y) < (cd_v2x * cd_v2x + cd_v2y * cd_v2y) )
02987 {
02988 const double cd_ppx = ad_s2[0] - ad_s1[0];
02989 const double cd_ppy = ad_s2[1] - ad_s1[1];
02990 const double cd_a = cd_ppx * cd_v2y - cd_ppy * cd_v2x;
02991
02992 double d_q = cd_a / cd_b;
02993
02994
02995
02996 if(d_q < DCTP_EPS)
02997 {
02998 pcl_split_vertex = pt_edge1->pclFromVertex;
02999 }
03000 else if(1.0 - d_q < DCTP_EPS)
03001 {
03002 pcl_split_vertex = pt_edge1->pclToVertex;
03003 }
03004 else
03005 {
03006 Vec3d cl_ip;
03007
03008 cl_ip[0] = pt_edge1->pclFromVertex->coords[0] + cd_v1x * d_q;
03009 cl_ip[1] = pt_edge1->pclFromVertex->coords[1] + cd_v1y * d_q;
03010
03011
03012 cl_ip[2] = 0.0;
03013 pcl_split_vertex = mesh->AddVertex(cl_ip);
03014 }
03015 }
03016 else
03017 {
03018 const double cd_ppx = ad_s1[0] - ad_s2[0];
03019 const double cd_ppy = ad_s1[1] - ad_s2[1];
03020 const double cd_a = cd_ppx * cd_v1y - cd_ppy * cd_v1x;
03021 const double cd_b = cd_v2x * cd_v1y - cd_v2y * cd_v1x;
03022 double d_q = cd_a / cd_b;
03023
03024
03025
03026 if(d_q < DCTP_EPS)
03027 {
03028 pcl_split_vertex = pt_edge2->pclFromVertex;
03029 }
03030 else if(1.0 - d_q < DCTP_EPS)
03031 {
03032 pcl_split_vertex = pt_edge2->pclToVertex;
03033 }
03034 else
03035 {
03036 Vec3d cl_ip;
03037
03038 cl_ip[0] = pt_edge2->pclFromVertex->coords[0] + cd_v2x * d_q;
03039 cl_ip[1] = pt_edge2->pclFromVertex->coords[1] + cd_v2y * d_q;
03040
03041
03042 cl_ip[2] = 0.0;
03043 pcl_split_vertex = mesh->AddVertex(cl_ip);
03044 }
03045 }
03046 }
03047
03048
03049
03050
03051
03052
03053 if( (pcl_split_vertex != pt_edge1->pclFromVertex) &&
03054 (pcl_split_vertex != pt_edge1->pclToVertex) )
03055 {
03056
03057
03058 pt_new_edge = new SScanLineEdge;
03059 if(DCTPVecIsLesser(pt_edge1->pclFromVertex->coords, pt_edge1->pclToVertex->coords) )
03060 {
03061 pt_new_edge->pclFromVertex = pt_edge1->pclFromVertex;
03062 if(pt_edge1->bInvalid)
03063 pt_new_edge->pclToVertex = pt_edge1->pclToVertex;
03064 else
03065 pt_new_edge->pclToVertex = pcl_split_vertex;
03066 pt_edge1->pclFromVertex = pcl_split_vertex;
03067 }
03068 else
03069 {
03070 pt_new_edge->pclToVertex = pt_edge1->pclToVertex;
03071 if(pt_edge1->bInvalid)
03072 pt_new_edge->pclFromVertex = pt_edge1->pclFromVertex;
03073 else
03074 pt_new_edge->pclFromVertex = pcl_split_vertex;
03075 pt_edge1->pclToVertex = pcl_split_vertex;
03076 }
03077 pt_new_edge->ptPrev = pt_edge1->ptPrev;
03078 if(pt_new_edge->ptPrev)
03079 pt_new_edge->ptPrev->ptNext = pt_new_edge;
03080 pt_new_edge->ptNext = pt_edge1->ptNext;
03081 if(pt_new_edge->ptNext)
03082 pt_new_edge->ptNext->ptPrev = pt_new_edge;
03083 pt_new_edge->ptEntry = pt_edge1->ptEntry;
03084 pt_new_edge->ptEntry->ptEdge = pt_new_edge;
03085
03086 pt_new_edge->bInvalid = pt_edge1->bInvalid;
03087 pt_edge1->ptPrev = NULL;
03088 pt_edge1->ptNext = NULL;
03089 pt_edge1->ptEntry = NULL;
03090 pt_edge1->bInvalid = false;
03091 insertScanLineEvents(pt_new_edge, rsptEvents, 1);
03092 insertScanLineEvents(pt_edge1, rsptEvents, 0);
03093
03094
03095 pcl_split_vertex->vertexinfo = reinterpret_cast<void*>(1);
03096 }
03097 if( (pcl_split_vertex != pt_edge2->pclFromVertex) &&
03098 (pcl_split_vertex != pt_edge2->pclToVertex) )
03099 {
03100
03101
03102 pt_new_edge = new SScanLineEdge;
03103 if(DCTPVecIsLesser(pt_edge2->pclFromVertex->coords, pt_edge2->pclToVertex->coords) )
03104 {
03105 pt_new_edge->pclFromVertex = pt_edge2->pclFromVertex;
03106 if(pt_edge2->bInvalid)
03107 pt_new_edge->pclToVertex = pt_edge2->pclToVertex;
03108 else
03109 pt_new_edge->pclToVertex = pcl_split_vertex;
03110 pt_edge2->pclFromVertex = pcl_split_vertex;
03111 }
03112 else
03113 {
03114 pt_new_edge->pclToVertex = pt_edge2->pclToVertex;
03115 if(pt_edge2->bInvalid)
03116 pt_new_edge->pclFromVertex = pt_edge2->pclFromVertex;
03117 else
03118 pt_new_edge->pclFromVertex = pcl_split_vertex;
03119 pt_edge2->pclToVertex = pcl_split_vertex;
03120 }
03121 pt_new_edge->ptPrev = pt_edge2->ptPrev;
03122 if(pt_new_edge->ptPrev)
03123 pt_new_edge->ptPrev->ptNext = pt_new_edge;
03124 pt_new_edge->ptNext = pt_edge2->ptNext;
03125 if(pt_new_edge->ptNext)
03126 pt_new_edge->ptNext->ptPrev = pt_new_edge;
03127 pt_new_edge->ptEntry = pt_edge2->ptEntry;
03128 pt_new_edge->ptEntry->ptEdge = pt_new_edge;
03129
03130 pt_new_edge->bInvalid = pt_edge2->bInvalid;
03131 pt_edge2->ptPrev = NULL;
03132 pt_edge2->ptNext = NULL;
03133 pt_edge2->ptEntry = NULL;
03134 pt_edge2->bInvalid = false;
03135 insertScanLineEvents(pt_new_edge, rsptEvents, 1);
03136 insertScanLineEvents(pt_edge2, rsptEvents, 0);
03137
03138
03139 pcl_split_vertex->vertexinfo = reinterpret_cast<void*>(1);
03140 }
03141 }
03142
03143 bool ParSpaceTrimmer::isSLEntryLess(SScanLineEdge *ptEdge1, SScanLineEdge *ptEdge2)
03144 {
03145 Vec2d top1;
03146 Vec2d bottom1;
03147 Vec2d top2;
03148 Vec2d bottom2;
03149
03150
03151
03152
03153
03154 if(DCTPVecIsLesser(ptEdge1->pclFromVertex->coords, ptEdge1->pclToVertex->coords) )
03155 {
03156 top1[0] = ptEdge1->pclFromVertex->coords[0];
03157 top1[1] = ptEdge1->pclFromVertex->coords[1];
03158 bottom1[0] = ptEdge1->pclToVertex->coords[0];
03159 bottom1[1] = ptEdge1->pclToVertex->coords[1];
03160 }
03161 else
03162 {
03163 top1[0] = ptEdge1->pclToVertex->coords[0];
03164 top1[1] = ptEdge1->pclToVertex->coords[1];
03165 bottom1[0] = ptEdge1->pclFromVertex->coords[0];
03166 bottom1[1] = ptEdge1->pclFromVertex->coords[1];
03167 }
03168 if(DCTPVecIsLesser(ptEdge2->pclFromVertex->coords, ptEdge2->pclToVertex->coords) )
03169 {
03170 top2[0] = ptEdge2->pclFromVertex->coords[0];
03171 top2[1] = ptEdge2->pclFromVertex->coords[1];
03172 bottom2[0] = ptEdge2->pclToVertex->coords[0];
03173 bottom2[1] = ptEdge2->pclToVertex->coords[1];
03174 }
03175 else
03176 {
03177 top2[0] = ptEdge2->pclToVertex->coords[0];
03178 top2[1] = ptEdge2->pclToVertex->coords[1];
03179 bottom2[0] = ptEdge2->pclFromVertex->coords[0];
03180 bottom2[1] = ptEdge2->pclFromVertex->coords[1];
03181 }
03182 if(DCTPVecIsNotEqual(top1, top2) )
03183 {
03184 double ad_s1[2];
03185
03186 double ad_s2[2];
03187 double ad_e2[2];
03188
03189 ad_s1[0] = top1[0];
03190 ad_s1[1] = top1[1];
03191
03192
03193 ad_s2[0] = top2[0];
03194 ad_s2[1] = top2[1];
03195 ad_e2[0] = bottom2[0];
03196 ad_e2[1] = bottom2[1];
03197
03198 const double cd_orient = orient2d(ad_s2, ad_e2, ad_s1);
03199 if(cd_orient != 0.0)
03200 {
03201 return (cd_orient > 0.0);
03202 }
03203 }
03204
03205
03206 Vec2d dir1 = bottom1 - top1;
03207 Vec2d dir2 = bottom2 - top2;
03208
03209 if(osgAbs(dir1[1]) < DCTP_EPS)
03210 {
03211 if(osgAbs(dir2[1]) < DCTP_EPS)
03212 {
03213 return (dir1[0] < dir2[0]);
03214 }
03215 return (dir1[0] < 0.0);
03216 }
03217 if(osgAbs(dir2[1]) < DCTP_EPS)
03218 {
03219 return (dir2[0] > 0.0);
03220 }
03221
03222 const double r1 = dir1[0] / dir1[1];
03223 const double r2 = dir2[0] / dir2[1];
03224
03225 if(osgAbs(r1 - r2) >= DCTP_EPS)
03226 {
03227 return (r1 < r2);
03228 }
03229
03230
03231 return ptEdge1 <ptEdge2;
03232 }
03233
03234 void ParSpaceTrimmer::removeSLEntry(SScanLineEntry *ptEntry, ScanLineEventSet &rsptEvents)
03235 {
03236 SScanLineEvent *pt_new_event;
03237 std::pair<ScanLineEventSet::iterator, bool> pr_insert;
03238 Vec2d min;
03239 Vec2d max;
03240
03241 if(DCTPVecIsLesser(ptEntry->ptEdge->pclFromVertex->coords, ptEntry->ptEdge->pclToVertex->coords) )
03242 {
03243 min[0] = ptEntry->ptEdge->pclFromVertex->coords[0];
03244 min[1] = ptEntry->ptEdge->pclFromVertex->coords[1];
03245 max[0] = ptEntry->ptEdge->pclToVertex->coords[0];
03246 max[1] = ptEntry->ptEdge->pclToVertex->coords[1];
03247 }
03248 else if(DCTPVecIsEqual(ptEntry->ptEdge->pclFromVertex->coords,
03249 ptEntry->ptEdge->pclToVertex->coords) )
03250 {
03251 return;
03252 }
03253 else
03254 {
03255 min[0] = ptEntry->ptEdge->pclToVertex->coords[0];
03256 min[1] = ptEntry->ptEdge->pclToVertex->coords[1];
03257 max[0] = ptEntry->ptEdge->pclFromVertex->coords[0];
03258 max[1] = ptEntry->ptEdge->pclFromVertex->coords[1];
03259 }
03260
03261
03262 pt_new_event = new SScanLineEvent;
03263 pt_new_event->ptEdge = ptEntry->ptEdge;
03264 pt_new_event->bStart = false;
03265 pt_new_event->clPos = max;
03266 pt_new_event->clOther = min;
03267
03268
03269
03270
03271
03272
03273
03274 unsigned int ui_old_size = rsptEvents.size();
03275
03276 rsptEvents.erase(pt_new_event);
03277
03278 delete pt_new_event;
03279
03280 if(rsptEvents.size() == ui_old_size)
03281 {
03282
03283 for(ScanLineEventSet::iterator i = rsptEvents.begin(); i != rsptEvents.end(); ++i)
03284 {
03285
03286
03287 if( ( (*i)->ptEdge == ptEntry->ptEdge) )
03288 {
03289 rsptEvents.erase(i);
03290 break;
03291 }
03292 }
03293
03294
03295
03296 }
03297
03298
03299 pt_new_event = new SScanLineEvent;
03300 pt_new_event->ptEdge = ptEntry->ptEdge;
03301 pt_new_event->bStart = false;
03302 pt_new_event->clPos = min;
03303 pt_new_event->clPos[1] -= 1.0;
03304 pt_new_event->clOther = min;
03305
03306
03307
03308
03309
03310
03311 pr_insert = rsptEvents.insert(pt_new_event);
03312 if(!pr_insert.second)
03313 {
03314 std::cerr << "Scan line event exists! aborting." << std::endl;
03315 exit(-1);
03316 }
03317
03318 }
03319
03320 DCTPVertex *ParSpaceTrimmer::intersectsLoop(DCTPVertex *pclVertex1, DCTPVertex *pclVertex2, unsigned int uiLoop)
03321 {
03322 unsigned int ui_vertex;
03323 unsigned int ui_size = vcel[uiLoop].size();
03324 DCTPVertex *pcl_prev_vertex;
03325 DCTPVertex *pcl_act_vertex = vcel[uiLoop][ui_size - 1];
03326 Vec3d cl_old;
03327
03328 for(ui_vertex = 0; ui_vertex < ui_size; ++ui_vertex)
03329 {
03330 pcl_prev_vertex = pcl_act_vertex;
03331 pcl_act_vertex = vcel[uiLoop][ui_vertex];
03332
03333 if( (DCTPVecIsNotEqual(pclVertex1->coords, pcl_prev_vertex->coords) ) &&
03334 (DCTPVecIsNotEqual(pclVertex1->coords, pcl_act_vertex->coords) ) &&
03335 (DCTPVecIsNotEqual(pclVertex2->coords, pcl_prev_vertex->coords) ) &&
03336 (DCTPVecIsNotEqual(pclVertex2->coords, pcl_act_vertex->coords) ) )
03337 {
03338
03339 double ad_s1[2];
03340 double ad_e1[2];
03341 double ad_s2[2];
03342 double ad_e2[2];
03343
03344 ad_s1[0] = pclVertex1->coords[0];
03345 ad_s1[1] = pclVertex1->coords[1];
03346 ad_e1[0] = pclVertex2->coords[0];
03347 ad_e1[1] = pclVertex2->coords[1];
03348 ad_s2[0] = pcl_prev_vertex->coords[0];
03349 ad_s2[1] = pcl_prev_vertex->coords[1];
03350 ad_e2[0] = pcl_act_vertex->coords[0];
03351 ad_e2[1] = pcl_act_vertex->coords[1];
03352
03353 const double cd_r1 = orient2d(ad_s1, ad_e1, ad_s2);
03354 const double cd_r2 = orient2d(ad_s1, ad_e1, ad_e2);
03355 if( ( (cd_r1 >= 0.0) || (cd_r2 >= 0.0) ) &&
03356 ( (cd_r1 <= 0.0) || (cd_r2 <= 0.0) ) )
03357 {
03358
03359 const double cd_r3 = orient2d(ad_s2, ad_e2, ad_s1);
03360 const double cd_r4 = orient2d(ad_s2, ad_e2, ad_e1);
03361 if( ( (cd_r3 >= 0.0) || (cd_r4 >= 0.0) ) &&
03362 ( (cd_r3 <= 0.0) || (cd_r4 <= 0.0) ) )
03363 {
03364 if( (cd_r1 == 0.0) && (cd_r2 == 0.0) && (cd_r3 == 0.0) && (cd_r4 == 0.0) )
03365 {
03366 const Vec3d ccl_v12 = pclVertex2->coords - pclVertex1->coords;
03367 const double cd_prod_a = ccl_v12.dot(pcl_act_vertex->coords - pclVertex1->coords);
03368 const double cd_prod_p = ccl_v12.dot(pcl_prev_vertex->coords - pclVertex1->coords);
03369 const double cd_qsize = ccl_v12.squareLength();
03370
03371 if( (cd_prod_a >= 0.0) && (cd_prod_a <= cd_qsize) )
03372 {
03373 if( (cd_prod_p >= 0.0) && (cd_prod_p <= cd_prod_a) )
03374 {
03375 return pcl_prev_vertex;
03376 }
03377 else
03378 {
03379 return pcl_act_vertex;
03380 }
03381 }
03382 else if( (cd_prod_p >= 0.0) && (cd_prod_p <= cd_qsize) )
03383 {
03384 return pcl_prev_vertex;
03385 }
03386 }
03387 else
03388 {
03389
03390
03391 cl_old = pclVertex1->coords - pclVertex2->coords;
03392 if( (Vec2d(pclVertex1->coords - pcl_prev_vertex->coords) ).dot(Vec2d(cl_old) ) -
03393 (Vec2d(pclVertex1->coords - pcl_act_vertex->coords) ).dot(Vec2d(cl_old) ) < DCTP_EPS)
03394 {
03395
03396 return pcl_prev_vertex;
03397 }
03398
03399 return pcl_act_vertex;
03400 }
03401 }
03402 }
03403 }
03404 }
03405
03406 return false;
03407 }
03408
03409 bool ParSpaceTrimmer::doIntersect(Vec2d clV1, Vec2d clV2, Vec2d clV3, Vec2d clV4, double &rdParam)
03410 {
03411 if(DCTPVecIsEqual(clV1, clV3) || DCTPVecIsEqual(clV1, clV4) )
03412 {
03413 if(DCTPVecIsEqual(clV1, clV3) )
03414 {
03415 clV3 = clV4;
03416 }
03417 const Vec2d v = clV3 - clV1;
03418 const Vec2d w = clV2 - clV1;
03419 const double c1 = v.dot(w);
03420 const double c2 = w.squareLength();
03421
03422
03423
03424
03425
03426
03427 if(c1 <= 0.0)
03428 {
03429 return false;
03430 }
03431 else if(c1 < c2)
03432 {
03433 if(DCTPVecIsNotEqual(clV1 + (w * (c1 / c2) ), clV3) )
03434 return false;
03435 }
03436 else
03437 {
03438 if(DCTPVecIsNotEqual(clV2, (clV1 + v * (c2 / c1) ) ) )
03439 return false;
03440 }
03441 rdParam = c1 / c2;
03442 if(rdParam < DCTP_EPS)
03443 {
03444 return false;
03445 }
03446 return true;
03447 }
03448
03449 double ad_s1[2];
03450 double ad_e1[2];
03451 double ad_s2[2];
03452 double ad_e2[2];
03453
03454 ad_s1[0] = clV1[0];
03455 ad_s1[1] = clV1[1];
03456 ad_e1[0] = clV2[0];
03457 ad_e1[1] = clV2[1];
03458 ad_s2[0] = clV3[0];
03459 ad_s2[1] = clV3[1];
03460 ad_e2[0] = clV4[0];
03461 ad_e2[1] = clV4[1];
03462
03463 const double cd_r3 = orient2d(ad_s2, ad_s1, ad_e1);
03464 const double cd_r4 = orient2d(ad_e2, ad_s1, ad_e1);
03465 if( ( (cd_r3 < 0.0) && (cd_r4 < 0.0) ) ||
03466 ( (cd_r3 > 0.0) && (cd_r4 > 0.0) ) )
03467 {
03468 return false;
03469 }
03470
03471 const double cd_r1 = orient2d(ad_s1, ad_s2, ad_e2);
03472 const double cd_r2 = orient2d(ad_e1, ad_s2, ad_e2);
03473 if( ( (cd_r1 < 0.0) && (cd_r2 < 0.0) ) ||
03474 ( (cd_r1 > 0.0) && (cd_r2 > 0.0) ) )
03475 {
03476 const Vec2d v = clV4 - clV3;
03477 const Vec2d w = clV2 - clV3;
03478 const double c1 = v.dot(w);
03479 const double c2 = v.squareLength();
03480 if(c1 <= 0.0)
03481 {
03482 if(DCTPVecIsNotEqual(clV2, clV3) )
03483 return false;
03484 }
03485 else if(c1 > c2)
03486 {
03487 if(DCTPVecIsNotEqual(clV2, clV4) )
03488 return false;
03489 }
03490 else
03491 {
03492 if(DCTPVecIsNotEqual(clV2, (clV3 + v * (c1 / c2) ) ) )
03493 return false;
03494
03495 }
03496
03497 rdParam = 1.0;
03498 return true;
03499 }
03500
03501
03502
03503
03504
03505 if( (cd_r1 == 0.0) && (cd_r2 == 0.0) &&
03506 (cd_r3 == 0.0) && (cd_r4 == 0.0) )
03507 {
03508
03509
03510 double d_tmp;
03511
03512 rdParam = -1.0;
03513 d_tmp = ( (clV4[0] - clV1[0]) * (clV2[0] - clV1[0])
03514 + (clV4[1] - clV1[1]) * (clV2[1] - clV1[1]) )
03515 / (clV2 - clV1).squareLength();
03516
03517 if(d_tmp > DCTP_EPS)
03518 rdParam = d_tmp;
03519 d_tmp = ( (clV3[0] - clV1[0]) * (clV2[0] - clV1[0])
03520 + (clV3[1] - clV1[1]) * (clV2[1] - clV1[1]) )
03521 / (clV2 - clV1).squareLength();
03522
03523 if(d_tmp > DCTP_EPS)
03524 {
03525 if( (rdParam < -0.5) || (d_tmp < rdParam) )
03526 rdParam = d_tmp;
03527 }
03528
03529
03530 return ( (rdParam > -0.5) && (rdParam <= 1.0) );
03531 }
03532
03533 if(cd_r1 == 0.0)
03534 {
03535
03536 return false;
03537 }
03538
03539
03540 const double cd_v1x = ad_e1[0] - ad_s1[0];
03541 const double cd_v1y = ad_e1[1] - ad_s1[1];
03542 const double cd_v2x = ad_e2[0] - ad_s2[0];
03543 const double cd_v2y = ad_e2[1] - ad_s2[1];
03544 const double cd_ppx = ad_s2[0] - ad_s1[0];
03545 const double cd_ppy = ad_s2[1] - ad_s1[1];
03546 const double cd_a = cd_ppx * cd_v2y - cd_ppy * cd_v2x;
03547 const double cd_b = cd_v1x * cd_v2y - cd_v1y * cd_v2x;
03548
03549 rdParam = cd_a / cd_b;
03550
03551
03552 if(rdParam <= 0.0)
03553 {
03554 rdParam = 0.0;
03555
03556
03557
03558 }
03559 if(rdParam >= 1.0)
03560 {
03561 rdParam = 1.0;
03562 }
03563 return true;
03564 }
03565
03566 void ParSpaceTrimmer::deleteVertexInfo()
03567 {
03568 dctpvertexset::iterator itspcl_end;
03569 dctpvertexset::iterator itspcl_v;
03570
03571 itspcl_end = mesh->vertices.end();
03572
03573 for(itspcl_v = mesh->vertices.begin(); itspcl_v != itspcl_end; ++itspcl_v)
03574 {
03575 if( (*itspcl_v)->vertexinfo)
03576 {
03577 #ifdef OSG_FORCE_NO_T_VERTICES
03578 delete (SPosNorm*)(*itspcl_v)->vertexinfo;
03579 #else
03580 delete static_cast<Vec3d*>((*itspcl_v)->vertexinfo);
03581 #endif
03582 (*itspcl_v)->vertexinfo = NULL;
03583 }
03584 }
03585 }
03586
03587
03588 bool ParSpaceTrimmer::isLoopValid(const unsigned int cuiLoop)
03589 {
03590 const unsigned int cui_loop_cnt = (*pvccrd).size();
03591 unsigned int ui_loop;
03592 unsigned int ui_edge_cnt;
03593 unsigned int ui_vertex_cnt;
03594 unsigned int ui_vertex;
03595
03596 Vec2d cl_ray_start;
03597 Vec2d cl_ray_end;
03598
03599 ui_vertex_cnt = (*pvccrd)[cuiLoop].size();
03600
03601
03602
03603
03604
03605
03606
03607
03608
03609
03610
03611
03612
03613
03614
03615
03616
03617
03618 if( (*m_pvbReversed)[cuiLoop])
03619 {
03620 ui_edge_cnt = 1;
03621 }
03622 else
03623 {
03624 ui_edge_cnt = 0;
03625 }
03626
03627 cl_ray_start = ( (*pvccrd)[cuiLoop][0] + (*pvccrd)[cuiLoop][1]) * 0.5;
03628
03629 cl_ray_end[0] = -FLT_MAX;
03630 cl_ray_end[1] = cl_ray_start[1];
03631
03632
03633
03634 for(ui_loop = 0; ui_loop < cui_loop_cnt; ++ui_loop)
03635 {
03636 if(ui_loop != cuiLoop)
03637 {
03638 ui_vertex_cnt = (*pvccrd)[ui_loop].size();
03639
03640 for(ui_vertex = 0; ui_vertex < ui_vertex_cnt; ++ui_vertex)
03641 {
03642
03643 if(intersectsRay( (*pvccrd)[ui_loop][ui_vertex],
03644 (*pvccrd)[ui_loop][(ui_vertex + 1) % ui_vertex_cnt],
03645 cl_ray_start, cl_ray_end) )
03646 {
03647
03648 ++ui_edge_cnt;
03649 }
03650 }
03651 }
03652 }
03653
03654 if( (ui_edge_cnt & 1) != 0)
03655 {
03656
03657 }
03658
03659 return ( (ui_edge_cnt & 1) == 0);
03660 }
03661
03662
03663 bool ParSpaceTrimmer::intersectsRay(const Vec2d cclV1, const Vec2d cclV2, const Vec2d cclStart, const Vec2d cclEnd)
03664 {
03665 double ad_v1[2];
03666 double ad_v2[2];
03667 double ad_start[2];
03668 double ad_end[2];
03669
03670 if(DCTPVecIsLesser(cclV1, cclV2) )
03671 {
03672 ad_v1[0] = cclV1[0];
03673 ad_v1[1] = cclV1[1];
03674 ad_v2[0] = cclV2[0];
03675 ad_v2[1] = cclV2[1];
03676 }
03677 else
03678 {
03679 ad_v1[0] = cclV2[0];
03680 ad_v1[1] = cclV2[1];
03681 ad_v2[0] = cclV1[0];
03682 ad_v2[1] = cclV1[1];
03683 }
03684 ad_start[0] = cclStart[0];
03685 ad_start[1] = cclStart[1];
03686 ad_end[0] = cclEnd[0];
03687 ad_end[1] = cclEnd[1];
03688
03689 const double cd_c1 = orient2d(ad_start, ad_end, ad_v1);
03690
03691 if(cd_c1 == 0.0)
03692 {
03693 return false;
03694 }
03695
03696 const double cd_c2 = orient2d(ad_start, ad_end, ad_v2);
03697
03698 if( ( (cd_c1 < 0.0) && (cd_c2 < 0.0) ) || ( (cd_c1 > 0.0) && (cd_c2 > 0.0) ) )
03699 {
03700 return false;
03701 }
03702
03703 const double cd_c3 = orient2d(ad_v1, ad_v2, ad_start);
03704 const double cd_c4 = orient2d(ad_v1, ad_v2, ad_end);
03705
03706 if( ( (cd_c3 < 0.0) && (cd_c4 < 0.0) ) || ( (cd_c3 > 0.0) && (cd_c4 > 0.0) ) )
03707 {
03708 return false;
03709 }
03710
03711 return true;
03712 }
03713
03714
03715 #ifdef OSG_USE_SIMPLIFIER
03716 double ParSpaceTrimmer::DistToEdge(const Vec3d cclPoint, const Vec3d cclLine1, const Vec3d cclLine2) const
03717 {
03718 const Vec3d ccl_v = cclLine2 - cclLine1;
03719 const Vec3d ccl_w = cclPoint - cclLine1;
03720
03721 const double cd_c1 = ccl_v[0] * ccl_w[0] + ccl_v[1] * ccl_w[1] + ccl_v[2] * ccl_w[2];
03722
03723 if(cd_c1 <= 0.0)
03724 {
03725 return (cclPoint - cclLine1).squareLength();
03726 }
03727
03728 const double cd_c2 = ccl_v.squareLength();
03729
03730 if(cd_c1 >= cd_c2)
03731 {
03732 return (cclPoint - cclLine2).squareLength();
03733 }
03734
03735 return (cclPoint - (cclLine1 + ccl_v * (cd_c1 / cd_c2) ) ).squareLength();
03736 }
03737 #endif
