CS3621 密歇根理工大学计算机几何学入门课程笔记-上

[TOC]

密歇根理工大学计算机几何学入门课程笔记上半部分, 主要介绍计算机几何的基础知识.

Introduction to Computing with Geometry

Dr. C.-K. Shene
Department of Computer Science
Michigan Technological University

学习目的

路径规划的目的就是得到一条可行的轨迹, 轨迹是必须要用计算机几何来描述/操作的. 因此有必要学习一些入门的基础知识, 特别是关于曲线相关的. 这门课程循序渐进并且以贝塞尔曲线与 B 样条曲线为主要内容, 正好适合目前的需求. 同时一些基础的应用数学也在讲义中有详细的推导过程, 例如 LU 分解求解法, 做到了在应用中学习数学的作用. 特记录学习笔记于此.

此笔记分为上下 2 部分. 此文为上部.

Unit 1: Course Overview

略过.

Unit 2: Geometric Concepts

Chapter1. Coordinate Systems, Points, Lines and Planes

Vectors

position vectors 点向量, 小写粗体 $\textbf{a}$, direction vectors 方向向量大写粗体 $\textbf{A}$.

Inner Product 内积

two vectors $\textbf{a}$ and $\textbf{b}$: sum of the products of corresponding components,记作为 $\textbf{a} \cdot \textbf{b}$.
例如 $\textbf{a} = <1,2,3>$ and $\textbf{b} = <2,-1,4>$, then $\textbf{a} \cdot \textbf{b} = 1 \times 2 + 2 \times (-1) + 3 \times 4 = 12$.
geometric meaning: $\textbf{a} \cdot \textbf{b} = |\textbf{a}| \cdot |\textbf{b}|cos(t)$, 计算向量间夹角.

推论：

1. 判断垂直: If $\textbf{a} \cdot \textbf{b}$ is zero, $\textbf{a}$ and $\textbf{b}$ are perpendicular to each other.
2. 判断同向: If $\textbf{a} \cdot \textbf{b}$ is equal to the product of lengths of $\textbf{a}$ and $\textbf{b}$, $\textbf{a}$ and $\textbf{b}$ are parallel to each other and point to the same direction.
3. 判断逆向: If $\textbf{a} \cdot \textbf{b}$ is equal to the negative product of lengths of $\textbf{a}$ and $\textbf{a}$, the cosine of $t$ is -1 and $\textbf{a}$ and $\textbf{b}$ are parallel to each other but point to opposite directions.

Lines

defined by a based point $\textbf{B}$ and a direction vector $\textbf{d}$(通常unit-length)
表达为 $B + td$.

Planes

$X \cdot n - B \cdot n = 0$
based point $B$ and its normal vector $n$, arbitrary point/position vector $\textbf{X}$ 与 $B$ 垂直.
可以用来求点面交点:
$$(A+td) \cdot n - B \cdot n = 0$$
$$t = (B-A) \cdot n / d \cdot n$$

Cross Product 外积

外积的结果为向量, 并且两个向量的外积与这两个向量组成的坐标平面垂直, $(\textbf{a},\textbf{b},\textbf{a}×\textbf{b})$构成右手系.

$\textbf{a} × \textbf{b}$, 例子:
$ \textbf{a} = < a_1, a_2, a_3 >, \textbf{b} = < b_1, b_2, b_3 > $
$ \textbf{a} × \textbf{b} = < a_2b_3 - a_3b_2, -(a_1b_3 - a_3b_1), a_1b_2 - a_2b_1 > $

即:

$$
\mathbf{a} \times \mathbf{b}=\left\langle\left|\begin{array}{ll}
a_{2} & a_{3} \
b_{2} & b_{3}
\end{array}\right|,-\left|\begin{array}{ll}
a_{1} & a_{3} \
b_{1} & b_{3}
\end{array}\right|,\left|\begin{array}{ll}
a_{1} & a_{2} \
b_{1} & b_{2}
\end{array}\right|\right\rangle
$$

