Loading...

Computer Aided Geometric Design

Algorithmic Geometry

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

Content

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

Exam Admission

  • 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

Example Applications

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
  • additional requirements:
    • design aesthetics
    • modelling simplicity

nice looks

examples:

  • all control points of a control net on the same side of the surface
  • smooth transition of design edges into surface

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

Part A

Foundational Geometric Considerations

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

$f_i(x_j) = \delta_{ij} f_i(x_i)$, i.e. for every function, there is only one support point where it does not evaluate to zero.

  • only one interval – global support
  • strictly separate intervals (touching only at their begins and ends) – local support by segments or splines
  • overlapping intervals: smooth transitions but wider influence when changing the support points

$t \in \lbrack 0, 1 \rbrack$ and the point indices range from $1$ to $n$.

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 \]

Global Support

Local Support with Segments and Splines

Problems with continuity

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 Curves

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.

A regular curve is a parametric curve where the tangent never vanishes. A parametric surface is a regular surface, if it is defined in two parameters for which these parameters are linearly independent in every point on the surface. Intuitively, this means a parametric surface is regular if its parameterization's derivatives with respect to the isoparameter directions (surface coordinate lines) span a tangent plane in every point on the surface.

Not pointing into the direction of the curve.

Reflection Lines

Concept: Reflection Lines

Reflection lines reveal discontinuities in surface tangents and normals.

A popular model for the local illumination of points on a surface. It models reflection of light in a point as a convex combination of three components, specular, diffuse, and ambient. The specular component determines the shiny reflection from light sources, the diffuse component captures the scattered light from the surrounding objects, and the ambient component adds a minimum intensity to capture environmental light that is not exlicitly modelled as a light source.

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
... ... ... ... ... ...

All operations are performed on the edges. In fact, the faces do not even need to be stored explicitly if they do not contain additional relevant information. However, since one edge belongs to exactly one face, using the twin and next/previous pointers can be interpreted as traversing the faces.

Data Structures for the GPU

  • shaders only process on single elements – usually no (direct) access to memory
  • meshes are passed per face; single primitives or interleaved structure
  • most common: triangle strip
  • examples from OpenGL:
    GL_TRIANGLES, GL_QUADS, GL_TRIANGLE_FAN, GL_TRIANGLE_STRIP

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

The set operations implied by the arithmetic operations on functions are not smooth. Therefore, one needs to introduce an additional blending function to merge the two objects smoothly. Two examples for such blending functions are metaballs and superelliptical blending. These blending needs to operate on the kernels and to achieve the desired $C^k$-continuity for $k>1$ they have to be nonlinear. Threfore, their evaluation is comparably expensive and can become infeasible for complex structures.

Constructive Solid Geometry. Complex geometric objects are modelled by applying boolean operators (intersection, merging, ...) to more primitive objects.

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