| View Issue Details [ Jump to Notes ] | [ Print ] | ||||||||
| ID | Project | Category | View Status | Date Submitted | Last Update | ||||
| 0000702 | VTK | (No Category) | public | 2004-03-24 14:27 | 2013-04-05 19:57 | ||||
| Reporter | Andreas Kuhn | ||||||||
| Assigned To | Zhanping Liu | ||||||||
| Priority | high | Severity | major | Reproducibility | always | ||||
| Status | closed | Resolution | open | ||||||
| Platform | OS | OS Version | |||||||
| Product Version | |||||||||
| Target Version | Fixed in Version | ||||||||
| Summary | 0000702: bug in vtkCellLocator | ||||||||
| Description | I think there is a problem in the vtkCellLocator. The attached program makes two spheres of radii 0.8 and 1. Afterwards, it traverses the points of the bigger sphere and searches for an intersection with a vector in the negative normal direction that has a specific length (0.15 to 0.7). I expect that if the search depth is bigger than 0.2 (difference between the two radii of the spheres), an intersection for all the points is found. But if you look at the output of the attached program, this is not the case (the output is also posted below). actual search depth : 0.15 points where intersection was found : 0 points with no intersection : 9802 actual search depth : 0.2 points where intersection was found : 1773 points with no intersection : 8029 actual search depth : 0.25 points where intersection was found : 3576 points with no intersection : 6226 actual search depth : 0.3 points where intersection was found : 3896 points with no intersection : 5906 actual search depth : 0.35 points where intersection was found : 4280 points with no intersection : 5522 actual search depth : 0.4 points where intersection was found : 4872 points with no intersection : 4930 actual search depth : 0.45 points where intersection was found : 6008 points with no intersection : 3794 actual search depth : 0.5 points where intersection was found : 7080 points with no intersection : 2722 actual search depth : 0.55 points where intersection was found : 8616 points with no intersection : 1186 actual search depth : 0.6 points where intersection was found : 9802 points with no intersection : 0 | ||||||||
| Tags | No tags attached. | ||||||||
| Project | |||||||||
| Type | |||||||||
| Attached Files |  Test.cxx [^] (2,768 bytes) 1969-12-31 19:00 | ||||||||
| Relationships | |
| Relationships |
| Notes | |
|
(0000820) Goodwin Lawlor (reporter) 2004-03-26 21:14 |
using vtkOBBTree, your test code works but run much more slowly... |
|
(0013616) Zhanping Liu (developer) 2008-09-29 15:28 |
The problem reported by Kuhnan resulted from the following two issues: (1) the bug with vtkCellLocator::IntersectWithLine(), in which ================== tMax = sqrt(tMax); ================== was missed immediately before ================================================= // create a parametric range around the tolerance deltaT = tol/maxLength; ================================================= After it is fixed, the result is: ========================================== actual search depth : 0.15 points where intersection was found : 0 points with no intersection : 9802 actual search depth : 0.2 points where intersection was found : 4976 points with no intersection : 4826 actual search depth : 0.25 points where intersection was found : 9802 points with no intersection : 0 actual search depth : 0.3 points where intersection was found : 9802 points with no intersection : 0 actual search depth : 0.35 points where intersection was found : 9802 points with no intersection : 0 actual search depth : 0.4 points where intersection was found : 9802 points with no intersection : 0 actual search depth : 0.45 points where intersection was found : 9802 points with no intersection : 0 actual search depth : 0.5 points where intersection was found : 9802 points with no intersection : 0 actual search depth : 0.55 points where intersection was found : 9802 points with no intersection : 0 actual search depth : 0.6 points where intersection was found : 9802 points with no intersection : 0 ========================================== The result for the "actual search depth" 0.2 --- (4976, 4826) is due to the inherent numerical inaccuracy that always exists in float-point computation. In fact, the algorithm itself is sufficiently accurate as indicated below: ========================================== actual search depth : 0.20000001 points where intersection was found : 6971 points with no intersection : 3011 actual search depth : 0.2000001 points where intersection was found : 9802 points with no intersection : 0 ========================================== Thus after the bug is fixed, the algorithm is robust. The user just needs to consider the floating-point related error tolerance (i.e., to use a value like 0.2000001 in place of 0.2 as the search depth) to obtain the correct result. Thanks. new revision: 1.89; previous revision: 1.88. |
| Notes |
| Issue History | |||
| Date Modified | Username | Field | Change |
| 2008-09-23 11:31 | Berk Geveci | Assigned To | Will Schroeder => Zhanping Liu |
| 2008-09-29 15:28 | Zhanping Liu | Note Added: 0013616 | |
| 2008-09-29 15:29 | Zhanping Liu | Status | tabled => @80@ |
| 2011-06-16 13:11 | Zack Galbreath | Category | => (No Category) |
| 2013-04-05 19:57 | Berk Geveci | Status | customer review => closed |
| Issue History |
| Copyright © 2000 - 2018 MantisBT Team |