MantisBT - Community
View Issue Details
0022989Community[OCCT] OCCT:Modeling Datapublic2012-02-12 16:462015-03-24 17:11
Roman Lygin 
bugmaster 
normalminor 
closedfixed 
32/64 bit, VS2005,08,10WindowsWindows 7
[OCCT] 6.5.2 
[OCCT] 6.5.3[OCCT] 6.5.3 
chl 934 V8
0022989: BSplCLib::Reparametrize() fails on near knots
    Due to double rounding error, BSplCLib::Reparametrize() fails to prepare a knot array
    that can later be set with Geom2d_BSplineCurve::SetKnots(). This problem is specific
    to Windows/VisualC++, it is not reproduced on Linux/gcc4.1.2. Reproduced with prebuilt
    binaries of 6.5.2, and with rebuilt with VS2008, VS2010, both 32 and 64bit, on
    OCC 6.5.0-6.5.2.

    Root-cause:
    Geom2d_BSplineCurve::SetKnots() uses CheckCurveData() function to verify that distance
    between adjacent knots is greater than Epsilon(Knot(i)). BSplCLib::Reparametrize() uses
    the same check and adds 1.1*Epsilon. However due to rounding error, one addition may not
    be enough and CheckCurveData() will fail afterwards.

    Fix:
    The approach is to incrementally add 1.1*Eps until this condition is satisfied.
    Incrementing will always happen, so there will be no infinite loop. A more moderate
    approach can be preferred (e.g. first increment is 1.1*Eps and consequent are 0.1*Eps).
    Current approach is preferred as it provides greater distance between knots (and some
    algorithms which divide by a range |Knots(i+1)-Knots(i)| can be more robust in this
    case), and for code compactness.
Reproducer:
    pload MODELING
    restore edge-nosameparemeter.brep e
    sameparameter e
    #throws exception with the bug and works gracefully with fixed
No tags attached.
related to 0025971closed bugmaster Near B-Spline knots get merged after saving/restoring (exporting/importing) 
? edge-nosameparameter.brep (2,351) 2012-02-12 16:46
https://tracker.dev.opencascade.org/
patch BSplCLib.cxx-id22989.patch (208) 2012-02-12 16:57
https://tracker.dev.opencascade.org/
patch BSplCLib.cxx-id22989-v2.patch (406) 2012-03-15 05:00
https://tracker.dev.opencascade.org/
? V8 (531) 2012-03-15 19:59
https://tracker.dev.opencascade.org/
patch BSplCLib.cxx-id22989-v3.patch (99) 2012-03-17 18:40
https://tracker.dev.opencascade.org/
? edge-nosameparameter-neg.brep (500) 2012-03-17 18:40
https://tracker.dev.opencascade.org/
Issue History
2012-02-12 16:46Roman LyginNew Issue
2012-02-12 16:46Roman LyginAssigned To => jgv
2012-02-12 16:46Roman LyginFile Added: edge-nosameparameter.brep
2012-02-12 16:57Roman LyginFile Added: BSplCLib.cxx-id22989.patch
2012-02-17 14:27abvAssigned Tojgv => dbv
2012-02-17 14:27abvStatusnew => assigned
2012-03-06 14:41dbvNote Added: 0019882
2012-03-06 14:41dbvAssigned Todbv => abv
2012-03-06 14:41dbvStatusassigned => resolved
2012-03-06 15:02abvNote Added: 0019883
2012-03-06 15:02abvAssigned Toabv => Roman Lygin
2012-03-06 15:02abvStatusresolved => assigned
2012-03-06 22:15Roman LyginNote Added: 0019889
2012-03-13 10:29abvNote Added: 0019943
2012-03-15 04:59Roman LyginNote Added: 0019977
2012-03-15 05:00Roman LyginFile Added: BSplCLib.cxx-id22989-v2.patch
2012-03-15 10:07abvNote Added: 0019978
2012-03-15 10:08abvNote Added: 0019979
2012-03-15 10:08abvStatusassigned => resolved
2012-03-15 10:08abvStatusresolved => reviewed
2012-03-15 10:29mkvAssigned ToRoman Lygin => mkv
2012-03-15 17:51Roman LyginNote Added: 0019995
2012-03-15 19:59mkvFile Added: V8
2012-03-15 20:03mkvNote Added: 0020008
2012-03-15 20:04mkvTest case number => chl 934 V8
2012-03-15 20:04mkvAssigned Tomkv => bugmaster
2012-03-15 20:04mkvStatusreviewed => tested
2012-03-17 18:34Roman LyginNote Added: 0020033
2012-03-17 18:40Roman LyginFile Added: BSplCLib.cxx-id22989-v3.patch
2012-03-17 18:40Roman LyginFile Added: edge-nosameparameter-neg.brep
2012-03-19 17:11bugmasterNote Added: 0020042
2012-03-19 17:11bugmasterStatustested => verified
2012-03-19 17:11bugmasterResolutionopen => fixed
2012-03-19 17:11bugmasterAssigned Tobugmaster => dbv
2012-03-19 17:20abvAssigned Todbv => Roman Lygin
2012-03-19 17:21abvTarget Version => 6.5.3
2012-03-29 17:26bugmasterChangeset attached => occt master d0ad288a
2015-03-24 17:11Roman LyginRelationship addedrelated to 0025971

Notes
(0019882)
dbv   
2012-03-06 14:41   
Patch applied.

Branch http://svn/svn/occt/branches/OCC22989 [^] is ready to be reviewed.

