On-Line Geometric Modeling Notes
Given an initial control polygon we can define a refinement process that generates a sequence of control polygons from the original. In the limit, this sequence converges to the uniform B-spline curve specified by the original control polygon. By examining this refinement process from a different angle, we can specify a procedure that allows us to directly calculate points on the curve.
For a postscript version of these notes look here.
Direct Calculation of Points on the Curve
In the cubic case, we define the general refinement procedure by
classifying the points of a refinement as either
``vertex'' or ``edge'' points. Using this classification
we can cleverly write this
refinement process in a matrix form.
This form takes a control point and its two adjacent control points of
a refinement and applies a refinement matrix as follows
where A is called the refinement matrix and is given by
Here we have denoted the control points as vertex and edge points.
This procedure
creates two new edge points and a vertex point which are part
of a new control polygon that represents the curve.
We can apply A again and obtain
where 
. In general, we can generate points on the kth
refinement by applying A k-times. In the limit, as k
approaches infinity, we obtain a point on the curve.
We call call this point 
and note that it is equal to
.
Calculating the Limit Point
The suprising thing is that we can actually calculate this limit.
We utilize the fact that the refinement matrix can be
diagonalized,
which defines the matrix A by
where
is the matrix whose columns are the right eigenvectors of A,
is the matrix whose rows are the left eigenvectors of A,
and 
is the matrix of eigenvalues
Since 
,
this allows us to write
(Noting that 
)
or, in general
To calculate the limit,
first consider applying A k-times
Now as 
, this approaches
and by substituting for R and L, this becomes
That is, the vertex and edge points all converge to the same value,
which is just the dot product of the left
eigenvector of A that corresponds to the eigenvalue one,
and the original vertex-edge vector of the refinement - obtaining the point
.
In short, given any vertex 
with corresponding edge points
and 
, we can directly calculate points on the
curve by dotting the left eigenvector that corresponds to the
eigenvalue 1 by the vertex-edge vector
This says that any vertex point on any refinement directly corresponds
to a point on the curve.
Examples
Consider a cubic uniform B-spline curve
with control polygon 
. This
curve can be written as
Consider the
first step of the refinement using 
as the vertex with 
and 
as the two respective edge points. The corresponding
point on the curve can be calculated directly as
which is exactly the point 
on the curve.
Similarly we can calculate a point on the curve using the vertex
with 
and 
as the two respective edge points.
In this case, we find that this is exactly the point 
on
the curve.
Carrying this one step further, suppose we generate one full refinement of the curve, generating new edge and vertex points.
These new points become the input to the
refinement process, and if we consider 
as the vertex point,
with 
and 
as the respective edge points, we obtain the
point on the curve
which is exactly 
.
Summary
It is possible, using eigenanalysis, to formulate simple procedures that calculate directly a point on the limit curve. This, in many cases, can be used to replace the overall refinement process.
The tangent vector on the curve at this limit point can also be directly calculated, by much the same procedure.
|
This document maintained by
Ken Joy
All contents copyright (c) 1996, 1997 |
|
