maspack.geometry

## Class DistanceGrid

• All Implemented Interfaces:
HasRenderProps, IsRenderable, IsSelectable, Renderable, Scannable
Direct Known Subclasses:
SignedDistanceGrid

```public class DistanceGrid
extends ScalarGridBase```
Implements a distance field on a regular 3D grid. Distances, normals and gradients can be interpolated between grid points using either linear or quadratic interpolation. Methods are provided to compute the distance field based on nearest distances to a set of geometric features, such as vertices, edges, or faces. One common use of such a field is to detect point penetration distances and normals for use in collision handling.

The field is implemented using a regular 3D grid composed of `nx` X `ny` X `nz` vertices along the x, y and z directions, giving the grid a resolution of `rx`, `ry`, `rz`, cells along each of these directions, where `rx = nx-1`, `ry = ny-1`, and ```rz = nz-1```. The grid has widths `w = (wx, wy, wz)` along each of these directions, and cell widths given by `wx/rx`, `wy/ry`, and `wz/rz`.

Several coordinate frames are associated with the grid: the local frame L, the world frame W, and the grid frame G. Details on these are given in the documentation for `InterpolatingGridBase`.

Support is provided to compute the distance field from sets of underlying mesh features (such as faces or vertices). These computations are done in the local frame.

Distances for any point within the grid can be obtained by interpolation of the distances at surrounding vertices. Interpolation can be either linear or quadratic. Linearly interpolated distances are obtained using `getLocalDistance(maspack.matrix.Point3d)` and are computed using trilinear interpolation within the grid cell containing the point. If the query point is outside the grid, then the distance is assigned the special value `ScalarGridBase.OUTSIDE_GRID`. Normals can also be obtained, using the `getLocalDistanceAndNormal` methods. Normals are also interpolated using trilinear interpolation, with the normals at each vertex being computed on demand by mid-point differencing with adjacent vertices. Note that this means that the normals do not correspond to the gradient of the distance function; however, their interpolated values are smoother than those of the gradient. Gradient values can be obtained instead, using the `getLocalDistanceAndGradient` methods. The returned gradient is the true gradient of the distance function within the interpolating cell and a linear function within that cell. All inputs and outputs for the above described distance methods are assumed to be in local coordinates. The method `getWorldDistance(maspack.matrix.Point3d)` and associated `getWorldDistanceAndNormal` and `getWorldDistanceAndGradient` methods perform the same operations in world coordinates.

Quadratically interpolated distances are obtained using `getQuadDistance(maspack.matrix.Point3d)`. Quadratic interpolation is done within a composite quadratic cell composed of 2 x 2 x 2 regular cells. To ensure that all points within the grid can be assigned a unique quadratic cell, the grid resolution is restricted so that `rx`, `ry` and `rz` are always even. Moreover, within each quadratic cell, interpolation is done by partitioning the cell into six tetrahedra, each with 10 nodes, and then performing quadratic interpolation within the appropriate tetrahedron. This is done to ensure that the interpolation function is exactly quadratic instead of tri-quadratic. Because the interpolation is exactly quadratic, certain operations, such as intersecting level set surfaces, can be performed by solving a simple quadratic equation. The gradient of the quadratically interpolated distance function can also be obtained using `getQuadDistanceAndGradient(maspack.matrix.Vector3d, maspack.matrix.Matrix3d, maspack.matrix.Point3d)`; this will return the gradient of the distance function within the quadratic cell containing the query point. These gradient values are smoother than those associated with linear interpolation and so (if normalized) can be used to provide normal vectors. Consequently, quadratically interpolated normals, analagous to those returned by `getLocalDistanceAndNormal(maspack.matrix.Vector3d, double, double, double)`, are not currently supported. All inputs and outputs for the above described quadratic distance methods are assumed to be in local coordinates. The methods `getWorldQuadDistance(maspack.matrix.Point3d)` and `getWorldQuadDistanceAndGradient(maspack.matrix.Vector3d, maspack.matrix.Matrix3d, maspack.matrix.Point3d)` perform the same operations in world coordinates.

Distances at the grid vertices can either be assigned directly, using `setVertexDistances(double[], boolean)`, or can be computed based on nearest distance calculations to a set of point-based geometric features such as vertices, edges, or faces, using `computeDistances(java.util.List<? extends maspack.geometry.Feature>, boolean)`. The convenience methods `computeFromFeatures(java.util.List<? extends maspack.geometry.Feature>, double, maspack.matrix.RigidTransform3d, int, boolean)` and `computeFromFeaturesOBB(java.util.List<? extends maspack.geometry.Feature>, double, int, boolean)` will both compute distances and also fit the grid to the features. When computed from features, each grid vertex is associated with a nearest feature.

Feature based distance computation assumes that the feature points are represented in local coordinates. For grid vertices close to the mesh, nearby features are examined to determine the distance from the mesh to the vertex. A sweep method is then used to propagate distance values throughout the volume and determine whether vertices are inside or outside. If the features are faces, it is possible to request that the grid be signed. In this case, ray casts are used to determine whether vertices are inside or outside the feature set, with interior and exterior vertices being given negative and positive distance values, respectively. The algorithm is based on C++ code provided by Robert Bridson (UBC) in the `makelevelset3` class of his common code set.

• ### Nested Class Summary

Nested Classes
Modifier and Type Class and Description
`static class ` `DistanceGrid.DistanceMethod`
Describes what method to use when generating distance values from polygonal meshes.
`class ` `DistanceGrid.GridEdge`
`static class ` `DistanceGrid.TetDesc`
`static class ` `DistanceGrid.TetID`
Identifies a sub tet within a hex cell.
• ### Field Summary

Fields
Modifier and Type Field and Description
`static int` `culledQueries`
`static DistanceGrid.DistanceMethod` `DEFAULT_DISTANCE_METHOD`
`static int` `totalQueries`
`boolean` `useNormalsForQuadGrad`
• ### Fields inherited from class maspack.geometry.ScalarGridBase

