Moka libraries
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
corefine-3d-face-face.cc
Go to the documentation of this file.
1 /*
2  * lib-corefinement : Opérations de corafinement.
3  * Copyright (C) 2004, Moka Team, Université de Poitiers, Laboratoire SIC
4  * http://www.sic.sp2mi.univ-poitiers.fr/
5  * Copyright (C) 2009, Guillaume Damiand, CNRS, LIRIS,
6  * guillaume.damiand@liris.cnrs.fr, http://liris.cnrs.fr/
7  *
8  * This file is part of lib-corefinement
9  *
10  * This program is free software: you can redistribute it and/or modify
11  * it under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation, either version 3 of the License, or
13  * (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  * GNU Lesser General Public License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this program. If not, see <http://www.gnu.org/licenses/>.
22  */
23 
24 #include <set>
25 #include <cfloat>
26 #include <sstream>
27 
28 // #define DEBUG_MESSAGES
29 // #define DEBUG_MARKS
30 // #define SAVE_STEPS_SINCE 11090
31 // #define SAVE_STEPS_UNTIL 200
32 #include "message-macros.hh"
33 
34 #include "corefine-3d-face-face.hh"
35 
36 using namespace std;
37 using namespace GMap3d;
38 
39 //******************************************************************************
40 
41 #define a0 FMap->alpha0
42 #define a1 FMap->alpha1
43 #define a2 FMap->alpha2
44 #define a3 FMap->alpha3
45 
46 // #define VTX(d) (FMap->findVertex(d))
47 #define VTX(d) ((CAttributeVertex*)FMap->getDirectInfo(d, FVertexDI))
48 #define LINK(d) ((CDart*)FMap->getDirectInfo(d, FLinkedVertexDI))
49 
50 #ifdef DEBUG_MARKS
51 #define freeMark(m) (assert(FMap->isWholeMapUnmarked(m)), FMap->freeMark(m))
52 #else // DEBUG_MARKS
53 #define freeMark(m) (FMap->freeMark(m))
54 #endif // DEBUG_MARKS
55 
56 //******************************************************************************
57 
58 struct SFaceListIterators
59 {
60  SFaceListIterators() {}
61  SFaceListIterators(TCorefFaceList::iterator f1, TCorefFaceList::iterator l1,
62  TCorefFaceList::iterator f2, TCorefFaceList::iterator l2)
63  : first1(f1), last1(l1), first2(f2), last2(l2) {}
64  TCorefFaceList::iterator first1, last1, first2, last2;
65 };
66 
67 //******************************************************************************
68 
69 CCorefine3dFF::CCorefine3dFF(CGMapVertex * AMap, bool ACalculateOrientation,
70  TCoordinate AEpsilon, int AVertexDI)
71  : CCorefine(AMap, AEpsilon), FCalculateOrientation(ACalculateOrientation),
72  FOptimizeSearch(true), FGridResolution(64), FDisplayMessages(2)
73 {
74  FTools = new CCorefine3dTools(FMap, AEpsilon);
75  CBoundingBox::setEpsilon(AEpsilon);
76 
77  if (AVertexDI < 0) {
78  FLocalVertexDI = true;
79  FVertexDI = FMap->getNewDirectInfo();
80  }
81  else {
82  FLocalVertexDI = false;
83  FVertexDI = AVertexDI;
84  }
85  FMesh1 = FMesh2 = NULL;
86 }
87 
88 //******************************************************************************
89 
90 CCorefine3dFF::~CCorefine3dFF()
91 {
92  if (FLocalVertexDI)
93  FMap->freeDirectInfo(FVertexDI);
94  clear();
95  delete FTools;
96 }
97 
98 //******************************************************************************
99 
100 int CCorefine3dFF::corefine(CDart *& AMesh1, CDart *& AMesh2,
101  bitset<NB_MARKS> ACopyMarks)
102 {
103  CDart *meshes[2] = {AMesh1, AMesh2};
104 
105  splitMeshes(AMesh1, AMesh2, ACopyMarks);
106  mergeMeshes();
107  removeDoubleFaces(meshes, 2);
108 
109  AMesh1 = meshes[0];
110  AMesh2 = meshes[1];
111 
112  return FInterEdges.size() / 2;
113 }
114 
115 //******************************************************************************
116 
117 int CCorefine3dFF::corefine(int AMark1, int AMark2,
118  bitset<NB_MARKS> ACopyMarks)
119 {
120  splitMeshes(AMark1, AMark2, ACopyMarks);
121  mergeMeshes();
122  removeDoubleFaces();
123 
124  return FInterEdges.size() / 2;
125 }
126 
127 //******************************************************************************
128 
129 void CCorefine3dFF::splitMeshes(CDart * AMesh1, CDart * AMesh2,
130  bitset<NB_MARKS> ACopyMarks)
131 {
132  DEBUG_FUNCTION;
133 
134  CTime start, end;
135 
136  FInterPointDI = FMap->getNewDirectInfo();
137  FLinkedVertexDI = FMap->getNewDirectInfo();
138  FFictiveVertexMark = FMap->getNewMark();
139  FFictiveEdgeMark = FMap->getNewMark();
140 
141  clear();
142 
143  if (FDisplayMessages) cout << "Initialisation des maillages" << endl;
144  start.updateTime();
145  CBoundingBox box1 = initMesh(AMesh1);
146  CBoundingBox box2 = initMesh(AMesh2);
147  end.updateTime();
148  FInitialisationTime = end - start;
149  if (FDisplayMessages) cout << "Durée de l'initialisation : "
150  << FInitialisationTime << endl;
151 
152  if (FCalculateOrientation) {
153  if (FDisplayMessages) cout << "Orientation des maillages" << endl;
154  start.updateTime();
155  AMesh1 = FTools->findWellOrientedDart(AMesh1, FVertexDI);
156  AMesh2 = FTools->findWellOrientedDart(AMesh2, FVertexDI);
157  end.updateTime();
158  if (FDisplayMessages) cout << "Durée de l'orientation : "
159  << end - start << endl;
160  }
161 
162  if (FDisplayMessages) cout << "Construction des listes de faces" << endl;
163  start.updateTime();
164  FMesh1 = buildFaceList(AMesh1);
165  FMesh2 = buildFaceList(AMesh2);
166  end.updateTime();
167  FFaceListCreationTime = end - start;
168  if (FDisplayMessages) cout << "Durée de la construction des listes : "
169  << FFaceListCreationTime << endl;
170  if (FDisplayMessages)
171  cout << "Le premier objet possède " << FMesh1->size()
172  << (FMesh1->size() > 1 ? " faces" : " face") << endl
173  << "Le second objet possède " << FMesh2->size()
174  << (FMesh2->size() > 1 ? " faces" : " face")<< endl;
175 
176  if (FOptimizeSearch) {
177  if (FDisplayMessages) cout << "Réduction de la taille des listes" << endl;
178  start.updateTime();
179  reduceFaceLists(FMesh1, FMesh2, box1 + box2);
180  end.updateTime();
181  FFaceListReductionTime = end - start;
182  if (FDisplayMessages) cout << "Durée de la réduction : "
183  << FFaceListReductionTime << endl;
184  }
185 
186  splitMeshes(ACopyMarks);
187 
188  if (FDisplayMessages) cout << "Nettoyage des maillages" << endl;
189  start.updateTime();
190  cleanMesh(AMesh1);
191  cleanMesh(AMesh2);
192  end.updateTime();
193  if (FDisplayMessages) cout << "Durée du nettoyage : " << end - start << endl;
194 
195  FMap->freeDirectInfo(FInterPointDI);
196  FMap->freeDirectInfo(FLinkedVertexDI);
197  freeMark(FFictiveVertexMark);
198  freeMark(FFictiveEdgeMark);
199 }
200 
201 //******************************************************************************
202 
203 void CCorefine3dFF::splitMeshes(int AMark1, int AMark2,
204  bitset<NB_MARKS> ACopyMarks)
205 {
206  DEBUG_FUNCTION;
207 
208  CTime start, end;
209 
210  FInterPointDI = FMap->getNewDirectInfo();
211  FLinkedVertexDI = FMap->getNewDirectInfo();
212  FFictiveVertexMark = FMap->getNewMark();
213  FFictiveEdgeMark = FMap->getNewMark();
214 
215  clear();
216 
217  if (FDisplayMessages) cout << "Initialisation des faces" << endl;
218  start.updateTime();
219  CBoundingBox box1 = initFaces(AMark1);
220  CBoundingBox box2 = initFaces(AMark2);
221  end.updateTime();
222  if (FDisplayMessages) cout << "Durée de l'initialisation : "
223  << end - start << endl;
224 
225  if (FDisplayMessages) cout << "Construction des listes de faces" << endl;
226  start.updateTime();
227  FMesh1 = buildFaceList(AMark1);
228  FMesh2 = buildFaceList(AMark2);
229  end.updateTime();
230  if (FDisplayMessages) cout << "Durée de la construction des listes : "
231  << end - start << endl;
232  if (FDisplayMessages)
233  cout << "Le premier objet possède " << FMesh1->size()
234  << (FMesh1->size() > 1 ? " faces" : " face") << endl
235  << "Le second objet possède " << FMesh2->size()
236  << (FMesh2->size() > 1 ? " faces" : " face")<< endl;
237 
238  if (FOptimizeSearch) {
239  if (FDisplayMessages) cout << "Réduction de la taille des listes" << endl;
240  start.updateTime();
241  reduceFaceLists(FMesh1, FMesh2, box1 + box2);
242  end.updateTime();
243  if (FDisplayMessages) cout << "Durée de la réduction : "
244  << end - start << endl;
245  }
246 
247  splitMeshes(ACopyMarks);
248 
249  if (FDisplayMessages) cout << "Nettoyage des faces" << endl;
250  start.updateTime();
251  for (CDynamicCoverageAll dca(FMap); dca.cont(); ++dca) {
252  FMap->unsetMark(*dca, FFictiveVertexMark);
253  FMap->unsetMark(*dca, FFictiveEdgeMark);
254  }
255  end.updateTime();
256  if (FDisplayMessages) cout << "Durée du nettoyage : " << end - start << endl;
257 
258  FMap->freeDirectInfo(FInterPointDI);
259  FMap->freeDirectInfo(FLinkedVertexDI);
260  freeMark(FFictiveVertexMark);
261  freeMark(FFictiveEdgeMark);
262 }
263 
264 //******************************************************************************
265 
266 void CCorefine3dFF::mergeMeshes()
267 {
268  if (!FInterEdges.empty()) {
269  CTime start, end;
270 
271  if (FDisplayMessages) cout << "Mise à jour de le topologie" << endl;
272  start.updateTime();
273 
274  int face_plane_di = FMap->getNewDirectInfo();
275  int negative_mark = FMap->getNewMark();
276 
277  for (CDynamicCoverageAll dca(FMap); dca.cont(); ++dca)
278  FMap->setDirectInfo(*dca, face_plane_di, NULL);
279 
280  assignFacesPlaneInfo(face_plane_di, negative_mark, FMesh1);
281  assignFacesPlaneInfo(face_plane_di, negative_mark, FMesh2);
282 
283  sortFacesAroundEdges(face_plane_di, negative_mark);
284 
285  removeFacesPlaneInfo(face_plane_di, negative_mark, FMesh1);
286  removeFacesPlaneInfo(face_plane_di, negative_mark, FMesh2);
287 
288  FMap->freeDirectInfo(face_plane_di);
289  freeMark(negative_mark);
290 
291  end.updateTime();
292  FMergeTime = end - start;
293  if (FDisplayMessages) cout << "Durée de la mise à jour : "
294  << FMergeTime << endl;
295  }
296 }
297 
298 //******************************************************************************
299 
300 void CCorefine3dFF::removeDoubleFaces(CDart **ADarts, int ANbDarts)
301 {
302  DEBUG_FUNCTION;
303 
304  if (!FDoubleFaces.empty()) {
305  int mark = FMap->getNewMark();
306  int i;
307  CTime start, end;
308 
309  if (FDisplayMessages) cout << "Suppression des faces doubles" << endl;
310  start.updateTime();
311 
312  markDoubleFaces(mark);
313 
314  for (i = 0; i < ANbDarts; ++i)
315  if (FMap->isMarked(ADarts[i], mark)) {
316  CDart *d = ADarts[i];
317  do d = a3(FTools->alpha2(d));
318  while (d != ADarts[i] && FMap->isMarked(d, mark));
319  ADarts[i] = (d == ADarts[i] ? NULL : d);
320  }
321 
322  TCorefFaceList::iterator fit, tmp_fit;
323  TCorefFaceList *face_list[2] = {FMesh1, FMesh2};
324  for (i = 0; i < 2; ++i)
325  for (fit = face_list[i]->begin(); fit != face_list[i]->end(); ) {
326  tmp_fit = fit++;
327  if (FMap->isMarked(tmp_fit->face, mark))
328  face_list[i]->erase(tmp_fit);
329  }
330 
331  list<CDart*>::iterator it;
332  for (it = FInterEdges.begin(); it != FInterEdges.end(); ++it)
333  if (FMap->isMarked(*it, mark))
334  *it = NULL;
335 
336  while (!FDoubleFaces.empty()) {
337  removeDoubleFace(FDoubleFaces.front());
338  FDoubleFaces.pop_front();
339  }
340 
341  freeMark(mark);
342 
343  end.updateTime();
344  if (FDisplayMessages) cout << "Durée de la suppression : "
345  << end - start << endl;
346  }
347 }
348 
349 //******************************************************************************
350 
351 // void CCorefine3dFF::linkCompounds(CDart * AMesh1, CDart * AMesh2,
352 // std::bitset<NB_MARKS> ACopyMarks)
353 // {
354 // DEBUG_FUNCTION;
355 
356 // if (FInterEdges.empty()) {
357 // CDart *d[2] = {AMesh1, AMesh2};
358 // CVertex line = *VTX(d[1]) - *VTX(d[0]);
359 
360 // if (FTools->isVectorNull(line)) {
361 // d[0] = a1(a0(d[0]));
362 // line = *VTX(d[1]) - *VTX(d[0]);
363 // assert(!FTools->isVectorNull(line));
364 // }
365 
366 // CEdgeIntersection inter[2];
367 // int mark = FMap->getNewMark();
368 // CVertex normal;
369 
370 // MSG("Recherche d'une arête sur le premier objet");
371 // for (int i = 0; i < 2; ++i) {
372 // inter[i] = FTools->findNearestIntersectionInOrbit(*VTX(d[(i+1)%2]),
373 // -line, d[i],
374 // ORBIT_CC, FVertexDI);
375 // assert(inter[i].getCell());
376 // d[i] = NULL;
377 // switch (inter[i].getCellDimension()) {
378 // case 0:
379 // FMap->halfMarkOrbit(inter[i].getCell(), ORBIT_VERTEX, mark);
380 // for (CDynamicCoverageVertex dcv(FMap, inter[i].getCell());
381 // dcv.cont(); ++dcv)
382 // if (FMap->isMarked(*dcv, mark)) {
383 // normal = ORIGIN;
384 // for (CDynamicCoverage12 cov(FMap, *dcv); cov.cont(); ++cov)
385 // if (FMap->isMarked(*cov, mark)) {
386 // FMap->unsetMark(*dcv, mark);
387 // normal += FTools->faceNormalVector(*cov, FVertexDI);
388 // }
389 // if (normal.dot(line) > 0.0)
390 // d[i] = *dcv;
391 // }
392 // break;
393 // case 1:
394 // FMap->halfMarkOrbit(inter[i].getCell(), ORBIT_EDGE, mark);
395 // for (CDynamicCoverageEdge dce(FMap, inter[i].getCell());
396 // dce.cont(); ++dce)
397 // if (FMap->isMarked(*dce, mark)) {
398 // FMap->unsetMark(*dce, mark);
399 // normal = FTools->faceNormalVector(*dce, FVertexDI);
400 // if (!FMap->isFree2(*dce)) {
401 // FMap->unsetMark(a0(a2(*dce)), mark);
402 // normal += FTools->faceNormalVector(a0(a2(*dce)), FVertexDI);
403 // }
404 // if (normal.dot(line) > 0.0)
405 // d[i] = *dce;
406 // }
407 // break;
408 // case 2:
409 // normal = FTools->faceNormalVector(inter[i].getCell(), FVertexDI);
410 // if (normal.dot(line) > 0.0)
411 // d[i] = inter[i].getCell();
412 // else {
413 // d[i] = a1(a3(inter[i].getCell()));
414 // assert(FTools->faceNormalVector(d[i], FVertexDI).dot(line) > 0.0);
415 // }
416 // }
417 // assert(d[i] != NULL);
418 // line = -line;
419 // }
420 
421 // assert(FMap->isWholeMapUnmarked(mark));
422 // freeMark(mark);
423 
424 // CDart *square = FMap->createTopoSquare();
425 // FMap->topoSew3(square, FMap->createTopoSquare());
426 // // FMap->topoSew2(a1(square), a3(a1(square)));
427 // // FMap->topoSew2(a1(a0(square)), a3(a1(a0(square))));
428 
429 // CDart *a2d[2] = {FTools->alpha2(d[0]), FTools->alpha2(d[1])};
430 
431 // for (int i = 0; i < 2; ++i) {
432 // if (!FMap->isFree2(d[i]))
433 // FMap->unsew2(d[i]);
434 // FMap->sew2(square, d[i]);
435 // FMap->sew2(a3(square), a2d[i]);
436 // square = a1(a0(a1(a0(square))));
437 // }
438 
439 // for (int m = 0; m < NB_MARKS; ++m)
440 // if (ACopyMarks[m])
441 // for (int i = 0; i < 2; ++i) {
442 // if (FMap->isMarked(d[i], m))
443 // FMap->markOrbit(a2(d[i]), ORBIT_01, m);
444 // if (FMap->isMarked(a2d[i], m))
445 // FMap->markOrbit(a2(a2d[i]), ORBIT_01, m);
446 // }
447 
448 // for (int i = 0; i < 2; ++i) {
449 // FMap->pointDirectInfoToAttributeVertex(FVertexDI, d[i]);
450 // FMap->pointDirectInfoToAttributeVertex(FVertexDI, a0(d[i]));
451 // }
452 // }
453 // }
454 
455 //******************************************************************************
456 
457 void CCorefine3dFF::linkCompounds(CDart * AMesh1, CDart * AMesh2,
458  std::bitset<NB_MARKS> ACopyMarks)
459 {
460  DEBUG_FUNCTION;
461 
462  if (FInterEdges.empty()) {
463  CDart *d1 = AMesh1, *d2 = AMesh2;
464  CVertex line = *VTX(d2) - *VTX(d1);
465 
466  if (line.getX() == 0.0 && line.getY() == 0.0 && line.getZ() == 0.0) {
467  d1 = a1(a0(d1));
468  line = *VTX(d2) - *VTX(d1);
469  }
470 
471  CPlane ref_plane(line, *VTX(d1));
472  TCoordinate dist, best_dist = 0.0;
473  CVertex normal;
474  int mark = FMap->getNewMark();
475 
476  MSG("Recherche d'un sommet de l'enveloppe convexe du premier objet");
477  FMap->halfMarkOrbit(d1, ORBIT_CC, mark);
478  FMap->unmarkOrbit(d1, ORBIT_VERTEX, mark);
479  for (CDynamicCoverageCC dcc(FMap, d1); dcc.cont(); ++dcc)
480  if (FMap->isMarked(*dcc, mark)) {
481  FMap->unmarkOrbit(*dcc, ORBIT_VERTEX, mark);
482  dist = ref_plane.pointDistance(*VTX(*dcc));
483  if (dist > best_dist) {
484  d1 = *dcc;
485  best_dist = dist;
486  }
487  }
488 
489  MSG("Calcul d'un nouveau vecteur directeur");
490  line = *VTX(d2) - *VTX(d1);
491  if (line.getX() == 0.0 && line.getY() == 0.0 && line.getZ() == 0.0) {
492  d2 = a1(a0(d2));
493  line = *VTX(d2) - *VTX(d1);
494  }
495 
496  MSG("Recherche d'une arête de l'enveloppe convexe du premier objet");
497  ref_plane.setPlane(line, *VTX(d1));
498  best_dist = -FLT_MAX;
499  FMap->halfMarkOrbit(d1, ORBIT_VERTEX, mark);
500  for (CDynamicCoverageVertex dcv(FMap, d1); dcv.cont(); ++dcv)
501  if (FMap->isMarked(*dcv, mark)) {
502  FMap->unsetMark(*dcv, mark);
503  normal = FTools->faceNormalVector(*dcv, FVertexDI);
504  if (!FMap->isFree2(*dcv))
505  normal += FTools->faceNormalVector(a0(a2(*dcv)), FVertexDI);
506  if (normal.dot(line) > 0.0) {
507  dist = ref_plane.pointDistance(*VTX(a0(*dcv)));
508  if (dist > best_dist) {
509  d1 = *dcv;
510  best_dist = dist;
511  }
512  }
513  }
514 
515  MSG("Recherche de la plus proche cellule du deuxième objet");
516  CEdgeIntersection inter;
517  inter = FTools->findNearestIntersectionInOrbit(*VTX(d1), line, d2,
518  ORBIT_CC, FVertexDI);
519  assert(inter.getCell());
520  d2 = inter.getCell();
521 
522  MSG("Recherche d'une arête de l'enveloppe convexe du deuxième objet");
523  TOrbit cell_orbit = ORBIT_VERTEX;
524  switch (inter.getCellDimension()) {
525  case 1: cell_orbit = ORBIT_EDGE;
526  case 2: cell_orbit = ORBIT_FACE;
527  }
528  ref_plane.setPlane(-line, *VTX(d2));
529  best_dist = -FLT_MAX;
530  FMap->halfMarkOrbit(d2, cell_orbit, mark);
531  CCoverage *cov = FMap->getDynamicCoverage(d2, cell_orbit);
532  for (; cov->cont(); ++(*cov))
533  if (FMap->isMarked(**cov, mark)) {
534  FMap->unsetMark(**cov, mark);
535  normal = FTools->faceNormalVector(**cov, FVertexDI);
536  if (!FMap->isFree2(**cov))
537  normal += FTools->faceNormalVector(a0(a2(**cov)), FVertexDI);
538  if (normal.dot(-line) > 0.0) {
539  dist = ref_plane.pointDistance(*VTX(a0(**cov)));
540  if (dist > best_dist) {
541  d2 = **cov;
542  best_dist = dist;
543  }
544  }
545  }
546  delete cov;
547 
548  if ((*VTX(a0(d1)) - *VTX(d1)).dot(*VTX(a0(d2)) - *VTX(d2)) > 0.0)
549  d2 = FTools->alpha2(a0(d2));
550 
551  freeMark(mark);
552 
553  CDart *square = FMap->createTopoSquare();
554  FMap->topoSew3(square, FMap->createTopoSquare());
555 // FMap->topoSew2(a1(square), a3(a1(square)));
556 // FMap->topoSew2(a1(a0(square)), a3(a1(a0(square))));
557 
558  CDart *a2d1 = FTools->alpha2(d1);
559  CDart *a2d2 = FTools->alpha2(d2);
560 
561  if (!FMap->isFree2(d1)) FMap->unsew2(d1);
562  if (!FMap->isFree2(d2)) FMap->unsew2(d2);
563 
564  FMap->sew2(square, d1);
565  FMap->sew2(a3(square), a2d1);
566  square = a3(a1(a0(a1(a0(square)))));
567  FMap->sew2(square, d2);
568  FMap->sew2(a3(square), a2d2);
569 
570  for (int m = 0; m < NB_MARKS; ++m)
571  if (ACopyMarks[m]) {
572  if (FMap->isMarked(d1, m)) FMap->markOrbit(a2(d1), ORBIT_01, m);
573  if (FMap->isMarked(a2d1, m)) FMap->markOrbit(a2(a2d1), ORBIT_01, m);
574  if (FMap->isMarked(d2, m)) FMap->markOrbit(a2(d2), ORBIT_01, m);
575  if (FMap->isMarked(a2d2, m)) FMap->markOrbit(a2(a2d2), ORBIT_01, m);
576  }
577 
578  FMap->pointDirectInfoToAttributeVertex(FVertexDI, d1);
579  FMap->pointDirectInfoToAttributeVertex(FVertexDI, a0(d1));
580  FMap->pointDirectInfoToAttributeVertex(FVertexDI, d2);
581  FMap->pointDirectInfoToAttributeVertex(FVertexDI, a0(d2));
582  }
583 }
584 
585 //******************************************************************************
586 
587 void CCorefine3dFF::markIntersectionEdges(int AMark, int AObjectsToMark)
588 {
589  CDart *edge1, *edge2;
590  for (list<CDart*>::iterator it = FInterEdges.begin();
591  it != FInterEdges.end(); ) {
592  edge1 = *it++;
593  edge2 = *it++;
594  if (AObjectsToMark & 1 && edge1 && !FMap->isMarked(edge1, AMark))
595  FMap->markOrbit(edge1, ORBIT_EDGE, AMark);
596  if (AObjectsToMark & 2 && edge2 && !FMap->isMarked(edge2, AMark))
597  FMap->markOrbit(edge2, ORBIT_EDGE, AMark);
598  }
599 }
600 
601 //******************************************************************************
602 
603 void CCorefine3dFF::markDoubleFaces(int AMark)
604 {
605  for (list<CDart*>::iterator it = FDoubleFaces.begin();
606  it != FDoubleFaces.end(); ++it)
607  if (!FMap->isMarked(*it, AMark))
608  FMap->markOrbit(*it, ORBIT_FACE, AMark);
609 }
610 
611 //******************************************************************************
612 
613 void CCorefine3dFF::spreadMarksWithoutMerging(bitset<NB_MARKS> AMarks)
614 {
615  int face_plane_di = FMap->getNewDirectInfo();
616  int negative_mark = FMap->getNewMark();
617  CDart *edge1, *edge2;
618  TFaceSet *face_set;
619 
620  assignFacesPlaneInfo(face_plane_di, negative_mark, FMesh1);
621  assignFacesPlaneInfo(face_plane_di, negative_mark, FMesh2);
622 
623  for (list<CDart*>::iterator it = FInterEdges.begin();
624  it != FInterEdges.end(); ) {
625  edge1 = *it++;
626  edge2 = *it++;
627  if (edge1 && edge2) {
628  face_set = sortFacesAroundEdges(edge1, edge2,
629  face_plane_di, negative_mark);
630  spreadMarksAroundEdges(face_set, AMarks);
631  delete face_set;
632  }
633  }
634 
635  removeFacesPlaneInfo(face_plane_di, negative_mark, FMesh1);
636  removeFacesPlaneInfo(face_plane_di, negative_mark, FMesh2);
637 
638  FMap->freeDirectInfo(face_plane_di);
639  freeMark(negative_mark);
640 }
641 
642 //******************************************************************************
643 
644 void CCorefine3dFF::clear()
645 {
646  if (FMesh1) delete FMesh1;
647  if (FMesh2) delete FMesh2;
648  FInterEdges.clear();
649 }
650 
651 //******************************************************************************
652 
653 void CCorefine3dFF::splitMeshes(bitset<NB_MARKS> ACopyMarks)
654 {
655  CTime start, end;
656 
657  FInterEdgeMark = FMap->getNewMark();
658  FFaceMark = FMap->getNewMark();
659  FDoubleFaceMark = FMap->getNewMark();
660  FCopyMarks = ACopyMarks;
661  FCopyMarks[FFaceMark] = true;
662 
663  list<SFaceListIterators> inter_list;
664  SFaceListIterators iters, next_iters;
665  TCorefFaceList::iterator it1, it2;
666  list<CDart*> face_list1, face_list2;
667  bool found;
668 
669  inter_list.push_back(SFaceListIterators(FMesh1->begin(), FMesh1->end(),
670  FMesh2->begin(), FMesh2->end()));
671 
672  if (FDisplayMessages) {
673  cout << "Création des intersections..." << endl;
674  if (FDisplayMessages > 2)
675  cout << "+ intersection franche" << endl
676  << "# faces coplanaires" << endl;
677  }
678  start.updateTime();
679  while (!inter_list.empty()) {
680  iters = inter_list.front();
681  inter_list.pop_front();
682 
683 // found = false;
684 // for (it1 = iters.first1; it1 != iters.last1 && !found; ++it1) {
685 // for (it2 = iters.first2; it2 != iters.last2 && !found; ++it2) {
686 // if (it1->box * it2->box && intersectFaces(it1->face, it2->face,
687 // it1->plane, it2->plane,
688 // &face_list1, &face_list2)) {
689 // next_iters.first1 = it1;
690 // next_iters.last1 = it1; ++next_iters.last1;
691 // next_iters.first2 = it2; ++next_iters.first2;
692 // next_iters.last2 = iters.last2;
693 // if (next_iters.first2 != next_iters.last2)
694 // inter_list.push_front(next_iters);
695 
696 // next_iters.first1 = next_iters.last1;
697 // next_iters.last1 = iters.last1;
698 // next_iters.first2 = iters.first2;
699 // next_iters.last2 = iters.last2;
700 // if (next_iters.first1 != next_iters.last1)
701 // inter_list.push_back(next_iters);
702 
703 // if (face_list1.size() > 1) updateFaceInList(FMesh1, it1, &face_list1);
704 // if (face_list2.size() > 1) updateFaceInList(FMesh2, it2, &face_list2);
705 // found = true;
706 // }
707 // }
708 // }
709 
710  for (it1 = iters.first1; it1 != iters.last1;) {
711  found = false;
712  for (it2 = iters.first2; it2 != iters.last2 && !found; ++it2) {
713  if (it1->box * it2->box && intersectFaces(it1->face, it2->face,
714  it1->plane, it2->plane,
715  &face_list1, &face_list2)) {
716  next_iters.first1 = it1;
717  next_iters.last1 = it1; ++next_iters.last1;
718  next_iters.first2 = it2; ++next_iters.first2;
719  next_iters.last2 = iters.last2;
720  if (face_list1.size() > 1) updateFaceInList(FMesh1, it1, &face_list1);
721  if (face_list2.size() > 1) updateFaceInList(FMesh2, it2, &face_list2);
722  if (next_iters.first2 != next_iters.last2)
723  inter_list.push_back(next_iters);
724  found = true;
725  it1 = next_iters.last1;
726  }
727  }
728  if (!found) ++it1;
729  }
730  }
731  end.updateTime();
732  FSplitTime = end - start;
733  if (FDisplayMessages) {
734  if (FDisplayMessages > 1) cout << endl;
735  cout << "Durée de la création des intersections : "
736  << FSplitTime << endl;
737  }
738 
739  FCopyMarks[FFaceMark] = false;
740  freeMark(FFaceMark);
741 
742  if (FDisplayMessages)
743  cout << "Il y a eu " << FInterEdges.size() / 2
744  << (FInterEdges.size() / 2 > 1 ? " arêtes" : " arête")
745  << " d'intersection" << endl;
746 
747  list<CDart*>::iterator it;
748  for (it = FInterEdges.begin(); it != FInterEdges.end(); ++it)
749  FMap->unmarkOrbit(*it, ORBIT_EDGE, FInterEdgeMark);
750  freeMark(FInterEdgeMark);
751 
752  for (it = FDoubleFaces.begin(); it != FDoubleFaces.end(); ++it)
753  FMap->unmarkOrbit(*it, ORBIT_FACE, FDoubleFaceMark);
754  freeMark(FDoubleFaceMark);
755 }
756 
757 //******************************************************************************
758 
759 bool CCorefine3dFF::checkEdges()
760 {
761  int mark = FMap->getNewMark();
762  bool result = true;
763 
764  for (CDynamicCoverageAll dca(FMap); dca.cont(); ++dca)
765  if (!FMap->isMarked(*dca, mark)) {
766  FMap->markOrbit(*dca, ORBIT_EDGE, mark);
767  if (FTools->arePointsEqual(*VTX(*dca), *VTX(a0(*dca)))) {
768  cout << "Arête de longueur nulle trouvée : [" << *VTX(*dca)
769  << ", " << *VTX(a0(*dca)) << "]" << endl;
770  result = false;
771  }
772  }
773  FMap->negateMaskMark(mark);
774  freeMark(mark);
775 
776  return result;
777 }
778 
779 //******************************************************************************
780 
781 void CCorefine3dFF::pointDirectInfoToData(int ADirectInfo, CDart * ADart,
782  TOrbit AOrbit, void * AData)
783 {
784  CCoverage *cov = FMap->getDynamicCoverage(ADart, AOrbit);
785  for (; cov->cont(); ++(*cov))
786  FMap->setDirectInfo(**cov, ADirectInfo, AData);
787  delete cov;
788 }
789 
790 //******************************************************************************
791 
792 CBoundingBox CCorefine3dFF::initMesh(CDart * AMesh)
793 {
794  DEBUG_FUNCTION;
795 
796  MSG("Fermeture des 3-bords");
797  for (CStaticCoverageCC scc(FMap, AMesh); scc.cont(); ++scc)
798  if (FMap->isFree3(*scc))
799  FMap->stopUp(*scc, 3);
800 
801  CBoundingBox box;
802  int mark = FMap->getNewMark();
803  CDynamicCoverageCC dcc(FMap, AMesh);
804  CAttributeVertex *vtx;
805 
806  MSG("Mise à jour des champs FVertexDI");
807 // if (FLocalVertexDI) {
808  for (; dcc.cont(); ++dcc)
809  if (!FMap->isMarked(*dcc, mark)) {
810  vtx = FMap->findVertex(*dcc);
811  assert(vtx != NULL);
812  box.addPoint(*vtx);
813  for (CDynamicCoverageVertex dcv(FMap, *dcc); dcv.cont(); ++dcv) {
814  FMap->setMark(*dcv, mark);
815  FMap->setDirectInfo(*dcv, FVertexDI, vtx);
816  }
817  }
818 // }
819 // else {
820 // for (; dcc.cont(); ++dcc)
821 // if (!FMap->isMarked(*dcc, mark)) {
822 // vtx = FMap->findVertex(*dcc);
823 // box.addPoint(*vtx);
824 // FMap->markOrbit(*dcc, ORBIT_VERTEX, mark);
825 // }
826 // }
827 
828  MSG("Initialisation des champs FInterPointDI et FLinkedVertexDI");
829  for (dcc.reinit(); dcc.cont(); ++dcc) {
830  FMap->unsetMark(*dcc, mark);
831  FMap->setDirectInfo(*dcc, FInterPointDI, NULL);
832  FMap->setDirectInfo(*dcc, FLinkedVertexDI, NULL);
833  }
834 
835  freeMark(mark);
836 
837  return box;
838 }
839 
840 //******************************************************************************
841 
842 CBoundingBox CCorefine3dFF::initFaces(int AMark)
843 {
844  DEBUG_FUNCTION;
845 
846  CDynamicCoverageAll dca(FMap);
847 
848  MSG("Fermeture des 3-bords");
849  for (; dca.cont(); ++dca)
850  if (FMap->isMarked(*dca, AMark) && FMap->isFree3(*dca))
851  FMap->stopUp(*dca, 3);
852 
853  CBoundingBox box;
854  int mark = FMap->getNewMark();
855  CAttributeVertex *vtx;
856 
857  FMap->markCopy(AMark, mark);
858  FMap->markIncidentCells(ORBIT_FACE, mark);
859  FMap->markIncidentCells(ORBIT_VERTEX, mark);
860  FMap->markIncidentCells(ORBIT_FACE, mark);
861 
862  MSG("Mise à jour des champs FVertexDI, FInterPointDI et FLinkedVertexDI");
863  for (dca.reinit(); dca.cont(); ++dca)
864  if (FMap->isMarked(*dca, mark)) {
865  vtx = FMap->findVertex(*dca);
866  assert(vtx != NULL);
867  box.addPoint(*vtx);
868  for (CDynamicCoverageVertex dcv(FMap, *dca); dcv.cont(); ++dcv) {
869  FMap->unsetMark(*dcv, mark);
870  FMap->setDirectInfo(*dcv, FVertexDI, vtx);
871  FMap->setDirectInfo(*dcv, FInterPointDI, NULL);
872  FMap->setDirectInfo(*dcv, FLinkedVertexDI, NULL);
873  }
874  }
875 
876  freeMark(mark);
877 
878  return box;
879 }
880 
881 //******************************************************************************
882 
883 void CCorefine3dFF::cleanMesh(CDart * AMesh)
884 {
885  DEBUG_FUNCTION;
886 
887  for (CDynamicCoverageCC dcc(FMap, AMesh); dcc.cont(); ++dcc) {
888  FMap->unsetMark(*dcc, FFictiveVertexMark);
889  FMap->unsetMark(*dcc, FFictiveEdgeMark);
890  }
891 }
892 
893 //******************************************************************************
894 
895 // void CCorefine3dFF::cleanMesh(CDart * AMesh)
896 // {
897 // DEBUG_FUNCTION;
898 
899 // int delete_mark = FMap->getNewMark();
900 // int nb;
901 // CCoverage *cov = FMap->getStaticCoverage(AMesh, ORBIT_CC);
902 
903 // // Suppression des arêtes fictives
904 // nb = 0;
905 // for (; cov->cont(); ++(*cov))
906 // if (FMap->isMarked(**cov, FFictiveEdgeMark)) {
907 // if (!FMap->isSameOrbit(**cov, a2(**cov), ORBIT_01)) {
908 // ++nb;
909 // removeFictiveEdge(**cov, delete_mark);
910 // }
911 // FMap->unmarkOrbit(**cov, ORBIT_EDGE, FFictiveEdgeMark);
912 // }
913 // if (nb && FDisplayMessages)
914 // cout << "Suppression de " << nb << " arête(s) fictive(s)" << endl;
915 
916 // // Suppression des sommets fictifs
917 // nb = 0;
918 // for (cov->reinit(); cov->cont(); ++(*cov))
919 // if (FMap->isMarked(**cov, FFictiveVertexMark)) {
920 // if (!isFictiveVertexUsed(**cov)) {
921 // ++nb;
922 // removeFictiveVertex(**cov, delete_mark);
923 // }
924 // FMap->unmarkOrbit(**cov, ORBIT_VERTEX, FFictiveVertexMark);
925 // }
926 // if (nb && FDisplayMessages)
927 // cout << "Suppression de " << nb << " sommet(s) fictif(s)" << endl;
928 
929 // delete cov;
930 // FMap->deleteMarkedDarts(delete_mark);
931 // freeMark(delete_mark);
932 // }
933 
934 //******************************************************************************
935 
936 SCorefFace CCorefine3dFF::computeFaceInfos(CDart * AFace, int AMark)
937 {
938  SCorefFace infos;
939  CVertex *vtx, pt, center, normal(0.0, 0.0, 0.0);
940  int nb = 2;
941  CDart *d;
942 
943  infos.face = AFace;
944 
945 // d = AFace; FMap->unsetMark(d, AMark);
946 // d = a3(AFace); FMap->unsetMark(a0(d), AMark);
947 // d = a1(d); FMap->unsetMark(d, AMark);
948 // d = a3(a0(d)); FMap->unsetMark(d, AMark);
949 
950  d = AFace; FMap->unsetMark(d, AMark);
951  d = a0(d); FMap->unsetMark(d, AMark);
952  d = a3(d); FMap->unsetMark(d, AMark);
953  d = a0(d); FMap->unsetMark(d, AMark);
954  d = a1(d); FMap->unsetMark(d, AMark);
955  d = a3(d); FMap->unsetMark(d, AMark);
956  d = a0(d); FMap->unsetMark(d, AMark);
957  d = a3(d); FMap->unsetMark(d, AMark);
958 
959  pt = *VTX(AFace);
960  infos.box.addPoint(pt);
961  infos.box.addPoint(*VTX(d));
962  center = pt;
963  center += *VTX(d);
964 
965  for (CDynamicCoverage01 cov(FMap, AFace); cov.cont(); ++cov)
966  if (FMap->isMarked(*cov, AMark)) {
967  vtx = VTX(*cov);
968  d = *cov; FMap->unsetMark(d, AMark);
969  d = a3(d); FMap->unsetMark(d, AMark);
970  d = a0(d); FMap->unsetMark(d, AMark);
971  d = a3(d); FMap->unsetMark(d, AMark);
972  normal += (*vtx - pt) * (*VTX(d) - pt);
973  center += *vtx;
974  infos.box.addPoint(*vtx);
975  ++nb;
976  }
977 
978  infos.plane.setPlane(normal, center / nb);
979 
980  return infos;
981 }
982 
983 //******************************************************************************
984 
985 TCorefFaceList * CCorefine3dFF::buildFaceList(CDart * AMesh)
986 {
987  DEBUG_FUNCTION;
988 
989  TCorefFaceList *faces = new TCorefFaceList;
990 
991  int mark = FMap->getNewMark();
992  FMap->halfMarkOrbit(AMesh, ORBIT_CC, mark);
993  for (CDynamicCoverageCC dcc(FMap, AMesh); dcc.cont(); ++dcc)
994  if (FMap->isMarked(*dcc, mark))
995  faces->push_back(computeFaceInfos(*dcc, mark));
996  freeMark(mark);
997 
998  return faces;
999 }
1000 
1001 //******************************************************************************
1002 
1003 TCorefFaceList * CCorefine3dFF::buildFaceList(int AMark)
1004 {
1005  DEBUG_FUNCTION;
1006 
1007  TCorefFaceList *faces = new TCorefFaceList;
1008 
1009  int mark = FMap->getNewMark();
1010  FMap->markCopy(AMark, mark);
1011  FMap->halfMarkIncidentCells(ORBIT_FACE, mark);
1012  for (CDynamicCoverageAll dca(FMap); dca.cont(); ++dca)
1013  if (FMap->isMarked(*dca, mark))
1014  faces->push_back(computeFaceInfos(*dca, mark));
1015  freeMark(mark);
1016 
1017  return faces;
1018 }
1019 
1020 //******************************************************************************
1021 
1022 void CCorefine3dFF::reduceFaceLists(TCorefFaceList * AList1,
1023  TCorefFaceList * AList2,
1024  const CBoundingBox & ABox)
1025 {
1026  CVertex size;
1027  TCoordinate max;
1028  long size_i, size_j, size_k;
1029  long nb_faces = (AList1->size() > AList2->size() ?
1030  AList1->size() : AList2->size());
1031 
1032  if (nb_faces < 50) {
1033  if (FDisplayMessages)
1034  cout << "Nombre de faces trop faible => aucune réduction !" << endl;
1035  return;
1036  }
1037 
1038  // Calcul de la résolution de la grille
1039  size = ABox.getEpsMaxBound() - ABox.getEpsMinBound();
1040  max = (size.getX() > size.getY() ?
1041  (size.getX() > size.getZ() ? size.getX() : size.getZ()) :
1042  (size.getY() > size.getZ() ? size.getY() : size.getZ()));
1043  size /= max;
1044 
1045 // double grid_res = pow((double)nb_faces /
1046 // (double)(ANbFacesPerCell *
1047 // size.getX() * size.getY() * size.getZ()),
1048 // 1.0/3.0);
1049 
1050  size_i = (int)(size.getX() * FGridResolution + 0.5);
1051  size_j = (int)(size.getY() * FGridResolution + 0.5);
1052  size_k = (int)(size.getZ() * FGridResolution + 0.5);
1053  if (size_i <= 0) size_i = 1;
1054  if (size_j <= 0) size_j = 1;
1055  if (size_k <= 0) size_k = 1;
1056 
1057  if (FDisplayMessages)
1058  cout << "Résolution de la grille = "
1059  << size_i << "x" << size_j << "x" << size_k << endl;
1060 
1061  TCorefFaceGrid grid(size_i, size_j, size_k, ABox);
1062  TCorefFaceList::iterator it, tmp_it;
1063  list<CDart*>::iterator li;
1064  int mark = FMap->getNewMark();
1065  int nb;
1066 
1067  for (it = AList1->begin(); it != AList1->end(); ++it)
1068  for (TCorefFaceGridIter gi(grid, it->box); gi.cont(); ++gi)
1069  gi->first.push_back(it->face);
1070  for (it = AList2->begin(); it != AList2->end(); ++it)
1071  for (TCorefFaceGridIter gi(grid, it->box); gi.cont(); ++gi)
1072  gi->second.push_back(it->face);
1073 
1074  for (TCorefFaceGridIter gi(grid); gi.cont(); ++gi) {
1075  if (gi->first.size() > 0 && gi->second.size() > 0) {
1076  for (li = gi->first.begin(); li != gi->first.end(); ++li)
1077  FMap->setMark(*li, mark);
1078  for (li = gi->second.begin(); li != gi->second.end(); ++li)
1079  FMap->setMark(*li, mark);
1080  }
1081  }
1082 
1083  nb = 0;
1084  for (it = AList1->begin(); it != AList1->end(); ) {
1085  tmp_it = it++;
1086  if (FMap->isMarked(tmp_it->face, mark))
1087  FMap->unsetMark(tmp_it->face, mark);
1088  else {
1089  ++nb;
1090  AList1->erase(tmp_it);
1091  }
1092  }
1093  if (FDisplayMessages)
1094  cout << nb << (nb == 1 ?
1095  " face a été supprimée" :
1096  " faces ont été supprimées")
1097  << " de la première liste" << endl;
1098 
1099  nb = 0;
1100  for (it = AList2->begin(); it != AList2->end(); ) {
1101  tmp_it = it++;
1102  if (FMap->isMarked(tmp_it->face, mark))
1103  FMap->unsetMark(tmp_it->face, mark);
1104  else {
1105  ++nb;
1106  AList2->erase(tmp_it);
1107  }
1108  }
1109  if (FDisplayMessages)
1110  cout << nb << (nb == 1 ?
1111  " face a été supprimée" :
1112  " faces ont été supprimées")
1113  << " de la seconde liste" << endl;
1114 
1115  freeMark(mark);
1116 }
1117 
1118 //******************************************************************************
1119 
1120 void CCorefine3dFF::updateFaceInList(TCorefFaceList * AList,
1121  TCorefFaceList::iterator AElt,
1122  list<CDart*> * AFaces)
1123 {
1124  DEBUG_FUNCTION;
1125 
1126  TCorefFaceList::iterator pos = AElt;
1127  list<CDart*>::iterator it = AFaces->begin();
1128 
1129  MSG("La face à été éclatée en " << AFaces->size() << " faces");
1130 
1131  *AElt = SCorefFace(*it, AElt->plane,
1132  FTools->orbitBoundingBox(*it, ORBIT_01, FVertexDI));
1133  ++pos; ++it;
1134 
1135  for (; it != AFaces->end(); ++it)
1136  AList->insert(pos, SCorefFace(*it, AElt->plane,
1137  FTools->orbitBoundingBox(*it, ORBIT_01,
1138  FVertexDI)));
1139 }
1140 
1141 //******************************************************************************
1142 
1143 bool CCorefine3dFF::isVertexLinkedWithFace(CDart * AVertex, int AFaceMark)
1144 {
1145  DEBUG_FUNCTION;
1146  if (LINK(AVertex) == NULL)
1147  return false;
1148 
1149  bool result = false;
1150  for (CDynamicCoverageVertex dcv(FMap, LINK(AVertex));
1151  dcv.cont() && !result; ++dcv)
1152  if (FMap->isMarked(*dcv, AFaceMark))
1153  result = true;
1154 
1155  return result;
1156 }
1157 
1158 //******************************************************************************
1159 
1160 void CCorefine3dFF::markFaceVertex(CDart * AVertex, int AFaceMark, int AMark)
1161 {
1162  for (CDynamicCoverageVertex dcv(FMap, AVertex); dcv.cont(); ++dcv)
1163  if (FMap->isMarked(*dcv, AFaceMark))
1164  FMap->setMark(*dcv, AMark);
1165 }
1166 
1167 //******************************************************************************
1168 
1169 CDart * CCorefine3dFF::getTwinDartOnFace(CDart * ADart, int AFaceMark)
1170 {
1171  CDart *d = NULL;
1172  for (CDynamicCoverage23 cov(FMap, ADart); cov.cont() && !d; ++cov)
1173  if (*cov != ADart && FMap->isMarked(*cov, AFaceMark)) d = *cov;
1174  return d;
1175 }
1176 
1177 //******************************************************************************
1178 
1179 CDart * CCorefine3dFF::findFaceSector(CDart * AFaceVertex,
1180  const CPlane & AFacePlane,
1181  int AFaceMark, const CVertex & AVector)
1182 {
1183  DEBUG_FUNCTION;
1184 
1185  int orient_mark = FMap->getNewMark();
1186  CDart *d = NULL;
1187  CVertex pt = *VTX(AFaceVertex);
1188 
1189  MSG("AVector = " << AVector);
1190  MSG("sommet testé : " << pt);
1191 
1192  FMap->halfMarkOrbit(AFaceVertex, ORBIT_VERTEX, orient_mark);
1193  for (CDynamicCoverageVertex dcv(FMap, AFaceVertex); dcv.cont(); ++dcv)
1194  if (FMap->isMarked(*dcv, orient_mark)) {
1195  FMap->unsetMark(*dcv, orient_mark);
1196  if (FMap->isMarked(*dcv, AFaceMark)) {
1197  if (a1(*dcv) == getTwinDartOnFace(*dcv, AFaceMark) ||
1198  FTools->isVectorInSector(AVector,
1199  *VTX(a0(*dcv)) - pt,
1200  *VTX(a0(a1(*dcv))) - pt,
1201  AFacePlane)) {
1202  assert(d == NULL);
1203  d = *dcv;
1204  MSG("secteur trouvé : " << *VTX(a0(*dcv))
1205  << ", " << *VTX(a0(a1(*dcv))));
1206  }
1207  }
1208  }
1209  freeMark(orient_mark);
1210 
1211  return d;
1212 }
1213 
1214 //******************************************************************************
1215 
1216 CDart * CCorefine3dFF::findNearestFaceVertex(CDart * AFace,
1217  const CPlane & ARefPlane,
1218  const CPlane & AClipPlane1,
1219  const CPlane & AClipPlane2)
1220 {
1221  CDart *d, *nearest = NULL;
1222  TCoordinate best_dist = 0, dist;
1223  CVertex pt;
1224 
1225  d = AFace;
1226  do {
1227  pt = *VTX(d);
1228 
1229  if (AClipPlane1.pointDistance(pt) >= -FEps &&
1230  AClipPlane2.pointDistance(pt) >= -FEps) {
1231  dist = abs(ARefPlane.pointDistance(pt));
1232  if (!nearest || dist < best_dist) {
1233  nearest = d;
1234  best_dist = dist;
1235  }
1236  }
1237 
1238  d = a1(a0(d));
1239  }
1240  while (d != AFace);
1241 
1242  return nearest;
1243 }
1244 
1245 //******************************************************************************
1246 
1247 CVertex CCorefine3dFF::edgeInsideVector(CDart * AEdge,
1248  const CPlane & AFacePlane)
1249 {
1250  return AFacePlane.getNormal() * (*VTX(a0(AEdge)) - *VTX(AEdge));
1251 }
1252 
1253 //******************************************************************************
1254 
1255 CVertex CCorefine3dFF::vertexInsideVector(CDart * AVertex,
1256  const CPlane & AFacePlane)
1257 {
1258  return (edgeInsideVector(AVertex, AFacePlane) +
1259  edgeInsideVector(a0(a1(AVertex)), AFacePlane)) / 2.0;
1260 }
1261 
1262 //******************************************************************************
1263 
1264 void CCorefine3dFF::classifyFaceVertices(CDart * AFace, const CPlane & APlane,
1265  int APositiveMark, int ANegativeMark,
1266  int AFacesMark, bool AUseVerticesLinks,
1267  int * ANbVertices,
1268  int * ANbPositiveVertices,
1269  int * ANbNegativeVertices)
1270 {
1271  CDart *d = AFace;
1272  TCoordinate dist;
1273  int treated_mark = FMap->getNewMark();
1274  int nb = 0, nb_pos = 0, nb_neg = 0;
1275 
1276  MSG("Classement des sommets de AFace par rapport à APlane");
1277  do {
1278  if (!FMap->isMarked(d, treated_mark)) {
1279  markFaceVertex(d, AFacesMark, treated_mark);
1280  ++nb;
1281  if (!AUseVerticesLinks || !isVertexLinkedWithFace(d, AFacesMark)) {
1282  dist = APlane.pointDistance(*VTX(d));
1283  if (dist < -FEps) { // Le point est au dessous du plan
1284  markFaceVertex(d, AFacesMark, ANegativeMark);
1285  ++nb_neg;
1286  }
1287  else if (dist > FEps) { // Le point est au dessus du plan
1288  markFaceVertex(d, AFacesMark, APositiveMark);
1289  ++nb_pos;
1290  }
1291  }
1292  }
1293 
1294  d = a1(a0(d));
1295  }
1296  while (d != AFace);
1297 
1298  MSG("Démarquage des brins de la face");
1299  do {
1300  FMap->unsetMark(d, treated_mark);
1301  d = a0(d);
1302  FMap->unsetMark(d, treated_mark);
1303  d = a1(d);
1304  }
1305  while (d != AFace);
1306 
1307  freeMark(treated_mark);
1308 
1309  MSG("La face comporte " << nb << " sommets dont :");
1310  MSG(" " << nb_pos << " du côté positif");
1311  MSG(" " << nb_neg << " du côté negatif");
1312 
1313  if (ANbVertices) *ANbVertices = nb;
1314  if (ANbPositiveVertices) *ANbPositiveVertices = nb_pos;
1315  if (ANbNegativeVertices) *ANbNegativeVertices = nb_neg;
1316 }
1317 
1318 //******************************************************************************
1319 
1320 void CCorefine3dFF::getFaceFictiveElements(CDart * AFace, int AFaceMark,
1321  std::list<CDart*> * AFictVertices,
1322  std::list<CDart*> * AFictEdges)
1323 {
1324  int fict_mark = FMap->getNewMark();
1325  CDart *d = AFace;
1326 
1327  // Récupération des sommets fictifs
1328  do {
1329  if (!FMap->isMarked(d, fict_mark) &&
1330  !FMap->isMarked(d, FFictiveEdgeMark)) {
1331  markFaceVertex(d, AFaceMark, fict_mark);
1332  if (FMap->isMarked(d, FFictiveVertexMark)) {
1333  MSG("Récupération du sommet fictif " << *VTX(d));
1334  AFictVertices->push_back(d);
1335  }
1336  }
1337  d = a1(a0(d));
1338  }
1339  while (d != AFace);
1340 
1341  // Récupération des arêtes fictives
1342  do {
1343  if (FMap->isMarked(d, fict_mark)) {
1344  FMap->unmarkOrbit(d, ORBIT_EDGE, fict_mark);
1345  if (FMap->isMarked(d, FFictiveEdgeMark))
1346  AFictEdges->push_back(d);
1347  }
1348  d = a1(a0(d));
1349  }
1350  while (d != AFace);
1351 
1352  freeMark(fict_mark);
1353 }
1354 
1355 //******************************************************************************
1356 
1357 void CCorefine3dFF::testPointInside(CDart * AVertex, TInterPt * APoint,
1358  int AFaceMark,
1359  const CVertex & AInterLine,
1360  const CPlane & AFacePlane)
1361 {
1362  MSG("sector = " << *VTX(a0(a1(AVertex))) << ","
1363  << *VTX(AVertex) << "," << *VTX(a0(AVertex)));
1364  if (APoint->getPosition() == FP_Outside &&
1365 // APoint->getPosition() != FP_OnBorder &&
1366 // APoint->getPosition() != FP_OnReversedBorder &&
1367  (a1(AVertex) == getTwinDartOnFace(AVertex, AFaceMark) ||
1368  FTools->isVectorInSector(AInterLine,
1369  *VTX(a0(AVertex)) - *VTX(AVertex),
1370  *VTX(a0(a1(AVertex))) - *VTX(AVertex),
1371  AFacePlane))) {
1372  MSG("On entre dans la face");
1373  APoint->setPosition(FP_Inside);
1374  APoint->setEnteringSector(AVertex);
1375  }
1376  if (FTools->isVectorInSector(-AInterLine,
1377  *VTX(a0(AVertex)) - *VTX(AVertex),
1378  *VTX(a0(a1(AVertex))) - *VTX(AVertex),
1379  AFacePlane)) {
1380  MSG("On sort de la face");
1381  APoint->setLeavingSector(AVertex);
1382  }
1383 }
1384 
1385 //******************************************************************************
1386 
1387 void CCorefine3dFF::testPointBorder(CDart * AVertex,
1388  TInterPt * ANewPoint, TInterPt * AOldPoint,
1389  const TInterPtCmp & AComparator)
1390 {
1391  if (AOldPoint) {
1392  MSG("Il y a une intersetion avec le bord");
1393  if (AComparator(AOldPoint, ANewPoint)) {
1394  MSG("AOldPoint < ANewPoint ==> OnBorder");
1395  AOldPoint->setPosition(FP_OnBorder);
1396  AOldPoint->setEnteringSector(a0(a1(AVertex)));
1397  if (!AOldPoint->getLeavingSector())
1398  AOldPoint->setLeavingSector(AOldPoint->getEnteringSector());
1399  }
1400  else {
1401  MSG("ANewPoint < AOldPoint ==> OnReversedBorder");
1402  ANewPoint->setPosition(FP_OnReversedBorder);
1403  ANewPoint->setEnteringSector(a0(a1(AVertex)));
1404  if (!ANewPoint->getLeavingSector())
1405  ANewPoint->setLeavingSector(AVertex);
1406  }
1407  }
1408 }
1409 
1410 //******************************************************************************
1411 #define GET_IP(d) ((TInterPt*)FMap->getDirectInfo(d, FInterPointDI))
1412 
1413 TInterPtSet *
1414 CCorefine3dFF::findIntersectionPoints(CDart * AFace,
1415  const CPlane & AFacePlane,
1416  const CPlane & AInterPlane,
1417  const CVertex & AInterLine,
1418  int APositiveMark, int ANegativeMark,
1419  int AFacesMark,
1420  const TInterPtCmp & AComparator)
1421 {
1422  DEBUG_FUNCTION;
1423 
1424  TInterPtSet *inter_set;
1425  TInterPt *inter_point, *old_point;
1426  CAttributeVertex *vtx1, *vtx2, pt;
1427  CVertex dir;
1428  TCoordinate t;
1429  CDart *d, *d2;
1430 
1431  inter_set = new TInterPtSet(AComparator);
1432 
1433  MSG("normale au plan : " << AFacePlane.getNormal());
1434 
1435  // Traitement du dernier sommet pour gérer le cas d'intersection avec le bord
1436  // entre le dernier et le premier sommet
1437  inter_point = NULL;
1438  d = a0(a1(AFace));
1439  if (!FMap->isMarked(d, APositiveMark) && !FMap->isMarked(d, ANegativeMark)) {
1440  inter_point = new TInterPt(*VTX(d), 0);
1441  inter_point->setLeavingSector(d);
1442  pointDirectInfoToData(FInterPointDI, d, ORBIT_VERTEX, inter_point);
1443  MSG("première intersection avec le sommet " << inter_point->getPoint());
1444  inter_set->insert(inter_point);
1445  testPointInside(d, inter_point, AFacesMark, AInterLine, AFacePlane);
1446  }
1447 
1448  MSG("Recherche des sommets de AFace se trouvant sur AInterPlane");
1449  d = AFace;
1450  do {
1451  old_point = inter_point;
1452  inter_point = GET_IP(d);
1453 
1454  // Si le point d'intersection existe déjà, on le met à jour si besoin
1455  if (inter_point) {
1456  MSG("intersection déjà existante avec un sommet");
1457  MSG(inter_point->getPoint());
1458  testPointInside(d, inter_point, AFacesMark, AInterLine, AFacePlane);
1459  testPointBorder(d, inter_point, old_point, AComparator);
1460  }
1461  else {
1462  if (!FMap->isMarked(d, APositiveMark) &&
1463  !FMap->isMarked(d, ANegativeMark)) {
1464  inter_point = new TInterPt(*VTX(d), 0);
1465  inter_point->setLeavingSector(d);
1466  pointDirectInfoToData(FInterPointDI, d, ORBIT_VERTEX, inter_point);
1467  MSG("nouvelle intersection avec un sommet");
1468  MSG(inter_point->getPoint());
1469  inter_set->insert(inter_point);
1470  testPointInside(d, inter_point, AFacesMark, AInterLine, AFacePlane);
1471  testPointBorder(d, inter_point, old_point, AComparator);
1472  }
1473  }
1474 
1475  d = a1(a0(d));
1476  }
1477  while (d != AFace);
1478 
1479  MSG("Recherche des arêtes de AFace intersectant AInterPlane");
1480  do {
1481  // Effacement des pointeurs sur les points d'intersections
1482  if (GET_IP(d)) pointDirectInfoToData(FInterPointDI, d, ORBIT_VERTEX, NULL);
1483 
1484  if ( (FMap->isMarked(d, APositiveMark) &&
1485  FMap->isMarked(a0(d), ANegativeMark)) ||
1486  (FMap->isMarked(d, ANegativeMark) &&
1487  FMap->isMarked(a0(d), APositiveMark))) {
1488  vtx1 = VTX(d);
1489  vtx2 = VTX(a0(d));
1490  dir = *vtx2 - *vtx1;
1491 
1492  MSG("dir = " << dir);
1493 
1494  if (AInterPlane.getLineIntersection(*vtx1, dir, &t)) {
1495  assert(t >= 0.0 && t <= 1.0);
1496 
1497  pt = *vtx1 + t * dir;
1498  inter_point = new TInterPt(pt, 1);
1499  inter_set->insert(inter_point);
1500  MSG("intersection avec l'arête [" << *vtx1 << "," << *vtx2 << "] en "
1501  << pt);
1502 
1503  if ((AFacePlane.getNormal() * dir).dot(AInterLine) > 0.0) {
1504  inter_point->setPosition(FP_Inside);
1505  inter_point->setEnteringSector(d);
1506  }
1507  else {
1508  inter_point->setPosition(FP_Outside);
1509  inter_point->setLeavingSector(d);
1510  }
1511 
1512  // On regarde si l'arête courante est une arête pendante
1513  if (!FMap->isFree2(d) || !FMap->isFree2(a3(d))) {
1514  d2 = NULL;
1515  for (CDynamicCoverage23 cov(FMap, d); cov.cont() && !d2; ++cov)
1516  if (*cov != d && FMap->isMarked(*cov, AFacesMark)) d2 = *cov;
1517  if (d2) {
1518  d2 = a0(d2);
1519  // Comme c'est une arête pendante, on reste forcément dans la face
1520  if (inter_point->getPosition() == FP_Outside) {
1521  inter_point->setPosition(FP_Inside);
1522  inter_point->setEnteringSector(d2);
1523  }
1524  else {
1525  inter_point->setLeavingSector(d2);
1526  }
1527  }
1528  }
1529 
1530  MSG("pos = " << inter_point->getPosition());
1531  }
1532  }
1533 
1534  // Démarquage de l'arête
1535  for (CDynamicCoverageEdge dce(FMap, d); dce.cont(); ++dce) {
1536  FMap->unsetMark(*dce, APositiveMark);
1537  FMap->unsetMark(*dce, ANegativeMark);
1538  }
1539 
1540  d = a1(a0(d));
1541  }
1542  while (d != AFace);
1543 
1544  return inter_set;
1545 }
1546 
1547 //******************************************************************************
1548 
1549 CDart * CCorefine3dFF::createEdge()
1550 {
1551  CDart *d[8];
1552 
1553  for (int i=0; i<8; ++i) {
1554  d[i] = FMap->addMapDart();
1555  FMap->setDirectInfo(d[i], FInterPointDI, NULL);
1556  FMap->setDirectInfo(d[i], FLinkedVertexDI, NULL);
1557  }
1558 
1559  FMap->linkAlpha0(d[0], d[1]);
1560  FMap->linkAlpha0(d[2], d[3]);
1561  FMap->linkAlpha0(d[4], d[5]);
1562  FMap->linkAlpha0(d[6], d[7]);
1563 
1564  FMap->linkAlpha2(d[0], d[2]);
1565  FMap->linkAlpha2(d[1], d[3]);
1566  FMap->linkAlpha2(d[4], d[6]);
1567  FMap->linkAlpha2(d[5], d[7]);
1568 
1569  FMap->linkAlpha3(d[0], d[4]);
1570  FMap->linkAlpha3(d[1], d[5]);
1571  FMap->linkAlpha3(d[2], d[6]);
1572  FMap->linkAlpha3(d[3], d[7]);
1573 
1574  return d[0];
1575 }
1576 
1577 //******************************************************************************
1578 
1579 CDart * CCorefine3dFF::insertVertexInFace(CDart * AFace, const CVertex & APoint)
1580 {
1581  DEBUG_FUNCTION;
1582 
1583  CDart *vertex = a1(a0(insertEdgeInFace(AFace, APoint)));
1584  FMap->markOrbit(vertex, ORBIT_EDGE, FFictiveEdgeMark);
1585 
1586  return vertex;
1587 }
1588 
1589 //******************************************************************************
1590 
1591 CDart * CCorefine3dFF::insertEdgeInFace(CDart * AVertex1,
1592  const CVertex & AVertex2)
1593 {
1594  DEBUG_FUNCTION;
1595 
1596  CDart *link = LINK(AVertex1);
1597  CDart *edge = createEdge();
1598 
1599  CDart *old_a1 = a1(AVertex1);
1600  FMap->unsew1(AVertex1);
1601  FMap->sew1(AVertex1, a2(edge));
1602  FMap->sew1(old_a1, edge);
1603  FMap->sew1(a0(edge), a0(a2(edge)));
1604 
1605  if (FMap->isMarked(AVertex1, FFictiveVertexMark))
1606  FMap->markOrbit(edge, ORBIT_23, FFictiveVertexMark);
1607 
1608  for (CDynamicCoverage23 dc(FMap, edge); dc.cont(); ++dc) {
1609  FMap->setDirectInfo(*dc, FLinkedVertexDI, link);
1610  for (int m = 0; m < NB_MARKS; m++)
1611  if (FCopyMarks[m] && FMap->isMarked(a1(*dc), m)) {
1612  FMap->setMark(*dc, m);
1613  FMap->setMark(a0(*dc), m);
1614  }
1615  }
1616  FMap->pointDirectInfoToAttributeVertex(FVertexDI, AVertex1);
1617 
1618  CAttributeVertex *vtx = new CAttributeVertex(AVertex2);
1619  FMap->setVertex(a0(edge), vtx);
1620 
1621  for (CDynamicCoverageVertex dcv(FMap, a0(edge)); dcv.cont(); ++dcv) {
1622  FMap->setDirectInfo(*dcv, FVertexDI, vtx);
1623  FMap->setDirectInfo(*dcv, FLinkedVertexDI, NULL);
1624  }
1625 
1626  MSG("arête insérée : [" << *VTX(AVertex1) << ";" << AVertex2 << "]");
1627 
1628  return edge;
1629 }
1630 
1631 //******************************************************************************
1632 
1633 CDart * CCorefine3dFF::splitEdge(CDart * AEdge, const CVertex & APoint,
1634  list<CDart*> * AFictiveEdges)
1635 {
1636  DEBUG_FUNCTION;
1637 
1638  FMap->CGMapGeneric::insertVertex(AEdge);
1639 
1640  CDart *d = a1(a0(AEdge));
1641 
1642  if (FMap->isMarked(AEdge, FFictiveEdgeMark)) {
1643  FMap->markOrbit(d, ORBIT_VERTEX, FFictiveEdgeMark);
1644 // FMap->markOrbit(d, ORBIT_VERTEX, FFictiveVertexMark);
1645 
1646  if (AFictiveEdges) {
1647  CDart *edge = a2(a3(AEdge));
1648  bool found = false;
1649  for (list<CDart*>::iterator it = AFictiveEdges->begin();
1650  it != AFictiveEdges->end() && !found; ++it)
1651  if (*it == AEdge || *it == edge)
1652  found = true;
1653  AFictiveEdges->push_back(found ? d : AEdge);
1654  }
1655  }
1656 
1657  CAttributeVertex *vtx = new CAttributeVertex(APoint);
1658  FMap->setVertex(d, vtx);
1659 
1660  for (CDynamicCoverageVertex dcv(FMap, d); dcv.cont(); ++dcv) {
1661  FMap->setDirectInfo(*dcv, FInterPointDI, NULL);
1662  FMap->setDirectInfo(*dcv, FLinkedVertexDI, NULL);
1663  FMap->setDirectInfo(*dcv, FVertexDI, vtx);
1664  for (int m = 0; m < NB_MARKS; m++)
1665  if (FCopyMarks[m] && FMap->isMarked(a0(*dcv), m))
1666  FMap->setMark(*dcv, m);
1667  }
1668 
1669  MSG("sommet inséré : " << APoint);
1670 
1671  return d;
1672 }
1673 
1674 //******************************************************************************
1675 
1676 CDart * CCorefine3dFF::splitFace(CDart * AVertex1, CDart * AVertex2)
1677 {
1678  DEBUG_FUNCTION;
1679 
1680  assert(AVertex1 != AVertex2);
1681 
1682  CDart *edge = createEdge();
1683  CDart *link;
1684 
1685  CDart *old_a1[2] = {a1(AVertex1), a1(AVertex2)};
1686  FMap->unsew1(AVertex1);
1687  FMap->sew1(AVertex1, a2(edge));
1688  FMap->sew1(old_a1[0], edge);
1689  FMap->unsew1(AVertex2);
1690  FMap->sew1(AVertex2, a0(edge));
1691  FMap->sew1(old_a1[1], a2(a0(edge)));
1692 
1693  if (FMap->isMarked(AVertex1, FFictiveVertexMark))
1694  FMap->markOrbit(edge, ORBIT_23, FFictiveVertexMark);
1695  if (FMap->isMarked(AVertex2, FFictiveVertexMark))
1696  FMap->markOrbit(a0(edge), ORBIT_23, FFictiveVertexMark);
1697 
1698  link = LINK(AVertex1);
1699  for (CDynamicCoverage23 dc1(FMap, edge); dc1.cont(); ++dc1) {
1700  FMap->setDirectInfo(*dc1, FLinkedVertexDI, link);
1701  for (int m = 0; m < NB_MARKS; m++)
1702  if (FCopyMarks[m] && FMap->isMarked(a1(*dc1), m))
1703  FMap->setMark(*dc1, m);
1704  }
1705  FMap->pointDirectInfoToAttributeVertex(FVertexDI, AVertex1);
1706 
1707  link = LINK(AVertex2);
1708  for (CDynamicCoverage23 dc2(FMap, a0(edge)); dc2.cont(); ++dc2) {
1709  FMap->setDirectInfo(*dc2, FLinkedVertexDI, link);
1710  for (int m = 0; m < NB_MARKS; m++)
1711  if (FCopyMarks[m] && FMap->isMarked(a1(*dc2), m))
1712  FMap->setMark(*dc2, m);
1713  }
1714  FMap->pointDirectInfoToAttributeVertex(FVertexDI, AVertex2);
1715 
1716  MSG("arête insérée : [" << *VTX(AVertex1) << ";" << *VTX(AVertex2) << "]");
1717 
1718  return edge;
1719 }
1720 
1721 //******************************************************************************
1722 
1723 bool CCorefine3dFF::isUselessFictiveVertex(CDart * AVertex)
1724 {
1725  bool result = true;
1726 
1727  for (CDynamicCoverageVertex dcv(FMap, AVertex); dcv.cont() && result; ++dcv)
1728  if (FMap->isMarked(*dcv, FFictiveEdgeMark))
1729  result = false;
1730 
1731  return result;
1732 }
1733 
1734 //******************************************************************************
1735 
1736 bool CCorefine3dFF::isUselessFictiveEdge(CDart * AEdge)
1737 {
1738  return (a1(AEdge) == a2(AEdge) || a1(a0(AEdge)) == a2(a0(AEdge)) ||
1739  !FMap->isSameOrbit(AEdge, a2(AEdge), ORBIT_01));
1740 }
1741 
1742 //******************************************************************************
1743 
1744 bool CCorefine3dFF::isWholeFaceMarked(CDart * AFace, int AMark)
1745 {
1746  bool result = true;
1747  for (CDynamicCoverageFace dcf(FMap, AFace); dcf.cont() && result; ++dcf)
1748  if (!FMap->isMarked(*dcf, AMark))
1749  result = false;
1750  return result;
1751 }
1752 
1753 //******************************************************************************
1754 
1755 CDart * CCorefine3dFF::copyDoubleFaceData(CDart * AFace)
1756 {
1757  DEBUG_FUNCTION;
1758 
1759  int edge_mark = FMap->getNewMark();
1760  CDart *d1, *d2, *other;
1761  int m;
1762 
1763  MSG("Marquage des arêtes de la face");
1764  d1 = AFace;
1765  do {
1766  FMap->markOrbit(d1, ORBIT_EDGE, edge_mark);
1767  d1 = a1(a0(d1));
1768  }
1769  while (d1 != AFace);
1770 
1771  MSG("Recherche de la face jumelle");
1772  if (isWholeFaceMarked(a2(AFace), edge_mark)) {
1773  other = a3(a2(AFace));
1774  }
1775  else {
1776  other = a2(a3(AFace));
1777  assert(isWholeFaceMarked(other, edge_mark));
1778  }
1779 // other = AFace;
1780 // do {
1781 // other = a3(a2(other));
1782 // }
1783 // while (!isWholeFaceMarked(other, edge_mark));
1784 // assert(other != AFace);
1785 
1786  MSG("Copie des marques se trouvant sur la face à supprimer");
1787  d2 = other;
1788  do {
1789  FMap->unmarkOrbit(d1, ORBIT_EDGE, edge_mark);
1790  for (m = 0; m < NB_MARKS; ++m) {
1791  if (FCopyMarks[m] && FMap->isMarked(d1, m))
1792  FMap->setMark(d2, m);
1793  if (FCopyMarks[m] && FMap->isMarked(a3(d1), m))
1794  FMap->setMark(a3(d2), m);
1795  }
1796  d1 = a0(d1);
1797  d2 = a0(d2);
1798  for (m = 0; m < NB_MARKS; ++m) {
1799  if (FCopyMarks[m] && FMap->isMarked(d1, m))
1800  FMap->setMark(d2, m);
1801  if (FCopyMarks[m] && FMap->isMarked(a3(d1), m))
1802  FMap->setMark(a3(d2), m);
1803  }
1804  d1 = a1(d1);
1805  d2 = a1(d2);
1806  }
1807  while (d1 != AFace);
1808  assert(d2 == other);
1809 
1810  freeMark(edge_mark);
1811 
1812  return other;
1813 }
1814 
1815 //******************************************************************************
1816 
1817 CDart * CCorefine3dFF::removeFictiveVertex(CDart * AVertex, int ADeleteMark)
1818 {
1819  DEBUG_FUNCTION;
1820 
1821  assert(FMap->isMarked(AVertex, FFictiveVertexMark));
1822  assert(LINK(AVertex) == NULL);
1823 
1824  CDart *d = a0(AVertex);
1825 
1826  if (ADeleteMark < 0)
1827  FMap->merge(AVertex, a1(AVertex), 1, true);
1828  else {
1829  FMap->markOrbit(AVertex, ORBIT_VERTEX, ADeleteMark);
1830  FMap->merge(AVertex, a1(AVertex), 1, false);
1831  }
1832 
1833  return d;
1834 }
1835 
1836 //******************************************************************************
1837 
1838 CDart * CCorefine3dFF::removeFictiveEdge(CDart * AEdge, int ADeleteMark)
1839 {
1840  DEBUG_FUNCTION;
1841 
1842  assert(FMap->isMarked(AEdge, FFictiveEdgeMark));
1843  assert(!FMap->isFree2(AEdge));
1844  assert(a3(a2(AEdge)) == a2(a3(AEdge)));
1845 
1846  CDart *d1 = a1(AEdge);
1847  CDart *d2 = a1(a0(AEdge));
1848  CDart *l1, *l2;
1849 
1850  if (a2(AEdge) == d1) d1 = NULL;
1851  if (a2(a0(AEdge)) == d2) d2 = NULL;
1852 
1853  l2 = LINK(AEdge);
1854  if (l2) {
1855  l1 = LINK(l2);
1856  if (AEdge == l1 || a3(a2(AEdge)) == l1 ||
1857  a2(AEdge) == l1 || a3(AEdge) == l1) {
1858  MSG("Déplacement des liens sur le premier sommet");
1859  pointDirectInfoToData(FLinkedVertexDI, l2, ORBIT_VERTEX, a1(a3(AEdge)));
1860  }
1861  }
1862  l2 = LINK(a0(AEdge));
1863  if (l2) {
1864  l1 = LINK(l2);
1865  if (a2(a0(AEdge)) == l1 || a3(a0(AEdge)) == l1 ||
1866  a0(AEdge) == l1 || a3(a2(a0(AEdge))) == l1) {
1867  MSG("Déplacement des liens sur le second sommet");
1868  pointDirectInfoToData(FLinkedVertexDI, l2, ORBIT_VERTEX, a1(a0(AEdge)));
1869  }
1870  }
1871 
1872  MSG("Démarquage des sommets de l'arête");
1873  if (FMap->isMarked(AEdge, FFictiveVertexMark))
1874  FMap->unmarkOrbit(AEdge, ORBIT_23, FFictiveVertexMark);
1875  if (FMap->isMarked(a0(AEdge), FFictiveVertexMark))
1876  FMap->unmarkOrbit(a0(AEdge), ORBIT_23, FFictiveVertexMark);
1877 
1878  MSG("Suppression de l'arête");
1879  if (ADeleteMark < 0)
1880  FMap->merge(AEdge, a2(AEdge), 2, true);
1881  else {
1882  FMap->markOrbit(AEdge, ORBIT_EDGE, ADeleteMark);
1883  FMap->merge(AEdge, a2(AEdge), 2, false);
1884  }
1885 
1886  MSG("Mise à jour des champs FVertexDI");
1887  if (d1) FMap->pointDirectInfoToAttributeVertex(FVertexDI, d1);
1888  if (d2) FMap->pointDirectInfoToAttributeVertex(FVertexDI, d2);
1889 
1890  return d1;
1891 }
1892 
1893 //******************************************************************************
1894 
1895 CDart * CCorefine3dFF::removeDoubleFace(CDart * AFace)
1896 {
1897  DEBUG_FUNCTION;
1898 
1899  CDart *other = copyDoubleFaceData(AFace);
1900 
1901  MSG("Suppression de la face en trop");
1902  FMap->merge(AFace, a3(AFace), 3, true);
1903 
1904  MSG("Mise à jour des champs FVertexDI");
1905  CDart *d = other;
1906  do {
1907  FMap->pointDirectInfoToAttributeVertex(FVertexDI, d);
1908  d = a1(a0(d));
1909  }
1910  while (d != other);
1911 
1912  return other;
1913 }
1914 
1915 //******************************************************************************
1916 
1917 void CCorefine3dFF::linkVertices(CDart * AVertex1, CDart * AVertex2)
1918 {
1919  DEBUG_FUNCTION;
1920  MSG("AVertex1 = " << *VTX(AVertex1));
1921  MSG("AVertex2 = " << *VTX(AVertex2));
1922  assert(FTools->arePointsEqual(*VTX(AVertex1), *VTX(AVertex2)));
1923  for (CDynamicCoverageVertex dcv1(FMap, AVertex1); dcv1.cont(); ++dcv1)
1924  FMap->setDirectInfo(*dcv1, FLinkedVertexDI, AVertex2);
1925  for (CDynamicCoverageVertex dcv2(FMap, AVertex2); dcv2.cont(); ++dcv2)
1926  FMap->setDirectInfo(*dcv2, FLinkedVertexDI, AVertex1);
1927 }
1928 
1929 //******************************************************************************
1930 
1931 void CCorefine3dFF::addIntersectionPoint(CDart *AVertices[2], int AFaceNumber,
1932  int AFacesMark, int AInterMark,
1933  std::list<CDart*> * AInterList)
1934 {
1935  MSG("Ajout du point d'intersection " << *VTX(AVertices[0]));
1936  if (FMap->isMarked(AVertices[0], FFictiveVertexMark))
1937  FMap->unmarkOrbit(AVertices[0], ORBIT_VERTEX, FFictiveVertexMark);
1938  if (FMap->isMarked(AVertices[1], FFictiveVertexMark))
1939  FMap->unmarkOrbit(AVertices[1], ORBIT_VERTEX, FFictiveVertexMark);
1940  linkVertices(AVertices[0], AVertices[1]);
1941  AInterList->push_back(AVertices[AFaceNumber]);
1942  markFaceVertex(AVertices[0], AFacesMark, AInterMark);
1943  markFaceVertex(AVertices[1], AFacesMark, AInterMark);
1944 }
1945 
1946 //******************************************************************************
1947 
1948 bool CCorefine3dFF::intersectFaces(CDart * AFace1, CDart * AFace2,
1949  const CPlane & APlane1,
1950  const CPlane & APlane2,
1951  list<CDart*> * AFaceList1,
1952  list<CDart*> * AFaceList2)
1953 {
1954  DEBUG_FUNCTION;
1955 
1956  list<CDart*> fict_vertices, fict_edges;
1957  list<CDart*>::iterator it, last_edge = FInterEdges.begin();
1958  int positive_mark = FMap->getNewMark();
1959  int negative_mark = FMap->getNewMark();
1960  int nb1, nb_pos1, nb_neg1, nb2, nb_pos2, nb_neg2;
1961  char inter_type = 0;
1962 
1963  FMap->markOrbit(AFace1, ORBIT_01, FFaceMark);
1964  FMap->markOrbit(AFace2, ORBIT_01, FFaceMark);
1965 
1966 #ifdef DEBUG_MESSAGES
1967  static int nb = 0;
1968  MSG("**** ETAPE N°" << nb << " ****");
1969 #ifdef SAVE_STEPS_SINCE
1970 #ifdef SAVE_STEPS_UNTIL
1971  if (nb >= SAVE_STEPS_SINCE && nb <= SAVE_STEPS_UNTIL) {
1972 #else
1973  if (nb >= SAVE_STEPS_SINCE) {
1974 #endif
1975 
1976  stringstream s;
1977  s<<"CCorefine3DFF_intersectFaces";
1978  s.width(4); s.fill(0); s.flags (ios::right);
1979  s<<nb;
1980  s.width(0);
1981  s<<".map";
1982 
1983  FMap->markCopy(FFictiveEdgeMark, 0);
1984  FMap->markCopy(FInterEdgeMark, 1);
1985  FMap->markCopy(FFaceMark, 2);
1986  FMap->save(s.str(), AsciiFormat);
1987  }
1988 #endif
1989  ++nb;
1990 #endif
1991 
1992  classifyFaceVertices(AFace1, APlane2, positive_mark, negative_mark,
1993  FFaceMark, true, &nb1, &nb_pos1, &nb_neg1);
1994  classifyFaceVertices(AFace2, APlane1, positive_mark, negative_mark,
1995  FFaceMark, true, &nb2, &nb_pos2, &nb_neg2);
1996 
1997  MSG("Récupération des sommets fictifs et des arêtes fictives sur les faces");
1998  getFaceFictiveElements(AFace1, FFaceMark, &fict_vertices, &fict_edges);
1999  getFaceFictiveElements(AFace2, FFaceMark, &fict_vertices, &fict_edges);
2000 
2001  if ((nb_pos1 == 0 && nb_neg1 == 0) || (nb_pos2 == 0 && nb_neg2 == 0)) {
2002  inter_type = '#';
2003  if (nb_pos1 > 0) FMap->unmarkOrbit(AFace1, ORBIT_01, positive_mark);
2004  if (nb_neg1 > 0) FMap->unmarkOrbit(AFace1, ORBIT_01, negative_mark);
2005  if (nb_pos2 > 0) FMap->unmarkOrbit(AFace2, ORBIT_01, positive_mark);
2006  if (nb_neg2 > 0) FMap->unmarkOrbit(AFace2, ORBIT_01, negative_mark);
2007  intersectCoplanarFaces(AFace1, AFace2, APlane1, APlane2,
2008  positive_mark, negative_mark, FFaceMark,
2009  &fict_vertices, &fict_edges);
2010  }
2011  else if (nb_pos1 < nb1 && nb_neg1 < nb1 && nb_pos2 < nb2 && nb_neg2 < nb2) {
2012  inter_type = '+';
2013  intersectSecantFaces(AFace1, AFace2, APlane1, APlane2,
2014  positive_mark, negative_mark, FFaceMark,
2015  &fict_vertices, &fict_edges);
2016  }
2017  else {
2018  for (CDynamicCoverage01 cov1(FMap, AFace1); cov1.cont(); ++cov1) {
2019  FMap->unsetMark(*cov1, positive_mark);
2020  FMap->unsetMark(*cov1, negative_mark);
2021  }
2022  for (CDynamicCoverage01 cov2(FMap, AFace2); cov2.cont(); ++cov2) {
2023  FMap->unsetMark(*cov2, positive_mark);
2024  FMap->unsetMark(*cov2, negative_mark);
2025  }
2026  }
2027 
2028  MSG("Suppression des arêtes fictives inutiles");
2029  for (it = fict_edges.begin(); it != fict_edges.end(); ++it)
2030  if (FMap->isMarked(*it, FFictiveEdgeMark) &&
2031  isUselessFictiveEdge(*it))
2032  removeFictiveEdge(*it);
2033 
2034  MSG("Suppression des sommets fictifs inutiles");
2035  for (it = fict_vertices.begin(); it != fict_vertices.end(); ++it)
2036  if (FMap->isMarked(*it, FFictiveVertexMark) &&
2037  isUselessFictiveVertex(*it))
2038  removeFictiveVertex(*it);
2039 
2040  MSG("Récupération des faces résultantes");
2041  assert(AFaceList1 != NULL);
2042  assert(AFaceList2 != NULL);
2043  AFaceList1->clear();
2044  AFaceList2->clear();
2045 
2046  bool result = last_edge != FInterEdges.begin();
2047 
2048  if (result) {
2049  if (FDisplayMessages > 1 && inter_type) {
2050  cout << inter_type;
2051  cout.flush();
2052  }
2053 
2054  list<CDart*> *face_list[2] = {AFaceList1, AFaceList2};
2055  CDart *edge;
2056  int i;
2057 
2058  for (it = FInterEdges.begin(); it != last_edge; ) {
2059  for (i = 0; i < 2; ++i) {
2060  edge = *it++;
2061  if (FMap->isMarked(edge, FFaceMark)) {
2062  FMap->unmarkOrbit(edge, ORBIT_01, FFaceMark);
2063  face_list[i]->push_back(edge);
2064  }
2065  if (FMap->isMarked(a2(edge), FFaceMark)) {
2066  FMap->unmarkOrbit(a2(edge), ORBIT_01, FFaceMark);
2067  face_list[i]->push_back(a0(a2(edge)));
2068  }
2069  }
2070  }
2071  }
2072  else {
2073  FMap->unmarkOrbit(AFace1, ORBIT_01, FFaceMark);
2074  FMap->unmarkOrbit(AFace2, ORBIT_01, FFaceMark);
2075  }
2076 
2077  freeMark(positive_mark);
2078  freeMark(negative_mark);
2079 
2080  return result;
2081 }
2082 
2083 //******************************************************************************
2084 
2085 void CCorefine3dFF::intersectSecantFaces(CDart * AFace1, CDart * AFace2,
2086  const CPlane & APlane1,
2087  const CPlane & APlane2,
2088  int APositiveMark, int ANegativeMark,
2089  int AFacesMark,
2090  list<CDart*> * /*AFictiveVertices*/,
2091  list<CDart*> * AFictiveEdges)
2092 {
2093  DEBUG_FUNCTION;
2094 
2095 // assert(!FMap->isSameOrbit(AFace1, AFace2, ORBIT_CC));
2096 
2097  CPlane plane[2] = {APlane1, APlane2};
2098  CVertex line;
2099 
2100  line = APlane1.getNormal() * APlane2.getNormal();
2101 
2102  MSG("line = " << line);
2103 
2104  assert(line.getX() != 0.0 || line.getY() != 0.0 || line.getZ() != 0.0);
2105 // if (FTools->isVectorNull(line))
2106 // cerr << "<CCorefine3dFF::intersectSecantFaces> "
2107 // << "Vecteur de coupe de longueur quasi-nulle : " << line << endl;
2108 
2109  // Calcul des points d'intersection sur chaque face
2110  TInterPtCmp comp(FTools, line);
2111  TInterPtSet *inter_set[2];
2112 
2113  MSG("Recherche des intersections sur la première face");
2114  inter_set[0] = findIntersectionPoints(AFace1, APlane1, APlane2, line,
2115  APositiveMark, ANegativeMark,
2116  AFacesMark, comp);
2117 
2118  MSG("Recherche des intersections sur la deuxième face");
2119  inter_set[1] = findIntersectionPoints(AFace2, APlane2, APlane1, line,
2120  APositiveMark, ANegativeMark,
2121  AFacesMark, comp);
2122 
2123  TInterPtSet::iterator it[2] = {inter_set[0]->begin(), inter_set[1]->begin()};
2124  TInterPt *ip[2];
2125  TPositionInFace pos[2], prev_pos[2];
2126  int prev_point, next_point;
2127  CDart *vtx[2], *edge[2], *last_vertex[2];
2128  int mark = FMap->getNewMark();
2129  int i;
2130 
2131  ip[0] = ip[1] = NULL;
2132  prev_pos[0] = prev_pos[1] = pos[0] = pos[1] = FP_Outside;
2133  prev_point = next_point = 0;
2134  last_vertex[0] = last_vertex[1] = NULL;
2135 
2136  // Parcours des ensembles et construction des segments d'intersection
2137  while (it[0] != inter_set[0]->end() && it[1] != inter_set[1]->end()) {
2138  // Les points se trouvent au même endroit sur les deux faces
2139  if (FTools->arePointsEqual((*it[0])->getPoint(), (*it[1])->getPoint()))
2140  next_point = 3;
2141  // Le point le plus proche se trouve sur la face 1
2142  else if (comp(*it[0], *it[1]))
2143  next_point = 1;
2144  // Le point le plus proche se trouve sur la face 2
2145  else
2146  next_point = 2;
2147 
2148  MSG("prev_point = " << prev_point);
2149  MSG("next_point = " << next_point);
2150  MSG("pos1 = " << pos[0]);
2151  MSG("pos2 = " << pos[1]);
2152 
2153  if (pos[0] != FP_Outside && pos[1] != FP_Outside) {
2154  for (i = 0; i < 2; ++i) {
2155  BEGIN("Création d'une arête d'intersection sur la face " << i);
2156  MSG("prev dim = " << ip[i]->getCellDim());
2157  MSG("prev point = " << ip[i]->getPoint());
2158  MSG("next dim = " << (*it[i])->getCellDim());
2159  MSG("next point = " << (*it[i])->getPoint());
2160 
2161  // On teste si la topologie est en cohérence avec la géométrie
2162  if (pos[i] == FP_OnBorder || pos[i] == FP_OnReversedBorder) {
2163  MSG("test d'erreur numérique");
2164  CDart *d;
2165  // vtx[0] = pointeur sur le premier sommet du segment courant
2166  // vtx[1] = pointeur sur le sommet d'intersection suivant
2167  // d = opposé (par a1 o a0) de vtx[0] sur le segment courant
2168  if (pos[i] == FP_OnBorder) {
2169  if (!(prev_point & (i+1)) && prev_pos[(i+1)%2] != FP_Outside) {
2170  assert(last_vertex[i] != NULL);
2171  vtx[0] = last_vertex[i];
2172  }
2173  else
2174  vtx[0] = ip[i]->getEnteringSector();
2175  d = a1(a0(vtx[0]));
2176  }
2177  else {
2178  d = ip[i]->getEnteringSector();
2179  vtx[0] = a1(a0(d));
2180  }
2181  vtx[1] = ((*it[i])->getPosition() == FP_Inside ?
2182  (*it[i])->getEnteringSector() :
2183  (*it[i])->getLeavingSector());
2184  markFaceVertex(vtx[1], AFacesMark, mark);
2185  MSG("vtx[0] = " << *VTX(vtx[0]));
2186  MSG("vtx[1] = " << *VTX(vtx[1]));
2187  // si d n'est pas marqué, c'est qu'il est différent de vtx[1] !!!
2188  if (!FMap->isMarked(d, mark)) {
2189  cerr << "Erreur numérique détectée : " << pos[i] << " ==> ";
2190  CDart *d_on = NULL;
2191  // Recherche d'un éventuel segment commun entre vtx[0] et vtx[1]
2192  markFaceVertex(vtx[0], AFacesMark, mark);
2193  d = vtx[0];
2194  do {
2195  if (FMap->isMarked(d, mark) && FMap->isMarked(a0(d), mark))
2196  d_on = d;
2197  FMap->unsetMark(d, mark);
2198  d = a0(d);
2199  FMap->unsetMark(d, mark);
2200  d = a1(d);
2201  }
2202  while (d != vtx[0]);
2203  if (d_on) {
2204  ip[i]->setEnteringSector(d_on);
2205  if ((*VTX(a0(d_on)) - *VTX(d_on)).dot(line) > 0.0)
2206  ip[i]->setPosition(FP_OnBorder);
2207  else
2208  ip[i]->setPosition(FP_OnReversedBorder);
2209  }
2210  else {
2211  // S'il n'y a pas de segment commun, on recherche le bon secteur
2212  CDart *d_in = findFaceSector(vtx[0], plane[i], AFacesMark, line);
2213  ip[i]->setEnteringSector(d_in);
2214  ip[i]->setPosition(d_in ? FP_Inside : FP_Outside);
2215  }
2216  pos[i] = ip[i]->getPosition();
2217  cerr << pos[i] << endl;
2218  }
2219  else {
2220  FMap->unmarkOrbit(vtx[0], ORBIT_VERTEX, mark);
2221  FMap->unmarkOrbit(vtx[1], ORBIT_VERTEX, mark);
2222  }
2223  }
2224 
2225  // On se trouve sur une arête orientée dans le même sens que la ligne
2226  if (pos[i] == FP_OnBorder) {
2227  vtx[0] = ip[i]->getEnteringSector();
2228  if (!(prev_point & (i+1))) {
2229  if (prev_pos[(i+1)%2] != FP_Outside) {
2230  assert(last_vertex[i] != NULL);
2231  vtx[0] = last_vertex[i];
2232  }
2233  else {
2234  vtx[0] = splitEdge(vtx[0], ip[(i+1)%2]->getPoint(),
2235  AFictiveEdges);
2236  ip[i]->setEnteringSector(vtx[0]);
2237  }
2238  }
2239  if (!(next_point & (i+1)))
2240  splitEdge(vtx[0], (*it[(i+1)%2])->getPoint(), AFictiveEdges);
2241  edge[i] = vtx[0];
2242  last_vertex[i] = vtx[1] = a1(a0(edge[i]));
2243  }
2244  // On se trouve sur une arête orientée dans le sens contraire
2245  else if (pos[i] == FP_OnReversedBorder) {
2246  last_vertex[i] = ip[i]->getEnteringSector();
2247  if (!(prev_point & (i+1))) {
2248  if (prev_pos[(i+1)%2] == FP_Outside)
2249  splitEdge(last_vertex[i], ip[(i+1)%2]->getPoint(), AFictiveEdges);
2250  }
2251  if (!(next_point & (i+1)))
2252  last_vertex[i] = splitEdge(last_vertex[i],
2253  (*it[(i+1)%2])->getPoint(),
2254  AFictiveEdges);
2255  vtx[0] = edge[i] = last_vertex[i];
2256  vtx[1] = a1(a0(edge[i]));
2257  }
2258  // On se trouve dans la face
2259  else {
2260  // Récupération du premier sommet
2261  if (prev_point & (i+1)) {
2262  MSG("Le premier sommet se trouve sur la face courante");
2263  if (ip[i]->getCellDim() == 0)
2264  vtx[0] = ip[i]->getEnteringSector();
2265  else
2266  vtx[0] = splitEdge(ip[i]->getEnteringSector(),
2267  ip[i]->getPoint(), AFictiveEdges);
2268  MSG("sommet trouvé : " << *VTX(vtx[0]));
2269  }
2270  else {
2271  MSG("Le premier sommet se trouve sur l'autre face");
2272  if (prev_pos[(i+1)%2] != FP_Outside) {
2273  assert(last_vertex[i] != NULL);
2274  vtx[0] = last_vertex[i];
2275  }
2276  else if (!(next_point & (i+1))) {
2277  if (!last_vertex[i]) {
2278  if (ip[i]->getCellDim() == 1) {
2279 // vtx[0] = splitEdge(ip[i]->getEnteringSector(),
2280 // ip[i]->getPoint(), AFictiveEdges);
2281 // FMap->markOrbit(vtx[0], ORBIT_VERTEX, FFictiveVertexMark);
2282 // AFictiveVertices->push_back(vtx[0]);
2283  vtx[0] = ip[i]->getEnteringSector();
2284  CPlane clip_plane1(edgeInsideVector(vtx[0], plane[i]),
2285  ip[i]->getPoint());
2286  CPlane clip_plane2(-line, ip[(i+1)%2]->getPoint());
2287  vtx[0] = findNearestFaceVertex(vtx[0], plane[(i+1)%2],
2288  clip_plane1, clip_plane2);
2289  vtx[0] = findFaceSector(vtx[0], plane[i], AFacesMark,
2290  ip[(i+1)%2]->getPoint() -
2291  *VTX(vtx[0]));
2292  assert(vtx[0]);
2293  }
2294  else
2295  vtx[0] = ip[i]->getEnteringSector();
2296  }
2297  else
2298  vtx[0] = last_vertex[i];
2299  vtx[0] = insertVertexInFace(vtx[0], ip[(i+1)%2]->getPoint());
2300  AFictiveEdges->push_back(vtx[0]);
2301  }
2302  else
2303  vtx[0] = NULL;
2304  }
2305 
2306  // Récupération du second sommet et création de l'arête
2307  if (next_point & (i+1)) {
2308  MSG("Le second sommet se trouve sur la face courante");
2309  MSG("next_point = " << (*it[i])->getPoint());
2310  if ((*it[i])->getCellDim() == 0)
2311  vtx[1] = ((*it[i])->getLeavingSector() ?
2312  (*it[i])->getLeavingSector() :
2313  (*it[i])->getEnteringSector());
2314  else
2315  vtx[1] = splitEdge((*it[i])->getLeavingSector(),
2316  (*it[i])->getPoint(), AFictiveEdges);
2317 
2318  if (vtx[0])
2319  edge[i] = splitFace(vtx[0], vtx[1]);
2320  else {
2321  edge[i] = a2(a0(insertEdgeInFace(vtx[1],
2322  ip[(i+1)%2]->getPoint())));
2323  vtx[0] = edge[i];
2324  }
2325 
2326  if ((*it[i])->getPosition() == FP_Inside) {
2327  if ((*it[i])->getCellDim() == 1) {
2328  (*it[i])->setCellDim(0);
2329  (*it[i])->setEnteringSector(a1(a0((*it[i])->getEnteringSector())));
2330  }
2331  else if (((*VTX(a0((*it[i])->getEnteringSector())) -
2332  *VTX((*it[i])->getEnteringSector()))
2333  * line).dot(plane[i].getNormal()) < 0.0)
2334  (*it[i])->setEnteringSector(a2(a0(edge[i])));
2335  }
2336  last_vertex[i] = NULL;
2337  }
2338  else {
2339  MSG("Le second sommet se trouve sur l'autre face");
2340  edge[i] = insertEdgeInFace(vtx[0], (*it[(i+1)%2])->getPoint());
2341  vtx[1] = last_vertex[i] = a1(a0(edge[i]));
2342  }
2343  }
2344  if (FMap->isMarked(vtx[0], FFictiveVertexMark))
2345  FMap->unmarkOrbit(vtx[0], ORBIT_VERTEX, FFictiveVertexMark);
2346  if (FMap->isMarked(vtx[1], FFictiveVertexMark))
2347  FMap->unmarkOrbit(vtx[1], ORBIT_VERTEX, FFictiveVertexMark);
2348  MSG("arête d'intersection trouvée : [" << *VTX(edge[i]) << ";"
2349  << *VTX(a0(edge[i])) << "]");
2350 
2351  END("");
2352  }
2353 
2354  if (!FMap->isMarked(edge[0], FInterEdgeMark) &&
2355  !FMap->isMarked(edge[1], FInterEdgeMark)) {
2356  MSG("Marquage et stockage des arêtes d'intersection");
2357  FInterEdges.push_front(edge[1]);
2358  FInterEdges.push_front(edge[0]);
2359 
2360 // if (!FMap->isMarked(edge[0], FInterEdgeMark))
2361  FMap->markOrbit(edge[0], ORBIT_EDGE, FInterEdgeMark);
2362 // else
2363 // cerr << "Topologie de l'objet 2 incorrecte !" << endl;
2364 // if (!FMap->isMarked(edge[1], FInterEdgeMark))
2365  FMap->markOrbit(edge[1], ORBIT_EDGE, FInterEdgeMark);
2366 // else
2367 // cerr << "Topologie de l'objet 1 incorrecte !" << endl;
2368 
2369  if (FMap->isMarked(edge[0], FFictiveEdgeMark))
2370  FMap->unmarkOrbit(edge[0], ORBIT_EDGE, FFictiveEdgeMark);
2371  if (FMap->isMarked(edge[1], FFictiveEdgeMark))
2372  FMap->unmarkOrbit(edge[1], ORBIT_EDGE, FFictiveEdgeMark);
2373 
2374  if (pos[0] == FP_OnReversedBorder) edge[0] = a0(edge[0]);
2375  if (pos[1] == FP_OnReversedBorder) edge[1] = a0(edge[1]);
2376  linkVertices(edge[0], edge[1]);
2377  linkVertices(a1(a0(edge[0])), a1(a0(edge[1])));
2378 
2379 // if (!FTools->arePointsEqual(*VTX(edge[0]), *VTX(edge[1]))) {
2380 // cerr << "intersectSecantFaces: "
2381 // << *VTX(edge[0]) << " != " << *VTX(edge[1]) << endl;
2382 // exit(0);
2383 // }
2384 // if (!FTools->arePointsEqual(*VTX(a0(edge[0])), *VTX(a0(edge[1])))) {
2385 // cerr << "intersectSecantFaces: "
2386 // << *VTX(a0(edge[0])) << " != " << *VTX(a0(edge[1])) << endl;
2387 // exit(0);
2388 // }
2389  }
2390  else if (FMap->isMarked(edge[0], FInterEdgeMark) !=
2391  FMap->isMarked(edge[1], FInterEdgeMark)) {
2392  cerr << "Intersection incohérante ignorée !" << endl;
2393  }
2394  }
2395 
2396  // Passage aux points suivants
2397  for (i = 0; i < 2; ++i) {
2398  if (next_point & (i+1)) {
2399  ip[i] = *it[i]++;
2400  prev_pos[i] = pos[i];
2401  pos[i] = ip[i]->getPosition();
2402  last_vertex[i] = NULL;
2403  }
2404  }
2405  prev_point = next_point;
2406  }
2407 
2408  freeMark(mark);
2409 
2410  MSG("Destruction des ensembles de points d'intersection");
2411  for (i = 0; i < 2; ++i) {
2412  for (it[i] = inter_set[i]->begin(); it[i] != inter_set[i]->end(); ++it[i])
2413  delete *it[i];
2414  delete inter_set[i];
2415  }
2416 }
2417 
2418 //******************************************************************************
2419 
2420 void CCorefine3dFF::intersectCoplanarFaces(CDart * AFace1, CDart * AFace2,
2421  const CPlane & APlane1,
2422  const CPlane & APlane2,
2423  int APositiveMark, int ANegativeMark,
2424  int AFacesMark,
2425  list<CDart*> * /*AFictiveVertices*/,
2426  list<CDart*> * AFictiveEdges)
2427 {
2428  DEBUG_FUNCTION;
2429 
2430  CDart *d, *face[2], *vtx[2], *edge[2];
2431  CPlane plane[2], edge_plane;
2432  CVertex edge_vector, pt1, pt2;
2433  int i, j, nb, nb_pos, nb_neg;
2434  int inter_mark = FMap->getNewMark();
2435  list<CDart*> inter_points;
2436  bool local_inside, inside;
2437 // TInterPt nearest_ip;
2438 
2439  face[0] = AFace1; plane[0] = APlane1;
2440  face[1] = AFace2; plane[1] = APlane2;
2441  for (i = 0; i < 2 && inter_points.empty(); ++i) {
2442  MSG("Recherche des points d'intersection entre les arêtes de la face "
2443  << i << " et les arêtes de la face " << (i+1)%2);
2444  inside = true;
2445  d = face[i];
2446  do {
2447  vtx[0] = d;
2448  d = a1(a0(d));
2449 
2450  pt1 = *VTX(vtx[0]);
2451  pt2 = *VTX(a0(vtx[0]));
2452  edge_vector = pt2 - pt1;
2453  edge_plane.setPlane(plane[i].getNormal() * edge_vector, pt1);
2454  local_inside = false;
2455 
2456  MSG("arête testée : [" << pt1 << " ; " << pt2 << "]");
2457 
2458  classifyFaceVertices(face[(i+1)%2], edge_plane,
2459  APositiveMark, ANegativeMark, AFacesMark,
2460  false, &nb, &nb_pos, &nb_neg);
2461  if (nb_pos == nb)
2462  FMap->unmarkOrbit(face[(i+1)%2], ORBIT_01, APositiveMark);
2463  else if (nb_neg == nb)
2464  FMap->unmarkOrbit(face[(i+1)%2], ORBIT_01, ANegativeMark);
2465  else {
2466  TInterPtCmp comp(FTools, edge_vector);
2467  TInterPtSet *inter_set[2];
2468  TInterPtSet::iterator it[2];
2469  TInterPt *ip[2];
2470  TPositionInFace pos[2];
2471  int prev_point, next_point;
2472 
2473  inter_set[0] = new TInterPtSet(comp);
2474  ip[0] = new TInterPt(pt1, 0, FP_OnBorder);
2475  ip[0]->setEnteringSector(vtx[0]);
2476  ip[0]->setLeavingSector(vtx[0]);
2477  inter_set[0]->insert(ip[0]);
2478  ip[0] = new TInterPt(pt2, 0, FP_Outside);
2479  ip[0]->setLeavingSector(d);
2480  inter_set[0]->insert(ip[0]);
2481 
2482  inter_set[1] = findIntersectionPoints(face[(i+1)%2], plane[(i+1)%2],
2483  edge_plane, edge_vector,
2484  APositiveMark, ANegativeMark,
2485  AFacesMark, comp);
2486 
2487  it[0] = inter_set[0]->begin();
2488  it[1] = inter_set[1]->begin();
2489  ip[0] = ip[1] = NULL;
2490  pos[0] = pos[1] = FP_Outside;
2491  prev_point = next_point = 0;
2492 
2493  // Parcours des ensembles et construction des segments d'intersection
2494  while (it[0] != inter_set[0]->end() && it[1] != inter_set[1]->end()) {
2495  // Les points se trouvent au même endroit
2496  if (FTools->arePointsEqual((*it[0])->getPoint(),
2497  (*it[1])->getPoint()))
2498  next_point = 3;
2499  // Le point le plus proche se trouve sur l'arête
2500  else if (comp(*it[0], *it[1]))
2501  next_point = 1;
2502  // Le point le plus proche se trouve sur la face
2503  else
2504  next_point = 2;
2505 
2506  MSG("prev_point = " << prev_point);
2507  MSG("next_point = " << next_point);
2508  MSG("pos[0] = " << pos[0]);
2509  MSG("pos[1] = " << pos[1]);
2510 
2511  // On se trouve entre les deux sommets de l'arête
2512  if (pos[0] != FP_Outside) {
2513  // On regarde s'il existe une intersection sur l'arête
2514  if (local_inside && (prev_point != 1 || next_point != 1))
2515  local_inside = false;
2516 
2517  /* On regarde si le premier sommet de l'arête est à l'intérieur
2518  de l'autre face */
2519  if (prev_point & 1 && pos[1] != FP_Outside) {
2520  if (pos[1] == FP_Inside ||
2521  edgeInsideVector(vtx[0], plane[i])
2522  .dot(edgeInsideVector(ip[1]->getEnteringSector(),
2523  plane[(i+1)%2])) > 0.0) {
2524  MSG("Le premier sommet est à l'intérieur");
2525  FMap->setMark(vtx[0], FDoubleFaceMark);
2526  }
2527  }
2528 
2529  if (pos[1] == FP_OnBorder || pos[1] == FP_OnReversedBorder) {
2530  if (prev_point == 1) {
2531  vtx[1] = splitEdge(ip[1]->getEnteringSector(), pt1,
2532  AFictiveEdges);
2533  if (pos[1] == FP_OnBorder)
2534  ip[1]->setEnteringSector(vtx[1]);
2535  }
2536  else
2537  vtx[1] = ip[1]->getLeavingSector();
2538  if (prev_point & 1 && !FMap->isMarked(vtx[0], inter_mark))
2539  addIntersectionPoint(vtx, i, AFacesMark, inter_mark,
2540  &inter_points);
2541 
2542  edge[0] = vtx[0];
2543 
2544  if (next_point == 1) {
2545  vtx[0] = a1(a0(vtx[0]));
2546  vtx[1] = splitEdge(ip[1]->getEnteringSector(), pt2,
2547  AFictiveEdges);
2548  if (pos[1] == FP_OnReversedBorder)
2549  ip[1]->setEnteringSector(vtx[1]);
2550  }
2551  else {
2552  if (next_point == 2) {
2553  vtx[0] = splitEdge(vtx[0], (*it[1])->getPoint(),
2554  AFictiveEdges);
2555  }
2556  else if (next_point == 3) {
2557  vtx[0] = a1(a0(vtx[0]));
2558  }
2559  vtx[1] = ((*it[1])->getPosition() == FP_Inside ?
2560  (*it[1])->getEnteringSector() :
2561  (*it[1])->getLeavingSector());
2562  }
2563 
2564  edge[1] = ip[1]->getEnteringSector();
2565 
2566  if (!FMap->isMarked(vtx[0], inter_mark))
2567  addIntersectionPoint(vtx, i, AFacesMark, inter_mark,
2568  &inter_points);
2569 
2570  MSG("edge[0] = [" << *VTX(edge[0]) << ";"
2571  << *VTX(a0(edge[0])) << "]");
2572  MSG("edge[1] = [" << *VTX(edge[1]) << ";"
2573  << *VTX(a0(edge[1])) << "]");
2574 
2575  if (!FMap->isMarked(edge[0], FInterEdgeMark) ||
2576  !FMap->isMarked(edge[1], FInterEdgeMark)) {
2577  MSG("Une arête d'intersection avec un bord trouvée");
2578  FInterEdges.push_front(edge[(i+1)%2]);
2579  FInterEdges.push_front(edge[i]);
2580 
2581  if (!FMap->isMarked(edge[0], FInterEdgeMark))
2582  FMap->markOrbit(edge[0], ORBIT_EDGE, FInterEdgeMark);
2583  else
2584  cerr << "topologie de l'objet " << (i+2)%2
2585  << " incorrecte !" << endl;
2586  if (!FMap->isMarked(edge[1], FInterEdgeMark))
2587  FMap->markOrbit(edge[1], ORBIT_EDGE, FInterEdgeMark);
2588  else
2589  cerr << "topologie de l'objet " << i+1
2590  << " incorrecte !" << endl;
2591 
2592  if (FMap->isMarked(edge[0], FFictiveEdgeMark))
2593  FMap->unmarkOrbit(edge[0], ORBIT_EDGE, FFictiveEdgeMark);
2594  if (FMap->isMarked(edge[1], FFictiveEdgeMark))
2595  FMap->unmarkOrbit(edge[1], ORBIT_EDGE, FFictiveEdgeMark);
2596  }
2597  else {
2598  assert(FMap->isMarked(edge[1], FInterEdgeMark));
2599  }
2600  }
2601  else {
2602  if (prev_point == 3 && ip[1]->getCellDim() == 1) {
2603  vtx[1] = splitEdge(pos[1] == FP_Outside ?
2604  ip[1]->getLeavingSector() :
2605  ip[1]->getEnteringSector(), pt1,
2606  AFictiveEdges);
2607  if (!FMap->isMarked(vtx[0], inter_mark))
2608  addIntersectionPoint(vtx, i, AFacesMark, inter_mark,
2609  &inter_points);
2610  }
2611 
2612  if (next_point != 1) {
2613  if (next_point == 2) {
2614  vtx[0] = splitEdge(vtx[0], (*it[1])->getPoint(),
2615  AFictiveEdges);
2616  vtx[1] = ((*it[1])->getPosition() == FP_Inside ?
2617  (*it[1])->getEnteringSector() :
2618  (*it[1])->getLeavingSector());
2619  if ((*it[1])->getCellDim() == 1)
2620  vtx[1] = splitEdge(vtx[1], (*it[1])->getPoint(),
2621  AFictiveEdges);
2622  }
2623  else {
2624  vtx[0] = a1(a0(vtx[0]));
2625  vtx[1] = ((*it[1])->getPosition() == FP_Inside ?
2626  (*it[1])->getEnteringSector() :
2627  (*it[1])->getLeavingSector());
2628  if ((*it[1])->getCellDim() == 1)
2629  vtx[1] = splitEdge(vtx[1], pt2, AFictiveEdges);
2630  }
2631  if (!FMap->isMarked(vtx[0], inter_mark))
2632  addIntersectionPoint(vtx, i, AFacesMark, inter_mark,
2633  &inter_points);
2634  }
2635  }
2636 
2637  /* On regarde si l'intersection suivante permet de rentrer dans
2638  l'autre face */
2639  if (next_point == 2 && (*it[1])->getPosition() != FP_Outside) {
2640  if ((*it[1])->getPosition() == FP_Inside ||
2641  edgeInsideVector(vtx[0], plane[i])
2642  .dot(edgeInsideVector((*it[1])->getEnteringSector(),
2643  plane[(i+1)%2])) > 0.0) {
2644  MSG("Le nouveau sommet est à l'intérieur");
2645  FMap->setMark(vtx[0], FDoubleFaceMark);
2646  }
2647  }
2648  }
2649  // On se trouve avant le premier sommet de l'arête
2650  else if (!ip[0]) {
2651  local_inside = (pos[1] == FP_Inside);
2652 // if (local_inside)
2653 // nearest_ip = *ip[1];
2654  }
2655 
2656  // Passage aux points suivants
2657  for (j = 0; j < 2; ++j) {
2658  if (next_point & (j+1)) {
2659  ip[j] = *it[j]++;
2660  pos[j] = ip[j]->getPosition();
2661  }
2662  }
2663  prev_point = next_point;
2664  }
2665 
2666  for (j = 0; j < 2; ++j) {
2667  for (it[j] = inter_set[j]->begin(); it[j] != inter_set[j]->end();
2668  ++it[j]) delete *it[j];
2669  delete inter_set[j];
2670  }
2671  }
2672  MSG("local_inside = " << local_inside);
2673  if (!local_inside) inside = false;
2674  }
2675  while (d != face[i]);
2676 
2677  MSG(inter_points.size() << " points d'intersection trouvés");
2678 
2679 // if (inside) {
2680 // MSG("La première face se trouve à l'intérieur de l'autre");
2681 // assert(inter_points.empty());
2682 // vtx[1] = nearest_ip.getEnteringSector();
2683 // if (nearest_ip.getCellDim() == 1) {
2684 // vtx[1] = splitEdge(vtx[1], nearest_ip.getPoint(), AFictiveEdges);
2685 // FMap->markOrbit(vtx[1], ORBIT_VERTEX, FFictiveVertexMark);
2686 // AFictiveVertices->push_back(vtx[1]);
2687 // }
2688 // vtx[1] = insertVertexInFace(vtx[1], pt1);
2689 // AFictiveEdges->push_back(vtx[1]);
2690 // addIntersectionPoint(vtx, i, AFacesMark, inter_mark, &inter_points);
2691 // }
2692  if (inside) {
2693  MSG("La première face se trouve à l'intérieur de l'autre");
2694  assert(inter_points.empty());
2695 
2696  TCoordinate dist, best_dist = 0;
2697  CPlane ref_plane(vertexInsideVector(d, plane[i]), *VTX(d));
2698 
2699  MSG("Recherche d'un sommet de l'enveloppe convexe de la face");
2700  vtx[0] = d;
2701  d = a1(a0(d));
2702  do {
2703  dist = ref_plane.pointDistance(*VTX(d));
2704  if (dist < best_dist) {
2705  best_dist = dist;
2706  vtx[0] = d;
2707  }
2708  d = a1(a0(d));
2709  }
2710  while (d != face[i]);
2711 
2712  edge_vector = -vertexInsideVector(vtx[0], plane[i]);
2713  edge_plane.setPlane(plane[i].getNormal() * edge_vector, *VTX(vtx[0]));
2714 
2715  MSG("Calcul des points d'intersection entre un vecteur et l'autre face");
2716  TInterPtCmp comp(FTools, edge_vector);
2717  TInterPtSet *inter_set;
2718  TInterPtSet::iterator it;
2719  inter_set = findIntersectionPoints(face[(i+1)%2], plane[(i+1)%2],
2720  edge_plane, edge_vector,
2721  APositiveMark, ANegativeMark,
2722  AFacesMark, comp);
2723 
2724  MSG("Recherche du point d'intersection le plus proche du sommet");
2725  it = inter_set->begin();
2726  while (it != inter_set->end() &&
2727  (*VTX(vtx[0]) - (*it)->getPoint()).dot(edge_vector) > 0.0) ++it;
2728 
2729  MSG("Recherche d'un sommet de l'autre face pour insérer une arête");
2730  vtx[1] = ((*it)->getPosition() == FP_Inside ?
2731  (*it)->getEnteringSector() : (*it)->getLeavingSector());
2732  if ((*it)->getCellDim() == 1) {
2733  CPlane clip_plane1(edgeInsideVector(vtx[1], plane[(i+1)%2]),
2734  (*it)->getPoint());
2735  CPlane clip_plane2(edge_vector, *VTX(vtx[0]));
2736  vtx[1] = findNearestFaceVertex(vtx[1], edge_plane,
2737  clip_plane1, clip_plane2);
2738  assert(vtx[1]);
2739  }
2740  MSG("Insertion de l'arête");
2741  vtx[1] = insertVertexInFace(vtx[1], *VTX(vtx[0]));
2742  AFictiveEdges->push_back(vtx[1]);
2743  addIntersectionPoint(vtx, i, AFacesMark, inter_mark, &inter_points);
2744  }
2745  }
2746 
2747  MSG("Création des arêtes d'intersection");
2748  int orient_mark = FMap->getNewMark();
2749  list<CDart*>::iterator it;
2750 
2751  for (it = inter_points.begin(); it != inter_points.end(); ++it) {
2752  CDart *d1, *d2;
2753 
2754  vtx[0] = *it;
2755  vtx[1] = LINK(*it);
2756 
2757  for (i = 0; i < 2; ++i) {
2758  MSG("Parcours des arêtes de la face " << i+1 << " autour du sommet "
2759  << *VTX(vtx[i]));
2760  FMap->halfMarkOrbit(vtx[i], ORBIT_VERTEX, orient_mark);
2761  for (CDynamicCoverageVertex dcv(FMap, vtx[i]); dcv.cont(); ++dcv)
2762  if (FMap->isMarked(*dcv, orient_mark)) {
2763  FMap->unsetMark(*dcv, orient_mark);
2764  if (FMap->isMarked(*dcv, inter_mark)) {
2765  FMap->unsetMark(*dcv, inter_mark);
2766  d = *dcv;
2767  do {
2768  if (!FMap->isMarked(d, FInterEdgeMark)) {
2769  MSG("L'arête courante n'est pas une arête d'intersection");
2770  assert(LINK(d));
2771  edge_vector = *VTX(a0(d)) - *VTX(d);
2772  d1 = findFaceSector(LINK(d), plane[(i+1)%2],
2773  AFacesMark, edge_vector);
2774  if (d1) {
2775  MSG("L'arête est à l'intérieur de l'autre face");
2776  d2 = LINK(a0(d));
2777  if (d2) {
2778  d2 = findFaceSector(d2, plane[(i+1)%2],
2779  AFacesMark, -edge_vector);
2780  assert(d2);
2781  d1 = splitFace(d1, d2);
2782  }
2783  else
2784  d1 = insertEdgeInFace(d1, *VTX(a0(d)));
2785  linkVertices(a1(a0(d)), a1(a0(d1)));
2786  if (FMap->isMarked(d, FFictiveEdgeMark))
2787  FMap->unmarkOrbit(d, ORBIT_EDGE, FFictiveEdgeMark);
2788  FMap->markOrbit(d, ORBIT_EDGE, FInterEdgeMark);
2789  FMap->markOrbit(d1, ORBIT_EDGE, FInterEdgeMark);
2790  if (i == 0) {
2791  FInterEdges.push_front(d1);
2792  FInterEdges.push_front(d);
2793  }
2794  else {
2795  FInterEdges.push_front(d);
2796  FInterEdges.push_front(d1);
2797  }
2798  }
2799  else
2800  FMap->setMark(a0(d), inter_mark);
2801  }
2802  d = a1(a0(d));
2803  }
2804  while (!FMap->isMarked(a1(d), inter_mark));
2805  FMap->unsetMark(a1(d), inter_mark);
2806  }
2807  }
2808  }
2809  }
2810  for (it = inter_points.begin(); it != inter_points.end(); ++it) {
2811  vtx[0] = *it;
2812  vtx[1] = LINK(*it);
2813  for (i = 0; i < 2; ++i)
2814  for (CDynamicCoverageVertex dcv(FMap, vtx[i]); dcv.cont(); ++dcv) {
2815  FMap->unsetMark(*dcv, inter_mark);
2816  if (FMap->isMarked(*dcv, FDoubleFaceMark) &&
2817  !FMap->isMarked(a1(*dcv), FDoubleFaceMark)) {
2818  FMap->markOrbit(*dcv, ORBIT_FACE, FDoubleFaceMark);
2819  FDoubleFaces.push_back(*dcv);
2820  }
2821  }
2822  }
2823 
2824  freeMark(inter_mark);
2825  freeMark(orient_mark);
2826 }
2827 
2828 //******************************************************************************
2829 
2830 void CCorefine3dFF::assignFacesPlaneInfo(int ADirectInfo, int ANegativeMark,
2831  TCorefFaceList * AList)
2832 {
2833  DEBUG_FUNCTION;
2834 
2835  for (TCorefFaceList::iterator it = AList->begin(); it != AList->end(); ++it)
2836  for (CDynamicCoverage01 cov(FMap, it->face); cov.cont(); ++cov) {
2837  FMap->setDirectInfo(*cov, ADirectInfo, &it->plane);
2838  FMap->setDirectInfo(a3(*cov), ADirectInfo, &it->plane);
2839  FMap->setMark(a3(*cov), ANegativeMark);
2840  }
2841 }
2842 
2843 //******************************************************************************
2844 
2845 void CCorefine3dFF::removeFacesPlaneInfo(int /*ADirectInfo*/, int ANegativeMark,
2846  TCorefFaceList * AList)
2847 {
2848  DEBUG_FUNCTION;
2849 
2850  for (TCorefFaceList::iterator it = AList->begin(); it != AList->end(); ++it)
2851  for (CDynamicCoverage01 cov(FMap, a3(it->face)); cov.cont(); ++cov)
2852  FMap->unsetMark(*cov, ANegativeMark);
2853 }
2854 
2855 //******************************************************************************
2856 
2857 void CCorefine3dFF::sortFacesAroundEdges(int AFacePlaneDI, int ANegativeMark)
2858 {
2859  DEBUG_FUNCTION;
2860 
2861  list<CDart*>::iterator it;
2862  TFaceSet *face_set;
2863  CDart *edge1, *edge2;
2864 
2865  for (it = FInterEdges.begin(); it != FInterEdges.end();) {
2866  edge1 = *it++;
2867  edge2 = *it++;
2868  if (edge1 && edge2) {
2869  face_set = sortFacesAroundEdges(edge1, edge2,
2870  AFacePlaneDI, ANegativeMark);
2871  linkSortedFaces(face_set);
2872  delete face_set;
2873  }
2874  }
2875 }
2876 
2877 //******************************************************************************
2878 #define VECT(d) (FMap->isMarked(d, ANegativeMark) ?\
2879  -((CPlane*)FMap->getDirectInfo(d, AFacePlaneDI))->getNormal():\
2880  ((CPlane*)FMap->getDirectInfo(d, AFacePlaneDI))->getNormal())
2881 
2882 TFaceSet * CCorefine3dFF::sortFacesAroundEdges(CDart * AEdge1, CDart * AEdge2,
2883  int AFacePlaneDI,
2884  int ANegativeMark)
2885 {
2886  DEBUG_FUNCTION;
2887 
2888  CDart *d1, *d2;
2889  CVertex axis = *VTX(a0(AEdge1)) - *VTX(AEdge1);
2890  CAngularFaceComparator comp(FMap, FTools, axis, VECT(AEdge1),
2891  FVertexDI, AFacePlaneDI, ANegativeMark);
2892  TFaceSet *faces = new TFaceSet(comp);
2893 
2894  // Ajout des premières faces
2895  d1 = AEdge1;
2896  do {
2897  faces->insert(d1);
2898  d1 = a3(FTools->alpha2(d1));
2899  }
2900  while (d1 != AEdge1);
2901 
2902  // Ajout des secondes faces
2903  if ((*VTX(a0(AEdge2)) - *VTX(AEdge2)).dot(axis) < 0.0)
2904  AEdge2 = a3(a0(AEdge2));
2905  d2 = AEdge2;
2906  do {
2907  faces->insert(d2);
2908  d2 = a3(FTools->alpha2(d2));
2909  }
2910  while (d2 != AEdge2);
2911 
2912  return faces;
2913 }
2914 
2915 //******************************************************************************
2916 
2917 // TFaceSet * CCorefine3dFF::sortFacesAroundEdges(CDart * AEdge1, CDart * AEdge2,
2918 // int AFacePlaneDI,
2919 // int ANegativeMark)
2920 // {
2921 // DEBUG_FUNCTION;
2922 
2923 // CDart *d1, *d2;
2924 // CVertex axis = *VTX(a0(AEdge1)) - *VTX(AEdge1);
2925 // TFaceSet *faces = new TFaceSet;
2926 // CPlane axis_plane(axis, *VTX(AEdge1));
2927 // CVertex v, v1, v2;
2928 
2929 // if (FTools->edgeVector(AEdge2, FVertexDI).dot(axis) < 0.0)
2930 // AEdge2 = a3(a0(AEdge2));
2931 
2932 // if (FMap->isFree2(AEdge1) && FMap->isFree2(a3(AEdge1))) {
2933 // CDart *tmp = AEdge1;
2934 // AEdge1 = AEdge2;
2935 // AEdge2 = tmp;
2936 // }
2937 
2938 // if (FMap->isFree2(AEdge2) && FMap->isFree2(a3(AEdge2))) {
2939 // faces->push_back(AEdge2);
2940 
2941 // if (FMap->isFree2(AEdge1) && FMap->isFree2(a3(AEdge1))) {
2942 // faces->push_back(AEdge1);
2943 // }
2944 // else {
2945 // v = VECT(d2);
2946 // v1 = VECT(AEdge1);
2947 // v2 = VECT(a3(FTools->alpha2(AEdge1)));
2948 // while (!FTools->isVectorInSector(v, v1, v2, axis_plane, false, true)) {
2949 // AEdge1 = a3(FTools->alpha2(AEdge1));
2950 // v1 = v2;
2951 // v2 = VECT(a3(FTools->alpha2(AEdge1)));
2952 // }
2953 // d1 = AEdge1;
2954 // do {
2955 // d1 = a3(FTools->alpha2(d1));
2956 // faces->push_back(d1);
2957 // }
2958 // while (d1 != AEdge1);
2959 // }
2960 // }
2961 // else {
2962 // int mark = FMap->getNewMark();
2963 
2964 // d1 = AEdge1;
2965 // v1 = VECT(d1);
2966 // v2 = VECT(a3(FTools->alpha2(d1)));
2967 
2968 // while (!FTools->isVectorInSector(VECT(AEdge2), v1, v2,
2969 // axis_plane, false, true))
2970 // AEdge2 = a3(FTools->alpha2(AEdge2));
2971 
2972 // d2 = AEdge2;
2973 // do {
2974 // v = VECT(d2);
2975 
2976 // while (!FTools->isVectorInSector(v, v1, v2, axis_plane, false, true)) {
2977 // d1 = a3(FTools->alpha2(d1));
2978 // v1 = v2;
2979 // v2 = VECT(a3(FTools->alpha2(d1)));
2980 // assert(!FMap->isMarked(d1, mark));
2981 // faces->push_back(d1);
2982 // FMap->setMark(d1, mark);
2983 // }
2984 
2985 // faces->push_back(d2);
2986 // d2 = a3(FTools->alpha2(d2));
2987 // }
2988 // while (d2 != AEdge2);
2989 
2990 // if (d1 != AEdge1 || !FMap->isMarked(d1, mark))
2991 // do {
2992 // d1 = a3(FTools->alpha2(d1));
2993 // assert(!FMap->isMarked(d1, mark));
2994 // faces->push_back(d1);
2995 // FMap->setMark(d1, mark);
2996 // }
2997 // while (d1 != AEdge1);
2998 
2999 // do {
3000 // assert(FMap->isMarked(d1, mark));
3001 // FMap->unsetMark(d1, mark);
3002 // d1 = a3(FTools->alpha2(d1));
3003 // }
3004 // while (d1 != AEdge1);
3005 
3006 // freeMark(mark);
3007 // }
3008 
3009 // return faces;
3010 // }
3011 
3012 #undef VECT
3013 //******************************************************************************
3014 
3015 void CCorefine3dFF::linkSortedFaces(TFaceSet * AFaceSet)
3016 {
3017  DEBUG_FUNCTION;
3018 
3019  CDart *d1, *d2;
3020  TFaceSet::iterator it;
3021 
3022  for (it = AFaceSet->begin(); it != AFaceSet->end(); ) {
3023  d1 = *it++;
3024  d2 = (it != AFaceSet->end()) ? *it : *AFaceSet->begin();
3025 
3026  if (a2(d1) != a3(d2)) {
3027  if (!FMap->isFree2(d1)) FMap->unsew2(d1);
3028  if (!FMap->isFree2(a3(d2))) FMap->unsew2(a3(d2));
3029  FMap->sew2(d1, a3(d2));
3030  FMap->pointDirectInfoToAttributeVertex(FVertexDI, d1);
3031  FMap->pointDirectInfoToAttributeVertex(FVertexDI, a0(d1));
3032  }
3033  }
3034 }
3035 
3036 //******************************************************************************
3037 
3038 void CCorefine3dFF::spreadMarksAroundEdges(TFaceSet * AFaceSet,
3039  bitset<NB_MARKS> AMarks)
3040 {
3041  DEBUG_FUNCTION;
3042 
3043  CDart *d1, *d2;
3044  TFaceSet::iterator it;
3045  int m;
3046 
3047  for (it = AFaceSet->begin(); it != AFaceSet->end(); ) {
3048  d1 = *it++;
3049  d2 = (it != AFaceSet->end()) ? *it : *AFaceSet->begin();
3050 
3051  for (m = 0; m < NB_MARKS; ++m)
3052  if (AMarks[m] && a2(d1) != a3(d2)) {
3053  if (FMap->isMarked(d1, m)) FMap->setMark(a3(d2), m);
3054  else if (FMap->isMarked(a3(d2), m)) FMap->setMark(d1, m);
3055  if (FMap->isMarked(a0(d1), m)) FMap->setMark(a0(a3(d2)), m);
3056  else if (FMap->isMarked(a0(a3(d2)), m)) FMap->setMark(a0(d1), m);
3057  }
3058  }
3059 }
3060 
3061 //******************************************************************************
3062 
3063 bool CCorefine3dFF::isPointInFace(const CVertex & APoint, CDart * AFace,
3064  const CPlane & APlane)
3065 {
3066  CVertex line = *VTX(AFace) - APoint;
3067 
3068  if (FTools->isVectorNull(line))
3069  return true;
3070 
3071  TInterPtCmp comp(FTools, line);
3072  CPlane plane(APlane.getNormal() * line, *VTX(AFace));
3073  int face_mark = FMap->getNewMark();
3074  int positive_mark = FMap->getNewMark();
3075  int negative_mark = FMap->getNewMark();
3076  TInterPtSet *inter_set;
3077 
3078  FMap->markOrbit(AFace, ORBIT_01, face_mark);
3079  classifyFaceVertices(AFace, plane, positive_mark, negative_mark,
3080  face_mark, false);
3081  inter_set = findIntersectionPoints(AFace, APlane, plane, line,
3082  positive_mark, negative_mark,
3083  face_mark, comp);
3084  assert(!inter_set->empty());
3085 
3086  TInterPtSet::iterator it;
3087  TPositionInFace pos = FP_Outside;
3088  for (it = inter_set->begin(); it != inter_set->end(); ++it) {
3089  if (FTools->arePointsEqual((*it)->getPoint(), APoint)) {
3090  pos = FP_Inside;
3091  break;
3092  }
3093  else if ((APoint - (*it)->getPoint()).dot(line) > 0.0)
3094  pos = (*it)->getPosition();
3095  else
3096  break;
3097  }
3098 
3099  for (it = inter_set->begin(); it != inter_set->end(); ++it)
3100  delete *it;
3101  delete inter_set;
3102 
3103  return pos == FP_Inside;
3104 }
3105 
3106 //******************************************************************************