性质:

• 不满足交换律
  特别地, $0×\textbf{a} = \textbf{a}×0 = 0$. 对任意向量 $\textbf{a}$, $\textbf{a}×\textbf{a}=0$.
• 反称性
  $\textbf{a} × \textbf{b} = -\textbf{b} × \textbf{a}$.
• 线性
  $(λ\textbf{a} + μ\textbf{b}) × \textbf{c} = λ(\textbf{a} ×c) + μ(\textbf{b} × \textbf{c})$.

几何意义:

1. $|\textbf{a}| \cdot |\textbf{b}| \sin(t)$, 计算夹角 $\sin$.
2. 在二维空间中, 外积还有另外一个几何意义就是: $|\textbf{a}×\textbf{b}|$ 在数值上等于由向量 $\textbf{a}$ 和向量 $\textbf{b}$ 构成的平行四边形的面积.

Chapter2. Simple Curves and Surfaces

Curves

Circles

$$
(x - a)^2 + (x - b)^2 = r^2
$$

参数曲线形式

$$
x = a + r \cos(t) \\
y = b + r \sin(t)
$$

Conics in Normal Forms 圆锥曲线

ellipse:

$$
x = acos(t) \\
y = bsin(t)
$$

hyperbola 双曲线:

$$
x = asec(t)\\
y = btan(t)
$$

parabola 抛物线:

$$
x = t\\
y = t^2 / (4p)
$$

Conics in General Form

$$
A x^{2}+2 B x y+C y^{2}+2 D x+2 E y+F=0
$$

If $B^2 < AC$, the general equation represents an *ellipse*.
If $B^2 = AC$, the general equation represents a *parabola*.
If $B^2 > AC$, the general equation represents a hyperbola.

Conics in Matrix Form

$$
X^TQX
$$

其中:

$$
\mathbf{x}=\left[\begin{array}{l}
x \
y \
1
\end{array}\right] \quad \mathbf{x}^{T}=[x, y, 1] \quad \mathbf{Q}=\left[\begin{array}{ccc}
A & B & D \
B & C & E \
D & E & F
\end{array}\right]
$$

Surfaces

略过.

Chapter3. Homogeneous Coordinates 齐次坐标

• 目的: capture the concept of infinity(Euclidean coordinate system 的局限无法表达无限)
  将点的欧式坐标系 $(x, y, z)$ 转换为齐次坐标系 $(x/w, y/w, z/w,w)$ 当 $w=0$ 时, 表示无穷, 被称作 ideal point or the point at infinity in the direction of $(x,y,z)$.
  向量表示 为$O + (1/w)d$, 坐标原点 $O$ 与方向向量 $\textbf{d}$.
• 几何意义: 将原坐标系升一个维度后原坐标点与 $w$ 平面的交点.

欧式坐标系与齐次坐标系转换:

• 欧式坐标系->齐次坐标系转换: 不唯一.
• 齐次坐标系->欧式坐标系: 唯一.

Chapter4. Geometric Transformations 几何变换

geometric objects transformation / coordinate system transformation

Euclidean Transformations

a translation, a rotation, or a reflection 平移/旋转/映射

Translations and Rotations on the xy-Plane 2D变换

• $(x,y)$ 转换为齐次坐标系:

$$
\begin{bmatrix}
x \
y \
1
\end{bmatrix}
$$

• 平移：

$$
\left[\begin{array}{l}
x^{\prime} \
y^{\prime} \
1
\end{array}\right]=\left[\begin{array}{lll}
1 & 0 & h \
0 & 1 & k \
0 & 0 & 1
\end{array}\right] \cdot\left[\begin{array}{l}
x \
y \
1
\end{array}\right] \quad\left[\begin{array}{l}
x \
y \
1
\end{array}\right]=\left[\begin{array}{ccc}
1 & 0 & -h \
0 & 1 & -k \
0 & 0 & 1
\end{array}\right] \cdot\left[\begin{array}{c}
x^{\prime} \
y^{\prime} \
1
\end{array}\right]
$$

