**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)
```

argument | description |
---|---|

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)
```

argument | description ————– | ——————————————————————————————————————- 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