Procedure

     XDDA  ( list voxels intersected by a ray )

     SUBROUTINE XDDA ( VERTEX, RAYDIR, GRDEXT, MAXNVX, NVX, VOXLST )

Abstract

     Return a list of voxels that a given ray intersects in a given
     voxel grid.

Required_Reading

     None.

Keywords

     GRID
     INTERSECTION
     PLATE
     VOXEL

Declarations

     IMPLICIT NONE

     DOUBLE PRECISION      GRDTOL
     PARAMETER           ( GRDTOL = 1.D-12 )

     DOUBLE PRECISION      VERTEX ( 3 )
     DOUBLE PRECISION      RAYDIR ( 3 )
     INTEGER               GRDEXT ( 3 )
     INTEGER               MAXNVX
     INTEGER               NVX
     INTEGER               VOXLST ( 3, * )

Brief_I/O

     VARIABLE  I/O  DESCRIPTION
     --------  ---  --------------------------------------------------
     GRDTOL     P   Tolerance for vertex distance from grid.
     VERTEX     I   Voxel grid coordinates of ray's vertex.
     RAYDIR     I   Direction vector of ray.
     GRDEXT     I   Dimensions of grid in voxel units.
     MAXNVX     I   Maximum value of VOXLST.
     NVX        O   Number of voxels in the VOXLST list.
     VOXLST     O   List of voxels intersected by ray.

Detailed_Input

     VERTEX   is the voxel grid coordinates of ray's vertex. These
              coordinates are zero-based, double precision offsets from
              the grid's origin. The units of the coordinates are
              voxels, that is, voxel edge lengths.

     RAYDIR   is the direction vector of ray from VERTEX.

     GRDEXT   is the integer 3-vector containing the voxel grid
              extents. These are the dimensions of the voxel grid in
              voxel units, in the X, Y, and Z directions respectively.

     MAXNVX   is the maximum number of voxel coordinate sets that can
              be stored in VOXLST.

Detailed_Output

     NVX      is the number of voxel coordinate sets contained in
              VOXLST.

     VOXLST   is the list of coordinate sets of voxels intersected by
              ray. Elements

                 VOXLST(J,I), J = 1, 3

              are the coordinates of the Ith voxel in the list. These
              coordinates are 1-based integer values.

              The voxels in the output list are ordered by increasing
              distance from the ray's vertex.

Parameters

     GRDTOL   is a tolerance value used to determine whether
              VERTEX is too far from the voxel grid. The Ith
              component of VERTEX must not differ from the
              Ith coordinate of the nearest grid point by more
              than

                  GRDTOL * EXTENT(I)

Exceptions

     1)  If the input RAYDIR has all zero components, the error
         SPICE(ZEROVECTOR) is signaled.

     2)  If the maximum output list size MAXNVX is non-positive, the
         error SPICE(INVALIDSIZE) is signaled.

     3)  If any element of the grid extents array GRDEXT is
         non-positive, the error SPICE(BADDIMENSIONS) is signaled.

     4)  If the ray's vertex is neither inside, nor within a small
         distance from, the voxel grid, the error
         SPICE(VERTEXNOTINGRID) is signaled. See the description of the
         parameter GRDTOL.

     5)  If the value of the NVX counter (number of intersected voxels)
         exceeds the size of the VOXLST input vector, the error
         SPICE(ARRAYTOOSMALL) is signaled.

Files

     None.

Particulars

     This routine supports use of a spatial index for rapid
     selection of plates that could be hit by a specified ray.

Examples

     See the routine DSKX02 for a usage example.

Restrictions

     None.

Literature_References

     None.

Author_and_Institution

     N.J. Bachman       (JPL)
     J.A. Bytof         (JPL)
     J. Diaz del Rio    (ODC Space)
     B.V. Semenov       (JPL)
     E.D. Wright        (JPL)

Version

    SPICELIB Version 3.1.1, 26-OCT-2021 (NJB) (JDR)

        Edited the header to comply with NAIF standard.

        Typo correction: the description of the error denoted
        by the short message SPICE(VERTEXNOTINGRID) had been
        the negative of what was intended.

    SPICELIB Version 3.1.0, 02-FEB-2016 (NJB)

        Updated to call ZZINGRD rather than INGRD.
        Minor updates were made to header I/O sections.

    SPICELIB Version 3.0.0, 11-JUL-2014 (NJB) (EDW) (BVS) (JAB)

        Previously released as DSKLIB:

        DSKLIB Version 3.0.0, 11-JUL-2014 (NJB)

           Bug fix: a correction was made to the computation of
           the vertex offset from the bounding planes of the
           voxel containing the vertex.

           Minor edits were made to comments.

        Last update was 05-JUN-2014 (NJB)

           Bug fix: the use of the MOD function led to a 1-voxel
           size error when the input ray's vertex was on the
           voxel grid boundary.

           An error check for invalid grid dimensions was added.

           Code to prevent arithmetic overflow was added.

           Code was added to prevent the values AX2ERR and AX3ERR from
           ever becoming negative when the components of the ray's
           direction vector in the corresponding directions are zero or
           too small for a voxel step in those directions to occur.

           Renamed the routine's arguments, except for NVX.

           Detailed output descriptions were updated to refer to
           voxel coordinates rather than IDs. References to sorting
           were deleted.

           In-line comments now explain the routine's algorithm.
           Old comments that are no longer applicable were deleted.

        DSKLIB Version 2.1.0, 26-JUL-2010 (NJB)

           Bug fix: voxel space coordinates of input
           vertex are now bracketed within the voxel
           grid.

           This prevents round-off errors from occurring
           when the vertex is slightly outside the grid,
           but may not be appropriate for all applications.
           Therefore it may make sense to make this a
           private routine.

        DSKLIB Version 2.0.0, 20-APR-2010 (NJB)

           Removed commented out lines declaring and calling VOX2ID.

        DSKLIB Version 1.1.0, 08-OCT-2009 (NJB)

           Updated header.

           Bug fix: driving axis for intercept computation is
           now determined by largest component of ray direction vector.
           This fix was made long before this header update.

        DSKLIB Version 1.1.0, 19-OCT-2004 (EDW)

           Added logic to remove duplicate voxel IDs from
           the return list. Extended programming comments.

        DSKLIB Version 1.0.1, 26-AUG-2002 (BVS)

           Replaced WRITE with normal error reporting calls.

        DSKLIB Version 1.0.0, 03-FEB-1999 (JAB)