zhengtongdu
Zhengtong's blog
learn&record&share

GAMES101_notes_03

GAMES101: 现代计算机图形学入门

笔记03：Geometry

Lesson 10 Geometry 1(Introduction)

本讲内容

  • Shading 3
    • Applications of textures(写在第九讲笔记最后)
  • Introduction to geometry
    • Examples of geometry
    • Various representations of geometry

Introduction to geometry

Many Ways to Represent Geometry

几何的显式表示和隐式表示

  • Implicit
    • algebraic surface
    • level sets
    • distance functions
    • …
  • Explicit
    • point cloud
    • polygon mesh
    • subdivision, NURBS
    • …

Each choice best suited to a different task/type of geometry

“Implicit” Representations of Geometry

  • Based on classifying points
    • Point satisfy some specified relationship
  • Sampling can be hard
  • Inside/Outside tests is easy

“Explicit” Representations of Geometry

  • All points are given directly or via parameter mapping
  • Sampling is easy
  • Inside/Outside Test Hard

Conclusion: Bset representation depends on the task.

More Implicit representations in Computer Graphics

  • Algebraic Surfaces
    • 非常不直观，且无法处理复杂几何结构
  • Constructive Solid Geometry(CSG)
    • 通过对简单几何体进行布尔运算
    • 可以得到复杂几何结构的表示
  • Distance Functions
    • Instead of Booleans, gradually blend surfaces together using Distance functions:
    • Giving minimum distance(could be signed distance) from anywhere to object
  • Level Set Method
    • Closed-form equation are hard to describe complex shapes
    • Alternative: store a grid of values approximating function
    • Surface is found where interpolated values equal zero
    • Provides such more explicit control over shape(like a texture)
  • Fractals 分形
    • Exhibit self-similarity, detail at all scales
    • “Language” for describing natural phenomena
    • Hard to control shape

Implicit Representations - Pros & Cons

  • Pros:
    • compact description(e.g., a function)
    • certain queries easy(inside object, distance to surface)
    • good for ray-to-surface intersection(more later)
    • for simple shapes, exact description / no sampling error
    • easy to handle changes in topology(e.g., fluid)
  • Cons:
    • difficult ot model complex shapes

Explicit Representations in Computer Graphics(later)

Lesson 11 Geometry 2(Curves and Surfaces)

本讲内容：

  • Explicit Representations
  • Curves
    • Bezier curves
    • De Casteljau’s Algorithm
    • B-splines, etc.
  • Surfaces
    • Bezier surfaces
    • Triangles & quads
      • Subdivision, simplification, regularization

Explicit Representations in Computer Graphics

Many Explicit Representations in Graphics

  • triangle meshes
  • Bezier surfaces
  • subdivision surfaces
  • NURBS
  • point cloud
  • …

Point Cloud

  • Easiest representation: list of points $(x, y, z)$
  • Easily represent any kind any kind of geometry
  • Useful for LARGE datasets(»1 point/pixel)
  • Often converted into polygon mesh
  • Difficult to draw in undersampled regions

Polygon Mesh

  • Store vertices & polygons(often triangles or quads)
  • Easier to do processing/simulation, adaptive sampling
  • More complicated data structures
  • Perhaps most common representation in graphics

The wavefront Object File(.obj) Format

常用的文件存储格式（obj文件）

  • Commonly used in Graphics research
  • Just a text file that specifies vertices, normals, texture coordinates and their connectivities

Curves

Bezier Curve

Defining Cubic Bezier Curve With Tangents

  • 由四个点$p_0, p_1, p_2, p_3$定义的Bezier曲线，满足曲线的起始点为$p_0$，终点为$p_3$，且$p_0$处切线为$\overline{p_0, p_1}$，$p_3$处切线为$\overline{p_2, p_3}$。

Evaluating Bezier Curves(de Casteljau Algorithm)

  • 并不是直接得到曲线的表示，而是当假设初始点对应时刻0，结束点对应时刻1，则对于任意时刻$t\in [0, 1]$都可以直接求出该时刻的曲线对应位置（利用插值）。

Evaluating Bezier Curves Algebraic Formula

  • de Casteljau algorithm gives a pyramid of coefficients
  • Bernstein form of a Bezier curve of order n:
\[\mathbf{b}^n(t) = \mathbf{b}_0^n(t) = \sum_{j = 0}^n\mathbf{b}_jB_j^n(t),\]

where Bernstein polynomial is

\[B_i^n(t) = \begin{pmatrix} n \\ i \end{pmatrix} t^i(1-t)^{n-i}\]

Properties of Bezier Curves:

  • Interpolates endpoints
    • For cubic Bezier: $\mathbf{b}(0) = \mathbf{b}_0; \mathbf{b}(1) = \mathbf{b}_3$
  • Tangent to end segment
    • Cubic case: $\mathbf{b}’(0) = 3(\mathbf{b}_1 - \mathbf{b}_0); \mathbf{b}’(1) = 3(\mathbf{b}_3 - \mathbf{b}_2)$
  • Affine transformation property
    • Transform curve by transforming control points
  • Convex hull property
    • Curve is within convex hull of control points

