第1页 / 共277页
第2页 / 共277页
第3页 / 共277页
第4页 / 共277页
第5页 / 共277页
第6页 / 共277页
第7页 / 共277页
第8页 / 共277页
Introduction to Computing with Geometry Notes.pdf
Course Overview
Why Is Computing with Geometry Important?
The Theme of this Course
The Complexity of Geometric Problems
Computing with Floating Point Numbers
Problems
References
Geometric Concepts
Coordinate Systems, Points, Lines and Planes
Two-Dimensional Objects
Three-Dimensional Objects
Vectors
Simple Curves and Surfaces
Curves
Surfaces
Homogeneous Coordinates
Geometric Transformations
Euclidean Transformations
Affine Transformations
Projective Transformations
Matrix Multiplication and Transformations
Problems
References
Solid Models
Solid Representations: An Introduction
Wireframe Models
Boundary Representations
Manifolds
The Winged-Edge Data Structure
The Euler-Poincaré Formula
Euler Operators
Constructive Solid Geometry
Interior, Exterior and Closure
Regularized Boolean Operators
A CSG Design Example
Problems
References
Parametric Curves
Parametric Curves: A Review
Tangent Vector and Tangent Line
Normal Vector and Curvature
Continuity Issues
Rational Curves
Problems
References
Bézier Curves
An Introduction
Construction of Bézier Curves
Moving Control Points
Finding a Point on a Bézier Curve: De Casteljau's Algorithm
Why Is de Casteljau's Algorithm Correct?
Derivatives of a Bézier Curve
Subdividing a Bézier Curve
Why Is the Subdivision Algorithm Correct?
Degree Elevation of a Bézier Curve
Why Is the Degree Elevation Algorithm Correct?
Problems
References
B-spline Curves
Motivation
B-spline Basis Functions
B-spline Basis Functions: Definition
B-spline Basis Functions: Important Properties
B-spline Basis Functions: Computation Examples
B-spline Curves
B-spline Curves: Definition
B-spline Curves: Important Properties
B-spline Curves: Computing the Coefficients
B-spline Curves: Moving Control Points
B-spline Curves: Modifying Knots
Derivatives of a B-spline Curve
Important Algorithms for B-spline Curves
Knot Insertion
De Boor's Algorithm
B-spline Curves: Subdividing a B-spline Curve
Problems
References
NURBS Curves
NURBS: Motivation
NURBS: Definition
NURBS: Important Properties
NURBS: Modifying Weights
An In-Depth Discussion
Important Algorithms for B-spline and NURBS Curves
NURBS Curves: Knot Insertion
De Boor's Algorithm
Rational Bézier Curves
Rational Bézier Curves: Conic Sections
Circular Arcs and Circles
Surfaces
Basic Concepts
Bézier Surfaces
Bézier Surfaces: Construction
Bézier Surfaces: Important Properties
Bézier Surfaces: de Casteljau's Algorithm
B-spline Surfaces
B-spline Surfaces: Construction
B-spline Surfaces: Important Properties
B-spline Surfaces: de Boor's Algorithm
Interpolation and Approximation
Parameter Selection and Knot Vector Generation
Parameter Selection Overview
The Uniformly Spaced Method
The Chord Length Method
The Centripetal Method
Knot Vector Generation
The Universal Method
Parameters and Knot Vectors for Surfaces
Solving Systems of Linear Equations
Curve Interpolation
Curve Global Approximation
Surface Global Interpolation
Surface Global Approximation
Introduction to Computing with Geometry Notes
Dr. C.-K. Shene
July 1, 1998
Chapter 1
Course Overview
1.1 Why Is Computing with Geometry Impor-
tant?
Up to now, perhaps most of your programs use only integers, except for
those you wrote in a numerical methods course which use floating point numbers
exclusively. Before you enter computer graphics, you perhaps would not know
how to use these numbers (integers and/or reals) for representing geometric ob-
jects. But, why is handling geometric objects so important? At a first
glance, the answer to this question is simple: it is because this world is full of
geometric objects. For example, your car, desk, table, chair, CD-ROM and its
player, and TV are all geometric objects. If this is not good enough, just take
a look at the field of computer science to see how many branches do need the
skill of handling geometric objects.
• Computer Graphics
This does not require any further explanation. All characters in Toy Story
are geometric objects. Computer-Aided Design Engineers use computer-
aided design systems for designing something (e.g., a piston engine or a
model aircraft). These are, of course, geometric objects.
• Computational Geometry
What is Computational Geometry? Is it identical to Computing with
Geometry? Literally, they should be the same. However, computational
geometers study the algorithmic aspect and complexity measure of geo-
metric problems involving simple geometric objects such as points, lines,
line segments, polylines and polygons, circles and circular arcs, spheres
and polyhedra. Some classical problems are (1) computing the convex
hull of a set of points, (2) determining the intersection points of a set of
line segments, and (3) triangulating a simple polygon. While the focus is
1
theoretical and algorithmic, the field of computational geometry does deal
with geometric objects.
• Visualization
Richard Hamming once said
The purpose of computing is insight, not numbers
Visualization explores data and information graphically - as a means of
gaining understanding and insight into the data (R. A. Earnshaw and
N. Wiseman, An Introductory Guide to Scientific Visualization, Springer-
Verlag, 1992). As long as graphics is involved, geometric objects appear.
A good example of visualization is medical scanning. An object is scanned
producing many contours on parallel planes. How do we reconstruct the
scanned object, including its interior, from the given contours?
• Computer Vision
In computer vision and image processing, features are extracted from im-
ages taken by cameras and used for other purposes. For example, two
cameras are mounted on a robot for taken stereo pictures. Features are
extracted and sent to algorithms that control the motion of the robot so
that it will not collide with the surrounding environment. What are fea-
tures? Points, line segments and circles are all features in an image. In
many cases, the extracted features are used to reconstructed the scene.
1.2 The Theme of this Course
Going from a geometric concept/problem to a working program usually
takes several steps as follows:
Geometry → Algebra → Algorithm → Program
Since computers do not understand geometry, one must convert a geometric
problem to an algebraic one that uses numbers. Then, one can design algorithms
to manipulate these numbers and finally, programs are developed based on these
algorithms. However, each step is a difficult and challenging task.
Geometry → Algebra
When we think about a geometric object, even a simple one such as a
point or a line, we normally have its shape in mind. But, to have computers to
process a geometric object, we have to find a representation for that object so
that it can be described in a form that can be manipulated by computers. For
example, a point in three-dimensional space is represented with three numbers
like (2.5, 0.0, -4.0), and a line in the xy-coordinate plane has an equation like
3x − 5.3y + 3 = 0.
A geometric object’s representation is usually not unique. A circle can be rep-
resented by an implicit equation:
x2 + y2 = 1
2
(1.1)
or in a parametric form using trigonometric functions:
x = cos(t)
y = sin(t)
(1.2)
(1.3)
where t is in the range of 0 and 360 degree.
Some geometric objects such as polyhedra many even require complex data
structures to represent all of its details. Therefore, finding a good and appro-
priate representation (for a particular application) is usually a very challenging
task. We shall cover some of these representations in this course. Some are
mathematical (for curves and surfaces) and some are combinatorial (for polyhe-
dra). Whatever representation is chosen, it must be easy to use and manipulate,
and support all desired operations efficiently and accurately.
In addition to a representation for a particular type of geometric objects,
one must convert geometric operations to algebraic forms, too. Take a look at
the following question. Given a sphere of radius r, what is the locus of this
sphere if its center moves on a curve? We know that the locus, usually referred
to as a sweep, looks like a tube; but, it is not so easy to know what exactly
this tube looks like. If the curve is a line, the locus is a cylinder. The difficult
part is that the curve is not a line and/or that the radius of the given sphere
can change. Therefore, we have an easily described geometric operation whose
algebraic counterpart is somewhat complicated.
Algebra → Algorithm
After finding representations for geometric objects and algebraic interpre-
tations for your geometric operations, the next step is to find algorithms for
manipulating the representations and equations. Is it easy? Sometimes it is.
For example, if the problem is ”determine if two lines on the xy-coordinate plane
intersect and if they are, find the intersection point,” it can be solved easily. Let
the lines be
Ax + By + C = 0
(1.4)
U x + V y + W = 0
(1.5)
Then, if they are parallel to each other (i.e., A ∗ V = B ∗ U ), there is no in-
tersection point; otherwise, the intersection point can be found by solving the
above simultaneous linear equations of two variables.
Unfortunately, other practical problems are not so easy. First, the repre-
sentation of a geometric object such as a piston engine of the Boeing 777 is huge
and the number of equations, usually non-linear ones with many variables, is
also huge. Manipulating these representations and equations is not an easy job.
However, we have at least the following choices:
• Symbolic Computation
A symbolic system delivers symbolic answers. For example, if you ask a
symbolic system to solve a quadratic equation Ax2 + Bx + C = 0, it would
3
give you the following equations of roots:
root1 = (−B + SQRT (B2 − 4 ∗ A ∗ C))/(2 ∗ A)
root2 = (−B − SQRT (B2 − 4 ∗ A ∗ C))/(2 ∗ A)
(1.6)
(1.7)
Therefore, the answers are algebraic rather than numerical. There are
good symbolic systems available (e.g., Mathematica and Maple). Com-
putation cost is usually very high (e.g. very slow). On the other hand,
symbolic computation is able to give you a closed-form solution, a form
that can be written in one or more formulae.
• Numerical Computation
Numerical solutions give you a bunch of numbers rather than a closed-form
solution. Numerical computation has been a popular way of finding solu-
tions for geometric problem. For example, in calculus you perhaps have
learned Newton’s method for solving non-linear equation. The solution is
merely a number. Numerical computation is fast; but, since computer-
s cannot represent real numbers exactly, extreme care must be taken to
avoid loss of significant digits and other related problems. For example,
if the initial guess for Newton’s method is incorrect, you may not be able
to find a root. As a suggestion, please try to solve the following equation
using Newton’s method:
f (x) = x1/(2n+1)
(1.8)
where n is a positive integer. This equation has a root at zero. But,
Newton’s method will not converge to zero at all. Try it yourself.
• Approximation
Since symbolic computation is time consuming and numerical computa-
tion sometime does not deliver the result, let us take a compromise. Let
us simplify our solution by only asking for a good approximation. For ex-
ample, it is provably true that in general a polynomial with degree higher
than four does not have any closed-form solution. Numerical methods
(e.g. Newton’s method) can only give us an approximation of the roots of
a higher degree polynomial. So, the question is ”how good is good.” This
is obviously problem dependent. We shall return to this question later on.
The above does not enumerate all possibilities. One can combine several ways
together to solve a single problem. For example, one can use symbolic to solve
some parts of the problem and use a combination of numerical computation
and approximation to do the remaining.Recently, some authors suggested the
so-called geometric methods whose fundamental merit involves characterizing
the results using geometry reasoning and using the characterization for calcu-
lating the result. This method usually work fine with simple problems and may
require a large number of case-by-case analysis. However, if geometric method
works, it usually delivers the solution fast and is more accurate and robust than
4
other methods. We will not pursue in this direction in this course.
Algorithm → Program
Ok, you might want to say that, after all of the troubles in the previous
steps, we have algorithms and therefore writing program should be easy. No,
it is not always the case. Translating some algorithms in your algorithms de-
sign textbook to programs may be easy. Translating geometric algorithms to
programs requires extreme care. There are geometric programming languages.
Even though you have had all the helps from a programming system, its de-
bugger and graphics library, you still have to be very careful about the problem
of real number computations. Computation errors and loss of significant dig-
its may occur easily and in many cases their impacts may be propagated and
amplified. As a result, a theoretically sound algorithm may deliver meaningless
results. You may have learned this in a numerical methods course; but, I will re-
iterate this issue later on to emphasize its importance in geometric computation.
————————————————
In this course, we shall introduce several representations for curves, surfaces
and solids and their accompanying geometric operations. We shall spend a
considerable amount of time on curves and surfaces design using approxima-
tion. Another point we want to emphasize is the impact of floating number
computations on geometric problems. Some classical computational geometry
problems will also be mentioned, because they are useful and can illustrate what
computational geometers are doing.
1.3 The Complexity of Geometric Problems
In an algorithms design course, you learned complexity measures of algo-
rithms. For example, an optimal sorting algorithm takes O(nlog(n)) compar-
isons, where n is the number of data items to be sorted. Although normally
we do not count the number of steps for solving a geometric problem because
it is not always possible (e.g., how many step are required to solve a non-linear
equation using Newton’s method?), understanding the complexity of a geomet-
ric problem would be very helpful.
Adrian Bowyer and John Woodwark distinguish three types of complexity
in a geometric problem: namely, dimensional complexity, analytic complexity
and combinatorial complexity.
Dimensional Complexity
Geometric objects in a plane are definitely simpler than those in space, because
as dimension increases the complexity of a geometric object increases. Moreover,
some geometric properties available in space may not exist in a plane. A line in
the xy plane has a simple equation like Ax+By+K=0; but, you have no way to
write a line equation by adding a new variable z like Ax+By+Cz+K=0 because
5
it is a plane rather than a line. Situation in higher dimensions is worse. For
example, a curve in a plane does not twist; but, it can be in three dimensions.
Thus, to describe the geometric properties of a curve, one has to include this
”twisting” into consideration. There is no ”surfaces” in a plane; but, surfaces
in space are more complex than curves in space and curves in a plane.
Analytic Complexity
While it is not accurate, you may think ”analytic” as ”equational.” Are
there any complexity related to equations? A lot. Polynomials of degree 1, 2,
3, 4 and 5 are usually referred to as linear, quadratic, cubic, quartic and quintic
polynomials. Then, we have rational polynomials which are the quotients of
two polynomials. The following are some examples:
f (x) =
g(x, y) =
x3 + 2x + 1
x2 + 4
x2 − y2
x2 + y2 + 1
h(x, y, z) =
Ax + By + Cz + K
x2 + 5xy − 4y2 + x − y + 10
(1.9)
(1.10)
(1.11)
Beyond polynomials and rational polynomials, we have transcendental functions
such as sin(), cos(), tan(), asin(), asin(), atan(), log() and exp(). All of these
functions add extra complexity into the solution of a geometric problem.
Worse, in many cases an equation does not tell us the actual geometric
intent at all. For example, x2 − y2 − 2y − 1 = 0 is a quadratic equation because
the highest degree is 2. But, it is not a conic curve (i.e., an ellipse, hyperbola
or parabola); it actually represents two lines, x + y + 1 = 0 and x − y − 1 = 0,
because it can be factorized as (x + y + 1)(x − y − 1) = 0. An equation may
not represent any point (well, any REAL point) in a plane. For example, what
is the graph of x2 + y2 + 1 = 0? Since the square of any real number must be
positive, the left-hand side (i.e., x2 + y2 + 1) is always positive and hence there
exists no real points that can satisfy this equation.
In some geometric operations such as intersection computation the situation
can become very nasty. Detecting if a line and a surface intersect is a common
operation in raytracing. However, this is definitely not an easy job, and if the
surface is a complex one this job could become much more difficult. Why? In
three-dimension, a line can be written as:
x = a + tu
y = b + tv
z = c + tw
where t is a parameter. Plugging (x, y, z) into the equation of a surface, say
f (x, y, z) = 0, yields f (a + tu, b + tv, c + tw) = 0. Rearranging gives us a
6
polynomial in t:
a0 + a1t + a2t2 + a3t3 + ... + an−1tn−1 + antn = 0
(1.12)
Solving for t gives the intersection points. Mathematically it is done. Since it
is well-known (in mathematics) that polynomials with degree higher than four
do not have closed-form solutions. That means, numerical methods is required
to solve the above equation. We have two problems here:
1. A polynomial of degree n has exactly n roots. Numerical methods for
solving equations usually deliver only one root. What if that one is not
what we want?
2. Since computers cannot represent real numbers precisely, the computed
root usually are not precise either. Generally it is not a big problem. The
problem usually occurs when the line is almost tangent to the surface. If
the distance between the line and the surface is smaller than the compu-
tation error, you might think the line actually intersects the surface!
All of these make analytic complexity very difficult to deal with. In fact, there
are other mathematical constraints that have not yet been touched upon. There-
fore, that is why we use approximations to bring the study of geometric objects
and their accompanying operations to a more manageable form.
Combinatorial Complexity
This is what you are familiar with. For example, searching a sorted array
of n elements uses O(log2n) comparisons. The number of steps used to solve
a geometric problem is a function of the number of geometric objects involved.
This is similar to what you have learned in algorithms design. Since many ap-
plications use computational geometry types algorithms (e.g., computing the
convex hull of a set of points), this type of combinatorial complexity measure
makes sense.
If polynomials are the major tools for solving geometric problems, the num-
ber of coefficients of a polynomial, which depends on the degree of the polyno-
mial and the number of dimensions, adds another level of complexity. For an
example, a polynomial of two variables, which described a curve in the xy-plane,
has (n + 1)(n + 2)/2 coefficients. More precisely, a line is a degree 1 polynomial
and has three coefficients (e.g., Ax + By + C = 0); a conic curve is a degree
two curve and has six coefficients (e.g., Ax2 + Bxy + Cy2 + Ex + Ey + F = 0);
and a cubic curve is a degree three polynomial and has 10 coefficients (e.g.,
Ax3 + Bx2y + Cxy2 + Dy3 + Ex2 + F xy + Gy2 + Hx + Iy + J = 0). Therefore,
the number of coefficients (or terms) of degree n polynomial increases propor-
tional to the square of n.
For polynomials of three variables, which describe surfaces in space, the
number of coefficients (or terms) is (n + 1)(n + 2)(n + 3)/6, where n is the
degree of the polynomial. For example, a plane is a degree 1 polynomial and
has four coefficients (e.g., Ax + By + Cz + D = 0); and a quadric surface is a
7
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
