# Computer Aided Geometric Design

## Algorithmic Geometry

Winter Semester 2016/17
Prof. Dr. Hans Hagen
Benjamin Karer M.Sc.
Alina Freund M.Sc.

# 0 - Organization

### People

#### Lecturer

• Prof. Dr. Hans Hagen
• 36-226
• hagen@cs.uni-kl.de

#### Assistant

• Benjamin Karer M.Sc.
• 36-218
• karer@rhrk.uni-kl.de

#### Assistant

• Alina Freund M.Sc.
• 36-218
• freund@rhrk.uni-kl.de

### Places and Dates

• lecture and exercise: 36-265
• Wednesdays 10:00 - 11:30 and Fridays, 11:45 - 13:15
• roughly every fourth appointment is an exercise
• presentations of practical exercises on appointment
• questions are answered by Benjamin Karer, either via email or in person on Mondays from 14:00 - 16:00 or on appointment
• materials and exercises are available at gfx.uni-kl.de/~alggeom

### Exercise Organization

• exercise sheets are made available on the lecture homepage
• roughly two weeks of time until due
• theoretical part: to be submitted in the last lecture before the next exercise
• practical part: to be presented on appointment
• paper talks:
• papers are handed out in December, talks are in the end of January
• paper discussion: approx. 2 pages including pictures
• talk: 12 minutes maximum, followed by about five to eight minutes discussion

• every exercise has to be submitted
• they do not have to be completely correct though – show how you came to your solution!
• submission of a two-page discussion/review of a scientific article on current research in the field and presentation of the results in a 12-minute talk

### Literature

• G. Farin. Curves and Surfaces for CAGD. Academic Press. 1992
• J. Hoschek, and D. Lasser. Fundamentals of CAGD. A K Peters Ltd. 1993
• G. Farin. NURBS for Curve and Surface Design from Projective Geometry. 2nd Edition. A K Peters. 1999

# 1 - Motivation

### Class A Surfaces

#### Definition: Class A Surface

A class A surface is a surface with smooth transitions in the surface curvature's rate of change ($G^3$-continuous) that additionally meets designers' requirements to aesthetics.

#### Remarks:

• visible and touchable design surfaces
• $G^3$ – smooth reflection lines
• design aesthetics
• modelling simplicity

### Class B

#### Class B Surfaces

• usually not directly visible
• design dominated by functionality rather than aesthetics
• examples
• inner sides of class A surfaces
• surfaces generating the object's primary structure
• surfaces used for the connection of parts

### Class C

#### Class C Surfaces

• purely functional
• not visible
• examples:
• surfaces of forming tools
• intermediate steps in manufacturing
• seat mounting in cars

### Designing Class A Surfaces

#### Step 1: Reverse Engineering a Clay Model

• Input: Clay model from styling and CAS after the choice of concept has been decided on
• 3d scan provides point cloud
• approximation algorithm fits surface through point cloud
• challenges: tolerance for approximation, noise, imperfections in clay model
• Output: Surface

### Designing Class A Surfaces

#### Step 2: Optimization and Transformation

• Input: Surface from 3d scan of clay model
• optimize the control structure towards $G^3$ continuity
• challenges: preserve control structure topology, boundary fitting for segments
• Output: refined Surface as Bézier-, B-Spline- or NURBS surface

### Designing Class A Surfaces

#### Step 3: Surface Manipulation and Testing

• Input: Control net for Bézier-, B-Spline- or NURBS Surface
• manual design refinement
• possibility to print the result using a 3d printer to test the model
• if the printed model does not achieve the design goals: go back to Step 1
• Output: class A surface for serial production

### Scope of the Lecture

Generating and manipulating (designing) curves and surfaces:

• Algorithms
• Data Structures
• Design Tools (interaction techniques for modelling)
• Quality Assessment

# 2 – Parametric Curves and Surfaces

### Functions and Graphs

#### Definition: Function

A function $f$ is a relation $D \rightarrow R$ between two sets that maps each element of the domain $D$ to exactly one element of the range $R$.

