00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 #include "g-map-generic.hh"
00026 using namespace std;
00027 using namespace GMap3d;
00028
00029 CDart * CGMapGeneric::insertVertex(CDart * ADart)
00030 {
00031 assert(ADart!=NULL);
00032
00033 bool closed = !isFree0(ADart);
00034 int treated = getNewMark();
00035
00036 CDynamicCoverage23 it(this, ADart);
00037
00038 for (; it.cont(); setMark(*it, treated), ++it)
00039 {
00040 CDart * d0 = alpha0(*it);
00041 CDart * n1 = addMapDart();
00042 CDart * n2 = addMapDart();
00043
00044 linkAlpha0(*it, n1);
00045 if (closed) linkAlpha0(d0 , n2);
00046
00047 linkAlpha1(n1, n2);
00048
00049 if (!isFree2(*it) && isMarked(alpha2(*it), treated))
00050 {
00051 linkAlpha2(n1, alpha20(*it));
00052 linkAlpha2(n2, alpha21(n1 ));
00053 }
00054
00055 if (!isFree3(*it) && isMarked(alpha3(*it), treated))
00056 {
00057 linkAlpha3(n1, alpha30(*it));
00058 linkAlpha3(n2, alpha31(n1 ));
00059 }
00060 }
00061
00062 unmarkOrbit(ADart, ORBIT_23, treated);
00063 freeMark(treated);
00064
00065 return alpha0(ADart);
00066 }
00067
00068 int CGMapGeneric::insertVertexOnMarkedEdges(int AMarkNumber)
00069 {
00070 CDynamicCoverageAll it(this);
00071 int nbInserted = 0;
00072 int treated = getNewMark();
00073
00074 for (; it.cont(); ++it)
00075 if (!isMarked(*it, treated))
00076 {
00077 if (isMarked(*it, AMarkNumber))
00078 {
00079 markOrbit(*it, ORBIT_EDGE, treated);
00080
00081 CDart * newVertex= insertVertex(*it);
00082 markOrbit(newVertex, ORBIT_VERTEX, treated);
00083 ++nbInserted;
00084 }
00085 else
00086 setMark(*it, treated);
00087 }
00088
00089 negateMaskMark(treated);
00090 freeMark(treated);
00091
00092 return nbInserted;
00093 }
00094
00095 CDart * CGMapGeneric::insertEdge(CDart * ADart1, CDart * ADart2)
00096 {
00097 assert(ADart1!=NULL && ADart2!=NULL);
00098
00099
00100 CDart * n1 = addMapDart();
00101 CDart * n2 = addMapDart();
00102
00103 linkAlpha0(n1,n2);
00104
00105 CDart * dd1 = isFree1(ADart1) ? NULL : alpha1(ADart1);
00106 CDart * dd2 = isFree1(ADart2) ? NULL : alpha1(ADart2);
00107
00108 linkAlpha1(ADart1,n1); linkAlpha1(ADart2,n2);
00109
00110 if (dd1!=NULL || dd2!=NULL)
00111 {
00112 CDart * nn1=addMapDart();
00113 CDart * nn2=addMapDart();
00114
00115 linkAlpha0(nn1,nn2);
00116 linkAlpha2(n1,nn1); linkAlpha2(n2,nn2);
00117
00118 if (dd1!=NULL) linkAlpha1(dd1,nn1);
00119 if (dd2!=NULL) linkAlpha1(dd2,nn2);
00120 }
00121
00122
00123 if (!isFree3(ADart1))
00124 {
00125 n1=addMapDart(); n2=addMapDart();
00126 linkAlpha0(n1,n2);
00127 linkAlpha3(n1,alpha1(ADart1)); linkAlpha3(n2,alpha1(ADart2));
00128
00129 if (dd1!=NULL) unlinkAlpha1(alpha3(ADart1));
00130 if (dd2!=NULL) unlinkAlpha1(alpha3(ADart2));
00131
00132 linkAlpha1(n1,alpha3(ADart1)); linkAlpha1(n2,alpha3(ADart2));
00133 if (dd1!=NULL || dd2!=NULL)
00134 {
00135 CDart * nn1=addMapDart();
00136 CDart * nn2=addMapDart();
00137
00138 linkAlpha0(nn1,nn2);
00139 linkAlpha2(n1,nn1); linkAlpha2(n2,nn2);
00140
00141 if (dd1!=NULL) linkAlpha1(alpha3(dd1),nn1);
00142 if (dd2!=NULL) linkAlpha1(alpha3(dd2),nn2);
00143
00144 linkAlpha3(alpha1(dd1),nn1); linkAlpha3(alpha1(dd2),nn2);
00145 }
00146 }
00147
00148 return alpha1(ADart1);
00149 }
00150
00151 int CGMapGeneric::insertEdgeOnMarkedFaces(int AMarkNumber,
00152 bool ANoCrossedFace,
00153 bool )
00154 {
00155 CDynamicCoverageAll it(this);
00156 int nbInserted = 0;
00157 int treated = getNewMark();
00158 int mark = getNewMark();
00159
00160 for (; it.cont(); ++it)
00161 if (!isMarked(*it, treated))
00162 {
00163 if (!isMarked(*it, AMarkNumber))
00164 setMark(*it, treated);
00165 else
00166 {
00167
00168 markOrbit(*it, ORBIT_FACE, treated);
00169
00170
00171 bool canInsert = true;
00172 CDart * d1 = NULL, * d2 = NULL;
00173
00174 CDynamicCoverageFace cov(this, *it);
00175
00176 for (; cov.cont() && canInsert; ++cov)
00177 if (isMarked(*cov, AMarkNumber) && !isMarked(*cov, mark))
00178 {
00179 if (ANoCrossedFace)
00180 markOrbit(*cov, ORBIT_13, mark);
00181
00182 if (d1==NULL)
00183 d1= *cov;
00184 else if (d2==NULL)
00185 d2= *cov;
00186 else
00187 canInsert = false;
00188 }
00189
00190 if (ANoCrossedFace)
00191 unmarkOrbit(*it, ORBIT_FACE, mark);
00192
00193 canInsert &= (d2!=NULL);
00194
00195 if (canInsert && ANoCrossedFace && !isSameOrbit(d1,d2,ORBIT_01))
00196 d2 = alpha3(d2);
00197
00198 if (canInsert && belongToSameOrientedOrbit(d1, d2, ORBIT_01))
00199 d2 = alpha1(d2);
00200
00201
00202 if (canInsert)
00203 {
00204 CDart * newEdge = insertEdge(d1,d2);
00205 markOrbit(newEdge, ORBIT_EDGE, treated);
00206 ++nbInserted;
00207 }
00208 }
00209 }
00210
00211 negateMaskMark(treated);
00212 freeMark(treated);
00213 freeMark(mark);
00214
00215 return nbInserted;
00216 }
00217
00218 #define IS_MARKED_EDGE(D) \
00219 ( \
00220 isMarked(D, AMarkNumber) || isMarked(alpha0(D), AMarkNumber) || \
00221 ( \
00222 ANoCrossedVolume && !isFree2(D) && \
00223 (isMarked(alpha2(D), AMarkNumber) || isMarked(alpha20(D), AMarkNumber)) \
00224 ) \
00225 )
00226
00227 #define IS_VALID_EDGE(D) \
00228 (ANoCrossedVolume || isFree2(D) || \
00229 (!isMarked( D , AMarkNumber) && !isMarked(alpha0 (D), AMarkNumber)) || \
00230 (!isMarked(alpha2(D), AMarkNumber) && !isMarked(alpha02(D), AMarkNumber)))
00231
00232 #define IS_ON_SAME_EDGE(D1,D2) \
00233 ((D1)==(D2) || (ANoCrossedVolume && ((D1)==alpha2(D2))))
00234
00235
00236 bool CGMapGeneric::turnAroundVertex(CDart * ADart, bool ANoCrossedVolume,
00237 int AMarkNumber,
00238 CDart * & ANext, bool & ACrossed)
00239 {
00240 assert(ADart!=NULL);
00241 assert(IS_MARKED_EDGE(ADart));
00242
00243 bool firstDirection = true;
00244 bool validVertex = true;
00245
00246 ANext = NULL;
00247
00248 for (CDynamicCoverage12 cov(this, ADart); validVertex && cov.cont(); ++cov)
00249 {
00250 if (cov.prevOperationType() == OP_JUMP)
00251 firstDirection = false;
00252
00253 if (IS_MARKED_EDGE(*cov) && !IS_ON_SAME_EDGE(*cov, ADart) &&
00254 (ANext==NULL || !IS_ON_SAME_EDGE(*cov, ANext)))
00255 {
00256 validVertex = ANext==NULL && IS_VALID_EDGE(*cov);
00257
00258 if (validVertex)
00259 {
00260 ACrossed =
00261 cov.prevOperationType() ==
00262 (firstDirection ? OP_ALPHAJ : OP_ALPHAI);
00263
00264 if (ACrossed && !isFree2(*cov) && IS_MARKED_EDGE(alpha2(*cov)))
00265 {
00266 ACrossed = false;
00267 ANext = alpha2(*cov);
00268 }
00269 else
00270 ANext = *cov;
00271 }
00272 else
00273 ANext = NULL;
00274 }
00275 }
00276
00277 return validVertex;
00278 }
00279
00280 bool CGMapGeneric::canInsertFace(CDart * ADart, int AMarkNumber,
00281 bool ANoCrossedVolume,
00282 bool ANoTwoEdgesFace,
00283 bool ANoTwoFacesVolume)
00284 {
00285 assert(ADart!=NULL);
00286 assert(isMarked(ADart, AMarkNumber));
00287
00288
00289
00290
00291
00292
00293 CDart * current = ADart;
00294 int nbVertices = 0;
00295
00296 bool firstDirection = true;
00297 bool finished = false;
00298 bool canInsert = IS_VALID_EDGE(current);
00299 bool sameFace[2] = { true, true };
00300
00301
00302
00303 while (canInsert && !finished)
00304 {
00305
00306
00307 ++nbVertices;
00308
00309
00310 CDart * next;
00311 bool crossed;
00312
00313 canInsert = turnAroundVertex(current, ANoCrossedVolume, AMarkNumber,
00314 next, crossed);
00315 if (next!=NULL)
00316 {
00317 sameFace[0] =
00318 sameFace[crossed ? 1 : 0] && isSameOrbit(alpha1 (next), current, ORBIT_2);
00319
00320 sameFace[1] =
00321 sameFace[crossed ? 0 : 1] && isSameOrbit(alpha21(next), current, ORBIT_2);
00322 }
00323
00324 if (canInsert)
00325 {
00326 if (next==NULL || isFree0(next))
00327 {
00328
00329 finished = !firstDirection || isFree0(ADart);
00330 firstDirection = false;
00331 current = alpha0(ADart);
00332 }
00333 else
00334 {
00335
00336 current = alpha0(next);
00337
00338 if (IS_ON_SAME_EDGE(current, ADart))
00339 finished = true;
00340 }
00341 }
00342 }
00343
00344
00345 bool enoughEdges = !ANoTwoEdgesFace || nbVertices >= (firstDirection ? 3 : 2);
00346 bool enoughFaces = !ANoTwoFacesVolume || (!sameFace[0] && !sameFace[1]);
00347
00348 return canInsert && enoughEdges && enoughFaces;
00349 }
00350
00351 CDart * CGMapGeneric::insertFace(CDart * ADart, int AMarkNumber,
00352 bool ANoCrossedVolume)
00353 {
00354 assert(ADart!=NULL);
00355 assert(canInsertFace(ADart, AMarkNumber, ANoCrossedVolume));
00356
00357
00358 bool firstDirection = true ;
00359 bool finished = false;
00360 bool turnedAround = false;
00361 bool jumped = false;
00362
00363 CDart * prev = NULL, * current = ADart, * next;
00364
00365
00366
00367 while (!finished)
00368 {
00369 assert(!turnedAround || !jumped);
00370
00371
00372
00373
00374 if (turnedAround)
00375 {
00376
00377 next = isFree0(current) ? NULL : alpha0(current);
00378 }
00379 else
00380 {
00381
00382 bool crossed;
00383 turnAroundVertex(current, ANoCrossedVolume,
00384 AMarkNumber, next, crossed);
00385
00386 if (next!=NULL && crossed && ANoCrossedVolume)
00387 {
00388 assert(!isFree2(current));
00389 current = alpha2(current);
00390 if (prev!=NULL)
00391 {
00392 assert(!isFree2(prev));
00393 prev = alpha2(prev);
00394 }
00395 }
00396 }
00397
00398
00399 CDart * d1 = current;
00400 CDart * d2 = isFree2(d1) ? NULL : alpha2(d1);
00401 CDart * n1 = addMapDart();
00402 CDart * n2 = addMapDart();
00403
00404 if (d2!=NULL)
00405 {
00406 unlinkAlpha2(d1);
00407 linkAlpha2(d2,n2);
00408 }
00409
00410 linkAlpha3(n1,n2);
00411 linkAlpha2(d1,n1);
00412
00413 if (turnedAround)
00414 {
00415 linkAlpha1(alpha2 (d1), alpha2 (prev));
00416 linkAlpha1(alpha23(d1), alpha23(prev));
00417 }
00418
00419 if (jumped)
00420 {
00421 linkAlpha0(n1, alpha02 (d1));
00422 linkAlpha0(n2, alpha023(d1));
00423 }
00424
00425
00426 if (next==NULL)
00427 {
00428
00429 finished = !firstDirection || isFree0(ADart);
00430 firstDirection = false;
00431 turnedAround = false;
00432 jumped = true;
00433 prev = ADart;
00434 current = alpha0(ADart);
00435 }
00436 else
00437 if (IS_ON_SAME_EDGE(next, ADart))
00438 finished = true;
00439 else
00440 {
00441 prev = current; jumped = turnedAround;
00442 current = next ; turnedAround = !turnedAround;
00443 }
00444 }
00445
00446
00447 if (firstDirection)
00448 {
00449 assert(!isFree2(next));
00450 linkAlpha0(alpha2 (ADart), alpha02 (ADart));
00451 linkAlpha0(alpha23(ADart), alpha023(ADart));
00452 }
00453
00454 return alpha2(ADart);
00455 }
00456
00457 #undef IS_ON_SAME_EDGE
00458 #undef IS_VALID_EDGE
00459 #undef IS_MARKED_EDGE
00460
00461 int CGMapGeneric::insertFaceOnMarkedVolumes(int AMarkNumber,
00462 bool ANoCrossedVolume,
00463 bool ANoTwoEdgesFace,
00464 bool ANoTwoFacesVolume)
00465 {
00466 CDynamicCoverageAll it(this);
00467 int nbInserted = 0;
00468 int treated = getNewMark();
00469
00470 for (; it.cont(); ++it)
00471 if (!isMarked(*it, treated))
00472 {
00473 if (isMarked(*it, AMarkNumber))
00474 {
00475
00476 stack<CDart *> toTreat; toTreat.push(*it);
00477
00478 while (!toTreat.empty())
00479 {
00480 CDart * dart = toTreat.top(); toTreat.pop();
00481
00482 for (CDynamicCoverage12 cov(this, dart); cov.cont(); ++cov)
00483 if (!isMarked(*cov, treated))
00484 {
00485 if (!isFree0(*cov) && !isMarked(alpha0(*cov), treated) &&
00486 (isMarked(*cov, AMarkNumber) ||
00487 isMarked(alpha0(*cov), AMarkNumber)))
00488 toTreat.push(alpha0(*cov));
00489
00490 setMark( *cov , treated);
00491 setMark(alpha2(*cov), treated);
00492 }
00493 }
00494
00495
00496 if (canInsertFace(*it, AMarkNumber, ANoCrossedVolume,
00497 ANoTwoEdgesFace, ANoTwoFacesVolume))
00498 {
00499 CDart * newFace = insertFace(*it, AMarkNumber, ANoCrossedVolume);
00500
00501 markOrbit(newFace, ORBIT_FACE, treated);
00502 ++nbInserted;
00503 }
00504 }
00505 else
00506 setMark(*it, treated);
00507 }
00508
00509 negateMaskMark(treated);
00510 freeMark(treated);
00511
00512 return nbInserted;
00513 }
00514