OSGDCTPMesh.cpp

00001 /*---------------------------------------------------------------------------*\
00002  *                           OpenSG NURBS Library                            *
00003  *                                                                           *
00004  *                                                                           *
00005  * Copyright (C) 2001-2006 by the University of Bonn, Computer Graphics Group*
00006  *                                                                           *
00007  *                         http://cg.cs.uni-bonn.de/                         *
00008  *                                                                           *
00009  * contact: edhellon@cs.uni-bonn.de, guthe@cs.uni-bonn.de, rk@cs.uni-bonn.de *
00010  *                                                                           *
00011 \*---------------------------------------------------------------------------*/
00012 /*---------------------------------------------------------------------------*\
00013  *                                License                                    *
00014  *                                                                           *
00015  * This library is free software; you can redistribute it and/or modify it   *
00016  * under the terms of the GNU Library General Public License as published    *
00017  * by the Free Software Foundation, version 2.                               *
00018  *                                                                           *
00019  * This library is distributed in the hope that it will be useful, but       *
00020  * WITHOUT ANY WARRANTY; without even the implied warranty of                *
00021  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU         *
00022  * Library General Public License for more details.                          *
00023  *                                                                           *
00024  * You should have received a copy of the GNU Library General Public         *
00025  * License along with this library; if not, write to the Free Software       *
00026  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.                 *
00027  *                                                                           *
00028 \*---------------------------------------------------------------------------*/
00029 /*---------------------------------------------------------------------------*\
00030  *                                Changes                                    *
00031  *                                                                           *
00032  *                                                                           *
00033  *                                                                           *
00034  *                                                                           *
00035  *                                                                           *
00036  *                                                                           *
00037 \*---------------------------------------------------------------------------*/
00038 #ifdef WIN32
00039 #   pragma warning (disable : 985)
00040 #endif
00041 #include "OSGDCTPMesh.h"
00042
00043 OSG_USING_NAMESPACE
00044
00045 #ifdef _DEBUG
00046  #ifdef WIN32
00047   #undef THIS_FILE
00048 static char THIS_FILE[] = __FILE__;
00049  #endif
00050 #endif
00051 
00052 const char DCTPMesh::ff_const_1[] = "BEGINTRIANGLESOUP";
00053 const char DCTPMesh::ff_const_2[] = "BEGINQUADSOUP";
00054
00055 DCTPMesh::DCTPMesh()
00056 {
00057     vertex_count = 0;
00058     edge_count   = 0;
00059     face_count   = 0;
00060     invalid      = true;
00061 }
00062
00063 DCTPMesh::~DCTPMesh()
00064 {
00065     dctpvertexset::iterator vend = vertices.end();
00066 #ifdef OSG_NO_EDGE_SET
00067     dctpedgevector::iterator eend = edges.end();
00068 #else
00069     dctpedgeset::iterator eend = edges.end();
00070 #endif
00071     dctpfacevector::iterator fend = faces.end();
00072
00073     for(dctpvertexset::iterator i1 = vertices.begin(); i1 != vend; ++i1)
00074     {
00075         delete *i1;
00076     }
00077
00078 #ifdef OSG_NO_EDGE_SET
00079 
00080     for(dctpedgevector::iterator i2 = edges.begin(); i2 != eend; ++i2)
00081 #else
00082
00083     for(dctpedgeset::iterator i2 = edges.begin(); i2 != eend; ++i2)
00084 #endif
00085     {
00086         delete *i2;
00087     }
00088
00089     for(dctpfacevector::iterator i3 = faces.begin(); i3 != fend; ++i3)
00090     {
00091         delete *i3;
00092     }
00093 }
00094
00095 DCTPVertex *DCTPMesh::AddVertex(Vec3d v)
00096 {
00097     DCTPVertex *nv = new DCTPVertex;
00098     if(!nv)
00099         return nv;
00100     invalid    = false;
00101     nv->coords = v;
00102
00103     std::pair<dctpvertexset::iterator, bool> siv;
00104     siv = vertices.insert(nv);
00105     if(!siv.second)
00106     {
00107 //    std::cerr << "AddVertex: already in: " << v << std::endl;
00108         delete nv;
00109         nv = *(siv.first);
00110     }
00111     else
00112     {
00113 //    std::cerr << "AddVertex: adding vx.: " << v << std::endl;
00114         nv->id = vertex_count++;
00115     }
00116     return nv;
00117 }
00118
00119 #ifdef OSG_INTEGER_MESH
00120 int DCTPMesh::directEdge(vec3i& from, vec3i& into)
00121 {
00122 #else
00123 int DCTPMesh::directEdge(Vec3d& from, Vec3d& into)
00124 {
00125 #endif
00126     DCTPVertex *from_vp = new DCTPVertex;
00127     DCTPVertex *into_vp = new DCTPVertex;
00128     if(!from_vp || !into_vp)
00129     {
00130         std::cerr << "Not enuf memory!" << std::endl;
00131         return -2;
00132     }
00133     from_vp->coords = from;
00134     into_vp->coords = into;
00135
00136 //        std::cerr << "directEdge in... coords: " << from << " " << into  << std::endl;
00137     dctpvertexset::iterator v1,v2, vend = vertices.end(); v1 =
00138         vertices.find(from_vp); if(v1 == vend)
00139     {
00140         delete from_vp;
00141         delete into_vp;
00142         return -1;
00143     }
00144     v2 = vertices.find(into_vp);
00145     if(v2 == vend)
00146     {
00147         delete from_vp;
00148         delete into_vp;
00149         return -1;
00150     }
00151 //        std::cerr << "still directEdge..." << std::endl;
00152 //        std::cerr.precision( DCTP_PRECISION );
00153 //        std::cerr << "v1->coords: " << (*v1)->coords << " v2->coords: " << (*v2)->coords << std::endl;
00154     delete from_vp;
00155     delete into_vp;
00156     std::vector<DCTPEdge*>::iterator eend = (*v1)->edges.end();
00157
00158     for(std::vector<DCTPEdge*>::iterator i = (*v1)->edges.begin(); i != eend; ++i)
00159     {
00160         DCTPVertex *tv1, *tv2;
00161         (*i)->getVertices(tv1, tv2);
00162         if(DCTPVecIsEqual(tv1->coords, (*v1)->coords) &&
00163            DCTPVecIsEqual(tv2->coords, (*v2)->coords) )
00164         {
00165             ++(*i)->orientation;
00166             return 0;
00167         }
00168         if(DCTPVecIsEqual(tv1->coords, (*v2)->coords) &&
00169            DCTPVecIsEqual(tv2->coords, (*v1)->coords) )
00170         {
00171             --(*i)->orientation;
00172             return 0;
00173         }
00174     }
00175
00176     return -1;
00177 }
00178
00179 DCTPEdge *DCTPMesh::AddEdge(DCTPVertex *v1, DCTPVertex *v2, int orient)
00180 {
00181 #ifdef OSG_NO_EDGE_SET
00182     DCTPEdge          *pcl_edge;
00183     const unsigned int cui_edge_cnt = v1->edges.size();
00184     unsigned int       ui_edge;
00185     DCTPVertex        *pcl_ev1;
00186     DCTPVertex        *pcl_ev2;
00187
00188     for(ui_edge = 0; ui_edge < cui_edge_cnt; ++ui_edge)
00189     {
00190         pcl_edge = v1->edges[ui_edge];
00191         pcl_edge->getVertices(pcl_ev1, pcl_ev2);
00192         if( (v2 == pcl_ev1) || (v2 == pcl_ev2) )
00193         {
00194             return pcl_edge;
00195         }
00196     }
00197
00198     invalid  = false;
00199     pcl_edge = new DCTPEdge(v1, v2, orient);
00200 //  std::cerr << "4-" << pcl_edge << " " << v1 << " " << v2 << std::endl;
00201     v1->edges.push_back(pcl_edge);
00202     v2->edges.push_back(pcl_edge);
00203     edges.push_back(pcl_edge);
00204
00205     return pcl_edge;
00206 #else
00207     DCTPEdge *ne = new DCTPEdge(v1, v2, orient);
00208     if(!ne)
00209         return ne;
00210
00211     invalid = false;
00212     std::pair<dctpedgeset::iterator, bool> sie;
00213 //  bool newas = false;
00214 /*
00215   dctpedgeset::iterator ee = edges.end();
00216   for (dctpedgeset::iterator i = edges.begin(); i !=ee; ++i ) {
00217     DCTPVertex *tt1, *tt2;
00218     (*i)->getVertices( tt1, tt2 );
00219     std::cerr << "edgeid: " << (*i)->id << " v1: " << (void*) tt1 << " " << (void*) tt2
00220     << std::endl;
00221   }
00222 */
00223     sie = edges.insert(ne);
00224     if(!sie.second)
00225     {
00226         delete ne;
00227         return *(sie.first);
00228 //    ne = *(sie.first);
00229 //    newas = true;
00230     }
00231     else
00232     {
00233 //    DCTPVertex *zz1, *zz2;
00234 //    ne->getVertices( zz1, zz2 );
00235 //    std::cerr << "Inserting new edge: " << (void*) zz1 << " " << (void*) zz2;
00236 //    std::cerr << " with coords: " << v1->coords << " " << v2->coords << std::endl;
00237         ne->id = edge_count++;
00238 //  }
00239 //  if ( !newas ) {
00240         v1->edges.push_back(ne);
00241         v2->edges.push_back(ne);
00242     }
00243
00244     return ne;
00245 #endif
00246 }
00247
00248
00249 DCTPFace *DCTPMesh::AddFace(void)
00250 {
00251     DCTPFace *nf = new DCTPFace;
00252     if(!nf)
00253         return NULL;
00254     invalid = false;
00255     nf->id  = face_count++;
00256     faces.push_back(nf);
00257
00258     return nf;
00259 }
00260
00261 int DCTPMesh::AddTriangle(Vec3d v1, Vec3d v2, Vec3d v3, double norm)
00262 {
00263     DCTPVertex *nv1 = AddVertex(v1);
00264     DCTPVertex *nv2 = AddVertex(v2);
00265     DCTPVertex *nv3 = AddVertex(v3);
00266     if(!nv1 || !nv2 || !nv3)
00267         return -1;
00268
00269     DCTPEdge *ne1 = AddEdge(nv1, nv2, 0);
00270     DCTPEdge *ne2 = AddEdge(nv2, nv3, 0);
00271     DCTPEdge *ne3 = AddEdge(nv3, nv1, 0);
00272     if(!ne1 || !ne2 || !ne3)
00273         return -1;
00274
00275     DCTPFace *nf = AddFace();
00276     if(!nf)
00277         return -1;
00278
00279     invalid = false;
00280     //do this here, to be able to dump valid data in DCTPEdge::AddFace
00281 #ifdef OSG_UNION_TRI_QUAD
00282     nf->orig_face[0] = nv1;
00283     nf->orig_face[1] = nv2;
00284     nf->orig_face[2] = nv3;
00285     nf->orig_face[3] = NULL;
00286 #else
00287     nf->orig_triangle[0] = nv1;
00288     nf->orig_triangle[1] = nv2;
00289     nf->orig_triangle[2] = nv3;
00290     // FIXME: is it really necessary? Any other (better) way to distinguish
00291     // FIXME: between triangle and quad faces?
00292     nf->orig_quad[0] = NULL;
00293     nf->orig_quad[1] = NULL;
00294     nf->orig_quad[2] = NULL;
00295     nf->orig_quad[3] = NULL;
00296 #endif
00297     nf->norm = norm;
00298
00299     ne1->AddFace(nf);
00300     ne2->AddFace(nf);
00301     ne3->AddFace(nf);
00302
00303     nv1->faces.push_back(nf);
00304     nv2->faces.push_back(nf);
00305     nv3->faces.push_back(nf);
00306
00307     nf->vertices.push_back(nv1);
00308     nf->vertices.push_back(nv2);
00309     nf->vertices.push_back(nv3);
00310     nf->edges.push_back(ne1);
00311     nf->edges.push_back(ne2);
00312     nf->edges.push_back(ne3);
00313
00314     return 0;
00315 }
00316
00317 int DCTPMesh::AddQuadSide(DCTPVertex *l, DCTPVertex *r, DCTPVertex *m, DCTPFace *nf)
00318 {
00319     if(m)
00320     {
00321         DCTPEdge *ue1 = AddEdge(l, m, 0);
00322         DCTPEdge *ue2 = AddEdge(m, r, 0);
00323         if(!ue1 || !ue2)
00324             return -1;
00325         ue1->AddFace(nf);
00326         ue2->AddFace(nf);
00327         nf->edges.push_back(ue1);
00328         nf->edges.push_back(ue2);
00329         l->faces.push_back(nf);
00330         m->faces.push_back(nf);
00331         r->faces.push_back(nf);
00332     }
00333     else
00334     {
00335         DCTPEdge *ue = AddEdge(l, r, 0);
00336         if(!ue)
00337             return -1;
00338         ue->AddFace(nf);
00339         nf->edges.push_back(ue);
00340         l->faces.push_back(nf);
00341         r->faces.push_back(nf);
00342     }
00343
00344     return 0;
00345 }
00346
00347
00348 /*  (nv1) ul   bool[0]   ur (nv2)
00349  *         X-----+-----X
00350  *         |           |
00351  *         |           |
00352  * bool[3] +           + bool[1]
00353  *         |           |
00354  *         |           |
00355  *         X-----+-----X
00356  *       ll   bool[2]   lr  (nv3)
00357  *  (nv4)                  (nv4)
00358  *
00359  *
00360  *  Note that this function adds vertices in clockwise order, i.e.
00361  *  nv1, nv,2 nv3, nv4 if there are no middle vertices.
00362  *
00363  *  Note that z coordinates are truncated to 0. This is essentially
00364  *  a 2D function using only (x, y) coords
00365  */
00366 int DCTPMesh::AddQuadTreeLeaf(Vec3d ul, Vec3d lr, bool *sides, double norm)
00367 {
00368     Vec3d ur, ll;
00369     ur[0] = lr[0]; ur[1] = ul[1]; ur[2] = 0.0;
00370     ll[0] = ul[0]; ll[1] = lr[1]; ll[2] = 0.0;
00371
00372     DCTPVertex *nv1 = AddVertex(ul);
00373     DCTPVertex *nv2 = AddVertex(ur);
00374     DCTPVertex *nv3 = AddVertex(lr);
00375     DCTPVertex *nv4 = AddVertex(ll);
00376     if(!nv1 || !nv2 || !nv3 || !nv4)
00377         return -1;
00378
00379     DCTPFace *nf = AddFace();
00380     if(!nf)
00381         return -1;
00382
00383 #ifdef OSG_UNION_TRI_QUAD
00384     nf->orig_face[0] = nv1;
00385     nf->orig_face[1] = nv2;
00386     nf->orig_face[2] = nv3;
00387     nf->orig_face[3] = nv4;
00388 #else
00389     nf->orig_quad[0] = nv1;
00390     nf->orig_quad[1] = nv2;
00391     nf->orig_quad[2] = nv3;
00392     nf->orig_quad[3] = nv4;
00393     // FIXME: is it really necessary? Any other (better) way to distinguish
00394     // FIXME: between triangle and quad faces?
00395     nf->orig_triangle[0] = NULL;
00396     nf->orig_triangle[1] = NULL;
00397     nf->orig_triangle[2] = NULL;
00398 #endif
00399     nf->norm = norm;
00400
00401     if(sides[0])
00402     {
00403         Vec3d umv;
00404         umv[0] = (ur[0] + ul[0]) / 2.0;
00405         umv[1] = ur[1];
00406         umv[2] = 0.0;
00407         DCTPVertex *um = AddVertex(umv);
00408         if(!um)
00409             return -1;
00410         AddQuadSide(nv1, nv2, um, nf);
00411         nf->vertices.push_back(nv1); // we have to add these here because
00412         nf->vertices.push_back(um); // on subsequent sides we mustn't add
00413         nf->vertices.push_back(nv2); // some vertices in order to avoid duplications
00414     }
00415     else
00416     {
00417         AddQuadSide(nv1, nv2, NULL, nf);
00418         nf->vertices.push_back(nv1); // see comment above
00419         nf->vertices.push_back(nv2);
00420     }
00421     if(sides[1])
00422     {
00423         Vec3d rmv;
00424         rmv[0] = ur[0];
00425         rmv[1] = (ur[1] + lr[1]) / 2.0;
00426         rmv[2] = 0.0;
00427         DCTPVertex *rm = AddVertex(rmv);
00428         if(!rm)
00429             return -1;
00430         AddQuadSide(nv2, nv3, rm, nf);
00431         nf->vertices.push_back(rm); // we don't need to push nv2 !!!
00432         nf->vertices.push_back(nv3);
00433     }
00434     else
00435     {
00436         AddQuadSide(nv2, nv3, NULL, nf);
00437         nf->vertices.push_back(nv3); // see comment above
00438     }
00439     if(sides[2])
00440     {
00441         Vec3d lmv;
00442         lmv[0] = (lr[0] + ll[0]) / 2.0;
00443         lmv[1] = lr[1];
00444         lmv[2] = 0.0;
00445         DCTPVertex *lm = AddVertex(lmv);
00446         if(!lm)
00447             return -1;
00448         AddQuadSide(nv3, nv4, lm, nf);
00449         nf->vertices.push_back(lm); // we don't need to push nv3 !!!
00450         nf->vertices.push_back(nv4);
00451     }
00452     else
00453     {
00454         AddQuadSide(nv3, nv4, NULL, nf);
00455         nf->vertices.push_back(nv4); // see comment above
00456     }
00457     if(sides[3])
00458     {
00459         Vec3d lemv;
00460         lemv[0] = ll[0];
00461         lemv[1] = (ll[1] + ul[1]) / 2.0;
00462         lemv[2] = 0.0;
00463         DCTPVertex *lem = AddVertex(lemv);
00464         if(!lem)
00465             return -1;
00466         AddQuadSide(nv4, nv1, lem, nf);
00467         nf->vertices.push_back(lem); // we don't need to push nv4 or nv1 !!!
00468     }
00469     else
00470     {
00471         AddQuadSide(nv4, nv1, NULL, nf);
00472     }
00473     return 0;
00474 }
00475
00476 /*
00477  * Note: in the SubdivideQuad() function we assume that the quads
00478  * were added this way:
00479  *
00480  * v1 .----. v2
00481  *    |    |
00482  * v4 `----' v3
00483  *
00484  */
00485 DCTPFace* DCTPMesh::AddQuad(Vec3d v1, Vec3d v2, Vec3d v3, Vec3d v4, double norm)
00486 {
00487     DCTPVertex *nv1 = AddVertex(v1);
00488     DCTPVertex *nv2 = AddVertex(v2);
00489     DCTPVertex *nv3 = AddVertex(v3);
00490     DCTPVertex *nv4 = AddVertex(v4);
00491     if(!nv1 || !nv2 || !nv3 || !nv4)
00492     {
00493         return NULL;
00494     }
00495
00496     DCTPEdge *ne1 = AddEdge(nv1, nv2, 0);
00497     DCTPEdge *ne2 = AddEdge(nv2, nv3, 0);
00498     DCTPEdge *ne3 = AddEdge(nv3, nv4, 0);
00499     DCTPEdge *ne4 = AddEdge(nv4, nv1, 0);
00500     if(!ne1 || !ne2 || !ne3 || !ne4)
00501     {
00502         return NULL;
00503     }
00504
00505     DCTPFace *nf = AddFace();
00506     if(!nf)
00507     {
00508         return NULL;
00509     }
00510
00511     invalid = false;
00512 #ifdef OSG_UNION_TRI_QUAD
00513     nf->orig_face[0] = nv1;
00514     nf->orig_face[1] = nv2;
00515     nf->orig_face[2] = nv3;
00516     nf->orig_face[3] = nv4;
00517 #else
00518     nf->orig_quad[0] = nv1;
00519     nf->orig_quad[1] = nv2;
00520     nf->orig_quad[2] = nv3;
00521     nf->orig_quad[3] = nv4;
00522     // FIXME: is it really necessary? Any other (better) way to distinguish
00523     // FIXME: between triangle and quad faces?
00524     nf->orig_triangle[0] = NULL;
00525     nf->orig_triangle[1] = NULL;
00526     nf->orig_triangle[2] = NULL;
00527 #endif
00528 
00529     ne1->AddFace(nf);
00530     ne2->AddFace(nf);
00531     ne3->AddFace(nf);
00532     ne4->AddFace(nf);
00533
00534     nv1->faces.push_back(nf);
00535     nv2->faces.push_back(nf);
00536     nv3->faces.push_back(nf);
00537     nv4->faces.push_back(nf);
00538
00539     nf->vertices.resize(4);
00540     nf->vertices[0] = nv1;
00541     nf->vertices[1] = nv2;
00542     nf->vertices[2] = nv3;
00543     nf->vertices[3] = nv4;
00544     nf->edges.resize(4);
00545     nf->edges[0] = ne1;
00546     nf->edges[1] = ne2;
00547     nf->edges[2] = ne3;
00548     nf->edges[3] = ne4;
00549     nf->norm     = norm;
00550
00551     return nf;
00552 }
00553
00554
00555 bool DCTPMesh::isInvalid(void)
00556 {
00557     return invalid;
00558 }
00559
00560 DCTPVertex * DCTPMesh::SplitEdge(DCTPEdge *edge, double t)
00561 {
00562 /*  if ( t < 0.0 || t > 1.0 )
00563   {
00564       std::cerr << "out of range" << std::endl;
00565       return NULL;
00566   }*/
00567     DCTPVertex *v1, *v2;
00568     edge->getVertices(v1, v2);
00569 //  if ( t < DCTP_EPS ) return v1;
00570 //  if ( t > 1 - DCTP_EPS ) return v2;
00571
00572 //  std::cerr << "split: " << v1->coords << " - " << v2->coords << ": " << t << std::endl;
00573
00574     DCTPVertex *nv = new DCTPVertex;
00575
00576     if(!nv)
00577     {
00578         std::cerr << "DCTPMesh::SplitEdge: Out of memory... " << std::endl;
00579         return NULL;
00580     }
00581
00582     nv->coords = v1->coords + (v2->coords - v1->coords) * t;
00583
00584     // add new vertex
00585     std::pair<dctpvertexset::iterator, bool> siv;
00586     siv = vertices.insert(nv);
00587     if(!siv.second)
00588     {
00589         // we already had this vertex in the mesh. Either the mesh is
00590         // corrupted/degenerate, or we've already applied this exact
00591         // SplitEdge operator.
00592         // or the splitvertex is very close to the ends of the edge... ;)
00593         delete nv;
00594         nv = *(siv.first);
00595         if(nv->edges.size() > 0)
00596         {
00597             std::cerr << "DCTPMesh::SplitEdge: error: inserting already existing splitvertex with edges..." << std::endl;
00598 //        std::cerr << "DCTPMesh::SplitEdge: error: numofedges: " << nv->edges.size()
00599 //                << std::endl;
00600 //        std::cerr << "DCTPMesh::SplitEdge: error: point location: " << nv->coords
00601 //                <<std::endl;
00602         }
00603         return nv;
00604     }
00605     else
00606     {
00607         nv->id = vertex_count++;
00608     }
00609
00610     // modify old (original) edge to (v1, nv)
00611 #ifdef OSG_NO_EDGE_SET
00612     edge->setVertices(v1, nv);
00613 //  std::cerr << "old: " << v1->coords << " - " << nv->coords << std::endl;
00614 #else
00615     // for this we have to erase the edge from the set
00616     // modify its vertices and insert it again.
00617     // NOTE: the _pointer_ itself does not change, only its iterator
00618     dctpedgeset::iterator edgeit = edges.find(edge);
00619     if(edgeit == edges.end() )
00620     {
00621         std::cerr << "splitedge: edge not found" << std::endl;
00622         exit(-1);
00623     }
00624     edges.erase(edgeit);
00625     edge->setVertices(v1, nv);
00626     std::pair<dctpedgeset::iterator, bool> sie1;
00627     sie1 = edges.insert(edge);
00628     if(!sie1.second)
00629     {
00630         std::cerr << "DCTPMesh::SplitEdge: error: reinserting already existing splitedge (this shouldn't happen)" << std::endl;
00631         return NULL;
00632     }
00633 #endif
00634 
00635     // add original edge to nv
00636 //  std::cerr << "1-" << edge << " " << nv << std::endl;
00637     nv->edges.push_back(edge);
00638
00639     // add original edge's faces to nv
00640     nv->faces.insert(nv->faces.end(), edge->faces.begin(), edge->faces.end() );
00643
00644     // create new edge between ( nv, v2 )
00645 #ifdef OSG_NO_EDGE_SET
00646     DCTPEdge *ne = AddEdge(nv, v2, edge->orientation);
00647     v2->edges.pop_back(); // remove edge from old vertex (is added later...)
00648 //  std::cerr << "new: " << nv->coords << " - " << v2->coords << std::endl;
00649 #else
00650     DCTPEdge *ne = new DCTPEdge(nv, v2, edge->orientation);
00651     if(!ne)
00652     {
00653         std::cerr << "DCTPMesh::SplitEdge: Out of memory... " << std::endl;
00654         return NULL;
00655     }
00656     ne->id = edge_count++;
00657
00658     std::pair<dctpedgeset::iterator, bool> sie;
00659     sie = edges.insert(ne);
00660     if(!sie.second)
00661     {
00662         delete ne;
00663         ne = *(sie.first);
00664         std::cerr << "DCTPMesh::SplitEdge: error: inserting already existing splitedge (this shouldn't happen)" << std::endl;
00665         return NULL;
00666     }
00667
00668     // add new edge to nv
00669     nv->edges.push_back(ne);
00670 #endif
00671 
00672     // add original edge's faces to the new edge
00673     ne->faces.insert(ne->faces.end(), edge->faces.begin(), edge->faces.end() );
00676
00677     // change v2's `edge' edge to `ne'
00678     std::vector<DCTPEdge*>::iterator v2ee = v2->edges.end();
00679     std::vector<DCTPEdge*>::iterator i;
00680
00681     for(i = v2->edges.begin(); i != v2ee; ++i)
00682         if(*i == edge)
00683             break;
00684
00685     if(i == v2ee)
00686     {
00687         std::cerr << " DCTPMesh::SplitEdge: error: couldn't find original edge in v2 " << std::endl;
00688         return NULL;
00689     }
00690     *i = ne;
00691
00692     // store the new vertex and the new edge for all incident facez0rz
00693     dctpfacevector::iterator fe = edge->faces.end();
00694
00695     for(dctpfacevector::iterator f = edge->faces.begin(); f != fe; ++f)
00696     {
00697         (*f)->vertices.push_back(nv);
00698         (*f)->edges.push_back(ne);
00699     }
00700
00701 /*
00702   if ( edge->f1 ) {
00703     edge->f1->vertices.push_back( nv );
00704     edge->f1->edges.push_back( ne );
00705   }
00706   if ( edge->f2 ) {
00707     edge->f2->vertices.push_back( nv );
00708     edge->f2->edges.push_back( ne );
00709   }
00710 */
00711
00712     //propagate `edgeinfo' to the new edge
00713     ne->edgeinfo = edge->edgeinfo;
00714
00715     return nv;
00716 }
00717
00718 double DCTPMesh::computeEdgePointDst(DCTPEdge *edg, Vec3d& pnt)
00719 {
00720     DCTPVertex *pp0,*pp1;
00721     Vec3d       p0, p1, pd;
00722     edg->getVertices(pp0, pp1);
00723     p0 = pp0->coords; p1 = pp1->coords;
00724     Vec3d  v  = p1 - p0;
00725     Vec3d  w  = pnt - p0;
00726     double c1 = v[0] * w[0] + v[1] * w[1] + v[2] * w[2];
00727     if(c1 <= 0)
00728     {
00729         pd = p0;
00730         Vec3d dist = pnt - p0;
00731         return sqrt(dist.squareLength() );
00732     }
00733     double c2 = v.squareLength();
00734     if(c2 <= c1)
00735     {
00736         pd = p1;
00737         Vec3d dist = pnt - p1;
00738         return sqrt(dist.squareLength() );
00739     }
00740     double b = c1 / c2;
00741     pd = v * b;
00742     pd = pd + p0;
00743     Vec3d dist = pnt - pd;
00744     return sqrt(dist.squareLength() );
00745 }
00746
00747 DCTPVertex* DCTPMesh::SplitEdge(DCTPEdge *edge, const Vec3d& p)
00748 {
00749
00750     DCTPVertex *v1, *v2;
00751     edge->getVertices(v1, v2);
00752 #ifdef OSG_INTEGER_MESH
00753     vec3i &p1 = v1->coords;
00754     vec3i &p2 = v2->coords;
00755 #else
00756     Vec3d &p1 = v1->coords;
00757     Vec3d &p2 = v2->coords;
00758 #endif
00759     if(DCTPVecIsEqual(p, p1) )
00760         return v1;
00761     if(DCTPVecIsEqual(p, p2) )
00762         return v2;
00763
00764     Vec3d  quickhack = p;
00765     double dist      = computeEdgePointDst(edge, quickhack);
00766 // DEBUG
00767 //    std::cerr << "SplitEdge, checkpoint I. distance = " << dist << std::endl;
00768 #ifdef OSG_INTEGER_MESH
00769     if(dist > 0.999)
00770 #else
00771     if(dist > 1e-9)
00772 #endif
00773     {
00774 #ifdef _DEBUG
00775 //  std::cerr << "DCTPMesh::SplitEdge, dist too big " << dist << std::endl;
00776 #endif
00777         return NULL;
00778     }
00779 // DEBUG
00780 //    std::cerr << "SplitEdge, checkpoint II.\n";
00781     Vec3d  lng_vec1 = p1 - p2;
00782     double lng1     = sqrt(lng_vec1.squareLength() );
00783     Vec3d  lng_vec2 = p - p1;
00784     double lng2     = sqrt(lng_vec2.squareLength() );
00785     double par      = lng2 / lng1;
00786     return SplitEdge(edge, par);
00787 }
00788
00789 /*
00790  * MoveVertex: move a vertex in 3D space.
00791  * This must be a separate function, since the vertices are
00792  * stored in a set, and the key is their position in 3D space,
00793  * so the vertex must be taken out of the set and inserted back
00794  * after it was moved.
00795  * The pointer to the vertex does not change, only its iterator.
00796  * Returns zero on success, and a negative value on failure.
00797  */
00798 int DCTPMesh::MoveVertex(DCTPVertex *vert, Vec3d &newpos)
00799 {
00800     if(DCTPVecIsEqual(vert->coords, newpos) )
00801         return 0;
00802     dctpvertexset::iterator vi = vertices.find(vert);
00803     if(vi == vertices.end() )
00804         return -1;
00805
00806     vertices.erase(vi);
00807     vert->coords = newpos;
00808     std::pair<dctpvertexset::iterator, bool> vinsert;
00809     vinsert = vertices.insert(vert);
00810     if(!vinsert.second)
00811     {
00812         std::cerr << "DCTPMesh::MoveVertex: error: reinserting already existing vertex (this shouldn't happen) " <<
00813         newpos[0] << " " << newpos[1] << " " << newpos[2] << std::endl;
00814         return -2;
00815     }
00816     return 0;
00817 }
00818
00819 #ifndef OSG_INTEGER_MESH
00820 /*
00821  * SplitFace: split a face using a sequence of predefined
00822  * points. The points must all lie on the edge, plus
00823  * be ordered. The result vector contains pointers to the newly inserted
00824  * vertices, so that the following holds:
00825  *
00826  * res[ i ]->coords = points[ i ].
00827  */
00828 int DCTPMesh::SplitFace(DCTPEdge *edge, DCTPVec3dvector &points, dctpvertexvector &res)
00829 {
00830     DCTPVertex *v1, *v2;
00831     DCTPVertex *v;
00832     res.clear();
00833     edge->getVertices(v1, v2);
00834     Vec3d &lp = points[points.size() - 1];
00835     Vec3d &fp = points[0];
00836
00837     if(DCTPVecIsEqual(lp, fp) )    // just one point
00838     {
00839         DCTPVertex *nv = SplitFace(edge, lp);
00840         if(!nv)
00841             return -1;
00842         res.push_back(nv);
00843         return 0;
00844     }
00845     if( (v1->coords - lp).squareLength() < (v1->coords - fp).squareLength() )
00846         v = v1;
00847     else
00848         v = v2;
00849     // v is the vertex closer to lp.
00850     DCTPVec3dvector::size_type k = points.size();
00851
00852     for(DCTPVec3dvector::size_type i = 0; i < k; ++i)
00853     {
00854         DCTPVertex *nv = SplitFace(edge, points[i]);
00855         if(!nv)
00856             return -1;
00857         res.push_back(nv);
00858         edge = findEdge(nv, v);
00859     } //for
00860
00861     return 0;
00862 }
00863
00864 /*
00865  * Split a face, by splitting an edge.
00866  * This possibly has an effect on all faces that are incident on the edge.
00867  * Presupposes that all affected faces are triangles.
00868  *
00869  */
00870 DCTPVertex *DCTPMesh::SplitFace(DCTPEdge *edge, const Vec3d& p)
00871 {
00872     // First we have to do an edgesplit, on the edge.
00873     DCTPVertex *v1, *v2;
00874     edge->getVertices(v1, v2);
00875     if(DCTPVecIsEqual(p, v1->coords) )
00876         return v1;
00877     if(DCTPVecIsEqual(p, v2->coords) )
00878         return v2;
00879
00880     DCTPVertex *nv = SplitEdge(edge, p);
00881     if(!nv)
00882         return NULL;
00883
00884     dctpfacevector::iterator fe = edge->faces.end();
00885
00886     // actually split all the faces belonging to the edge
00887     for(dctpfacevector::iterator i = edge->faces.begin(); i != fe; ++i)
00888         SplitOneFace(*i, edge, nv);
00889
00890     return nv;
00891 }
00892
00893 /*
00894  * Finish splitting up a face, do the necessary "bookkeeping".
00895  *
00896  */
00897 void DCTPMesh::SplitOneFace(DCTPFace *f, DCTPEdge *edge, DCTPVertex *nv)
00898 {
00899     DCTPVertex  *left, *right, *third;
00900     DCTPEdge    *e1, *e2, *e3;
00901     unsigned int i;
00902
00903     edge->getVertices(left, right);
00904     if(left == nv)
00905     {
00906         left = right; right = NULL;
00907     }
00908     if(right == nv)
00909         right = NULL;
00910
00911 //DEBUGCHECK
00912     if(right)
00913         std::cerr << "DCTPMesh::SplitOneFace: something strange..." << std::endl;
00914
00915     //we must find the edge which is:
00916     // - edge over `f'
00917     // - has `nv' as one of its vertices
00918     // - not equal to `edge'
00919     e3 = NULL;
00920     std::vector<DCTPEdge*>::iterator fee = f->edges.end();
00921
00922     for(std::vector<DCTPEdge*>::iterator e = f->edges.begin(); e != fee; ++e)
00923     {
00924         DCTPVertex *tv1, *tv2;
00925         if(*e != edge)
00926         {
00927             (*e)->getVertices(tv1, tv2);
00928             if(tv1 == nv || tv2 == nv)
00929             {
00930                 e3 = *e;
00931                 break;
00932             } //if
00933         } //if
00934     } //for
00935
00936     if(!e3)
00937         std::cerr << "DCTPMesh::SplitOneFace: something strange #1.5..." << std::endl;
00938     e3->getVertices(right, third);
00939     if(right == nv)
00940     {
00941         right = third; third = NULL;
00942     }
00943     if(third == nv)
00944         third = NULL;
00945     if(third)
00946         std::cerr << "DCTPMesh::SplitOneFace: something strange #2..." << std::endl;
00947
00948     for(i = 0; i < 3; ++i)
00949 #ifdef OSG_UNION_TRI_QUAD
00950
00951
00952
00953         if(f->orig_face[i] != left && f->orig_face[i] != right)
00954         {
00955             third = f->orig_face[i]; break;
00956         }
00957
00958 #else
00959 
00960
00961
00962         if(f->orig_triangle[i] != left && f->orig_triangle[i] != right)
00963         {
00964             third = f->orig_triangle[i]; break;
00965         }
00966 #endif
00967     if(!third)
00968         std::cerr << "DCTPMesh::SplitOneFace: something strange #3..." << std::endl;
00969
00970     e1 = findEdge(left, third);
00971     if(!e1)
00972         std::cerr << "DCTPMesh::SplitOneFace: something strange #4..." << std::endl;
00973     e2 = findEdge(third, right);
00974     if(!e2)
00975         std::cerr << "DCTPMesh::SplitOneFace: something strange #5..." << std::endl;
00976
00977     //create new unoriented edge between 'third' and 'nv'
00978     DCTPEdge *ne = AddEdge(third, nv, 0);
00979     //modify `f' such as:
00980     //change e2 to ne
00981     e2->RemoveFace(f);
00982     ne->AddFace(f);
00983     f->RemoveEdge(e2);
00984     f->AddEdge(ne);
00985
00986     //replace `right' with `nv'
00987     for(i = 0; i < 3; ++i)
00988 #ifdef OSG_UNION_TRI_QUAD
00989
00990
00991
00992         if(f->orig_face[i] == right)
00993         {
00994             f->orig_face[i] = nv;
00995         }
00996
00997 #else
00998 
00999
01000
01001         if(f->orig_triangle[i] == right)
01002         {
01003             f->orig_triangle[i] = nv;
01004         }
01005 #endif
01006     f->ReplaceVertex(right, nv);
01007     //remove last vertex of `f', which must be `nv'
01008     if(f->vertices[f->vertices.size() - 1] != nv)
01009         std::cerr << "DCTPMesh::SplitOneFace: something strange #6..." << std::endl;
01010     f->vertices.resize(f->vertices.size() - 1);
01011
01012     //remove `f' from right
01013     right->RemoveFace(f);
01014
01015     //remove `e3' from `f', since SplitEdge added it
01016     f->RemoveEdge(e3);
01017     //remove `f' from `e3', since SplitEdge added it
01018     e3->RemoveFace(f);
01019
01020     //OK, we're done with `f' so let's create the new face and fill it in!
01021     DCTPFace *nf = AddFace();
01022     //add the new edges
01023     nf->AddEdge(ne);
01024     nf->AddEdge(e2);
01025     nf->AddEdge(e3);
01026
01027     if(f->vertices.size() != 3)
01028         std::cerr << "DCTPMesh::SplitOneFace: something strange #7..." << std::endl;
01029
01030     //add the vertices _in order_
01031     //FIXME: it could be more efficient if we create `nf' before, and copy
01032     //everything from `f', and replace `left' with `nv'
01033     for(i = 0; i< 3; ++i)
01034     {
01035 #ifdef OSG_UNION_TRI_QUAD
01036         if(f->orig_face[i] == left)
01037             nf->orig_face[i] = nv;
01038         else if(f->orig_face[i] == nv)
01039             nf->orig_face[i] = right;
01040         else
01041             nf->orig_face[i] = f->orig_face[i];
01042 #else
01043         if(f->orig_triangle[i] == left)
01044             nf->orig_triangle[i] = nv;
01045         else if(f->orig_triangle[i] == nv)
01046             nf->orig_triangle[i] = right;
01047         else
01048             nf->orig_triangle[i] = f->orig_triangle[i];
01049 #endif
01050 
01051         if(f->vertices[i] == left)
01052             nf->vertices.push_back(nv);
01053         else if(f->vertices[i] == nv)
01054             nf->vertices.push_back(right);
01055         else
01056             nf->vertices.push_back(f->vertices[i]);
01057     } //for
01058
01059     //add `nf' to its vertices
01060     nv->AddFace(nf);
01061     third->AddFace(nf);
01062     right->AddFace(nf);
01063
01064     //and to its edges
01065     ne->AddFace(nf);
01066     e2->AddFace(nf);
01067     e3->AddFace(nf);
01068
01069 } //end SplitOneFace
01070 #endif
01071 
01072
01073 /*
01074  *  Subdivide the current (quad) face into four smaller faces.
01075  *  Change the values of the current face to be the upper left
01076  *  quarter, and generate new faces, edges, etc. for the other
01077  *  three quarters.
01078  */
01079 int DCTPMesh::SubdivideQuad(DCTPFace *f)
01080 {
01081
01082     Vec3d       n, s, e, w;
01083     DCTPVertex *np = NULL, *sp = NULL, *ep = NULL, *wp = NULL;
01084
01085 #ifdef OSG_UNION_TRI_QUAD
01086     n = (f->orig_face[0]->coords + f->orig_face[1]->coords) * 0.5;
01087     s = (f->orig_face[2]->coords + f->orig_face[3]->coords) * 0.5;
01088     e = (f->orig_face[1]->coords + f->orig_face[2]->coords) * 0.5;
01089     w = (f->orig_face[3]->coords + f->orig_face[0]->coords) * 0.5;
01090 #else
01091     n = (f->orig_quad[0]->coords + f->orig_quad[1]->coords) * 0.5;
01092     s = (f->orig_quad[2]->coords + f->orig_quad[3]->coords) * 0.5;
01093     e = (f->orig_quad[1]->coords + f->orig_quad[2]->coords) * 0.5;
01094     w = (f->orig_quad[3]->coords + f->orig_quad[0]->coords) * 0.5;
01095 #endif
01096 
01097     // iterate through the vertices and do splitedges if necessary
01098     std::vector<DCTPVertex*>::iterator ve = f->vertices.end();
01099     std::vector<DCTPVertex*>::iterator i;
01100
01101     for(i = f->vertices.begin(); i != ve; ++i)
01102     {
01103         if(DCTPVecIsEqual( (*i)->coords, n) )
01104             np = *i;
01105         if(DCTPVecIsEqual( (*i)->coords, s) )
01106             sp = *i;
01107         if(DCTPVecIsEqual( (*i)->coords, e) )
01108             ep = *i;
01109         if(DCTPVecIsEqual( (*i)->coords, w) )
01110             wp = *i;
01111     }
01112
01113 #ifdef OSG_UNION_TRI_QUAD
01114     if(!np)
01115         np = SplitEdge(getEdgeFromFace(f, f->orig_face[0], f->orig_face[1]), 0.5);
01116     if(!sp)
01117         sp = SplitEdge(getEdgeFromFace(f, f->orig_face[2], f->orig_face[3]), 0.5);
01118     if(!ep)
01119         ep = SplitEdge(getEdgeFromFace(f, f->orig_face[1], f->orig_face[2]), 0.5);
01120     if(!wp)
01121         wp = SplitEdge(getEdgeFromFace(f, f->orig_face[3], f->orig_face[0]), 0.5);
01122 #else
01123     if(!np)
01124         np = SplitEdge(getEdgeFromFace(f, f->orig_quad[0], f->orig_quad[1]), 0.5);
01125     if(!sp)
01126         sp = SplitEdge(getEdgeFromFace(f, f->orig_quad[2], f->orig_quad[3]), 0.5);
01127     if(!ep)
01128         ep = SplitEdge(getEdgeFromFace(f, f->orig_quad[1], f->orig_quad[2]), 0.5);
01129     if(!wp)
01130         wp = SplitEdge(getEdgeFromFace(f, f->orig_quad[3], f->orig_quad[0]), 0.5);
01131 #endif
01132 
01133     //these removals must be done after the splitedge operators
01134     //go through the edges of the face, and remove this face
01135     //from each edge.
01136     std::vector<DCTPEdge*>::iterator ee = f->edges.end();
01137
01138     for(std::vector<DCTPEdge*>::iterator ed = f->edges.begin(); ed != ee; ++ed)
01139         (*ed)->RemoveFace(f);
01140
01141     //go through the vertices of the face, and remove this face
01142     //from each vertex.
01143     ve = f->vertices.end();
01144
01145     for(i = f->vertices.begin(); i != ve; ++i)
01146         (*i)->RemoveFace(f);
01147
01148
01149     buildNewFaces(f, np, sp, wp, ep);
01150     return 0;
01151 }
01152
01153 void DCTPMesh::buildNewFaces(DCTPFace *f, DCTPVertex *np, DCTPVertex *sp, DCTPVertex *wp, DCTPVertex *ep)
01154 {
01155     //set up middle point
01156     Vec3d        middle  = (np->coords + sp->coords) * 0.5;
01157     DCTPVertex * middlev = AddVertex(middle);
01158     //set up new edges to/from middlepoint
01159     // v1 .----. v2
01160     //    |    |
01161     // v4 `----' v3
01162     std::vector<DCTPVertex *> vertsides[8];
01163
01164     setupSides(f, vertsides, 0.5, 0.5);
01165     sortSides(f, vertsides);
01166     //clear original face's edges and vertices
01167     f->edges.clear();
01168     f->vertices.clear();
01169
01170     DCTPVertex * quad_save[4];
01171 #ifdef OSG_UNION_TRI_QUAD
01172     quad_save[0] = f->orig_face[0]; quad_save[1] = f->orig_face[1];
01173     quad_save[2] = f->orig_face[2]; quad_save[3] = f->orig_face[3];
01174 #else
01175     quad_save[0] = f->orig_quad[0]; quad_save[1] = f->orig_quad[1];
01176     quad_save[2] = f->orig_quad[2]; quad_save[3] = f->orig_quad[3];
01177 #endif
01178 
01179     //construct the vertices-vectors of the new faces
01180     std::vector<DCTPVertex *> vertsvec;
01181     //upper left
01182     vertsvec.push_back(wp);
01183     vertsvec.insert(vertsvec.end(), vertsides[7].begin(), vertsides[7].end() );
01184     vertsvec.push_back(quad_save[0]);
01185     vertsvec.insert(vertsvec.end(), vertsides[0].begin(), vertsides[0].end() );
01186     vertsvec.push_back(np);
01187     vertsvec.push_back(middlev);
01188     buildQuadFace(vertsvec, f);
01189 #ifdef OSG_UNION_TRI_QUAD
01190     f->orig_face[1] = np; f->orig_face[2] = middlev; f->orig_face[3] = wp;
01191 #else
01192     f->orig_quad[1]     = np; f->orig_quad[2] = middlev; f->orig_quad[3] = wp;
01193     f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
01194 #endif
01195     //upper right
01196     vertsvec.clear();
01197     vertsvec.push_back(np);
01198     vertsvec.insert(vertsvec.end(), vertsides[1].begin(), vertsides[1].end() );
01199     vertsvec.push_back(quad_save[1]);
01200     vertsvec.insert(vertsvec.end(), vertsides[2].begin(), vertsides[2].end() );
01201     vertsvec.push_back(ep);
01202     vertsvec.push_back(middlev);
01203 //  std::cerr <<"vertsvec size: " << vertsvec.size() << std::endl;
01204     f = buildQuadFace(vertsvec, NULL);
01205 #ifdef OSG_UNION_TRI_QUAD
01206     f->orig_face[0] = np; f->orig_face[1] = quad_save[1];
01207     f->orig_face[2] = ep; f->orig_face[3] = middlev;
01208 #else
01209     f->orig_quad[0]     = np; f->orig_quad[1] = quad_save[1];
01210     f->orig_quad[2]     = ep; f->orig_quad[3] = middlev;
01211     f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
01212 #endif
01213     //lower right
01214     vertsvec.clear();
01215     vertsvec.push_back(ep);
01216     vertsvec.insert(vertsvec.end(), vertsides[3].begin(), vertsides[3].end() );
01217     vertsvec.push_back(quad_save[2]);
01218     vertsvec.insert(vertsvec.end(), vertsides[4].begin(), vertsides[4].end() );
01219     vertsvec.push_back(sp);
01220     vertsvec.push_back(middlev);
01221     f = buildQuadFace(vertsvec, NULL);
01222 #ifdef OSG_UNION_TRI_QUAD
01223     f->orig_face[0] = middlev; f->orig_face[1] = ep;
01224     f->orig_face[2] = quad_save[2]; f->orig_face[3] = sp;
01225 #else
01226     f->orig_quad[0]     = middlev; f->orig_quad[1] = ep;
01227     f->orig_quad[2]     = quad_save[2]; f->orig_quad[3] = sp;
01228     f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
01229 #endif
01230     //lower left
01231     vertsvec.clear();
01232     vertsvec.push_back(sp);
01233     vertsvec.insert(vertsvec.end(), vertsides[5].begin(), vertsides[5].end() );
01234     vertsvec.push_back(quad_save[3]);
01235     vertsvec.insert(vertsvec.end(), vertsides[6].begin(), vertsides[6].end() );
01236     vertsvec.push_back(wp);
01237     vertsvec.push_back(middlev);
01238     f = buildQuadFace(vertsvec, NULL);
01239 #ifdef OSG_UNION_TRI_QUAD
01240     f->orig_face[0] = wp; f->orig_face[1] = middlev;
01241     f->orig_face[2] = sp; f->orig_face[3] = quad_save[3];
01242 #else
01243     f->orig_quad[0]     = wp; f->orig_quad[1] = middlev;
01244     f->orig_quad[2]     = sp; f->orig_quad[3] = quad_save[3];
01245     f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
01246 #endif
01247 }
01248
01249 /*
01250  *  Subdivide the current (quad) face into two smaller faces.
01251  *  Change the values of the current face to be the upper
01252  *  half, and generate new faces, edges, etc. for the other
01253  *  quad.
01254  */
01255 int DCTPMesh::SubdivideQuadNS(DCTPFace *f)
01256 {
01257
01258     Vec3d       e, w;
01259     DCTPVertex *ep = NULL, *wp = NULL;
01260
01261 #ifdef OSG_UNION_TRI_QUAD
01262     e = (f->orig_face[1]->coords + f->orig_face[2]->coords) * 0.5;
01263     w = (f->orig_face[3]->coords + f->orig_face[0]->coords) * 0.5;
01264 #else
01265     e = (f->orig_quad[1]->coords + f->orig_quad[2]->coords) * 0.5;
01266     w = (f->orig_quad[3]->coords + f->orig_quad[0]->coords) * 0.5;
01267 #endif
01268 
01269     // iterate through the vertices and do splitedges if necessary
01270     std::vector<DCTPVertex*>::iterator ve = f->vertices.end();
01271     std::vector<DCTPVertex*>::iterator i;
01272
01273     for(i = f->vertices.begin(); i != ve; ++i)
01274     {
01275         if(DCTPVecIsEqual( (*i)->coords, e) )
01276             ep = *i;
01277         if(DCTPVecIsEqual( (*i)->coords, w) )
01278             wp = *i;
01279     }
01280
01281 #ifdef OSG_UNION_TRI_QUAD
01282     if(!ep)
01283         ep = SplitEdge(getEdgeFromFace(f, f->orig_face[1], f->orig_face[2]), 0.5);
01284     if(!wp)
01285         wp = SplitEdge(getEdgeFromFace(f, f->orig_face[3], f->orig_face[0]), 0.5);
01286 #else
01287     if(!ep)
01288         ep = SplitEdge(getEdgeFromFace(f, f->orig_quad[1], f->orig_quad[2]), 0.5);
01289     if(!wp)
01290         wp = SplitEdge(getEdgeFromFace(f, f->orig_quad[3], f->orig_quad[0]), 0.5);
01291 #endif
01292 
01293     //these removals must be done after the splitedge operators
01294     //go through the edges of the face, and remove this face
01295     //from each edge.
01296     std::vector<DCTPEdge*>::iterator ee = f->edges.end();
01297
01298     for(std::vector<DCTPEdge*>::iterator ed = f->edges.begin(); ed != ee; ++ed)
01299         (*ed)->RemoveFace(f);
01300
01301     //go through the vertices of the face, and remove this face
01302     //from each vertex.
01303     ve = f->vertices.end();
01304
01305     for(i = f->vertices.begin(); i != ve; ++i)
01306         (*i)->RemoveFace(f);
01307
01308
01309     buildNewFacesNS(f, wp, ep);
01310     return 0;
01311 }
01312
01313 void DCTPMesh::buildNewFacesNS(DCTPFace *f, DCTPVertex *wp, DCTPVertex *ep)
01314 {
01315     //set up middle point
01316 #ifdef OSG_UNION_TRI_QUAD
01317     DCTPVertex *np = findVertex( (f->orig_face[0]->coords + f->orig_face[1]->coords) * 0.5);
01318     DCTPVertex *sp = findVertex( (f->orig_face[2]->coords + f->orig_face[3]->coords) * 0.5);
01319 #else
01320     DCTPVertex *np = findVertex( (f->orig_quad[0]->coords + f->orig_quad[1]->coords) * 0.5);
01321     DCTPVertex *sp = findVertex( (f->orig_quad[2]->coords + f->orig_quad[3]->coords) * 0.5);
01322 #endif
01323     //set up new edges
01324     // v1 .----. v2
01325     //    |    |
01326     // v4 `----' v3
01327     std::vector<DCTPVertex *> vertsides[8];
01328
01329     setupSides(f, vertsides, 0.5, 0.5);
01330     sortSides(f, vertsides);
01331     //clear original face's edges and vertices
01332     f->edges.clear();
01333     f->vertices.clear();
01334
01335     DCTPVertex * quad_save[4];
01336 #ifdef OSG_UNION_TRI_QUAD
01337     quad_save[0] = f->orig_face[0]; quad_save[1] = f->orig_face[1];
01338     quad_save[2] = f->orig_face[2]; quad_save[3] = f->orig_face[3];
01339 #else
01340     quad_save[0] = f->orig_quad[0]; quad_save[1] = f->orig_quad[1];
01341     quad_save[2] = f->orig_quad[2]; quad_save[3] = f->orig_quad[3];
01342 #endif
01343 
01344     //construct the vertices-vectors of the new faces
01345     std::vector<DCTPVertex *> vertsvec;
01346     //upper
01347     vertsvec.push_back(quad_save[0]);
01348     vertsvec.insert(vertsvec.end(), vertsides[0].begin(), vertsides[0].end() );
01349     if(np)
01350         vertsvec.push_back(np);
01351     vertsvec.insert(vertsvec.end(), vertsides[1].begin(), vertsides[1].end() );
01352     vertsvec.push_back(quad_save[1]);
01353     vertsvec.insert(vertsvec.end(), vertsides[2].begin(), vertsides[2].end() );
01354     vertsvec.push_back(ep);
01355     vertsvec.push_back(wp);
01356     vertsvec.insert(vertsvec.end(), vertsides[7].begin(), vertsides[7].end() );
01357     buildQuadFace(vertsvec, f);
01358 #ifdef OSG_UNION_TRI_QUAD
01359     f->orig_face[2] = ep; f->orig_face[3] = wp;
01360 #else
01361     f->orig_quad[2]     = ep; f->orig_quad[3] = wp;
01362     f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
01363 #endif
01364 /*  std::cerr << "NS: " << f->orig_quad[ 0 ]->coords << " ";
01365   std::cerr << f->orig_quad[ 1 ]->coords << " ";
01366   std::cerr << f->orig_quad[ 2 ]->coords << " ";
01367   std::cerr << f->orig_quad[ 3 ]->coords << std::endl;*/
01368 //lower
01369     vertsvec.clear();
01370     vertsvec.push_back(wp);
01371     vertsvec.push_back(ep);
01372     vertsvec.insert(vertsvec.end(), vertsides[3].begin(), vertsides[3].end() );
01373     vertsvec.push_back(quad_save[2]);
01374     vertsvec.insert(vertsvec.end(), vertsides[4].begin(), vertsides[4].end() );
01375     if(sp)
01376         vertsvec.push_back(sp);
01377     vertsvec.insert(vertsvec.end(), vertsides[5].begin(), vertsides[5].end() );
01378     vertsvec.push_back(quad_save[3]);
01379     vertsvec.insert(vertsvec.end(), vertsides[6].begin(), vertsides[6].end() );
01380     f = buildQuadFace(vertsvec, NULL);
01381 #ifdef OSG_UNION_TRI_QUAD
01382     f->orig_face[0] = wp; f->orig_face[1] = ep;
01383     f->orig_face[2] = quad_save[2]; f->orig_face[3] = quad_save[3];
01384 #else
01385     f->orig_quad[0]     = wp; f->orig_quad[1] = ep;
01386     f->orig_quad[2]     = quad_save[2]; f->orig_quad[3] = quad_save[3];
01387     f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
01388 #endif
01389 /*  std::cerr << f->orig_quad[ 0 ]->coords << " ";
01390   std::cerr << f->orig_quad[ 1 ]->coords << " ";
01391   std::cerr << f->orig_quad[ 2 ]->coords << " ";
01392   std::cerr << f->orig_quad[ 3 ]->coords << std::endl;*/
01393
01394 }
01395
01396 /*
01397  *  Subdivide the current (quad) face into two smaller faces.
01398  *  Change the values of the current face to be the left
01399  *  half, and generate new faces, edges, etc. for the other
01400  *  quad.
01401  */
01402 int DCTPMesh::SubdivideQuadEW(DCTPFace *f)
01403 {
01404
01405     Vec3d       n, s;
01406     DCTPVertex *np = NULL, *sp = NULL;
01407
01408 #ifdef OSG_UNION_TRI_QUAD
01409     n = (f->orig_face[0]->coords + f->orig_face[1]->coords) * 0.5;
01410     s = (f->orig_face[2]->coords + f->orig_face[3]->coords) * 0.5;
01411 #else
01412     n = (f->orig_quad[0]->coords + f->orig_quad[1]->coords) * 0.5;
01413     s = (f->orig_quad[2]->coords + f->orig_quad[3]->coords) * 0.5;
01414 #endif
01415 
01416     //iterate through the vertices and do splitedges if necessary
01417     std::vector<DCTPVertex*>::iterator ve = f->vertices.end();
01418     std::vector<DCTPVertex*>::iterator i;
01419
01420     for(i = f->vertices.begin(); i != ve; ++i)
01421     {
01422         if(DCTPVecIsEqual( (*i)->coords, n) )
01423             np = *i;
01424         if(DCTPVecIsEqual( (*i)->coords, s) )
01425             sp = *i;
01426     }
01427
01428 #ifdef OSG_UNION_TRI_QUAD
01429     if(!np)
01430         np = SplitEdge(getEdgeFromFace(f, f->orig_face[0], f->orig_face[1]), 0.5);
01431     if(!sp)
01432         sp = SplitEdge(getEdgeFromFace(f, f->orig_face[2], f->orig_face[3]), 0.5);
01433 #else
01434     if(!np)
01435         np = SplitEdge(getEdgeFromFace(f, f->orig_quad[0], f->orig_quad[1]), 0.5);
01436     if(!sp)
01437         sp = SplitEdge(getEdgeFromFace(f, f->orig_quad[2], f->orig_quad[3]), 0.5);
01438 #endif
01439 
01440     //these removals must be done after the splitedge operators
01441     //go through the edges of the face, and remove this face
01442     //from each edge.
01443     std::vector<DCTPEdge*>::iterator ee = f->edges.end();
01444
01445     for(std::vector<DCTPEdge*>::iterator ed = f->edges.begin(); ed != ee; ++ed)
01446         (*ed)->RemoveFace(f);
01447
01448     //go through the vertices of the face, and remove this face
01449     //from each vertex.
01450     ve = f->vertices.end();
01451
01452     for(i = f->vertices.begin(); i != ve; ++i)
01453         (*i)->RemoveFace(f);
01454
01455
01456     buildNewFacesEW(f, np, sp);
01457     return 0;
01458 }
01459
01460 void DCTPMesh::buildNewFacesEW(DCTPFace *f, DCTPVertex *np, DCTPVertex *sp)
01461 {
01462     //set up middle point
01463 #ifdef OSG_UNION_TRI_QUAD
01464     DCTPVertex *ep = findVertex( (f->orig_face[1]->coords + f->orig_face[2]->coords) * 0.5);
01465     DCTPVertex *wp = findVertex( (f->orig_face[0]->coords + f->orig_face[3]->coords) * 0.5);
01466 #else
01467     DCTPVertex *ep = findVertex( (f->orig_quad[1]->coords + f->orig_quad[2]->coords) * 0.5);
01468     DCTPVertex *wp = findVertex( (f->orig_quad[0]->coords + f->orig_quad[3]->coords) * 0.5);
01469 #endif
01470     //set up new edges
01471     // v1 .----. v2
01472     //    |    |
01473     // v4 `----' v3
01474     std::vector<DCTPVertex *> vertsides[8];
01475
01476     setupSides(f, vertsides, 0.5, 0.5);
01477     sortSides(f, vertsides);
01478     //clear original face's edges and vertices
01479     f->edges.clear();
01480     f->vertices.clear();
01481
01482     DCTPVertex * quad_save[4];
01483 #ifdef OSG_UNION_TRI_QUAD
01484     quad_save[0] = f->orig_face[0]; quad_save[1] = f->orig_face[1];
01485     quad_save[2] = f->orig_face[2]; quad_save[3] = f->orig_face[3];
01486 #else
01487     quad_save[0] = f->orig_quad[0]; quad_save[1] = f->orig_quad[1];
01488     quad_save[2] = f->orig_quad[2]; quad_save[3] = f->orig_quad[3];
01489 #endif
01490 
01491     //construct the vertices-vectors of the new faces
01492     std::vector<DCTPVertex *> vertsvec;
01493     //left
01494     vertsvec.push_back(quad_save[0]);
01495     vertsvec.insert(vertsvec.end(), vertsides[0].begin(), vertsides[0].end() );
01496     vertsvec.push_back(np);
01497     vertsvec.push_back(sp);
01498     vertsvec.insert(vertsvec.end(), vertsides[5].begin(), vertsides[5].end() );
01499     vertsvec.push_back(quad_save[3]);
01500     vertsvec.insert(vertsvec.end(), vertsides[6].begin(), vertsides[6].end() );
01501     if(wp)
01502         vertsvec.push_back(wp);
01503     vertsvec.insert(vertsvec.end(), vertsides[7].begin(), vertsides[7].end() );
01504     buildQuadFace(vertsvec, f);
01505 #ifdef OSG_UNION_TRI_QUAD
01506     f->orig_face[1] = np; f->orig_face[2] = sp;
01507 #else
01508     f->orig_quad[1]     = np; f->orig_quad[2] = sp;
01509     f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
01510 #endif
01511 /*  std::cerr << "EW: " << f->orig_face[ 0 ]->coords << " ";
01512   std::cerr << f->orig_face[ 0 ]->coords << " ";
01513   std::cerr << f->orig_face[ 1 ]->coords << " ";
01514   std::cerr << f->orig_face[ 2 ]->coords << " ";
01515   std::cerr << f->orig_face[ 3 ]->coords << std::endl;*/
01516 //right
01517     vertsvec.clear();
01518     vertsvec.push_back(np);
01519     vertsvec.insert(vertsvec.end(), vertsides[1].begin(), vertsides[1].end() );
01520     vertsvec.push_back(quad_save[1]);
01521     vertsvec.insert(vertsvec.end(), vertsides[2].begin(), vertsides[2].end() );
01522     if(ep)
01523         vertsvec.push_back(ep);
01524     vertsvec.insert(vertsvec.end(), vertsides[3].begin(), vertsides[3].end() );
01525     vertsvec.push_back(quad_save[2]);
01526     vertsvec.insert(vertsvec.end(), vertsides[4].begin(), vertsides[4].end() );
01527     vertsvec.push_back(sp);
01528     f = buildQuadFace(vertsvec, NULL);
01529 #ifdef OSG_UNION_TRI_QUAD
01530     f->orig_face[0] = np; f->orig_face[1] = quad_save[1];
01531     f->orig_face[2] = quad_save[2]; f->orig_face[3] = sp;
01532 #else
01533     f->orig_quad[0]     = np; f->orig_quad[1] = quad_save[1];
01534     f->orig_quad[2]     = quad_save[2]; f->orig_quad[3] = sp;
01535     f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
01536 #endif
01537 /*  std::cerr << f->orig_face[ 0 ]->coords << " ";
01538   std::cerr << f->orig_face[ 1 ]->coords << " ";
01539   std::cerr << f->orig_face[ 2 ]->coords << " ";
01540   std::cerr << f->orig_face[ 3 ]->coords << std::endl;*/
01541
01542 }
01543
01544 /*
01545  *  Subdivide the current (quad) face into two smaller faces.
01546  *  Change the values of the current face to be the upper
01547  *  half, and generate new faces, edges, etc. for the other
01548  *  quad.
01549  */
01550 int DCTPMesh::SubdivideQuadNS(DCTPFace *f, double dRatio)
01551 {
01552
01553     Vec3d       e, w;
01554     DCTPVertex *ep = NULL, *wp = NULL;
01555
01556 #ifdef OSG_UNION_TRI_QUAD
01557     e[0] = f->orig_face[2]->coords[0];
01558     w[0] = f->orig_face[3]->coords[0];
01559     e[1] = f->orig_face[2]->coords[1] + (f->orig_face[1]->coords[1] - f->orig_face[2]->coords[1]) * dRatio;
01560     e[1] = 10.0 * DCTP_EPS * floor(e[1] / (10.0 * DCTP_EPS) + 0.5);
01561     w[1] = e[1];
01562     e[2] = w[2] = 0.0;
01563 #else
01564     e = f->orig_quad[2]->coords + (f->orig_quad[1]->coords - f->orig_quad[2]->coords) * dRatio;
01565     w = f->orig_quad[3]->coords + (f->orig_quad[0]->coords - f->orig_quad[3]->coords) * dRatio;
01566 #endif
01567 
01568 //  std::cerr.precision( 16 );
01569 //  std::cerr << "SudivideQuadNS: " << dRatio << std::endl;
01570 //  f->dump_triangle( );
01571
01572     // iterate through the vertices and do splitedges if necessary
01573     std::vector<DCTPVertex*>::iterator ve = f->vertices.end();
01574     std::vector<DCTPVertex*>::iterator i;
01575
01576     for(i = f->vertices.begin(); i != ve; ++i)
01577     {
01578         if(DCTPVecIsEqual( (*i)->coords, e) )
01579             ep = *i;
01580         if(DCTPVecIsEqual( (*i)->coords, w) )
01581             wp = *i;
01582     }
01583
01584     std::vector<DCTPEdge*>::iterator ee = f->edges.end();
01585     std::vector<DCTPEdge*>::iterator ei;
01586
01587     for(ei = f->edges.begin(); ei != ee; ++ei)
01588     {
01589         ep = SplitEdge(*ei, e);
01590         if(ep != NULL)
01591             break;
01592     }
01593
01594     ee = f->edges.end();
01595
01596     for(ei = f->edges.begin(); ei != ee; ++ei)
01597     {
01598         wp = SplitEdge(*ei, w);
01599         if(wp != NULL)
01600             break;
01601     }
01602
01603     if( (ep == NULL) || (wp == NULL) )
01604     {
01605         std::cerr << "error" << std::endl;
01606     }
01607
01608     // these removals must be done after the splitedge operators
01609     // go through the edges of the face, and remove this face
01610     // from each edge.
01611     ee = f->edges.end();
01612
01613     for(std::vector<DCTPEdge*>::iterator ed = f->edges.begin(); ed != ee; ++ed)
01614         (*ed)->RemoveFace(f);
01615
01616     // go through the vertices of the face, and remove this face
01617     // from each vertex.
01618     ve = f->vertices.end();
01619
01620     for(i = f->vertices.begin(); i != ve; ++i)
01621         (*i)->RemoveFace(f);
01622
01623
01624     buildNewFacesNS(f, wp, ep, dRatio);
01625     return 0;
01626 }
01627
01628 void DCTPMesh::buildNewFacesNS(DCTPFace *f, DCTPVertex *wp, DCTPVertex *ep, double dRatio)
01629 {
01630     //set up middle point
01631 #ifdef OSG_UNION_TRI_QUAD
01632     DCTPVertex *np = findVertex( (f->orig_face[0]->coords + f->orig_face[1]->coords) * 0.5);
01633     DCTPVertex *sp = findVertex( (f->orig_face[3]->coords + f->orig_face[2]->coords) * 0.5);
01634 #else
01635     DCTPVertex *np = findVertex( (f->orig_quad[0]->coords + f->orig_quad[1]->coords) * 0.5);
01636     DCTPVertex *sp = findVertex( (f->orig_quad[3]->coords + f->orig_quad[2]->coords) * 0.5);
01637 #endif
01638     //set up new edges
01639     // v1 .----. v2
01640     //    |    |
01641     // v4 `----' v3
01642     std::vector<DCTPVertex *> vertsides[8];
01643
01644     setupSides(f, vertsides, 0.5, dRatio);
01645     sortSides(f, vertsides);
01646     //clear original face's edges and vertices
01647     f->edges.clear();
01648     f->vertices.clear();
01649
01650     DCTPVertex * quad_save[4];
01651 #ifdef OSG_UNION_TRI_QUAD
01652     quad_save[0] = f->orig_face[0]; quad_save[1] = f->orig_face[1];
01653     quad_save[2] = f->orig_face[2]; quad_save[3] = f->orig_face[3];
01654 #else
01655     quad_save[0] = f->orig_quad[0]; quad_save[1] = f->orig_quad[1];
01656     quad_save[2] = f->orig_quad[2]; quad_save[3] = f->orig_quad[3];
01657 #endif
01658 
01659     //construct the vertices-vectors of the new faces
01660     std::vector<DCTPVertex *> vertsvec;
01661     //lower
01662     vertsvec.push_back(wp);
01663     vertsvec.push_back(ep);
01664     vertsvec.insert(vertsvec.end(), vertsides[3].begin(), vertsides[3].end() );
01665     vertsvec.push_back(quad_save[2]);
01666     vertsvec.insert(vertsvec.end(), vertsides[4].begin(), vertsides[4].end() );
01667     if(sp)
01668         vertsvec.push_back(sp);
01669     vertsvec.insert(vertsvec.end(), vertsides[5].begin(), vertsides[5].end() );
01670     vertsvec.push_back(quad_save[3]);
01671     vertsvec.insert(vertsvec.end(), vertsides[6].begin(), vertsides[6].end() );
01672     buildQuadFace(vertsvec, f);
01673 #ifdef OSG_UNION_TRI_QUAD
01674     f->orig_face[0] = wp; f->orig_face[1] = ep;
01675 //  f->orig_face[ 2 ] = quad_save[ 2 ]; f->orig_face[ 3 ] = quad_save[ 3 ];
01676 #else
01677     f->orig_quad[0] = wp; f->orig_quad[1] = ep;
01678 //  f->orig_quad[ 2 ] = quad_save[ 2 ]; f->orig_quad[ 3 ] = quad_save[ 3 ];
01679     f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
01680 #endif
01681 /*  std::cerr << "NS: " << f << std::endl;
01682   std::cerr << f->orig_face[ 0 ]->coords << std::endl;
01683   std::cerr << f->orig_face[ 1 ]->coords << std::endl;
01684   std::cerr << f->orig_face[ 2 ]->coords << std::endl;
01685   std::cerr << f->orig_face[ 3 ]->coords << std::endl;*/
01686 //upper
01687     vertsvec.clear();
01688     vertsvec.push_back(quad_save[0]);
01689     vertsvec.insert(vertsvec.end(), vertsides[0].begin(), vertsides[0].end() );
01690     if(np)
01691         vertsvec.push_back(np);
01692     vertsvec.insert(vertsvec.end(), vertsides[1].begin(), vertsides[1].end() );
01693     vertsvec.push_back(quad_save[1]);
01694     vertsvec.insert(vertsvec.end(), vertsides[2].begin(), vertsides[2].end() );
01695     vertsvec.push_back(ep);
01696     vertsvec.push_back(wp);
01697     vertsvec.insert(vertsvec.end(), vertsides[7].begin(), vertsides[7].end() );
01698     f = buildQuadFace(vertsvec, NULL);
01699 #ifdef OSG_UNION_TRI_QUAD
01700     f->orig_face[0] = quad_save[0]; f->orig_face[1] = quad_save[1];
01701     f->orig_face[2] = ep; f->orig_face[3] = wp;
01702 #else
01703     f->orig_quad[0]     = quad_save[0]; f->orig_quad[1] = quad_save[1];
01704     f->orig_quad[2]     = ep; f->orig_quad[3] = wp;
01705     f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
01706 #endif
01707 /*  std::cerr << f << std::endl;
01708   std::cerr << f->orig_face[ 0 ]->coords << std::endl;
01709   std::cerr << f->orig_face[ 1 ]->coords << std::endl;
01710   std::cerr << f->orig_face[ 2 ]->coords << std::endl;
01711   std::cerr << f->orig_face[ 3 ]->coords << std::endl;*/
01712
01713 }
01714
01715 /*
01716  *  Subdivide the current (quad) face into two smaller faces.
01717  *  Change the values of the current face to be the left
01718  *  half, and generate new faces, edges, etc. for the other
01719  *  quad.
01720  */
01721 int DCTPMesh::SubdivideQuadEW(DCTPFace *f, double dRatio)
01722 {
01723
01724     Vec3d       n, s;
01725     DCTPVertex *np = NULL, *sp = NULL;
01726
01727 #ifdef OSG_UNION_TRI_QUAD
01728     n[0] = f->orig_face[0]->coords[0] + (f->orig_face[1]->coords[0] - f->orig_face[0]->coords[0]) * dRatio;
01729     n[0] = 10.0 * DCTP_EPS * floor(n[0] / (10.0 * DCTP_EPS) + 0.5);
01730     s[0] = n[0];
01731     n[1] = f->orig_face[0]->coords[1];
01732     s[1] = f->orig_face[3]->coords[1];
01733     n[2] = s[2] = 0.0;
01734 #else
01735     n = f->orig_quad[0]->coords + (f->orig_quad[1]->coords - f->orig_quad[0]->coords) * dRatio;
01736     s = f->orig_quad[3]->coords + (f->orig_quad[2]->coords - f->orig_quad[3]->coords) * dRatio;
01737 #endif
01738 
01739 //  std::cerr.precision( 4 );
01740 //  std::cerr << "SudivideQuadEW: " << dRatio << std::endl;
01741 //  f->dump_triangle( );
01742
01743     // iterate through the vertices and do splitedges if necessary
01744     std::vector<DCTPVertex*>::iterator ve = f->vertices.end();
01745     std::vector<DCTPVertex*>::iterator i;
01746
01747     for(i = f->vertices.begin(); i != ve; ++i)
01748     {
01749         if(DCTPVecIsEqual( (*i)->coords, n) )
01750             np = *i;
01751         if(DCTPVecIsEqual( (*i)->coords, s) )
01752             sp = *i;
01753     }
01754
01755     std::vector<DCTPEdge*>::iterator ee = f->edges.end();
01756     std::vector<DCTPEdge*>::iterator ei;
01757
01758     for(ei = f->edges.begin(); ei != ee; ++ei)
01759     {
01760         np = SplitEdge(*ei, n);
01761         if(np != NULL)
01762             break;
01763     }
01764
01765     ee = f->edges.end();
01766
01767     for(ei = f->edges.begin(); ei != ee; ++ei)
01768     {
01769         sp = SplitEdge(*ei, s);
01770         if(sp != NULL)
01771             break;
01772     }
01773
01774     if( (np == NULL) || (sp == NULL) )
01775     {
01776         std::cerr << "error" << std::endl;
01777     }
01778
01779     //these removals must be done after the splitedge operators
01780     //go through the edges of the face, and remove this face
01781     //from each edge.
01782     /*std::vector< DCTPEdge* >::iterator*/
01783     ee = f->edges.end();
01784
01785     for(std::vector<DCTPEdge*>::iterator ed = f->edges.begin(); ed != ee; ++ed)
01786         (*ed)->RemoveFace(f);
01787
01788     //go through the vertices of the face, and remove this face
01789     //from each vertex.
01790     ve = f->vertices.end();
01791
01792     for(i = f->vertices.begin(); i != ve; ++i)
01793         (*i)->RemoveFace(f);
01794
01795
01796     buildNewFacesEW(f, np, sp, dRatio);
01797     return 0;
01798 }
01799
01800 void DCTPMesh::buildNewFacesEW(DCTPFace *f, DCTPVertex *np, DCTPVertex *sp, double dRatio)
01801 {
01802     //set up middle point
01803 #ifdef OSG_UNION_TRI_QUAD
01804     DCTPVertex *ep = findVertex( (f->orig_face[2]->coords + f->orig_face[1]->coords) * 0.5);
01805     DCTPVertex *wp = findVertex( (f->orig_face[3]->coords + f->orig_face[0]->coords) * 0.5);
01806 #else
01807     DCTPVertex *ep = findVertex( (f->orig_quad[2]->coords + f->orig_quad[1]->coords) * 0.5);
01808     DCTPVertex *wp = findVertex( (f->orig_quad[3]->coords + f->orig_quad[0]->coords) * 0.5);
01809 #endif
01810     //set up new edges
01811     // v1 .----. v2
01812     //    |    |
01813     // v4 `----' v3
01814     std::vector<DCTPVertex *> vertsides[8];
01815
01816     setupSides(f, vertsides, dRatio, 0.5);
01817     sortSides(f, vertsides);
01818     //clear original face's edges and vertices
01819     f->edges.clear();
01820     f->vertices.clear();
01821
01822     DCTPVertex * quad_save[4];
01823 #ifdef OSG_UNION_TRI_QUAD
01824     quad_save[0] = f->orig_face[0]; quad_save[1] = f->orig_face[1];
01825     quad_save[2] = f->orig_face[2]; quad_save[3] = f->orig_face[3];
01826 #else
01827     quad_save[0] = f->orig_quad[0]; quad_save[1] = f->orig_quad[1];
01828     quad_save[2] = f->orig_quad[2]; quad_save[3] = f->orig_quad[3];
01829 #endif
01830 
01831     //construct the vertices-vectors of the new faces
01832     std::vector<DCTPVertex *> vertsvec;
01833     //left
01834     vertsvec.push_back(quad_save[0]);
01835     vertsvec.insert(vertsvec.end(), vertsides[0].begin(), vertsides[0].end() );
01836     vertsvec.push_back(np);
01837     vertsvec.push_back(sp);
01838     vertsvec.insert(vertsvec.end(), vertsides[5].begin(), vertsides[5].end() );
01839     vertsvec.push_back(quad_save[3]);
01840     vertsvec.insert(vertsvec.end(), vertsides[6].begin(), vertsides[6].end() );
01841     if(wp)
01842         vertsvec.push_back(wp);
01843     vertsvec.insert(vertsvec.end(), vertsides[7].begin(), vertsides[7].end() );
01844     buildQuadFace(vertsvec, f);
01845 #ifdef OSG_UNION_TRI_QUAD
01846     f->orig_face[1] = np; f->orig_face[2] = sp;
01847 #else
01848     f->orig_quad[1]     = np; f->orig_quad[2] = sp;
01849     f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
01850 #endif
01851 /*  std::cerr << "EW: " << f << std::endl;
01852   std::cerr << f->orig_face[ 0 ]->coords << std::endl;
01853   std::cerr << f->orig_face[ 1 ]->coords << std::endl;
01854   std::cerr << f->orig_face[ 2 ]->coords << std::endl;
01855   std::cerr << f->orig_face[ 3 ]->coords << std::endl;*/
01856 //right
01857     vertsvec.clear();
01858     vertsvec.push_back(np);
01859     vertsvec.insert(vertsvec.end(), vertsides[1].begin(), vertsides[1].end() );
01860     vertsvec.push_back(quad_save[1]);
01861     vertsvec.insert(vertsvec.end(), vertsides[2].begin(), vertsides[2].end() );
01862     if(ep)
01863         vertsvec.push_back(ep);
01864     vertsvec.insert(vertsvec.end(), vertsides[3].begin(), vertsides[3].end() );
01865     vertsvec.push_back(quad_save[2]);
01866     vertsvec.insert(vertsvec.end(), vertsides[4].begin(), vertsides[4].end() );
01867     vertsvec.push_back(sp);
01868     f = buildQuadFace(vertsvec, NULL);
01869 #ifdef OSG_UNION_TRI_QUAD
01870     f->orig_face[0] = np; f->orig_face[1] = quad_save[1];
01871     f->orig_face[2] = quad_save[2]; f->orig_face[3] = sp;
01872 #else
01873     f->orig_quad[0]     = np; f->orig_quad[1] = quad_save[1];
01874     f->orig_quad[2]     = quad_save[2]; f->orig_quad[3] = sp;
01875     f->orig_triangle[0] = f->orig_triangle[1] = f->orig_triangle[2] = NULL;
01876 #endif
01877 /*  std::cerr << f << std::endl;
01878   std::cerr << f->orig_face[ 0 ]->coords << std::endl;
01879   std::cerr << f->orig_face[ 1 ]->coords << std::endl;
01880   std::cerr << f->orig_face[ 2 ]->coords << std::endl;
01881   std::cerr << f->orig_face[ 3 ]->coords << std::endl;*/
01882
01883 }
01884
01885 DCTPFace * DCTPMesh::buildQuadFace(std::vector<DCTPVertex *> &verts, DCTPFace *f)
01886 {
01887     if(!f)
01888         f = AddFace();
01889 //  std::cerr << "buildquadface numofedges begin: " << edge_count << std::endl;
01890     std::vector<DCTPVertex *>::size_type vs = verts.size() - 1;
01891
01892     for(std::vector<DCTPVertex *>::size_type i = 0; i < vs; ++i)
01893     {
01894         if(verts[i] != verts[i + 1])
01895         {
01896 //      std::cerr << verts[ i ]->coords << verts[ i + 1 ]->coords << std::endl;
01897             DCTPEdge *ne = AddEdge(verts[i], verts[i + 1], 0);     //new edge
01898             f->edges.push_back(ne);
01899             f->vertices.push_back(verts[i]);
01900             ne->AddFace(f);
01901             verts[i]->AddFace(f);
01902         }
01903     }
01904
01905     if(verts[vs] != verts[0])
01906     {
01907 //    std::cerr << verts[ vs ]->coords << verts[ 0 ]->coords << std::endl;
01908         DCTPEdge *ne = AddEdge(verts[vs], verts[0], 0);
01909         f->edges.push_back(ne);
01910         f->vertices.push_back(verts[vs]);
01911         ne->AddFace(f);
01912         verts[vs]->AddFace(f);
01913     }
01914     f->norm = -1.0;
01915 //  std::cerr << "buildquadface numofedges end: " << edge_count << std::endl;
01916
01917     return f;
01918 }
01919
01920 DCTPEdge *DCTPMesh::getEdgeFromFace(DCTPFace *f, DCTPVertex *v1, DCTPVertex *v2)
01921 {
01922     std::vector<DCTPEdge*>::iterator ee = f->edges.end();
01923
01924     for(std::vector<DCTPEdge*>::iterator i = f->edges.begin(); i != ee; ++i)
01925     {
01926         DCTPVertex *tv1, *tv2;
01927         (*i)->getVertices(tv1, tv2);
01928         if( (DCTPVecIsEqual(v1->coords, tv1->coords) &&
01929              DCTPVecIsEqual(v2->coords, tv2->coords) ) ||
01930             (DCTPVecIsEqual(v1->coords, tv2->coords) &&
01931              DCTPVecIsEqual(v2->coords, tv1->coords) ) )
01932             return *i;
01933     }
01934
01935     std::cerr << "DCTPMesh:getEdgeFromFace: nonexistant edge requested... " << std::endl;
01936     return NULL;
01937 }
01938
01939 void DCTPMesh::sortSides(DCTPFace *f, std::vector<DCTPVertex *> * sides)
01940 {
01941     std::sort(sides[0].begin(), sides[0].end(), sortnorth() );
01942     std::sort(sides[1].begin(), sides[1].end(), sortnorth() );
01943     std::sort(sides[2].begin(), sides[2].end(), sorteast() );
01944     std::sort(sides[3].begin(), sides[3].end(), sorteast() );
01945     std::sort(sides[4].begin(), sides[4].end(), sortsouth() );
01946     std::sort(sides[5].begin(), sides[5].end(), sortsouth() );
01947     std::sort(sides[6].begin(), sides[6].end(), sortwest() );
01948     std::sort(sides[7].begin(), sides[7].end(), sortwest() );
01949
01950 }
01951
01952 void DCTPMesh::setupSides(DCTPFace *f, std::vector<DCTPVertex *> * sides, double dXRatio, double dYRatio)
01953 {
01954 #ifdef OSG_UNION_TRI_QUAD
01955     Vec3d n = f->orig_face[0]->coords + (f->orig_face[1]->coords - f->orig_face[0]->coords) * dXRatio;
01956     Vec3d s = f->orig_face[3]->coords + (f->orig_face[2]->coords - f->orig_face[3]->coords) * dXRatio;
01957 #else
01958     Vec3d n = f->orig_quad[0]->coords + (f->orig_quad[1]->coords - f->orig_quad[0]->coords) * dXRatio;
01959     Vec3d s = f->orig_quad[3]->coords + (f->orig_quad[2]->coords - f->orig_quad[3]->coords) * dXRatio;
01960 #endif
01961     Vec3d                              middle = s + (n - s) * dYRatio;
01962     std::vector<DCTPVertex*>::iterator ve     = f->vertices.end();
01963
01964     for(std::vector<DCTPVertex*>::iterator i = f->vertices.begin(); i != ve; ++i)
01965     {
01966         //top left and right
01967 #ifdef OSG_UNION_TRI_QUAD
01968         if(osgAbs((*i)->coords[1] - f->orig_face[0]->coords[1]) < DCTP_EPS)
01969         {
01970             //left
01971             if( ((*i)->coords[0] > f->orig_face[0]->coords[0]) &&
01972                 ((*i)->coords[0] < middle[0]))
01973 #else
01974         if(osgAbs((*i)->coords[1] - f->orig_quad[0]->coords[1]) < DCTP_EPS)
01975         {
01976             //left
01977             if( ((*i)->coords[0] > f->orig_quad[0]->coords[0]) &&
01978                 ((*i)->coords[0] < middle[0]))
01979 #endif
01980 
01981
01982
01983                 sides[0].push_back(*i);
01984             //right
01985 #ifdef OSG_UNION_TRI_QUAD
01986             else if( ((*i)->coords[0] > middle[0]) &&
01987                      ((*i)->coords[0] < f->orig_face[1]->coords[0]))
01988 #else
01989             else if( ((*i)->coords[0] > middle[0]) &&
01990                      ((*i)->coords[0] < f->orig_quad[1]->coords[0]))
01991 #endif
01992 
01993
01994
01995                 sides[1].push_back(*i);
01996         } //end if
01997           //right up and down
01998 #ifdef OSG_UNION_TRI_QUAD
01999         if(osgAbs((*i)->coords[0] - f->orig_face[1]->coords[0]) < DCTP_EPS)
02000         {
02001             //up
02002             if( ((*i)->coords[1] < f->orig_face[1]->coords[1]) &&
02003                 ((*i)->coords[1] > middle[1]))
02004 #else
02005         if(osgAbs((*i)->coords[0] - f->orig_quad[1]->coords[0]) < DCTP_EPS)
02006         {
02007             //up
02008             if( ((*i)->coords[1] < f->orig_quad[1]->coords[1]) &&
02009                 ((*i)->coords[1] > middle[1]))
02010 #endif
02011 
02012
02013
02014                 sides[2].push_back(*i);
02015             //down
02016 #ifdef OSG_UNION_TRI_QUAD
02017             else if( ((*i)->coords[1] < middle[1]) &&
02018                      ((*i)->coords[1] > f->orig_face[2]->coords[1]))
02019 #else
02020             else if( ((*i)->coords[1] < middle[1]) &&
02021                      ((*i)->coords[1] > f->orig_quad[2]->coords[1]))
02022 #endif
02023 
02024
02025
02026                 sides[3].push_back(*i);
02027         } //end if
02028           //bottom left and right
02029 #ifdef OSG_UNION_TRI_QUAD
02030         if(osgAbs((*i)->coords[1] - f->orig_face[2]->coords[1]) < DCTP_EPS)
02031         {
02032             //right
02033             if( ((*i)->coords[0] < f->orig_face[2]->coords[0]) &&
02034                 ((*i)->coords[0] > middle[0]))
02035 #else
02036         if(osgAbs((*i)->coords[1] - f->orig_quad[2]->coords[1]) < DCTP_EPS)
02037         {
02038             //right
02039             if( ((*i)->coords[0] < f->orig_quad[2]->coords[0]) &&
02040                 ((*i)->coords[0] > middle[0]))
02041 #endif
02042 
02043
02044
02045                 sides[4].push_back(*i);
02046             //left
02047 #ifdef OSG_UNION_TRI_QUAD
02048             else if( ((*i)->coords[0] < middle[0]) &&
02049                      ((*i)->coords[0] > f->orig_face[3]->coords[0]))
02050 #else
02051             else if( ((*i)->coords[0] < middle[0]) &&
02052                      ((*i)->coords[0] > f->orig_quad[3]->coords[0]))
02053 #endif
02054 
02055
02056
02057                 sides[5].push_back(*i);
02058         } //end if
02059           //left up and down
02060 #ifdef OSG_UNION_TRI_QUAD
02061         if(osgAbs((*i)->coords[0] - f->orig_face[3]->coords[0]) < DCTP_EPS)
02062         {
02063             //down
02064             if( ((*i)->coords[1] > f->orig_face[3]->coords[1]) &&
02065                 ((*i)->coords[1] < middle[1]))
02066 #else
02067         if(osgAbs((*i)->coords[0] - f->orig_quad[3]->coords[0]) < DCTP_EPS)
02068         {
02069             //down
02070             if( ((*i)->coords[1] > f->orig_quad[3]->coords[1]) &&
02071                 ((*i)->coords[1] < middle[1]))
02072 #endif
02073 
02074
02075
02076                 sides[6].push_back(*i);
02077             //up
02078 #ifdef OSG_UNION_TRI_QUAD
02079             else if( ((*i)->coords[1] > middle[1]) &&
02080                      ((*i)->coords[1] < f->orig_face[0]->coords[1]))
02081 #else
02082             else if( ((*i)->coords[1] > middle[1]) &&
02083                      ((*i)->coords[1] < f->orig_quad[0]->coords[1]))
02084 #endif
02085 
02086
02087
02088                 sides[7].push_back(*i);
02089         } //end if
02090     } //end for
02091
02092 }
02093
02094
02095
02096
02097
02098
02099 unsigned long DCTPMesh::getNumOfVertices(void)
02100 {
02101     return vertex_count;
02102 }
02103
02104 unsigned long DCTPMesh::getNumOfFaces(void)
02105 {
02106     return face_count;
02107 }
02108
02109 void DCTPMesh::reinit(void)
02110 {
02111     if(invalid)
02112         return;
02113
02114     dctpvertexset::iterator vend = vertices.end();
02115 #ifdef OSG_NO_EDGE_SET
02116     dctpedgevector::iterator eend = edges.end();
02117 #else
02118     dctpedgeset::iterator eend = edges.end();
02119 #endif
02120     dctpfacevector::iterator fend = faces.end();
02121
02122     for(dctpvertexset::iterator v = vertices.begin(); v != vend; ++v)
02123     {
02124         delete *v;
02125     }
02126
02127 #ifdef OSG_NO_EDGE_SET
02128 
02129     for(dctpedgevector::iterator e = edges.begin(); e != eend; ++e)
02130 #else
02131
02132     for(dctpedgeset::iterator e = edges.begin(); e != eend; ++e)
02133 #endif
02134     {
02135         delete *e;
02136     }
02137
02138     for(dctpfacevector::iterator f = faces.begin(); f != fend; ++f)
02139     {
02140         delete *f;
02141     }
02142
02143
02144     vertices.clear();
02145     edges.clear();
02146     faces.clear();
02147     vertex_count = 0;
02148     edge_count   = 0;
02149     face_count   = 0;
02150     invalid      = true;
02151 }
02152
02153 DCTPVertex * DCTPMesh::findVertex(const Vec3d& v)
02154 {
02155     DCTPVertex *vert = new DCTPVertex;
02156     if(!vert)
02157         return NULL;
02158     vert->coords = v;
02159     dctpvertexset::iterator vi = vertices.find(vert);
02160     delete vert;
02161     if(vi == vertices.end() )
02162         return NULL;
02163     else
02164         return (*vi);
02165 }
02166
02167 DCTPEdge *DCTPMesh::findEdge(DCTPVertex *v1, DCTPVertex *v2)
02168 {
02169 #ifdef OSG_NO_EDGE_SET
02170     DCTPEdge          *pcl_edge;
02171     const unsigned int cui_edge_cnt = v1->edges.size();
02172     unsigned int       ui_edge;
02173     DCTPVertex        *pcl_ev1;
02174     DCTPVertex        *pcl_ev2;
02175
02176     for(ui_edge = 0; ui_edge < cui_edge_cnt; ++ui_edge)
02177     {
02178         pcl_edge = v1->edges[ui_edge];
02179         pcl_edge->getVertices(pcl_ev1, pcl_ev2);
02180         if( (v2 == pcl_ev1) || (v2 == pcl_ev2) )
02181         {
02182             return pcl_edge;
02183         }
02184     }
02185
02186     return NULL;
02187 #else
02188     DCTPEdge             *e  = new DCTPEdge(v1, v2, 0);
02189     dctpedgeset::iterator ei = edges.find(e);
02190     delete e;
02191     if(ei == edges.end() )
02192         return NULL;
02193     else
02194         return (*ei);
02195 #endif
02196 }
02197
02198 DCTPEdge *DCTPMesh::findEdge(const Vec3d &vc1, const Vec3d &vc2)
02199 {
02200     DCTPVertex *v1 = findVertex(vc1);
02201     if(!v1)
02202     {
02203 //  std::cerr << "findEdge: vertex1 not found." << std::endl;
02204         return NULL;
02205     }
02206     DCTPVertex *v2 = findVertex(vc2);
02207     if(!v2)
02208     {
02209 //  std::cerr << "findEdge: vertex2 not found." << std::endl;
02210         return NULL;
02211     }
02212 //  std::cerr << "seachring for edge " << v1->id << ", " << v2->id << std::endl;
02213     return findEdge(v1, v2);
02214 }
02215
02216
02217 void DCTPMesh::removeFace(unsigned int ui_face)
02218 {
02219     unsigned int ui_loop;
02220     unsigned int ui_loop_cnt;
02221     DCTPFace    *pcl_face = faces[ui_face];
02222     DCTPEdge    *pcl_edge;
02223     DCTPVertex  *pcl_vertex;
02224     DCTPVertex  *pcl_vertex2;
02225 #ifdef OSG_NO_EDGE_SET
02226     unsigned int ui_edge;
02227     unsigned int ui_edge_cnt = edges.size();
02228 #endif
02229 
02230     // remove edges
02231     ui_loop_cnt = pcl_face->edges.size();
02232
02233     for(ui_loop = 0; ui_loop < ui_loop_cnt; ++ui_loop)
02234     {
02235         pcl_edge = pcl_face->edges[ui_loop];
02236         pcl_edge->RemoveFace(pcl_face);
02237         if(pcl_edge->faces.size() == 0)
02238         {
02239             // no faces left on edge
02240             pcl_edge->getVertices(pcl_vertex, pcl_vertex2);
02241             pcl_vertex->RemoveEdge(pcl_edge);
02242             pcl_vertex2->RemoveEdge(pcl_edge);
02243 #ifdef OSG_NO_EDGE_SET
02244 
02245             for(ui_edge = 0; ui_edge < ui_edge_cnt; ++ui_edge)
02246             {
02247                 if(edges[ui_edge] == pcl_edge)
02248                 {
02249                     --ui_edge_cnt;
02250                     edges[ui_edge] = edges[ui_edge_cnt];
02251                     edges.pop_back();
02252                     ui_edge = ui_edge_cnt;
02253                 }
02254             }
02255
02256 #else
02257             edges.erase(pcl_edge);
02258 #endif
02259         }
02260     }
02261
02262     // remove vertices
02263     ui_loop_cnt = pcl_face->vertices.size();
02264
02265     for(ui_loop = 0; ui_loop < ui_loop_cnt; ++ui_loop)
02266     {
02267         pcl_vertex = pcl_face->vertices[ui_loop];
02268         pcl_vertex->RemoveFace(pcl_face);
02269         if(pcl_vertex->faces.size() == 0)
02270         {
02271             vertices.erase(pcl_vertex);
02272         }
02273     }
02274
02275     // finally remove face
02276     faces[ui_face] = faces[faces.size() - 1];
02277     faces.pop_back();
02278 }