[MOAB-dev] Possible bug in AdaptiveKDTree

[Steve Jackson]

Moabsters,

I've encountered a corner case with KDTrees that may constitute a bug.  

The attached test case fires a single ray at the included mesh geometry.  This particular ray passes through two faces of a single tetrahedron; both faces are part of the outside boundary of the mesh.  Using MOAB's AdaptiveKDTree::ray_intersect_triangles function, only one of the two intersections is found.  Doing a ray-triangle intersection on all triangles in the mesh finds both intersections.

A second geometry file is included that contains only the one tetrahedron.  If this tiny geometry is substituted for the large geometry, then the KDTree ray intersection query finds both intersections correctly.  

I've traced the KDTree code enough to know that, when only one of the two intersections is found, the missed triangle is never evaluated within a KDTree leaf node.  ("Evaluated" here means "passed to MBGeomUtil::ray_tri_intersect.")  So it's possible that this is a bug in the construction of the KDTree, rather than the ray_intersect_triangles function itself.  

Please let me know if I could usefully provide more info.
~S

-------------- next part --------------
A non-text attachment was scrubbed...
Name: kdtree.tar.gz
Type: application/x-gzip
Size: 64531 bytes
Desc: not available
URL: <http://lists.mcs.anl.gov/pipermail/moab-dev/attachments/20100329/44cfda8a/attachment-0001.bin>