|
Purpose:
|
Contains arrays to be interpolated and the information necessary for the interpolation.
|
|
|
Derivation:
|
curve_interp : ACIS_OBJECT : -
|
|
|
Filename:
|
kern/kernel/spline/bs3_crv/fit.hxx
|
|
|
Description:
|
The main way of constructing a new
intcurve (as opposed to a copy of an existing one), and the only way to make one with an
int_cur of a derived type, is using an object of the
curve_interp class, or a class derived from it. This class contains arrays of points to be interpolated, and the information necessary for the interpolation. Each derived class must supply two virtual functions,
true_point specifies how the interpolation information is used, and
make_int_cur constructs an
int_cur of the appropriate derived class, which is usually defined at the same time as the derived
curve_interp class. This class can also take parameter values at the points that are interpolated. These values can be given as an array of doubles in the data member
param.
|
|
|
The first task in constructing an
intcurve is to generate a sequence of points along the true curve in some context-dependent way, subject to certain conditions discussed later. For each point there must be a position in object space, a curve direction, and possibly one or more positions in the parameter space of any surfaces involved. All of this information goes into the base class-any further information needed by the virtual functions supplied by the application can be added to the derived class. The (derived)
curve_interp object is then passed to the
intcurve constructor, together with an optional region of interest, resulting in the interpolating curve of the correct type.
|
|
|
RestrictionsonInputPointLists
|
|
|
The current curve fitting algorithm takes points pair wise from the input point lists, constructs a Hermite interpolant, cubic in object space, and quadratic in parameter space, and tests its mid-point for a valid fit. On failure, it subdivides the interpolant into two at the true mid point and tries again for each half. At each stage it tests the box containing the span end points and the points of nearest approach of its two end tangents against a supplied region of interest. If there is no overlap, it assumes that the true curve between those end points lies entirely outside the region of interest, and does not attempt to fit the spline any further. The application must ensure that the initial points supplied in the
curve_interp object are near enough so that all these operations and assumptions are valid. Although there are efficiency/reliability trade-offs to be considered, it is unlikely that a precise analysis of boxing would be justified.
|
|
|
Hermite interpolation
|
|
|
This involves determining the points of nearest approach of the end tangents in object space, and determining the distance (measured algebraically along the tangent direction) from the start point to point of nearest approach on the start tangent, and from the point of nearest approach on the end tangent to the end point. For the interpolation to be successful, both distances must be positive, and their ratio should not be too large or small--for example, a factor of 10. Similarly, in each parameter space, the intersection point of the end tangents should lie on the correct side of the end points to ensure that the Bezier quadratic defined by these three control points has the correct initial and final tangent directions.
|
|
|
True point finding
|
|
|
It is essential that the mid-point of the initial Hermite fit is close enough to the true curve for the application-supplied
true_point function to find a valid point. It will normally need to be closer to the required curve than to any other curve satisfying the interpolation conditions, and there should not be any high-frequency undulations in the surfaces between the initial approximation and the true curve. This condition is impossible to specify or test precisely, and so is subject to a series of heuristics. The main one currently used is to reduce the allowable angle between the end tangent directions of a span to roughly 30 degrees. This, together with the hard point order requirements for the initial Hermite interpolation, has proved effective for surface-surface intersections and silhouette lines in
ACIS so far.
|
|
|
Boxing
|
|
|
This requires that the whole of the span of the true curve between the given end points lies within the box containing those two end points and the points of nearest approach between the end tangents. As a special case, it is permissible for the end points of a nonperiodic curve to have zero-length direction vectors. This is for the case that the curve direction is ill-defined by the normal procedure, and it is inconvenient to go to higher order. With an intersection curve, for example, the surfaces may be tangent, so that the curve direction can only be determined by a second-order method. In this case, the interpolation process continually adjusts the end direction of the curve to give zero curvature there, then calling
true_point with that direction to adjust the direction to be valid if it only has one degree of freedom. This appears to be effective and cheap.
|
|
|
References:
|
by KERN
|
point_data, point_obj_data, point_surf_data
|
|
BASE
|
SPAinterval
|
|
|
Data:
|
public double const *param;
|
|
The parameter values at the given points. This value is
NULL if the fitting process chooses its own parameter values.
|
|
|
public double fitol;
|
|
The tolerance allowed on fitted splines.
|
|
|
public int nobj;
|
|
The number of object-space curves being interpolated.
|
|
|
public int npts;
|
|
The number of points to be interpolated. If the curve is periodic, this number is negative; i.e., the last point and the direction are the same as the first point and direction. All arrays, both object-space and parameter-space, are of this length.
|
|
|
public int nsurf;
|
|
The number of surface-related records.
|
|
|
public int nvalid;
|
|
The number of intervals in
valid.
|
|
|
public interp_obj_data *objdata;
|
|
The pointer to an array of object-space curve data records.
|
|
|
public interp_surf_data *sfdata;
|
|
The pointer to an array of objects describing surface-related information.
|
|
|
public SPAinterval *valid;
|
|
The array of parameter intervals within which the fit is in tolerance. Portions outside these intervals are entirely outside the region of interest, and so they may be well outside the tolerance. This is always kept in numerical order and disjoint.
|
|
|
Constructor:
|
public: curve_interp::curve_interp
(
|
|
|
int,
|
// # array entries
|
|
|
double,
|
// fit tolerance
|
|
|
int
|
|
// # obj.-sp. curves
|
|
|
|
= 0,
|
|
|
int
|
|
// number of surfaces
|
|
|
|
= 0
|
|
|
);
|
|
|
C++ initialize constructor requests memory for this object and populates it with the data supplied as arguments.
|
|
|
|
|
|
|
public: curve_interp::curve_interp
(
|
|
|
int,
|
// # array entries
|
|
|
SPAposition const*,
|
// array of points
|
|
|
SPAvector const*,
|
// array of tangents
|
|
|
double,
|
// fit tolerance
|
|
|
int
|
|
// # sur.-rel. objs
|
|
|
|
= 0
|
|
|
);
|
|
|
C++ initialize constructor requests memory for this object and populates it with the data supplied as arguments.
|
|
|
Creates a curve interpolation by accepting a list of positions and tangent directions for the curve that is to be interpolated or fit, depending upon whether the tolerance is 0.
|
|
|
|
|
|
Destructor:
|
public: virtual curve_interp::~curve_interp
();
|
|
|
C++ destructor, deleting a
curve_interp.
|
|
|
|
|
Methods:
|
public: void curve_interp::fit
(
|
|
|
SPAbox const&
|
// given precision region
|
|
|
);
|
|
|
Fits the object-space splines and possible parameter-space splines to the specified initial lists of points.
|
|
|
|
|
|
|
public: virtual int_cur*
|
|
|
curve_interp::make_int_cur () = 0;
|
|
|
Constructs an
int_cur to represent the fitted curve. This is used by the
intcurve constructor for fitting curves to the point lists. This method must be provided for every class derived from this one, and it constructs the appropriate object to represent that type of curve, normally derived from the base class,
int_cur.
|
|
|
|
|
|
|
public: bs3_curve curve_interp::obj_bs
(
|
|
|
int
|
|
// object-space curve
|
|
|
|
= 0
|
|
|
);
|
|
|
Extracts the
nth object-space curve after fitting. The result becomes the property of the caller, and subsequent calls return
NULL.
|
|
|
|
|
|
|
public: double curve_interp::obj_fitol
(
|
|
|
int
|
|
// tolerance
|
|
|
|
= 0
|
|
|
);
|
|
|
Extract the actual fit tolerance achieved for the given object-space curve.
|
|
|
|
|
|
|
public: bs2_curve curve_interp::par_bs
(
|
|
|
int
|
|
// parameter-space curve
|
|
|
);
|
|
|
Extracts the
nth parameter-space curve after fitting. The result becomes the property of the caller, and subsequent calls return
NULL.
|
|
|
|
|
|
|
public: virtual void curve_interp::true_point
(
|
|
|
double,
|
// tolerance
|
|
|
point_data&
|
// point data
|
|
|
) const = 0;
|
|
|
Finds the true-point in 3D for a given parameter value. The input position, direction, and parameter values are approximate; the exact values are provided as output.
|
|
|
|
|
|
|
public: SPAinterval const* curve_interp::valid_range
(
|
|
|
int
|
|
// valid interval
|
|
|
);
|
|
|
Extracts the
nth valid interval from the object, where
n ranges from 0 to
nvalid - 1. This method returns
NULL if
n is outside the range.
|