| DSK Required Reading |
Table of ContentsDSK Required Reading Abstract Purpose Intended Audience References Introduction DSK Software High-Level DSK-Enabled Geometry Functions DSK File Loading and Unloading DSK Utility Functions DSK Type 2 Functions DLA and DAS Functions Surface Name and ID Conversion Functions SPICE Toolkit DSK Utility Programs Non-SPICE Toolkit DSK Utility Programs DSK Concepts Shapes and Surfaces Surface IDs Defining Surface Name-ID Mappings Segments DLA and DSK Descriptors Reference Frames Coordinate Systems and Spatial Coverage Spatial coverage: Dimensions Spatial coverage: Gaps and Padding Time Bounds Data Types Data Classes Data Competition and Priority Greedy Algorithms Greedy Ray-Segment Boundary Intercepts DSK Type 2 Plate Expansion Additional Greedy Algorithms DSK Tolerances Drawbacks Access to DSK Tolerances and Margin Values DSK Files DAS Files DLA Files DSK File Format DSK Type 2: Triangular Plate Model Type 2 Shape Data Vertices Plates Type 2 Ancillary Information Pointers and Offsets DSK Type 2 Segment Parameters Spatial Index: Voxel-Plate Mapping Fine Voxel Grid Fine Voxel Scale Coarse Voxel Grid Purpose of the Coarse Voxel Grid Voxel-Plate Pointer Array Voxel-Plate Association Array Size of the Voxel-Plate Association Array Spatial Index: Vertex-Plate Mapping Structure of the Vertex-Plate Mapping Size of the Vertex-Plate Mapping Array Layout of DSK Type 2 Segments DSK Type 2 Integer Segment Component DSK Type 2 Double Precision Segment Component Coordinate System Parameters Common Problems Slow DSK Computations Non-Portable and Unstable Results Non-Convex and Multi-Valued Surfaces DSK File Creation Errors MKDSK Setup File Errors Data Errors Segment Coverage Errors Poor Data Distribution Across Segments Appendix A --- Revision History 2017 APR 05 by N. J. Bachman. Appendix B --- DSK Subsystem Limits General Limits DSK Type 2 Segment Limits DSK Required Reading
Abstract
Purpose
Intended Audience
This document assumes you already have a strong understanding of SPICE concepts and terminology. References
https://naif.jpl.nasa.gov/naif/tutorials.html
The programs
DLACAT BINGOare utilities that are not part of the SPICE Toolkit, but that operate on DSK files. They are available on the NAIF web site at
https://naif.jpl.nasa.gov/naif/utilities.html Introduction
DSK data also can represent shapes of artificial objects such as spacecraft components, or represent abstractions such as the subset of a target body's surface that has a property of interest. The DSK subsystem comprises software, the DSK file format specification, and documentation. The primary purpose of the DSK subsystem is to enable SPICE-based applications to conveniently and efficiently use detailed shape data in geometry computations performed by SPICE functions. DSK data enable these functions to produce more accurate results than those obtainable using triaxial ellipsoid shape models. See the section below titled ``High-Level DSK-Enabled Geometry Routines'' for details. The DSK implementation ensures that shape data used by SPICE are accompanied by all of the attribute information necessary for correct, programmatic use of the data---including, but not limited to, reference frames, central bodies, coordinate systems, spatial coverage bounds, and time bounds of applicability. The DSK format enables data to be augmented by indexes, or other pre-computed parameters, that greatly enhance the speed of common geometric computations, such as those of ray-surface intercepts. DSK data sets can be distributed across multiple DSK files; this is normal for large data sets. Such sets of files can be ``loaded'' (made available for read access by CSPICE software) concurrently; CSPICE software will select data from the appropriate files as needed to perform computations. The DSK file format facilitates storage, transmission, and archival of shape data. It allows the data to be annotated with free-form descriptive comments, also called ``metadata.'' DSK documentation uses the term ``data type'' to refer to types of mathematical shape representations, associated DSK file formats, and software. The DSK subsystem is designed to accommodate multiple data types, and to enable high-level SPICE geometry software to function independently of these types. Currently there is only one DSK data type, which represents the shape of an object by a set of triangular plates. This representation is called a ``tessellated plate model'' or ``triangular plate model.'' The DSK documentation refers to this type as ``DSK type 2.'' Support for digital elevation models (DEMs) will be added in a later version of the SPICE Toolkit; one or more new DSK data types will be developed to support such data. Because many popular file formats for shape data exist, and because it is impractical for these formats to be used directly by SPICE for geometric computations, the DSK subsystem supports conversion of a variety of text-based shape data file formats to DSK format; it also supports conversion of DSK files to a variety of text formats. DSK Software
High-Level DSK-Enabled Geometry Functions
All of these routines perform computations that involve a target body. All can model the shape of that body using data provided by DSK files. Many of the functions can use triaxial ellipsoid models as well. These functions have extensive header documentation. Each header describes all input and output arguments and includes one or more example programs accompanied by example meta-kernels and corresponding program outputs.
DSK File Loading and Unloading
DSK Utility Functions
Functions for DSK file creation:
Function for fetching DSK segment attributes:
DSK Type 2 Functions
DLA and DAS Functions
Some lower-level functionality is provided by functions of the DLA and DAS subsystems. The routines below support linear traversal of the doubly linked list---also called ``searching'' the list---of DSK segments within a DSK file:
Surface Name and ID Conversion Functions
SPICE Toolkit DSK Utility Programs
Non-SPICE Toolkit DSK Utility Programs
DSK ConceptsShapes and Surfaces
The term ``surfaces'' is also used to refer to DSK data sets themselves, particularly when there are multiple data sets, differing in some aspects, that provide data for a given body. For example, Mars topography data sets based on MGS MOLA data might be referred to as the ``64 pixels/degree surface'' or the ``128 pixels/degree surface.'' Surface IDs
At run time, calls from user applications to CSPICE functions can restrict the DSK data used to those from specified surfaces. For example, a user application might direct the CSPICE sub-observer point function subpnt_c to to use a high-resolution surface for a spacecraft altitude computation, versus a low-resolution surface for plotting the spacecraft's ground track. Because surface IDs enable SPICE applications to select data from among those available in loaded DSK files, it is not necessary for applications to repeatedly load and unload DSK files to control which shape data are used for a given body and computation. Applications normally can load at start-up all of the DSK data for a given body, then select the data to be used on a per-computation basis. Avoiding repetitive DSK loading tends to improve an application's computation speed. This is because after any change to the set of loaded DSK files, the DSK subsystem must perform some bookkeeping computations before DSK-based computations can be performed. Degradation of overall execution speed due to these computations is slight as long as they're performed infrequently. SPICE surface IDs are associated with surface names; these associations are made via assignments in SPICE text kernels. Surface name-ID associations are made for specific bodies: the combination of a body name or body ID and surface name can be mapped to a surface ID code, and the combination of a body name or body ID and a surface ID code can be mapped to a surface name. A given surface ID code can be re-used for different bodies without ambiguity. For a given body, it's important for users to coordinate assignment of surface names and surface IDs. The CSPICE functions for converting between surface IDs and surface names are listed in the section ``Surface Name and ID Conversion Functions'' above. Defining Surface Name-ID Mappings
NAIF_SURFACE_NAME += ( <surface name 1>, ... ) NAIF_SURFACE_CODE += ( <surface code 1>, ... ) NAIF_SURFACE_BODY += ( <body code 1>, ... )Above, the Ith elements of the lists on the assignments' right hand sides together define the Ith surface name/ID mapping. The same effect can be achieved using assignments formatted as follows:
NAIF_SURFACE_NAME += <surface name 1>
NAIF_SURFACE_CODE += <surface code 1>
NAIF_SURFACE_BODY += <body code 1>
NAIF_SURFACE_NAME += <surface name 2>
NAIF_SURFACE_CODE += <surface code 2>
NAIF_SURFACE_BODY += <body code 2>
...
Note the use of the
+=operator; this operator appends to rather than overwrites the kernel variable named on the left hand side of the assignment. Segments
Each DSK segment contains data for some or all of the surface of a single body object. This object is called the ``body,'' ``central body,'' or ``center,'' even though it need not be a natural solar system body. Within a segment, the data have the following attributes in common:
When DSK files are loaded via one or more calls to furnsh_c, all segments from those files become available to the DSK subsystem for use in computations. At run time, when a request for shape data for a specified body is made to the DSK subsystem, all segments for that body can be considered as possible sources of data to satisfy the request. For small DSK data sets, such as low-resolution shape models for asteroids, a single segment can suffice to store all of the data for the model. Large DSK data sets typically consist of tens or hundreds of segments distributed over multiple DSK files. Normally all segments for a given body can be loaded at one time. The limit on the total number of DSK segments for all bodies that can be loaded is given in Appendix B. DSK utilities typically create or operate on segments:
DLA and DSK Descriptors
The DLA descriptor of a DSK segment indicates the location of the segment's data in the DSK file containing that segment. DLA descriptors contain DAS base addresses and sizes of the double precision and integer components of the associated segments. DLA descriptors are integer arrays. User applications can locate all segments in a DSK file by calling the DLA ``begin forward search'' routine dlabfs_c, then repeatedly calling the DLA ``find next segment'' routine dlafns_c. See the API documentation of those functions for details and code examples. The DSK descriptor of a DSK segment contains the segment's attribute information; these are the attributes listed above. User applications can determine attributes of a DSK segment by obtaining the DLA descriptor of the segment, then calling the CSPICE function dskgd_c to obtain the segment's DSK descriptor. See the chapter ``DSK Files'' for details. Reference Frames
Within a DSK segment, all shape data are expressed relative to that segment's reference frame. For example, if a segment containing data for Phobos uses the IAU_PHOBOS body-fixed frame, and if the segment contains vertices of triangular plates, the coordinates of those vertices are expressed in the IAU_PHOBOS reference frame. The set of DSK segments to be used in a computation for a given body need not be associated with a single reference frame, but using data from mixed frames should be done cautiously. It is up to the user to combine data in ways that make sense. For example, Mars data expressed in the Mars-centered IAU_MARS frame can be used together with Mars data expressed in one or more Mars topocentric frames. On the other hand, it doesn't make sense to combine earth data expressed in the ITRF93 frame with data expressed in the IAU_EARTH frame, because those frames have some relative rotation. The same is true for data expressed in the IAU_MOON and MOON_ME frames: even though these are realizations of the same reference frame, the approximation error in the IAU_MOON frame is time-dependent, so these frames have relative rotation. Coordinate Systems and Spatial Coverage
The supported coordinate systems are:
Planetodetic coordinates should be used only for large bodies having surfaces well approximated by spheroids. Rectangular coordinates may be appropriate for data sets expressed in topocentric reference frames, for artificial structures, and for extremely irregular natural bodies. A segment's coordinate system is used to represent the segment's coverage bounds. For example, a DSK segment that uses the Phobos planetocentric coordinate system and IAU_PHOBOS reference frame might contain surface data for Phobos within the spatial region
Planetocentric latitude: -90 to +90 degrees Planetocentric longitude: -180 to +180 degrees Radius: 0 to 10 kmHere the planetocentric coordinate system's equatorial plane is the X-Y plane of the IAU_PHOBOS frame. The prime meridian of the coordinate system lies in the frame's X-Z plane and intersects the +X axis of the frame. Another example: a DSK segment that uses a Mars planetodetic coordinate system might contain surface data for Mars within the spatial region
Planetodetic latitude: -30 to +30 degrees Planetodetic longitude: +60 to +90 degrees Altitude: -10 to +20 kmHere the planetodetic coordinate system's equatorial plane is the X-Y plane of the segment's reference frame, for example the IAU_MARS frame. The prime meridian of the coordinate system lies in the frame's X-Z plane and intersects the +X axis of the frame. The altitude is measured relative to a reference spheroid, the size and shape parameters of which are contained in the segment. A third example: a DSK segment that contains data for a horizon mask for a tracking station might use rectangular coordinates and a topocentric frame having axis directions
X: north Y: west Z: upThe region covered by the segment might be
X: -0.5 to +0.5 km Y: -0.5 to +0.5 km Z: -0.2 to +0.2 kmIn this case the horizon mask need not model the topography surrounding the station; it can simply model obscuration due to the topography. So the coverage region need not extend to the horizon; it can be contained in a small box enclosing the station. Spatial coverage: Dimensions
For many applications, it is more natural to consider the spatial coverage of a segment to be two-dimensional. This is true when the surface represented by the segment can be expressed as a function that maps a two-dimensional region to radius or height values. For example, surface height relative to a reference spheroid can be a function of planetodetic longitude and latitude. In a topocentric frame, the Z coordinate of a surface can be a function of the X and Y coordinates. In cases where a surface is viewed as a function of two coordinates, those coordinates are called the ``domain coordinates.'' In some DSK documentation, the terms ``horizontal'' or ``tangential'' coordinates may be used as synonyms. The DSKBRIEF summary utility displays spatial coverage in three dimensions for individual segments. It treats spatial coverage as two-dimensional for the purpose of displaying combined coverage of multiple segments, and for displaying gaps within that combined coverage. For such displays, coverage and gaps will be displayed as longitude-latitude rectangles in the planetocentric or planetodetic systems, or as X-Y rectangles in the rectangular system. Spatial coverage: Gaps and Padding
Spatial coverage gaps also can occur due to the way data are grouped in segments by a DSK file's creator. Normally DSK file creators should ensure that segments don't have coverage gaps that users would not expect. Coverage gaps can cause geometric computations to fail at run time. The concept of spatial coverage gaps normally applies to a segment's domain coordinates, such as longitude and latitude. It is also possible for a surface's maximum or minimum height, radius, or Z coordinate to be, respectively, strictly less than or strictly greater than the corresponding upper or lower bound. The term ``gap'' usually does not apply to such differences; these differences usually have no impact on computations. Data for a segment need not be confined to the spatial region delimited by the spatial bounds. DSK creators can include in DSK segments ``padding'' data that extend slightly beyond the segments' spatial bounds. Padding data can ensure that coverage implied by a segment's domain coordinate bounds is really present. Time Bounds
For a surface having a shape that evolves over a time span of interest, multiple versions of the surface corresponding to different time intervals can be created. When a computation is performed for a particular time, only segments providing data for time intervals that include that time will be considered. In many cases the surface represented by a DSK segment is considered to be constant with respect to time, so the start and stop time bounds may be set, respectively, to values far in the past and future (for example, plus or minus one century) relative to the time range for which the segment is expected to be used. Data Types
DSK data type 2 represents body shapes using collections of triangular plates. Another DSK data type, not yet implemented, will represent surfaces as digital elevation models (DEMs). The CSPICE system's high-level geometry functions operate without reference to the data types of DSK segments providing shape data to these routines. These routines require lower-level, type-dependent routines to provide functionality that is common across all DSK data types, such as ``find the intercept of a ray with the surface defined by a segment,'' or ``return the unit length outward normal vector at a specified point on the surface defined by a segment.'' Some CSPICE functions perform functions specific to particular data types. For example, the functions dskv02_c and dskp02_c return, respectively, vertices and plates from a type 2 segment. Data Classes
Data Competition and Priority
Unlike the other SPICE binary kernel systems, the DSK subsystem does not necessarily make use of segment priority for a given computation. Instead, a user application can specify that a computation is ``unprioritized.'' This means that all loaded data for the given body and a specified list of surfaces are to be used together to represent the shape to be used in the computation. When DSK data for different surfaces for one body are loaded concurrently, surface lists, which are inputs to CSPICE API functions that use DSK data, can be used to ensure that the correct set of DSK data are used for a given computation, and that none of the data compete. It is not necessary to load or unload DSK files to give the desired data top priority. See the API documentation for any high-level CSPICE geometry function, for example sincpt_c, for a discussion of surface lists. In the N0066 CSPICE Toolkit, all high-level geometry functions that work with DSK data support only unprioritized computations. Although not currently used, the DSK subsystem does have a priority scheme: as in the SPICE SPK, CK, and binary PCK subsystems, when two segments from the same file compete, the one located later in the file (at higher addresses) takes precedence. When two segments from different files compete, the one from the file loaded later takes precedence. Greedy Algorithms
The possibility of false negatives, at a minimum, complicates the design of user applications that depend on DSK data. Aside from errors in DSK files themselves, the main cause of false negative results is round-off error. Round-off error can cause a ray that should hit the common edge between two plates to be determined, according to double precision arithmetic, to miss both plates. Similarly, round-off error can cause a ray that should hit the common longitude boundary or latitude boundary shared by two DSK segments to hit neither segment boundary. The DSK subsystem uses several techniques to avoid false negative results for ray-surface intercepts. These fall into the category of ``greedy algorithms'': they effectively treat segments and data as though they occupy not only the spatial regions implied by their boundaries, but the surrounding regions as well. (An examination of the default DSK ``greedy'' parameters will reveal that the greediness of DSK algorithms is a mild case. See ``Access to DSK Tolerances and Margin Values'' below.) For example, when a ray-surface intercept computation is attempted, an intercept is considered to exist if the ray passes sufficiently close to the target---not only if it hits. Greedy Ray-Segment Boundary Intercepts
By default, when the ray's intersection with a segment's tangent surface is computed, if that intersection is close to the spatial region indicated by the segment's boundaries, an intersection with the segment is considered to exist. In the example we're using, a ray's intersection with the sphere of radius 6400 km that has longitude slightly greater than 30 degrees and latitude slightly greater than 45 degrees could be considered an intersection with the segment's boundary, if the longitude and latitude excursions are within margins. The goal is to ensure that any segment that the ray might hit is considered for a more detailed intercept computation. DSK Type 2 Plate Expansion
The default plate expansion fraction is 1e-10. The expansion factor is
1 + expansion_fraction Additional Greedy Algorithms
DSK Tolerances
Drawbacks
For example, if a ray hits the edge of an expanded plate, and that plate has a maximum edge length of 1 km, then the ray might have missed the original plate by as much as 0.1 millimeters. After missing the original plate, the ray might hit the surface far from that plate, or it might miss the target altogether. This issue, while it may appear serious, is a normal consequence of using finite precision arithmetic. A comparable difference in results might be observed were the computation without plate expansion performed on two different computer systems. Access to DSK Tolerances and Margin Values
The parameters used for greedy algorithms are user-adjustable. Applications can call the functions dskgtl_c or dskstl_c to fetch or reset these parameters at run time. It is recommended that the parameters be reset only by expert users. DSK Files
The DSK file format is based on two lower-level SPICE file formats: the DSK format is a special case of the SPICE DLA format, which in turn is a special case of SPICE DAS format. DAS Files
DLA Files
DLA files indicate the DAS addresses and sizes of their segments' character, double precision, and integer components using data structures called ``DLA descriptors.'' The DLA segment descriptor members are:
+---------------+ | BACKWARD PTR | Linked list backward pointer +---------------+ | FORWARD PTR | Linked list forward pointer +---------------+ | BASE INT ADDR | Base DAS integer address +---------------+ | INT COMP SIZE | Size of integer segment component +---------------+ | BASE DP ADDR | Base DAS d.p. address +---------------+ | DP COMP SIZE | Size of d.p. segment component +---------------+ | BASE CHR ADDR | Base DAS character address +---------------+ | CHR COMP SIZE | Size of character segment component +---------------+The ``base address'' of a segment component of a given data type is the address, in the DAS address space of that type, preceding the first element of that component. All DAS addresses are 1-based. DLA descriptors are used in the DSK subsystem to identify locations of the components of DSK segments within DSK files. See the DLA Required Reading, dla.req, for details concerning the DLA subsystem and file format. DSK File Format
+----------------------------------+ | File Record | +----------------------------------+ | Comment Area | +----------------------------------+ | Segment 1 | +----------------------------------+ -+ | ... | | +----------------------------------+ | Optional | Segment N | | +----------------------------------+ -+That is, a DSK file contains some identification and bookkeeping information called a ``file record,'' it has a comment area, and it has one or more DSK segments containing shape data. The segments are connected to each other as a doubly linked list, and the list can be traversed in forward or backward order. (In the N0066 Mice and Icy Toolkits, only forward traversal is supported.) Each DSK segment has integer and double precision components. These components occupy, respectively, contiguous ranges of DAS integer and double precision addresses:
+----------------------------------+
| Segment I | =
+----------------------------------+
+--------------+ +------------------+
| | | |
| Segment I: | | Segment I: |
| | | |
| Integer | + | Double |
| Component | | Precision |
| (optional) | | Component |
| | | |
+--------------+ | |
| |
+------------------+
The double precision component of a segment can be further expanded as:
+------------------+
| |
| Segment I: |
| |
| Double |
| Precision | =
| Component |
| |
| |
+------------------+
+--------------+ +------------------+
| Segment I: | | Segment I: |
| | | |
| DSK Segment | + | Double |
| Descriptor | | Precision |
+--------------+ | Data |
| (optional) |
| |
| + Bookkeeping |
| Information |
| (optional) |
| |
+------------------+
The base addresses and sizes of a DSK segment's integer and double
precision components are given by the segment's DLA descriptor. The DAS
integer address range of a DSK segment is
integer base address+1 : integer base address+
integer component size
Similarly, the DAS double precision address range of a DSK segment is
d.p. base address+1 : d.p. base address+
d.p. component size
Low-level details of the general DSK file format, if not discussed in
this document, can be obtained from the DAS Required Reading, das.req,
and from the DLA Required Reading, dla.req.
An abstract view of a DSK segment---a view that ignores physical file layout and numeric data types---is
DSK segment =
+-------------------------------------+
| DSK Descriptor |
+-------------------------------------+
| Type-specific shape data |
+-------------------------------------+
| Type-specific ancillary information |
+-------------------------------------+
DSK segments of all data types contain DSK descriptors.
Further details of the DSK segment's structure are data type-dependent. Currently there is just one DSK data type: type 2. It is discussed below. DSK Type 2: Triangular Plate Model
Type 2 Shape Data
Each triangular plate has three vertices: type 2 data consist of a set of vertices and a set of ``plates'' to which the vertices belong. Vertices
The components of a vertex are expressed in the body-fixed reference frame of the DSK segment to which the vertex belongs. Each vertex represents an offset from the center of that reference frame. The center of a type 2 segment's reference frame need not coincide with the body for which the segment provides data. For example, vertices for a DSK segment representing Mars topography might be expressed in a Mars topocentric frame; the vertices would then represent offsets from the Mars surface point at the center of that frame. Within a type 2 segment, vertex components are always expressed in units of km, regardless of the units associated with the input data from which the segment was constructed. Each vertex has an associated integer ID; vertex IDs range from 1 to NV, where NV is the number of vertices in the segment. This 1-based numbering scheme is used for all language versions of SPICE, so the vertex IDs in a DSK file match those used in SPICE DSK code on all platforms. Plates
As a data structure, a plate is a 3-tuple of integer vertex IDs that indicate which vertices belong to that plate. Each plate has an associated ``outward normal'' direction: this direction is perpendicular to the plate. For surfaces that constitute boundaries of solid objects---for example, a sphere---the outward normal direction has the usual meaning: it points toward the exterior of the object. For other surfaces, for example a single plate, the outward normal direction may be an arbitrary choice. The order of a plate's vertices implies the outward normal direction: if the vertices are
V(1), V(2), V(3)then the outward normal direction is
( V(2) - V(1) ) x ( V(3) - V(2) )where ``x'' denotes the vector cross product operator. DSK creators must take vertex order into account when they define the plates of a DSK type 2 segment. As the formula above shows, the outward normal direction is undefined if two or three vertices of a plate coincide; in this case the ``plate'' is actually a line segment or a point. Plates having these characteristics are termed ``degenerate.'' Even if all of a plate's vertices are distinct, the normal direction vector suffers great loss of precision if the angle between two plate edges is very close to zero. Degenerate and nearly degenerate plates are allowed in type 2 segments, but it is strongly recommended that DSK creators exclude them from input data sets. Such plates can cause run-time failures of user applications performing functions that require outward normal directions to exist, for example computing emission and solar incidence angles. Each plate has an associated integer ID; plate IDs range from 1 to NP, where NP is the number of plates in the segment. This 1-based numbering scheme is used for all language versions of SPICE, so the plate IDs in a DSK file match those used in SPICE DSK code on all platforms. Type 2 Ancillary Information
A DSK type 2 spatial index consists of a ``voxel-plate mapping'' and optionally, a ``vertex-plate mapping,'' as well as various associated parameters. All DSK type 2 segments contain a voxel-plate mapping. This mapping enables DSK type 2 software to rapidly determine which plates are near a specified ray or point. Pointers and Offsets
In a DSK type 2 segment, pointers and offsets are expressed relative to the DAS base addresses of that segment, or relative to the DAS addresses of other members of the segment. This ensures that the segment is ``relocatable'': it has no dependence on its absolute DAS addresses and can be moved or copied without corrupting its contents. DSK Type 2 Segment Parameters
A subset of these parameters refer to the segment's voxel grids. They are listed here; they are explained later in context. The integer parameters are:
Spatial Index: Voxel-Plate Mapping
The voxel-plate mapping plays a critical role in DSK geometry computations, because it enables plates relevant to computation to be located quickly:
+---------------+ | | | | | | | | +-------------+ | | | | | | | | | | | | | | +-------------+ | | | | | | | | | | +--------+ | | | | | | | | | | | | | Fine | | Coarse | | Voxel-plate | | Voxel-plate | | voxel |-->| voxel |-->| pointer |-->| association | | grid | | grid | | array | | array | | | | | | | | | | | +--------+ | | | | | | | | | | | | +-------------+ | | | | | | | | | | | | | | | | +-------------+ | | | | | | +---------------+The structures shown above enable DSK software to map a point in 3-dimensional space to a set of nearby plates as follows:
Fine Voxel Grid
The sides of the grid are aligned with the coordinate axes of the DSK segment's reference frame. A segment's fine voxel grid contains all vertices in the segment (and therefore all plates); a small margin is used so that no plate contacts the grid's boundary. Thus no point on or outside of the grid's boundary can touch a plate. The fine voxel grid is fully characterized by
The diagram below shows the position of the fine voxel grid relative to its origin, the orientation of the grid relative to the reference frame's axes, and the relationship between the grid extents and the dimensions of the fine voxel grid. In this diagram
.------------. ^ fine voxel count =
/ /| | VGREXT(3)
/ / | |
/ / | | length =
/ / | | VGREXT(3) * VOXSIZ (km)
^ +Z / / . . v
| . .------------. / /
| / | | / /
| /+Y | | / / fine voxel count = VRGEXT(2)
| / | | / /
|/ | |/ / length =
*-------> O------------* * VGREXT(2) * VOXSIZ (km)
+X
<------------>
fine voxel count = VGREXT(1)
length = VGREXT(1) * VOXSIZ (km)
Fine Voxel Scale
A plate's ``extent'' in the direction of coordinate axis i is the maximum value of coordinate i, taken over the plate's three vertices, minus the minimum value of coordinate i, also taken over the plate's three vertices. The average extent of a segment's plate set is the average of all the the plates' extents in the X, Y, and Z directions. The fine voxel scale maps the plate set's extents to a voxel size by:
VOXSIZ = file_voxel_scale * average_plate_extent Coarse Voxel Grid
The voxels of the coarse grid are cubes of identical size. The edge length of the coarse voxels is an integer multiple of the fine voxels' edge length. Let CGRSCL represent this multiple; then each coarse voxel contains
3
CGRSCL
fine voxels.
We use the term ``parent'' to refer to the unique coarse voxel that contains a specified fine voxel. Each extent of the fine voxel grid is
CGRSCLtimes the corresponding extent of the coarse grid. The diagram below shows the relationship between the coarse voxel grid's extents and edge lengths. The integer array VGREXT, as above, contains the extents of the fine voxel grid. The parameter VOXSIZ contains the fine voxels' edge length.
.------------. ^ coarse voxel count =
/ /| | VGREXT(3) / CGRSCL
/ / | |
/ / | | length =
/ / | | VGREXT(3) * VOXSIZ (km)
/ / . . v
.------------. / /
| | / / coarse voxel count = VRGEXT(2)/CGRSCL
| | / /
| | / / length =
| |/ / VGREXT(2) * VOXSIZ (km)
*------------* *
<------------>
coarse voxel count = VGREXT(1) / CGRSCL
length = VGREXT(1) * VOXSIZ (km)
In the description below, the term ``integer'' refers to an element of
the DAS integer address space.
The DSK integer array representing the coarse voxel grid has one element for each coarse voxel. If any plates intersect the spatial region corresponding to a coarse voxel, the corresponding coarse voxel grid array element contains a pointer into the voxel-plate pointer array. If no plates intersect that spatial region, the voxel contains the value zero, which represents a null pointer. (Caution: for reasons of backward compatibility, the values zero and -1 are used in different parts of DSK type 2 segments indicate null pointers.) Note that during the construction of a spatial index, plate-voxel ``intersection'' may be determined using a margin so that plates very near a voxel are considered to intersect it. This is the case for DSK type 2 segments created by dskw02_c and by MKDSK. A non-null pointer in a given coarse voxel is a 1-based index of a pointer set within the voxel-plate pointer array. The pointer set indicates the locations of plate lists associated with the fine voxels having the coarse voxel as a parent. The maximum coarse voxel count within a segment, SPICE_DSK02_MAXCGR, is set to
100000This value cannot be changed in any future version of SPICE. The value is small enough to make it practical for DSK type 2 software to buffer the entire coarse voxel grid in memory. In all DSK type 2 segments, SPICE_DSK02_MAXCGR integers are allocated for the coarse voxel grid, even if the grid is smaller. Purpose of the Coarse Voxel Grid
The coarse voxel grid allows type 2 segments to avoid storing pointers for all fine voxels, since only fine voxels belonging to non-empty coarse voxels require pointers. Since in many practical cases, the majority of coarse voxels are empty, this often greatly reduces the required number of pointers. The coarse voxel grid also tends to reduce the number of physical file reads necessary to determine the plate set relevant to a given computation, since DSK type 2 software often can use it to quickly determine that a given fine voxel is empty, without looking up a voxel-plate pointer and then a plate list for that voxel. Any fine voxel that belongs to an empty coarse voxel is empty as well, and typically the majority of empty fine voxels do belong to empty coarse voxels. Voxel-Plate Pointer Array
The pointer set for a given coarse voxel contains one pointer for each fine voxel having that coarse voxel as a parent, so there are
3
CGRSCL
pointers in each set.
Let NNECVX indicate the number of non-empty coarse voxels. Then the voxel-plate pointer array has the form:
+---------------------+
| pointer set 1 |
+---------------------+
...
+---------------------+
| pointer set NNECVX | (number of non-empty coarse voxels)
+---------------------+
The mapping from the coarse voxel grid to pointer sets in the
voxel-plate pointer array is determined by the segment's data, the voxel
grid parameters, and the order in which the data are processed. As
indicated in the following diagram, no particular relationship should be
assumed to exist between a non-empty coarse voxel's coordinates in the
coarse grid and the position of its pointer set in the voxel-plate
pointer array:
Coarse voxel grid Voxel-plate pointer array
+--------------------------------+
.->| pointer set for coarse voxel v |
/ +--------------------------------+
/
+----------------+ /
| NULL | /
+----------------+ /
| coarse voxel u |--./ ...
+----------------+ /\
| coarse voxel v |-* \
+----------------+ \
... \ +--------------------------------+
+----------------+ *--> | pointer set for coarse voxel u |
| NULL | +--------------------------------+
+----------------+ ...
| coarse voxel w |--.
+----------------+ \ +--------------------------------+
| NULL | *-----> | pointer set for coarse voxel w |
+----------------+ +--------------------------------+
Above, the letters
u, v, windicate arbitrary voxel indices. The positions of the null values were selected for this example. They're not representative of an actual DSK segment. Within the voxel-plate pointer array, each pointer set has the form:
+-----------+
| pointer | voxel 1
+-----------+
...
+-----------+
| pointer | voxel CGRSCL**3
+-----------+
Each pointer corresponds to a fine voxel in the coarse voxel associated
with the pointer set. Treating the fine voxels in this coarse voxel as a
1-dimensional array, the first fine voxel maps to the first pointer, and
so on. The ordering of the fine voxels is Fortran-style, so a fine voxel
with 1-based indices (I, J, K) relative to its parent coarse voxel has
the one-dimensional index
2
I + (J-1)*CGRSCL + (K-1)*CGRSCL
The fine voxel with coordinates (1, 1, 1) relative to the parent coarse
voxel is located in parent voxel's corner having minimum X, Y, and Z
values in the Cartesian coordinate system associated with the segment's
reference frame.
Voxel-Plate Association Array
Let NNEFVX be the total number of non-empty fine voxels in the fine grid. Let
v_1, v_2, ..., v_NNEFVXindicate NNEFVX indices of non-empty fine voxels in arbitrary order. The voxel-plate association array has the form:
+-------------------------+
| List for voxel v_1 |
+-------------------------+
| List for voxel v_2 |
+-------------------------+
...
+-------------------------+
| List for voxel v_NNEFVX | (number of non-empty fine voxels)
+-------------------------+
Let N be the number of plates in the plate list for voxel v_i. Let
p_1, p_2, ..., p_Nbe the plate IDs of these plates. The plate list for the fine voxel at index v_i has the form
+--------------------+
| List count = N |
+--------------------+
| Plate ID p_1 |
+--------------------+
...
+--------------------+
| Plate ID p_N |
+--------------------+
The mapping from a pointer in the voxel-plate pointer array to a plate
list in the voxel-plate association array is determined by the segment's
data, the voxel grid parameters, and the order in which the data are
processed. As indicated in the following diagram, no particular
relationship should be assumed to exist between the position of a
pointer in the voxel-plate pointer array and the position of the
corresponding plate list in the voxel-plate association array:
Voxel-plate Voxel-plate association array
pointer array
+-------------------------------+
.->| plate list for voxel u_2 |
/ +-------------------------------+
/
/
pointer set u /
+----------------+ /
| voxel u_1 |--./ ...
+----------------+ /\
| voxel u_2 |-* \
+----------------+ \
... \ +-------------------------------+
+----------------+ *--->| plate list for voxel u_1 |
| NULL | +-------------------------------+
+----------------+ ...
| voxel u_n |--.
+----------------+ \ +-------------------------------+
| NULL | *------>| plate list for voxel u_n |
+----------------+ +-------------------------------+
3
CGRSCL elements
Above, the letter ``u'' indicates an arbitrary pointer set in the
voxel-plate pointer array, which contains NNECVX such sets. The
positions of the null values were selected for this example. They're not
representative of an actual DSK segment.
Size of the Voxel-Plate Association Array
Other than the optional vertex-plate association array, the voxel-plate association array is the largest ancillary data structure in a DSK type 2 segment. The size, in units of integers, of this array is affected by the fine voxel scale, which is a user-selectable parameter. For a given plate and vertex set, the size of fine voxels varies in proportion to the fine voxel scale. Let NVOXPL be the size, in units of integers, of the voxel-plate association array; as above, let NNEFVX be the total count of non-empty fine voxels; let NP be the segment's plate count. A lower bound on NVOXPL is
NNEFVX + NPThis number reflects the plate counts for the plate lists of each non-empty fine voxel, plus the presence of each plate ID on at least one list. Normally, a large number of plates cross voxel boundaries and so have their IDs on multiple lists. Hence NVOXPL is normally larger than the lower bound shown above. Reducing the fine voxel size improves the discrimination of the fine grid, which can improve the efficiency of algorithms that must operate on plates associated with a specified spatial region. For example, in the ray-surface intercept computation, the count of plates associated with voxels intersected by the ray will usually decrease as the voxel size is reduced. However, as the fine voxel size is reduced, more plates cross voxel boundaries---such plates are on the plate list of each voxel they touch---and NVOXPL increases. The memory required to hold the spatial index increases as well; it may become too large to allow a program calling dskw02_c (the utility MKDSK is one such program) to run successfully. If a DSK segment with a very large value of NVOXPL is successfully created, its large size may have a detrimental effect on disk access time. Spatial Index: Vertex-Plate Mapping
Currently (as of the time of release of the N0066 SPICE Toolkit) there are no CSPICE routines that rely on the vertex-plate mapping. Creation of this mapping is therefore optional. Both the DSK type 2 writer function dskw02_c and the utility program MKDSK enable users to indicate whether to create a vertex-plate mapping in an output DSK segment. Structure of the Vertex-Plate Mapping
+--------------+
| |
| |
+---------------+ | |
| | | |
| | | |
| | | |
| Vertex-plate |-->| Vertex-plate |
| pointer array | | association |
| | | array |
| | | |
+---------------+ | |
| |
| |
+--------------+
Let NV be the number of vertices in the segment. Then the vertex-plate
pointer array contains NV elements, and the ith element indicates the
plate list associated with vertex i.
The vertex-plate association array contains a plate list for each vertex:
+----------------------+
| List for vertex v_1 |
+----------------------+
| List for vertex v_2 |
+----------------------+
...
+----------------------+
| List for vertex v_NV |
+----------------------+
Let N be the number of plates in the plate list for vertex i. Let
p_1, p_2, ..., p_Nbe the plate IDs of these plates. The plate list for vertex i has the form
+--------------------+
| List count = N |
+--------------------+
| Plate ID p_1 |
+--------------------+
...
+--------------------+
| Plate ID p_N |
+--------------------+
The mapping from a vertex to a plate list in the vertex-plate
association array is determined by the segment's data, the voxel grid
parameters, and the order in which the data are processed. No particular
relationship should be assumed to exist between a vertex ID and the
position of the corresponding plate list in the vertex-plate association
array.
Size of the Vertex-Plate Mapping Array
Let NV be a DSK type 2 segment's vertex count, and let NP be the segment's plate count. Then the size, in units of integers, of the vertex-plate pointer array is
NVand the size of the vertex-plate association array is
NV + 3*NPThe latter value is due to the facts that
Layout of DSK Type 2 Segments
DSK Type 2 Integer Segment Component
+-----------------+
| NV | number of vertices
+-----------------+
| NP | number of plates
+-----------------+
| NVXTOT | total number of voxels
+-----------------+
| VGREXT | voxel grid extents, 3 integers
+-----------------+
| CGRSCL | coarse voxel grid scale
+-----------------+
| VOXNPT | size of voxel-plate pointer list
+-----------------+
| VOXNPL | size of voxel-plate association list
+-----------------+
| VTXNPL | size of vertex-plate association list
+-----------------+
| PLATES | NP 3-tuples of vertex IDs
+-----------------+
| VOXPTR | voxel-plate pointer array, variable size
+-----------------+
| VOXPLT | voxel-plate association list, variable size
+-----------------+
| VTXPTR | vertex-plate pointer array, 0 or
| | NV integers
+-----------------+
| VTXPLT | vertex-plate association list,
| | 0 or NV + 3*NP integers
+-----------------+
| CGRPTR | coarse grid pointers,
| | SPICE_DSK02_MAXCGR integers
+-----------------+
The sizes of all variable-size items are stored at known locations, so
the starting position of any item can be calculated. Parameters
specifying offsets of the items from the segment's base integer address
are declared in SpiceDSK.h. The segment's base integer address is
available from the segment's DLA descriptor.
CSPICE provides the low-level utility function dski02_c to fetch any of the items shown above. Plates and the plate count may be fetched more conveniently using the routines dskp02_c and dskz02_c. DSK Type 2 Double Precision Segment Component
+-------------------+
| DSK descriptor | SPICE_DSK_DSCSIZ d.p. values
+-------------------+
| Vertex bounds | 6 d.p. values (min/max for each component)
+-------------------+
| Voxel grid origin | 3 d.p. values
+-------------------+
| Fine voxel size | 1 d.p. value
+-------------------+
| Vertices | 3*NV d.p. values
+-------------------+
The parameter SPICE_DSK_DSCSIZ is declared in SpiceDSK.h.
CSPICE provides the low-level utility function dskd02_c to fetch any of the items shown above. Vertices and the vertex count may be fetched more conveniently using the routines dskv02_c and dskz02_c. The DSK segment descriptor layout is:
+---------------------+
| Surface ID code |
+---------------------+
| Center ID code |
+---------------------+
| Data class code |
+---------------------+
| Data type |
+---------------------+
| Ref frame code |
+---------------------+
| Coord sys code |
+---------------------+
| Coord sys parameters| 10 d.p. values
+---------------------+
| Min coord 1 |
+---------------------+
| Max coord 1 |
+---------------------+
| Min coord 2 |
+---------------------+
| Max coord 2 |
+---------------------+
| Min coord 3 |
+---------------------+
| Max coord 3 |
+---------------------+
| Start time |
+---------------------+
| Stop time |
+---------------------+
The DSK descriptor of a DSK segment may be fetched using the function
dskgd_c.
Coordinate System Parameters
The contents of this section are dependent on the coordinate system. For planetodetic coordinates, the contents are:
+------------------------+
| Equatorial radius (km) |
+------------------------+
| Flattening coefficient |
+------------------------+
| <undefined> | 8 d.p. values
+------------------------+
These parameters define the axes of a reference ellipsoid. The length of
the polar axis is
polar_axis = (1 - flattening_coefficient) * equatorial_axis
For planetocentric latitudinal and rectangular coordinates, all elements
are undefined.
DSK subsystem computations involving a DSK segment always use the coordinate parameters stored in that segment. These parameters may differ from those specified in a text PCK used by the same application program, or from those specified in a different segment for the same body. It is not necessarily an error for different sets of coordinate parameters to be used in a computation, but DSK users should be aware of which parameters are used for which purpose. Common ProblemsSlow DSK Computations
SPICE users can speed up DSK computations by several means:
Non-Portable and Unstable Results
These problems are best avoided at the time application software is designed: software developers must account for the effects of round-off error. Non-Convex and Multi-Valued Surfaces
Even a slight deviation from convexity can change numerical results considerably from those obtained using a triaxial ellipsoid model. For example, depending on whether there is a mountain in the foreground or whether the intercept lies in a valley (oriented in the general direction of the ray's projection on the surface), the range from an observer to a ray-surface intercept point can be much shorter or longer than the distance to the ray's intercept on the target body's reference ellipsoid. Non-convex surfaces can, in some cases, render some geometric quantities undefined or unusable. For example, the nearest surface point to a given point, not on the surface, can have multiple solutions, all in substantially different directions from the given point. Another example: the origin of a body-fixed reference frame for an object may be outside of the object--- a surface modeling a planetary ring would have this property. Multi-valued surfaces are those for which, for a given latitude and longitude, or for a given (X,Y) value, there are multiple radius or height values. These surfaces can occur due to presence of topographic features such as cliffs, caves, and arches. They can also occur due to the large-scale shape of an object, as is the case for the nucleus of the comet Churyumov-Gerasimenko. Multi-valued surfaces invite new categories of errors not possible with single-valued, non-convex surfaces. For example, for a given observer position, the sub-observer point can vary depending on the observer's altitude. Software meant for use with single-valued surfaces, for example the function latsrf_c, may yield incorrect results for such cases. Multi-valued surfaces can yield discontinuities in derived quantities that are well-behaved when an ellipsoid is used to model the target's shape. For example, when an observing spacecraft overflies a cliff, the observer's altitude can change discontinuously. If the sub-spacecraft point is corrected for light time, the light time algorithm may converge slowly or not at all. Again, these problems are best solved by designing application software to avoid assumptions appropriate only for ellipsoids. DSK File Creation Errors
MKDSK Setup File Errors
Data Errors
Segment Coverage Errors
This is an easy error to make when a large data set is distributed across multiple DSK files. The DSK creator may assume that the original plate set, partitioned among various files, will yield the same coverage as if all plates were stored in a single segment. Not so---each segment can only provide the coverage its DSK descriptor claims it has, so if a plate needed by a segment to provide coverage near, but within, that segment's boundary is allocated to a different segment, the first segment's coverage will have a gap. An artificial, but simple, example of this is a tessellation of a sphere, using triangular plates. Suppose that the surface is partitioned into a 6 x 12 grid of segments, each covering a 30 degree by 30 degree region of planetocentric longitude and latitude. Suppose each segment contains 225 pairs of plates such that each pair covers a longitude-latitude rectangle having angular extent 2 degrees by 2 degrees, so each segment is ``covered'' by 450 plates. Consider the segment covering the coordinate rectangle
Planetocentric longitude (deg): 0 to +30 Planetocentric latitude (deg): +30 to +60For each plate having two vertices on the segment's southern boundary, the edge of that plate connecting those vertices has latitude greater than 30 degrees everywhere but at the vertices themselves. At the midpoint of that edge, the latitude is actually about 30.00378 degrees. A ray aimed from an exterior vertex to the center of the sphere will miss the surface if the longitude of the vertex is 15 degrees and latitude of the vertex is above 30 degrees but less than the latitude of the edge's midpoint. The solution is to create each segment using ``padding''---additional plates extending slightly beyond the segment's southern boundary, so no ray emanating from the origin and hitting the sphere within the segment's longitude-latitude coverage can miss all of the segment's plates. The same problem exists for all southern segment latitude boundaries having positive latitude, and for all northern segment latitude boundaries having negative latitude. All of these boundaries require padding in order to achieve the intended coverage. Poor Data Distribution Across Segments
A seemingly attractive choice that can lead to this problem is partitioning a large data set into a small number of files, each of which contains a large number of plates. Type 2 segments can contain 10000000 or more plates (see Appendix B), but as a segment's plate count increases, the speed of DSK ray-surface intercept computations decreases. Experience indicates that DSK ray-surface intercepts exhibit an ``economy of small scale'' phenomenon, whereby spreading data across multiple, small segments tends to improve performance. This is true only up to a point: as the number of segments grows, the amount of time spent reading new data when switching from one segment to another grows. At some point this overhead becomes a significant drag on performance. Appendix A --- Revision History2017 APR 05 by N. J. Bachman.
Appendix B --- DSK Subsystem Limits
See the file
SpiceDSK.hfor declarations of public parameters defining DSK limits. General Limits
DSK Type 2 Segment Limits
PC-64BIT-MS_C PC-CYGWIN-64BIT-GCC_C PC-CYGWIN-64BIT-GFORTRAN PC-CYGWIN-GFORTRAN PC-CYGWIN_C PC-MS_C PC-WINDOWS-64BIT-IFORT PC-WINDOWS-IFORT SUN-SOLARIS SUN-SOLARIS-64BIT-GCC_C SUN-SOLARIS-64BIT-NATIVE_C SUN-SOLARIS-GCC_C SUN-SOLARIS-NATIVE_Cthe following limits apply:
|