#### Definition: Graph of a Function

The graph of a function $f$ is the collection of all ordered pairs $(x, f(x))$ where $f: D \rightarrow R$, $x \in D$ and $f(x) \in R$.

### Curves

#### Definition: Curve

A curve is a continuous function $c: I \rightarrow S$ from a parameter interval $I$ into a space $S$ with the condition that there is a total ordering on the elements of $I$. If $S$ is the Euclidean plane, the curve is also called a plane curve, if it is the three dimensional Eulidean space, $c$ is a space curve.

#### Remarks:

1. typical choice: $I \subseteq \mathbb{R}$
2. $c$ continuous $\nLeftrightarrow$ $c$ differentiable
3. graphs of functions are special cases of curves

### Higher Dimensions

#### Definition: Parametric Surface

A parametric Surface is the image of a function $s: \mathbb{R}^2 \rightarrow \mathbb{R}^3$ from two-dimensional into three-dimensional Euclidean space. A surface that can be rotated into a representation where one of the coordinates is constant in every point on the surface by only using rotations is called a plane.

#### Remarks:

• $s$ is a plane $\Leftrightarrow$ the curvature vanishes in every point on $s$
• The definition can be directly extended to volumes and higher dimensions.

# 3 – Blending, Local vs. Global Support, Segments, and Splines

### Blending

#### Definition: Blending Function

Given a set of basis functions for some function space, the procedure of generating a new function as the linear combination of the basis functions is called blending. The basis functions therefore are also called blending functions.

#### Properties

• blending functions form a basis for a function space – every function of this space can be created by blending
• Let $S$ be a set of support points that impose constraints on the target function.
Then, the blending is determined by:
• the evaluation of basis functions at support points
• the intervals over which each basis function is evaluated

#### An Example

Curve $c(t)$ with support points $\lbrace P_1, \dots, P_n \rbrace$: $c_{i,d}(t) = (1 - t)c_{i,(d-1)}(t) + t c_{j,(d-1)}(t) \\ c_{i,1}(t) = (1 - t) P_i + t P_j$

### Local Support with Segments and Splines

#### Blending with Segments:

• + local support
• + clear bounds of influence
• Either continuity is lost in higher derivatives or complex boundary conditions have to be met at the connections
interaktive Grafik mit festen Segmenten und verstellbaren Punkten (Verdeutlichung Vor- und Nachteile)

### Overlapping Segments

• alternative to continuitiy constraints: overlapping intervals
• let the segments overlap and blend the functions for each segment containing the current support interval
• + overlap guarantees continuity
• wider region of influence for each support point

# 4 – Continuity and Smoothness

### Curvature and Torsion

#### Concept: Curvature

The curvature $\kappa$ measures the deviation of a curve from the straight line. For a curve $c(t)$ with tangent vector $T(t)$, we have: $\kappa(t) = \frac{\Vert \lbrack T(t), \dot{T}(t) \rbrack \Vert}{\Vert T(t) \Vert^3}$

#### Concept: Torsion

The torsion $\tau$ of a curve measures the deviation of a space curve from the plane. For a curve $c(t)$ with tangent $T(t)$, we have: $\tau(t) = \frac{\det (T(t), \dot{T}(t), \ddot{T}(t))}{\Vert \lbrack T(t), \dot{T}(t) \rbrack \Vert^2}$

### Repetition: Continuity of Functions

#### Definition: Continuitiy of a Function

A function $f(x)$ is continuous at $x_0$ if for the right side limit and the left side limit approaching $x_0$, $f(x)$ approaches the same value, i.e. $\lim_{x \to x_0}^\rightarrow f(x) = \lim_{x \to x_0}^\leftarrow f(x)$. The function is called continuous if it is continuous for all $x_0$.

#### Definition: Differentiablibity of a Function

A function $f(x)$ is differentiable at $x_0$ if the limit $\lim_{h \to 0}\tfrac{f(x + h) - f(x)}{h}$ exists and differentiable if this limit exists for all $x_0$.