Dear Andrey,
Please review.
(0019883)
abv   
2012-03-06 15:02   
I believe the current fix can cause infinite loop; just imagine that Eps = 0. In practice, it should never be 0., but can be DBL_MIN if Knots(i-1) = 0.

I suggest to modify instead a way Eps is computed:

Standard_Real Eps = Max (Epsilon(Knots(i-1)), Epsilon(Knots(i)));

Naturally, for optimization we can re-use value of Epsilon computed for previous knot on each cycle. Note that it is not necessary to take Abs() of the knot value, as function Epsilon() always returns positive number (see implementation in Standard_Real.hxx).

Besides, it is strange to see factor 1.1 multiplying Eps: by the very nature of Eps, all values below it should vanish when added to Knot(i). I suggest either removing that factor or (perhaps better) replacing it by 2.
(0019889)
Roman Lygin   
2012-03-06 22:15   
1. The warning of 0 was in the original bug report - the code of Epsilon() seems to ensure this does not ever happen. Otherwise, theoretically Max (Epsilon(Knots(i-1)), Epsilon(Knots(i))) can also be zero.
2. 2 vs 1.1 is good.
3. Did not get a comment regarding Abs().
(0019943)
abv   
2012-03-13 10:29   
I do not like while() here because it is not clear how many cycles it will take in worst case. If it is never infinite, from the same logic one cycle should be always sufficient.

I do not like 1.1 since I do not understand which effect additional 0.1 can have if we know that values less than Eps yield no change in the value of the Knot(i-1) when added to it (from definition of Eps). Sorry, I am not an expert in discrete math and FPE...

So why we need to replace "if" by "while"?
How can we be sure that it is safe and works in all cases?
Should not we just replace 1.1 by 2?

Can you share the values of knots and epsilon at which the problem happens on your case?

I still believe the cycle is dangerous. Consider the possible case if Knot(i-1)=0 (hence Epsilon = DBL_MIN) and Knot(i) = -1. Note that even this is invalid situation, nothing guarantees that Knot(i) > Knot(i-1) in the input array. It is better to prevent this function from hanging up even on invalid data.

Perhaps the correct code would be:

      if (Knots(i) - Knots(i-1) <= Eps)
    Knots(i) = Knots(i-1) + Eps;
(0019977)
Roman Lygin   
2012-03-15 04:59   
The suggested code does not work as is - CheckCurveData() in Geom[2d]_BSplineCurve.cxx (or CheckSurfaceData() in Geom_BSplineSurface.cxx) fail as they use the same test and the difference Knots(i)-Knots(i-1) is exactly Eps.

However, the approach to add to Knots(i-1) (not to Knots(i)) is reasonable so I reworked the code, using it. Note however that Knots(i)=Knots(i-1)+1.1*Eps does not work (even if Eps is ~8e-16). There must be some issues in mixing multiplication and addition, so single iteration is not enough. I reworked the code as follows:

> if (Knots(i) - Knots(i-1) <= Eps) {
> //increment Knots(i) until the condition has been satisfied - see 0022989 for details
> Standard_Real anInc = Max (Eps, DBL_MIN);
> Knots(i) = Knots(i-1) + anInc;
> while (Knots(i) - Knots(i-1) <= Eps)
> Knots(i) += anInc;
> }
 
This avoids multiplication and ensures incrementation (Eps >= DBL_MIN), and thus no infinite loop.

Now to address your question:
the original 6.5.2 code fails here:
Knot(i-1): 6.2831853071795853
Knot(i) : 6.2831853071795853
(not they are equal in VS IDE - likely difference is beyond the last digit).

Eps: 8.8817841970012523e-016
After Knot += 1.1*Eps, Knot(i):6.2831853071795862

P.S. The new version will be attached.
(0019978)
abv   
2012-03-15 10:07   
Ok, now see the point: the distance should be not Eps, but greater. OCCT provides function NextAfter exactly for this, so my variant is:

  if (Knots(i) - Knots(i-1) <= Eps)
    Knots(i) = NextAfter (Knots(i-1) + Eps, RealLast());

This fix seems to work on your case (VS 2008)
(0019979)
abv   
2012-03-15 10:08   
The fix submitted to branch CR22989, please test
(0019995)
Roman Lygin   
2012-03-15 17:51   
NextAfter (Knots(i-1) + Eps, RealLast()); is good for non-negative Knots(i-1). The original test case proceeds with it successfully.

However, for negative ones another code branch in NextAfter() is used which is not used in Epsilon(). So it must be investigated and better a test case created before committing the change. I can try to do this within a few days, unless you can do on your own.

In any case we better leave a bug id close to this modification, so that can consult these notes in the future if needed.
(0020008)
mkv   
2012-03-15 20:03   
Dear BugMaster,
Workbench KAS:dev:mkv-22989-occt was created from git branch CR22989
(and mkv-22989-products from svn trunk) and compiled on Linux platform.

Test case for this bug is chl/934/V8. It is OK.

There are not regressions in mkv-22989-products regarding to KAS:dev:products-20120306-opt

See results in /QADisk/occttests/results/KAS/dev/mkv-22989-products_15032012/lin
See reference results in /QADisk/occttests/results/KAS/dev/products-20120306-opt_07032012/lin
See test cases in /QADisk/occttests/tests/ED
N.B. In order to launch testing case you can make use the following instructions
http://doc/doku.php?id=occt:certification [^]
(0020033)
Roman Lygin   
2012-03-17 18:34   
To respond to my note above.
I confirm that the fix suggested by Andrey works for negative Knots as well. I attach a test case for that (edge-nosameparameter-neg.brep)
(0020042)
bugmaster   
2012-03-19 17:11   
Integrated into master