160 lines
3.3 KiB
Plaintext
Executable File
160 lines
3.3 KiB
Plaintext
Executable File
.. _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;
|
|
|