MantisBT - VTK
View Issue Details

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
Project
Type

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
Steps To Reproduce
Additional Information
Tags	No tags attached.
Relationships
Attached Files	Test.cxx (2,768) 1969-12-31 19:00 https://www.vtk.org/Bug/file/5072/Test.cxx

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

Notes

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.