Agoston M.K. Computer Graphics and Geometric Modelling: Implementation and Algorithms

Подождите немного. Документ загружается.

14.11 EXERCISES

Section 14.2

14.2.1. Carefully describe an algorithm that ﬁnds the distance between a point and a polygo-

nal curve.

14.2.2. Find the the point q on the curve p(u) = (u,u

) that is closest to p = (-3,1).

14.2.3. Find the two nearest points on the curves p: [-•,3] Æ R

, p(u) = (2u,u

), and q: R Æ

R, q(u) = (-u + 1,u + 5).

14.2.4. Consider the surface p: D Æ R

, p(u,v) = (u,v,u

+ v

(a) Find the the point q on the surface that is closest to p = (0,3,0) if D = R

(b) Find the the point q on the surface that is closest to p = (0,3,0) if D = R¥(-•,-1].

14.2.5. Find the two nearest points on the surfaces p(u,v) = (u,v,u

) and q(u,v) = (u,v,2u-

6).

Section 14.5.1

14.5.1.1 Consider the curve deﬁned implicitly by the equation y

- x

= 0. Resolve the singu-

larity of this curve at (0,0) using the method described in Section 14.5. Work through

and explain the details just like we did in Example 14.5.1.2.

Section 14.9.1

14.9.1.1 Consider the planar curve p(u) = (u,u

). Analyze the offset curve p

(u) deﬁned by equa-

tion (14.28) with respect to cusps, turning points, inﬂection points, vertices, and self-

intersections for the following values of d:

(a) 0 < d < 0.5

(b) 0.5 < d

14.12 PROGRAMMING PROJECTS

Section 14.2

14.2.1. Implement a point-curve distance algorithm for planar

(a) polygonal curves, and

(b) B-spline curves.

Let the user deﬁne a curve interactively with a mouse or specify a previously created

one. Then let him/her pick a point with the mouse and display both the distance and

the point on the curve that is closest to the picked point.

14.12 Programming Projects 647

Section 14.4

14.4.1. Implement a trimmed surface algorithm for smooth surfaces with rectangular

domains, such as surfaces of rotation, Bézier surfaces, or B-spline surfaces. After a

user has selected one, show him/her the domain and let him/her deﬁne polygonal

curves in that domain. The curves are of two types: those that that deﬁne the outer

boundary of the ﬁnal trimmed region and those that specify a hole. After the user has

speciﬁed the region that is to be trimmed away display the trimmed surface. Develop

this program for

(a) polygonal trimming curves, and

(b) B-spline trimming curves with the picked points becoming their control points

Section 14.5.1

14.5.1.1. Implement a marching algorithm for an implicit planar curve that is deﬁned by some

predeﬁned polynomial equation.

Section 14.6

14.6.1. Implement a contour program for graphs of functions f: R

Æ R. After the user deﬁnes

a polynomial function, display the surface, prompt the user for a value h, and then

highlight the contour f

-1

(h) on the surface.

Section 14.9.1

14.9.1.1. Display offset curves for planar B-spline curves. Allow the user to specify the curve

and the d parameter. Check for singularities in the offset curve and mark them for

the user to see.

648 14 Global Geometric Modeling Topics

To begin with, there is the notion of curvature itself. In the case of curves, there

is really only one concept of curvature and computing it involves the second deriva-

tive of the curve. In the case of surfaces, the situation is not as simple because there

are a number of different curvature related concepts. The most important is Gauss

curvature, but principal and mean curvatures are also useful. To compute these one

needs second order partial derivatives. Formulas for computing the various curva-

tures can be found in Chapter 9 in [AgoM05].

We consider curves ﬁrst. The fairness of a curve is deﬁned in terms of curvature.

See Section 11.12. Typically one seeks curves whose curvature functions are appro-

priately piecewise monotone. Sapidis ([Sapi92]) describes a simple geometric condi-

tion so that a quadratic Bézier curve segment has a monotone curvature function. It

is furthermore shown how to move the middle control point of that segment to correct

any bad curvature plot it may have initially.

Just because we have an approximation that is within a given tolerance of an

object does not mean that the shape of the object has been approximated very well.

A curve that wiggles about a straight line would not be a good approximation of

the shape of the line. As was indicated in earlier chapters, the choice of metric with

respect to which an approximation is deﬁned matters. Wolters and Farin ([WolF97])

describe a metric based on total curvature that does a better job in approximating

shape.

Miura ([Miur00]) proposes a new type of curve whose curvature is easier to manip-

ulate than that of the more traditional curves. The method is based on integrating

tangent vectors, speciﬁcally unit tangent vectors. In order to make this easier for the

user to deﬁne such vectors, the author’s system asks the user to pick points on the

unit sphere in an interactive way. The selected vectors are interpolated by thinking of

them as unit quaternions. This construction is the analog of the clothoid construc-

tion that has been used to manipulate plane curves in a way that controls curvature

properties. Miura calls his curve a unit quaternion integral curve.

Next, consider surfaces. Krsek et al. ([KrLM98]) describe methods for computing

curvature quantities from discrete data. The approach is to approximate the data by

second order curves or surfaces. Higher orders did not seem to lead to much improve-

ment. They describe various methods but analyze

The circle ﬁtting method: This turns out to be the fastest.

The paraboloid ﬁtting method: This is slower than the circle ﬁtting method but

more accurate on noisy data.

The Dupin cyclide method: This is the slowest but is usually more accurate than

the other two methods.

Wollmann ([Woll00]) also tries to estimate curvature values for a discrete surface. The

method is based on getting estimates to the curvature of curves and using Euler’s and

Meusnier’s theorem.

Meek and Walton ([MeeW00]) analyze the accuracy of various approaches to the

problem of getting approximations to surface normals and Gauss curvature given a

surface deﬁned by a set of discrete points. The assumption is that one has accurate

data for a smooth surface such as one would get from sampling points on a real object.

They analyzed the following methods for ﬁnding an approximation to the surface

normal and/or the Gauss curvature at a point p:

650 15 Local Geometric Modeling Topics

(1) Fitting a quadratic surface to the given data near p and using its normal and

Gauss curvature as approximations.

(2) Approximating the surface at p by a set of triangles incident to p and using

various types of averages of their normals.

(3) Approximating the Gauss curvature at p by discretizing its deﬁnition based

on the Gauss map where one thinks of it as a limit of the quotient of small

areas containing p and the area of their images on the unit sphere. See equa-

tion (9.42) in Chapter 9 in [AgoM05].

(4) Approximating the Gauss curvature at p by means of the angle deﬁcit

method.

One surprising conclusion was that the popular method (4) is not always very

accurate.

Andersson ([Ande93]) discusses how one could design a surface by modifying its

curvature. This is carried out in terms of solutions to boundary value problems for

partial differential equations.

Ye ([Ye96]) points out how a color-coded Gauss curvature map can be used to

judge the fairness of a surface. A smoothly varying map is good and rapidly varying

ones are bad. Ye answers the following question about the fairness of a surface where

two patches meet:

Question: Can the curvature continuity between the patches be visualized by means of the

Gauss curvature? Alternatively, if two patches are tangent-plane continuous along their

common edge and they have the same Gaussian curvature along the common edge, are

they curvature continuous there?

There is a similar question for mean curvature. Let k

(C,S,p) denote the normal cur-

vature at a point p of a curve C lying in surface S.

Deﬁnition. Let S

and S

be surfaces that are tangent-plane continuous along a

curve C. The surfaces are said to be curvature continuous along C if for all curves C

and C

on S

and S

, respectively, that meet and are tangent at a point p on C we have

that k

,p) = k