`OUTSIDE_GRID`
• ### Fields inherited from interface maspack.render.IsRenderable

`TRANSPARENT, TWO_DIMENSIONAL`
• ### Constructor Summary

Constructors
Constructor and Description
`DistanceGrid()`
Default constructor.
`DistanceGrid(DistanceGrid grid)`
Creates a new distance grid that is a copy of an existing grid.
```DistanceGrid(java.util.List<? extends Feature> features, double marginFrac, int maxRes, boolean signed)```
Creates a new distance grid for a specified list of features, axis-aligned and centered on the features, with a uniform cell width along all axes defined so that the resolution along the maximum width axis is `maxRes`.
```DistanceGrid(java.util.List<? extends Feature> features, double marginFrac, Vector3i resolution, boolean signed)```
Creates a new distance grid for a specified list of features, axis-aligned and centered on the features, with a the cell resolution along each axis given by `resolution`.
```DistanceGrid(Vector3d widths, Vector3i resolution, RigidTransform3d TCL)```
Creates a new distance grid with specified widths, resolution, and position and orientation of the center given by `TCL`.
`DistanceGrid(Vector3i resolution)`
Creates a new distance grid, axis-aligned and centered on the origin, with the specified resolution and x, y, z widths set to 1.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`void` `checkGradient()`
`void` `clearFeatures()`
Clears the features, if any, associated with this distance grid.
`void` `computeDifference01(PolygonalMesh mesh)`
`void` `computeDifference10(PolygonalMesh mesh)`
`void` ```computeDistances(java.util.List<? extends Feature> features, boolean signed)```
Computes the distance field for this grid, based on the nearest distances to a supplied set of features.
`void` ```computeDistances(PolygonalMesh mesh, boolean signed)```
`void` ```computeFromFeatures(java.util.List<? extends Feature> features, double marginFrac, RigidTransform3d TCL, int maxRes, boolean signed)```
Fits this grid to a set of features and computes the corresponding distance field.
`void` ```computeFromFeaturesOBB(java.util.List<? extends Feature> features, double marginFrac, int maxRes, boolean signed)```
Fits this grid in an oriented manner to a set of features and computes the corresponding distance field.
`void` ```computeFromMesh(PolygonalMesh mesh, double marginFrac, RigidTransform3d TCL, int maxRes, boolean signed)```
`void` `computeIntersection(PolygonalMesh mesh)`
`void` ```computeQuadCoefs(double[] a, DistanceGrid.TetDesc tdesc)```
`void` ```computeQuadCoefsStub(double[] a, DistanceGrid.TetDesc tdesc)```
`void` `computeUnion(PolygonalMesh mesh)`
`PolygonalMesh` ```createQuadDistanceSurface(double val, int res)```
Creates a triangular mesh approximating the surface on which the quadratically interpolated distance function equals `val`.
`boolean` ```epsilonEquals(DistanceGrid grid, double tol)```
Returns `true` if this grid equals another within a prescribed tolerance.
`boolean` ```findQuadSurfaceIntersection(Point3d pi, Point3d p0, Point3d pa, Vector3d nrm)```
Experimental method.
`boolean` ```findQuadSurfaceTangent(Point3d pt, Point3d p0, Point3d pa, Vector3d nrm)```
Find a point `pt` such that the line segment `pa-pt` is tangent to the quadratic zero distance surface and also lies in the plane defined by point `p0` and normal `nrm`.
`java.util.ArrayList<DistanceGrid.TetDesc>` `findSurfaceEdgeTets(java.util.ArrayList<DistanceGrid.GridEdge> edges)`
`java.util.ArrayList<DistanceGrid.GridEdge>` `findSurfaceIntersectingEdges()`
`void` ```fitToFeatures(java.util.Collection<java.util.List<? extends Feature>> featureSets, double marginFrac, RigidTransform3d TCL, int maxRes)```
Fits the widths and center of this grid to a several sets of features.
`void` ```fitToFeatures(java.util.List<? extends Feature> features, double marginFrac, RigidTransform3d TCL, int maxRes)```
Fits the widths and center of this grid to a set of features.
`void` ```fitToFeaturesOBB(java.util.Collection<java.util.List<? extends Feature>> featureSets, double marginFrac, int maxRes)```
Fits the widths, center and local orientation of this grid to several sets of features.
`void` ```fitToFeaturesOBB(java.util.List<? extends Feature> features, double marginFrac, int maxRes)```
Fits the widths, center and local orientation of this grid to a set of features.
`Feature` `getClosestFeature(int idx)`
Returns the closest Feature to the vertex indexed by `idx`.
`DistanceGrid.DistanceMethod` `getDistanceMethod()`
Returns the method used to compute distance values from polygonal meshes.
`Feature[]` `getFeatures()`
Returns the features, if any, associated with this distance grid Features will be associated with the field if they were used to compute it, via `computeFromFeatures(java.util.List<? extends maspack.geometry.Feature>, double, maspack.matrix.RigidTransform3d, int, boolean)`, `computeFromFeaturesOBB(java.util.List<? extends maspack.geometry.Feature>, double, int, boolean)`, or one of the associated constructors.
`double` `getLocalDistance(Point3d point)`
Calculates the distance at an arbitrary point in local coordinates using multilinear interpolation of the vertex values for the grid cell containing the point.
`double` ```getLocalDistanceAndGradient(Vector3d grad, double x, double y, double z)```
Calculates the distance and gradient at an arbitrary point in local coordinates using multilinear interpolation, as described for `getLocalDistanceAndGradient(Vector3d,Point3d)`.
`double` ```getLocalDistanceAndGradient(Vector3d grad, Point3d point)```
Calculates the distance and gradient at an arbitrary point in local coordinates using multilinear interpolation of the vertex values for the grid cell containing the point.
`double` ```getLocalDistanceAndNormal(Vector3d norm, double x, double y, double z)```
Calculates the distance and normal at an arbitrary point in local coordinates using multilinear interpolation, as described for `getLocalDistanceAndNormal(Vector3d,Point3d)`.
`double` ```getLocalDistanceAndNormal(Vector3d norm, Matrix3d Dnrm, Point3d point)```
Calculates the distance and normal at an arbitrary point in local coordinates using multilinear interpolation, as described for `getLocalDistanceAndNormal(Vector3d,Point3d)`.
`double` ```getLocalDistanceAndNormal(Vector3d norm, Point3d point)```
Calculates the distance and normal at an arbitrary point in local coordinates using multilinear interpolation of the vertex values for the grid cell containing the point.
`Feature` ```getNearestLocalFeature(Point3d nearest, Point3d point)```
Determines nearest feature to an arbitray point in local coordinates.
`Feature` ```getNearestWorldFeature(Point3d nearest, Point3d point)```
Determines nearest feature to an arbitray point in world coordinates.
`java.lang.String` `getQuadCellInfo(Point3d point)`
`double` `getQuadDistance(Point3d point)`
Calculates the distance at an arbitrary point in local coordinates using quadratic interpolation, as described for `getQuadDistanceAndGradient(maspack.matrix.Vector3d, maspack.matrix.Matrix3d, maspack.matrix.Point3d)`.
`double` ```getQuadDistanceAndGradient(Vector3d grad, Matrix3d dgrad, Point3d point)```
Calculates the distance and gradient at an arbitrary point in local coordinates using quadratic interpolation.
`DistanceGrid.TetDesc` `getQuadTet(Point3d point)`
Used for debugging
`Vector3d` ```getRenderVector(int xi, int yj, int zk)```
For grid subclasses wishing to render 3D vector information, this method should be overridden to optionally returns a vector quantity associated with the vertex at indices `xi`, `yj`, and `zk`.
`double` `getRenderVectorScale()`
For grid subclasses wishing to render 3D vector information, this method should be overridden to return a scaling factor to be applied to vectors returned by `InterpolatingGridBase.getRenderVector(int, int, int)` to determine the length of the actual rendered vector.
`double` `getVertexDistance(Vector3i vxyz)`
Queries the distance value at a specified vertex, as specified by x, y, z indices.
`double[]` `getVertexDistances()`
Returns the full array of distances at each vertex.
`double` `getWorldDistance(Point3d point)`
Calculates the distance at an arbitrary point in world coordinates using multilinear interpolation of the vertex values for the grid cell containing the point.
`double` ```getWorldDistanceAndGradient(Vector3d grad, double x, double y, double z)```
Calculates the distance and gradient at an arbitrary point in world coordinates using multilinear interpolation, as described for `getLocalDistanceAndGradient(Vector3d,Point3d)`.
`double` ```getWorldDistanceAndGradient(Vector3d grad, Point3d point)```
Calculates the distance and gradient at an arbitrary point.
`double` ```getWorldDistanceAndNormal(Vector3d norm, double x, double y, double z)```
Calculates the distance and normal at an arbitrary point in world coordinates using multilinear interpolation, as described for `getLocalDistanceAndNormal(Vector3d,Point3d)`.
`double` ```getWorldDistanceAndNormal(Vector3d norm, Point3d point)```
Calculates the distance and normal at an arbitrary point in world coordinates using multilinear interpolation, as described for `getLocalDistanceAndNormal(Vector3d,Point3d)`.
`double` `getWorldQuadDistance(Point3d point)`
Calculates the distance at an arbitrary point in world coordinates using quadratic interpolation, as described for `getQuadDistanceAndGradient(maspack.matrix.Vector3d, maspack.matrix.Matrix3d, maspack.matrix.Point3d)`.
`double` ```getWorldQuadDistanceAndGradient(Vector3d grad, Matrix3d dgrad, Point3d point)```
Calculates the distance and gradient at an arbitrary point in world coordinates using quadratic interpolation, as described for `getLocalDistanceAndGradient(Vector3d,Point3d)`.
`boolean` `isSigned()`
Queries whether or not this grid is signed.
`void` `markOutsideQuadtets(double mindist)`
Marks all tets whose nodes all have distance values `> mindist` as being "outside".
`void` `scaleDistance(double s)`
Scales the distance units of the grid, which entails scaling the widths, distances and coordinate transform information.
`void` `set(DistanceGrid grid)`
Sets this distance grid to be a copy of an existing grid.
`void` `setDistanceMethod(DistanceGrid.DistanceMethod method)`
Sets the method used to compute distance values from polygonal meshes.
`void` ```setDistancesAndFeatures(double[] distances, java.util.List<? extends Feature> features, int[] closestFeatures, boolean signed)```
Explicitly sets the distance field and features for this grid.
`void` `setLocalToWorld(RigidTransform3d TLW)`
Sets a transform that maps from local to world coordinates.
`void` `setResolution(Vector3i resolution)`
Sets the resolution for this grid along the x, y, and z axes.
`void` ```setVertexDistances(double[] distances, boolean signed)```
Explicitly sets the distance field for this grid, by setting the distance values at each vertex.
`void` `smooth()`
Applies a simple Laplacian smoothing operation to the distance grid
`void` ```smooth(double lambda, double mu)```
Taubin Smoothing
`void` ```smooth(double lambda, double mu, int iters)```
Applies Taubin smoothing
`void` `smooth(int n)`
Apply the smoothing operation n times
`void` `zeroVertexDistances()`
Explicitly zeros the distance field for this grid.
• ### Methods inherited from class maspack.geometry.ScalarGridBase