$$
Ax + By + C = 0 \rightarrow Ax’ + By’ + (-Ah - Bk + C) = 0
$$

• 原点旋转：

$$
\left[\begin{array}{c}
x^{\prime} \
y^{\prime} \
1
\end{array}\right]=\left[\begin{array}{ccc}
\cos a & -\sin a & 0 \
\sin a & \cos a & 0 \
0 & 0 & 1
\end{array}\right] \cdot\left[\begin{array}{l}
x \
y \
1
\end{array}\right] \\
\quad \\
\left[\begin{array}{l}
x \
y \
1
\end{array}\right]=\left[\begin{array}{ccc}
\cos a & \sin a & 0 \
-\sin a & \cos a & 0 \
0 & 0 & 1
\end{array}\right] \cdot\left[\begin{array}{l}
x^{\prime} \
y^{\prime} \
1
\end{array}\right]
$$

$$
(A \cos a - B \sin a)x’ + (A \sin a + B \cos a)y’ + C = 0
$$

• 先平移后原点旋转：

$$
\begin{array}{l}
{\left[\begin{array}{l}
x^{\prime} \
y^{\prime} \
1
\end{array}\right]=\left[\begin{array}{ccc}
\cos a & -\sin a & h \
\sin a & \cos a & k \
0 & 0 & 1
\end{array}\right] \cdot\left[\begin{array}{l}
x \
y \
1
\end{array}\right]} \
\quad \
{\left[\begin{array}{l}
x \
y \
1
\end{array}\right]=\left[\begin{array}{ccc}
\cos a & \sin a & -h \cos a-k \sin a \
-\sin a & \cos a & h \sin a-k \cos a \
0 & 0 & 1
\end{array}\right] \cdot\left[\begin{array}{c}
x^{\prime} \
y^{\prime} \
1
\end{array}\right]}
\end{array}
$$

• 先原点旋转后平移：

$$
\begin{array}{c}
{\left[\begin{array}{l}
x^{\prime} \
y^{\prime} \
1
\end{array}\right]=\left[\begin{array}{ccc}
\cos a & -\sin a & h \cos a-k \sin a \
\sin a & \cos a & h \sin a+k \cos a \
0 & 0 & 1
\end{array}\right] \cdot\left[\begin{array}{l}
x \
y \
1
\end{array}\right]} \
\quad \
{\left[\begin{array}{l}
x \
y \
1
\end{array}\right]=\left[\begin{array}{ccc}
\cos a & \sin a & -h \
-\sin a & \cos a & -k \
0 & 0 & 1
\end{array}\right] \cdot\left[\begin{array}{c}
x^{\prime} \
y^{\prime} \
1
\end{array}\right]}
\end{array}
$$

旋转平移的矩阵互为逆矩阵.

Translations and Rotations in Space 3D 变换

• 平移:
  

$$
\left[\begin{array}{c}
x^{\prime} \
y^{\prime} \
z^{\prime} \
1
\end{array}\right]=\left[\begin{array}{llll}
1 & 0 & 0 & p \
0 & 1 & 0 & q \
0 & 0 & 1 & r \
0 & 0 & 0 & 1
\end{array}\right] \cdot\left[\begin{array}{l}
x \
y \
z \
1
\end{array}\right] \
\quad \
\left[\begin{array}{l}
x \
y \
z \
1
\end{array}\right]=\left[\begin{array}{cccc}
1 & 0 & 0 & -p \
0 & 1 & 0 & -q \
0 & 0 & 1 & -r \
0 & 0 & 0 & 1
\end{array}\right] \cdot\left[\begin{array}{c}
x^{\prime} \
y^{\prime} \
z^{\prime} \
1
\end{array}\right]
$$

