MantisBT
Mantis Bug Tracker Workflow

View Issue Details Jump to Notes ] Related Changesets ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0022989Community[OCCT] OCCT:Modeling Datapublic2012-02-12 16:462015-03-24 17:11
ReporterRoman Lygin 
Assigned Tobugmaster 
PrioritynormalSeverityminor 
StatusclosedResolutionfixed 
Platform32/64 bit, VS2005,08,10OSWindowsOS VersionWindows 7
Product Version[OCCT] 6.5.2 
Target Version[OCCT] 6.5.3Fixed in Version[OCCT] 6.5.3 
Summary0022989: BSplCLib::Reparametrize() fails on near knots
Description    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.
Steps To ReproduceReproducer:
    pload MODELING
    restore edge-nosameparemeter.brep e
    sameparameter e
    #throws exception with the bug and works gracefully with fixed
TagsNo tags attached.
Test case numberchl 934 V8
Attached Files? file icon edge-nosameparameter.brep (2,351 bytes) 2012-02-12 16:46
patch file icon BSplCLib.cxx-id22989.patch (208 bytes) 2012-02-12 16:57
patch file icon BSplCLib.cxx-id22989-v2.patch (406 bytes) 2012-03-15 05:00
? file icon V8 (531 bytes) 2012-03-15 19:59
patch file icon BSplCLib.cxx-id22989-v3.patch (99 bytes) 2012-03-17 18:40
? file icon edge-nosameparameter-neg.brep (500 bytes) 2012-03-17 18:40

- Relationships
related to 0025971closedbugmaster Near B-Spline knots get merged after saving/restoring (exporting/importing) 

-  Notes
(0019882)
dbv (developer)
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 (manager)
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 (developer)
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 (manager)
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 (developer)
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 (manager)
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 (manager)
2012-03-15 10:08

The fix submitted to branch CR22989, please test
(0019995)
Roman Lygin (developer)
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 (tester)
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 (developer)
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 (administrator)
2012-03-19 17:11

Integrated into master

- Related Changesets
occt: master d0ad288a
Timestamp: 2012-03-15 04:50:00
Author: abv
Committer: bugmaster
Details ] Diff ]
0022989: BSplCLib::Reparametrize() fails on near knots
mod - src/BSplCLib/BSplCLib.cxx Diff ] File ]

- Issue History
Date Modified Username Field Change
2012-02-12 16:46 Roman Lygin New Issue
2012-02-12 16:46 Roman Lygin Assigned To => jgv
2012-02-12 16:46 Roman Lygin File Added: edge-nosameparameter.brep
2012-02-12 16:57 Roman Lygin File Added: BSplCLib.cxx-id22989.patch
2012-02-17 14:27 abv Assigned To jgv => dbv
2012-02-17 14:27 abv Status new => assigned
2012-03-06 14:41 dbv Note Added: 0019882
2012-03-06 14:41 dbv Assigned To dbv => abv
2012-03-06 14:41 dbv Status assigned => resolved
2012-03-06 15:02 abv Note Added: 0019883
2012-03-06 15:02 abv Assigned To abv => Roman Lygin
2012-03-06 15:02 abv Status resolved => assigned
2012-03-06 22:15 Roman Lygin Note Added: 0019889
2012-03-13 10:29 abv Note Added: 0019943
2012-03-15 04:59 Roman Lygin Note Added: 0019977
2012-03-15 05:00 Roman Lygin File Added: BSplCLib.cxx-id22989-v2.patch
2012-03-15 10:07 abv Note Added: 0019978
2012-03-15 10:08 abv Note Added: 0019979
2012-03-15 10:08 abv Status assigned => resolved
2012-03-15 10:08 abv Status resolved => reviewed
2012-03-15 10:29 mkv Assigned To Roman Lygin => mkv
2012-03-15 17:51 Roman Lygin Note Added: 0019995
2012-03-15 19:59 mkv File Added: V8
2012-03-15 20:03 mkv Note Added: 0020008
2012-03-15 20:04 mkv Test case number => chl 934 V8
2012-03-15 20:04 mkv Assigned To mkv => bugmaster
2012-03-15 20:04 mkv Status reviewed => tested
2012-03-17 18:34 Roman Lygin Note Added: 0020033
2012-03-17 18:40 Roman Lygin File Added: BSplCLib.cxx-id22989-v3.patch
2012-03-17 18:40 Roman Lygin File Added: edge-nosameparameter-neg.brep
2012-03-19 17:11 bugmaster Note Added: 0020042
2012-03-19 17:11 bugmaster Status tested => verified
2012-03-19 17:11 bugmaster Resolution open => fixed
2012-03-19 17:11 bugmaster Assigned To bugmaster => dbv
2012-03-19 17:20 abv Assigned To dbv => Roman Lygin
2012-03-19 17:21 abv Target Version => 6.5.3
2012-03-29 17:26 bugmaster Changeset attached => occt master d0ad288a
2015-03-24 17:11 Roman Lygin Relationship added related to 0025971


Copyright © 2000 - 2018 MantisBT Team
Powered by Mantis Bugtracker