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 #ifndef __VCGLIB_TRI_CLIP
00032 #define __VCGLIB_TRI_CLIP
00033
00034 #include <vector>
00035
00036 #ifdef _WIN32
00037 #ifndef __MINGW32__
00038 #include <hash_map>
00039 #define STDEXT stdext
00040 #else
00041 #include <ext/hash_map>
00042 #define STDEXT __gnu_cxx
00043 #endif
00044 #else
00045 #include <ext/hash_map>
00046 #define STDEXT __gnu_cxx
00047 #endif
00048 namespace vcg
00049 {
00050 namespace tri
00051 {
00052
00053 template <typename MESH_TYPE>
00054 class GenericVertexInterpolator
00055 {
00056 public:
00057 typedef typename MESH_TYPE::VertexType VertexType;
00058 typedef GenericVertexInterpolator<MESH_TYPE> ClassType;
00059 typedef typename VertexType::CoordType CoordType;
00060 typedef typename CoordType::ScalarType ScalarType;
00061 GenericVertexInterpolator(MESH_TYPE &_m) : m(_m) {}
00062 private:
00063 MESH_TYPE &m;
00064 public:
00065 inline void operator () (const VertexType & v0, const VertexType & v1, const VertexType & v2, const ScalarType & a, const ScalarType & b, VertexType & r) const
00066 {
00067
00068 r.P() = v0.P() + (v1.P() - v0.P()) * a + (v2.P() - v0.P()) * b;
00069
00070
00071 if (tri::HasPerVertexNormal(m))
00072 {
00073 r.N() = v0.cN() + (v1.cN() - v0.cN()) * a + (v2.cN() - v0.cN()) * b;
00074 }
00075
00076
00077 if (tri::HasPerVertexColor(m))
00078 {
00079 vcg::Point4<ScalarType> vc[3];
00080 vc[0].Import(v0.cC());
00081 vc[1].Import(v1.cC());
00082 vc[2].Import(v2.cC());
00083 const vcg::Point4<ScalarType> rc = (vc[0] + (vc[1] - vc[0]) * a + (vc[2] - vc[0]) * b);
00084 r.C()[0] = (typename vcg::Color4b::ScalarType)(rc[0]);
00085 r.C()[1] = (typename vcg::Color4b::ScalarType)(rc[1]);
00086 r.C()[2] = (typename vcg::Color4b::ScalarType)(rc[2]);
00087 r.C()[3] = (typename vcg::Color4b::ScalarType)(rc[3]);
00088 }
00089
00090
00091 if (tri::HasPerVertexTexCoord(m))
00092 {
00093 const short nt = 1;
00094 for (short i=0; i<nt; ++i)
00095 {
00096 r.T().t(i) = v0.cT().t(i) + (v1.cT().t(i) - v0.cT().t(i)) * a + (v2.cT().t(i) - v0.cT().t(i)) * b;
00097 }
00098 }
00099 }
00100 };
00101 template <typename TRIMESHTYPE>
00102 class TriMeshClipper
00103 {
00104 public:
00105
00106 typedef TriMeshClipper<TRIMESHTYPE> ClassType;
00107 typedef TRIMESHTYPE TriMeshType;
00108 typedef typename TriMeshType::FaceType FaceType;
00109 typedef typename FaceType::VertexType VertexType;
00110 typedef typename VertexType::CoordType CoordType;
00111 typedef typename CoordType::ScalarType ScalarType;
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132
00133 template <class ScalarType>
00134 class VertexClipInfo
00135 {
00136 public:
00137
00138
00139 ScalarType fU;
00140 ScalarType fV;
00141 unsigned int idx;
00142 unsigned int tref;
00143 };
00144 typedef typename std::vector< VertexClipInfo<ScalarType> > VertexClipInfoVec;
00145 class TriangleInfo
00146 {
00147 public:
00148 typedef TriangleInfo ClassType;
00149
00150 unsigned int v[3];
00151 unsigned int idx;
00152 };
00153
00154 typedef std::vector<TriangleInfo> TriangleInfoVec;
00155
00156 class EdgeIsect
00157 {
00158 public:
00159 CoordType p;
00160 unsigned int idx;
00161 };
00162
00163 template <typename VERTEXINTEPOLATOR>
00164 static inline void Box(const Box3<ScalarType> & b, VERTEXINTEPOLATOR & vInterp, TriMeshType & m)
00165 {
00166 std::vector<unsigned int> facesToDelete;
00167 ClassType::Box(b, vInterp, m, facesToDelete);
00168 for (size_t i=0; i<facesToDelete.size(); ++i)
00169 {
00170 m.face[facesToDelete[i]].SetD();
00171 }
00172 }
00173
00174 class EdgeIntersections
00175 {
00176 public:
00177 unsigned int n;
00178 EdgeIsect isects[6];
00179
00180 EdgeIntersections(void)
00181 {
00182 this->n = 0;
00183 }
00184 };
00185
00186 typedef STDEXT::hash_map<unsigned int, EdgeIntersections> UIntHMap;
00187 typedef typename UIntHMap::iterator UIntHMap_i;
00188 typedef typename UIntHMap::value_type UIntHMap_v;
00189
00190 typedef STDEXT::hash_map<unsigned int, UIntHMap> EdgeMap;
00191 typedef typename EdgeMap::iterator EdgeMap_i;
00192 typedef typename EdgeMap::value_type EdgeMap_v;
00193
00194 typedef typename TriMeshType::FaceIterator FaceIterator;
00195
00196 template <typename VERTEXINTEPOLATOR, typename FACEINDEXCONTAINER>
00197 static inline void Box(const Box3<ScalarType> & b, VERTEXINTEPOLATOR & vInterp, TriMeshType & m, FACEINDEXCONTAINER & facesToDelete)
00198 {
00199 if (m.fn <= 0)
00200 {
00201 return;
00202 }
00203
00204 EdgeMap edges;
00205 VertexClipInfoVec vInfos;
00206 TriangleInfoVec tInfos;
00207
00208 CoordType vTriangle[4];
00209 CoordType vClipped[64];
00210
00211 CoordType pvP0[64];
00212 CoordType pvP1[64];
00213
00214 unsigned int numDeletedTris = 0;
00215 unsigned int numTriangles = 0;
00216 unsigned int numVertices = 0;
00217
00218 unsigned int vIdx = (unsigned int)(m.vn);
00219 unsigned int tIdx = (unsigned int)(m.fn);
00220
00221 ScalarType boxOffsets[6];
00222
00223 boxOffsets[0] = b.min[0];
00224 boxOffsets[1] = -b.max[0];
00225 boxOffsets[2] = b.min[1];
00226 boxOffsets[3] = -b.max[1];
00227 boxOffsets[4] = b.min[2];
00228 boxOffsets[5] = -b.max[2];
00229
00230 UIntHMap emptyMap;
00231 EdgeIntersections emptyIsects;
00232
00233 const ScalarType eps = (ScalarType)(1e-6);
00234
00235 for (FaceIterator it=m.face.begin(); it!=m.face.end(); ++it)
00236 {
00237 if ((*it).IsD())
00238 {
00239 continue;
00240 }
00241
00242 unsigned int cc[3];
00243
00244 cc[0] = ClassType::BoxClipCode(boxOffsets, (*it).V(0)->P());
00245 cc[1] = ClassType::BoxClipCode(boxOffsets, (*it).V(1)->P());
00246 cc[2] = ClassType::BoxClipCode(boxOffsets, (*it).V(2)->P());
00247
00248 if ((cc[0] | cc[1] | cc[2]) == 0)
00249 {
00250 continue;
00251 }
00252
00253 const unsigned int refT = (unsigned int)(std::distance(m.face.begin(), it));
00254
00255 if ((cc[0] & cc[1] & cc[2]) != 0)
00256 {
00257 facesToDelete.push_back(refT);
00258 (*it).SetD();
00259 numDeletedTris++;
00260 continue;
00261 }
00262
00263 facesToDelete.push_back(refT);
00264
00265 vTriangle[0] = (*it).V(0)->P();
00266 vTriangle[1] = (*it).V(1)->P();
00267 vTriangle[2] = (*it).V(2)->P();
00268 vTriangle[3] = (*it).V(0)->P();
00269
00270 unsigned int n, n0, n1;
00271
00272 ClipPolygonLine(0, b.min[0], vTriangle, 4, pvP1, n1);
00273 ClipPolygonLine(1, b.max[0], pvP1, n1, pvP0, n0);
00274
00275 ClipPolygonLine(2, b.min[1], pvP0, n0, pvP1, n1);
00276 ClipPolygonLine(3, b.max[1], pvP1, n1, pvP0, n0);
00277
00278 ClipPolygonLine(4, b.min[2], pvP0, n0, pvP1, n1);
00279 ClipPolygonLine(5, b.max[2], pvP1, n1, vClipped, n);
00280
00281 assert(n < 64);
00282
00283 unsigned int firstV, lastV;
00284
00285 if (n > 2)
00286 {
00287 if (vClipped[0] == vClipped[n - 1])
00288 {
00289 n--;
00290 }
00291
00292 const CoordType vU = vTriangle[1] - vTriangle[0];
00293 const CoordType vV = vTriangle[2] - vTriangle[0];
00294
00295 const ScalarType tArea = (vU ^ vV).SquaredNorm();
00296 if (tArea < eps)
00297 {
00298 continue;
00299 }
00300
00301 unsigned int tvidx[3];
00302 tvidx[0] = (*it).V(0) - &(*(m.vert.begin()));
00303 tvidx[1] = (*it).V(1) - &(*(m.vert.begin()));
00304 tvidx[2] = (*it).V(2) - &(*(m.vert.begin()));
00305
00306 numTriangles += n - 2;
00307
00308 size_t vBegin = vInfos.size();
00309
00310 VertexClipInfo<ScalarType> vnfo;
00311 TriangleInfo tnfo;
00312
00313 unsigned int vmin[3];
00314 unsigned int vmax[3];
00315
00316 if (tvidx[0] < tvidx[1])
00317 {
00318 vmin[0] = tvidx[0];
00319 vmax[0] = tvidx[1];
00320 }
00321 else
00322 {
00323 vmin[0] = tvidx[1];
00324 vmax[0] = tvidx[0];
00325 }
00326
00327 if (tvidx[0] < tvidx[2])
00328 {
00329 vmin[1] = tvidx[0];
00330 vmax[1] = tvidx[2];
00331 }
00332 else
00333 {
00334 vmin[1] = tvidx[2];
00335 vmax[1] = tvidx[0];
00336 }
00337
00338 if (tvidx[1] < tvidx[2])
00339 {
00340 vmin[2] = tvidx[1];
00341 vmax[2] = tvidx[2];
00342 }
00343 else
00344 {
00345 vmin[2] = tvidx[2];
00346 vmax[2] = tvidx[1];
00347 }
00348
00349 for (unsigned int i=0; i<n; ++i)
00350 {
00351 vnfo.tref = refT;
00352
00353 const CoordType vP = vClipped[i] - vTriangle[0];
00354
00355 ScalarType tAreaU = (vU ^ vP).SquaredNorm();
00356 ScalarType tAreaV = (vP ^ vV).SquaredNorm();
00357
00358 vnfo.fU = (ScalarType)(sqrt(tAreaU / tArea));
00359 vnfo.fV = (ScalarType)(sqrt(tAreaV / tArea));
00360
00361 if (vClipped[i] == vTriangle[0])
00362 {
00363 vnfo.idx = tvidx[0];
00364 }
00365 else if (vClipped[i] == vTriangle[1])
00366 {
00367 vnfo.idx = tvidx[1];
00368 }
00369 else if (vClipped[i] == vTriangle[2])
00370 {
00371 vnfo.idx = tvidx[2];
00372 }
00373 else if (vnfo.fV < eps)
00374 {
00375 std::pair<EdgeMap_i, bool> mi = edges.insert(std::make_pair(vmin[1], emptyMap));
00376 std::pair<UIntHMap_i, bool> hi = (*(mi.first)).second.insert(std::make_pair(vmax[1], emptyIsects));
00377 bool found = false;
00378 for (unsigned int s=0; s<(*(hi.first)).second.n; ++s)
00379 {
00380 if (vClipped[i] == (*(hi.first)).second.isects[s].p)
00381 {
00382 found = true;
00383 vnfo.idx = (*(hi.first)).second.isects[s].idx;
00384 break;
00385 }
00386 }
00387 if (!found)
00388 {
00389 vnfo.idx = vIdx++;
00390 numVertices++;
00391 vInfos.push_back(vnfo);
00392
00393 (*(hi.first)).second.isects[(*(hi.first)).second.n].p = vClipped[i];
00394 (*(hi.first)).second.isects[(*(hi.first)).second.n].idx = vnfo.idx;
00395 (*(hi.first)).second.n++;
00396 }
00397 }
00398 else if (vnfo.fU < eps)
00399 {
00400 std::pair<EdgeMap_i, bool> mi = edges.insert(std::make_pair(vmin[0], emptyMap));
00401 std::pair<UIntHMap_i, bool> hi = (*(mi.first)).second.insert(std::make_pair(vmax[0], emptyIsects));
00402 bool found = false;
00403 for (unsigned int s=0; s<(*(hi.first)).second.n; ++s)
00404 {
00405 if (vClipped[i] == (*(hi.first)).second.isects[s].p)
00406 {
00407 found = true;
00408 vnfo.idx = (*(hi.first)).second.isects[s].idx;
00409 break;
00410 }
00411 }
00412 if (!found)
00413 {
00414 vnfo.idx = vIdx++;
00415 numVertices++;
00416 vInfos.push_back(vnfo);
00417
00418 (*(hi.first)).second.isects[(*(hi.first)).second.n].p = vClipped[i];
00419 (*(hi.first)).second.isects[(*(hi.first)).second.n].idx = vnfo.idx;
00420 (*(hi.first)).second.n++;
00421 }
00422 }
00423 else if ((vnfo.fU + vnfo.fV) >= ((ScalarType)(1.0 - 1e-5)))
00424 {
00425 std::pair<EdgeMap_i, bool> mi = edges.insert(std::make_pair(vmin[2], emptyMap));
00426 std::pair<UIntHMap_i, bool> hi = (*(mi.first)).second.insert(std::make_pair(vmax[2], emptyIsects));
00427 bool found = false;
00428 for (unsigned int s=0; s<(*(hi.first)).second.n; ++s)
00429 {
00430 if (vClipped[i] == (*(hi.first)).second.isects[s].p)
00431 {
00432 found = true;
00433 vnfo.idx = (*(hi.first)).second.isects[s].idx;
00434 break;
00435 }
00436 }
00437 if (!found)
00438 {
00439 vnfo.idx = vIdx++;
00440 numVertices++;
00441 vInfos.push_back(vnfo);
00442
00443 (*(hi.first)).second.isects[(*(hi.first)).second.n].p = vClipped[i];
00444 (*(hi.first)).second.isects[(*(hi.first)).second.n].idx = vnfo.idx;
00445 (*(hi.first)).second.n++;
00446 }
00447 }
00448 else
00449 {
00450 vnfo.idx = vIdx++;
00451 numVertices++;
00452 vInfos.push_back(vnfo);
00453 }
00454
00455 if (i == 0)
00456 {
00457 firstV = vnfo.idx;
00458 }
00459
00460 if (i > 1)
00461 {
00462 tnfo.idx = tIdx++;
00463 tnfo.v[0] = firstV;
00464 tnfo.v[1] = lastV;
00465 tnfo.v[2] = vnfo.idx;
00466
00467 tInfos.push_back(tnfo);
00468 }
00469
00470 lastV = vnfo.idx;
00471 }
00472 }
00473 }
00474
00475 if (numTriangles == 0)
00476 {
00477 return;
00478 }
00479
00480 const unsigned int vSize = (unsigned int)(m.vn);
00481 const unsigned int tSize = (unsigned int)(m.fn);
00482
00483 typedef Allocator<TriMeshType> TriMeshAllocatorType;
00484
00485 TriMeshAllocatorType::AddVertices(m, numVertices);
00486 TriMeshAllocatorType::AddFaces(m, numTriangles);
00487
00488 unsigned int j = vSize;
00489 for (size_t i=0; i<vInfos.size(); ++i)
00490 {
00491 if (vInfos[i].idx >= vSize)
00492 {
00493 const unsigned int tref = vInfos[i].tref;
00494 vInterp(*(m.face[tref].V(0)), *(m.face[tref].V(1)), *(m.face[tref].V(2)), vInfos[i].fV, vInfos[i].fU, m.vert[j]);
00495 j++;
00496 }
00497 }
00498
00499 j = tSize;
00500 for (size_t i=0; i<tInfos.size(); ++i)
00501 {
00502 m.face[j].V(0) = &(m.vert[tInfos[i].v[0]]);
00503 m.face[j].V(1) = &(m.vert[tInfos[i].v[1]]);
00504 m.face[j].V(2) = &(m.vert[tInfos[i].v[2]]);
00505 j++;
00506 }
00507 }
00508
00509
00510
00511
00512
00513
00514
00515
00516
00517
00518
00519
00520
00521
00522
00523
00524
00525
00526 template <typename VERTEXINTEPOLATOR>
00527 static inline void Box(const Box3<ScalarType> & b, VERTEXINTEPOLATOR & vInterp, const TriMeshType & m, TriMeshType & r)
00528 {
00529 r.Clear();
00530
00531 if (m.fn <= 0)
00532 {
00533 return;
00534 }
00535
00536 class VertexClipInfo
00537 {
00538 public:
00539 typedef VertexClipInfo ClassType;
00540
00541 ScalarType fU;
00542 ScalarType fV;
00543 unsigned int idx;
00544 unsigned int tref;
00545 };
00546
00547 typedef std::vector<VertexClipInfo> VertexClipInfoVec;
00548
00549 class TriangleInfo
00550 {
00551 public:
00552 typedef TriangleInfo ClassType;
00553
00554 unsigned int v[3];
00555 unsigned int idx;
00556 };
00557
00558 typedef std::vector<TriangleInfo> TriangleInfoVec;
00559
00560 class EdgeIsect
00561 {
00562 public:
00563 CoordType p;
00564 unsigned int idx;
00565 };
00566
00567 class EdgeIntersections
00568 {
00569 public:
00570 unsigned int n;
00571 EdgeIsect isects[6];
00572
00573 EdgeIntersections(void)
00574 {
00575 this->n = 0;
00576 }
00577 };
00578
00579 typedef STDEXT::hash_map<unsigned int, EdgeIntersections> UIntHMap;
00580 typedef typename UIntHMap::iterator UIntHMap_i;
00581 typedef typename UIntHMap::value_type UIntHMap_v;
00582
00583 typedef STDEXT::hash_map<unsigned int, UIntHMap> EdgeMap;
00584 typedef typename EdgeMap::iterator EdgeMap_i;
00585 typedef typename EdgeMap::value_type EdgeMap_v;
00586
00587 typedef STDEXT::hash_map<unsigned int, unsigned int> UIHMap;
00588 typedef typename UIHMap::iterator UIHMap_i;
00589
00590 typedef typename TriMeshType::ConstFaceIterator ConstFaceIterator;
00591
00592 UIHMap origVertsMap;
00593 EdgeMap edges;
00594 VertexClipInfoVec vInfos;
00595 TriangleInfoVec tInfos;
00596
00597 CoordType vTriangle[4];
00598 CoordType vClipped[64];
00599
00600 CoordType pvP0[64];
00601 CoordType pvP1[64];
00602
00603 unsigned int numDeletedTris = 0;
00604 unsigned int numTriangles = 0;
00605 unsigned int numVertices = 0;
00606
00607 unsigned int vIdx = 0;
00608 unsigned int tIdx = 0;
00609
00610 ScalarType boxOffsets[6];
00611
00612 boxOffsets[0] = b.min[0];
00613 boxOffsets[1] = -b.max[0];
00614 boxOffsets[2] = b.min[1];
00615 boxOffsets[3] = -b.max[1];
00616 boxOffsets[4] = b.min[2];
00617 boxOffsets[5] = -b.max[2];
00618
00619 UIntHMap emptyMap;
00620 EdgeIntersections emptyIsects;
00621
00622 const ScalarType eps = (ScalarType)(1e-6);
00623
00624 for (ConstFaceIterator it=m.face.begin(); it!=m.face.end(); ++it)
00625 {
00626 if ((*it).IsD())
00627 {
00628 continue;
00629 }
00630
00631 unsigned int cc[3];
00632
00633 cc[0] = ClassType::BoxClipCode(boxOffsets, (*it).V(0)->P());
00634 cc[1] = ClassType::BoxClipCode(boxOffsets, (*it).V(1)->P());
00635 cc[2] = ClassType::BoxClipCode(boxOffsets, (*it).V(2)->P());
00636
00637 if ((cc[0] | cc[1] | cc[2]) == 0)
00638 {
00639 TriangleInfo tnfo;
00640 VertexClipInfo vnfo;
00641
00642 tnfo.idx = tIdx++;
00643
00644 for (int i=0; i<3; ++i)
00645 {
00646 const unsigned int v = (*it).V(i) - &(*(m.vert.begin()));
00647 std::pair<UIHMap_i, bool> hi = origVertsMap.insert(std::make_pair(v, vIdx));
00648
00649 if (hi.second)
00650 {
00651 vnfo.idx = v;
00652 vInfos.push_back(vnfo);
00653 tnfo.v[i] = vIdx++;
00654 }
00655 else
00656 {
00657 tnfo.v[i] = (*(hi.first)).second;
00658 }
00659 }
00660
00661 tInfos.push_back(tnfo);
00662
00663 continue;
00664 }
00665
00666 if ((cc[0] & cc[1] & cc[2]) != 0)
00667 {
00668 numDeletedTris++;
00669 continue;
00670 }
00671
00672 vTriangle[0] = (*it).V(0)->P();
00673 vTriangle[1] = (*it).V(1)->P();
00674 vTriangle[2] = (*it).V(2)->P();
00675 vTriangle[3] = (*it).V(0)->P();
00676
00677 unsigned int n, n0, n1;
00678
00679 ClipPolygonLine(0, b.min[0], vTriangle, 4, pvP1, n1);
00680 ClipPolygonLine(1, b.max[0], pvP1, n1, pvP0, n0);
00681
00682 ClipPolygonLine(2, b.min[1], pvP0, n0, pvP1, n1);
00683 ClipPolygonLine(3, b.max[1], pvP1, n1, pvP0, n0);
00684
00685 ClipPolygonLine(4, b.min[2], pvP0, n0, pvP1, n1);
00686 ClipPolygonLine(5, b.max[2], pvP1, n1, vClipped, n);
00687
00688 assert(n < 64);
00689
00690 unsigned int firstV, lastV;
00691
00692
00693 if (n > 2)
00694 {
00695 if (vClipped[0] == vClipped[n - 1])
00696 {
00697 n--;
00698 }
00699
00700 const CoordType vU = vTriangle[1] - vTriangle[0];
00701 const CoordType vV = vTriangle[2] - vTriangle[0];
00702
00703 const ScalarType tArea = (vU ^ vV).SquaredNorm();
00704 if (tArea < eps)
00705 {
00706 continue;
00707 }
00708
00709 unsigned int tvidx[3];
00710 tvidx[0] = (*it).V(0) - &(*(m.vert.begin()));
00711 tvidx[1] = (*it).V(1) - &(*(m.vert.begin()));
00712 tvidx[2] = (*it).V(2) - &(*(m.vert.begin()));
00713
00714 unsigned int refT = (unsigned int)(std::distance(m.face.begin(), it));
00715
00716 numTriangles += n - 2;
00717
00718 size_t vBegin = vInfos.size();
00719
00720 VertexClipInfo vnfo;
00721 TriangleInfo tnfo;
00722
00723 unsigned int vmin[3];
00724 unsigned int vmax[3];
00725
00726 if (tvidx[0] < tvidx[1])
00727 {
00728 vmin[0] = tvidx[0];
00729 vmax[0] = tvidx[1];
00730 }
00731 else
00732 {
00733 vmin[0] = tvidx[1];
00734 vmax[0] = tvidx[0];
00735 }
00736
00737 if (tvidx[0] < tvidx[2])
00738 {
00739 vmin[1] = tvidx[0];
00740 vmax[1] = tvidx[2];
00741 }
00742 else
00743 {
00744 vmin[1] = tvidx[2];
00745 vmax[1] = tvidx[0];
00746 }
00747
00748 if (tvidx[1] < tvidx[2])
00749 {
00750 vmin[2] = tvidx[1];
00751 vmax[2] = tvidx[2];
00752 }
00753 else
00754 {
00755 vmin[2] = tvidx[2];
00756 vmax[2] = tvidx[1];
00757 }
00758
00759 for (unsigned int i=0; i<n; ++i)
00760 {
00761 vnfo.tref = refT;
00762
00763 const CoordType vP = vClipped[i] - vTriangle[0];
00764
00765 ScalarType tAreaU = (vU ^ vP).SquaredNorm();
00766 ScalarType tAreaV = (vP ^ vV).SquaredNorm();
00767
00768 vnfo.fU = (ScalarType)(sqrt(tAreaU / tArea));
00769 vnfo.fV = (ScalarType)(sqrt(tAreaV / tArea));
00770
00771 unsigned int currVIdx;
00772
00773 if (vClipped[i] == vTriangle[0])
00774 {
00775 std::pair<UIHMap_i, bool> hi = origVertsMap.insert(std::make_pair(tvidx[0], vIdx));
00776 if (hi.second)
00777 {
00778 vnfo.idx = tvidx[0];
00779 vInfos.push_back(vnfo);
00780 currVIdx = vIdx++;
00781 }
00782 else
00783 {
00784 currVIdx = (*(hi.first)).second;
00785 }
00786 }
00787 else if (vClipped[i] == vTriangle[1])
00788 {
00789 std::pair<UIHMap_i, bool> hi = origVertsMap.insert(std::make_pair(tvidx[1], vIdx));
00790 if (hi.second)
00791 {
00792 vnfo.idx = tvidx[1];
00793 vInfos.push_back(vnfo);
00794 currVIdx = vIdx++;
00795 }
00796 else
00797 {
00798 currVIdx = (*(hi.first)).second;
00799 }
00800 }
00801 else if (vClipped[i] == vTriangle[2])
00802 {
00803 std::pair<UIHMap_i, bool> hi = origVertsMap.insert(std::make_pair(tvidx[2], vIdx));
00804 if (hi.second)
00805 {
00806 vnfo.idx = tvidx[2];
00807 vInfos.push_back(vnfo);
00808 currVIdx = vIdx++;
00809 }
00810 else
00811 {
00812 currVIdx = (*(hi.first)).second;
00813 }
00814 }
00815 else if (vnfo.fV < eps)
00816 {
00817 std::pair<EdgeMap_i, bool> mi = edges.insert(std::make_pair(vmin[1], emptyMap));
00818 std::pair<UIntHMap_i, bool> hi = (*(mi.first)).second.insert(std::make_pair(vmax[1], emptyIsects));
00819 bool found = false;
00820 for (unsigned int s=0; s<(*(hi.first)).second.n; ++s)
00821 {
00822 if (vClipped[i] == (*(hi.first)).second.isects[s].p)
00823 {
00824 found = true;
00825 vnfo.idx = (unsigned int)(-1);
00826 currVIdx = (*(hi.first)).second.isects[s].idx;
00827 break;
00828 }
00829 }
00830 if (!found)
00831 {
00832 (*(hi.first)).second.isects[(*(hi.first)).second.n].p = vClipped[i];
00833 (*(hi.first)).second.isects[(*(hi.first)).second.n].idx = vIdx;
00834 (*(hi.first)).second.n++;
00835
00836 vnfo.idx = (unsigned int)(-1);
00837 numVertices++;
00838 vInfos.push_back(vnfo);
00839 currVIdx = vIdx++;
00840 }
00841 }
00842 else if (vnfo.fU < eps)
00843 {
00844 std::pair<EdgeMap_i, bool> mi = edges.insert(std::make_pair(vmin[0], emptyMap));
00845 std::pair<UIntHMap_i, bool> hi = (*(mi.first)).second.insert(std::make_pair(vmax[0], emptyIsects));
00846 bool found = false;
00847 for (unsigned int s=0; s<(*(hi.first)).second.n; ++s)
00848 {
00849 if (vClipped[i] == (*(hi.first)).second.isects[s].p)
00850 {
00851 found = true;
00852 vnfo.idx = (unsigned int)(-1);
00853 currVIdx = (*(hi.first)).second.isects[s].idx;
00854 break;
00855 }
00856 }
00857 if (!found)
00858 {
00859 (*(hi.first)).second.isects[(*(hi.first)).second.n].p = vClipped[i];
00860 (*(hi.first)).second.isects[(*(hi.first)).second.n].idx = vIdx;
00861 (*(hi.first)).second.n++;
00862
00863 vnfo.idx = (unsigned int)(-1);
00864 numVertices++;
00865 vInfos.push_back(vnfo);
00866 currVIdx = vIdx++;
00867 }
00868 }
00869 else if ((vnfo.fU + vnfo.fV) >= ((ScalarType)(1.0 - 1e-5)))
00870 {
00871 std::pair<EdgeMap_i, bool> mi = edges.insert(std::make_pair(vmin[2], emptyMap));
00872 std::pair<UIntHMap_i, bool> hi = (*(mi.first)).second.insert(std::make_pair(vmax[2], emptyIsects));
00873 bool found = false;
00874 for (unsigned int s=0; s<(*(hi.first)).second.n; ++s)
00875 {
00876 if (vClipped[i] == (*(hi.first)).second.isects[s].p)
00877 {
00878 found = true;
00879 vnfo.idx = (unsigned int)(-1);
00880 currVIdx = (*(hi.first)).second.isects[s].idx;
00881 break;
00882 }
00883 }
00884 if (!found)
00885 {
00886 (*(hi.first)).second.isects[(*(hi.first)).second.n].p = vClipped[i];
00887 (*(hi.first)).second.isects[(*(hi.first)).second.n].idx = vIdx;
00888 (*(hi.first)).second.n++;
00889
00890 vnfo.idx = (unsigned int)(-1);
00891 numVertices++;
00892 vInfos.push_back(vnfo);
00893 currVIdx = vIdx++;
00894 }
00895 }
00896 else
00897 {
00898 vnfo.idx = (unsigned int)(-1);
00899 numVertices++;
00900 vInfos.push_back(vnfo);
00901 currVIdx = vIdx++;
00902 }
00903
00904 if (i == 0)
00905 {
00906 firstV = currVIdx;
00907 }
00908
00909 if (i > 1)
00910 {
00911 tnfo.idx = tIdx++;
00912 tnfo.v[0] = firstV;
00913 tnfo.v[1] = lastV;
00914 tnfo.v[2] = currVIdx;
00915
00916 tInfos.push_back(tnfo);
00917 }
00918
00919 lastV = currVIdx;
00920 }
00921 }
00922 }
00923
00924 if (tInfos.empty())
00925 {
00926 return;
00927 }
00928
00929 const unsigned int vSize = (unsigned int)(m.vn);
00930 const unsigned int tSize = (unsigned int)(m.fn);
00931
00932 typedef Allocator<TriMeshType> TriMeshAllocatorType;
00933
00934 TriMeshAllocatorType::AddVertices(r, (int)(vInfos.size()));
00935 TriMeshAllocatorType::AddFaces(r, (int)(tInfos.size()));
00936
00937 for (size_t i=0; i<vInfos.size(); ++i)
00938 {
00939 if (vInfos[i].idx != ((unsigned int)(-1)))
00940 {
00941 r.vert[i] = m.vert[vInfos[i].idx];
00942 }
00943 else
00944 {
00945 const unsigned int tref = vInfos[i].tref;
00946 vInterp(*(m.face[tref].V(0)), *(m.face[tref].V(1)), *(m.face[tref].V(2)), vInfos[i].fV, vInfos[i].fU, r.vert[i]);
00947 }
00948 }
00949
00950 for (size_t i=0; i<tInfos.size(); ++i)
00951 {
00952 r.face[i].V(0) = &(r.vert[tInfos[i].v[0]]);
00953 r.face[i].V(1) = &(r.vert[tInfos[i].v[1]]);
00954 r.face[i].V(2) = &(r.vert[tInfos[i].v[2]]);
00955 }
00956 }
00957
00958 protected:
00959
00960 static inline unsigned int BoxClipCode(const ScalarType * offsets, const CoordType & p)
00961 {
00962
00963 const ScalarType eps = (ScalarType)(0);
00964 unsigned int code = 0;
00965
00966 code |= ((( p[0] - offsets[0]) < eps) ? (1 << 0) : (0));
00967 code |= (((-p[0] - offsets[1]) < eps) ? (1 << 1) : (0));
00968 code |= ((( p[1] - offsets[2]) < eps) ? (1 << 2) : (0));
00969 code |= (((-p[1] - offsets[3]) < eps) ? (1 << 3) : (0));
00970 code |= ((( p[2] - offsets[4]) < eps) ? (1 << 4) : (0));
00971 code |= (((-p[2] - offsets[5]) < eps) ? (1 << 5) : (0));
00972
00973 return (code);
00974 }
00975
00976 static inline unsigned int InRegion(int mode, const ScalarType & value, const CoordType & p_in)
00977 {
00978
00979 const ScalarType eps = (ScalarType)(0);
00980 unsigned int flag = 0;
00981
00982 switch(mode)
00983 {
00984 case 0:
00985 flag = p_in[0] + eps < value;
00986 break;
00987 case 1:
00988 flag = p_in[0] > value + eps;
00989 break;
00990 case 2:
00991 flag = p_in[1] + eps < value;
00992 break;
00993 case 3:
00994 flag = p_in[1] > value + eps;
00995 break;
00996 case 4:
00997 flag = p_in[2] + eps < value;
00998 break;
00999 case 5:
01000 flag = p_in[2] > value + eps;
01001 break;
01002 default:
01003 break;
01004 }
01005
01006 return (flag);
01007 }
01008
01009 static inline void CrossPoint(int mode, const ScalarType & value, const CoordType & SP, const CoordType & PP, CoordType & p_out)
01010 {
01011 switch(mode)
01012 {
01013 case 0:
01014 case 1:
01015 p_out[0] = value;
01016 if ((PP[0] - SP[0]) == ((ScalarType)(0)))
01017 {
01018 p_out[1] = PP[1];
01019 p_out[2] = PP[2];
01020 }
01021 else
01022 {
01023 p_out[1] = SP[1] + (value - SP[0]) * (PP[1] - SP[1]) / (PP[0] - SP[0]);
01024 p_out[2] = SP[2] + (value - SP[0]) * (PP[2] - SP[2]) / (PP[0] - SP[0]);
01025 }
01026 break;
01027 case 2:
01028 case 3:
01029 p_out[1] = value;
01030 if ((PP[1] - SP[1]) == ((ScalarType)(0)))
01031 {
01032 p_out[0] = PP[0];
01033 p_out[2] = PP[2];
01034 }
01035 else
01036 {
01037 p_out[0] = SP[0] + (value - SP[1]) * (PP[0] - SP[0]) / (PP[1] - SP[1]);
01038 p_out[2] = SP[2] + (value - SP[1]) * (PP[2] - SP[2]) / (PP[1] - SP[1]);
01039 }
01040 break;
01041 case 4:
01042 case 5:
01043 p_out[2] = value;
01044 if ((PP[2] - SP[2]) == ((ScalarType)(0)))
01045 {
01046 p_out[0] = PP[0];
01047 p_out[1] = PP[1];
01048 }
01049 else
01050 {
01051 p_out[0] = SP[0] + (value - SP[2]) * (PP[0] - SP[0]) / (PP[2] - SP[2]);
01052 p_out[1] = SP[1] + (value - SP[2]) * (PP[1] - SP[1]) / (PP[2] - SP[2]);
01053 }
01054 break;
01055 default:
01056 break;
01057 }
01058 }
01059
01060 static inline void ClipPolygonLine(int mode, const ScalarType & value, CoordType * P_in, unsigned int n_in, CoordType * P_out, unsigned int & n_out)
01061 {
01062 unsigned int ps;
01063 CoordType * SP;
01064 CoordType * PP;
01065
01066 n_out = 0;
01067 SP = &P_in[n_in-1];
01068
01069 if (ClassType::InRegion(mode, value, *SP))
01070 {
01071 ps = 0;
01072 }
01073 else
01074 {
01075 ps = 2;
01076 }
01077
01078 for(unsigned int i=0; i<n_in; ++i)
01079 {
01080 PP = &(P_in[i]);
01081 ps = (ps >> 1) | ((ClassType::InRegion(mode, value, *PP)) ? (0) : (2));
01082
01083 switch(ps)
01084 {
01085 case 0:
01086 break;
01087 case 1:
01088 ClassType::CrossPoint(mode, value, *SP, *PP, P_out[n_out]);
01089 n_out++;
01090 break;
01091 case 2:
01092 ClassType::CrossPoint(mode, value, *SP, *PP, P_out[n_out]);
01093 n_out++;
01094 P_out[n_out] = *PP;
01095 n_out++;
01096 break;
01097 case 3:
01098 P_out[n_out] = *PP;
01099 n_out++;
01100 break;
01101 default:
01102 break;
01103 }
01104
01105 SP = PP;
01106 }
01107 }
01108
01109 };
01110
01111 }
01112 }
01113
01114 #endif // __VCGLIB_TRI_CLIP
