src/TopOpeBRepTool/TopOpeBRepTool_RegularizeW.cxx

   1 // Created on: 1998-12-23
   2 // Created by: Xuan PHAM PHU
   3 // Copyright (c) 1998-1999 Matra Datavision
   4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   5 //
   6 // This file is part of Open CASCADE Technology software library.
   7 //
   8 // This library is free software; you can redistribute it and/or modify it under
   9 // the terms of the GNU Lesser General Public License version 2.1 as published
  10 // by the Free Software Foundation, with special exception defined in the file
  11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  12 // distribution for complete text of the license and disclaimer of any warranty.
  13 //
  14 // Alternatively, this file may be used under the terms of Open CASCADE
  15 // commercial license or contractual agreement.
  16
  17 #include <TopOpeBRepTool.hxx>
  18 #include <TopOpeBRepTool_EXPORT.hxx>
  19 #include <TopOpeBRepTool_CLASSI.hxx>
  20 #include <TopOpeBRepTool_REGUW.hxx>
  21 #include <TopOpeBRepTool_TOOL.hxx>
  22 #include <TopOpeBRepTool_define.hxx>
  23 #include <TopExp_Explorer.hxx>
  24 #include <BRep_Tool.hxx>
  25 #include <TopAbs.hxx>
  26 #include <TopoDS.hxx>
  27
  28 #ifdef DRAW
  29 #include <TopOpeBRepTool_DRAW.hxx>
  30 #endif
  31
  32 #define SAME     (-1)
  33 #define DIFF     (-2)
  34 #define UNKNOWN  ( 0)
  35 #define oneINtwo ( 1)
  36 #define twoINone ( 2)
  37
  38 #define M_FORWARD(sta)  (sta == TopAbs_FORWARD)
  39 #define M_REVERSED(sta) (sta == TopAbs_REVERSED)
  40 #define M_INTERNAL(sta) (sta == TopAbs_INTERNAL)
  41 #define M_EXTERNAL(sta) (sta == TopAbs_EXTERNAL)
  42
  43 #ifdef OCCT_DEBUG
  44 extern Standard_Boolean TopOpeBRepTool_GettraceREGUFA();
  45 static TopTools_IndexedMapOfShape STATIC_mapw,STATIC_mapf;
  46 static Standard_Integer FUN_adds(const TopoDS_Shape& s) {
  47   TopAbs_ShapeEnum typ = s.ShapeType();
  48   TCollection_AsciiString aa; Standard_Integer is = 0;
  49   if (typ == TopAbs_WIRE)   {aa = TCollection_AsciiString("wi"); is = STATIC_mapw.Add(s); }
  50   if (typ == TopAbs_FACE)   {aa = TCollection_AsciiString("fa"); is = STATIC_mapf.Add(s); }
  51 #ifdef DRAW
  52   FUN_tool_draw(aa,s,is);
  53 #endif
  54   return is;
  55 }
  56 Standard_EXPORT void FUN_tool_coutsta(const Standard_Integer& sta, const Standard_Integer& i1, const Standard_Integer& i2)
  57 {
  58   switch (sta) {
  59   case SAME:
  60     cout<<i1<<" gives SAME bnd with "<<i2<<endl; break;
  61   case DIFF:
  62     cout<<i1<<" gives  OUT bnd with "<<i2<<endl; break;
  63   case oneINtwo:
  64     cout<<i1<<" is IN "<<i2<<endl; break;
  65   case twoINone:
  66     cout<<i2<<" is IN "<<i1<<endl; break;
  67   }
  68 }
  69 #endif
  70
  71 Standard_EXPORT void FUN_addOwlw(const TopoDS_Shape& Ow, const TopTools_ListOfShape& lw, TopTools_ListOfShape& lresu);
  72
  73 //=======================================================================
  74 //function : RegularizeWires
  75 //purpose  :
  76 //=======================================================================
  77
  78 Standard_Boolean TopOpeBRepTool::RegularizeWires(const TopoDS_Face& theFace,
  79                                     TopTools_DataMapOfShapeListOfShape& mapoldWnewW,
  80                                     TopTools_DataMapOfShapeListOfShape& ESplits) // (e,esp); esp = splits of e
  81 {
  82   if (theFace.IsNull()) return Standard_False;
  83  TopoDS_Shape aLocalShape = theFace.Oriented(TopAbs_FORWARD);
  84   TopoDS_Face aFace = TopoDS::Face(aLocalShape);
  85 //  TopoDS_Face aFace = TopoDS::Face(theFace.Oriented(TopAbs_FORWARD));
  86
  87   TopOpeBRepTool_REGUW REGUW(aFace);
  88   REGUW.SetOwNw(mapoldWnewW);
  89   REGUW.SetEsplits(ESplits);
  90
  91 //  Standard_Boolean hasregu = Standard_False;
  92   TopExp_Explorer exw(aFace, TopAbs_WIRE);
  93   for (; exw.More(); exw.Next()) {
  94     const TopoDS_Shape& W = exw.Current();
  95     REGUW.Init(W);
  96     Standard_Boolean ok = REGUW.MapS();
  97     if (!ok) return Standard_False;
  98     ok = REGUW.SplitEds();
  99     if (!ok) return Standard_False;
 100     ok = REGUW.REGU();
 101     if (!ok) return Standard_False;
 102   }
 103
 104   REGUW.GetEsplits(ESplits);
 105   REGUW.GetOwNw(mapoldWnewW);
 106   return Standard_True;
 107 }
 108
 109 //=======================================================================
 110 //function : Regularize
 111 //purpose  :
 112 //=======================================================================
 113
 114 Standard_Boolean TopOpeBRepTool::Regularize(const TopoDS_Face& theFace,
 115                                TopTools_ListOfShape& aListOfFaces,
 116                                TopTools_DataMapOfShapeListOfShape& ESplits)
 117 {
 118   TopOpeBRepTool_REGUW REGUW(theFace);
 119   aListOfFaces.Clear();
 120   TopTools_DataMapOfShapeListOfShape mapoldWnewW;
 121   Standard_Boolean regu = TopOpeBRepTool::RegularizeWires(theFace,mapoldWnewW,ESplits);
 122   if (regu) {
 123     regu = TopOpeBRepTool::RegularizeFace(theFace,mapoldWnewW,aListOfFaces);
 124   }
 125   return regu;
 126 }
 127
 128 //**********************************************************************
 129 //   classifying wires
 130 //**********************************************************************
 131
 132 // ------------------------------------------------------------
 133 // ------------------ classifying wires -----------------------
 134
 135 // function : bFgreaterbFF (F,FF)
 136 // purpose  : returns False if <F>'s 3d bounding box smaller than <FF>'s
 137
 138 // function : mkBnd2d (W,F,B2d)
 139 // purpose  : get 2d bounding box <B2d> of wire <W>'s UV
 140 //            representation on face <F>.
 141
 142 // function : classiBnd2d (B,ismaller)
 143 // purpose  : compare the two 2d bounding boxes of array <B>
 144 //            if found, B<ismaller> is the smaller one and returns IN
 145 //            else if boxes are disjoint, returns OUT
 146 //            else return UNKNOWN
 147 // function : classiBnd2d (B)
 148 // purpose  : returns SAME,DIFF,UNKNOWN,oneINtwo or twoINone
 149
 150
 151 // function : mkboundedF(W,boundedF)
 152 // purpose  :
 153
 154 // function : FindAPointInTheFace(F,u,v)
 155 // purpose  :
 156
 157 // function : GetFP2d(W,boundedF,p2d)
 158 // purpose  : computes <boundedF> the bounded face built up with wire <W>
 159 //            and <p2d> a point in <boundedF>
 160 //
 161
 162 // function : classiwithp2d(wi)
 163 // purpose  : classify wires (wi(k),k = 1,2)
 164 //            prequesitory : wires of <wi> are not intersecting each other.
 165
 166 // function : ClassifW(F,mapoldWnewW,mapWlow)
 167 // purpose  : all wires described in <mapoldWnewW> are on face <F>
 168 //            <mapoldWnewW> = map with :
 169 //             key = a wire of <F>
 170 //             item = the splits of the previous wire (can be an empty list)
 171 //            the aim is to get map <mapWlow> with :
 172 //             key = a new face's boundary
 173 //             item = wires dexcribing holes in the previous face
 174 //                    (can be an empty list)
 175 // ------------------------------------------------------------
 176
 177 /*static TopAbs_State FUN_tool_classiBnd2d(const Bnd_Array1OfBox2d& B,Standard_Integer& ismaller,
 178                                  const Standard_Boolean chklarge = Standard_True)
 179 {
 180   // purpose :
 181   //   Getting <ismaller>, index of the smallest Bnd Box
 182   //   if B(i) is IN B(j): ismaller = i,
 183   //                       return IN.
 184   //   else: ismaller = 1,
 185   //         if B(1) and B(2) are disjoint, return OUT
 186   //         if B(1) and B(2) are same, return ON
 187   //         else return UNKNOWN.
 188   ismaller = 1;
 189
 190   TColStd_Array2OfReal UV(1,2, 1,4);
 191   for (Standard_Integer i = 1; i <= 2; i++)
 192     //      (Umin(i), Vmin(i), Umax(i), Vmax(i))
 193     B(i).Get(UV(i,1), UV(i,3), UV(i,2), UV(i,4));
 194
 195 #ifdef OCCT_DEBUG
 196   Standard_Boolean trc = Standard_False;
 197   if (trc) {
 198     for (Standard_Integer i = 1; i <= 2; i++)
 199       cout<<"B("<<i<<") = ("<<UV(i,1)<<" "<<UV(i,3)<<" "<<UV(i,2)<<" "<<UV(i,4)<<")"<<endl;
 200   }
 201 #endif
 202
 203   Standard_Boolean smaller, same;
 204   Standard_Integer ii, jj;
 205   Standard_Real tol = 1.e-6;
 206
 207   Standard_Boolean disjoint = Standard_False;
 208   for (Standard_Integer k = 1; k <= 3; k+=2) {
 209     for (i = 1; i <= 2; i++) {
 210       ii = i; jj = (i == 1) ?  2 : 1;
 211       //  diff = Umin<ii> - Umax<jj> : k = 1
 212       //  diff = Vmin<ii> - Vmax<jj> : k = 3
 213       Standard_Real diff = UV(ii,k) - UV(jj,k+1);
 214       // IMPORTANT : for splitted faces sharing same edge, use
 215       // chklarge = True.
 216       disjoint = chklarge ? (diff >= -tol) : (diff > 0.);
 217       if (disjoint) {ismaller = 1; return TopAbs_OUT;}
 218     }
 219   }
 220
 221   for (i = 1; i <= 2; i++) {
 222     ii = i; jj = (i == 1) ? 2 : 1;
 223     smaller = same = Standard_True;
 224     for (Standard_Integer k = 1; k <= 3; k += 2){
 225       //  diff = Umin<ii> - Umin<jj> : k = 1
 226       //  diff = Vmin<ii> - Vmin<jj> : k = 3
 227       Standard_Real diff = UV(ii,k) - UV(jj,k);
 228       smaller = chklarge ? (smaller && (diff > -tol)) : (smaller && (diff > 0.));
 229       same = same && (Abs(diff) <= tol);
 230     }
 231     for (k = 2; k <= 4; k +=2){
 232       //  diff = Umax<ii> - Umax<jj> : k = 2
 233       //  diff = Vmax<ii> - Vmax<jj> : k = 4
 234       Standard_Real diff = UV(ii,k) - UV(jj,k);
 235       smaller = chklarge ? (smaller && (diff < tol)) : (smaller && (diff < 0.));
 236       same = same && (Abs(diff) <= tol);
 237     }
 238
 239     if (same) return TopAbs_ON;
 240     if (smaller) {
 241       ismaller = ii;
 242       return TopAbs_IN;
 243     }
 244   }
 245   return TopAbs_UNKNOWN;
 246 }
 247
 248 #define SAME     (-1)
 249 #define DIFF     (-2)
 250 #define UNKNOWN  ( 0)
 251 #define oneINtwo ( 1)
 252 #define twoINone ( 2)
 253
 254 Standard_EXPORT Standard_Integer FUN_tool_classiBnd2d(const Bnd_Array1OfBox2d& B,
 255                                          const Standard_Boolean chklarge = Standard_True)
 256 {
 257   Standard_Integer ismaller;
 258   TopAbs_State sta = FUN_tool_classiBnd2d(B, ismaller, chklarge);
 259   Standard_Integer res = -10;
 260   switch (sta) {
 261   case TopAbs_IN :
 262     res = ismaller; break;
 263   case TopAbs_OUT :
 264     res = DIFF; break;
 265   case TopAbs_ON :
 266     res = SAME; break;
 267   case TopAbs_UNKNOWN :
 268     res = UNKNOWN; break;
 269   }
 270   return res;
 271 }
 272
 273 static Standard_Boolean FUN_tool_mkboundedF(const TopoDS_Wire& W, TopoDS_Face& boundedF)
 274 {
 275   BRepLib_MakeFace mf(W, Standard_False);
 276   Standard_Boolean done = mf.IsDone();
 277   if (done) boundedF = mf.Face();
 278   return done;
 279 }
 280 Standard_Boolean FUN_tool_FindAPointInTheFace(const TopoDS_Face& F,
 281                                  Standard_Real& u, Standard_Real& v)
 282 {
 283   Standard_Boolean ok = BRepClass3d_SolidExplorer::FindAPointInTheFace(F,u,v);
 284   return ok;
 285 }
 286 static Standard_Boolean FUN_tool_GetFP2d(const TopoDS_Shape& W,
 287                             TopoDS_Shape& boundedF, gp_Pnt2d& p2d)
 288 {
 289   Standard_Boolean ok = FUN_tool_mkboundedF(TopoDS::Wire(W), TopoDS::Face(boundedF));
 290   if (!ok) return Standard_False;
 291
 292   Standard_Real u,v; ok = FUN_tool_FindAPointInTheFace(TopoDS::Face(boundedF),u,v);
 293   if (!ok) return Standard_False;
 294   p2d = gp_Pnt2d(u,v);
 295   return Standard_True;
 296 }
 297 static Standard_Integer FUN_tool_classiwithp2d(const TopTools_Array1OfShape& wi)
 298 {
 299   Standard_Integer stares = UNKNOWN;
 300   TopTools_Array1OfShape fa(1,2);
 301   TColgp_Array1OfPnt     p3d(1,2);
 302   for (Standard_Integer k = 1; k <= 2; k++) {
 303     gp_Pnt2d p2d;
 304     Standard_Boolean ok = FUN_tool_GetFP2d(wi(k), fa(k), p2d);
 305     if (!ok) return UNKNOWN;
 306     BRepAdaptor_Surface BS(TopoDS::Face(fa(k)));
 307     p3d(k) = BS.Value(p2d.X(),p2d.Y());
 308   }
 309
 310   TopAbs_State sta;
 311   Standard_Integer i,j; i = j = 0;
 312   for (Standard_Integer nite = 1; nite <= 2; nite++) {
 313     i = nite;
 314     j = (i == 1) ? 2 : 1;
 315     TopoDS_Face f = TopoDS::Face(fa(j));
 316     const gp_Pnt p = p3d(i);
 317     Standard_Real tol = BRep_Tool::Tolerance(f);
 318     BRepClass_FaceClassifier Fclass(f, p, tol);
 319     sta = Fclass.State();
 320     if (sta == TopAbs_IN) break;
 321   }
 322   switch (sta) {
 323   case TopAbs_IN :
 324     stares = i; break;
 325   case TopAbs_OUT :
 326     stares = DIFF; break;
 327   case TopAbs_ON :
 328   case TopAbs_UNKNOWN :
 329     stares = UNKNOWN; break;
 330   }
 331   return stares;
 332 }
 333
 334 Standard_EXPORT Standard_Boolean FUN_tool_ClassifW(const TopoDS_Face& F,
 335                                       const TopTools_DataMapOfShapeListOfShape& mapoldWnewW,
 336                                       TopTools_DataMapOfShapeListOfShape& mapWlow)
 337 {
 338   // NYI : create maps to store Bnd_Box2d, and faces.
 339
 340 #ifdef OCCT_DEBUG
 341   Standard_Boolean trc = TopOpeBRepTool_GettraceREGUFA();
 342   if (trc) cout<<"** ClassifW :"<<endl;
 343   STATIC_mapw.Clear();
 344 #endif
 345
 346   // Purpose :
 347   // --------
 348   // Filling the map <mapWlow> : with (key + item) = new face,
 349   //  item = (newface has holes) ? list of wires IN the wire key: empty list
 350
 351   // prequesitory : <mapoldWnewW> binds (non splitted wire of <F>, emptylos)
 352   //                                    (splitted wire of <F>, splits of the wire)
 353
 354   // Mapping :
 355   // --------
 356   // Filling <oldW> : list of wires of <F>
 357   // Filling <mapWlow> : with (non-splitted old wire, emptylos),
 358   //                          (split of old wire, emptylos)
 359   TopTools_ListOfShape oldW;
 360   Standard_Integer noldW = mapoldWnewW.Extent();
 361   Standard_Boolean oneoldW = (noldW == 1);
 362   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape ite(mapoldWnewW);
 363   TopTools_ListOfShape emptylos;
 364
 365   // --------------
 366   // * noldW == 1 :
 367   // --------------
 368   if (oneoldW) {
 369     const TopoDS_Wire& oldwi = TopoDS::Wire(ite.Key());
 370     const TopTools_ListOfShape& low = ite.Value();
 371     Standard_Integer nw = low.Extent();
 372     if (nw == 0) {mapWlow.Bind(oldwi,emptylos); return Standard_True;}
 373     if (nw == 1) {mapWlow.Bind(low.First(),emptylos); return Standard_True;}
 374
 375     // <complWoldw> = {(newwire, emptylos)}
 376     TopTools_DataMapOfShapeListOfShape complWoldw;
 377     TopTools_ListIteratorOfListOfShape itlw(low);
 378     for (; itlw.More(); itlw.Next()) complWoldw.Bind(itlw.Value(), emptylos);
 379
 380     // iteration on <complWoldw> :
 381     Standard_Integer ncompl = complWoldw.Extent();
 382     Standard_Boolean go = Standard_True;
 383     Standard_Integer nite = 0, nitemax = Standard_Integer(ncompl*(ncompl-1)/2);
 384     while (go && (nite <= nitemax)){
 385       Bnd_Array1OfBox2d Bnd2d(1,2);
 386       TopTools_Array1OfShape wi(1,2);
 387
 388       TopTools_DataMapIteratorOfDataMapOfShapeListOfShape itmap(complWoldw);
 389       wi(1) = itmap.Key();
 390       if (ncompl == 1) {
 391         mapWlow.Bind(wi(1),itmap.Value());
 392         break;
 393       }
 394       FUN_tool_mkBnd2d(wi(1), F, Bnd2d(1));
 395       Standard_Boolean OUTall = Standard_False;
 396       Standard_Boolean oneINother = Standard_False;
 397       Standard_Integer sma,gre; // dummy if !oneINother
 398
 399       for (; itmap.More(); itmap.Next()) {
 400         wi(2) = itmap.Key();
 401         if (wi(1).IsSame(wi(2))) continue;
 402         FUN_tool_mkBnd2d(wi(2), F, Bnd2d(2));
 403
 404         // sta : wi(1) / wi(2)
 405         Standard_Integer sta = FUN_tool_classiBnd2d(Bnd2d);
 406         nite++;
 407         if ((sta == SAME)||(sta == UNKNOWN)) sta = FUN_tool_classiwithp2d(wi);
 408 #ifdef OCCT_DEBUG
 409         if (trc) {cout<<"#wi :";FUN_tool_coutsta(sta,FUN_adds(wi(1)),FUN_adds(wi(2)));}
 410 #endif
 411         if ((sta == SAME)||(sta == UNKNOWN)) return Standard_False;
 412         if ((sta == DIFF) && itmap.More()) {OUTall = Standard_True; continue;}// w(1) OUT w(2)
 413         sma = (sta == oneINtwo) ? 1 : 2;
 414         gre = (sta == oneINtwo) ? 2 : 1;
 415         oneINother = Standard_True;
 416         break;
 417       } // itmap
 418
 419       if (oneINother) {
 420         // Updating map <complWoldw> with :
 421         //  - key = wi(gre),
 422         //    item += wi(sma) && item += item(wi(sma))
 423         //  - unbinding key = (wi(sma))
 424         TopTools_ListOfShape& lwgre = complWoldw.ChangeFind(wi(gre));
 425         lwgre.Append(wi(sma));
 426         TopTools_ListIteratorOfListOfShape itwsma(complWoldw.Find(wi(sma)));
 427         for (; itwsma.More(); itwsma.Next()) lwgre.Append(itwsma.Value());
 428         complWoldw.UnBind(wi(sma));
 429       }
 430       else if (OUTall) {mapWlow.Bind(wi(1),emptylos); complWoldw.UnBind(wi(1));}
 431       else return Standard_False;
 432
 433       ncompl = complWoldw.Extent();
 434       go = (ncompl >= 1);
 435     }
 436     return Standard_True;
 437   } // oneoldW
 438
 439
 440   // -------------
 441   // * noldW > 1 :
 442   // -------------
 443   for (; ite.More(); ite.Next()){
 444     const TopoDS_Wire& oldwi = TopoDS::Wire(ite.Key());
 445     const TopTools_ListOfShape& low = ite.Value();
 446     TopTools_ListIteratorOfListOfShape itlow(low);
 447     if (low.IsEmpty()) mapWlow.Bind(oldwi, emptylos);
 448     else
 449       for (; itlow.More(); itlow.Next()) mapWlow.Bind(itlow.Value(), emptylos);
 450     oldW.Append(oldwi);
 451   }
 452
 453   // classifying wires of <mapoldWnewW> :
 454   // -----------------------------------
 455   // <Owi>            : old wires
 456   // <OBnd2d>         : old wires' bounding boxes
 457   // <Owhassp>(k) : Owi(k) has splits
 458
 459   TopTools_ListOfShape oldWcopy; oldWcopy.Assign(oldW);
 460   for (TopTools_ListIteratorOfListOfShape itoldW(oldW); itoldW.More(); itoldW.Next()) {
 461
 462     TopTools_Array1OfShape Owi(1,2);
 463     Bnd_Array1OfBox2d OBnd2d(1,2);
 464     TColStd_Array1OfBoolean Owhassp(1,2);
 465
 466     Owi(1) = itoldW.Value();
 467     if (oldWcopy.Extent() <1) break;
 468     oldWcopy.RemoveFirst();
 469
 470     Owhassp(1) = !mapoldWnewW.Find(Owi(1)).IsEmpty();
 471     Standard_Boolean Owi1notkey = !mapWlow.IsBound(Owi(1));
 472     if (Owi1notkey && !Owhassp(1)) continue;
 473
 474     FUN_tool_mkBnd2d(Owi(1), F, OBnd2d(1));
 475
 476     // Classifying oldwire(i) with oldwires(j): j = i+1..nwiresofF
 477     Standard_Integer osma,ogre,osta;
 478     TopTools_ListIteratorOfListOfShape itoldWcopy(oldWcopy);
 479     for (; itoldWcopy.More(); itoldWcopy.Next()) {
 480
 481       TopTools_Array1OfListOfShape newwi(1,2);
 482       Owi(2) = TopoDS::Wire(itoldWcopy.Value());
 483       Standard_Boolean Owi2notkey = !mapWlow.IsBound(Owi(2));
 484       Owhassp(2) = !mapoldWnewW.Find(Owi(2)).IsEmpty();
 485       if (Owi2notkey && !Owhassp(2)) continue;
 486       FUN_tool_mkBnd2d(Owi(2), F, OBnd2d(2));
 487
 488       // <osma>, <ogre> :
 489       // ----------------
 490       // Classifying Ow<i> with Ow<j> :
 491       osta = FUN_tool_classiBnd2d(OBnd2d);
 492       if ((osta == SAME)||(osta == UNKNOWN)) osta = FUN_tool_classiwithp2d(Owi);
 493 #ifdef OCCT_DEBUG
 494       if (trc) {cout<<"wi : "; FUN_tool_coutsta(osta,FUN_adds(Owi(1)),FUN_adds(Owi(2)));}
 495 #endif
 496       if ((osta == SAME)||(osta == UNKNOWN)) return Standard_False;
 497       if (osta == DIFF)                    continue; // Ow(1), Ow(2) are disjoint
 498       // Owi<sma> is IN Owi<grea>
 499       osma = (osta == oneINtwo) ? 1 : 2;
 500       ogre = (osta == oneINtwo) ? 2 : 1;
 501
 502       // Owhassp<k>  : newwi<k> = splits (Owi<k>)
 503       // !Owhassp<k> : newwi<k> = Owi<k>
 504       for (Standard_Integer i = 1; i <= 2; i++) {
 505         const TopoDS_Shape& owi = Owi(i);
 506         if (!Owhassp(i)) newwi(i).Append(owi);
 507         else             newwi(i) = mapoldWnewW.Find(owi);
 508       }
 509
 510       //
 511       // classifying wires of newwi<sma> with wires of newwi<gre> :
 512       //
 513       Standard_Integer sta, sma, gre;
 514       TopTools_ListIteratorOfListOfShape itnwi(newwi(osma));
 515       for (; itnwi.More(); itnwi.Next()) {
 516         // <wi>    : new wires
 517         // <Bnd2d> : new wires' bounding boxes
 518         TopTools_Array1OfShape wi(1,2);
 519         Bnd_Array1OfBox2d Bnd2d(1,2);
 520
 521         wi(1) = itnwi.Value(); // wi(1) in {newwi(osma)}
 522         Standard_Boolean wi1notkey = !mapWlow.IsBound(wi(1));
 523         if (wi1notkey) continue;
 524
 525         if (!Owhassp(osma)) Bnd2d(1).Add(OBnd2d(osma));
 526         else               FUN_tool_mkBnd2d(wi(1), F, Bnd2d(1));
 527
 528         TopTools_ListIteratorOfListOfShape itnwj(newwi(ogre));
 529         for (; itnwj.More(); itnwj.Next()) {
 530
 531           wi(2) = itnwj.Value(); // wi(2) in {newwi(ogre)}
 532           Standard_Boolean wi2notkey = !mapWlow.IsBound(wi(2));
 533           if (wi2notkey) continue;
 534
 535           // empty the bounding box
 536           Bnd_Box2d newB2d;
 537           if (!Owhassp(ogre)) newB2d.Add(OBnd2d(ogre));
 538           else                FUN_tool_mkBnd2d(wi(2), F, newB2d);
 539            FUN_tool_UpdateBnd2d(Bnd2d(2),newB2d);
 540
 541           // Classifying wi(1)  with wi(2) :
 542           sta = FUN_tool_classiBnd2d(Bnd2d);
 543 #ifdef OCCT_DEBUG
 544           if (trc) {cout<<"wi : "; FUN_tool_coutsta(sta,STATIC_mapw.FindIndex(wi(1)),
 545                                                     STATIC_mapw.FindIndex(wi(2)));}
 546 #endif
 547           if ((sta == SAME)||(sta == UNKNOWN)) sta = FUN_tool_classiwithp2d(wi);
 548           if ((sta == SAME)||(sta == UNKNOWN)) return Standard_False;
 549           if (sta == DIFF)                   continue;
 550           // wi<sma> is IN wi<grea>
 551           sma = (sta == oneINtwo) ? 1 : 2;
 552           gre = (sta == oneINtwo) ? 2 : 1;
 553
 554           // Updating map <mapWlow> with :
 555           //  - key = wi(gre),
 556           //    item += wi(sma) && item += item(wi(sma))
 557           //  - unbinding key = (wi(sma))
 558           TopTools_ListOfShape& lwgre = mapWlow.ChangeFind(wi(gre));
 559           lwgre.Append(wi(sma));
 560           TopTools_ListIteratorOfListOfShape itwsma(mapWlow.Find(wi(sma)));
 561           for (; itwsma.More(); itwsma.Next()) lwgre.Append(itwsma.Value());
 562           mapWlow.UnBind(wi(sma));
 563           break;
 564           // wi<sma> IN wi<gre>, wi<sma> is OUT {newwi<gre>} / wi<gre>
 565           // wi<sma> is classified / all newwires.
 566         }
 567       } // itnwi(newwi(sma))
 568     }// itoldWcopy
 569   } // itoldW
 570   return Standard_True;
 571 }
 572 // ------------------------------------------------------------
 573 // -------------------- building up faces ---------------------
 574 // ------------------------------------------------------------
 575
 576 Standard_EXPORT Standard_Boolean FUN_tool_MakeFaces(const TopoDS_Face& theFace,
 577                                        TopTools_DataMapOfShapeListOfShape& mapWlow,
 578                                        TopTools_ListOfShape& aListOfFaces)
 579 {
 580 #ifdef OCCT_DEBUG
 581   Standard_Boolean trc = TopOpeBRepTool_GettraceREGUFA();
 582   if (trc) cout<<"** MakeFaces :"<<endl;
 583 #endif
 584   Standard_Boolean toreverse = M_REVERSED(theFace.Orientation());
 585   TopoDS_Face F = TopoDS::Face(theFace.Oriented(TopAbs_FORWARD));
 586   BRep_Builder BB;
 587
 588   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape itm(mapWlow);
 589   for (; itm.More(); itm.Next()) {
 590     const TopoDS_Wire& wi = TopoDS::Wire(itm.Key());
 591     TopoDS_Shape FF = F.EmptyCopied(); BB.Add(FF,wi);
 592 //    BB.MakeFace(FF); // put a TShape
 593
 594     TopTools_ListIteratorOfListOfShape itlow(itm.Value());
 595     for (; itlow.More(); itlow.Next()) {
 596       const TopoDS_Wire& wwi = TopoDS::Wire(itlow.Value());
 597       BB.Add(FF,wwi);
 598     }
 599
 600     if (toreverse) FF.Orientation(TopAbs_REVERSED);
 601     aListOfFaces.Append(FF);
 602   }
 603
 604 #ifdef OCCT_DEBUG
 605   if (trc) {
 606     cout<<"sp(fa"<<FUN_adds(theFace)<<")=";
 607     TopTools_ListIteratorOfListOfShape it(aListOfFaces);
 608     for (; it.More(); it.Next()) cout<<" fa"<<FUN_adds(it.Value());
 609     cout<<endl;
 610   }
 611 #endif
 612
 613   return Standard_True;
 614 }*/
 615
 616 Standard_EXPORT Standard_Boolean FUN_tool_ClassifW(const TopoDS_Face& F,
 617                                       const TopTools_DataMapOfShapeListOfShape& mapOwNw,
 618                                       TopTools_DataMapOfShapeListOfShape& mapWlow)
 619 {
 620 #ifdef OCCT_DEBUG
 621   Standard_Boolean trc = TopOpeBRepTool_GettraceREGUFA();
 622   if (trc) cout<<"** ClassifW :"<<endl;
 623 #endif
 624   Standard_Real tolF = BRep_Tool::Tolerance(F);
 625   Standard_Real toluv = TopOpeBRepTool_TOOL::TolUV(F,tolF);
 626   TopoDS_Shape aLocalShape = F.Oriented(TopAbs_FORWARD);
 627   TopoDS_Face FFOR = TopoDS::Face(aLocalShape);
 628 //  TopoDS_Face FFOR = TopoDS::Face(F.Oriented(TopAbs_FORWARD));
 629   TopOpeBRepTool_CLASSI CLASSI; CLASSI.Init2d(FFOR);
 630
 631   TopTools_ListOfShape null;
 632   TopTools_ListOfShape oldW;
 633   Standard_Integer noldW = mapOwNw.Extent();
 634   TopTools_DataMapIteratorOfDataMapOfShapeListOfShape itm(mapOwNw);
 635
 636   // noldW = 1
 637   // ---------
 638   if (noldW == 1) {
 639     const TopTools_ListOfShape& low = itm.Value();
 640     Standard_Boolean ok = CLASSI.Classilist(low,mapWlow);
 641     if (!ok) return Standard_False;
 642     return Standard_True;
 643   }
 644
 645   // noldW > 1
 646   // ---------
 647   TopTools_ListOfShape lOws;
 648   for (; itm.More(); itm.Next()){
 649     const TopoDS_Shape& owi = itm.Key();
 650     lOws.Append(owi);
 651     const TopTools_ListOfShape& low = itm.Value();
 652     TopTools_ListOfShape lwresu; FUN_addOwlw(owi,low,lwresu);
 653     TopTools_ListIteratorOfListOfShape itw(lwresu);
 654     for (; itw.More(); itw.Next()) mapWlow.Bind(itw.Value(), null);
 655   }//itm(mapOwNw)
 656
 657   TopTools_MapOfShape mapdone;
 658   Standard_Integer nOw = noldW;
 659   Standard_Integer nite = 0, nitemax = Standard_Integer(nOw*(nOw-1)/2);
 660   while (nite <= nitemax){
 661     nOw = lOws.Extent();
 662     if (nOw == 0) break;
 663
 664     TopTools_ListIteratorOfListOfShape itOw(lOws);
 665     const TopoDS_Shape& Ow1 = itOw.Value();
 666     Standard_Boolean isb1 = mapWlow.IsBound(Ow1);
 667     isb1 = isb1 || !mapdone.Contains(Ow1);
 668     if (!isb1) continue;
 669
 670     const TopTools_ListOfShape& lw1 = mapOwNw.Find(Ow1);
 671
 672     if (nOw == 1) {
 673       // all wires of <mapWs> have been treated, except the last one
 674       // if (nw1 == 0) mapWlow binds already (Ow1,null);
 675       // else         {mapWlow binds already (w1k,null), w1k in lw1}
 676       break;
 677     }//nOw == 1
 678
 679     itOw.Next();
 680     Standard_Boolean OUTall = Standard_False;
 681     TopoDS_Shape Ow2;
 682     Standard_Integer sta12 = UNKNOWN;
 683     for (; itOw.More(); itOw.Next()){
 684       Ow2 = itOw.Value();
 685       Standard_Boolean isb2 = mapWlow.IsBound(Ow2);
 686       isb2 = isb2 || !mapdone.Contains(Ow2);
 687       if (!isb2) continue;
 688       Standard_Integer stabnd2d12 = CLASSI.ClassiBnd2d(Ow1,Ow2,toluv,Standard_True);
 689       sta12 = CLASSI.Classip2d(Ow1,Ow2, stabnd2d12);
 690       if      (sta12 == DIFF)                       {OUTall = Standard_True; continue;}
 691       else if ((sta12 == UNKNOWN)||(sta12 == SAME)) return Standard_False;
 692       break;
 693     }
 694     if (OUTall) {
 695       // if (nw1 == 0) mapWlow binds already (Ow1,null);
 696       // else         {mapWlow binds already (w1k,null), w1k in lw1}
 697       TopTools_ListOfShape ldone; FUN_addOwlw(Ow1,lw1,ldone);
 698       TopTools_ListIteratorOfListOfShape itw(ldone);
 699       for (; itw.More(); itw.Next()) mapdone.Add(itw.Value());
 700 #ifdef OCCT_DEBUG
 701       if (trc) cout<<"old wires :wi"<<FUN_adds(Ow1)<<" is OUT all old wires"<<endl;
 702 #endif
 703       lOws.RemoveFirst();
 704     }//OUTall
 705     else {
 706 #ifdef OCCT_DEBUG
 707       if (trc) {cout<<"old wires :wi -> ";
 708                 FUN_tool_coutsta(sta12,FUN_adds(Ow1),FUN_adds(Ow2));
 709                 cout<<endl;}
 710 #endif
 711       const TopTools_ListOfShape& lw2 = mapOwNw.Find(Ow2);
 712
 713       TopTools_ListOfShape lw1r; FUN_addOwlw(Ow1,lw1,lw1r);
 714       TopTools_ListOfShape lw2r; FUN_addOwlw(Ow2,lw2,lw2r);
 715       TopTools_ListOfShape lgre,lsma;
 716       if (sta12 == oneINtwo) {lgre.Append(lw2r); lsma.Append(lw1r);}
 717       if (sta12 == twoINone) {lgre.Append(lw1r); lsma.Append(lw2r);}
 718
 719       TopTools_ListIteratorOfListOfShape itsma(lsma);
 720       for (; itsma.More(); itsma.Next()){
 721         const TopoDS_Shape& wsma = itsma.Value();
 722         Standard_Boolean isbsma = mapWlow.IsBound(wsma);
 723         isbsma = isbsma || !mapdone.Contains(wsma);
 724         if (!isbsma) continue;
 725
 726         TopTools_ListIteratorOfListOfShape itgre(lgre);
 727         for (; itgre.More(); itgre.Next()){
 728           const TopoDS_Shape& wgre = itgre.Value();
 729           Standard_Boolean isbgre = mapWlow.IsBound(wgre);
 730           isbgre = isbgre || !mapdone.Contains(wgre);
 731           if (!isbgre) continue;
 732
 733           Standard_Integer stabnd2d = CLASSI.ClassiBnd2d(wsma,wgre,toluv,Standard_True);
 734           Standard_Integer sta = CLASSI.Classip2d(wsma,wgre, stabnd2d);
 735 #ifdef OCCT_DEBUG
 736       if (trc) {cout<<" wires :wi -> ";
 737                 FUN_tool_coutsta(sta,FUN_adds(wsma),FUN_adds(wgre));
 738                 cout<<endl;}
 739 #endif
 740
 741           if      (sta == DIFF) continue;
 742           else if (sta == oneINtwo) {// wsma IN wgre
 743             mapWlow.ChangeFind(wgre).Append(mapWlow.ChangeFind(wsma));
 744             mapWlow.UnBind(wsma);
 745           }
 746           else if (sta == twoINone) {// wgre IN wsma
 747             mapWlow.ChangeFind(wsma).Append(mapWlow.ChangeFind(wgre));
 748             mapWlow.UnBind(wgre);
 749           }
 750           else return Standard_False;
 751         }//itgre
 752       }//itsma
 753       lOws.RemoveFirst();
 754     } //!OUTall
 755   }//nite
 756   return Standard_True;
 757 }
 758
 759 //=======================================================================
 760 //function : RegularizeFace
 761 //purpose  :
 762 //=======================================================================
 763
 764 Standard_Boolean TopOpeBRepTool::RegularizeFace(const TopoDS_Face& theFace,
 765                                    const TopTools_DataMapOfShapeListOfShape& mapoldWnewW,
 766                                    TopTools_ListOfShape& newFaces)
 767 {
 768   // <mapWlow>
 769   // ---------
 770   // key = wire <w>,
 771   // item = if the new face has holes, the item contains wires
 772   //        classified IN the area described by the boundary <w>
 773   //        on <aFace>,
 774   //        else : the item is an empty list, <w> describes the
 775   //        whole new face.
 776   TopTools_DataMapOfShapeListOfShape mapWlow;
 777
 778   // Classifying  wires :
 779   // -------------------
 780   //  Standard_Boolean classifok = FUN_tool_ClassifW(theFace, mapoldWnewW, mapWlow);
 781   TopoDS_Shape aLocalShape = theFace.Oriented(TopAbs_FORWARD);
 782   TopoDS_Face aFace = TopoDS::Face(aLocalShape);
 783 //  TopoDS_Face aFace = TopoDS::Face(theFace.Oriented(TopAbs_FORWARD));
 784
 785   Standard_Boolean classifok = FUN_tool_ClassifW(aFace, mapoldWnewW, mapWlow);
 786   if (!classifok) return Standard_False;
 787
 788   // <aListOfFaces>
 789   // -------------
 790   Standard_Boolean facesbuilt = TopOpeBRepTool_TOOL::WireToFace(theFace, mapWlow, newFaces);
 791   if (!facesbuilt) return Standard_False;
 792   return Standard_True;
 793 }