• 绕 Z 轴旋转:

$$
\left[\begin{array}{c}
x^{\prime} \
y^{\prime} \
z^{\prime} \
1
\end{array}\right]=\left[\begin{array}{cccc}
\cos a & -\sin a & 0 & 0 \
\sin a & \cos a & 0 & 0 \
0 & 0 & 1 & 0 \
0 & 0 & 0 & 1
\end{array}\right] \cdot\left[\begin{array}{l}
x \
y \
z \
1
\end{array}\right] \
\quad \
\left[\begin{array}{l}
x \
y \
z \
1
\end{array}\right]=\left[\begin{array}{cccc}
\cos a & \sin a & 0 & 0 \
-\sin a & \cos a & 0 & 0 \
0 & 0 & 1 & 0 \
0 & 0 & 0 & 1
\end{array}\right] \cdot\left[\begin{array}{c}
x^{\prime} \
y^{\prime} \
z^{\prime} \
1
\end{array}\right]
$$

注意左右手坐标系等造成的旋转正负问题.

Affine Transformations 仿射变换

平移旋转不改变长度角度, 仿射变换改变, 但不改变要素几何关系例如平行相交, 仿射变换包括欧式变换.

• Scaling
  在某个坐标轴上延伸/缩短 scaling factor, $x’ = p x$
• Shear 切变

$$
\left[\begin{array}{l}
x^{\prime} \
y^{\prime} \
z^{\prime} \
1
\end{array}\right]=\left[\begin{array}{llll}
1 & 0 & a & 0 \
0 & 1 & b & 0 \
0 & 0 & 1 & 0 \
0 & 0 & 0 & 1
\end{array}\right] \cdot\left[\begin{array}{l}
x \
y \
z \
1
\end{array}\right] \
\quad \
\left[\begin{array}{l}
x \
y \
z \
1
\end{array}\right]=\left[\begin{array}{cccc}
1 & 0 & -a & 0 \
0 & 1 & -b & 0 \
0 & 0 & 1 & 0 \
0 & 0 & 0 & 1
\end{array}\right] \cdot\left[\begin{array}{c}
x^{\prime} \
y^{\prime} \
z^{\prime} \
1
\end{array}\right]
$$

$$
x’ = x + az\
y’ = y + bz\
z’ = z
$$

保持一个轴不变, $(x, y)$ is “pushed” in the direction of $(a, b, 0)$ with a factor $z$.

• General Affine Transformations
  

注意系数矩阵 non-singular.

Projective Transformations

仿射变换的更进一步,可以改变几何关系,使平行变换成相交,在homogeneous coordinates内.

4-by-4 matrices must be non-singular.
Projective transformation can bring finite points to infinity and points at infinity to finite range.

Unit 3: Solid Models

略过.

Unit 4: Parametric Curves 参数曲线

Chapter1 Overview

略过.

Chapter2. Tangent Vector and Tangent Line

unit-length tangent vector: at parameter u, or at point $f(u)$, is $f’(u) / | f’(u) |$
tangent line: at $f(u)$ is $f(u) + tf’(u)$ 换成 unit-length direction vector$f(u) + t(f’(u)/|f’(u)|)$

Chapter3. Normal Vector and Curvature

moving trihedron 移动三面体

fixed point $f(u)$
osculating plane 密切平面：包含$f(u)$ tangent line,表达为$f(u) + pf’(u) + qf’’(u)$
binormal vector$b(u)$:$b(u) = (f’(u) × f’’(u)) / | (f’(u) × f’’(u)) |$
binormal line:$f(u)+tb(u)$
normal vector:$n(u) = ( b(u) × f’(u) ) / | b(u) × f’(u) |$
normal line:$f(u)+tn(u)$
三条线组成了点的移动三面体,描述了沿曲线运动的前进/上下/转向过程.具体关系见下图

right-handed system

Curvature

两种描述方式:1.速度,derivative of the tangent vector.2.切近圆弧度,下图.

