Graphics Reference
In-Depth Information
The correspondence problem:
One has to determine a correspondence between closed
curves of adjacent contours. This defines some crude topological properties of an object.
For example, if two closed curves of one contour correspond to one closed curve on the
next, this would indicate a saddle structure for the object. Clearly, the only hope for coming
up with a reasonable answer to the correspondence problem is to assume that the contours
of the skinning surface have been spaced close enough together so that simple heuristics
will work.
The tiling problem:
One has to determine a triangulation for the surface that is to span
two adjacent contours. There is no unique triangulation, and so solutions to this problem
try to optimize some function that measure the appropriateness of spanning surfaces. Many
such “metrics” have been proposed. Each one has its problems.
The branching problem:
If there is more than one closed curve on adjacent contours,
then one may need to determine how two or more closed curves in one contour get merged
into one closed curve in the next contour. This would typically also entail determining how
parts on the closed curves of the first contour are related. The tiling problem is more com-
plicated when there are branches. Early work on tiling tended to assume that there were
no branches or expected a user to help out interactively.
The surface-fitting problem:
After one has a tiling, one may want to fit a smooth surface
to that tiling.
Let us look at a simple aspect of the tiling problem. Assume that two adjacent
contours are defined by two closed polygonal curves with distinct vertices
p
0
,
p
1
,...,
p
m
and
q
0
,
q
1
,...,
q
n
, respectively. One would like a triangulation of the skinning
surface
S
to look something like the surface shown in Figure 14.33, where m = n = 4.
Now, in general, m and n are not equal, but the real problem is that one is not given
any information about which point
q
j
should connect to which point
p
i
. For example,
in Figure 14.33, how do we determine that
q
2
is the point that should be connected
to
p
0
and
p
1
? We certainly do not want to connect
p
0
and
q
0
. It is not the case that
there is no algorithm for finding the triangulated surface as shown in Figure 14.33.
One could do an exhaustive search, but this would be prohibitively slow to carry
out. The issue is finding an efficient algorithm. Fuchs et al. ([FuKU77]) reduced the
problem to one of searching a toroidal graph. (A
toroidal graph
is a graph that can be
embedded in a torus.) They used a “divide-and-conquer” technique along with an area-
minimizing heuristic. A number of other approaches have been proposed using dif-
ferent heuristics. For such heuristics to work reasonably well, a common assumption
Figure 14.33.
Skinning polygonal curves.
