View Issue Details
| ID | Project | Category | View Status | Date Submitted | Last Update |
|---|---|---|---|---|---|
| 0022989 | Community | OCCT:Modeling Data | public | 2012-02-12 16:46 | 2015-03-24 17:11 |
| Reporter | Roman Lygin | Assigned To | bugmaster | ||
| Priority | normal | Severity | minor | ||
| Status | closed | Resolution | fixed | ||
| Platform | 32/64 bit, VS2005,08,10 | OS | Windows | ||
| Product Version | 6.5.2 | ||||
| Target Version | 6.5.3 | Fixed in Version | 6.5.3 | ||
| Summary | 0022989: 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 Reproduce | Reproducer: pload MODELING restore edge-nosameparemeter.brep e sameparameter e #throws exception with the bug and works gracefully with fixed | ||||
| Tags | No tags attached. | ||||
| Test case number | chl 934 V8 | ||||
|
|
edge-nosameparameter.brep (2,351 bytes) |
|
|
BSplCLib.cxx-id22989.patch (208 bytes) |
|
|
Patch applied. Branch http://svn/svn/occt/branches/OCC22989 is ready to be reviewed. Dear Andrey, Please review. |
|
|
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. |
|
|
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(). |
|
|
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; |
|
|
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. |
|
|
BSplCLib.cxx-id22989-v2.patch (406 bytes) |
|
|
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) |
|
|
The fix submitted to branch CR22989, please test |
|
|
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. |
|
2012-03-15 19:59 tester |
V8 (531 bytes) |
|
|
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 |
|
|
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) |
|
|
BSplCLib.cxx-id22989-v3.patch (99 bytes) |
|
|
edge-nosameparameter-neg.brep (500 bytes) |
|
|
Integrated into master |
| 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 |
|
Assigned To | jgv => dbv |
| 2012-02-17 14:27 |
|
Status | new => assigned |
| 2012-03-06 14:41 |
|
Note Added: 0019882 | |
| 2012-03-06 14:41 |
|
Assigned To | dbv => abv |
| 2012-03-06 14:41 |
|
Status | assigned => resolved |
| 2012-03-06 15:02 |
|
Note Added: 0019883 | |
| 2012-03-06 15:02 |
|
Assigned To | abv => Roman Lygin |
| 2012-03-06 15:02 |
|
Status | resolved => assigned |
| 2012-03-06 22:15 | Roman Lygin | Note Added: 0019889 | |
| 2012-03-13 10:29 |
|
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 |
|
Note Added: 0019978 | |
| 2012-03-15 10:08 |
|
Note Added: 0019979 | |
| 2012-03-15 10:08 |
|
Status | assigned => resolved |
| 2012-03-15 10:08 |
|
Status | resolved => reviewed |
| 2012-03-15 10:29 |
|
Assigned To | Roman Lygin => mkv |
| 2012-03-15 17:51 | Roman Lygin | Note Added: 0019995 | |
| 2012-03-15 19:59 |
|
File Added: V8 | |
| 2012-03-15 20:03 |
|
Note Added: 0020008 | |
| 2012-03-15 20:04 |
|
Test case number | => chl 934 V8 |
| 2012-03-15 20:04 |
|
Assigned To | mkv => bugmaster |
| 2012-03-15 20:04 |
|
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 |
|
Assigned To | dbv => Roman Lygin |
| 2012-03-19 17:21 |
|
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 |