A function $f(x)$ is continuously differentiable if this limit exists and is equal for the forwards and the backwards difference qoutient, i.e. if $\lim_{h \to 0} \tfrac{f(x) - f(x - h)}{h} = \lim_{h \to 0} \tfrac{f(x + h) - f(x)}{h}$.

#### Remarks:

• these definitions directly generalize to functions in multiple variables
• Differentiating a function over the whole domain yields the derivative
• A function is $k$ times continuouly differentiable if the function itself and its first $k-1$ derivatives are continuously differentiable

### (Parametric) Continuity of Curves

#### Definition: $C^k$-Continuity

A curve $c(t)$ is $C^k$-continuous in $t$ if at least its first $k$ derivatives $\tfrac{d^kc}{dt^k}$ are continuous throughout the curve.

### Geometrically Continuous Contact of Surfaces

#### Definition: $G^k$-Continuity of Surfaces

Let $s_1$ and $s_2$ be two parametric surfaces sharing a common point $P$. The contact of $s_1$ and $s_2$ is $G^k$-continuous in $P$ iff. for all directions their partial derivatives with respect to the same direction are identical up to order $k$.

### $G^2$-continuous Contact

#### Mean curvature Criterion:

Let $s_1$ and $s_2$ be two surfaces that share a common boundary $b$ and let the contact of $s_1$ and $s_2$ be $G^1$-continuous at every point along $b$, i.e. the surfaces share the same tangent planes along $b$. Then, the contact of $s_1$ and $s_2$ is $G^2$-continuous along $b$ iff. the mean curvatures of $s_1$ and $s_2$ are identical along $b$.

#### $G^3$-continous Contact

If, additionally, the rate of change of the normal curvatures is equal at the contact boundary of two surfaces, the contact is $G^3$-continuous.

### Reflection Lines

#### Concept: Reflection Lines

Reflection lines reveal discontinuities in surface tangents and normals.

#### Reflection Lines for Curvature Smoothing Towards $G^3$-Continuity

• $G^0$-contact: sharp edges between surfaces
• $G^1$-contact: surfaces tangent-continuous, reflection lines are $C^0$ buckling at the connections
• $G^2$-contact: surfaces curvature-continuous, reflection lines are $C^1$, i.e. tangents transition smoothly
• $G^3$-contact: surfaces continuous in the change of curvature, reflection lines are $C^2$, i.e. normals transition smoothly

# 5 – Some Fundamentals of Grids and Meshes

### Grids

• problem: space and objects continuous but computer can only store discrete data
• idea: approximate using a grid and interpolation:
• need: exact points in space (vertices) and their neighborhood relations (edges, faces)
• one face bounded entirely by edges connected by vertices – cells
• combine cells to form the grid

#### Types of grids

• structured vs. unstructured
• hierarchy
• order
• face-shape (triangular, quadrilateral, irregular, ...)

### Meshes

#### Definition: Polygon Mesh

A polygon mesh is a grid that generates the surface of an object.

#### Definition: Volumetric Mesh

A volumetric mesh is a grid that that generates the three-dimensional geometric structure of an object

### Data Structures for Meshes

#### Requirements

• capture topology and geometry
• efficient access
• small size

#### Special Cases

• Structured grid: store neighborhood implicitly by ordering the vertices properly
• uniform shape: each face has the same number od edges and/or vertices
• triangulations: three edges uniquely define a triangle and the triangle uniquely defines these three edges

#### Node List

• stores vertices and neighbors in an array
• egdes: two neighboring vertices (by indices)
• face: minimum simple path of nodes (by indices)
• no next or previous element

#### Edge List

• stores vertices in list
• edges: list of tuples two vertex indices and two face indices
• face: minimum closed sequence of edges (by index in egde list)
• previous/next edges implicity given by polygons

#### Winged Edge

