1 // Created on: 1991-08-09
3 // Copyright (c) 1991-1999 Matra Datavision
4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
6 // This file is part of Open CASCADE Technology software library.
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.
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
17 // Modified RLE 9 Sep 1993
18 // pmn : modified 28-01-97 : fixed a mistake in LocateParameter (PRO6973)
19 // pmn : modified 4-11-96 : fixed a mistake in BuildKnots (PRO6124)
20 // pmn : modified 28-Jun-96 : fixed a mistake in AntiBoorScheme
21 // xab : modified 15-Jun-95 : fixed a mistake in IsRational
22 // xab : modified 15-Mar-95 : removed Epsilon comparison in IsRational
23 // added RationalDerivatives.
24 // xab : 30-Mar-95 : fixed coupling with lti in RationalDerivatives
25 // xab : 15-Mar-96 : fixed a typo in Eval with extrapolation
26 // jct : 15-Apr-97 : added TangExtendToConstraint
27 // jct : 24-Apr-97 : correction on computation of Tbord and NewFlatKnots
28 // in TangExtendToConstraint; Continuity can be equal to 0
30 #include <BSplCLib.hxx>
32 #include <gp_Pnt2d.hxx>
34 #include <gp_Vec2d.hxx>
35 #include <math_Matrix.hxx>
36 #include <NCollection_LocalArray.hxx>
38 #include <Precision.hxx>
39 #include <Standard_NotImplemented.hxx>
43 typedef TColgp_Array1OfPnt Array1OfPnt;
44 typedef TColStd_Array1OfReal Array1OfReal;
45 typedef TColStd_Array1OfInteger Array1OfInteger;
47 //=======================================================================
48 //class : BSplCLib_LocalMatrix
49 //purpose: Auxiliary class optimizing creation of matrix buffer for
50 // evaluation of bspline (using stack allocation for main matrix)
51 //=======================================================================
53 class BSplCLib_LocalMatrix : public math_Matrix
56 BSplCLib_LocalMatrix (Standard_Integer DerivativeRequest, Standard_Integer Order)
57 : math_Matrix (myBuffer, 1, DerivativeRequest + 1, 1, Order)
59 Standard_OutOfRange_Raise_if (DerivativeRequest > BSplCLib::MaxDegree() ||
60 Order > BSplCLib::MaxDegree()+1 || BSplCLib::MaxDegree() > 25,
61 "BSplCLib: bspline degree is greater than maximum supported");
65 // local buffer, to be sufficient for addressing by index [Degree+1][Degree+1]
66 // (see math_Matrix implementation)
67 Standard_Real myBuffer[27*27];
70 //=======================================================================
73 //=======================================================================
75 void BSplCLib::Hunt (const Array1OfReal& XX,
76 const Standard_Real X,
77 Standard_Integer& Ilc)
79 // replaced by simple dichotomy (RLE)
81 if (XX.Length() <= 1) return;
82 const Standard_Real *px = &XX(Ilc);
89 Standard_Integer Ihi = XX.Upper();
96 while (Ihi - Ilc != 1) {
97 Im = (Ihi + Ilc) >> 1;
98 if (X > px[Im]) Ilc = Im;
103 //=======================================================================
104 //function : FirstUKnotIndex
106 //=======================================================================
108 Standard_Integer BSplCLib::FirstUKnotIndex (const Standard_Integer Degree,
109 const TColStd_Array1OfInteger& Mults)
111 Standard_Integer Index = Mults.Lower();
112 Standard_Integer SigmaMult = Mults(Index);
114 while (SigmaMult <= Degree) {
116 SigmaMult += Mults (Index);
121 //=======================================================================
122 //function : LastUKnotIndex
124 //=======================================================================
126 Standard_Integer BSplCLib::LastUKnotIndex (const Standard_Integer Degree,
127 const Array1OfInteger& Mults)
129 Standard_Integer Index = Mults.Upper();
130 Standard_Integer SigmaMult = Mults(Index);
132 while (SigmaMult <= Degree) {
134 SigmaMult += Mults.Value (Index);
139 //=======================================================================
140 //function : FlatIndex
142 //=======================================================================
144 Standard_Integer BSplCLib::FlatIndex
145 (const Standard_Integer Degree,
146 const Standard_Integer Index,
147 const TColStd_Array1OfInteger& Mults,
148 const Standard_Boolean Periodic)
150 Standard_Integer i, index = Index;
151 const Standard_Integer MLower = Mults.Lower();
152 const Standard_Integer *pmu = &Mults(MLower);
155 for (i = MLower + 1; i <= Index; i++)
160 index += pmu[MLower] - 1;
164 //=======================================================================
165 //function : LocateParameter
166 //purpose : Processing of nodes with multiplicities
167 //pmn 28-01-97 -> compute eventual of the period.
168 //=======================================================================
170 void BSplCLib::LocateParameter
171 (const Standard_Integer , //Degree,
172 const Array1OfReal& Knots,
173 const Array1OfInteger& , //Mults,
174 const Standard_Real U,
175 const Standard_Boolean IsPeriodic,
176 const Standard_Integer FromK1,
177 const Standard_Integer ToK2,
178 Standard_Integer& KnotIndex,
181 Standard_Real uf = 0, ul=1;
183 uf = Knots(Knots.Lower());
184 ul = Knots(Knots.Upper());
186 BSplCLib::LocateParameter(Knots,U,IsPeriodic,FromK1,ToK2,
187 KnotIndex,NewU, uf, ul);
190 //=======================================================================
191 //function : LocateParameter
192 //purpose : For plane nodes
193 // pmn 28-01-97 -> There is a need of the degre to calculate
194 // the eventual period
195 //=======================================================================
197 void BSplCLib::LocateParameter
198 (const Standard_Integer Degree,
199 const Array1OfReal& Knots,
200 const Standard_Real U,
201 const Standard_Boolean IsPeriodic,
202 const Standard_Integer FromK1,
203 const Standard_Integer ToK2,
204 Standard_Integer& KnotIndex,
208 BSplCLib::LocateParameter(Knots, U, IsPeriodic, FromK1, ToK2,
210 Knots(Knots.Lower() + Degree),
211 Knots(Knots.Upper() - Degree));
213 BSplCLib::LocateParameter(Knots, U, IsPeriodic, FromK1, ToK2,
219 //=======================================================================
220 //function : LocateParameter
221 //purpose : Effective computation
222 // pmn 28-01-97 : Add limits of the period as input argument,
223 // as it is imposible to produce them at this level.
224 //=======================================================================
226 void BSplCLib::LocateParameter
227 (const TColStd_Array1OfReal& Knots,
228 const Standard_Real U,
229 const Standard_Boolean IsPeriodic,
230 const Standard_Integer FromK1,
231 const Standard_Integer ToK2,
232 Standard_Integer& KnotIndex,
234 const Standard_Real UFirst,
235 const Standard_Real ULast)
238 Let Knots are distributed as follows (the array is sorted in ascending order):
240 K1, K1,..., K1, K1, K2, K2,..., K2, K2,..., Kn, Kn,..., Kn
241 M1 times M2 times Mn times
243 NbKnots = sum(M1+M2+...+Mn)
244 If U <= K1 then KnotIndex should be equal to M1.
245 If U >= Kn then KnotIndex should be equal to NbKnots-Mn-1.
246 If Ki <= U < K(i+1) then KnotIndex should be equal to sum (M1+M2+...+Mi).
249 Standard_Integer First,Last;
258 Standard_Integer Last1 = Last - 1;
261 Standard_Real Period = ULast - UFirst;
263 while (NewU > ULast )
266 while (NewU < UFirst)
270 BSplCLib::Hunt (Knots, NewU, KnotIndex);
273 const Standard_Integer KLower = Knots.Lower(),
274 KUpper = Knots.Upper();
276 const Standard_Real Eps = Epsilon(Min(Abs(Knots(KUpper)), Abs(U)));
278 const Standard_Real *knots = &Knots(KLower);
280 if ( KnotIndex < Knots.Upper()) {
281 val = NewU - knots[KnotIndex + 1];
282 if (val < 0) val = - val;
283 // <= to be coherent with Segment where Eps corresponds to a bit of error.
284 if (val <= Eps) KnotIndex++;
286 if (KnotIndex < First) KnotIndex = First;
287 if (KnotIndex > Last1) KnotIndex = Last1;
289 if (KnotIndex != Last1) {
290 Standard_Real K1 = knots[KnotIndex];
291 Standard_Real K2 = knots[KnotIndex + 1];
293 if (val < 0) val = - val;
298 if(KnotIndex >= Knots.Upper())
302 K2 = knots[KnotIndex + 1];
304 if (val < 0) val = - val;
309 //=======================================================================
310 //function : LocateParameter
311 //purpose : the index is recomputed only if out of range
312 //pmn 28-01-97 -> eventual computation of the period.
313 //=======================================================================
315 void BSplCLib::LocateParameter
316 (const Standard_Integer Degree,
317 const TColStd_Array1OfReal& Knots,
318 const TColStd_Array1OfInteger* Mults,
319 const Standard_Real U,
320 const Standard_Boolean Periodic,
321 Standard_Integer& KnotIndex,
324 Standard_Integer first,last;
327 first = Knots.Lower();
328 last = Knots.Upper();
331 first = FirstUKnotIndex(Degree,*Mults);
332 last = LastUKnotIndex (Degree,*Mults);
336 first = Knots.Lower() + Degree;
337 last = Knots.Upper() - Degree;
339 if ( KnotIndex < first || KnotIndex > last)
340 BSplCLib::LocateParameter(Knots, U, Periodic, first, last,
341 KnotIndex, NewU, Knots(first), Knots(last));
346 //=======================================================================
347 //function : MaxKnotMult
349 //=======================================================================
351 Standard_Integer BSplCLib::MaxKnotMult
352 (const Array1OfInteger& Mults,
353 const Standard_Integer FromK1,
354 const Standard_Integer ToK2)
356 Standard_Integer MLower = Mults.Lower();
357 const Standard_Integer *pmu = &Mults(MLower);
359 Standard_Integer MaxMult = pmu[FromK1];
361 for (Standard_Integer i = FromK1; i <= ToK2; i++) {
362 if (MaxMult < pmu[i]) MaxMult = pmu[i];
367 //=======================================================================
368 //function : MinKnotMult
370 //=======================================================================
372 Standard_Integer BSplCLib::MinKnotMult
373 (const Array1OfInteger& Mults,
374 const Standard_Integer FromK1,
375 const Standard_Integer ToK2)
377 Standard_Integer MLower = Mults.Lower();
378 const Standard_Integer *pmu = &Mults(MLower);
380 Standard_Integer MinMult = pmu[FromK1];
382 for (Standard_Integer i = FromK1; i <= ToK2; i++) {
383 if (MinMult > pmu[i]) MinMult = pmu[i];
388 //=======================================================================
391 //=======================================================================
393 Standard_Integer BSplCLib::NbPoles(const Standard_Integer Degree,
394 const Standard_Boolean Periodic,
395 const TColStd_Array1OfInteger& Mults)
397 Standard_Integer i,sigma = 0;
398 Standard_Integer f = Mults.Lower();
399 Standard_Integer l = Mults.Upper();
400 const Standard_Integer * pmu = &Mults(f);
402 Standard_Integer Mf = pmu[f];
403 Standard_Integer Ml = pmu[l];
404 if (Mf <= 0) return 0;
405 if (Ml <= 0) return 0;
407 if (Mf > Degree) return 0;
408 if (Ml > Degree) return 0;
409 if (Mf != Ml ) return 0;
413 Standard_Integer Deg1 = Degree + 1;
414 if (Mf > Deg1) return 0;
415 if (Ml > Deg1) return 0;
416 sigma = Mf + Ml - Deg1;
419 for (i = f + 1; i < l; i++) {
420 if (pmu[i] <= 0 ) return 0;
421 if (pmu[i] > Degree) return 0;
427 //=======================================================================
428 //function : KnotSequenceLength
430 //=======================================================================
432 Standard_Integer BSplCLib::KnotSequenceLength
433 (const TColStd_Array1OfInteger& Mults,
434 const Standard_Integer Degree,
435 const Standard_Boolean Periodic)
437 Standard_Integer i,l = 0;
438 Standard_Integer MLower = Mults.Lower();
439 Standard_Integer MUpper = Mults.Upper();
440 const Standard_Integer * pmu = &Mults(MLower);
443 for (i = MLower; i <= MUpper; i++)
445 if (Periodic) l += 2 * (Degree + 1 - pmu[MLower]);
449 //=======================================================================
450 //function : KnotSequence
452 //=======================================================================
454 void BSplCLib::KnotSequence
455 (const TColStd_Array1OfReal& Knots,
456 const TColStd_Array1OfInteger& Mults,
457 TColStd_Array1OfReal& KnotSeq,
458 const Standard_Boolean Periodic)
460 BSplCLib::KnotSequence(Knots,Mults,0,Periodic,KnotSeq);
463 //=======================================================================
464 //function : KnotSequence
466 //=======================================================================
468 void BSplCLib::KnotSequence
469 (const TColStd_Array1OfReal& Knots,
470 const TColStd_Array1OfInteger& Mults,
471 const Standard_Integer Degree,
472 const Standard_Boolean Periodic,
473 TColStd_Array1OfReal& KnotSeq)
476 Standard_Integer Mult;
477 Standard_Integer MLower = Mults.Lower();
478 const Standard_Integer * pmu = &Mults(MLower);
480 Standard_Integer KLower = Knots.Lower();
481 Standard_Integer KUpper = Knots.Upper();
482 const Standard_Real * pkn = &Knots(KLower);
484 Standard_Integer M1 = Degree + 1 - pmu[MLower]; // for periodic
485 Standard_Integer i,j,index = Periodic ? M1 + 1 : 1;
487 for (i = KLower; i <= KUpper; i++) {
491 for (j = 1; j <= Mult; j++) {
497 Standard_Real period = pkn[KUpper] - pkn[KLower];
502 for (i = M1; i >= 1; i--) {
503 KnotSeq(i) = pkn[j] - period;
513 for (i = index; i <= KnotSeq.Upper(); i++) {
514 KnotSeq(i) = pkn[j] + period;
524 //=======================================================================
525 //function : KnotsLength
527 //=======================================================================
528 Standard_Integer BSplCLib::KnotsLength(const TColStd_Array1OfReal& SeqKnots,
529 // const Standard_Boolean Periodic)
530 const Standard_Boolean )
532 Standard_Integer sizeMult = 1;
533 Standard_Real val = SeqKnots(1);
534 for (Standard_Integer jj=2;
535 jj<=SeqKnots.Length();jj++)
537 // test on strict equality on nodes
538 if (SeqKnots(jj)!=val)
547 //=======================================================================
550 //=======================================================================
551 void BSplCLib::Knots(const TColStd_Array1OfReal& SeqKnots,
552 TColStd_Array1OfReal &knots,
553 TColStd_Array1OfInteger &mult,
554 // const Standard_Boolean Periodic)
555 const Standard_Boolean )
557 Standard_Real val = SeqKnots(1);
558 Standard_Integer kk=1;
562 for (Standard_Integer jj=2;jj<=SeqKnots.Length();jj++)
564 // test on strict equality on nodes
565 if (SeqKnots(jj)!=val)
579 //=======================================================================
580 //function : KnotForm
582 //=======================================================================
584 BSplCLib_KnotDistribution BSplCLib::KnotForm
585 (const Array1OfReal& Knots,
586 const Standard_Integer FromK1,
587 const Standard_Integer ToK2)
589 Standard_Real DU0,DU1,Ui,Uj,Eps0,val;
590 BSplCLib_KnotDistribution KForm = BSplCLib_Uniform;
592 Standard_Integer KLower = Knots.Lower();
593 const Standard_Real * pkn = &Knots(KLower);
596 if (Ui < 0) Ui = - Ui;
597 Uj = pkn[FromK1 + 1];
598 if (Uj < 0) Uj = - Uj;
600 if (DU0 < 0) DU0 = - DU0;
601 Eps0 = Epsilon (Ui) + Epsilon (Uj) + Epsilon (DU0);
602 Standard_Integer i = FromK1 + 1;
604 while (KForm != BSplCLib_NonUniform && i < ToK2) {
606 if (Ui < 0) Ui = - Ui;
609 if (Uj < 0) Uj = - Uj;
611 if (DU1 < 0) DU1 = - DU1;
613 if (val < 0) val = -val;
614 if (val > Eps0) KForm = BSplCLib_NonUniform;
616 Eps0 = Epsilon (Ui) + Epsilon (Uj) + Epsilon (DU0);
621 //=======================================================================
622 //function : MultForm
624 //=======================================================================
626 BSplCLib_MultDistribution BSplCLib::MultForm
627 (const Array1OfInteger& Mults,
628 const Standard_Integer FromK1,
629 const Standard_Integer ToK2)
631 Standard_Integer First,Last;
640 Standard_Integer MLower = Mults.Lower();
641 const Standard_Integer *pmu = &Mults(MLower);
643 Standard_Integer FirstMult = pmu[First];
644 BSplCLib_MultDistribution MForm = BSplCLib_Constant;
645 Standard_Integer i = First + 1;
646 Standard_Integer Mult = pmu[i];
648 // while (MForm != BSplCLib_NonUniform && i <= Last) { ???????????JR????????
649 while (MForm != BSplCLib_NonConstant && i <= Last) {
650 if (i == First + 1) {
651 if (Mult != FirstMult) MForm = BSplCLib_QuasiConstant;
653 else if (i == Last) {
654 if (MForm == BSplCLib_QuasiConstant) {
655 if (FirstMult != pmu[i]) MForm = BSplCLib_NonConstant;
658 if (Mult != pmu[i]) MForm = BSplCLib_NonConstant;
662 if (Mult != pmu[i]) MForm = BSplCLib_NonConstant;
670 //=======================================================================
671 //function : KnotAnalysis
673 //=======================================================================
675 void BSplCLib::KnotAnalysis (const Standard_Integer Degree,
676 const Standard_Boolean Periodic,
677 const TColStd_Array1OfReal& CKnots,
678 const TColStd_Array1OfInteger& CMults,
679 GeomAbs_BSplKnotDistribution& KnotForm,
680 Standard_Integer& MaxKnotMult)
682 KnotForm = GeomAbs_NonUniform;
684 BSplCLib_KnotDistribution KSet =
685 BSplCLib::KnotForm (CKnots, 1, CKnots.Length());
688 if (KSet == BSplCLib_Uniform) {
689 BSplCLib_MultDistribution MSet =
690 BSplCLib::MultForm (CMults, 1, CMults.Length());
692 case BSplCLib_NonConstant :
694 case BSplCLib_Constant :
695 if (CKnots.Length() == 2) {
696 KnotForm = GeomAbs_PiecewiseBezier;
699 if (CMults (1) == 1) KnotForm = GeomAbs_Uniform;
702 case BSplCLib_QuasiConstant :
703 if (CMults (1) == Degree + 1) {
704 Standard_Real M = CMults (2);
705 if (M == Degree ) KnotForm = GeomAbs_PiecewiseBezier;
706 else if (M == 1) KnotForm = GeomAbs_QuasiUniform;
712 Standard_Integer FirstKM =
713 Periodic ? CKnots.Lower() : BSplCLib::FirstUKnotIndex (Degree,CMults);
714 Standard_Integer LastKM =
715 Periodic ? CKnots.Upper() : BSplCLib::LastUKnotIndex (Degree,CMults);
717 if (LastKM - FirstKM != 1) {
718 Standard_Integer Multi;
719 for (Standard_Integer i = FirstKM + 1; i < LastKM; i++) {
721 MaxKnotMult = Max (MaxKnotMult, Multi);
726 //=======================================================================
727 //function : Reparametrize
729 //=======================================================================
731 void BSplCLib::Reparametrize
732 (const Standard_Real U1,
733 const Standard_Real U2,
736 Standard_Integer Lower = Knots.Lower();
737 Standard_Integer Upper = Knots.Upper();
738 Standard_Real UFirst = Min (U1, U2);
739 Standard_Real ULast = Max (U1, U2);
740 Standard_Real NewLength = ULast - UFirst;
741 BSplCLib_KnotDistribution KSet = BSplCLib::KnotForm (Knots, Lower, Upper);
742 if (KSet == BSplCLib_Uniform) {
743 Standard_Real DU = NewLength / (Upper - Lower);
744 Knots (Lower) = UFirst;
746 for (Standard_Integer i = Lower + 1; i <= Upper; i++) {
747 Knots (i) = Knots (i-1) + DU;
753 Standard_Real K1 = Knots (Lower);
754 Standard_Real Length = Knots (Upper) - Knots (Lower);
755 Knots (Lower) = UFirst;
757 for (Standard_Integer i = Lower + 1; i <= Upper; i++) {
759 Ratio = (K2 - K1) / Length;
760 Knots (i) = Knots (i-1) + (NewLength * Ratio);
763 Standard_Real Eps = Epsilon( Abs(Knots(i-1)) );
764 if (Knots(i) - Knots(i-1) <= Eps)
765 Knots(i) = NextAfter (Knots(i-1) + Eps, RealLast());
772 //=======================================================================
775 //=======================================================================
777 void BSplCLib::Reverse(TColStd_Array1OfReal& Knots)
779 Standard_Integer first = Knots.Lower();
780 Standard_Integer last = Knots.Upper();
781 Standard_Real kfirst = Knots(first);
782 Standard_Real klast = Knots(last);
783 Standard_Real tfirst = kfirst;
784 Standard_Real tlast = klast;
788 while (first <= last) {
789 tfirst += klast - Knots(last);
790 tlast -= Knots(first) - kfirst;
791 kfirst = Knots(first);
793 Knots(first) = tfirst;
800 //=======================================================================
803 //=======================================================================
805 void BSplCLib::Reverse(TColStd_Array1OfInteger& Mults)
807 Standard_Integer first = Mults.Lower();
808 Standard_Integer last = Mults.Upper();
809 Standard_Integer temp;
811 while (first < last) {
813 Mults(first) = Mults(last);
820 //=======================================================================
823 //=======================================================================
825 void BSplCLib::Reverse(TColStd_Array1OfReal& Weights,
826 const Standard_Integer L)
828 Standard_Integer i, l = L;
829 l = Weights.Lower()+(l-Weights.Lower())%(Weights.Upper()-Weights.Lower()+1);
831 TColStd_Array1OfReal temp(0,Weights.Length()-1);
833 for (i = Weights.Lower(); i <= l; i++)
834 temp(l-i) = Weights(i);
836 for (i = l+1; i <= Weights.Upper(); i++)
837 temp(l-Weights.Lower()+Weights.Upper()-i+1) = Weights(i);
839 for (i = Weights.Lower(); i <= Weights.Upper(); i++)
840 Weights(i) = temp(i-Weights.Lower());
843 //=======================================================================
844 //function : IsRational
846 //=======================================================================
848 Standard_Boolean BSplCLib::IsRational(const TColStd_Array1OfReal& Weights,
849 const Standard_Integer I1,
850 const Standard_Integer I2,
851 // const Standard_Real Epsi)
852 const Standard_Real )
854 Standard_Integer i, f = Weights.Lower(), l = Weights.Length();
855 Standard_Integer I3 = I2 - f;
856 const Standard_Real * WG = &Weights(f);
859 for (i = I1 - f; i < I3; i++) {
860 if (WG[f + (i % l)] != WG[f + ((i + 1) % l)]) return Standard_True;
862 return Standard_False ;
865 //=======================================================================
867 //purpose : evaluate point and derivatives
868 //=======================================================================
870 void BSplCLib::Eval(const Standard_Real U,
871 const Standard_Integer Degree,
872 Standard_Real& Knots,
873 const Standard_Integer Dimension,
874 Standard_Real& Poles)
876 Standard_Integer step,i,Dms,Dm1,Dpi,Sti;
877 Standard_Real X, Y, *poles, *knots = &Knots;
885 for (step = - 1; step < Dm1; step++) {
891 for (i = 0; i < Dms; i++) {
894 X = (knots[Dpi] - U) / (knots[Dpi] - knots[Sti]);
896 poles[0] *= X; poles[0] += Y * poles[1];
904 for (step = - 1; step < Dm1; step++) {
910 for (i = 0; i < Dms; i++) {
913 X = (knots[Dpi] - U) / (knots[Dpi] - knots[Sti]);
915 poles[0] *= X; poles[0] += Y * poles[2];
916 poles[1] *= X; poles[1] += Y * poles[3];
924 for (step = - 1; step < Dm1; step++) {
930 for (i = 0; i < Dms; i++) {
933 X = (knots[Dpi] - U) / (knots[Dpi] - knots[Sti]);
935 poles[0] *= X; poles[0] += Y * poles[3];
936 poles[1] *= X; poles[1] += Y * poles[4];
937 poles[2] *= X; poles[2] += Y * poles[5];
945 for (step = - 1; step < Dm1; step++) {
951 for (i = 0; i < Dms; i++) {
954 X = (knots[Dpi] - U) / (knots[Dpi] - knots[Sti]);
956 poles[0] *= X; poles[0] += Y * poles[4];
957 poles[1] *= X; poles[1] += Y * poles[5];
958 poles[2] *= X; poles[2] += Y * poles[6];
959 poles[3] *= X; poles[3] += Y * poles[7];
968 for (step = - 1; step < Dm1; step++) {
974 for (i = 0; i < Dms; i++) {
977 X = (knots[Dpi] - U) / (knots[Dpi] - knots[Sti]);
980 for (k = 0; k < Dimension; k++) {
982 poles[k] += Y * poles[k + Dimension];
991 //=======================================================================
992 //function : BoorScheme
994 //=======================================================================
996 void BSplCLib::BoorScheme(const Standard_Real U,
997 const Standard_Integer Degree,
998 Standard_Real& Knots,
999 const Standard_Integer Dimension,
1000 Standard_Real& Poles,
1001 const Standard_Integer Depth,
1002 const Standard_Integer Length)
1005 // Compute the values
1009 // for i = 0 to Depth,
1010 // j = 0 to Length - i
1012 // The Boor scheme is :
1015 // P(i,j) = x * P(i-1,j) + (1-x) * P(i-1,j+1)
1017 // where x = (knot(i+j+Degree) - U) / (knot(i+j+Degree) - knot(i+j))
1020 // The values are stored in the array Poles
1021 // They are alternatively written if the odd and even positions.
1023 // The successives contents of the array are
1024 // ***** means unitialised, l = Degree + Length
1026 // P(0,0) ****** P(0,1) ...... P(0,l-1) ******** P(0,l)
1027 // P(0,0) P(1,0) P(0,1) ...... P(0,l-1) P(1,l-1) P(0,l)
1028 // P(0,0) P(1,0) P(2,0) ...... P(2,l-1) P(1,l-1) P(0,l)
1031 Standard_Integer i,k,step;
1032 Standard_Real *knots = &Knots;
1033 Standard_Real *pole, *firstpole = &Poles - 2 * Dimension;
1034 // the steps of recursion
1036 for (step = 0; step < Depth; step++) {
1037 firstpole += Dimension;
1039 // compute the new row of poles
1041 for (i = step; i < Length; i++) {
1042 pole += 2 * Dimension;
1044 Standard_Real X = (knots[i+Degree-step] - U)
1045 / (knots[i+Degree-step] - knots[i]);
1046 Standard_Real Y = 1. - X;
1048 // P(i,j) = X * P(i-1,j) + (1-X) * P(i-1,j+1)
1050 for (k = 0; k < Dimension; k++)
1051 pole[k] = X * pole[k - Dimension] + Y * pole[k + Dimension];
1056 //=======================================================================
1057 //function : AntiBoorScheme
1059 //=======================================================================
1061 Standard_Boolean BSplCLib::AntiBoorScheme(const Standard_Real U,
1062 const Standard_Integer Degree,
1063 Standard_Real& Knots,
1064 const Standard_Integer Dimension,
1065 Standard_Real& Poles,
1066 const Standard_Integer Depth,
1067 const Standard_Integer Length,
1068 const Standard_Real Tolerance)
1070 // do the Boor scheme reverted.
1072 Standard_Integer i,k,step, half_length;
1073 Standard_Real *knots = &Knots;
1074 Standard_Real z,X,Y,*pole, *firstpole = &Poles + (Depth-1) * Dimension;
1076 // Test the special case length = 1
1077 // only verification of the central point
1080 X = (knots[Degree] - U) / (knots[Degree] - knots[0]);
1083 for (k = 0; k < Dimension; k++) {
1084 z = X * firstpole[k] + Y * firstpole[k+2*Dimension];
1085 if (Abs(z - firstpole[k+Dimension]) > Tolerance)
1086 return Standard_False;
1088 return Standard_True;
1092 // the steps of recursion
1094 for (step = Depth-1; step >= 0; step--) {
1095 firstpole -= Dimension;
1098 // first step from left to right
1100 for (i = step; i < Length-1; i++) {
1101 pole += 2 * Dimension;
1103 X = (knots[i+Degree-step] - U) / (knots[i+Degree-step] - knots[i]);
1106 for (k = 0; k < Dimension; k++)
1107 pole[k+Dimension] = (pole[k] - X*pole[k-Dimension]) / Y;
1111 // second step from right to left
1112 pole += 4* Dimension;
1113 half_length = (Length - 1 + step) / 2 ;
1115 // only do half of the way from right to left
1116 // otherwise it start degenerating because of
1120 for (i = Length-1; i > half_length ; i--) {
1121 pole -= 2 * Dimension;
1124 X = (knots[i+Degree-step] - U) / (knots[i+Degree-step] - knots[i]);
1127 for (k = 0; k < Dimension; k++) {
1128 z = (pole[k] - Y * pole[k+Dimension]) / X;
1129 if (Abs(z-pole[k-Dimension]) > Tolerance)
1130 return Standard_False;
1131 pole[k-Dimension] += z;
1132 pole[k-Dimension] /= 2.;
1136 return Standard_True;
1139 //=======================================================================
1140 //function : Derivative
1142 //=======================================================================
1144 void BSplCLib::Derivative(const Standard_Integer Degree,
1145 Standard_Real& Knots,
1146 const Standard_Integer Dimension,
1147 const Standard_Integer Length,
1148 const Standard_Integer Order,
1149 Standard_Real& Poles)
1151 Standard_Integer i,k,step,span = Degree;
1152 Standard_Real *knot = &Knots;
1154 for (step = 1; step <= Order; step++) {
1155 Standard_Real* pole = &Poles;
1157 for (i = step; i < Length; i++) {
1158 Standard_Real coef = - span / (knot[i+span] - knot[i]);
1160 for (k = 0; k < Dimension; k++) {
1161 pole[k] -= pole[k+Dimension];
1170 //=======================================================================
1173 //=======================================================================
1175 void BSplCLib::Bohm(const Standard_Real U,
1176 const Standard_Integer Degree,
1177 const Standard_Integer N,
1178 Standard_Real& Knots,
1179 const Standard_Integer Dimension,
1180 Standard_Real& Poles)
1182 // First phase independant of U, compute the poles of the derivatives
1183 Standard_Integer i,j,iDim,min,Dmi,DDmi,jDmi,Degm1;
1184 Standard_Real *knot = &Knots, *pole, coef, *tbis, *psav, *psDD, *psDDmDim;
1186 if (N < Degree) min = N;
1189 DDmi = (Degree << 1) + 1;
1190 switch (Dimension) {
1192 psDD = psav + Degree;
1193 psDDmDim = psDD - 1;
1195 for (i = 0; i < Degree; i++) {
1201 for (j = Degm1; j >= i; j--) {
1204 *pole = (knot[jDmi] == knot[j]) ? 0.0 : *pole / (knot[jDmi] - knot[j]);
1209 // Second phase, dependant of U
1212 for (i = 0; i < Degree; i++) {
1218 for (j = i; j >= 0; j--) {
1219 *pole += coef * (*tbis);
1224 // multiply by the degrees
1229 for (i = 1; i <= min; i++) {
1230 *pole *= coef; pole++;
1237 psDD = psav + (Degree << 1);
1238 psDDmDim = psDD - 2;
1240 for (i = 0; i < Degree; i++) {
1246 for (j = Degm1; j >= i; j--) {
1248 coef = (knot[jDmi] == knot[j]) ? 0.0 : 1. / (knot[jDmi] - knot[j]);
1249 *pole -= *tbis; *pole *= coef; pole++; tbis++;
1250 *pole -= *tbis; *pole *= coef;
1255 // Second phase, dependant of U
1258 for (i = 0; i < Degree; i++) {
1264 for (j = i; j >= 0; j--) {
1265 *pole += coef * (*tbis); pole++; tbis++;
1266 *pole += coef * (*tbis);
1271 // multiply by the degrees
1276 for (i = 1; i <= min; i++) {
1277 *pole *= coef; pole++;
1278 *pole *= coef; pole++;
1285 psDD = psav + (Degree << 1) + Degree;
1286 psDDmDim = psDD - 3;
1288 for (i = 0; i < Degree; i++) {
1294 for (j = Degm1; j >= i; j--) {
1296 coef = (knot[jDmi] == knot[j]) ? 0.0 : 1. / (knot[jDmi] - knot[j]);
1297 *pole -= *tbis; *pole *= coef; pole++; tbis++;
1298 *pole -= *tbis; *pole *= coef; pole++; tbis++;
1299 *pole -= *tbis; *pole *= coef;
1304 // Second phase, dependant of U
1307 for (i = 0; i < Degree; i++) {
1313 for (j = i; j >= 0; j--) {
1314 *pole += coef * (*tbis); pole++; tbis++;
1315 *pole += coef * (*tbis); pole++; tbis++;
1316 *pole += coef * (*tbis);
1321 // multiply by the degrees
1326 for (i = 1; i <= min; i++) {
1327 *pole *= coef; pole++;
1328 *pole *= coef; pole++;
1329 *pole *= coef; pole++;
1336 psDD = psav + (Degree << 2);
1337 psDDmDim = psDD - 4;
1339 for (i = 0; i < Degree; i++) {
1345 for (j = Degm1; j >= i; j--) {
1347 coef = (knot[jDmi] == knot[j]) ? 0.0 : 1. /(knot[jDmi] - knot[j]) ;
1348 *pole -= *tbis; *pole *= coef; pole++; tbis++;
1349 *pole -= *tbis; *pole *= coef; pole++; tbis++;
1350 *pole -= *tbis; *pole *= coef; pole++; tbis++;
1351 *pole -= *tbis; *pole *= coef;
1356 // Second phase, dependant of U
1359 for (i = 0; i < Degree; i++) {
1365 for (j = i; j >= 0; j--) {
1366 *pole += coef * (*tbis); pole++; tbis++;
1367 *pole += coef * (*tbis); pole++; tbis++;
1368 *pole += coef * (*tbis); pole++; tbis++;
1369 *pole += coef * (*tbis);
1374 // multiply by the degrees
1379 for (i = 1; i <= min; i++) {
1380 *pole *= coef; pole++;
1381 *pole *= coef; pole++;
1382 *pole *= coef; pole++;
1383 *pole *= coef; pole++;
1391 Standard_Integer Dim2 = Dimension << 1;
1392 psDD = psav + Degree * Dimension;
1393 psDDmDim = psDD - Dimension;
1395 for (i = 0; i < Degree; i++) {
1401 for (j = Degm1; j >= i; j--) {
1403 coef = (knot[jDmi] == knot[j]) ? 0.0 : 1. / (knot[jDmi] - knot[j]);
1405 for (k = 0; k < Dimension; k++) {
1406 *pole -= *tbis; *pole *= coef; pole++; tbis++;
1412 // Second phase, dependant of U
1415 for (i = 0; i < Degree; i++) {
1418 tbis = pole + Dimension;
1421 for (j = i; j >= 0; j--) {
1423 for (k = 0; k < Dimension; k++) {
1424 *pole += coef * (*tbis); pole++; tbis++;
1430 // multiply by the degrees
1433 pole = psav + Dimension;
1435 for (i = 1; i <= min; i++) {
1437 for (k = 0; k < Dimension; k++) {
1438 *pole *= coef; pole++;
1447 //=======================================================================
1448 //function : BuildKnots
1450 //=======================================================================
1452 void BSplCLib::BuildKnots(const Standard_Integer Degree,
1453 const Standard_Integer Index,
1454 const Standard_Boolean Periodic,
1455 const TColStd_Array1OfReal& Knots,
1456 const TColStd_Array1OfInteger* Mults,
1459 Standard_Integer KLower = Knots.Lower();
1460 const Standard_Real * pkn = &Knots(KLower);
1462 Standard_Real *knot = &LK;
1463 if (Mults == NULL) {
1466 Standard_Integer j = Index ;
1467 knot[0] = pkn[j]; j++;
1472 Standard_Integer j = Index - 1;
1473 knot[0] = pkn[j]; j++;
1474 knot[1] = pkn[j]; j++;
1475 knot[2] = pkn[j]; j++;
1480 Standard_Integer j = Index - 2;
1481 knot[0] = pkn[j]; j++;
1482 knot[1] = pkn[j]; j++;
1483 knot[2] = pkn[j]; j++;
1484 knot[3] = pkn[j]; j++;
1485 knot[4] = pkn[j]; j++;
1490 Standard_Integer j = Index - 3;
1491 knot[0] = pkn[j]; j++;
1492 knot[1] = pkn[j]; j++;
1493 knot[2] = pkn[j]; j++;
1494 knot[3] = pkn[j]; j++;
1495 knot[4] = pkn[j]; j++;
1496 knot[5] = pkn[j]; j++;
1497 knot[6] = pkn[j]; j++;
1502 Standard_Integer j = Index - 4;
1503 knot[0] = pkn[j]; j++;
1504 knot[1] = pkn[j]; j++;
1505 knot[2] = pkn[j]; j++;
1506 knot[3] = pkn[j]; j++;
1507 knot[4] = pkn[j]; j++;
1508 knot[5] = pkn[j]; j++;
1509 knot[6] = pkn[j]; j++;
1510 knot[7] = pkn[j]; j++;
1511 knot[8] = pkn[j]; j++;
1516 Standard_Integer j = Index - 5;
1517 knot[ 0] = pkn[j]; j++;
1518 knot[ 1] = pkn[j]; j++;
1519 knot[ 2] = pkn[j]; j++;
1520 knot[ 3] = pkn[j]; j++;
1521 knot[ 4] = pkn[j]; j++;
1522 knot[ 5] = pkn[j]; j++;
1523 knot[ 6] = pkn[j]; j++;
1524 knot[ 7] = pkn[j]; j++;
1525 knot[ 8] = pkn[j]; j++;
1526 knot[ 9] = pkn[j]; j++;
1527 knot[10] = pkn[j]; j++;
1532 Standard_Integer i,j;
1533 Standard_Integer Deg2 = Degree << 1;
1536 for (i = 0; i < Deg2; i++) {
1545 Standard_Integer Deg1 = Degree - 1;
1546 Standard_Integer KUpper = Knots.Upper();
1547 Standard_Integer MLower = Mults->Lower();
1548 Standard_Integer MUpper = Mults->Upper();
1549 const Standard_Integer * pmu = &(*Mults)(MLower);
1551 Standard_Real dknot = 0;
1552 Standard_Integer ilow = Index , mlow = 0;
1553 Standard_Integer iupp = Index + 1, mupp = 0;
1554 Standard_Real loffset = 0., uoffset = 0.;
1555 Standard_Boolean getlow = Standard_True, getupp = Standard_True;
1557 dknot = pkn[KUpper] - pkn[KLower];
1558 if (iupp > MUpper) {
1563 // Find the knots around Index
1565 for (i = 0; i < Degree; i++) {
1568 if (mlow > pmu[ilow]) {
1571 getlow = (ilow >= MLower);
1572 if (Periodic && !getlow) {
1575 getlow = Standard_True;
1579 knot[Deg1 - i] = pkn[ilow] - loffset;
1583 if (mupp > pmu[iupp]) {
1586 getupp = (iupp <= MUpper);
1587 if (Periodic && !getupp) {
1590 getupp = Standard_True;
1594 knot[Degree + i] = pkn[iupp] + uoffset;
1600 //=======================================================================
1601 //function : PoleIndex
1603 //=======================================================================
1605 Standard_Integer BSplCLib::PoleIndex(const Standard_Integer Degree,
1606 const Standard_Integer Index,
1607 const Standard_Boolean Periodic,
1608 const TColStd_Array1OfInteger& Mults)
1610 Standard_Integer i, pindex = 0;
1612 for (i = Mults.Lower(); i <= Index; i++)
1615 pindex -= Mults(Mults.Lower());
1617 pindex -= Degree + 1;
1622 //=======================================================================
1623 //function : BuildBoor
1624 //purpose : builds the local array for boor
1625 //=======================================================================
1627 void BSplCLib::BuildBoor(const Standard_Integer Index,
1628 const Standard_Integer Length,
1629 const Standard_Integer Dimension,
1630 const TColStd_Array1OfReal& Poles,
1633 Standard_Real *poles = &LP;
1634 Standard_Integer i,k, ip = Poles.Lower() + Index * Dimension;
1636 for (i = 0; i < Length+1; i++) {
1638 for (k = 0; k < Dimension; k++) {
1639 poles[k] = Poles(ip);
1641 if (ip > Poles.Upper()) ip = Poles.Lower();
1643 poles += 2 * Dimension;
1647 //=======================================================================
1648 //function : BoorIndex
1650 //=======================================================================
1652 Standard_Integer BSplCLib::BoorIndex(const Standard_Integer Index,
1653 const Standard_Integer Length,
1654 const Standard_Integer Depth)
1656 if (Index <= Depth) return Index;
1657 if (Index <= Length) return 2 * Index - Depth;
1658 return Length + Index - Depth;
1661 //=======================================================================
1662 //function : GetPole
1664 //=======================================================================
1666 void BSplCLib::GetPole(const Standard_Integer Index,
1667 const Standard_Integer Length,
1668 const Standard_Integer Depth,
1669 const Standard_Integer Dimension,
1671 Standard_Integer& Position,
1672 TColStd_Array1OfReal& Pole)
1675 Standard_Real* pole = &LP + BoorIndex(Index,Length,Depth) * Dimension;
1677 for (k = 0; k < Dimension; k++) {
1678 Pole(Position) = pole[k];
1681 if (Position > Pole.Upper()) Position = Pole.Lower();
1684 //=======================================================================
1685 //function : PrepareInsertKnots
1687 //=======================================================================
1689 Standard_Boolean BSplCLib::PrepareInsertKnots
1690 (const Standard_Integer Degree,
1691 const Standard_Boolean Periodic,
1692 const TColStd_Array1OfReal& Knots,
1693 const TColStd_Array1OfInteger& Mults,
1694 const TColStd_Array1OfReal& AddKnots,
1695 const TColStd_Array1OfInteger* AddMults,
1696 Standard_Integer& NbPoles,
1697 Standard_Integer& NbKnots,
1698 const Standard_Real Tolerance,
1699 const Standard_Boolean Add)
1701 Standard_Boolean addflat = AddMults == NULL;
1703 Standard_Integer first,last;
1705 first = Knots.Lower();
1706 last = Knots.Upper();
1709 first = FirstUKnotIndex(Degree,Mults);
1710 last = LastUKnotIndex(Degree,Mults);
1712 Standard_Real adeltaK1 = Knots(first)-AddKnots(AddKnots.Lower());
1713 Standard_Real adeltaK2 = AddKnots(AddKnots.Upper())-Knots(last);
1714 if (adeltaK1 > Tolerance) return Standard_False;
1715 if (adeltaK2 > Tolerance) return Standard_False;
1717 Standard_Integer sigma = 0, mult, amult;
1719 Standard_Integer k = Knots.Lower() - 1;
1720 Standard_Integer ak = AddKnots.Lower();
1722 if(Periodic && AddKnots.Length() > 1)
1724 //gka for case when segments was produced on full period only one knot
1725 //was added in the end of curve
1726 if(fabs(adeltaK1) <= gp::Resolution() &&
1727 fabs(adeltaK2) <= gp::Resolution())
1731 Standard_Integer aLastKnotMult = Mults (Knots.Upper());
1732 Standard_Real au,oldau = AddKnots(ak),Eps;
1734 while (ak <= AddKnots.Upper()) {
1736 if (au < oldau) return Standard_False;
1739 Eps = Max(Tolerance,Epsilon(au));
1741 while ((k < Knots.Upper()) && (Knots(k+1) - au <= Eps)) {
1747 if (addflat) amult = 1;
1748 else amult = Max(0,(*AddMults)(ak));
1750 while ((ak < AddKnots.Upper()) &&
1751 (Abs(au - AddKnots(ak+1)) <= Eps)) {
1754 if (addflat) amult++;
1755 else amult += Max(0,(*AddMults)(ak));
1760 if (Abs(au - Knots(k)) <= Eps) {
1761 // identic to existing knot
1764 if (mult + amult > Degree)
1765 amult = Max(0,Degree - mult);
1769 else if (amult > mult) {
1770 if (amult > Degree) amult = Degree;
1771 if (k == Knots.Upper () && Periodic)
1773 aLastKnotMult = Max (amult, mult);
1774 sigma += 2 * (aLastKnotMult - mult);
1778 sigma += amult - mult;
1782 // on periodic curves if this is the last knot
1783 // the multiplicity is added twice to account for the first knot
1784 if (k == Knots.Upper() && Periodic) {
1788 sigma += amult - mult;
1793 // not identic to existing knot
1795 if (amult > Degree) amult = Degree;
1804 // count the last knots
1805 while (k < Knots.Upper()) {
1812 //for periodic B-Spline the requirement is that multiplicites of the first
1813 //and last knots must be equal (see Geom_BSplineCurve constructor for
1815 //respectively AddMults() must meet this requirement if AddKnots() contains
1816 //knot(s) coincident with first or last
1817 NbPoles = sigma - aLastKnotMult;
1820 NbPoles = sigma - Degree - 1;
1823 return Standard_True;
1826 //=======================================================================
1828 //purpose : copy reals from an array to an other
1830 // NbValues are copied from OldPoles(OldFirst)
1831 // to NewPoles(NewFirst)
1833 // Periodicity is handled.
1834 // OldFirst and NewFirst are updated
1835 // to the position after the last copied pole.
1837 //=======================================================================
1839 static void Copy(const Standard_Integer NbPoles,
1840 Standard_Integer& OldFirst,
1841 const TColStd_Array1OfReal& OldPoles,
1842 Standard_Integer& NewFirst,
1843 TColStd_Array1OfReal& NewPoles)
1845 // reset the index in the range for periodicity
1847 OldFirst = OldPoles.Lower() +
1848 (OldFirst - OldPoles.Lower()) % (OldPoles.Upper() - OldPoles.Lower() + 1);
1850 NewFirst = NewPoles.Lower() +
1851 (NewFirst - NewPoles.Lower()) % (NewPoles.Upper() - NewPoles.Lower() + 1);
1856 for (i = 1; i <= NbPoles; i++) {
1857 NewPoles(NewFirst) = OldPoles(OldFirst);
1859 if (OldFirst > OldPoles.Upper()) OldFirst = OldPoles.Lower();
1861 if (NewFirst > NewPoles.Upper()) NewFirst = NewPoles.Lower();
1865 //=======================================================================
1866 //function : InsertKnots
1867 //purpose : insert an array of knots and multiplicities
1868 //=======================================================================
1870 void BSplCLib::InsertKnots
1871 (const Standard_Integer Degree,
1872 const Standard_Boolean Periodic,
1873 const Standard_Integer Dimension,
1874 const TColStd_Array1OfReal& Poles,
1875 const TColStd_Array1OfReal& Knots,
1876 const TColStd_Array1OfInteger& Mults,
1877 const TColStd_Array1OfReal& AddKnots,
1878 const TColStd_Array1OfInteger* AddMults,
1879 TColStd_Array1OfReal& NewPoles,
1880 TColStd_Array1OfReal& NewKnots,
1881 TColStd_Array1OfInteger& NewMults,
1882 const Standard_Real Tolerance,
1883 const Standard_Boolean Add)
1885 Standard_Boolean addflat = AddMults == NULL;
1887 Standard_Integer i,k,mult,firstmult;
1888 Standard_Integer index,kn,curnk,curk;
1889 Standard_Integer p,np, curp, curnp, length, depth;
1891 Standard_Integer need;
1894 // -------------------
1895 // create local arrays
1896 // -------------------
1898 Standard_Real *knots = new Standard_Real[2*Degree];
1899 Standard_Real *poles = new Standard_Real[(2*Degree+1)*Dimension];
1901 //----------------------------
1902 // loop on the knots to insert
1903 //----------------------------
1905 curk = Knots.Lower()-1; // current position in Knots
1906 curnk = NewKnots.Lower()-1; // current position in NewKnots
1907 curp = Poles.Lower(); // current position in Poles
1908 curnp = NewPoles.Lower(); // current position in NewPoles
1910 // NewKnots, NewMults, NewPoles contains the current state of the curve
1912 // index is the first pole of the current curve for insertion schema
1914 if (Periodic) index = -Mults(Mults.Lower());
1915 else index = -Degree-1;
1917 // on Periodic curves the first knot and the last knot are inserted later
1918 // (they are the same knot)
1919 firstmult = 0; // multiplicity of the first-last knot for periodic
1922 // kn current knot to insert in AddKnots
1924 for (kn = AddKnots.Lower(); kn <= AddKnots.Upper(); kn++) {
1927 Eps = Max(Tolerance,Epsilon(u));
1929 //-----------------------------------
1930 // find the position in the old knots
1931 // and copy to the new knots
1932 //-----------------------------------
1934 while (curk < Knots.Upper() && Knots(curk+1) - u <= Eps) {
1936 NewKnots(curnk) = Knots(curk);
1937 index += NewMults(curnk) = Mults(curk);
1940 //-----------------------------------
1941 // Slice the knots and the mults
1942 // to the current size of the new curve
1943 //-----------------------------------
1945 i = curnk + Knots.Upper() - curk;
1946 TColStd_Array1OfReal nknots(NewKnots(NewKnots.Lower()),NewKnots.Lower(),i);
1947 TColStd_Array1OfInteger nmults(NewMults(NewMults.Lower()),NewMults.Lower(),i);
1949 //-----------------------------------
1950 // copy enough knots
1951 // to compute the insertion schema
1952 //-----------------------------------
1958 while (mult < Degree && k < Knots.Upper()) {
1960 nknots(i) = Knots(k);
1961 mult += nmults(i) = Mults(k);
1964 // copy knots at the end for periodic curve
1970 while (mult < Degree && i > curnk) {
1971 nknots(i) = Knots(k);
1972 mult += nmults(i) = Mults(k);
1976 nmults(nmults.Upper()) = nmults(nmults.Lower());
1981 //------------------------------------
1982 // do the boor scheme on the new curve
1983 // to insert the new knot
1984 //------------------------------------
1986 Standard_Boolean sameknot = (Abs(u-NewKnots(curnk)) <= Eps);
1988 if (sameknot) length = Max(0,Degree - NewMults(curnk));
1989 else length = Degree;
1991 if (addflat) depth = 1;
1992 else depth = Min(Degree,(*AddMults)(kn));
1996 if ((NewMults(curnk) + depth) > Degree)
1997 depth = Degree - NewMults(curnk);
2000 depth = Max(0,depth-NewMults(curnk));
2004 // on periodic curve the first and last knot are delayed to the end
2005 if (curk == Knots.Lower() || (curk == Knots.Upper())) {
2006 if (firstmult == 0) // do that only once
2012 if (depth <= 0) continue;
2014 BuildKnots(Degree,curnk,Periodic,nknots,&nmults,*knots);
2018 need = NewPoles.Lower()+(index+length+1)*Dimension - curnp;
2019 need = Min(need,Poles.Upper() - curp + 1);
2023 Copy(need,p,Poles,np,NewPoles);
2027 // slice the poles to the current number of poles in case of periodic
2028 TColStd_Array1OfReal npoles(NewPoles(NewPoles.Lower()),NewPoles.Lower(),curnp-1);
2030 BuildBoor(index,length,Dimension,npoles,*poles);
2031 BoorScheme(u,Degree,*knots,Dimension,*poles,depth,length);
2033 //-------------------
2034 // copy the new poles
2035 //-------------------
2037 curnp += depth * Dimension; // number of poles is increased by depth
2038 TColStd_Array1OfReal ThePoles(NewPoles(NewPoles.Lower()),NewPoles.Lower(),curnp-1);
2039 np = NewKnots.Lower()+(index+1)*Dimension;
2041 for (i = 1; i <= length + depth; i++)
2042 GetPole(i,length,depth,Dimension,*poles,np,ThePoles);
2044 //-------------------
2046 //-------------------
2050 NewMults(curnk) += depth;
2054 NewKnots(curnk) = u;
2055 NewMults(curnk) = depth;
2059 //------------------------------
2060 // copy the last poles and knots
2061 //------------------------------
2063 Copy(Poles.Upper() - curp + 1,curp,Poles,curnp,NewPoles);
2065 while (curk < Knots.Upper()) {
2067 NewKnots(curnk) = Knots(curk);
2068 NewMults(curnk) = Mults(curk);
2071 //------------------------------
2072 // process the first-last knot
2073 // on periodic curves
2074 //------------------------------
2076 if (firstmult > 0) {
2077 curnk = NewKnots.Lower();
2078 if (NewMults(curnk) + firstmult > Degree) {
2079 firstmult = Degree - NewMults(curnk);
2081 if (firstmult > 0) {
2083 length = Degree - NewMults(curnk);
2086 BuildKnots(Degree,curnk,Periodic,NewKnots,&NewMults,*knots);
2087 TColStd_Array1OfReal npoles(NewPoles(NewPoles.Lower()),
2089 NewPoles.Upper()-depth*Dimension);
2090 BuildBoor(0,length,Dimension,npoles,*poles);
2091 BoorScheme(NewKnots(curnk),Degree,*knots,Dimension,*poles,depth,length);
2093 //---------------------------
2094 // copy the new poles
2095 // but rotate them with depth
2096 //---------------------------
2098 np = NewPoles.Lower();
2100 for (i = depth; i < length + depth; i++)
2101 GetPole(i,length,depth,Dimension,*poles,np,NewPoles);
2103 np = NewPoles.Upper() - depth*Dimension + 1;
2105 for (i = 0; i < depth; i++)
2106 GetPole(i,length,depth,Dimension,*poles,np,NewPoles);
2108 NewMults(NewMults.Lower()) += depth;
2109 NewMults(NewMults.Upper()) += depth;
2112 // free local arrays
2117 //=======================================================================
2118 //function : RemoveKnot
2120 //=======================================================================
2122 Standard_Boolean BSplCLib::RemoveKnot
2123 (const Standard_Integer Index,
2124 const Standard_Integer Mult,
2125 const Standard_Integer Degree,
2126 const Standard_Boolean Periodic,
2127 const Standard_Integer Dimension,
2128 const TColStd_Array1OfReal& Poles,
2129 const TColStd_Array1OfReal& Knots,
2130 const TColStd_Array1OfInteger& Mults,
2131 TColStd_Array1OfReal& NewPoles,
2132 TColStd_Array1OfReal& NewKnots,
2133 TColStd_Array1OfInteger& NewMults,
2134 const Standard_Real Tolerance)
2136 Standard_Integer index,i,j,k,p,np;
2138 Standard_Integer TheIndex = Index;
2141 Standard_Integer first,last;
2143 first = Knots.Lower();
2144 last = Knots.Upper();
2147 first = BSplCLib::FirstUKnotIndex(Degree,Mults) + 1;
2148 last = BSplCLib::LastUKnotIndex(Degree,Mults) - 1;
2150 if (Index < first) return Standard_False;
2151 if (Index > last) return Standard_False;
2153 if ( Periodic && (Index == first)) TheIndex = last;
2155 Standard_Integer depth = Mults(TheIndex) - Mult;
2156 Standard_Integer length = Degree - Mult;
2158 // -------------------
2159 // create local arrays
2160 // -------------------
2162 Standard_Real *knots = new Standard_Real[4*Degree];
2163 Standard_Real *poles = new Standard_Real[(2*Degree+1)*Dimension];
2166 // ------------------------------------
2167 // build the knots for anti Boor Scheme
2168 // ------------------------------------
2170 // the new sequence of knots
2171 // is obtained from the knots at Index-1 and Index
2173 BSplCLib::BuildKnots(Degree,TheIndex-1,Periodic,Knots,&Mults,*knots);
2174 index = PoleIndex(Degree,TheIndex-1,Periodic,Mults);
2175 BSplCLib::BuildKnots(Degree,TheIndex,Periodic,Knots,&Mults,knots[2*Degree]);
2179 for (i = 0; i < Degree - Mult; i++)
2180 knots[i] = knots[i+Mult];
2182 for (i = Degree-Mult; i < 2*Degree; i++)
2183 knots[i] = knots[2*Degree+i];
2186 // ------------------------------------
2187 // build the poles for anti Boor Scheme
2188 // ------------------------------------
2190 p = Poles.Lower()+index * Dimension;
2192 for (i = 0; i <= length + depth; i++) {
2193 j = Dimension * BoorIndex(i,length,depth);
2195 for (k = 0; k < Dimension; k++) {
2196 poles[j+k] = Poles(p+k);
2199 if (p > Poles.Upper()) p = Poles.Lower();
2207 Standard_Boolean result = AntiBoorScheme(Knots(TheIndex),Degree,*knots,
2209 depth,length,Tolerance);
2220 np = NewPoles.Lower();
2222 // unmodified poles before
2223 Copy((index+1)*Dimension,p,Poles,np,NewPoles);
2228 for (i = 1; i <= length; i++)
2229 BSplCLib::GetPole(i,length,0,Dimension,*poles,np,NewPoles);
2230 p += (length + depth) * Dimension ;
2232 // unmodified poles after
2233 if (p != Poles.Lower()) {
2234 i = Poles.Upper() - p + 1;
2235 Copy(i,p,Poles,np,NewPoles);
2243 NewMults(TheIndex) = Mult;
2245 if (TheIndex == first) NewMults(last) = Mult;
2246 if (TheIndex == last) NewMults(first) = Mult;
2250 if (!Periodic || (TheIndex != first && TheIndex != last)) {
2252 for (i = Knots.Lower(); i < TheIndex; i++) {
2253 NewKnots(i) = Knots(i);
2254 NewMults(i) = Mults(i);
2257 for (i = TheIndex+1; i <= Knots.Upper(); i++) {
2258 NewKnots(i-1) = Knots(i);
2259 NewMults(i-1) = Mults(i);
2263 // The interesting case of a Periodic curve
2264 // where the first and last knot is removed.
2266 for (i = first; i < last-1; i++) {
2267 NewKnots(i) = Knots(i+1);
2268 NewMults(i) = Mults(i+1);
2270 NewKnots(last-1) = NewKnots(first) + Knots(last) - Knots(first);
2271 NewMults(last-1) = NewMults(first);
2277 // free local arrays
2284 //=======================================================================
2285 //function : IncreaseDegreeCountKnots
2287 //=======================================================================
2289 Standard_Integer BSplCLib::IncreaseDegreeCountKnots
2290 (const Standard_Integer Degree,
2291 const Standard_Integer NewDegree,
2292 const Standard_Boolean Periodic,
2293 const TColStd_Array1OfInteger& Mults)
2295 if (Periodic) return Mults.Length();
2296 Standard_Integer f = FirstUKnotIndex(Degree,Mults);
2297 Standard_Integer l = LastUKnotIndex(Degree,Mults);
2298 Standard_Integer m,i,removed = 0, step = NewDegree - Degree;
2301 m = Degree + (f - i + 1) * step + 1;
2303 while (m > NewDegree+1) {
2305 m -= Mults(i) + step;
2308 if (m < NewDegree+1) removed--;
2311 m = Degree + (i - l + 1) * step + 1;
2313 while (m > NewDegree+1) {
2315 m -= Mults(i) + step;
2318 if (m < NewDegree+1) removed--;
2320 return Mults.Length() - removed;
2323 //=======================================================================
2324 //function : IncreaseDegree
2326 //=======================================================================
2328 void BSplCLib::IncreaseDegree
2329 (const Standard_Integer Degree,
2330 const Standard_Integer NewDegree,
2331 const Standard_Boolean Periodic,
2332 const Standard_Integer Dimension,
2333 const TColStd_Array1OfReal& Poles,
2334 const TColStd_Array1OfReal& Knots,
2335 const TColStd_Array1OfInteger& Mults,
2336 TColStd_Array1OfReal& NewPoles,
2337 TColStd_Array1OfReal& NewKnots,
2338 TColStd_Array1OfInteger& NewMults)
2340 // Degree elevation of a BSpline Curve
2342 // This algorithms loops on degree incrementation from Degree to NewDegree.
2343 // The variable curDeg is the current degree to increment.
2345 // Before degree incrementations a "working curve" is created.
2346 // It has the same knot, poles and multiplicities.
2348 // If the curve is periodic knots are added on the working curve before
2349 // and after the existing knots to make it a non-periodic curves.
2350 // The poles are also copied.
2352 // The first and last multiplicity of the working curve are set to Degree+1,
2353 // null poles are added if necessary.
2355 // Then the degree is incremented on the working curve.
2356 // The knots are unchanged but all multiplicities will be incremented.
2358 // Each degree incrementation is achieved by averaging curDeg+1 curves.
2360 // See : Degree elevation of B-spline curves
2361 // Hartmut PRAUTZSCH
2365 //-------------------------
2366 // create the working curve
2367 //-------------------------
2369 Standard_Integer i,k,f,l,m,pf,pl,firstknot;
2371 pf = 0; // number of null poles added at beginning
2372 pl = 0; // number of null poles added at end
2374 Standard_Integer nbwknots = Knots.Length();
2375 f = FirstUKnotIndex(Degree,Mults);
2376 l = LastUKnotIndex (Degree,Mults);
2379 // Periodic curves are transformed in non-periodic curves
2381 nbwknots += f - Mults.Lower();
2385 for (i = Mults.Lower(); i <= f; i++)
2388 nbwknots += Mults.Upper() - l;
2392 for (i = l; i <= Mults.Upper(); i++)
2396 // copy the knots and multiplicities
2397 TColStd_Array1OfReal wknots(1,nbwknots);
2398 TColStd_Array1OfInteger wmults(1,nbwknots);
2404 // copy the knots for a periodic curve
2405 Standard_Real period = Knots(Knots.Upper()) - Knots(Knots.Lower());
2408 for (k = l; k < Knots.Upper(); k++) {
2410 wknots(i) = Knots(k) - period;
2411 wmults(i) = Mults(k);
2414 for (k = Knots.Lower(); k <= Knots.Upper(); k++) {
2416 wknots(i) = Knots(k);
2417 wmults(i) = Mults(k);
2420 for (k = Knots.Lower()+1; k <= f; k++) {
2422 wknots(i) = Knots(k) + period;
2423 wmults(i) = Mults(k);
2427 // set the first and last mults to Degree+1
2428 // and add null poles
2430 pf += Degree + 1 - wmults(1);
2431 wmults(1) = Degree + 1;
2432 pl += Degree + 1 - wmults(nbwknots);
2433 wmults(nbwknots) = Degree + 1;
2435 //---------------------------
2436 // poles of the working curve
2437 //---------------------------
2439 Standard_Integer nbwpoles = 0;
2441 for (i = 1; i <= nbwknots; i++) nbwpoles += wmults(i);
2442 nbwpoles -= Degree + 1;
2444 // we provide space for degree elevation
2445 TColStd_Array1OfReal
2446 wpoles(1,(nbwpoles + (nbwknots-1) * (NewDegree - Degree)) * Dimension);
2448 for (i = 1; i <= pf * Dimension; i++)
2453 for (i = pf * Dimension + 1; i <= (nbwpoles - pl) * Dimension; i++) {
2454 wpoles(i) = Poles(k);
2456 if (k > Poles.Upper()) k = Poles.Lower();
2459 for (i = (nbwpoles-pl)*Dimension+1; i <= nbwpoles*Dimension; i++)
2463 //-----------------------------------------------------------
2464 // Declare the temporary arrays used in degree incrementation
2465 //-----------------------------------------------------------
2467 Standard_Integer nbwp = nbwpoles + (nbwknots-1) * (NewDegree - Degree);
2468 // Arrays for storing the temporary curves
2469 TColStd_Array1OfReal tempc1(1,nbwp * Dimension);
2470 TColStd_Array1OfReal tempc2(1,nbwp * Dimension);
2472 // Array for storing the knots to insert
2473 TColStd_Array1OfReal iknots(1,nbwknots);
2475 // Arrays for receiving the knots after insertion
2476 TColStd_Array1OfReal nknots(1,nbwknots);
2480 //------------------------------
2481 // Loop on degree incrementation
2482 //------------------------------
2484 Standard_Integer step,curDeg;
2485 Standard_Integer nbp = nbwpoles;
2488 for (curDeg = Degree; curDeg < NewDegree; curDeg++) {
2490 nbp = nbwp; // current number of poles
2491 nbwp = nbp + nbwknots - 1; // new number of poles
2493 // For the averaging
2494 TColStd_Array1OfReal nwpoles(1,nbwp * Dimension);
2495 nwpoles.Init(0.0e0) ;
2498 for (step = 0; step <= curDeg; step++) {
2500 // Compute the bspline of rank step.
2502 // if not the first time, decrement the multiplicities back
2504 for (i = 1; i <= nbwknots; i++)
2508 // Poles are the current poles
2509 // but the poles congruent to step are duplicated.
2511 Standard_Integer offset = 0;
2513 for (i = 0; i < nbp; i++) {
2516 for (k = 0; k < Dimension; k++) {
2517 tempc1((offset-1)*Dimension+k+1) =
2518 wpoles(NewPoles.Lower()+i*Dimension+k);
2520 if (i % (curDeg+1) == step) {
2523 for (k = 0; k < Dimension; k++) {
2524 tempc1((offset-1)*Dimension+k+1) =
2525 wpoles(NewPoles.Lower()+i*Dimension+k);
2530 // Knots multiplicities are increased
2531 // For each knot where the sum of multiplicities is congruent to step
2533 Standard_Integer stepmult = step+1;
2534 Standard_Integer nbknots = 0;
2535 Standard_Integer smult = 0;
2537 for (k = 1; k <= nbwknots; k++) {
2539 if (smult >= stepmult) {
2540 // this knot is increased
2541 stepmult += curDeg+1;
2545 // this knot is inserted
2547 iknots(nbknots) = wknots(k);
2551 // the curve is obtained by inserting the knots
2552 // to raise the multiplicities
2554 // we build "slices" of the arrays to set the correct size
2556 TColStd_Array1OfReal aknots(iknots(1),1,nbknots);
2557 TColStd_Array1OfReal curve (tempc1(1),1,offset * Dimension);
2558 TColStd_Array1OfReal ncurve(tempc2(1),1,nbwp * Dimension);
2559 // InsertKnots(curDeg+1,Standard_False,Dimension,curve,wknots,wmults,
2560 // aknots,NoMults(),ncurve,nknots,wmults,Epsilon(1.));
2562 InsertKnots(curDeg+1,Standard_False,Dimension,curve,wknots,wmults,
2563 aknots,NoMults(),ncurve,nknots,wmults,0.0);
2565 // add to the average
2567 for (i = 1; i <= nbwp * Dimension; i++)
2568 nwpoles(i) += ncurve(i);
2571 // add to the average
2573 for (i = 1; i <= nbwp * Dimension; i++)
2574 nwpoles(i) += tempc1(i);
2578 // The result is the average
2580 for (i = 1; i <= nbwp * Dimension; i++) {
2581 wpoles(i) = nwpoles(i) / (curDeg+1);
2589 // index in new knots of the first knot of the curve
2591 firstknot = Mults.Upper() - l + 1;
2595 // the new curve starts at index firstknot
2596 // so we must remove knots until the sum of multiplicities
2597 // from the first to the start is NewDegree+1
2599 // m is the current sum of multiplicities
2602 for (k = 1; k <= firstknot; k++)
2605 // compute the new first knot (k), pf will be the index of the first pole
2609 while (m > NewDegree+1) {
2614 if (m < NewDegree+1) {
2616 wmults(k) += m - NewDegree - 1;
2617 pf += m - NewDegree - 1;
2620 // on a periodic curve the knots start with firstknot
2626 for (i = NewKnots.Lower(); i <= NewKnots.Upper(); i++) {
2627 NewKnots(i) = wknots(k);
2628 NewMults(i) = wmults(k);
2635 for (i = NewPoles.Lower(); i <= NewPoles.Upper(); i++) {
2637 NewPoles(i) = wpoles(pf);
2641 //=======================================================================
2642 //function : PrepareUnperiodize
2644 //=======================================================================
2646 void BSplCLib::PrepareUnperiodize
2647 (const Standard_Integer Degree,
2648 const TColStd_Array1OfInteger& Mults,
2649 Standard_Integer& NbKnots,
2650 Standard_Integer& NbPoles)
2653 // initialize NbKnots and NbPoles
2654 NbKnots = Mults.Length();
2655 NbPoles = - Degree - 1;
2657 for (i = Mults.Lower(); i <= Mults.Upper(); i++)
2658 NbPoles += Mults(i);
2660 Standard_Integer sigma, k;
2661 // Add knots at the beginning of the curve to raise Multiplicities
2663 sigma = Mults(Mults.Lower());
2664 k = Mults.Upper() - 1;
2666 while ( sigma < Degree + 1) {
2668 NbPoles += Mults(k);
2672 // We must add exactly until Degree + 1 ->
2673 // Supress the excedent.
2674 if ( sigma > Degree + 1)
2675 NbPoles -= sigma - Degree - 1;
2677 // Add knots at the end of the curve to raise Multiplicities
2679 sigma = Mults(Mults.Upper());
2680 k = Mults.Lower() + 1;
2682 while ( sigma < Degree + 1) {
2684 NbPoles += Mults(k);
2688 // We must add exactly until Degree + 1 ->
2689 // Supress the excedent.
2690 if ( sigma > Degree + 1)
2691 NbPoles -= sigma - Degree - 1;
2694 //=======================================================================
2695 //function : Unperiodize
2697 //=======================================================================
2699 void BSplCLib::Unperiodize
2700 (const Standard_Integer Degree,
2701 const Standard_Integer , // Dimension,
2702 const TColStd_Array1OfInteger& Mults,
2703 const TColStd_Array1OfReal& Knots,
2704 const TColStd_Array1OfReal& Poles,
2705 TColStd_Array1OfInteger& NewMults,
2706 TColStd_Array1OfReal& NewKnots,
2707 TColStd_Array1OfReal& NewPoles)
2709 Standard_Integer sigma, k, index = 0;
2710 // evaluation of index : number of knots to insert before knot(1) to
2711 // raise sum of multiplicities to <Degree + 1>
2712 sigma = Mults(Mults.Lower());
2713 k = Mults.Upper() - 1;
2715 while ( sigma < Degree + 1) {
2721 Standard_Real period = Knots(Knots.Upper()) - Knots(Knots.Lower());
2723 // set the 'interior' knots;
2725 for ( k = 1; k <= Knots.Length(); k++) {
2726 NewKnots ( k + index ) = Knots( k);
2727 NewMults ( k + index ) = Mults( k);
2730 // set the 'starting' knots;
2732 for ( k = 1; k <= index; k++) {
2733 NewKnots( k) = NewKnots( k + Knots.Length() - 1) - period;
2734 NewMults( k) = NewMults( k + Knots.Length() - 1);
2736 NewMults( 1) -= sigma - Degree -1;
2738 // set the 'ending' knots;
2739 sigma = NewMults( index + Knots.Length() );
2741 for ( k = Knots.Length() + index + 1; k <= NewKnots.Length(); k++) {
2742 NewKnots( k) = NewKnots( k - Knots.Length() + 1) + period;
2743 NewMults( k) = NewMults( k - Knots.Length() + 1);
2744 sigma += NewMults( k - Knots.Length() + 1);
2746 NewMults(NewMults.Length()) -= sigma - Degree - 1;
2748 for ( k = 1 ; k <= NewPoles.Length(); k++) {
2749 NewPoles(k ) = Poles( (k-1) % Poles.Length() + 1);
2753 //=======================================================================
2754 //function : PrepareTrimming
2756 //=======================================================================
2758 void BSplCLib::PrepareTrimming(const Standard_Integer Degree,
2759 const Standard_Boolean Periodic,
2760 const TColStd_Array1OfReal& Knots,
2761 const TColStd_Array1OfInteger& Mults,
2762 const Standard_Real U1,
2763 const Standard_Real U2,
2764 Standard_Integer& NbKnots,
2765 Standard_Integer& NbPoles)
2768 Standard_Real NewU1, NewU2;
2769 Standard_Integer index1 = 0, index2 = 0;
2771 // Eval index1, index2 : position of U1 and U2 in the Array Knots
2772 // such as Knots(index1-1) <= U1 < Knots(index1)
2773 // Knots(index2-1) <= U2 < Knots(index2)
2774 LocateParameter( Degree, Knots, Mults, U1, Periodic,
2775 Knots.Lower(), Knots.Upper(), index1, NewU1);
2776 LocateParameter( Degree, Knots, Mults, U2, Periodic,
2777 Knots.Lower(), Knots.Upper(), index2, NewU2);
2779 if ( Abs(Knots(index2) - U2) <= Epsilon( U1))
2783 NbKnots = index2 - index1 + 3;
2786 NbPoles = Degree + 1;
2788 for ( i = index1; i <= index2; i++)
2789 NbPoles += Mults(i);
2792 //=======================================================================
2793 //function : Trimming
2795 //=======================================================================
2797 void BSplCLib::Trimming(const Standard_Integer Degree,
2798 const Standard_Boolean Periodic,
2799 const Standard_Integer Dimension,
2800 const TColStd_Array1OfReal& Knots,
2801 const TColStd_Array1OfInteger& Mults,
2802 const TColStd_Array1OfReal& Poles,
2803 const Standard_Real U1,
2804 const Standard_Real U2,
2805 TColStd_Array1OfReal& NewKnots,
2806 TColStd_Array1OfInteger& NewMults,
2807 TColStd_Array1OfReal& NewPoles)
2809 Standard_Integer i, nbpoles=0, nbknots=0;
2810 Standard_Real kk[2];
2811 Standard_Integer mm[2];
2812 TColStd_Array1OfReal K( kk[0], 1, 2 );
2813 TColStd_Array1OfInteger M( mm[0], 1, 2 );
2815 K(1) = U1; K(2) = U2;
2816 mm[0] = mm[1] = Degree;
2817 if (!PrepareInsertKnots( Degree, Periodic, Knots, Mults, K, &M,
2818 nbpoles, nbknots, Epsilon( U1), 0))
2819 Standard_OutOfRange::Raise();
2821 TColStd_Array1OfReal TempPoles(1, nbpoles*Dimension);
2822 TColStd_Array1OfReal TempKnots(1, nbknots);
2823 TColStd_Array1OfInteger TempMults(1, nbknots);
2826 // do not allow the multiplicities to Add : they must be less than Degree
2828 InsertKnots(Degree, Periodic, Dimension, Poles, Knots, Mults,
2829 K, &M, TempPoles, TempKnots, TempMults, Epsilon(U1),
2832 // find in TempPoles the index of the pole corresponding to U1
2833 Standard_Integer Kindex = 0, Pindex;
2834 Standard_Real NewU1;
2835 LocateParameter( Degree, TempKnots, TempMults, U1, Periodic,
2836 TempKnots.Lower(), TempKnots.Upper(), Kindex, NewU1);
2837 Pindex = PoleIndex ( Degree, Kindex, Periodic, TempMults);
2838 Pindex *= Dimension;
2840 for ( i = 1; i <= NewPoles.Length(); i++) NewPoles(i) = TempPoles(Pindex + i);
2842 for ( i = 1; i <= NewKnots.Length(); i++) {
2843 NewKnots(i) = TempKnots( Kindex+i-1);
2844 NewMults(i) = TempMults( Kindex+i-1);
2846 NewMults(1) = Min(Degree, NewMults(1)) + 1 ;
2847 NewMults(NewMults.Length())= Min(Degree, NewMults(NewMults.Length())) + 1 ;
2850 //=======================================================================
2851 //function : Solves a LU factored Matrix
2853 //=======================================================================
2856 BSplCLib::SolveBandedSystem(const math_Matrix& Matrix,
2857 const Standard_Integer UpperBandWidth,
2858 const Standard_Integer LowerBandWidth,
2859 const Standard_Integer ArrayDimension,
2860 Standard_Real& Array)
2862 Standard_Integer ii,
2869 Standard_Real *PolesArray = &Array ;
2870 Standard_Real Inverse ;
2873 if (Matrix.LowerCol() != 1 ||
2874 Matrix.UpperCol() != UpperBandWidth + LowerBandWidth + 1) {
2879 for (ii = Matrix.LowerRow() + 1; ii <= Matrix.UpperRow() ; ii++) {
2880 MinIndex = (ii - LowerBandWidth >= Matrix.LowerRow() ?
2881 ii - LowerBandWidth : Matrix.LowerRow()) ;
2883 for ( jj = MinIndex ; jj < ii ; jj++) {
2885 for (kk = 0 ; kk < ArrayDimension ; kk++) {
2886 PolesArray[(ii-1) * ArrayDimension + kk] +=
2887 PolesArray[(jj-1) * ArrayDimension + kk] * Matrix(ii, jj - ii + LowerBandWidth + 1) ;
2892 for (ii = Matrix.UpperRow() ; ii >= Matrix.LowerRow() ; ii--) {
2893 MaxIndex = (ii + UpperBandWidth <= Matrix.UpperRow() ?
2894 ii + UpperBandWidth : Matrix.UpperRow()) ;
2896 for (jj = MaxIndex ; jj > ii ; jj--) {
2898 for (kk = 0 ; kk < ArrayDimension ; kk++) {
2899 PolesArray[(ii-1) * ArrayDimension + kk] -=
2900 PolesArray[(jj - 1) * ArrayDimension + kk] *
2901 Matrix(ii, jj - ii + LowerBandWidth + 1) ;
2905 //fixing a bug PRO18577 to avoid divizion by zero
2907 Standard_Real divizor = Matrix(ii,LowerBandWidth + 1) ;
2908 Standard_Real Toler = 1.0e-16;
2909 if ( Abs(divizor) > Toler )
2910 Inverse = 1.0e0 / divizor ;
2913 // cout << " BSplCLib::SolveBandedSystem() : zero determinant " << endl;
2918 for (kk = 0 ; kk < ArrayDimension ; kk++) {
2919 PolesArray[(ii-1) * ArrayDimension + kk] *= Inverse ;
2923 return (ReturnCode) ;
2926 //=======================================================================
2927 //function : Solves a LU factored Matrix
2929 //=======================================================================
2932 BSplCLib::SolveBandedSystem(const math_Matrix& Matrix,
2933 const Standard_Integer UpperBandWidth,
2934 const Standard_Integer LowerBandWidth,
2935 const Standard_Boolean HomogeneousFlag,
2936 const Standard_Integer ArrayDimension,
2937 Standard_Real& Poles,
2938 Standard_Real& Weights)
2940 Standard_Integer ii,
2945 Standard_Real Inverse,
2946 *PolesArray = &Poles,
2947 *WeightsArray = &Weights ;
2949 if (Matrix.LowerCol() != 1 ||
2950 Matrix.UpperCol() != UpperBandWidth + LowerBandWidth + 1) {
2954 if (HomogeneousFlag == Standard_False) {
2956 for (ii = 0 ; ii < Matrix.UpperRow() - Matrix.LowerRow() + 1; ii++) {
2958 for (kk = 0 ; kk < ArrayDimension ; kk++) {
2959 PolesArray[ii * ArrayDimension + kk] *=
2965 BSplCLib::SolveBandedSystem(Matrix,
2970 if (ErrorCode != 0) {
2975 BSplCLib::SolveBandedSystem(Matrix,
2980 if (ErrorCode != 0) {
2984 if (HomogeneousFlag == Standard_False) {
2986 for (ii = 0 ; ii < Matrix.UpperRow() - Matrix.LowerRow() + 1 ; ii++) {
2987 Inverse = 1.0e0 / WeightsArray[ii] ;
2989 for (kk = 0 ; kk < ArrayDimension ; kk++) {
2990 PolesArray[ii * ArrayDimension + kk] *= Inverse ;
2994 FINISH : return (ReturnCode) ;
2997 //=======================================================================
2998 //function : BuildSchoenbergPoints
3000 //=======================================================================
3002 void BSplCLib::BuildSchoenbergPoints(const Standard_Integer Degree,
3003 const TColStd_Array1OfReal& FlatKnots,
3004 TColStd_Array1OfReal& Parameters)
3006 Standard_Integer ii,
3008 Standard_Real Inverse ;
3009 Inverse = 1.0e0 / (Standard_Real)Degree ;
3011 for (ii = Parameters.Lower() ; ii <= Parameters.Upper() ; ii++) {
3012 Parameters(ii) = 0.0e0 ;
3014 for (jj = 1 ; jj <= Degree ; jj++) {
3015 Parameters(ii) += FlatKnots(jj + ii) ;
3017 Parameters(ii) *= Inverse ;
3021 //=======================================================================
3022 //function : Interpolate
3024 //=======================================================================
3026 void BSplCLib::Interpolate(const Standard_Integer Degree,
3027 const TColStd_Array1OfReal& FlatKnots,
3028 const TColStd_Array1OfReal& Parameters,
3029 const TColStd_Array1OfInteger& ContactOrderArray,
3030 const Standard_Integer ArrayDimension,
3031 Standard_Real& Poles,
3032 Standard_Integer& InversionProblem)
3034 Standard_Integer ErrorCode,
3037 // Standard_Real *PolesArray = &Poles ;
3038 math_Matrix InterpolationMatrix(1, Parameters.Length(),
3039 1, 2 * Degree + 1) ;
3041 BSplCLib::BuildBSpMatrix(Parameters,
3045 InterpolationMatrix,
3049 Standard_OutOfRange::Raise("BSplCLib::Interpolate");
3052 BSplCLib::FactorBandedMatrix(InterpolationMatrix,
3057 Standard_OutOfRange::Raise("BSplCLib::Interpolate");
3060 BSplCLib::SolveBandedSystem(InterpolationMatrix,
3066 Standard_OutOfRange::Raise("BSplCLib::Interpolate");
3069 //=======================================================================
3070 //function : Interpolate
3072 //=======================================================================
3074 void BSplCLib::Interpolate(const Standard_Integer Degree,
3075 const TColStd_Array1OfReal& FlatKnots,
3076 const TColStd_Array1OfReal& Parameters,
3077 const TColStd_Array1OfInteger& ContactOrderArray,
3078 const Standard_Integer ArrayDimension,
3079 Standard_Real& Poles,
3080 Standard_Real& Weights,
3081 Standard_Integer& InversionProblem)
3083 Standard_Integer ErrorCode,
3087 math_Matrix InterpolationMatrix(1, Parameters.Length(),
3088 1, 2 * Degree + 1) ;
3090 BSplCLib::BuildBSpMatrix(Parameters,
3094 InterpolationMatrix,
3098 Standard_OutOfRange::Raise("BSplCLib::Interpolate");
3101 BSplCLib::FactorBandedMatrix(InterpolationMatrix,
3106 Standard_OutOfRange::Raise("BSplCLib::Interpolate");
3109 BSplCLib::SolveBandedSystem(InterpolationMatrix,
3117 Standard_OutOfRange::Raise("BSplCLib::Interpolate");
3120 //=======================================================================
3121 //function : Evaluates a Bspline function : uses the ExtrapMode
3122 //purpose : the function is extrapolated using the Taylor expansion
3123 // of degree ExtrapMode[0] to the left and the Taylor
3124 // expansion of degree ExtrapMode[1] to the right
3125 // this evaluates the numerator by multiplying by the weights
3126 // and evaluating it but does not call RationalDerivatives after
3127 //=======================================================================
3130 (const Standard_Real Parameter,
3131 const Standard_Boolean PeriodicFlag,
3132 const Standard_Integer DerivativeRequest,
3133 Standard_Integer& ExtrapMode,
3134 const Standard_Integer Degree,
3135 const TColStd_Array1OfReal& FlatKnots,
3136 const Standard_Integer ArrayDimension,
3137 Standard_Real& Poles,
3138 Standard_Real& Weights,
3139 Standard_Real& PolesResults,
3140 Standard_Real& WeightsResults)
3142 Standard_Integer ii,
3151 ExtrapolatingFlag[2],
3154 FirstNonZeroBsplineIndex,
3155 LocalRequest = DerivativeRequest ;
3156 Standard_Real *PResultArray,
3164 PolesArray = &Poles ;
3165 WeightsArray = &Weights ;
3166 ExtrapModeArray = &ExtrapMode ;
3167 PResultArray = &PolesResults ;
3168 WResultArray = &WeightsResults ;
3169 LocalParameter = Parameter ;
3170 ExtrapolatingFlag[0] =
3171 ExtrapolatingFlag[1] = 0 ;
3173 // check if we are extrapolating to a degree which is smaller than
3174 // the degree of the Bspline
3177 Period = FlatKnots(FlatKnots.Upper() - 1) - FlatKnots(2) ;
3179 while (LocalParameter > FlatKnots(FlatKnots.Upper() - 1)) {
3180 LocalParameter -= Period ;
3183 while (LocalParameter < FlatKnots(2)) {
3184 LocalParameter += Period ;
3187 if (Parameter < FlatKnots(2) &&
3188 LocalRequest < ExtrapModeArray[0] &&
3189 ExtrapModeArray[0] < Degree) {
3190 LocalRequest = ExtrapModeArray[0] ;
3191 LocalParameter = FlatKnots(2) ;
3192 ExtrapolatingFlag[0] = 1 ;
3194 if (Parameter > FlatKnots(FlatKnots.Upper()-1) &&
3195 LocalRequest < ExtrapModeArray[1] &&
3196 ExtrapModeArray[1] < Degree) {
3197 LocalRequest = ExtrapModeArray[1] ;
3198 LocalParameter = FlatKnots(FlatKnots.Upper()-1) ;
3199 ExtrapolatingFlag[1] = 1 ;
3201 Delta = Parameter - LocalParameter ;
3202 if (LocalRequest >= Order) {
3203 LocalRequest = Degree ;
3206 Modulus = FlatKnots.Length() - Degree -1 ;
3209 Modulus = FlatKnots.Length() - Degree ;
3212 BSplCLib_LocalMatrix BsplineBasis (LocalRequest, Order);
3214 BSplCLib::EvalBsplineBasis(1,
3219 FirstNonZeroBsplineIndex,
3221 if (ErrorCode != 0) {
3224 if (ExtrapolatingFlag[0] == 0 && ExtrapolatingFlag[1] == 0) {
3228 for (ii = 1 ; ii <= LocalRequest + 1 ; ii++) {
3229 Index1 = FirstNonZeroBsplineIndex ;
3231 for (kk = 0 ; kk < ArrayDimension ; kk++) {
3232 PResultArray[Index + kk] = 0.0e0 ;
3234 WResultArray[Index] = 0.0e0 ;
3236 for (jj = 1 ; jj <= Order ; jj++) {
3238 for (kk = 0 ; kk < ArrayDimension ; kk++) {
3239 PResultArray[Index + kk] +=
3240 PolesArray[(Index1-1) * ArrayDimension + kk]
3241 * WeightsArray[Index1-1] * BsplineBasis(ii,jj) ;
3243 WResultArray[Index2] += WeightsArray[Index1-1] * BsplineBasis(ii,jj) ;
3245 Index1 = Index1 % Modulus ;
3248 Index += ArrayDimension ;
3254 // store Taylor expansion in LocalRealArray
3256 NewRequest = DerivativeRequest ;
3257 if (NewRequest > Degree) {
3258 NewRequest = Degree ;
3260 NCollection_LocalArray<Standard_Real> LocalRealArray((LocalRequest + 1)*ArrayDimension);
3264 for (ii = 1 ; ii <= LocalRequest + 1 ; ii++) {
3265 Index1 = FirstNonZeroBsplineIndex ;
3267 for (kk = 0 ; kk < ArrayDimension ; kk++) {
3268 LocalRealArray[Index + kk] = 0.0e0 ;
3271 for (jj = 1 ; jj <= Order ; jj++) {
3273 for (kk = 0 ; kk < ArrayDimension ; kk++) {
3274 LocalRealArray[Index + kk] +=
3275 PolesArray[(Index1-1)*ArrayDimension + kk] *
3276 WeightsArray[Index1-1] * BsplineBasis(ii,jj) ;
3278 Index1 = Index1 % Modulus ;
3282 for (kk = 0 ; kk < ArrayDimension ; kk++) {
3283 LocalRealArray[Index + kk] *= Inverse ;
3285 Index += ArrayDimension ;
3286 Inverse /= (Standard_Real) ii ;
3288 PLib::EvalPolynomial(Delta,
3297 for (ii = 1 ; ii <= LocalRequest + 1 ; ii++) {
3298 Index1 = FirstNonZeroBsplineIndex ;
3299 LocalRealArray[Index] = 0.0e0 ;
3301 for (jj = 1 ; jj <= Order ; jj++) {
3302 LocalRealArray[Index] +=
3303 WeightsArray[Index1-1] * BsplineBasis(ii,jj) ;
3304 Index1 = Index1 % Modulus ;
3307 LocalRealArray[Index + kk] *= Inverse ;
3309 Inverse /= (Standard_Real) ii ;
3311 PLib::EvalPolynomial(Delta,
3321 //=======================================================================
3322 //function : Evaluates a Bspline function : uses the ExtrapMode
3323 //purpose : the function is extrapolated using the Taylor expansion
3324 // of degree ExtrapMode[0] to the left and the Taylor
3325 // expansion of degree ExtrapMode[1] to the right
3326 // WARNING : the array Results is supposed to have at least
3327 // (DerivativeRequest + 1) * ArrayDimension slots and the
3329 //=======================================================================
3332 (const Standard_Real Parameter,
3333 const Standard_Boolean PeriodicFlag,
3334 const Standard_Integer DerivativeRequest,
3335 Standard_Integer& ExtrapMode,
3336 const Standard_Integer Degree,
3337 const TColStd_Array1OfReal& FlatKnots,
3338 const Standard_Integer ArrayDimension,
3339 Standard_Real& Poles,
3340 Standard_Real& Results)
3342 Standard_Integer ii,
3350 ExtrapolatingFlag[2],
3353 FirstNonZeroBsplineIndex,
3354 LocalRequest = DerivativeRequest ;
3356 Standard_Real *ResultArray,
3363 PolesArray = &Poles ;
3364 ExtrapModeArray = &ExtrapMode ;
3365 ResultArray = &Results ;
3366 LocalParameter = Parameter ;
3367 ExtrapolatingFlag[0] =
3368 ExtrapolatingFlag[1] = 0 ;
3370 // check if we are extrapolating to a degree which is smaller than
3371 // the degree of the Bspline
3374 Period = FlatKnots(FlatKnots.Upper() - 1) - FlatKnots(2) ;
3376 while (LocalParameter > FlatKnots(FlatKnots.Upper() - 1)) {
3377 LocalParameter -= Period ;
3380 while (LocalParameter < FlatKnots(2)) {
3381 LocalParameter += Period ;
3384 if (Parameter < FlatKnots(2) &&
3385 LocalRequest < ExtrapModeArray[0] &&
3386 ExtrapModeArray[0] < Degree) {
3387 LocalRequest = ExtrapModeArray[0] ;
3388 LocalParameter = FlatKnots(2) ;
3389 ExtrapolatingFlag[0] = 1 ;
3391 if (Parameter > FlatKnots(FlatKnots.Upper()-1) &&
3392 LocalRequest < ExtrapModeArray[1] &&
3393 ExtrapModeArray[1] < Degree) {
3394 LocalRequest = ExtrapModeArray[1] ;
3395 LocalParameter = FlatKnots(FlatKnots.Upper()-1) ;
3396 ExtrapolatingFlag[1] = 1 ;
3398 Delta = Parameter - LocalParameter ;
3399 if (LocalRequest >= Order) {
3400 LocalRequest = Degree ;
3404 Modulus = FlatKnots.Length() - Degree -1 ;
3407 Modulus = FlatKnots.Length() - Degree ;
3410 BSplCLib_LocalMatrix BsplineBasis (LocalRequest, Order);
3413 BSplCLib::EvalBsplineBasis(1,
3418 FirstNonZeroBsplineIndex,
3420 if (ErrorCode != 0) {
3423 if (ExtrapolatingFlag[0] == 0 && ExtrapolatingFlag[1] == 0) {
3426 for (ii = 1 ; ii <= LocalRequest + 1 ; ii++) {
3427 Index1 = FirstNonZeroBsplineIndex ;
3429 for (kk = 0 ; kk < ArrayDimension ; kk++) {
3430 ResultArray[Index + kk] = 0.0e0 ;
3433 for (jj = 1 ; jj <= Order ; jj++) {
3435 for (kk = 0 ; kk < ArrayDimension ; kk++) {
3436 ResultArray[Index + kk] +=
3437 PolesArray[(Index1-1) * ArrayDimension + kk] * BsplineBasis(ii,jj) ;
3439 Index1 = Index1 % Modulus ;
3442 Index += ArrayDimension ;
3447 // store Taylor expansion in LocalRealArray
3449 NewRequest = DerivativeRequest ;
3450 if (NewRequest > Degree) {
3451 NewRequest = Degree ;
3453 NCollection_LocalArray<Standard_Real> LocalRealArray((LocalRequest + 1)*ArrayDimension);
3458 for (ii = 1 ; ii <= LocalRequest + 1 ; ii++) {
3459 Index1 = FirstNonZeroBsplineIndex ;
3461 for (kk = 0 ; kk < ArrayDimension ; kk++) {
3462 LocalRealArray[Index + kk] = 0.0e0 ;
3465 for (jj = 1 ; jj <= Order ; jj++) {
3467 for (kk = 0 ; kk < ArrayDimension ; kk++) {
3468 LocalRealArray[Index + kk] +=
3469 PolesArray[(Index1-1)*ArrayDimension + kk] * BsplineBasis(ii,jj) ;
3471 Index1 = Index1 % Modulus ;
3475 for (kk = 0 ; kk < ArrayDimension ; kk++) {
3476 LocalRealArray[Index + kk] *= Inverse ;
3478 Index += ArrayDimension ;
3479 Inverse /= (Standard_Real) ii ;
3481 PLib::EvalPolynomial(Delta,
3491 //=======================================================================
3492 //function : TangExtendToConstraint
3493 //purpose : Extends a Bspline function using the tangency map
3497 //=======================================================================
3499 void BSplCLib::TangExtendToConstraint
3500 (const TColStd_Array1OfReal& FlatKnots,
3501 const Standard_Real C1Coefficient,
3502 const Standard_Integer NumPoles,
3503 Standard_Real& Poles,
3504 const Standard_Integer CDimension,
3505 const Standard_Integer CDegree,
3506 const TColStd_Array1OfReal& ConstraintPoint,
3507 const Standard_Integer Continuity,
3508 const Standard_Boolean After,
3509 Standard_Integer& NbPolesResult,
3510 Standard_Integer& NbKnotsResult,
3511 Standard_Real& KnotsResult,
3512 Standard_Real& PolesResult)
3515 if (CDegree<Continuity+1) {
3516 cout<<"The BSpline degree must be greater than the order of continuity"<<endl;
3519 Standard_Real * Padr = &Poles ;
3520 Standard_Real * KRadr = &KnotsResult ;
3521 Standard_Real * PRadr = &PolesResult ;
3523 ////////////////////////////////////////////////////////////////////////
3525 // 1. calculation of extension nD
3527 ////////////////////////////////////////////////////////////////////////
3530 Standard_Integer Csize = Continuity + 2;
3531 math_Matrix MatCoefs(1,Csize, 1,Csize);
3533 PLib::HermiteCoefficients(0, 1, // Limits
3534 Continuity, 0, // Orders of constraints
3538 PLib::HermiteCoefficients(0, 1, // Limits
3539 0, Continuity, // Orders of constraints
3544 // position at the node of connection
3545 Standard_Real Tbord ;
3547 Tbord = FlatKnots(FlatKnots.Upper()-CDegree);
3550 Tbord = FlatKnots(FlatKnots.Lower()+CDegree);
3552 Standard_Boolean periodic_flag = Standard_False ;
3553 Standard_Integer ipos, extrap_mode[2], derivative_request = Max(Continuity,1);
3554 extrap_mode[0] = extrap_mode[1] = CDegree;
3555 TColStd_Array1OfReal EvalBS(1, CDimension * (derivative_request+1)) ;
3556 Standard_Real * Eadr = (Standard_Real *) &EvalBS(1) ;
3557 BSplCLib::Eval(Tbord,periodic_flag,derivative_request,extrap_mode[0],
3558 CDegree,FlatKnots,CDimension,Poles,*Eadr);
3560 // norm of the tangent at the node of connection
3561 math_Vector Tgte(1,CDimension);
3563 for (ipos=1;ipos<=CDimension;ipos++) {
3564 Tgte(ipos) = EvalBS(ipos+CDimension);
3566 Standard_Real L1=Tgte.Norm();
3569 // matrix of constraints
3570 math_Matrix Contraintes(1,Csize,1,CDimension);
3573 for (ipos=1;ipos<=CDimension;ipos++) {
3574 Contraintes(1,ipos) = EvalBS(ipos);
3575 Contraintes(2,ipos) = C1Coefficient * EvalBS(ipos+CDimension);
3576 if(Continuity >= 2) Contraintes(3,ipos) = EvalBS(ipos+2*CDimension) * Pow(C1Coefficient,2);
3577 if(Continuity >= 3) Contraintes(4,ipos) = EvalBS(ipos+3*CDimension) * Pow(C1Coefficient,3);
3578 Contraintes(Continuity+2,ipos) = ConstraintPoint(ipos);
3583 for (ipos=1;ipos<=CDimension;ipos++) {
3584 Contraintes(1,ipos) = ConstraintPoint(ipos);
3585 Contraintes(2,ipos) = EvalBS(ipos);
3586 if(Continuity >= 1) Contraintes(3,ipos) = C1Coefficient * EvalBS(ipos+CDimension);
3587 if(Continuity >= 2) Contraintes(4,ipos) = EvalBS(ipos+2*CDimension) * Pow(C1Coefficient,2);
3588 if(Continuity >= 3) Contraintes(5,ipos) = EvalBS(ipos+3*CDimension) * Pow(C1Coefficient,3);
3592 // calculate the coefficients of extension
3593 Standard_Integer ii, jj, kk;
3594 TColStd_Array1OfReal ExtraCoeffs(1,Csize*CDimension);
3595 ExtraCoeffs.Init(0.);
3597 for (ii=1; ii<=Csize; ii++) {
3599 for (jj=1; jj<=Csize; jj++) {
3601 for (kk=1; kk<=CDimension; kk++) {
3602 ExtraCoeffs(kk+(jj-1)*CDimension) += MatCoefs(ii,jj)*Contraintes(ii,kk);
3607 // calculate the poles of extension
3608 TColStd_Array1OfReal ExtrapPoles(1,Csize*CDimension);
3609 Standard_Real * EPadr = &ExtrapPoles(1) ;
3610 PLib::CoefficientsPoles(CDimension,
3611 ExtraCoeffs, PLib::NoWeights(),
3612 ExtrapPoles, PLib::NoWeights());
3614 // calculate the nodes of extension with multiplicities
3615 TColStd_Array1OfReal ExtrapNoeuds(1,2);
3616 ExtrapNoeuds(1) = 0.;
3617 ExtrapNoeuds(2) = 1.;
3618 TColStd_Array1OfInteger ExtrapMults(1,2);
3619 ExtrapMults(1) = Csize;
3620 ExtrapMults(2) = Csize;
3622 // flat nodes of extension
3623 TColStd_Array1OfReal FK2(1, Csize*2);
3624 BSplCLib::KnotSequence(ExtrapNoeuds,ExtrapMults,FK2);
3626 // norm of the tangent at the connection point
3628 BSplCLib::Eval(0.,periodic_flag,1,extrap_mode[0],
3629 Csize-1,FK2,CDimension,*EPadr,*Eadr);
3632 BSplCLib::Eval(1.,periodic_flag,1,extrap_mode[0],
3633 Csize-1,FK2,CDimension,*EPadr,*Eadr);
3636 for (ipos=1;ipos<=CDimension;ipos++) {
3637 Tgte(ipos) = EvalBS(ipos+CDimension);
3639 Standard_Real L2 = Tgte.Norm();
3641 // harmonisation of degrees
3642 TColStd_Array1OfReal NewP2(1, (CDegree+1)*CDimension);
3643 TColStd_Array1OfReal NewK2(1, 2);
3644 TColStd_Array1OfInteger NewM2(1, 2);
3645 if (Csize-1<CDegree) {
3646 BSplCLib::IncreaseDegree(Csize-1,CDegree,Standard_False,CDimension,
3647 ExtrapPoles,ExtrapNoeuds,ExtrapMults,
3651 NewP2 = ExtrapPoles;
3652 NewK2 = ExtrapNoeuds;
3653 NewM2 = ExtrapMults;
3656 // flat nodes of extension after harmonization of degrees
3657 TColStd_Array1OfReal NewFK2(1, (CDegree+1)*2);
3658 BSplCLib::KnotSequence(NewK2,NewM2,NewFK2);
3661 ////////////////////////////////////////////////////////////////////////
3663 // 2. concatenation C0
3665 ////////////////////////////////////////////////////////////////////////
3667 // ratio of reparametrization
3668 Standard_Real Ratio=1, Delta;
3669 if ( (L1 > Precision::Confusion()) && (L2 > Precision::Confusion()) ) {
3672 if ( (Ratio < 1.e-5) || (Ratio > 1.e5) ) Ratio = 1;
3675 // do not touch the first BSpline
3676 Delta = Ratio*NewFK2(NewFK2.Lower()) - FlatKnots(FlatKnots.Upper());
3679 // do not touch the second BSpline
3680 Delta = Ratio*NewFK2(NewFK2.Upper()) - FlatKnots(FlatKnots.Lower());
3683 // result of the concatenation
3684 Standard_Integer NbP1 = NumPoles, NbP2 = CDegree+1;
3685 Standard_Integer NbK1 = FlatKnots.Length(), NbK2 = 2*(CDegree+1);
3686 TColStd_Array1OfReal NewPoles (1, (NbP1+ NbP2-1)*CDimension);
3687 TColStd_Array1OfReal NewFlats (1, NbK1+NbK2-CDegree-2);
3690 Standard_Integer indNP, indP, indEP;
3693 for (ii=1; ii<=NbP1+NbP2-1; ii++) {
3695 for (jj=1; jj<=CDimension; jj++) {
3696 indNP = (ii-1)*CDimension+jj;
3697 indP = (ii-1)*CDimension+jj-1;
3698 indEP = (ii-NbP1)*CDimension+jj;
3699 if (ii<NbP1) NewPoles(indNP) = Padr[indP];
3700 else NewPoles(indNP) = NewP2(indEP);
3706 for (ii=1; ii<=NbP1+NbP2-1; ii++) {
3708 for (jj=1; jj<=CDimension; jj++) {
3709 indNP = (ii-1)*CDimension+jj;
3710 indEP = (ii-1)*CDimension+jj;
3711 indP = (ii-NbP2)*CDimension+jj-1;
3712 if (ii<NbP2) NewPoles(indNP) = NewP2(indEP);
3713 else NewPoles(indNP) = Padr[indP];
3720 // start with the nodes of the initial surface
3722 for (ii=1; ii<NbK1; ii++) {
3723 NewFlats(ii) = FlatKnots(FlatKnots.Lower()+ii-1);
3725 // continue with the reparameterized nodes of the extension
3727 for (ii=1; ii<=NbK2-CDegree-1; ii++) {
3728 NewFlats(NbK1+ii-1) = Ratio*NewFK2(NewFK2.Lower()+ii+CDegree) - Delta;
3732 // start with the reparameterized nodes of the extension
3734 for (ii=1; ii<NbK2-CDegree; ii++) {
3735 NewFlats(ii) = Ratio*NewFK2(NewFK2.Lower()+ii-1) - Delta;
3737 // continue with the nodes of the initial surface
3739 for (ii=2; ii<=NbK1; ii++) {
3740 NewFlats(NbK2+ii-CDegree-2) = FlatKnots(FlatKnots.Lower()+ii-1);
3745 ////////////////////////////////////////////////////////////////////////
3747 // 3. reduction of multiplicite at the node of connection
3749 ////////////////////////////////////////////////////////////////////////
3751 // number of separate nodes
3752 Standard_Integer KLength = 1;
3754 for (ii=2; ii<=NbK1+NbK2-CDegree-2;ii++) {
3755 if (NewFlats(ii) != NewFlats(ii-1)) KLength++;
3758 // flat nodes --> nodes + multiplicities
3759 TColStd_Array1OfReal NewKnots (1, KLength);
3760 TColStd_Array1OfInteger NewMults (1, KLength);
3763 NewKnots(jj) = NewFlats(1);
3765 for (ii=2; ii<=NbK1+NbK2-CDegree-2;ii++) {
3766 if (NewFlats(ii) == NewFlats(ii-1)) NewMults(jj)++;
3769 NewKnots(jj) = NewFlats(ii);
3773 // reduction of multiplicity at the second or the last but one node
3774 Standard_Integer Index = 2, M = CDegree;
3775 if (After) Index = KLength-1;
3776 TColStd_Array1OfReal ResultPoles (1, (NbP1+ NbP2-1)*CDimension);
3777 TColStd_Array1OfReal ResultKnots (1, KLength);
3778 TColStd_Array1OfInteger ResultMults (1, KLength);
3779 Standard_Real Tol = 1.e-6;
3780 Standard_Boolean Ok = Standard_True;
3782 while ( (M>CDegree-Continuity) && Ok) {
3783 Ok = RemoveKnot(Index, M-1, CDegree, Standard_False, CDimension,
3784 NewPoles, NewKnots, NewMults,
3785 ResultPoles, ResultKnots, ResultMults, Tol);
3790 // number of poles of the concatenation
3791 NbPolesResult = NbP1 + NbP2 - 1;
3792 // the poles of the concatenation
3793 Standard_Integer PLength = NbPolesResult*CDimension;
3795 for (jj=1; jj<=PLength; jj++) {
3796 PRadr[jj-1] = NewPoles(jj);
3799 // flat nodes of the concatenation
3800 Standard_Integer ideb = 0;
3802 for (jj=0; jj<NewKnots.Length(); jj++) {
3803 for (ii=0; ii<NewMults(jj+1); ii++) {
3804 KRadr[ideb+ii] = NewKnots(jj+1);
3806 ideb += NewMults(jj+1);
3808 NbKnotsResult = ideb;
3812 // number of poles of the result
3813 NbPolesResult = NbP1 + NbP2 - 1 - CDegree + M;
3814 // the poles of the result
3815 Standard_Integer PLength = NbPolesResult*CDimension;
3817 for (jj=0; jj<PLength; jj++) {
3818 PRadr[jj] = ResultPoles(jj+1);
3821 // flat nodes of the result
3822 Standard_Integer ideb = 0;
3824 for (jj=0; jj<ResultKnots.Length(); jj++) {
3825 for (ii=0; ii<ResultMults(jj+1); ii++) {
3826 KRadr[ideb+ii] = ResultKnots(jj+1);
3828 ideb += ResultMults(jj+1);
3830 NbKnotsResult = ideb;
3834 //=======================================================================
3835 //function : Resolution
3838 // Let C(t) = SUM Ci Bi(t) a Bspline curve of degree d
3840 // with nodes tj for j = 1,n+d+1
3844 // Then C (t) = SUM d * --------- Bi (t)
3845 // i = 2,n ti+d - ti
3848 // for the base of BSpline Bi (t) of degree d-1.
3850 // Consequently the upper bound of the norm of the derivative from C is :
3854 // d * Max | --------- |
3855 // i = 2,n | ti+d - ti |
3858 // In the rational case set C(t) = -----
3862 // D(t) = SUM Di Bi(t)
3865 // N(t) = SUM Di * Ci Bi(t)
3868 // N'(t) - D'(t) C(t)
3869 // C'(t) = -----------------------
3873 // N'(t) - D'(t) C(t) =
3875 // Di * (Ci - C(t)) - Di-1 * (Ci-1 - C(t)) d-1
3876 // SUM d * ---------------------------------------- * Bi (t) =
3880 // Di * (Ci - Cj) - Di-1 * (Ci-1 - Cj) d-1
3881 // SUM SUM d * ----------------------------------- * Betaj(t) * Bi (t)
3882 //i=2,n j=1,n ti+d - ti
3887 // Betaj(t) = --------
3890 // Betaj(t) form a partition >= 0 of the entity with support
3891 // tj, tj+d+1. Consequently if Rj = {j-d, ...., j+d+d+1}
3892 // obtain an upper bound of the derivative of C by taking :
3899 // Di * (Ci - Cj) - Di-1 * (Ci-1 - Cj)
3900 // Max Max d * -----------------------------------
3901 // j=1,n i dans Rj ti+d - ti
3903 // --------------------------------------------------------
3909 //=======================================================================
3911 void BSplCLib::Resolution( Standard_Real& Poles,
3912 const Standard_Integer ArrayDimension,
3913 const Standard_Integer NumPoles,
3914 const TColStd_Array1OfReal* Weights,
3915 const TColStd_Array1OfReal& FlatKnots,
3916 const Standard_Integer Degree,
3917 const Standard_Real Tolerance3D,
3918 Standard_Real& UTolerance)
3920 Standard_Integer ii,num_poles,ii_index,jj_index,ii_inDim;
3921 Standard_Integer lower,upper,ii_minus,jj,ii_miDim;
3922 Standard_Integer Deg1 = Degree + 1;
3923 Standard_Integer Deg2 = (Degree << 1) + 1;
3924 Standard_Real value,factor,W,min_weights,inverse;
3925 Standard_Real pa_ii_inDim_0, pa_ii_inDim_1, pa_ii_inDim_2, pa_ii_inDim_3;
3926 Standard_Real pa_ii_miDim_0, pa_ii_miDim_1, pa_ii_miDim_2, pa_ii_miDim_3;
3927 Standard_Real wg_ii_index, wg_ii_minus;
3928 Standard_Real *PA,max_derivative;
3929 const Standard_Real * FK = &FlatKnots(FlatKnots.Lower());
3931 max_derivative = 0.0e0;
3932 num_poles = FlatKnots.Length() - Deg1;
3933 switch (ArrayDimension) {
3935 if (Weights != NULL) {
3936 const Standard_Real * WG = &(*Weights)(Weights->Lower());
3937 min_weights = WG[0];
3939 for (ii = 1 ; ii < NumPoles ; ii++) {
3941 if (W < min_weights) min_weights = W;
3944 for (ii = 1 ; ii < num_poles ; ii++) {
3945 ii_index = ii % NumPoles;
3946 ii_inDim = ii_index << 1;
3947 ii_minus = (ii - 1) % NumPoles;
3948 ii_miDim = ii_minus << 1;
3949 pa_ii_inDim_0 = PA[ii_inDim]; ii_inDim++;
3950 pa_ii_inDim_1 = PA[ii_inDim];
3951 pa_ii_miDim_0 = PA[ii_miDim]; ii_miDim++;
3952 pa_ii_miDim_1 = PA[ii_miDim];
3953 wg_ii_index = WG[ii_index];
3954 wg_ii_minus = WG[ii_minus];
3955 inverse = FK[ii + Degree] - FK[ii];
3956 inverse = 1.0e0 / inverse;
3958 if (lower < 0) lower = 0;
3960 if (upper > num_poles) upper = num_poles;
3962 for (jj = lower ; jj < upper ; jj++) {
3963 jj_index = jj % NumPoles;
3964 jj_index = jj_index << 1;
3966 factor = (((PA[jj_index] - pa_ii_inDim_0) * wg_ii_index) -
3967 ((PA[jj_index] - pa_ii_miDim_0) * wg_ii_minus));
3968 if (factor < 0) factor = - factor;
3969 value += factor; jj_index++;
3970 factor = (((PA[jj_index] - pa_ii_inDim_1) * wg_ii_index) -
3971 ((PA[jj_index] - pa_ii_miDim_1) * wg_ii_minus));
3972 if (factor < 0) factor = - factor;
3975 if (max_derivative < value) max_derivative = value;
3978 max_derivative /= min_weights;
3982 for (ii = 1 ; ii < num_poles ; ii++) {
3983 ii_index = ii % NumPoles;
3984 ii_index = ii_index << 1;
3985 ii_minus = (ii - 1) % NumPoles;
3986 ii_minus = ii_minus << 1;
3987 inverse = FK[ii + Degree] - FK[ii];
3988 inverse = 1.0e0 / inverse;
3990 factor = PA[ii_index] - PA[ii_minus];
3991 if (factor < 0) factor = - factor;
3992 value += factor; ii_index++; ii_minus++;
3993 factor = PA[ii_index] - PA[ii_minus];
3994 if (factor < 0) factor = - factor;
3997 if (max_derivative < value) max_derivative = value;
4003 if (Weights != NULL) {
4004 const Standard_Real * WG = &(*Weights)(Weights->Lower());
4005 min_weights = WG[0];
4007 for (ii = 1 ; ii < NumPoles ; ii++) {
4009 if (W < min_weights) min_weights = W;
4012 for (ii = 1 ; ii < num_poles ; ii++) {
4013 ii_index = ii % NumPoles;
4014 ii_inDim = (ii_index << 1) + ii_index;
4015 ii_minus = (ii - 1) % NumPoles;
4016 ii_miDim = (ii_minus << 1) + ii_minus;
4017 pa_ii_inDim_0 = PA[ii_inDim]; ii_inDim++;
4018 pa_ii_inDim_1 = PA[ii_inDim]; ii_inDim++;
4019 pa_ii_inDim_2 = PA[ii_inDim];
4020 pa_ii_miDim_0 = PA[ii_miDim]; ii_miDim++;
4021 pa_ii_miDim_1 = PA[ii_miDim]; ii_miDim++;
4022 pa_ii_miDim_2 = PA[ii_miDim];
4023 wg_ii_index = WG[ii_index];
4024 wg_ii_minus = WG[ii_minus];
4025 inverse = FK[ii + Degree] - FK[ii];
4026 inverse = 1.0e0 / inverse;
4028 if (lower < 0) lower = 0;
4030 if (upper > num_poles) upper = num_poles;
4032 for (jj = lower ; jj < upper ; jj++) {
4033 jj_index = jj % NumPoles;
4034 jj_index = (jj_index << 1) + jj_index;
4036 factor = (((PA[jj_index] - pa_ii_inDim_0) * wg_ii_index) -
4037 ((PA[jj_index] - pa_ii_miDim_0) * wg_ii_minus));
4038 if (factor < 0) factor = - factor;
4039 value += factor; jj_index++;
4040 factor = (((PA[jj_index] - pa_ii_inDim_1) * wg_ii_index) -
4041 ((PA[jj_index] - pa_ii_miDim_1) * wg_ii_minus));
4042 if (factor < 0) factor = - factor;
4043 value += factor; jj_index++;
4044 factor = (((PA[jj_index] - pa_ii_inDim_2) * wg_ii_index) -
4045 ((PA[jj_index] - pa_ii_miDim_2) * wg_ii_minus));
4046 if (factor < 0) factor = - factor;
4049 if (max_derivative < value) max_derivative = value;
4052 max_derivative /= min_weights;
4056 for (ii = 1 ; ii < num_poles ; ii++) {
4057 ii_index = ii % NumPoles;
4058 ii_index = (ii_index << 1) + ii_index;
4059 ii_minus = (ii - 1) % NumPoles;
4060 ii_minus = (ii_minus << 1) + ii_minus;
4061 inverse = FK[ii + Degree] - FK[ii];
4062 inverse = 1.0e0 / inverse;
4064 factor = PA[ii_index] - PA[ii_minus];
4065 if (factor < 0) factor = - factor;
4066 value += factor; ii_index++; ii_minus++;
4067 factor = PA[ii_index] - PA[ii_minus];
4068 if (factor < 0) factor = - factor;
4069 value += factor; ii_index++; ii_minus++;
4070 factor = PA[ii_index] - PA[ii_minus];
4071 if (factor < 0) factor = - factor;
4074 if (max_derivative < value) max_derivative = value;
4080 if (Weights != NULL) {
4081 const Standard_Real * WG = &(*Weights)(Weights->Lower());
4082 min_weights = WG[0];
4084 for (ii = 1 ; ii < NumPoles ; ii++) {
4086 if (W < min_weights) min_weights = W;
4089 for (ii = 1 ; ii < num_poles ; ii++) {
4090 ii_index = ii % NumPoles;
4091 ii_inDim = ii_index << 2;
4092 ii_minus = (ii - 1) % NumPoles;
4093 ii_miDim = ii_minus << 2;
4094 pa_ii_inDim_0 = PA[ii_inDim]; ii_inDim++;
4095 pa_ii_inDim_1 = PA[ii_inDim]; ii_inDim++;
4096 pa_ii_inDim_2 = PA[ii_inDim]; ii_inDim++;
4097 pa_ii_inDim_3 = PA[ii_inDim];
4098 pa_ii_miDim_0 = PA[ii_miDim]; ii_miDim++;
4099 pa_ii_miDim_1 = PA[ii_miDim]; ii_miDim++;
4100 pa_ii_miDim_2 = PA[ii_miDim]; ii_miDim++;
4101 pa_ii_miDim_3 = PA[ii_miDim];
4102 wg_ii_index = WG[ii_index];
4103 wg_ii_minus = WG[ii_minus];
4104 inverse = FK[ii + Degree] - FK[ii];
4105 inverse = 1.0e0 / inverse;
4107 if (lower < 0) lower = 0;
4109 if (upper > num_poles) upper = num_poles;
4111 for (jj = lower ; jj < upper ; jj++) {
4112 jj_index = jj % NumPoles;
4113 jj_index = jj_index << 2;
4115 factor = (((PA[jj_index] - pa_ii_inDim_0) * wg_ii_index) -
4116 ((PA[jj_index] - pa_ii_miDim_0) * wg_ii_minus));
4117 if (factor < 0) factor = - factor;
4118 value += factor; jj_index++;
4119 factor = (((PA[jj_index] - pa_ii_inDim_1) * wg_ii_index) -
4120 ((PA[jj_index] - pa_ii_miDim_1) * wg_ii_minus));
4121 if (factor < 0) factor = - factor;
4122 value += factor; jj_index++;
4123 factor = (((PA[jj_index] - pa_ii_inDim_2) * wg_ii_index) -
4124 ((PA[jj_index] - pa_ii_miDim_2) * wg_ii_minus));
4125 if (factor < 0) factor = - factor;
4126 value += factor; jj_index++;
4127 factor = (((PA[jj_index] - pa_ii_inDim_3) * wg_ii_index) -
4128 ((PA[jj_index] - pa_ii_miDim_3) * wg_ii_minus));
4129 if (factor < 0) factor = - factor;
4132 if (max_derivative < value) max_derivative = value;
4135 max_derivative /= min_weights;
4139 for (ii = 1 ; ii < num_poles ; ii++) {
4140 ii_index = ii % NumPoles;
4141 ii_index = ii_index << 2;
4142 ii_minus = (ii - 1) % NumPoles;
4143 ii_minus = ii_minus << 2;
4144 inverse = FK[ii + Degree] - FK[ii];
4145 inverse = 1.0e0 / inverse;
4147 factor = PA[ii_index] - PA[ii_minus];
4148 if (factor < 0) factor = - factor;
4149 value += factor; ii_index++; ii_minus++;
4150 factor = PA[ii_index] - PA[ii_minus];
4151 if (factor < 0) factor = - factor;
4152 value += factor; ii_index++; ii_minus++;
4153 factor = PA[ii_index] - PA[ii_minus];
4154 if (factor < 0) factor = - factor;
4155 value += factor; ii_index++; ii_minus++;
4156 factor = PA[ii_index] - PA[ii_minus];
4157 if (factor < 0) factor = - factor;
4160 if (max_derivative < value) max_derivative = value;
4166 Standard_Integer kk;
4167 if (Weights != NULL) {
4168 const Standard_Real * WG = &(*Weights)(Weights->Lower());
4169 min_weights = WG[0];
4171 for (ii = 1 ; ii < NumPoles ; ii++) {
4173 if (W < min_weights) min_weights = W;
4176 for (ii = 1 ; ii < num_poles ; ii++) {
4177 ii_index = ii % NumPoles;
4178 ii_inDim = ii_index * ArrayDimension;
4179 ii_minus = (ii - 1) % NumPoles;
4180 ii_miDim = ii_minus * ArrayDimension;
4181 wg_ii_index = WG[ii_index];
4182 wg_ii_minus = WG[ii_minus];
4183 inverse = FK[ii + Degree] - FK[ii];
4184 inverse = 1.0e0 / inverse;
4186 if (lower < 0) lower = 0;
4188 if (upper > num_poles) upper = num_poles;
4190 for (jj = lower ; jj < upper ; jj++) {
4191 jj_index = jj % NumPoles;
4192 jj_index *= ArrayDimension;
4195 for (kk = 0 ; kk < ArrayDimension ; kk++) {
4196 factor = (((PA[jj_index + kk] - PA[ii_inDim + kk]) * wg_ii_index) -
4197 ((PA[jj_index + kk] - PA[ii_miDim + kk]) * wg_ii_minus));
4198 if (factor < 0) factor = - factor;
4202 if (max_derivative < value) max_derivative = value;
4205 max_derivative /= min_weights;
4209 for (ii = 1 ; ii < num_poles ; ii++) {
4210 ii_index = ii % NumPoles;
4211 ii_index *= ArrayDimension;
4212 ii_minus = (ii - 1) % NumPoles;
4213 ii_minus *= ArrayDimension;
4214 inverse = FK[ii + Degree] - FK[ii];
4215 inverse = 1.0e0 / inverse;
4218 for (kk = 0 ; kk < ArrayDimension ; kk++) {
4219 factor = PA[ii_index + kk] - PA[ii_minus + kk];
4220 if (factor < 0) factor = - factor;
4224 if (max_derivative < value) max_derivative = value;
4229 max_derivative *= Degree;
4230 if (max_derivative > RealSmall())
4231 UTolerance = Tolerance3D / max_derivative;
4233 UTolerance = Tolerance3D / RealSmall();
4236 //=======================================================================
4237 // function: FlatBezierKnots
4239 //=======================================================================
4241 // array of flat knots for bezier curve of maximum 25 degree
4242 static const Standard_Real knots[52] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4243 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
4244 const Standard_Real& BSplCLib::FlatBezierKnots (const Standard_Integer Degree)
4246 Standard_OutOfRange_Raise_if (Degree < 1 || Degree > MaxDegree() || MaxDegree() != 25,
4247 "Bezier curve degree greater than maximal supported");
4249 return knots[25-Degree];