0026937: Eliminate NO_CXX_EXCEPTION macro support
[occt.git] / src / ShapeAnalysis / ShapeAnalysis_WireOrder.cxx
1 // Copyright (c) 1999-2014 OPEN CASCADE SAS
2 //
3 // This file is part of Open CASCADE Technology software library.
4 //
5 // This library is free software; you can redistribute it and/or modify it under
6 // the terms of the GNU Lesser General Public License version 2.1 as published
7 // by the Free Software Foundation, with special exception defined in the file
8 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
9 // distribution for complete text of the license and disclaimer of any warranty.
10 //
11 // Alternatively, this file may be used under the terms of Open CASCADE
12 // commercial license or contractual agreement.
13
14 //:o4 abv 17.02.99: r0301_db.stp #53082: treatment of open wires implemented
15 // pdn 11.03.99 S4135 changing reordering algorithm in order to make it independent on tolerance
16 //szv#4 S4163
17 //    pdn 09.05.99: S4174: preserve order of edges for complete torus
18
19 #include <gp_Pnt.hxx>
20 #include <gp_XY.hxx>
21 #include <gp_XYZ.hxx>
22 #include <Precision.hxx>
23 #include <ShapeAnalysis_WireOrder.hxx>
24 #include <Standard_TypeMismatch.hxx>
25 #include <TColgp_Array1OfXYZ.hxx>
26 #include <TColStd_Array1OfBoolean.hxx>
27 #include <TColStd_Array1OfInteger.hxx>
28 #include <TColStd_HSequenceOfInteger.hxx>
29 #include <TColStd_SequenceOfInteger.hxx>
30 #include <TColStd_SequenceOfTransient.hxx>
31
32 //=======================================================================
33 //function : ShapeAnalysis_WireOrder
34 //purpose  : 
35 //=======================================================================
36 ShapeAnalysis_WireOrder::ShapeAnalysis_WireOrder()
37   : myKeepLoops(Standard_False) , myGap (0.) , myStat (0)  , myMode (Standard_True) 
38 {
39   myTol = Precision::Confusion();
40   Clear();
41 }
42
43 //=======================================================================
44 //function : ShapeAnalysis_WireOrder
45 //purpose  : 
46 //=======================================================================
47
48 ShapeAnalysis_WireOrder::ShapeAnalysis_WireOrder(const Standard_Boolean mode3d,
49                                                  const Standard_Real tol)
50   : myKeepLoops(Standard_False), myTol (tol), myGap (0.), myStat (0), myMode (mode3d)
51 {
52   Clear();
53 }
54
55 //=======================================================================
56 //function : SetMode
57 //purpose  : 
58 //=======================================================================
59
60 void ShapeAnalysis_WireOrder::SetMode(const Standard_Boolean mode3d,const Standard_Real tol) 
61 {
62   if (mode3d != myMode) Clear();
63   myOrd.Nullify();  myStat = 0; myGap = 0.;
64   myMode = mode3d;
65   myTol = (tol > 0.)? tol : 1.e-08; //szv#4:S4163:12Mar99 optimized
66 }
67
68 //=======================================================================
69 //function : Tolerance
70 //purpose  : 
71 //=======================================================================
72
73 Standard_Real ShapeAnalysis_WireOrder::Tolerance() const
74 {
75   return myTol;
76 }
77
78 //=======================================================================
79 //function : Clear
80 //purpose  : 
81 //=======================================================================
82
83 void ShapeAnalysis_WireOrder::Clear() 
84 {
85   myXYZ = new TColgp_HSequenceOfXYZ();
86   myStat = 0;
87   myGap = 0.;
88 }
89
90 //=======================================================================
91 //function : Add
92 //purpose  : 
93 //=======================================================================
94
95 void ShapeAnalysis_WireOrder::Add(const gp_XYZ& start3d,const gp_XYZ& end3d) 
96 {
97   //szv#4:S4163:12Mar99 waste raise
98   //if (!myMode)
99     //throw Standard_TypeMismatch("ShapeAnalysis_WireOrder : AddXYZ");
100   if (myMode) {
101     myXYZ->Append (start3d);  myXYZ->Append (end3d);
102   }
103 }
104
105 //=======================================================================
106 //function : Add
107 //purpose  : 
108 //=======================================================================
109
110 void ShapeAnalysis_WireOrder::Add(const gp_XY& start2d,const gp_XY& end2d) 
111 {
112   //szv#4:S4163:12Mar99 waste raise
113   //if ( myMode)
114     //throw Standard_TypeMismatch("ShapeAnalysis_WireOrder : AddXY");
115   if (!myMode) {
116     gp_XYZ val;
117     val.SetCoord (start2d.X(),start2d.Y(),0.);
118     myXYZ->Append (val);
119     val.SetCoord (end2d.X(),end2d.Y(),0.);
120     myXYZ->Append (val);
121   }
122 }
123
124 //=======================================================================
125 //function : NbEdges
126 //purpose  : 
127 //=======================================================================
128
129 Standard_Integer ShapeAnalysis_WireOrder::NbEdges() const
130 {
131   return myXYZ->Length() / 2;
132 }
133
134
135 static Standard_Real DISTABS (const gp_XYZ& v1, const gp_XYZ& v2)
136 {
137   return Abs (v1.X() - v2.X()) + Abs (v1.Y() - v2.Y()) + Abs (v1.Z() - v2.Z());
138 }
139
140 //  La routine qui suit gere les boucles internes a un wire. Questce a dire ?
141 //  Un wire normalement chaine (meme pas dans l ordre et avec des inverses)
142 //   balaie toutes ses edges au moins une fois dans une seule liste
143 //  En 3D il peut y avoir des COUTURES ... une, mais evt plusieurs ...
144 //  En ce cas le critere fin-debut peut definir des sous-parties fermees du
145 //  wire, ce sont les boucles en question
146 //  Exemple (cylindre gentil) : la couture (balayee deux fois) : 1 boucle
147 //   chaque limite (haute et basse) definit aussi une boucle (1 edge ou +)
148
149 //  En cours de chainage, il faut donc :
150 //  1/ sauter la boucle, pour ne pas la rebalayer 36 fois : NextFree y pourvoit
151 //    en notant les tetes de boucles, on n a pas le droit de les revoir
152 //   NB: ca marche car en cours de constitution de liste, on s interdit de
153 //   repasser plus d une fois sur chaque edge (test fol-pre non nul)
154 //  2/ reprendre les boucles pour les fusionner : pas encore fait
155 //   (pour l instant, on imprime un petit message, c est tout)
156
157 //=======================================================================
158 //function : KeepLoopsMode
159 //purpose  : 
160 //=======================================================================
161
162 Standard_Boolean& ShapeAnalysis_WireOrder::KeepLoopsMode()
163 {
164   return myKeepLoops;
165 }
166
167 //=======================================================================
168 //function : Perform
169 //purpose  : 
170 //=======================================================================
171
172 static Standard_Boolean IsBetter(const Standard_Integer first,
173                                  const Standard_Integer second)
174 {
175   //rln 23.03.99 bm4_al_eye.stp, entity 5281
176   //Order in the file is better even if another order has the same distance
177   //Lexicograhical order of preference: 0 > 2 > 1 > 3
178   if (first == 0 &&  second  > 0                ) return Standard_True;
179   if (first == 2 && (second == 1 || second == 3)) return Standard_True;
180   if (first == 1 &&  second == 3                ) return Standard_True;
181   return Standard_False;
182 }
183
184 void ShapeAnalysis_WireOrder::Perform(const Standard_Boolean /*closed*/) 
185 {
186   myStat = 0;
187   Standard_Integer i, nb = NbEdges();
188   if(nb == 0)
189     return; // no edges loaded, nothing to do -- return with status OK
190   myOrd = new TColStd_HArray1OfInteger(1,nb);
191   myOrd->Init(0);
192
193   Handle(TColStd_HSequenceOfInteger) seq = new TColStd_HSequenceOfInteger;
194   TColStd_SequenceOfTransient loops;
195   
196   TColgp_Array1OfXYZ debs(0,nb);
197   TColgp_Array1OfXYZ fins(0,nb);
198   
199   TColStd_Array1OfBoolean idone (1, nb);
200   idone.Init (Standard_False);
201   
202 //   Calcul des precedents-suivants
203   for (i = 1; i <= nb; i ++) {
204     debs(i) = myXYZ->Value(2*i-1);
205     fins(i) = myXYZ->Value(2*i);
206   }
207
208   Standard_Real tol2 = Precision::SquareConfusion();
209   idone(1) = Standard_True;
210   gp_Pnt wireFirst = debs(1);
211   gp_Pnt wireLast  = fins(1);
212   seq->Append(1);
213   Standard_Boolean done = Standard_False;
214   
215   //pdn 11.03.99 S4135 constructing closed loops of edges
216   while(!done) {
217     Standard_Integer resultType = 3;
218     Standard_Real distmin = RealLast();
219     Standard_Integer ledge = 0;
220     Standard_Boolean found = Standard_False;
221     Standard_Real closeDist = wireFirst.SquareDistance(wireLast);
222     
223     for(Standard_Integer iedge = 1; (iedge <= nb) && (distmin||resultType||(resultType!=2)); iedge++)
224       if(!idone(iedge)) {
225         Standard_Real tailhead = wireLast.SquareDistance(debs(iedge));
226         Standard_Real tailtail = wireLast.SquareDistance(fins(iedge));
227         Standard_Real headtail = wireFirst.SquareDistance(fins(iedge));
228         Standard_Real headhead = wireFirst.SquareDistance(debs(iedge));
229         Standard_Real dm1 = tailhead, dm2 = headtail;
230         Standard_Integer res1 = 0, res2 = 2;
231
232         if (tailhead > tailtail) {res1 = 1; dm1 = tailtail;}
233         if (headtail > headhead) {res2 = 3; dm2 = headhead;}
234         Standard_Integer result =0;
235         Standard_Real myMin3d = Min (dm1, dm2);
236         if(fabs(dm1 - dm2) < tol2 ) {
237           Standard_Boolean isB = IsBetter(res1,res2);
238           result = (isB ? res1 : res2);
239         }
240         else 
241           result = ((dm1 > dm2) ? res2 : res1); // 0 > 2 > 1 > 3
242         
243         if (distmin > tol2 || IsBetter(result,resultType))
244           if (myMin3d < distmin || ((myMin3d == distmin || myMin3d < tol2) && IsBetter(result,resultType))) {
245             found = Standard_True;
246             distmin = myMin3d;
247             ledge = iedge;
248             resultType = result;
249           }
250       }
251     if(found) {
252       if (distmin == 0 || distmin < closeDist) {
253         switch(resultType){
254         case 0: seq->Append(ledge); wireLast = fins(ledge); break;
255         case 1: seq->Append(-ledge); wireLast = debs(ledge); break;
256         case 2: seq->Prepend(ledge); wireFirst = debs(ledge); break;
257         case 3: seq->Prepend(-ledge); wireFirst = fins(ledge); break;
258         }
259       } else {
260         //pdn 11.03.99 S4135 closing loop and creating new one
261         loops.Append(seq);
262         seq = new TColStd_HSequenceOfInteger;
263         wireFirst = debs(ledge);
264         wireLast  = fins(ledge);
265         seq->Append(ledge);
266       }
267       idone(ledge) = Standard_True;
268     } else {
269       ledge = -1;
270       for (i = 1 ; i <= nb && ledge == -1; i++)
271         ledge = idone(i) ? ledge : i;
272       if (ledge == -1) 
273         done = 1;
274       else {
275         wireFirst = debs(ledge);
276         wireLast  = fins(ledge);
277         seq->Append(ledge);
278         idone(ledge) = Standard_True;
279       }
280     }
281   }
282   loops.Append(seq);
283
284   Handle(TColStd_HSequenceOfInteger) mainSeq;
285   if (myKeepLoops) {
286     
287     //pdn Keeping the loops, adding one after another.
288     mainSeq = new TColStd_HSequenceOfInteger;
289     for (Standard_Integer ii = 1; ii <= loops.Length(); ii++) {
290       Handle(TColStd_HSequenceOfInteger) subLoop = 
291         Handle(TColStd_HSequenceOfInteger)::DownCast(loops(ii));
292       for (Standard_Integer j = 1; j<= subLoop->Length(); j++)
293         mainSeq->Append(subLoop->Value(j));
294     }
295   }
296   else {
297     //pdn 11.03.99 S4135 connecting loops.
298     mainSeq = Handle(TColStd_HSequenceOfInteger)::DownCast(loops.First());
299     loops.Remove(1);
300     while(loops.Length()) {
301       Standard_Real minLoopDist = RealLast();
302       Standard_Integer loopNum=0;
303       Standard_Integer loopShift=0;
304       Standard_Boolean loopDirect=0;
305       Standard_Integer numInLoop=0;
306       for(i = 1; i <= loops.Length(); i++) {
307         Handle(TColStd_HSequenceOfInteger) loop = Handle(TColStd_HSequenceOfInteger)::DownCast(loops.Value(i));
308         Standard_Integer num = loop->Length();
309         Standard_Integer LocShift=0;
310         Standard_Integer LocNumInLoop=0;
311         Standard_Boolean LocDirect = Standard_False;
312         Standard_Real minLocDist = RealLast();
313         for(Standard_Integer ibegin = 1; ibegin <= loop->Length(); ibegin++) {
314           Standard_Integer iend = (ibegin==1 ? num : ibegin -1);
315           gp_Pnt loopFirst = (loop->Value(ibegin) > 0 ? debs(loop->Value(ibegin)) : fins(-loop->Value(ibegin)));
316           gp_Pnt loopLast = (loop->Value(iend) > 0 ? fins(loop->Value(iend)) : debs(-loop->Value(iend)));
317           Standard_Real distmin = RealLast();
318           Standard_Integer lloop=0;
319           Standard_Boolean direct = Standard_False;
320           for(Standard_Integer j = 1; (j <= mainSeq->Length())&& distmin; j++) {
321             Standard_Integer k = (j == mainSeq->Length()? 1 : j+1);
322             gp_Pnt first = (mainSeq->Value(j) > 0 ? fins(mainSeq->Value(j)) : debs(-mainSeq->Value(j)));
323             gp_Pnt last  = (mainSeq->Value(k) > 0 ? debs(mainSeq->Value(k)) : fins(-mainSeq->Value(k)));
324             Standard_Real dirDist = loopFirst.SquareDistance(first)+loopLast.SquareDistance(last);
325             Standard_Real revDist = loopFirst.SquareDistance(last)+loopLast.SquareDistance(first);
326             Standard_Real minDist;
327             if((dirDist<tol2)||(dirDist < 2.*revDist)) {
328               minDist = dirDist;
329               revDist = dirDist;
330             }
331             else 
332               minDist = revDist;
333             if(minDist < distmin && Abs(distmin - minDist) > tol2) {
334               distmin = minDist;
335               direct = (dirDist <= revDist);
336               lloop = j;
337             }
338           }
339           if(distmin < minLocDist && Abs(minLocDist - distmin) > tol2) {
340             minLocDist = distmin;
341             LocDirect = direct;
342             LocNumInLoop = lloop;
343             LocShift = ibegin;
344           }
345           
346         }
347         if(minLocDist < minLoopDist && Abs(minLoopDist - minLocDist) > tol2) {
348           minLoopDist = minLocDist;
349           loopNum = i;
350           loopDirect = LocDirect;
351           numInLoop = LocNumInLoop;
352           loopShift = LocShift;
353         }
354       }
355       
356       Handle(TColStd_HSequenceOfInteger) loop = Handle(TColStd_HSequenceOfInteger)::DownCast(loops.Value(loopNum));
357       Standard_Integer factor = (loopDirect ? 1: -1);
358       // skl : in the next block for{} I change "i" to "ii"
359       for(Standard_Integer ii = 1; ii <= loop->Length(); ii++) {
360         Standard_Integer num = (ii+loopShift-1>loop->Length() ? ii+loopShift-1-loop->Length() : ii+loopShift-1);
361         mainSeq->InsertAfter(numInLoop+ii-1,loop->Value(num)*factor);
362       }
363       loops.Remove(loopNum);
364     }
365   }
366   
367   Standard_Integer stTmp=0;
368   for(i = 1; i <= mainSeq->Length(); i++) {
369     if(i!=mainSeq->Value(i))
370       if(stTmp>=0) stTmp = (mainSeq->Value(i) > 0 ? 1 : -1);
371     myOrd->SetValue(i,mainSeq->Value(i));
372   }
373   if (stTmp == 0) {
374     myStat = stTmp;
375     return;
376   }
377   else {//check if edges were only shifted in reverse or forward, not reordered
378     Standard_Boolean isShiftReverse = Standard_True, isShiftForward = Standard_True;
379     Standard_Integer tmpFirst = 0, tmpSecond = 0, length = mainSeq->Length();
380     for(i = 1; i <= length - 1; i++) {
381       tmpFirst = mainSeq->Value(i);
382       tmpSecond = mainSeq->Value(i+1);
383       if (!(tmpSecond - tmpFirst == 1 || (tmpFirst == length && tmpSecond == 1)))
384         isShiftForward = Standard_False;
385       if (!(tmpFirst - tmpSecond == 1 || (tmpSecond == length && tmpFirst == 1)))
386         isShiftReverse = Standard_False;
387     }
388     tmpFirst = mainSeq->Value(length);
389     tmpSecond = mainSeq->Value(1);
390     if (!(tmpSecond - tmpFirst == 1 || (tmpFirst == length && tmpSecond == 1)))
391       isShiftForward = Standard_False;
392     if (!(tmpFirst - tmpSecond == 1 || (tmpSecond == length && tmpFirst == 1)))
393       isShiftReverse = Standard_False;
394     if (isShiftForward || isShiftReverse)
395       stTmp = 3;
396     myStat = stTmp;
397     return;
398   }
399 }
400
401 //=======================================================================
402 //function : IsDone
403 //purpose  : 
404 //=======================================================================
405
406  Standard_Boolean ShapeAnalysis_WireOrder::IsDone() const
407 {
408   return  !myOrd.IsNull();
409 }
410
411 //=======================================================================
412 //function : Status
413 //purpose  : 
414 //=======================================================================
415
416  Standard_Integer ShapeAnalysis_WireOrder::Status() const
417 {
418   return  myStat;
419 }
420
421 //=======================================================================
422 //function : Ordered
423 //purpose  : 
424 //=======================================================================
425
426  Standard_Integer ShapeAnalysis_WireOrder::Ordered(const Standard_Integer n) const
427 {
428   if (myOrd.IsNull() || myOrd->Upper() < n) return n;
429   Standard_Integer ord = myOrd->Value(n);
430   return (ord == 0 ? n : ord);
431 }
432
433 //=======================================================================
434 //function : XYZ
435 //purpose  : 
436 //=======================================================================
437
438  void ShapeAnalysis_WireOrder::XYZ(const Standard_Integer num,gp_XYZ& start3d,gp_XYZ& end3d) const
439 {
440   if (num > 0) {
441     start3d = myXYZ->Value (2*num-1);
442     end3d   = myXYZ->Value (2*num);
443   } else {
444     start3d = myXYZ->Value (-2*num);
445     end3d   = myXYZ->Value (-2*num-1);
446   }
447 }
448
449 //=======================================================================
450 //function : XY
451 //purpose  : 
452 //=======================================================================
453
454  void ShapeAnalysis_WireOrder::XY(const Standard_Integer num,gp_XY& start2d,gp_XY& end2d) const
455 {
456   const gp_XYZ& st2d = myXYZ->Value ( (num > 0 ? 2*num-1 : -2*num) );
457   start2d.SetCoord (st2d.X(),st2d.Y());
458   const gp_XYZ& en2d = myXYZ->Value ( (num > 0 ? 2*num   : -2*num -1) );
459   end2d.SetCoord   (en2d.X(),en2d.Y());
460 }
461
462 //=======================================================================
463 //function : Gap
464 //purpose  : 
465 //=======================================================================
466
467  Standard_Real ShapeAnalysis_WireOrder::Gap(const Standard_Integer num) const
468 {
469   if (num == 0) return myGap;
470   Standard_Integer n1 = Ordered (num);
471   Standard_Integer n0 = Ordered (num == 1 ? NbEdges() : num-1);
472 //  Distance entre fin (n0) et debut (n1)
473   return DISTABS (myXYZ->Value( (n0 > 0 ? 2*n0   : -2*n0 -1) ) ,
474                   myXYZ->Value( (n1 > 0 ? 2*n1-1 : -2*n1   ) ) );
475 ////  return (myXYZ->Value(2*n0)).Distance (myXYZ->Value(2*n1-1));
476 }
477
478 //=======================================================================
479 //function : SetChains
480 //purpose  : 
481 //=======================================================================
482
483 void ShapeAnalysis_WireOrder::SetChains(const Standard_Real gap) 
484 {
485   Standard_Integer n0 = 0, n1, n2, nb = NbEdges(); //szv#4:S4163:12Mar99 o0,o1,o2 not needed
486   if (nb == 0) return;
487   TColStd_SequenceOfInteger chain;
488   n0 = 0;
489   chain.Append (1);    // On demarre la partie
490   gp_XYZ f3d, l3d, f13d, l13d; //szv#4:S4163:12Mar99 f03d,l03d unused
491   for (n1 = 1; n1 <= nb; n1 ++) {
492     if (n0 == 0) {    // nouvelle boucle
493       n0 = n1;
494       //szv#4:S4163:12Mar99 optimized
495       XYZ ( Ordered(n0), f13d, l13d );
496     }
497     //szv#4:S4163:12Mar99 optimized
498     n2 = (n1 == nb)? n0 : (n1 + 1);
499     XYZ ( Ordered(n2), f3d, l3d );
500     if (!f3d.IsEqual (l13d,gap)) { chain.Append (n2);  n0 = 0; }
501     f13d = f3d;  l13d = l3d;
502   }
503   nb = chain.Length();
504   if (nb == 0) return;
505   myChains = new TColStd_HArray1OfInteger (1,nb);
506   for (n1 = 1; n1 <= nb; n1 ++)  myChains->SetValue (n1,chain.Value(n1));
507 }
508
509 //=======================================================================
510 //function : NbChains
511 //purpose  : 
512 //=======================================================================
513
514  Standard_Integer ShapeAnalysis_WireOrder::NbChains() const
515 {
516   return (myChains.IsNull() ? 0 : myChains->Length());
517 }
518
519 //=======================================================================
520 //function : Chain
521 //purpose  : 
522 //=======================================================================
523
524  void ShapeAnalysis_WireOrder::Chain(const Standard_Integer num,Standard_Integer& n1,Standard_Integer& n2) const
525 {
526   n1 = n2 = 0;
527   if (myChains.IsNull()) return;
528   Standard_Integer nb = myChains->Upper();
529   if (num == 0 || num > nb) return;
530   n1 = myChains->Value (num);
531   if (num == nb) n2 = NbEdges();
532   else n2 = myChains->Value (num+1) - 1;
533 }
534
535 //=======================================================================
536 //function : SetCouples
537 //purpose  : 
538 //=======================================================================
539
540  void ShapeAnalysis_WireOrder::SetCouples(const Standard_Real /*gap*/) 
541 {
542 #ifdef OCCT_DEBUG
543   cout<<"ShapeAnalysis_WireOrder:SetCouple not yet implemented"<<endl;
544 #endif
545 }
546
547 //=======================================================================
548 //function : NbCouples
549 //purpose  : 
550 //=======================================================================
551
552  Standard_Integer ShapeAnalysis_WireOrder::NbCouples() const
553 {
554   return (myCouples.IsNull() ? 0 : myCouples->Length());
555 }
556
557 //=======================================================================
558 //function : Couple
559 //purpose  : 
560 //=======================================================================
561
562  void ShapeAnalysis_WireOrder::Couple(const Standard_Integer num,Standard_Integer& n1,Standard_Integer& n2) const
563 {
564   n1 = n2 = 0;
565   if (myCouples.IsNull()) return;
566   Standard_Integer nb = myCouples->Upper();
567   if (num == 0 || num*2 > nb) return;
568   n1 = myCouples->Value (2*num-1);
569   n2 = myCouples->Value (2*num);
570 }
571