• idea: use edges to describe geometry, topology, and orientation
• stores edges with pointers to:
• start/end vertex
• left/right face
• previous/next edges
• mesh traversal by the edges
• good for subdivision, deformations (e.g. extrusion)

$V = \lbrace v_1, v_2, v_3, ... \rbrace;$

forwards backwards
# $v_{start}$ $v_{end}$ prev next prev next
1 1 2 3 4 5 6
2 2 3 8 9 7 1
... ... ... ... ... ... ...

#### Half Edge

• idea: interpret each edge as a pair of directed (half) edges to clearly separate the cells
• stores edges with pointers to:
• start vertex
• one face
• previous/next edges sharing same face
• twin edge (the other half, part of the neighbor face)
• mesh traversal by the faces
• good for subdivision, mesh simplification, cutting, glueing

$V = \lbrace v_1, v_2, v_3, ... \rbrace;$

# $v_{start}$ $v_{end}$ prev next twin
1 1 2 3 4 2
2 2 1 5 6 1
3 3 1 7 1 4
... ... ... ... ... ...

#### Data Structures for the GPU

• meshes are passed per face; single primitives or interleaved structure
• most common: triangle strip
• examples from OpenGL:

### Grids and Implicit Surface Functions

• implicit surface: isocontour in some function:
$S(x_0, x_1, \dots) = c$ for some constant (vector) $c$
• arbitrarily exact but finding the isocontour typically involves traversing large portions of parameter space (cf. level set methods)
• boolean operations are easily translated to the functions – good for CSG

# 6 – Computing Tangents and Normals

### Tangent to a Curve

#### Algorithm: Two-point Methods for Curve Tangents Involving $c(t)$

Let $c: \mathbb{R} \rightarrow \mathbb{R}^n$ be a curve in one parameter $t$. Given the piecewise linear approximation, we can compute an approximate tangent $T(t) = \dot c (t)$ using one of the following two one-point methods:

1. forwards: $T_f(t) = \frac{c(t+\Delta t) - c(t)}{\Delta t}$
2. backwards: $T_b(t) = \frac{c(t) - c(t-\Delta t)}{\Delta t}$

#### Algorithm: Symmetric Difference Quotient

Let $c: \mathbb{R} \rightarrow \mathbb{R}^n$ be a curve in one parameter $t$. Given the piecewise linear approximation, we can compute an approximate tangent $T(t) = \dot c (t)$ using the following two-point method: $T(t) = \frac{1}{2} \left( T_f(t) + T_b(t) \right) \\ = \frac{c(t + \Delta t) - c(t - \Delta t)}{2 \Delta t}$

### Normal to a Curve

#### Algorithm: Normal to a Curve

A naive approach to computing normals to a curve is to apply the property that the normal points into the direction of the change of tangents in $c(t)$: $N(t) = \left( c(t) + T_f(t) \right) - \left( c(t) + T_b(T) \right) \\ = c(t + \Delta t) - c(t - \Delta t) + 2 c(t)$

### Tangents and Normals on Surfaces

Estimate the Jacobian $J = \begin{bmatrix} \tfrac{df_x}{du} & \tfrac{df_x}{dv} \\ \tfrac{df_y}{du} & \tfrac{df_y}{dv} \\ \tfrac{df_z}{du} & \tfrac{df_z}{dv} \end{bmatrix}$ computing the difference quotient for the "parameter matrix" $M = \begin{bmatrix} f(u-d, v-d) & f(u, v-d) & f(u+d, v-d) \\ f(u-d, v) & f(u, v)=P & f(u+d, v) \\ f(u-d, v+d) & f(u, v+d) & f(u+d, v+d) \end{bmatrix}$

1. For each of the eight points in $M$ surrounding $P$, compute the connection and the average difference quotients in $x$, $y$, and $z$, respectively to obtain the Jacobian
2. Every point $P'(u', v') = P(u, v) + J * ((u', v') - (u, v))$ is in the tagnent plane in $P$ – two of these points together with $P$ span the tangent plane and yield the normal