Chapter4. Continuity Issues 连续性

$C^k$ continuous at point $f(b)=g(m)$: for all $i <= k$, the i-th derivatives at $f(b)$ and $g(m)$ are equal.
curvature continuous does not guarantee $C^2$ continuous; but, $C^2$ continuous does imply curvature continuous.

Problems with Parametric Representations

变换参数表达式对连续性影响很大.
reparameterization or change of variables have a dramatic impact on continuity!

例如：

$$
f(u) = A + u(B - A)
g(v) = B + v(C - B)
$$

not $C^1$ continuous at the joining point B.

VS
$$
F(u) = A + u(B - A)/ | B - A |
G(v) = B + v(C - B)/ | C - B |
$$

$C^1$ continuous at the joining point B

Arc Length Parameterization

弧长参数曲线可以避免上述问题. 但是比较难求, 对应到自动驾驶规划轨迹为 spiral curve.

Because different parametric forms of the same curve may induce different continuity results.
=> use arc length as a parameter.
reparameterizing it with arc length sometime is extremely difficult.
That is, finding arc length is not an easy task,
since it requires to integrate a function involving the use of square root.

Geometric Continuity

参数连续有时无法准确描述真实曲线的连续性, 例如有些 $C^1$ 连续的曲线在连接处 $C^2$ 甚至不可导, 但是如果换个参数表达式又可以反映出 $C^2$ 连续性. 因此引出了稍微宽松的几何连续性 $G^k$.

• 弧长参数表达式可以准确表达连续性 $G^k$

Two curve segments are said $G^k$ geometric continuous at the joining point if and only if all $i$-th derivatives, $i$ less than or equal to $k$, computed with arc length parameters agree at the joining point.

• 连接处如果能找到两种参数表达式(不要求是弧长)满足连续性, 成为 $G^k$ 连续

Two curve segments are said $G^k$ geometric continuous at the joining point if and only if there exists two parameterizations, one for each curve segment, such that all $i$-th derivatives, $i$ less than or equal to $k$, computed with these new parameterizations agree at the joining point.

对于一般应用而言 $G^1$, $G^2$ 常用, 如何找到满足 $G^1$, $G^2$ 条件参考如下.

对于 $G^1$:
Two $C^0$ curve segments are said $G^1$ geometric continuous at the joining point if and only if vectors $f’(u)$ and $g’(v)$ are in the same direction at the joining point.

对于$G^2$:
Two $C^1$ curve segments are said $G^2$ geometric continuous at the joining point if and only if vector $f’’(u) - g’’(v)$ is parallel to the tangent vector at the joining point.

Chapter5. Rational Curves

Parametric representations using polynomials 的局限: 无法表达封闭曲线.

rational curve: A parametric curve in homogeneous form 齐次坐标系下描述的曲线描述.

polynomial curve: a curve in polynomial form
分为
implicit polynomial form curve: 例如, $y=f(x)$.
parametric polynomial form curve: 例如, $y=f(u), x=g(u)$.

转换过程例子如下:

$F(u) = ( x(u), y(u), z(u), w(u) ) => f(u) = ( x(u) / w(u), y(u) / w(u), z(u) / w(u) )$

$$
\begin{aligned}
&x=f(u)=a u^{2}+b u+c \
&y=g(u)=p u^{2}+q u+r
\end{aligned}
$$

消去 $u$ 后得到

$$
x=a\left[\frac{p(x-c)-a(y-r)}{b p-a q}\right]^{2}+b\left[\frac{p(x-c)-a(y-r)}{b p-a q}\right]+c
$$
即

$$
A x^{2}-2 B x y+C y^{2}+D x+E y+F=0
$$

并不是所有的曲线都可以表示为上面 2 种形式:

Uniformization Theorems: there exists curves which do not have any polynomial or rational parametric forms(e.g., the elliptic curve $y^2 = x^3 + ax + c$).