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