Graphics Reference
In-Depth Information
An arc length,
s
, can be linearly interpolated from the approximated arc lengths,
G
, in the table by using
the differences between the given parametric value and the parametric values on either side of it in the
table, as in
Equation 3.10
.
v V½i
V½i þ
s ¼ G½iþ
V½i
ðG½i þ
1
G½iÞ
1
0
:
73
0
:
70
(3.10)
¼
0
:
944
þ
70
ð
0
:
959
0
:
944
Þ
0
:
75
0
:
¼
0
:
953
The solution to the first problem cited above (given two parameters
u
a
and
u
b
, find the distance
between the corresponding points) can be found by applying this calculation twice and subtracting
the respective distances.
The converse situation, that of finding the value of
u
given the arc length, is dealt with in a similar
manner. The table is searched for the closest arc length entry to the given arc length value, and the
corresponding parametric entry is used to estimate the parametric value. This situation is a bit more
complicated because the arc length entries are not evenly spaced; the table must actually be searched
for the closest entry. Because the arc length entries are monotonically increasing, a binary search is an
effective method of locating the closest entry. As before, once the closest arc length entry is found the
corresponding parametric entry can be used as the approximate parametric value, or the parametric
entries corresponding to arc length entries on either side of the given arc length value can be used
to linearly interpolate an estimated parametric value.
For example, if the task is to estimate the location of the point on the curve that is 0.75 unit of arc length
from the beginning of the curve, the table is searched for the entrywhose arc length is closest to that value.
In this case, the closest arc length is 0.72 and the corresponding parametric value is 0.40. For a better
estimate, the values in the table that are on either side of the given distance are used to linearly interpolate
a parametric value. In this case, the value of 0.75 is three-eighths of the way between the table values
0.72 and 0.80. Therefore, an estimate of the parametric value would be calculated as in
Equation 3.11
.
3
8
ð
u ¼
0
:
40
þ
0
:
45
0
:
40
Þ¼
0
:
41875
(3.11)
The solution to the second problem (given an arc length
s
and a parameter value
u
a
, find
u
b
such that
LENGTH
(
u
a
,
u
b
)
¼s
) can be found by using the table to estimate the arc length associatedwith
u
a
, adding
that to the givenvalue of
s
, and thenusing the table to estimate the parametric value of the resulting length.
The advantages of this approach are that it is easy to implement, intuitive, and fast to compute.
The downside is that both the estimate of the arc length and the interpolation of the parametric value
introduce errors into the calculation. These errors can be reduced in a couple of ways.
The curve can be supersampled to help reduce errors in forming the table. For example, ten
thousand equally spaced values of the parameter could be used to construct a table consisting of
a thousand entries by breaking down each interval into ten subintervals. This is useful if the curve
is given beforehand and the table construction can be performed as a preprocessing step.
Better methods of interpolation can be used to reduce errors in estimating the parametric value.
Instead of linear interpolation, higher-degree interpolation procedures can be used in computing the
parametric value. Of course, higher-degree interpolation slows down the computation somewhat, so
a decision about the speed/accuracy trade-off has to be made.
Search WWH ::
Custom Search