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-vertex.hh"
00026 #include "geometry.hh"
00027 using namespace GMap3d;
00028
00029 CVertex CGMapVertex::basicBarycenter(CDart * ADart, TOrbit AOrbit,
00030 int AOrbitMark, int ATreatedMark,
00031 int ADirectInfoVertex)
00032 {
00033 assert(ADart!=NULL);
00034 assert(AOrbit==ORBIT_012 || AOrbit==ORBIT_123 || AOrbit==ORBIT_0123);
00035 assert(AOrbitMark >=0 && AOrbitMark <NB_MARKS);
00036 assert(ATreatedMark>=0 && ATreatedMark<NB_MARKS);
00037 assert(ADirectInfoVertex<NB_DIRECT_INFO);
00038
00039 CVertex bary(ORIGIN);
00040 int n = 0;
00041
00042 CCoverage * cov = getBasicDynamicCoverage(ADart, AOrbit, AOrbitMark);
00043 assert(cov!=NULL);
00044
00045 TOrbit orbit = AND_ORBIT(ORBIT_VERTEX, AOrbit);
00046
00047 for (; cov->cont(); ++(*cov))
00048 if (!isMarked(**cov, ATreatedMark))
00049 {
00050 bary +=
00051 ADirectInfoVertex>=0
00052 ? * getDirectInfoAsAttributeVertex(**cov, ADirectInfoVertex)
00053 : * findVertex(**cov);
00054
00055 ++n;
00056 markOrbit(**cov, orbit, ATreatedMark);
00057 }
00058
00059 delete cov;
00060
00061 return n==0 ? ORIGIN : bary/n;
00062 }
00063
00064 CVertex CGMapVertex::barycenter(CDart * ADart, TOrbit AOrbit,
00065 int ADirectInfoVertex)
00066 {
00067 assert(ADart!=NULL);
00068
00069 CVertex bary(ORIGIN);
00070 int n = 0;
00071 int treated = getNewMark();
00072
00073 CCoverage * cov;
00074 TOrbit orbit;
00075
00076 if (AOrbit>=ORBIT_BORDER_0 && AOrbit<=ORBIT_BORDER_3)
00077 {
00078 cov = getStaticCoverage(ADart, AOrbit);
00079 orbit = ORBIT_VERTEX;
00080 }
00081 else
00082 {
00083 cov = getDynamicCoverage(ADart, AOrbit);
00084 orbit = AND_ORBIT(AOrbit, ORBIT_VERTEX);
00085 }
00086
00087 assert(cov!=NULL);
00088
00089 for (; cov->cont(); ++(*cov))
00090 if (!isMarked(**cov, treated))
00091 {
00092 bary +=
00093 ADirectInfoVertex>=0
00094 ? * getDirectInfoAsAttributeVertex(**cov, ADirectInfoVertex)
00095 : * findVertex(**cov);
00096
00097 ++n;
00098 markOrbit(**cov, orbit, treated);
00099 }
00100
00101
00102 if (AOrbit>=ORBIT_BORDER_0 && AOrbit<=ORBIT_BORDER_3)
00103 {
00104 for (cov->reinit(); cov->cont(); ++(*cov))
00105 if (isMarked(**cov, treated))
00106 unmarkOrbit(**cov, ORBIT_VERTEX, treated);
00107 }
00108 else
00109 unmarkOrbit(ADart, AOrbit, treated);
00110
00111 delete cov;
00112
00113 freeMark(treated);
00114
00115 return n==0 ? ORIGIN : bary/n;
00116 }
00117
00118 CVertex CGMapVertex::barycenter(int AMarkNumber)
00119 {
00120 CVertex bary(ORIGIN);
00121 int n=0;
00122
00123 int treated= getNewMark();
00124
00125 for (CDynamicCoverageAll it(this); it.cont(); ++it)
00126 {
00127 if (!isMarked(*it, treated))
00128 {
00129 if (isMarked(*it, AMarkNumber))
00130 {
00131 bary += * findVertex(*it);
00132 ++n;
00133 markOrbit(*it, ORBIT_VERTEX, treated);
00134 }
00135 else
00136 setMark(*it, treated);
00137 }
00138 }
00139
00140 negateMaskMark(treated);
00141 freeMark(treated);
00142
00143 return n==0 ? ORIGIN : bary/n;
00144 }
00145
00146 CVertex CGMapVertex::directInfoBarycenter(int ADirectInfoVertex)
00147 {
00148 CVertex bary(ORIGIN);
00149 int n=0;
00150
00151 for (CDynamicCoverageAll it(this); it.cont(); ++it)
00152 if (getDirectInfo(*it, ADirectInfoVertex) != NULL)
00153 {
00154 bary += * getDirectInfoAsVertex(*it, ADirectInfoVertex);
00155 ++n;
00156 }
00157
00158 return n==0 ? ORIGIN : bary/n;
00159 }
00160
00161 void CGMapVertex::boundingBox(int AMarkNumber, CVertex & AMin, CVertex & AMax)
00162 {
00163 bool first = true;
00164 int treated = getNewMark();
00165
00166 for (CDynamicCoverageAll it(this); it.cont(); ++it)
00167 if (! isMarked(*it, treated))
00168 {
00169 if (isMarked(*it, AMarkNumber))
00170 {
00171 markOrbit(*it, ORBIT_VERTEX, treated);
00172
00173 CVertex & vertex = * findVertex(*it);
00174
00175 if (first)
00176 {
00177 first = false;
00178 AMin = AMax = vertex;
00179 }
00180 else
00181 {
00182 if (vertex.getX() < AMin.getX()) AMin.setX(vertex.getX());
00183 if (vertex.getY() < AMin.getY()) AMin.setY(vertex.getY());
00184 if (vertex.getZ() < AMin.getZ()) AMin.setZ(vertex.getZ());
00185
00186 if (vertex.getX() > AMax.getX()) AMax.setX(vertex.getX());
00187 if (vertex.getY() > AMax.getY()) AMax.setY(vertex.getY());
00188 if (vertex.getZ() > AMax.getZ()) AMax.setZ(vertex.getZ());
00189 }
00190 }
00191 else
00192 setMark(*it, treated);
00193 }
00194
00195 if (first == true)
00196 AMin = AMax = ORIGIN;
00197
00198 negateMaskMark(treated);
00199 freeMark(treated);
00200 }
00201
00202 CVertex CGMapVertex::centerOfBoundingBox(int AMarkNumber)
00203 {
00204 CVertex min, max;
00205
00206 boundingBox(AMarkNumber, min, max);
00207
00208 return (min + max) / 2;
00209 }
00210
00211 void CGMapVertex::boundingBox(CDart * ADart, TOrbit AOrbit,
00212 CVertex & AMin, CVertex & AMax)
00213 {
00214 assert(ADart != NULL);
00215
00216 bool first = true;
00217 int treated = getNewMark();
00218 CCoverage * cov = getDynamicCoverage(ADart, AOrbit);
00219
00220 for (; cov->cont(); ++(*cov))
00221 if (! isMarked(**cov, treated))
00222 {
00223 markOrbit(**cov, AND_ORBIT(AOrbit, ORBIT_VERTEX), treated);
00224
00225 CVertex & vertex = * findVertex(**cov);
00226
00227 if (first)
00228 {
00229 first = false;
00230 AMin = AMax = vertex;
00231 }
00232 else
00233 {
00234 if (vertex.getX() < AMin.getX()) AMin.setX(vertex.getX());
00235 if (vertex.getY() < AMin.getY()) AMin.setY(vertex.getY());
00236 if (vertex.getZ() < AMin.getZ()) AMin.setZ(vertex.getZ());
00237
00238 if (vertex.getX() > AMax.getX()) AMax.setX(vertex.getX());
00239 if (vertex.getY() > AMax.getY()) AMax.setY(vertex.getY());
00240 if (vertex.getZ() > AMax.getZ()) AMax.setZ(vertex.getZ());
00241 }
00242 }
00243
00244 assert(first == false);
00245
00246 unmarkOrbit(ADart, AOrbit, treated);
00247 freeMark(treated);
00248 delete cov;
00249 }
00250
00251 CVertex CGMapVertex::centerOfBoundingBox(CDart * ADart, TOrbit AOrbit)
00252 {
00253 assert(ADart != NULL);
00254 CVertex min, max;
00255
00256 boundingBox(ADart, AOrbit, min, max);
00257
00258 return (min + max) / 2;
00259 }
00260
00261 #define PUSH(STACK,V) \
00262 ( \
00263 (STACK)[1]= (STACK)[0], \
00264 (STACK)[0]= (V) \
00265 )
00266
00267 #define DISTANCE(STACK) \
00268 ( \
00269 (*(STACK)[0] - *(STACK)[1]).norm() \
00270 )
00271
00272
00273 TCoordinate CGMapVertex::orbitLength(CDart * ADart, TOrbit AOrbit)
00274 {
00275 assert(ADart!=NULL);
00276 assert(AOrbit==ORBIT_0 || AOrbit==ORBIT_BORDER_1 ||
00277 AOrbit==ORBIT_01 || AOrbit==ORBIT_BORDER_2);
00278
00279 TCoordinate length=0;
00280
00281
00282
00283 {
00284 CCoverage * firstIt = getDynamicCoverage(ADart, AOrbit);
00285
00286 while (firstIt->cont() && firstIt->prevOperationType()!=OP_JUMP)
00287 ADart= (*firstIt)++;
00288
00289 delete firstIt;
00290 }
00291
00292 {
00293 CCoverage * it = getDynamicCoverage(ADart, AOrbit);
00294 CVertex * stack[2] = { NULL, NULL };
00295
00296 if (isFree0(**it))
00297 ++(*it);
00298
00299
00300
00301 PUSH(stack, findVertex((*it)++));
00302
00303
00304 while (it->cont())
00305 {
00306 PUSH(stack, findVertex((*it)++));
00307 length+= DISTANCE(stack);
00308
00309 if (it->cont()) ++(*it);
00310 }
00311
00312 delete it;
00313 }
00314
00315 return length;
00316 }
00317
00318 #undef DISTANCE
00319 #undef PUSH
00320
00321 TCoordinate CGMapVertex::edgeLength(CDart * ADart)
00322 {
00323 assert(ADart!=NULL);
00324
00325 if (isFree0(ADart))
00326 return 0;
00327
00328 return (*findVertex(ADart) - *findVertex(alpha0(ADart))).norm();
00329 }
00330
00331 TCoordinate CGMapVertex::facePerimeter(CDart * ADart)
00332 {
00333 assert(ADart!=NULL);
00334 return orbitLength(ADart, ORBIT_01);
00335 }
00336
00337 TCoordinate CGMapVertex::border1Length(CDart * ADart)
00338 {
00339 assert(ADart!=NULL);
00340 return orbitLength(ADart, ORBIT_BORDER_1);
00341 }
00342
00343 TCoordinate CGMapVertex::border2Length(CDart * ADart)
00344 {
00345 assert(ADart!=NULL);
00346 return orbitLength(ADart, ORBIT_BORDER_2);
00347 }
00348
00349 #define PUSH(STACK,V) \
00350 ( \
00351 (STACK)[2]=(STACK)[1], \
00352 (STACK)[1]=(STACK)[0], \
00353 (STACK)[0]=(V) \
00354 )
00355
00356 #define NORMAL(STACK) \
00357 ( \
00358 CGeometry::getNormalVector(*(STACK)[0] - *(STACK)[1] , \
00359 *(STACK)[2] - *(STACK)[1] ) \
00360 )
00361
00362
00363 CVertex CGMapVertex::orbitNormalVector(CDart * ADart, TOrbit AOrbit)
00364 {
00365 assert(ADart!=NULL);
00366 assert(AOrbit==ORBIT_01 || AOrbit==ORBIT_BORDER_2);
00367
00368 CVertex normal(ORIGIN);
00369 int nbEdges = 0;
00370 bool closed;
00371
00372
00373
00374 if (isFree1(ADart))
00375 {
00376 if (isFree0(ADart))
00377 return OX;
00378
00379 closed = false;
00380 }
00381 else
00382 {
00383
00384 CVertex * vertex0 = findVertex(ADart);
00385 CDart * current=NULL;
00386 CCoverage * cov = getDynamicCoverage(ADart, AOrbit);
00387
00388 while (cov->cont())
00389 current = (*cov)++;
00390
00391 closed = vertex0==findVertex(current);
00392 ADart = closed ? ADart : current;
00393
00394 delete cov;
00395 }
00396
00397
00398
00399
00400 {
00401 CCoverage * it = getDynamicCoverage(ADart, AOrbit);
00402 CVertex * stack[3] = { NULL, NULL, NULL };
00403 CVertex * second;
00404
00405 if (isFree0(**it))
00406 ++(*it);
00407
00408
00409
00410 PUSH(stack, findVertex((*it)++));
00411
00412 if (!it->cont())
00413 {
00414 delete it;
00415 return OX;
00416 }
00417
00418
00419
00420 PUSH(stack, second = findVertex((*it)++));
00421
00422 if (it->cont())
00423 ++(*it);
00424
00425 if (!it->cont())
00426 {
00427 delete it;
00428 return CGeometry::getNormalVector(*stack[0] - *stack[1]);
00429 }
00430
00431
00432 while (it->cont())
00433 {
00434 PUSH(stack, findVertex((*it)++));
00435 normal+= NORMAL(stack);
00436 ++nbEdges;
00437
00438 if (it->cont())
00439 ++(*it);
00440 }
00441
00442 delete it;
00443
00444
00445 if (closed)
00446 {
00447 PUSH(stack, second);
00448 normal+= NORMAL(stack);
00449 ++nbEdges;
00450 }
00451 }
00452
00453 if (normal.isNull())
00454 return OZ;
00455
00456 assert(nbEdges>0);
00457
00458
00459 return normal/(2*sqrt(static_cast<double>(nbEdges)));
00460 }
00461
00462 #undef NORMAL
00463 #undef PUSH
00464
00465 CVertex CGMapVertex::edgeVector(CDart * ADart)
00466 {
00467 assert(ADart!=NULL);
00468
00469 return * findVertex(alpha0(ADart)) - * findVertex(ADart);
00470 }
00471
00472 CVertex CGMapVertex::edgeNormalVector(CDart * ADart)
00473 {
00474 assert(ADart!=NULL);
00475
00476 CVertex vector = edgeVector(ADart);
00477
00478 if (vector.isNull())
00479 return OX;
00480
00481 return CGeometry::getNormalVector(vector);
00482 }
00483
00484 CVertex CGMapVertex::faceNormalVector(CDart * ADart)
00485 {
00486 assert(ADart!=NULL);
00487 return orbitNormalVector(ADart, ORBIT_01);
00488 }
00489
00490 CVertex CGMapVertex::cellNormalVector(int ADim, CDart * ADart)
00491 {
00492 assert(0<=ADim && ADim<=2);
00493
00494 if (ADim==2)
00495 return faceNormalVector(ADart);
00496
00497 if (ADim==1)
00498 return edgeNormalVector(ADart);
00499
00500 return OX;
00501 }
00502
00503 CVertex CGMapVertex::border2NormalVector(CDart * ADart)
00504 {
00505 assert(ADart!=NULL);
00506 return orbitNormalVector(ADart, ORBIT_BORDER_2);
00507 }
00508
00509 CVertex CGMapVertex::regionNormalVector(CDart * ADart, int ADim)
00510 {
00511 assert(ADart!=NULL);
00512 assert(ADim>=0 && ADim<=2);
00513
00514
00515
00516
00517
00518
00519 TOrbit orbitCell = AND_ORBIT(ORBIT_CELL[ADim], NEG_ORBIT(ORBIT_3));
00520
00521
00522
00523
00524
00525
00526
00527
00528
00529
00530
00531 CVertex normal = ORIGIN;
00532 int n = 0;
00533
00534 int toTreat = getNewMark();
00535
00536 halfMarkOrbit(ADart, orbitCell, toTreat);
00537
00538 CCoverage * cov = getDynamicCoverage(ADart, orbitCell);
00539
00540 for (; cov->cont(); ++(*cov))
00541 if (isMarked(**cov, toTreat))
00542 {
00543 if (ADim==2)
00544 {
00545 if (!isFree2(**cov))
00546 {
00547 normal -= faceNormalVector(alpha(**cov, ADim));
00548 ++n;
00549 }
00550 }
00551 else
00552 {
00553 normal += faceNormalVector(**cov);
00554 ++n;
00555 }
00556
00557 unsetMark(**cov, toTreat);
00558 }
00559
00560 delete cov;
00561
00562 freeMark(toTreat);
00563
00564 return normal/(n==0 ? 1 : n);
00565 }
00566
00567 CVertex CGMapVertex::regionNormalVector(CDart * ADart, int ADim,
00568 int AMarkNumber)
00569 {
00570 assert(ADart!=NULL);
00571 assert(ADim>=0 && ADim<=2);
00572 assert(AMarkNumber>=0);
00573
00574 CVertex normal = ORIGIN;
00575 int n = 0;
00576
00577 int toTreat = getNewMark();
00578
00579 markCopy(AMarkNumber, toTreat, ADart, ORBIT_CELL[ADim]);
00580
00581 CCoverage * cov = getDynamicCoverage(ADart, ORBIT_CELL[ADim]);
00582
00583 for (; cov->cont(); ++(*cov))
00584 if (isMarked(**cov, toTreat))
00585 {
00586 if (ADim==2)
00587 {
00588 if (!isFree2(**cov))
00589 {
00590 normal -= faceNormalVector(alpha(**cov, ADim));
00591 ++n;
00592 }
00593 }
00594 else
00595 {
00596 normal += faceNormalVector(**cov);
00597 ++n;
00598 }
00599
00600 unsetMark(**cov, toTreat);
00601 }
00602
00603 delete cov;
00604
00605 freeMark(toTreat);
00606
00607 return normal/(n==0 ? 1 : n);
00608 }
00609
00610 CVertex CGMapVertex::cellDimensionNormalVector(CDart * ADart, int ADim)
00611 {
00612 assert(ADart!=NULL);
00613 assert(3 <= ADim && ADim <= 4);
00614
00615 if (!isOrientable(ADart, ORBIT_CELL[ADim]))
00616 return ORIGIN;
00617
00618 TOrbit pieceOfFace = AND_ORBIT(ORBIT_CELL[2], ORBIT_CELL[ADim]);
00619
00620 int treated = getNewMark();
00621 int out = getNewMark();
00622
00623 halfMarkOrbit(ADart, ORBIT_CELL[ADim], out);
00624
00625 CCoverage * cov = getDynamicCoverage(ADart, ORBIT_CELL[ADim]);
00626
00627 CVertex normal = ORIGIN;
00628 int nbFaces = 0;
00629
00630 for (; cov->cont(); ++(*cov))
00631 if (!isMarked(**cov, treated) && isMarked(**cov, out))
00632 {
00633 markOrbit(**cov, pieceOfFace, treated);
00634
00635 if (ADim==3 || isFree3(**cov))
00636 {
00637 normal += faceNormalVector(**cov);
00638 ++nbFaces;
00639 }
00640 }
00641
00642 for (cov->reinit(); cov->cont(); ++(*cov))
00643 {
00644 unsetMark(**cov, treated);
00645 unsetMark(**cov, out);
00646 }
00647
00648 delete cov;
00649
00650 freeMark(treated);
00651 freeMark(out);
00652
00653 if (nbFaces>0)
00654 normal /= nbFaces;
00655
00656 return normal;
00657 }
00658