KDTREEKDTREE uses the elements of the current mesh object to produce a k-D tree that is stored in the attributes LINKT and SBOX that are appended to the mesh object. Leaf nodes in LINKT each contain exactly one element index. Because of the possibility of triangle overlap, KDTREE also produces an array SBOX which gives 'safety boxes'. For each node in the k-D tree, there is a corresponding safety box which is just big enough to contain all the triangles "under" the node. The attributes LINKT and SBOX are used by the subroutine: RETRIEVE_WITHIN_EPS. RETRIEVE_WITHIN_EPS finds all elements with epsilon of the query point (xq,yq,zq). What is actually returned is a small subset of leaves (i.e., elements) that feasibly could be within epsilon of the query point. The user must then do exact geometric tests on this small subset to actually determine which elements are a distance epsilon from the query point.
subroutine retrieve_within_eps(xq,yq,zq,linkt,sbox, eps,nefound,iefound,ierr)
xq, yq, zq coordinates of query point linkt, sbox mesh object KDTREE attributes created by the KDTREE command eps search epsilon nefound number of elements found iefound array of elements found ierr error flag (0 = no error)
The attributes LINKT and SBOX may also be used by the subroutine: NEARESTPOINT. NEARESTPOINT uses the k-D tree structure for a triangular surface mesh object (generated by KDTREE) to accelerate finding the nearest point on the surface to the given query point (xq,yq,zq). What is actually returned is a small subset of leaves (i.e., triangles) that feasibly could contain the nearest point. The user must then do exact geometric tests on this small subset to determine points of intersection.
subroutine nearestpoint(xq,yq,zq,xic,yic,zic,itet,xs,ys,zs, linkt,sbox,eps,distpossleaf,mtfound,itfound,ierr)
xq, yq, zq coordinates of query point xic,yic,zic arrays of coordinates of nodes in the surface mesh object itet array containing trianged-node relationship for surface mesh object. xs,ys,zs coordinates of previous retrieved "nearestpoint". If there is no previous query, set these to a very large value linkt, sbox mesh object. KDTREE attributes created by the KDTREE command distpossleaf work array of length = number of triangles in the surface mesh. mtfound number of triangles found itfound array of triangle (element number) found ierr error flag