KDTREE

KDTREE 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 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