Piecewise Bezier Curves

  • 当控制点数量过多的时候，贝塞尔曲线不能很好刻画控制点的分布情况
  • Therefore, piecewise cubic Bezier curve is the most common technique

Piecewise Bezier Curve - Continuity

  • $C^0$ continuity
  • $C^1$ continuity

Other types of splines

  • Spline
    • a continuous curve constructed so as to pass through a given set of points and have a certain number of continuous derivatives
    • In short, a curve under control
  • B-Splines
    • Short for basis splines
    • Require more information than Bezier curves
    • Satisfy all important properties that Bezier curves have(i.e. superset)

Surfaces

Bezier Surfaces

Extend Bezier curves to surfaces

Evaluating Surface Position For Parameters $(u, v)$

  • For bi-cubic Bezier surface patch,
    • Input: $4\times 4$ control points
    • Output: a 2D surface parameterized by $(u, v)$ in $[0, 1]^2$

Method: Separable 1D de Casteljau Algorithm

  • Use de Casteljau to evaluate point u on each of the 4 Bezier curves in $u$. This gives 4 control points for the “moving” Bezier curve
  • Use 1D de Casteljau to evaluate point $v$ on the “moving” curve

Subdivision surfaces(triangles & quads)

Mesh Operations: Geometry Processing

  • Mesh subdivision 网格细分
  • Mesh simplification 网格简化
  • Mesh regularization 网格正规化

Lecture 12 Geometry 3

Mesh Operations

  • Mesh subdivision : Increase resolution
  • Mesh simplification : Decrease resolution; try to preserve shape/appearance
  • Mesh regularization : Modify sample distribution to improve quality

Subdivision

Loop Subdivision

  • Common subdivision rul for triangle meshes.

First, create more triangles(vertices); Second, tune their positions

  • Split each triangle into four
  • Assign new vertex positions according to weights
    • New/old vertices updated differently

更新规则

  • 对于待更新的新顶点，利用共享其所在边的三角形上原顶点进行加权平均，得到新顶点的坐标
  • 对于待更新的原顶点，其结果为自身位置与相邻原顶点位置加权得到结果

Catmull-Clark Subdivision(General Mesh)

  • 可以对非三角形网格进行细分

定义四边形面为 quad face，其余面为 non-quad face，记度数不为4的顶点为extraordinary vertex(奇异点)

Each subdivision step:

  • Add vertex in each face
  • Add midpoint on each edge
  • Connect all new vertices

After one subdivision:

  • How many extraordinary vertices? 原本的奇异点加上非四边形面中添加的点
  • What are their degrees? 非四边形面的边数
  • How many non-quad faces? 0

相当于将非四边形面全部用奇异点替换了，再做细分的时候，非四边形面数量仍然是0，而且奇异点数量不会增加。

Catmull-Clark Vertex Updates Rules(Quad Mesh)

  • 新增加的点，根据面中的点和边上的点，利用相邻的点进行加权平均；
  • 原有的点，利用周围新添加的点及其本身，进行加权平均。

Mesh Simplification

Goal: reduce number of mesh elements while maintaining the overall shape

Collapsing An Edge 边坍缩

  • Suppose we simplify a mesh using edge collapsing

Quadric Error Metrics 用来选择需要坍缩的边

  • How much geometric error is introduced by simplification?
  • Not a good idea to perform local averaging of vertices
  • Quadric error: New vertex should minimize its sum of square distance($L_2$ distance) to previous related triangle planes

Quadric Error of Edge Collapse

  • How much does it cost to collapse an edge?
  • Idea: Compute edge midpoint, measure quadric error

Simplification via Quadric Error

  • Iteratively collapse edges
  • Which edges? Assign score with quadric error metric
    • Approximate distance to surface as sum of distances to planes containing triangles
    • Iteratively collapse edge with smallest score
    • Greedy algorithm… great results!

Shadows Mapping(with Rasterization)

Shadow

  • How to draw shadows using rasterization?
  • Shadow mapping!

Shadow Mapping（只涉及点光源的硬阴影）

  • An Image-space Algorithm
    • no knowledge of scene’s geometry during shadow computation
    • must deal with aliasing artifacts
  • Key idea:
    • thepoins NOT in shadow must be seen both by the light and by the camera

具体实现方法：

  • Pass 1: Render from Light 记录光源按不同方向到场景得到的深度
    • Deep image from light source
  • Pass 2A: Render from Eye 确定从摄像机得到的场景中的具体像素
    • Standard image(with depth) from eye
  • Pass 2B: Project to light 从这些像素投影回光源，与之前对照的深度相比查看是否一致
    • Project visible points in eye view back to light source

Problems with shadow maps

  • Hard shadows(point lights only)
  • Quality depends on shadow map resolution(general problem with image-based techniques)
  • Involves equality comparison of floating point depth values means issues of scale, bias, tolerance

Hard shadows vs. soft shadows

  • 当阴影位置完全得不到光照，则该点处在本影区域，阴影是最硬的；否则阴影位置可以被部分光照，此时该点位于半影区域，阴影会比较软。

Table of Contents