`createDistanceSurface, createDistanceSurface, createDistanceSurface, epsilonEquals, getParameterType, setVertexValue`
• ### Methods inherited from class maspack.geometry.InterpolatingGridBase

`clearColors, createRenderProps, epsilonEquals, getCellVertex, getCellWidths, getCenter, getCenterAndOrientation, getClosestVertex, getDebug, getDefaultVertexColor, getGridToLocalTransformer, getLocalToWorld, getLocalToWorldTransformer, getLocalVertexCoords, getLocalVertexCoords, getOrientation, getRadius, getRenderHints, getRenderProps, getRenderRanges, getResolution, getSelection, getVertexColor, getWidths, getWidths, getWorldCenter, getWorldOrientation, getWorldVertexCoords, getWorldVertexCoords, hasLocalToWorld, isSelectable, isWritable, numSelectionQueriesNeeded, numVertices, parseRenderRanges, prerender, prerender, render, render, scan, set, setCenter, setCenterAndOrientation, setDebug, setDefaultVertexColor, setOrientation, setRenderProps, setRenderRanges, setVertexColor, updateBounds, vertexToXyzIndices, write, xyzIndicesToVertex`
• ### Methods inherited from class java.lang.Object

`equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Field Detail

• #### DEFAULT_DISTANCE_METHOD

`public static DistanceGrid.DistanceMethod DEFAULT_DISTANCE_METHOD`

`public boolean useNormalsForQuadGrad`
• #### totalQueries

`public static int totalQueries`
• #### culledQueries

`public static int culledQueries`
• ### Constructor Detail

• #### DistanceGrid

```public DistanceGrid(java.util.List<? extends Feature> features,
double marginFrac,
int maxRes,
boolean signed)```
Creates a new distance grid for a specified list of features, axis-aligned and centered on the features, with a uniform cell width along all axes defined so that the resolution along the maximum width axis is `maxRes`. The grid is created by calling
```  computeFromFeatures (features, marginFrac, null, maxRes, signed);
```
Parameters:
`features` - features used to compute the distance field
`marginFrac` - specifies the fractional amount that the grid should be grown in each direction to better contain the features
`maxRes` - specfies the resolution along the longest width, with resolutions along other widths set to ensure uniform cell size. Must be `>` 0.
`signed` - if `true`, indicates that the field should be signed. At present, signed fields can only be computed if all features are faces (i.e., `Face`).
• #### DistanceGrid

```public DistanceGrid(java.util.List<? extends Feature> features,
double marginFrac,
Vector3i resolution,
boolean signed)```
Creates a new distance grid for a specified list of features, axis-aligned and centered on the features, with a the cell resolution along each axis given by `resolution`. The grid is created by calling
```  setResolution (resolution);
computeFromFeatures (features, marginFrac, null, 0, signed);
```
Parameters:
`features` - features used to compute the distance field
`marginFrac` - specifies the fractional amount that the grid should be grown in each direction to better contain the features
`resolution` - specfies the resolution along each of the x, y, and z axes.
`signed` - if `true`, indicates that the field should be signed. At present, signed fields can only be computed if all features are faces (i.e., `Face`).
• #### DistanceGrid

```public DistanceGrid(Vector3d widths,
Vector3i resolution,
RigidTransform3d TCL)```
Creates a new distance grid with specified widths, resolution, and position and orientation of the center given by `TCL`. The grid distances are initialized to zero.
Parameters:
`widths` - widths along the x, y, and z axes
`resolution` - cell resolution along the x, y, and z axes
`TCL` - transformation giving the position and orientation of the grid center
• #### DistanceGrid

`public DistanceGrid(Vector3i resolution)`
Creates a new distance grid, axis-aligned and centered on the origin, with the specified resolution and x, y, z widths set to 1. The grid distances are initialized to zero.
Parameters:
`resolution` - cell resolution along the x, y, and z axes
• #### DistanceGrid

`public DistanceGrid(DistanceGrid grid)`
Creates a new distance grid that is a copy of an existing grid.
Parameters:
`grid` - distance grid to copy
• ### Method Detail

• #### setDistanceMethod

`public void setDistanceMethod(DistanceGrid.DistanceMethod method)`
Sets the method used to compute distance values from polygonal meshes. Specifying `null` sets the method to the default value, which is `DistanceGrid.DistanceMethod.BRIDSON`.
Parameters:
`method` - distance method for polygonal meshes
• #### getDistanceMethod

`public DistanceGrid.DistanceMethod getDistanceMethod()`
Returns the method used to compute distance values from polygonal meshes.
Returns:
distance method for polygonal meshes
• #### setLocalToWorld

`public void setLocalToWorld(RigidTransform3d TLW)`
Sets a transform that maps from local to world coordinates. If the specified transform is the identity, then `hasLocalToWorld` will subsequently return `false`.
Overrides:
`setLocalToWorld` in class `InterpolatingGridBase`
Parameters:
`TLW` - transform from local to world coordinates
• #### setResolution

`public void setResolution(Vector3i resolution)`
Sets the resolution for this grid along the x, y, and z axes. Resolutions are rounded up to be an even number, to allow quadratic interpolation (and the `resolution` argument is adjusted accordingly). If features are present for this grid, as described for `getFeatures()`, then these are used to recompute the distances. Otherwise, the distances are set to zero. If a color map is present, it is cleared.
Overrides:
`setResolution` in class `InterpolatingGridBase`
Parameters:
`resolution` - cell resolution along the x, y and z axes. Must be at least 1 along each axis.
• #### set

`public void set(DistanceGrid grid)`
Sets this distance grid to be a copy of an existing grid.
Parameters:
`grid` - distance grid to copy
• #### computeDistances

```public void computeDistances(java.util.List<? extends Feature> features,
boolean signed)```
Computes the distance field for this grid, based on the nearest distances to a supplied set of features. These features are stored internally and can be later retrieved using `getFeatures()`. The grid resolution, widths, center and orientation remain unchanged.
Parameters:
`features` - features used to compute the distance field
`signed` - if `true`, indicates that the field should be signed. At present, signed fields can only be computed if all features are faces (i.e., `Face`).
• #### computeDistances

```public void computeDistances(PolygonalMesh mesh,
boolean signed)```
• #### setVertexDistances

```public void setVertexDistances(double[] distances,
boolean signed)```
Explicitly sets the distance field for this grid, by setting the distance values at each vertex. The internal feature cache and nearest feature setting for each vertex are cleared.

The input array is indexed such that for vertex indices xi, yj, zk, the corresponding index into this array is

``` idx = xi + nx*yj + (nx*ny)*zk
```
where `nx` and `ny` are the number of vertices along x and y axes.
Parameters:
`distances` - distance for each vertex. Must have a length `>=` `InterpolatingGridBase.numVertices()`.
`signed` - if `true`, indicates that the field should be considered signed.
• #### getVertexDistances

`public double[] getVertexDistances()`
Returns the full array of distances at each vertex. See `setVertexDistances(double[], boolean)` for a description of how vertices are indexed with respect to this array.
Returns:
array of distances, or `null` if distances have not yet been set.
• #### getVertexDistance

`public double getVertexDistance(Vector3i vxyz)`
Queries the distance value at a specified vertex, as specified by x, y, z indices.
Parameters:
`vxyz` - x, y, z vertex indices
Returns:
distance value at the vertex
• #### zeroVertexDistances

`public void zeroVertexDistances()`
Explicitly zeros the distance field for this grid. The internal feature cache and nearest feature setting for each vertex are cleared. The signed property is set to `false`.
• #### setDistancesAndFeatures

```public void setDistancesAndFeatures(double[] distances,
java.util.List<? extends Feature> features,
int[] closestFeatures,
boolean signed)```
Explicitly sets the distance field and features for this grid.
Parameters:
`distances` - distance for each vertex. Must have a length `>=` `InterpolatingGridBase.numVertices()`.
`features` - list of features to be associated with this grid.
`closestFeatures` - index (with respect to `features`( of the nearest feature to each vertex. Must have a length `>=` `InterpolatingGridBase.numVertices()`.
`signed` - if `true`, indicates that the field should be considered signed.
• #### computeFromFeatures

```public void computeFromFeatures(java.util.List<? extends Feature> features,
double marginFrac,
RigidTransform3d TCL,
int maxRes,
boolean signed)```
Fits this grid to a set of features and computes the corresponding distance field. These features are stored internally and can be later retrieved using `getFeatures()`. The existing grid resolution is unchanged, unless `maxRes` exceeds 0, in which case the resolution along the longest width is set to `maxRes` and the resolution along all other axes are set so as to ensure a uniform cell size. All resolutions are rounded up to an even number.

The points of the features are assumed to be given in local coordinates. The application has the option of specifying the position and orientation of the grid center using the optional argument `TCL`. If this is non-null, then the widths are set large enough about the specified center to accomodate the features. Otherwise, if `TCL` is null, then the grid is fit in an axis-aligned manner to the local coordinate frame (i.e., `InterpolatingGridBase.getOrientation(maspack.matrix.RotationMatrix3d)` returns the identity), with a center and widths computed to best fit the features.

To ensure that the grid is not degenerate, all widths are adjusted if necessary to ensure that they are at least 0.05 of the maximum width. Widths are then further adjusted by multiplying by

``` (1 + 2*marginFrac)
```
to provide a margin around the features. Finally, if `maxRes > 0`, widths may be grown to ensure uniform cell size.
Parameters:
`features` - features used to compute the distance field
`marginFrac` - specifies the fractional amount that the grid should be grown in each direction to better contain the features
`TCL` - optional - if non-null, specifies the pose of the grid center
`maxRes` - if `> 0`, specifies the resolution along the longest width, with resolutions along other widths set to ensure uniform cell size
`signed` - if `true`, indicates that the field should be signed. At present, signed fields can only be computed if all features are faces (i.e., `Face`).
• #### computeFromMesh

```public void computeFromMesh(PolygonalMesh mesh,
double marginFrac,
RigidTransform3d TCL,
int maxRes,
boolean signed)```
• #### fitToFeatures

```public void fitToFeatures(java.util.List<? extends Feature> features,
double marginFrac,
RigidTransform3d TCL,
int maxRes)```
Fits the widths and center of this grid to a set of features. The way in which this is done is the same as for `computeFromFeatures(java.util.List<? extends maspack.geometry.Feature>, double, maspack.matrix.RigidTransform3d, int, boolean)`; however, no distance field is computed and the features are not stored.
Parameters:
`features` - features used to fit the grid
`marginFrac` - specifies the fractional amount that the grid should be grown in each direction to better contain the features
`TCL` - optional - if non-null, specifies the pose of the grid center
`maxRes` - if `> 0`, specifies the resolution along the longest width, with resolutions along other widths set to ensure uniform cell size
• #### fitToFeatures

```public void fitToFeatures(java.util.Collection<java.util.List<? extends Feature>> featureSets,
double marginFrac,
RigidTransform3d TCL,
int maxRes)```
Fits the widths and center of this grid to a several sets of features. The way in which this is done is the same as for `computeFromFeatures(java.util.List<? extends maspack.geometry.Feature>, double, maspack.matrix.RigidTransform3d, int, boolean)`; however, no distance field is computed and the features are not stored.
Parameters:
`featureSets` - lists of features used to fit the grid
`marginFrac` - specifies the fractional amount that the grid should be grown in each direction to better contain the features
`TCL` - optional - if non-null, specifies the pose of the grid center
`maxRes` - if `> 0`, specifies the resolution along the longest width, with resolutions along other widths set to ensure uniform cell size
• #### computeFromFeaturesOBB

```public void computeFromFeaturesOBB(java.util.List<? extends Feature> features,
double marginFrac,
int maxRes,
boolean signed)```
Fits this grid in an oriented manner to a set of features and computes the corresponding distance field. These features are stored internally and can be later retrieved using `getFeatures()`. The existing grid resolution is unchanged, unless `maxRes` exceeds 0, in which case the resolution along the longest width is set to `maxRes` and the resolution along all other axes are set so as to ensure a uniform cell size. All resolutions are rounded up to an even number.

The points of the features are assumed to be given in local coordinates. The grid is fit to an oriented bounding box (OBB) with respect to this frame; `InterpolatingGridBase.getCenter(maspack.matrix.Vector3d)` and `InterpolatingGridBase.getOrientation(maspack.matrix.RotationMatrix3d)` will return the center and orientation of this box. To ensure that the grid is not degenerate, all widths are adjusted if necessary to ensure that they are at least 0.05 of the maximum width. Widths are then further adjusted by multiplying by

` (1 + 2*marginFrac) `
to provide a margin around the features.
Parameters:
`features` - features used to compute the distance field
`marginFrac` - specifies the fractional amount that the grid should be grown in each direction to better contain the features
`maxRes` - if `>` 0, specfies the resolution along the longest width, with resolutions along other widths set to ensure uniform cell size
`signed` - if `true`, indicates that the field should be signed. At present, signed fields can only be computed if all features are faces (i.e., `Face`).
• #### fitToFeaturesOBB

```public void fitToFeaturesOBB(java.util.List<? extends Feature> features,
double marginFrac,
int maxRes)```
Fits the widths, center and local orientation of this grid to a set of features. The way in which this is done is the same as for `computeFromFeaturesOBB(java.util.List<? extends maspack.geometry.Feature>, double, int, boolean)`; however, no distance field is computed and the features are not stored.
Parameters:
`features` - features used to fit the grid
`marginFrac` - specifies the fractional amount that the grid should be grown in each direction to better contain the features
`maxRes` - if `>` 0, specfies the resolution along the longest width, with resolutions along other widths set to ensure uniform cell size
• #### fitToFeaturesOBB

```public void fitToFeaturesOBB(java.util.Collection<java.util.List<? extends Feature>> featureSets,
double marginFrac,
int maxRes)```
Fits the widths, center and local orientation of this grid to several sets of features. The way in which this is done is the same as for `computeFromFeaturesOBB(java.util.List<? extends maspack.geometry.Feature>, double, int, boolean)`; however, no distance field is computed and the features are not stored.
Parameters:
`featureSets` - lists of features used to fit the grid
`marginFrac` - specifies the fractional amount that the grid should be grown in each direction to better contain the features
`maxRes` - if `>` 0, specfies the resolution along the longest width, with resolutions along other widths set to ensure uniform cell size
• #### computeUnion

`public void computeUnion(PolygonalMesh mesh)`
• #### computeIntersection

`public void computeIntersection(PolygonalMesh mesh)`
• #### computeDifference01

`public void computeDifference01(PolygonalMesh mesh)`
• #### computeDifference10

`public void computeDifference10(PolygonalMesh mesh)`
• #### getLocalDistance

`public double getLocalDistance(Point3d point)`
Calculates the distance at an arbitrary point in local coordinates using multilinear interpolation of the vertex values for the grid cell containing the point. If the point lies outside the grid volume, `ScalarGridBase.OUTSIDE_GRID` is returned.
Parameters:
`point` - point at which to calculate the normal and distance (local coordinates).
Returns:
interpolated distance, or `OUTSIDE_GRID`.
• #### getWorldDistance

`public double getWorldDistance(Point3d point)`
Calculates the distance at an arbitrary point in world coordinates using multilinear interpolation of the vertex values for the grid cell containing the point. If the point lies outside the grid volume, `ScalarGridBase.OUTSIDE_GRID` is returned.
Parameters:
`point` - point at which to calculate the normal and distance (world coordinates).
Returns:
interpolated distance, or `OUTSIDE_GRID`.
• #### getLocalDistanceAndNormal

```public double getLocalDistanceAndNormal(Vector3d norm,
double x,
double y,
double z)```
Calculates the distance and normal at an arbitrary point in local coordinates using multilinear interpolation, as described for `getLocalDistanceAndNormal(Vector3d,Point3d)`. If the point lies outside the grid volume, `ScalarGridBase.OUTSIDE_GRID` is returned.
Parameters:
`norm` - returns the normal (local coordinates)
`x` - x coordinate of point (local coordinates).
`y` - y coordinate of point (local coordinates).
`z` - z coordinate of point (local coordinates).
Returns:
interpolated distance, or `OUTSIDE_GRID`.
• #### getWorldDistanceAndNormal

```public double getWorldDistanceAndNormal(Vector3d norm,
double x,
double y,
double z)```
Calculates the distance and normal at an arbitrary point in world coordinates using multilinear interpolation, as described for `getLocalDistanceAndNormal(Vector3d,Point3d)`. If the point lies outside the grid volume, `ScalarGridBase.OUTSIDE_GRID` is returned.
Parameters:
`norm` - returns the normal (world coordinates)
`x` - x coordinate of point (world coordinates).
`y` - y coordinate of point (world coordinates).
`z` - z coordinate of point (world coordinates).
Returns:
interpolated distance, or `OUTSIDE_GRID`.

```public double getLocalDistanceAndGradient(Vector3d grad,
double x,
double y,
double z)```
Calculates the distance and gradient at an arbitrary point in local coordinates using multilinear interpolation, as described for `getLocalDistanceAndGradient(Vector3d,Point3d)`. If the point lies outside the grid volume, `ScalarGridBase.OUTSIDE_GRID` is returned.
Parameters:
`grad` - returns the gradient (local coordinates)
`x` - x coordinate of point (local coordinates).
`y` - y coordinate of point (local coordinates).
`z` - z coordinate of point (local coordinates).
Returns:
interpolated distance, or `OUTSIDE_GRID`.

```public double getWorldDistanceAndGradient(Vector3d grad,
double x,
double y,
double z)```
Calculates the distance and gradient at an arbitrary point in world coordinates using multilinear interpolation, as described for `getLocalDistanceAndGradient(Vector3d,Point3d)`. If the point lies outside the grid volume, `ScalarGridBase.OUTSIDE_GRID` is returned.
Parameters:
`grad` - returns the gradient (world coordinates)
`x` - x coordinate of point (world coordinates).
`y` - y coordinate of point (world coordinates).
`z` - z coordinate of point (world coordinates).
Returns:
interpolated distance, or `OUTSIDE_GRID`.
• #### getLocalDistanceAndNormal

```public double getLocalDistanceAndNormal(Vector3d norm,
Point3d point)```
Calculates the distance and normal at an arbitrary point in local coordinates using multilinear interpolation of the vertex values for the grid cell containing the point. Both the distance and normal values are determined this way, with normal values at the vertices being computed on demand by mid-point differencing of distances at adjacent vertices. The returned normal values do not therefore correspond to the gradient of the distance field, but instead vary more smoothly across the grid. If the point lies outside the grid volume, `ScalarGridBase.OUTSIDE_GRID` is returned.
Parameters:
`norm` - returns the normal (local coordinates)
`point` - point at which to calculate the normal and distance (local coordinates).
Returns:
interpolated distance, or `OUTSIDE_GRID`.
• #### getWorldDistanceAndNormal

```public double getWorldDistanceAndNormal(Vector3d norm,
Point3d point)```
Calculates the distance and normal at an arbitrary point in world coordinates using multilinear interpolation, as described for `getLocalDistanceAndNormal(Vector3d,Point3d)`. If the point lies outside the grid volume, `ScalarGridBase.OUTSIDE_GRID` is returned.
Parameters:
`norm` - returns the normal (world coordinates)
`point` - point at which to calculate the normal and distance (world coordinates).
Returns:
interpolated distance, or `OUTSIDE_GRID`.
• #### getLocalDistanceAndNormal

```public double getLocalDistanceAndNormal(Vector3d norm,
Matrix3d Dnrm,
Point3d point)```
Calculates the distance and normal at an arbitrary point in local coordinates using multilinear interpolation, as described for `getLocalDistanceAndNormal(Vector3d,Point3d)`. If `Dnrm` is non-`null`, the method also calculated the normal derivative. If the point lies outside the grid volume, `ScalarGridBase.OUTSIDE_GRID` is returned.
Parameters:
`norm` - returns the normal (local coordinates)
`Dnrm` - if non-null, returns the normal derivative (local coordinates)
`point` - point at which to calculate the normal and distance (local coordinates).
Returns:
interpolated distance, or `OUTSIDE_GRID`.

```public double getLocalDistanceAndGradient(Vector3d grad,
Point3d point)```
Calculates the distance and gradient at an arbitrary point in local coordinates using multilinear interpolation of the vertex values for the grid cell containing the point. The gradient is the true derivative of the interpolated distance function within the cell, and is in fact linear within the cell. If the point lies outside the grid volume, `ScalarGridBase.OUTSIDE_GRID` is returned.
Parameters:
`grad` - returns the gradient direction (local coordinates)
`point` - point at which to calculate the gradient and distance (local coordinates).
Returns:
interpolated distance, or `OUTSIDE_GRID`.

```public double getWorldDistanceAndGradient(Vector3d grad,
Point3d point)```
Calculates the distance and gradient at an arbitrary point. These values are determined by multilinear interpolation of the vertex values for the grid cell containing the point. If the point lies outside the grid volume, `ScalarGridBase.OUTSIDE_GRID` is returned.
Parameters:
`grad` - returns the gradient (world coordinates)
`point` - point at which to calculate the gradient and distance (world coordinates).
Returns:
distance to the nearest feature
• #### getNearestLocalFeature

```public Feature getNearestLocalFeature(Point3d nearest,
Point3d point)```
Determines nearest feature to an arbitray point in local coordinates. If the grid is not associated with features (i.e., `getFeatures()` returns `null`), or if the point lies outside the grid, `null` is returned.
Parameters:
`nearest` - returns the nearest point on the feature (local coordinates)
`point` - point for which to find nearest feature (local coordinates)
Returns:
nearest feature, or null if outside of domain or if no features are set.
• #### getNearestWorldFeature

```public Feature getNearestWorldFeature(Point3d nearest,
Point3d point)```
Determines nearest feature to an arbitray point in world coordinates. If the grid is not associated with features (i.e., `getFeatures()` returns `null`), or if the point lies outside the grid, `null` is returned.
Parameters:
`nearest` - returns the nearest point on the feature (world coordinates)
`point` - point for which to find nearest feature (world coordinates)
Returns:
nearest feature, or null if outside of domain or if no features are set.
• #### isSigned

`public boolean isSigned()`
Queries whether or not this grid is signed.
Returns:
`true` if this grid is signed.
• #### clearFeatures

`public void clearFeatures()`
Clears the features, if any, associated with this distance grid.
• #### getClosestFeature

`public Feature getClosestFeature(int idx)`
Returns the closest Feature to the vertex indexed by `idx`. This assumes that the distance field is associated with features, as described for `getFeatures()`. If this is not the case, `null` is returned.
Parameters:
`idx` - vertex index
Returns:
nearest Feature to the vertex, or `null` if there are no features
• #### smooth

`public void smooth(int n)`
Apply the smoothing operation n times
Parameters:
`n` - number of times to apply the smoothing operation
• #### smooth

```public void smooth(double lambda,
double mu)```
Taubin Smoothing
Parameters:
`lambda` - `>` 0, fraction of gradient to shrink
`mu` - `<` 0, fraction of gradient to expand
• #### smooth

```public void smooth(double lambda,
double mu,
int iters)```
Applies Taubin smoothing
Parameters:
`lambda` - `>` 0, fraction of gradient to shrink
`mu` - `<` 0, fraction of gradient to expand
`iters` - number of applications
• #### smooth

`public void smooth()`
Applies a simple Laplacian smoothing operation to the distance grid

```public PolygonalMesh createQuadDistanceSurface(double val,
int res)```
Creates a triangular mesh approximating the surface on which the quadratically interpolated distance function equals `val`.
Parameters:
`val` - iso surface value
`res` - multiplies the resolution of this grid to obtain the resolution of the grid used to create the mesh.
Returns:
• #### getRenderVector

```public Vector3d getRenderVector(int xi,
int yj,
int zk)```
Description copied from class: `InterpolatingGridBase`
For grid subclasses wishing to render 3D vector information, this method should be overridden to optionally returns a vector quantity associated with the vertex at indices `xi`, `yj`, and `zk`. Should returns `null` if no vector information should be rendered at that vertex.
Overrides:
`getRenderVector` in class `InterpolatingGridBase`
Parameters:
`xi` - x vertex index
`yj` - y vertex index
`zk` - z vertex index
• #### getRenderVectorScale

`public double getRenderVectorScale()`
Description copied from class: `InterpolatingGridBase`
For grid subclasses wishing to render 3D vector information, this method should be overridden to return a scaling factor to be applied to vectors returned by `InterpolatingGridBase.getRenderVector(int, int, int)` to determine the length of the actual rendered vector. Returning 0 disables vector rendering.
Overrides:
`getRenderVectorScale` in class `InterpolatingGridBase`
Returns:
scaling factor for rendered vectors

`public java.lang.String getQuadCellInfo(Point3d point)`

`public DistanceGrid.TetDesc getQuadTet(Point3d point)`
Used for debugging

```public double getQuadDistanceAndGradient(Vector3d grad,
Point3d point)```
Calculates the distance and gradient at an arbitrary point in local coordinates using quadratic interpolation. This interpolation is done within the composite quadratic cell (composed of 2 x 2 x 2 regular cells) containing the point. This cell is in turn decomposed into 6 tetrahedra, each with ten vertices, and the interpolation is done within the tet containing the point. Performing the interpolation on a tet ensures that the interpolation function is purely quadratic, and that its gradient is purely linear. The returned gradient is the exact gradient of the interpolation function within the tet. If the point lies outside the grid volume, `ScalarGridBase.OUTSIDE_GRID` is returned.
Parameters:
`grad` - returns the gradient direction (local coordinates)
`point` - point at which to calculate the gradient and distance (local coordinates).
`dgrad` - if non-null, returns the derivative of the gradient (local coordinates)
Returns:
interpolated distance, or `OUTSIDE_GRID`.

```public double getWorldQuadDistanceAndGradient(Vector3d grad,
Point3d point)```
Calculates the distance and gradient at an arbitrary point in world coordinates using quadratic interpolation, as described for `getLocalDistanceAndGradient(Vector3d,Point3d)`. If the point lies outside the grid volume, `ScalarGridBase.OUTSIDE_GRID` is returned.
Parameters:
`grad` - returns the gradient (world coordinates)
`dgrad` - if non-null, returns the derivative of the gradient (world coordinates)
`point` - point at which to calculate the gradient and distance (world coordinates).
Returns:
interpolated distance, or `OUTSIDE_GRID`.

```public void computeQuadCoefsStub(double[] a,
DistanceGrid.TetDesc tdesc)```

```public void computeQuadCoefs(double[] a,
DistanceGrid.TetDesc tdesc)```

```public boolean findQuadSurfaceTangent(Point3d pt,
Point3d p0,
Point3d pa,
Vector3d nrm)```
Find a point `pt` such that the line segment `pa-pt` is tangent to the quadratic zero distance surface and also lies in the plane defined by point `p0` and normal `nrm`. The search starts by finding a point on the surface that is close to `p0` and proceeds from there.
Parameters:
`pt` - returns the tangent point
`p0` - point on the plane
`pa` - origin for the tangent segment
`nrm` - normal defining the plane
Returns:
false if the intersection could not be found

```public boolean findQuadSurfaceIntersection(Point3d pi,
Point3d p0,
Point3d pa,
Vector3d nrm)```
Experimental method. Find the intersection point `pi` between the quadratic zero surface and a ray `(p0, pa)` lying in the plane defined by point `p0` and normal `nrm`. `pa` is projected onto the plane internally so the caller does not need to ensure this.
Parameters:
`pi` - returns the intersection point
`p0` - point on the plane and ray origin
`pa` - projected onto the plane to form the outer point defining the ray
`nrm` - normal defining the plane
Returns:
false if the intersection could not be found
• #### epsilonEquals

```public boolean epsilonEquals(DistanceGrid grid,
double tol)```
Returns `true` if this grid equals another within a prescribed tolerance. The grids are equal if the resolution, widths, center, orientation, distances and signed property are equal. Specifying `tol = 0` requires exact equality.
Parameters:
`grid` - grid to compare against
`tol` - floating point tolerance (absolute)
• #### scaleDistance

`public void scaleDistance(double s)`
Scales the distance units of the grid, which entails scaling the widths, distances and coordinate transform information.
Overrides:
`scaleDistance` in class `InterpolatingGridBase`
Parameters:
`s` - scaling factor
`public void markOutsideQuadtets(double mindist)`
Marks all tets whose nodes all have distance values `> mindist` as being "outside".
`public void checkGradient()`
`public java.util.ArrayList<DistanceGrid.GridEdge> findSurfaceIntersectingEdges()`
`public java.util.ArrayList<DistanceGrid.TetDesc> findSurfaceEdgeTets(java.util.ArrayList<DistanceGrid.GridEdge> edges)`