,p).

Ye gives an answer to the question in terms of Dupin indicatrices, principal cur-

vatures, and Gauss and mean curvatures. Mean curvatures turn out to be a better way

to measure curvature continuity.

Kaklis and Ginnis ([KakG96]) address the problem of constructing shape-

preserving C

surfaces that interpolate point sets lying on parallel planes. Call the

planar curves p

(u) interpolating the data of a given plane a skeletal line. We are basi-

cally looking for a skinning surface p(u,v) for the skeletal lines p

(u). Kaklis and Ginnis

describe how one can get a skinning surface that has the property that if the curva-

ture of adjacent curves p

(u) and p

i+1

(u) has the same sign over an interval [u

j+1

then the curvature of all the curves p(u,v), v Œ [v

i+1

] also has the same sign over the

interval [u

j+1

Wolter and Tuohy ([WolT92]) describe how to compute curvatures for degenerate

surface patches.

Other aspects of surfaces that are sometimes interesting are their lines of curva-

ture. Analyzing these involves solving differential equations. See [BeFH86]. Lines of

curvature are used to deﬁne principal patches.

15.2 Curvature 651

Finally, is there a notion of curvature in the case of polygonal objects? Such a

notion would be deﬁned at vertices and would be a function involving the angle

between adjacent edges for curves and the sum of the angles of the faces meeting at

a vertex for surfaces.

15.3 Geodesics

15.3.1 Generating Smooth Geodesics

The mathematics of geodesics for surfaces in R

is discussed in Section 9.10 in

[AgoM05]. The mathematical deﬁnition of a geodesic is that it is a function (a para-

meterized curve) deﬁned by second-order differential equations. This is what we shall

mean by the term “geodesic,” but it is sometimes used more loosely, for example, to

refer to the underlying set that is traced out by a geodesic. A common statement is

that a straight line in the plane is a geodesic, but one needs to remember that a line

can be parameterized in many ways and only some of those parameterizations would

actually fulﬁll the mathematical deﬁnition of a geodesic. Two other deﬁnitions that

are given sometimes (and that consider geodesics as sets rather than maps) are:

The Kinematic Deﬁnition. A geodesic is a curve traversed by a particle whose accel-

eration vector at a point lies in the plane spanned by the velocity vector and the normal

to the surface at that point. There is no “side-to-side” acceleration. Any acceleration

that there is, is used to keep the particle in the surface or to speed it up or slow it

down in the direction of the path.

The Static Force Deﬁnition. On a convex surface, a curve is called a geodesic if a

thread stretched along the path it traces out on the surface is in static equilibrium

with respect to any sideways tension on it.

A true geodesic would satisfy both of these criteria. However, a geodesic in the

kinematic or static force sense would not necessarily be a real geodesic since its accel-

eration vector might not be orthogonal to its velocity vector. Nevertheless, by Theorem

9.10.11 in [AgoM05] it does trace out a geodesic path.

Note. The boundary of a surface causes technical problems for the deﬁnition of a

geodesic because one often needs derivatives to be deﬁned in open neighborhoods of

a point. To avoid such problems, we shall assume throughout this section that either

our surfaces have no boundary or that all the curves being deﬁned are well away from

the boundary.

Consider a surface patch S in R

parameterized by

Any curve g(t) in S can be expressed in the form g(t) =j(a(t)), where

(If we were given g ﬁrst we could deﬁne a=j

-1

g.) See Figure 15.1. Let

a :, , ,.ab cd ef

[]

j :, ,cd ef

[]

Æ S

652 15 Local Geometric Modeling Topics

and

We know that

form a basis for the tangent space at every point of the surface and

is a normal vector at those points. The chain rule implies that

(15.1)

where Jj is the Jacobian matrix for j. It follows that

(15.2)

and

gajaj≤= ≤ + ¢

()

¢JJ

gja

jjj

()

=¢

()()

=¢

() ( )

=¢

()

()()

∂

()

∂

()

∂

()

∂

()

∂

()

∂

()

tD t

tJ uv

,,,

123

n =

∂

jjjj jjjj

uuuu

and

vvvv

123 123

,, ,,

aaattt

()

() ()()

jjjjuv uv uv uv,,,,,,

()

()()()()

123

15.3 Geodesics 653

Figure 15.1. Curve in parameterized

surface.

The condition on g≤(t) which makes the curve g(t) into a geodesic is that

(15.3a)

(15.3b)

This would lead to having to solve a second order differential equation for a.

Instead, by introducing a new variable a¢(t) =b(t), one turns the system (15.3)

into a system of ﬁrst order differential equations, which is the usual preferred

approach. See [PFTV86], for example, for ways to solve such systems of

equations.

Next, assume that we only want a geodesic in the kinematic or static force sense.

In this case, equations (15.3) get replaced by the single equation

(15.4)

where

Of course, as was pointed out earlier, such a curve g(t) may not mathematically be a

geodesic since g≤(t) may not be a normal to the surface, but it will trace out a geo-

desic path. Now, assume that the curve a(t) above is an arc-length parameterization

of a curve, so that |a¢(t)|=1. Let us parameterize the unit vectors a¢(t) by the turning

angle q(t). In other words, write

(15.5)

It follows from (15.5) and the chain rule that

(15.6)

If we replace g≤ in equation (15.4) by the right-hand side of equation (15.2) and also

replace a≤ by the right hand side of equation (15.6), then one can solve for q¢(t). In

fact, it is easy to show that solving (15.4) is equivalent to solving the following system

of equations:

¢¢

()

=¢

()

() ()()

aq q qtt t tsin , cos .

aqq¢

()

() ()()

tttcos , sin .

bnttt

()

()()

¥¢

()

gg.

g≤

() ()

=tt• b 0

a≤

()

∂

()()

t•.0

a≤

()

∂

()()

t•,0

uv uv

()

¢=

∂

¢+

∂

∂∂

∂

∂∂

¢+

∂

¢+

∂

∂∂

∂

∂∂

¢+

∂

¢+

∂

∂∂

∂

∂∂

¢+

∂

654 15 Local Geometric Modeling Topics

(15.7)

We shall return to this equation in Section 15.4.

Now what we have described so far are just local conditions for geodesics. The

curves must satisfy the differential equations shown above in a neighborhood of any

point through which they pass. Furthermore, there are of course many solutions to

these equations and to get unique solutions one needs to specify additional con-

straints. The most common constraints, and the ones handled most easily with stan-

dard numerical techniques for solving differential equations, are initial conditions.

Typical initial conditions would be a start point of the desired curve and a direction

vector. However, this does not solve the problem of ﬁnding a shortest curve between

two points because we would not know the initial direction of the curve. The short-

est curve problem is a boundary value problem and much more difﬁcult. A solution

to the discrete version of this problem is described in the next section.

One area where one has to deal with geodesics is in the design and manufacture

of composite materials. See Section 15.4 below. In this case one wants to generate

geodesics given a start point and an initial direction. A common approach is to tes-

sellate the surface and generate geodesics on the resulting polygonal surface. The

paper [KSHS03] describes differential equations for a geodesic obtained from a vari-

ational approach and compares the numeric solution to these equations to the dis-

crete geodesics one can generate on the approximating polygonal surface using two

different algorithms. It turns out that the deviation of the discrete geodesics from the

smooth geodesic is not always proportional to the error caused by the tessellation but

depends also on the complexity of the surface.

We ﬁnish this section with an example. Unfortunately, just as very few curves have

a simple formula for their length, very few geodesics have a simple formula. Never-

theless, the following may help the reader understand the mathematics.

15.3.1.1 Example. Consider the paraboloid of revolution S deﬁned by the

equation

and parameterization

We want to compute the equations that deﬁne the geodesics for this surface.

Solution. Let a(t) = (u(t),v(t)) be a curve in the domain of j. First of all, observe

that

∂

()

∂

()

u and

v102 012,, ,, ,

j uv uvu v uv,,, ,, .

()

22 2

fxyz z x y,,

()

=- -

qqy

¢=

()()

¢=

cos , sin •

sin , cos •

cos

cos .

15.3 Geodesics 655