Moka gmapkernel: src/lib-gmapkernel/g-map-vertex/gmv-burstview.cc Source File

00001 /*
00002  * lib-gmapkernel : Un noyau de 3-G-cartes et des opérations.
00003  * Copyright (C) 2004, Moka Team, Université de Poitiers, Laboratoire SIC
00004  *               http://www.sic.sp2mi.univ-poitiers.fr/
00005  * Copyright (C) 2009, Guillaume Damiand, CNRS, LIRIS,
00006  *               guillaume.damiand@liris.cnrs.fr, http://liris.cnrs.fr/
00007  *
00008  * This file is part of lib-gmapkernel
00009  *
00010  * This program is free software: you can redistribute it and/or modify
00011  * it under the terms of the GNU Lesser General Public License as published by
00012  * the Free Software Foundation, either version 3 of the License, or
00013  * (at your option) any later version.
00014  *
00015  * This program is distributed in the hope that it will be useful,
00016  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00017  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00018  * GNU Lesser General Public License for more details.
00019  *
00020  * You should have received a copy of the GNU Lesser General Public License
00021  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
00022  */
00023 
00024 //******************************************************************************
00025 #include "g-map-vertex.hh"
00026 using namespace GMap3d;
00027 //******************************************************************************
00028 void CGMapVertex::setBurstMethod(TBurstMethod AMethod)
00029 {
00030   assert( FIRST_BURST_METHOD<=AMethod && AMethod<LAST_BURST_METHOD );
00031   FBurstMethod = AMethod;
00032 }
00033 //------------------------------------------------------------------------------
00034 TBurstMethod CGMapVertex::getBurstMethod() const
00035 { return FBurstMethod; }
00036 //******************************************************************************
00037 void CGMapVertex::updateAllBurstDarts()
00038 {
00039   int selected = getNewMark();
00040   negateMaskMark(selected);
00041   updateMarkedBurstDarts(selected, false);
00042   negateMaskMark(selected);
00043   freeMark(selected);
00044 }
00045 //******************************************************************************
00046 void CGMapVertex::updateMarkedBurstDarts(int AMarkNumber,
00047                                          bool AUpdateIncidentVolumes)
00048 {
00049   switch (FBurstMethod)
00050     {
00051     case BURST_METHOD_SCALE:
00052       updateMarkedDartsMethodScale(AMarkNumber, AUpdateIncidentVolumes);
00053       break;
00054     case BURST_METHOD_SHIFT:
00055       updateMarkedDartsMethodShift(AMarkNumber, AUpdateIncidentVolumes);
00056       break;
00057     default: assert(false);
00058     }
00059 }
00060 //******************************************************************************
00061 #define GET_VERTEX(DART,INDEX) (getDirectInfoAsAttributeVertex(DART, INDEX))
00062 //******************************************************************************
00063 void CGMapVertex::updateMarkedDartsMethodScale(int AMarkNumber,
00064                                                bool AUpdateIncidentVolumes)
00065 {
00066   if (AUpdateIncidentVolumes)
00067     {
00068       int selected = getNewMark();
00069       markIncidentCells(ORBIT_VERTEX, AMarkNumber, selected);
00070       markIncidentCells(ORBIT_VOLUME, selected);
00071       updateMarkedBurstDarts(selected, false);
00072       unmarkAll(selected);
00073       freeMark(selected);
00074       return;
00075     }
00076 
00077   TCoordinate k1 = getBurstCoef(1);
00078   TCoordinate k2 = getBurstCoef(2);
00079   TCoordinate k3 = getBurstCoef(3);
00080 
00081   int directIndex = getNewDirectInfo();
00082 
00083   int markV = getNewMark(); // volume mark
00084 
00085   int mark3 = getNewMark(); // volume mark
00086   int mark2 = getNewMark(); // face mark
00087   int mark1 = getNewMark(); // edge mark
00088 
00089   pointDirectInfoToAttributeVertex(directIndex);
00090 
00091   // CARTE ENTIÈRE:
00092   for (CDynamicCoverageAll all(this); all.cont(); ++all)
00093     if (!isMarked(*all, mark3))
00094       {
00095         if (!isMarked(*all, AMarkNumber))
00096           {
00097             setMark(*all, mark3);
00098             setMark(*all, mark2);
00099             setMark(*all, mark1);
00100           }
00101         else
00102           {
00103             // VOLUME:
00104             CVertex bary3 =
00105               basicBarycenter(*all, ORBIT_012, markV, mark3, directIndex);
00106 
00107             negateMaskMark(markV);
00108         
00109             for (CBasicDynamicCoverage012 vol(this, *all, markV);
00110                  vol.cont(); ++vol)
00111               if (!isMarked(*vol, mark2))
00112                 {
00113                   if (!isMarked(*vol, AMarkNumber))
00114                     {
00115                       setMark(*vol, mark2);
00116                       setMark(*vol, mark1);
00117                     }
00118                   else
00119                     {
00120                       // FACE:
00121                       CVertex bary2 =
00122                         barycenter(*vol, ORBIT_01, directIndex);
00123                 
00124                       markOrbit(*vol, ORBIT_01, mark2);
00125                 
00126                       CVertex delta2 = bary2 - bary3;
00127                 
00128                       for (CDynamicCoverage01 fac(this, *vol);
00129                            fac.cont(); ++fac)
00130                         if (!isMarked(*fac, mark1))
00131                           {
00132                             if (!isMarked(*fac, AMarkNumber))
00133                               setMark(*fac, mark1);
00134                             else
00135                               {
00136                                 // ARÊTE:
00137                                 CVertex bary1 =
00138                                   barycenter(*fac, ORBIT_0, directIndex);
00139                                 
00140                                 markOrbit(*fac, ORBIT_0, mark1);
00141                                 
00142                                 CVertex delta1 = bary1 - bary2;
00143                                 
00144                                 CVertex & b1 = getBurstVertex(   *fac );
00145                                 CVertex & b2 = getBurstVertex(alpha0(*fac));
00146 
00147                                 CAttributeVertex & v1 =
00148                                   * GET_VERTEX(   *fac , directIndex);
00149 
00150                                 CAttributeVertex & v2 =
00151                                   * GET_VERTEX(alpha0(*fac), directIndex);
00152                         
00153                                 /* Les lignes suivantes sont équivalentes à:
00154                                  *
00155                                  * b1 = bary3 +
00156                                  *      k3*(delta2 +
00157                                  *          k2*(delta1 +
00158                                  *              k1*(v1-bary1)));
00159                                  *
00160                                  * b2 = bary3 +
00161                                  *      k3*(delta2 +
00162                                  *          k2*(delta1 +
00163                                  *              k1*(v2-bary1)));
00164                                  *
00165                                  * Pour minimiser le nombre d'allocations et de
00166                                  * désallocations, elles sont remplacées par:
00167                                  */
00168                                 
00169                                 b1.setX(bary3.getX() +
00170                                         k3*(delta2.getX() +
00171                                             k2*(delta1.getX() +
00172                                                 k1*(v1.getX()-bary1.getX()))));
00173                                 
00174                                 b1.setY(bary3.getY() +
00175                                         k3*(delta2.getY() +
00176                                             k2*(delta1.getY() +
00177                                                 k1*(v1.getY()-bary1.getY()))));
00178                                 
00179                                 b1.setZ(bary3.getZ() +
00180                                         k3*(delta2.getZ() +
00181                                             k2*(delta1.getZ() +
00182                                                 k1*(v1.getZ()-bary1.getZ()))));
00183                                 
00184                                 b2.setX(bary3.getX() +
00185                                         k3*(delta2.getX() +
00186                                             k2*(delta1.getX() +
00187                                                 k1*(v2.getX()-bary1.getX()))));
00188                                 
00189                                 b2.setY(bary3.getY() +
00190                                         k3*(delta2.getY() +
00191                                             k2*(delta1.getY() +
00192                                                 k1*(v2.getY()-bary1.getY()))));
00193                                 
00194                                 b2.setZ(bary3.getZ() +
00195                                         k3*(delta2.getZ() +
00196                                             k2*(delta1.getZ() +
00197                                                 k1*(v2.getZ()-bary1.getZ()))));
00198                               }
00199                           }
00200                     }
00201                 }
00202 
00203             negateMaskMark(markV);
00204           }
00205       }
00206 
00207   freeMark(markV);
00208   negateMaskMark(mark3); freeMark(mark3);
00209   negateMaskMark(mark2); freeMark(mark2);
00210   negateMaskMark(mark1); freeMark(mark1);
00211 
00212   freeDirectInfo(directIndex);
00213 }
00214 //******************************************************************************
00215 void CGMapVertex::updateMarkedDartsMethodShift(int AMarkNumber,
00216                                                bool AUpdateIncidentVolumes)
00217 {
00219   if (AUpdateIncidentVolumes)
00220     {
00221       int selected = getNewMark();
00222       markIncidentCells(ORBIT_VERTEX, AMarkNumber, selected);
00223       markIncidentCells(ORBIT_VOLUME, selected);
00224       updateMarkedBurstDarts(selected, false);
00225       unmarkAll(selected);
00226       freeMark(selected);
00227       return;
00228     }
00229 
00230   int directIndex = getNewDirectInfo();
00231 
00232   int markV = getNewMark(); // volume mark
00233 
00234   int mark3 = getNewMark(); // volume mark
00235   int mark2 = getNewMark(); // face mark
00236   int marki = getNewMark(); // mark intersection
00237   
00238   pointDirectInfoToAttributeVertex(directIndex);
00239 
00240   // CARTE ENTIÈRE:
00241   for (CDynamicCoverageAll all(this); all.cont(); ++all)
00242     if (!isMarked(*all, mark3))
00243       {
00244         if (!isMarked(*all, AMarkNumber))
00245           {
00246             setMark(*all, mark3);
00247             setMark(*all, mark2);
00248           }
00249         else
00250           {
00251             // VOLUME:
00252             CVertex bary3 =
00253               basicBarycenter(*all, ORBIT_012, markV, mark3, directIndex);
00254 
00255             negateMaskMark(markV);
00256 
00257             for (CBasicDynamicCoverage012 vol(this, *all, markV);
00258                  vol.cont(); ++vol)
00259               if (!isMarked(*vol, mark2))
00260                 {
00261                   if (!isMarked(*vol, AMarkNumber))
00262                     setMark(*vol, mark2);
00263                   else
00264                     // Traitement d'une face :
00265                     updateFaceMethodShift(mark2,marki,*vol, bary3, directIndex);
00266                 }
00267 
00268             negateMaskMark(markV);
00269           }
00270       }
00271 
00272   freeMark(markV);
00273   negateMaskMark(mark3); freeMark(mark3);
00274   negateMaskMark(mark2); freeMark(mark2);
00275   freeMark(marki);
00276   freeDirectInfo(directIndex);
00277 }
00278 //------------------------------------------------------------------------------
00279 // A DEBUGGER !!!!!!!!!!!!!
00280 void CGMapVertex::updateFaceMethodShift(int AMarkNumber, int AMarkI,
00281                                         CDart* ADart, const CVertex& ABaryVol,
00282                                         int ADirectIndex)
00283 {
00284   TCoordinate k1 = 1 - getBurstCoef(1);
00285   TCoordinate k2 = 1 - getBurstCoef(2);
00286   TCoordinate k3 = 1 - getBurstCoef(3);  
00287   
00288   halfMarkOrbit(ADart, ORBIT_01, AMarkNumber);
00289   
00290   CVertex normalf = - faceNormalVector(ADart);
00291 
00292   CDynamicCoverage01 fac(this, ADart);
00293   
00294   for ( ; fac.cont(); ++fac)
00295     if ( !isMarked(*fac, AMarkNumber) || isFree1(*fac) )
00296       {
00297         // Point associé au sommet :
00298         CAttributeVertex& v = * GET_VERTEX(*fac, ADirectIndex);
00299         
00300         // Recherche de la première extrémité en sautant les arêtes de longueur nulle :
00301         CDart* dartExt1      = alpha0(*fac);
00302         CAttributeVertex& v1 = * GET_VERTEX(dartExt1, ADirectIndex);
00303         if ( !isFree0(*fac) )
00304           {
00305             while( v1==v && dartExt1!=alpha1(*fac) &&
00306                    !isFree1(dartExt1) && !isFree0(alpha1(dartExt1)) )
00307               {
00308                 //              cout<<"Null edge case 1"<<endl;
00309                 dartExt1 = alpha10(dartExt1);
00310                 v1       = * GET_VERTEX(dartExt1, ADirectIndex);
00311               }
00312           }
00313 
00314         // Recherche de la deuxième extrémité en sautant les arêtes de longueur nulle :
00315         CDart* dartExt2      = isFree1(*fac) ? *fac : alpha10(*fac);
00316         CAttributeVertex& v2 = * GET_VERTEX(dartExt2, ADirectIndex);
00317         while( v2==v && dartExt2!=*fac &&
00318                !isFree1(dartExt2) && !isFree0(alpha1(dartExt2)) )
00319           {
00320             //      cout<<"Null edge case 2"<<endl;
00321             dartExt2 = alpha10(dartExt2);
00322             v2       = * GET_VERTEX(dartExt2, ADirectIndex);
00323           }
00324         
00325         // Calcul "normal" :
00326 
00327         CVertex vecteur1 = v - v1;
00328         CVertex vecteur2 = v2 - v;
00329         
00330         CVertex n1 = vecteur1 * normalf; n1 *= k2 / n1.norm();
00331         CVertex n2 = vecteur2 * normalf; n2 *= k2 / n2.norm();
00332 
00333         // Intersection entre les 2 droites :
00334         CVertex intersection;
00335         if ( (v==v1 && v==v2) || n1==-n2 ) // 2eme cas pour les arêtes parallèles et opposés
00336           intersection = v;
00337         else
00338           if ( v==v1 || n1==n2 ) // 2eme cas pour les arêtes parallèles dans le même sens
00339             intersection = v + n2;
00340           else
00341             if ( v==v2 )
00342               {
00343                 if ( isMarked(*fac, AMarkNumber) )
00344                   intersection = (v -  (vecteur1.normalized() * k2)) - n1;
00345                 else
00346                   intersection = (v - (vecteur1.normalized() * k2)) + n1;
00347               }
00348             else
00349               intersection = CGeometry::getLinesIntersection(v + n1, v1 + n1 ,
00350                                                              v + n2, v2 + n2 );
00351 
00352         // Affectation des coordonnées éclatées.
00353         dartExt1 = alpha0(dartExt1);
00354         while ( dartExt1!=dartExt2 )
00355           {
00356             setBurstVertex( dartExt1, intersection );
00357             setMark       ( dartExt1, AMarkNumber  );
00358             
00359             if ( !isFree1(dartExt1) )
00360               {
00361                 setBurstVertex( alpha1(dartExt1), intersection );
00362                 setMark       ( alpha1(dartExt1), AMarkNumber  );
00363                 dartExt1 = alpha10(dartExt1);
00364               }
00365             else dartExt1 = dartExt2;
00366           }
00367       }
00368 
00369   return;
00370   
00371   unmarkOrbit(ADart, ORBIT_01, AMarkNumber);
00372   
00373   // Deuxième passe pour l'éclatement sur les arêtes (k1) et les volumes (k3)
00374   for (fac.reinit(); fac.cont(); ++fac)
00375     if (! isMarked(*fac, AMarkNumber))
00376       {
00377                 
00378         CVertex& b1 = getBurstVertex(       *fac );
00379         CVertex& b2 = getBurstVertex(alpha0(*fac));
00380       
00381         if ( b1!=b2 )
00382           {
00383             CVertex vedge = (b1 - b2).normalized();         
00384             // Point associé au sommet :
00385             CVertex & v = * GET_VERTEX(*fac, ADirectIndex);
00386             // Points associés aux sommets voisins :
00387             CVertex & v1 = * GET_VERTEX(alpha0 (*fac), ADirectIndex);
00388             
00389             CVertex vecteur1 = (v - v1).normalized();
00390             
00391             
00392             b1 -= vedge * k1;
00393             b2 += vedge * k1;
00394                                             
00395             b1 += (ABaryVol - b1) * k3;
00396             b2 += (ABaryVol - b2) * k3;
00397             
00398             //      TCoordinate cosinus = vecteur1.dot(vedge);
00399             
00400             if ( ! vedge.isNull() && isNegative(vecteur1.dot(vedge)) )
00401               {         
00402 //              setMark(*fac ,AMarkI);
00403 //              setMark(alpha0(*fac),AMarkI);
00404               }
00405           }
00406         
00407         setMark(       *fac , AMarkNumber);
00408         setMark(alpha0(*fac), AMarkNumber);
00409       }
00410 
00411   return;
00412   
00413   // Traitement des croisements
00414   unmarkOrbit(ADart, ORBIT_01, AMarkNumber);
00415 
00416   for (fac.reinit(); fac.cont(); ++fac)
00417     if ((isMarked(*fac,AMarkI )) &&  ( ! isMarked(*fac, AMarkNumber ) ))
00418       {
00419         CVertex& b1 = getBurstVertex(       *fac );
00420         //Cas ou il y a des intersections consecuitive  
00421         CVertex& b2 = getBurstVertex(alpha0(*fac));     
00422         if (b1 != b2)
00423           {
00424             CVertex vedge = (b1 - b2).normalized();
00425             
00426             // Point associé au sommet :
00427             CVertex & v = * GET_VERTEX(*fac, ADirectIndex);
00428             // Points associés aux sommets voisins :
00429             CVertex & v1 = * GET_VERTEX(alpha0 (*fac),ADirectIndex);
00430             
00431             CVertex vecteur1 = (v - v1).normalized();
00432             
00433             b1 -= vedge * k1;
00434             b2 += vedge * k1;
00435             
00436             //    b1 += (ABaryVol - b1) * k3;
00437             // b2 += (ABaryVol - b2) * k3;
00438             
00439             CVertex & b4 = getBurstVertex(alpha1 (*fac));
00440             CVertex & b3 = getBurstVertex(alpha01(*fac));
00441 
00442             b1 = b2 = b3 = b4 = b1 + (b2 - b1) / 2;
00443             
00444             setMark(*fac , AMarkNumber);
00445             setMark(alpha0(*fac) , AMarkNumber); 
00446 
00447             CDart * dartb1 = alpha1(alpha0(*fac));
00448             
00449             while ( isMarked(dartb1, AMarkI))
00450               {
00451                 
00452                 CVertex & b5 = getBurstVertex(       dartb1 );
00453                 CVertex & b6 = getBurstVertex(alpha0(dartb1));
00454                 CVertex & b7 = getBurstVertex(alpha10(dartb1));
00455                 CVertex & b8 = getBurstVertex(alpha01(dartb1));
00456 
00457                 b5 = b6 = b7 = b8 = b1;
00458                 
00459                 dartb1 = alpha1(alpha0(dartb1));
00460 
00461                 setMark(dartb1 , AMarkNumber);                                                        
00462                 setMark(alpha0(dartb1) , AMarkNumber);
00463                 }
00464           }     
00465       }  
00466 }
00467 
00468 //******************************************************************************
00469 #undef GET_VERTEX
00470 //******************************************************************************