We use a bounding box of
to eliminate easily
resolvable cases, with some level of subdivision to reduce box
size. For a rational polynomial curve with
control points
, the bounding box is given by
(5.20)
(5.21)
(5.22)
as shown in Fig. 5.8 for a planar curve case. A
tighter bounding box can be obtained by axis reorientation
[208]. To eliminate numerical error in the subdivision
process (which can lead to erroneous decisions), rational arithmetic
may be employed (if the input coefficients of
are
rational or floating point numbers). This can be easily done in
object-oriented languages such as C++ using operator overloading. We
continue subdivision until the bounding box is small. Then, we could
use a numerical technique
[69], for example:
(5.23)
and use some values of
from the interval
as the initial approximation. Use of the
square of the distance function is necessary to avoid possible
divergence of the derivative of the distance function, if it
approaches zero.
If the minimization process converges to
and
, then
is the desired solution.
Figure 5.8:
Bounding box of a rational polynomial curve
Next: 5.4.2.3 Distance function method
Up: 5.4.2 Point/rational polynomial parametric
Previous: 5.4.2.1 Elementary method
Contents Index
December 2009