Geometric Models

Christoph Garth
Scientific Visualization Lab
Motivation
 Geometric models enable processing (e. g. rendering) of 3-dimensional models
using computers.

In computer graphics, different types of approximations are used in order to

represent objects.
Computer Graphics – Geometric Models – Motivation 8–1
 In general, it is assumed that objects are hollow and can be characterized by an
approximation of their bounding surface.

→ boundary representation (b-rep)

In most cases, this allows objects to be rendered (e.g. using ray tracing).

Typical surface representations:

• polygonal meshes
• implicit surfaces
• parametric surfaces

Computer Graphics – Geometric Models – Motivation 8–2

Polygonal Meshes
 Polygons (see also Chapter 2)

• Vertices (sgl. vertex) are points in R2 or R3

• Determined by (x, y, z)-coordinates

• Vertices are pairwise connected by edges

• Determined by the coordinates of the start and end vertices

• A polygon is the inner part of a connected and closed line of edges

• The edges do not intersect
• Exactly two edges meet in every vertex
• (In R3 all the points lie in one plane)

Common notation (“polygon chain” or “polyline”):

P = (p1 , . . . , pn ) → E = {(p1 , p2 ), (p2 , p3 ), . . . , (pn−1 , pn ), (pn , p1 )}

Computer Graphics – Geometric Models – Polygonal Meshes 8–3

 Illustration: Polygons

triangle pentagon hexagon

quadrilateral
convex

concave
heptagon octagon nonagon decagon

regular polygons

This is more formally covered in the Computational Geometry course.

Computer Graphics – Geometric Models – Polygonal Meshes 8–4

 Polygonal mesh
• Boundary representation consists of polygons (faces)

Often called surface mesh.

Objects are modeled as polyhedrons.

(Polyhedron: A body bounded by planes.)

Computer Graphics – Geometric Models – Polygonal Meshes 8–5

 Typical surface meshes: triangule and quad meshes

Computer Graphics – Geometric Models – Polygonal Meshes 8–6

 Manifold Mesh: A mesh is manifold if the intersection of two polygons is either empty, a
common vertex or a common line.

This property is required by many algorithms.

(This can often be worked around, at much additional expense.)

not allowed:
not allowed:
overlapping faces
allowed T-vertex

Computer Graphics – Geometric Models – Polygonal Meshes 8–7

Polygonal Meshes as Graphs
 A graph is a tuple (V, E), where

• V is the set of all vertices

• E is the set of all edges

A planar graph is a graph which vertices can be position on a plane such that no edges
intersect.

non planar planar

Computer Graphics – Geometric Models – Polygonal Meshes as Graphs 8–8

 A connected planar graph is a 2-tuple (V, E)

• V: set of vertices
• E: set of edges
• For each pair of vertices, there exists a path which connects these two vertices.
• F: set of faces
• Continuous areas of the plane that are bounded by a closed polyline.

A triangulation is a graph in which every face is a triangle.

Computer Graphics – Geometric Models – Polygonal Meshes as Graphs 8–9

 For planar graphs the Euler formula holds:

|V| − |E| + |F| = 2

Note: The surrounding area is counted as face too.

Each convex polyhedron can be transformed into a connected planar graph.

• The Euler formula holds for surfaces of convex polyhedra.

For arbitrary polyhedra:

|V| − |E| + |F| = χ
where χ is the so-called Euler characteristic.

Computer Graphics – Geometric Models – Polygonal Meshes as Graphs 8–10

 The genus of a polyhedron is the maximum number of cuts along non-self intersecting
closed curves that do not split the graph into multiple connected components.

Intuitively: Number of "holes" (handles)

genus 0 genus 1 genus 2 genus 3

More details → Computational Topology course

Computer Graphics – Geometric Models – Polygonal Meshes as Graphs 8–11

 Euler-Poincaré formula: For an orientable, closed polygonal mesh with genus g, the
number of vertices V, edges E and faces f fulfills the following equation

V − E + F = 2 − 2g

The number χ := 2 − 2g is called Euler characteristic

χ=2 χ=0 χ = −2 χ = −4

Computer Graphics – Geometric Models – Polygonal Meshes as Graphs 8–12

 Example:

V = 3890
E = 11664
F = 7776

genus 0, χ = 2

Computer Graphics – Geometric Models – Polygonal Meshes as Graphs 8–13

 Example: “knot”

genus 1, χ = 0

Computer Graphics – Geometric Models – Polygonal Meshes as Graphs 8–14

 Interpreting polygonal meshes as graphs allows the application of graph
algorithms and graph-theoretic insights:

Examples:
• Shortest edge path between two vertices
• Is there a path that visits every node exactly once?
• How many edges can be contained in a triangular mesh with V vertices?

3F ≈ 2E ⇒ E ≈ 3V, F ≈ 2V

2V − 2E + 2F = 2χ ⇒ 2V = F − 2χ ≈ F ⇒ V : F : E ≈ 1 : 2 : 3
• What is the average valence (number of neighbors) of the vertices in a
• triangular mesh? ⇒ < 6
• quad mesh? ⇒ < 4

Computer Graphics – Geometric Models – Polygonal Meshes as Graphs 8–15

Polygonal Approximation
 A polygonal approximation is an approximation of a continuous surface with a polygonal
mesh.

Example: Approximation of a curve

Example: approximation of a sphere

Computer Graphics – Geometric Models – Polygonal Approximation 8–16

 Typically, a polygonal approximation consists of a discrete set of points of the
continuous surface, which are connected by edges.

Construction of such connectivity (determining the edges) from a given set of surface
points is called triangulation (quadrangulation,. . . ).

Computer Graphics – Geometric Models – Polygonal Approximation 8–17

 Properties of polygonal mesh approximations:

• For piecewise linear approximations, the maximum distance between the continuous
surface and the approximation with decreasing maximal edge length h is in O(h2 )

3 6 12 24

25% 6.5% 1.7% 0.4%

The error decreases as the amount of interpolation points increases.

O(h2 ): if h is halved then the error decreases by a factor of 4.

Computer Graphics – Geometric Models – Polygonal Approximation 8–18

 Often, polygonal approximation is used adaptively: A larger amount of polygons is used
in places where the curvature (2nd derivative) is large.

few vertices / polygons in “flat” areas, more in “curved” areas

approximation error can be reduced while retaining a small number of polygons.
Computer Graphics – Geometric Models – Polygonal Approximation 8–19
 Example: polygonal/polyhedral approximation

Computer Graphics – Geometric Models – Polygonal Approximation 8–20

Data Structures for Polygonal Meshes
 There are multiple data structures for polygonal meshes that offer different compromises
between runtime complexity and memory requirements.

Typical algorithms for polygonal meshes:

• Computation of normal vectors

• Removing measurement and sampling errors by smoothing
• Refining meshes for more detailed models
• Thinning / coarsening meshes (e. g. compression)
• Constructive Solid Geometry (set operations on polyhedra)
• ...

Some of these algorithms need only very little information about the mesh, while others
can benefit enormously from additional information.
Computer Graphics – Geometric Models – Data Structures for Polygonal Meshes 8–21
 At the very least, a mesh data structure describe

• geometry: position of the vertices (always)

and at least one of these alternatives:

• Explicit representation of polygons

• (polygon) topology: connection between vertices and edges
• (mesh) topology: connection between edges and polygons

Information that is not given can be reconstructed (at some computational cost) from the
given information, for example, mesh topology from polygon topology.

Computer Graphics – Geometric Models – Data Structures for Polygonal Meshes 8–22
 Example: Computation of vertex neighborhoods

• The n-ring of a vertex v is the set of vertices that are connected to v via a path of
edges of length n or less.
• The valence of a vertex is the number of incident edges (= neighbors in the the
1-ring)

v v

1-ring 2-ring

Computer Graphics – Geometric Models – Data Structures for Polygonal Meshes 8–23
 Explicit representation for triangular meshes (face set)

• Three vertices with x, y, z coordinates for each of n triangles

n × 3 × 3 = 9n floats (4 bytes/float)
• High redundancy
• 36 bytes/face ≈ 72 bytes/vertex
• Topology/connectivity not represented explicitly, thus often called “triangle soup”

t vi vj vk
Data format: e. g. 0 ( 1.0, 1.0, 1.0) (-1.0, 1.0,-1.0) ( 1.0, 1.0, 1.0)
STL (STere- 1 ( 1.0, 1.0, 1.0) (-1.0,-1.0, 1.0) ( 1.0,-1.0,-1.0)
oLithography) 2 ( 1.0, 1.0, 1.0) ( 1.0,-1.0, 1.0) (-1.0, 1.0,-1.0)
3 (1.0,-1.0,-1.0) (-1.0,-1.0, 1.0) (-1.0, 1.0,-1.0)

Computer Graphics – Geometric Models – Data Structures for Polygonal Meshes 8–24
 Example: STL file

1 solid name
2 facet normal n_i n_j n_k normal vector
3 outer loop
4 vertex v1_x v1_y v1_z
5 vertex v2_x v2_y v2_z
6 vertex v3_x v3_y v3_z
7 end loop
8 end facet
9 ...

Computer Graphics – Geometric Models – Data Structures for Polygonal Meshes 8–25
 Shared Vertex Representation / Indexed Face Set

• Array of coordinates for all vertices (geometry, 3 × n floats)

• Array of triangles stores indices of its corners in the vertex
list (3 × n integer, 4 bytes/integer)
• 12 bytes/vertex + 12 bytes/face ≈ 36 bytes/vertex
• Data formats: OBJ, OFF

v x y z t i j k
0 1.0 1.0 1.0 0 0 1 2
1 -1.0 1.0 -1.0 1 0 2 3
2 -1.0 -1.0 1.0 2 0 3 1
3 1.0 -1.0 1.0 3 3 2 1

vertex array triangle array

Computer Graphics – Geometric Models – Data Structures for Polygonal Meshes 8–26
 Discussion: Shared Vertex Representation/Indexed Face Set

• Less redundancy than explicit representation

• Separation of geometry and (polygon) topology
• Many operations are costly, e. g. 1-neighborhoods

Example: OBJ file format (“object file”, implicit numbering of vertices and faces):

1 # List of geometric vertices with (x,y,z)

2 v 0.123 0.234 0.345 # vertex 1
3 v 1.234 2.345 3.456 # vertex 2
4 # Polygonal face elements
5 f 1 2 3
6 f 3 4 5
7 f 6 3 7 Note: The file format is more potent, see
here)

Computer Graphics – Geometric Models – Data Structures for Polygonal Meshes 8–27
 Extended Shared Vertex Representation (also Face-Based Connectivity)

• Array of vertices: coordinates for each vertex and an index to one adjacent triangle:
3n floats + n integers
• Array of triangles: references to each three vertices and neighboring faces (adjacent
triangles, boundary neighbor indicated by −1): 6n integers
• 16 bytes/v + 24 bytes/f ≈ 64 bytes/v

v x y z l t i j k n0 n1 n2
0 1.0 1.0 1.0 0 0 0 1 2 3 1 2
1 -1.0 1.0 -1.0 0 1 0 2 3 3 2 0
2 -1.0 -1.0 1.0 0 2 0 3 1 3 0 1
3 1.0 -1.0 1.0 1 3 3 2 1 0 2 1
Note: here n stands for “neighbor” not “normal”

Computer Graphics – Geometric Models – Data Structures for Polygonal Meshes 8–28
 Edge-Based Connectivity/Winged Edge Data Structure (Baumgart, 1994)

One array for each (≈ 120 bytes/vertex):

• Edges (primary key):
VEND
• Start (VSTART) and end vertex (VEND)
• Two adjacent faces (FCW and FCCW)
EPCCW ENCW
• Previous and next edge in one face
(EPCW and ENCW)
• Previous and next edge in the other FCCW FCW
face (EPCCW and ENCCW)
• Vertices (key): ENCCW EPCW
• coordinates + one adjacent edge
• Faces (key): VSTART

• one adjacent edge

Computer Graphics – Geometric Models – Data Structures for Polygonal Meshes 8–29
 Example: (compute by yourself)

Computer Graphics – Geometric Models – Data Structures for Polygonal Meshes 8–30
 More specific data structures for minimal redundancy and memory efficient
representation by implicit topology:

• triangle/quad strips
• triangle fans

Complex meshes are partitioned into a set of strips and fans.

More common in the past (→ hardware).

Computer Graphics – Geometric Models – Data Structures for Polygonal Meshes 8–31
 Example: Triangle Strip Subdivision

Computer Graphics – Geometric Models – Data Structures for Polygonal Meshes 8–32
Rendering Polygonal Meshes
 During rendering or other operations, polygon meshes often have to be checked
for intersections with other primitives, e. g. in ray tracing.

Typical problems:

• Does a ray intersect with the polygon?

• Which face is hit?
• What is the angle between the ray and the surface?

Without further afo, each face has to be tested for intersection. Because of this,
acceleration structures are used (e. g. bounding volumes, cf. chapter 6)

Computer Graphics – Geometric Models – Rendering Polygonal Meshes 8–33

 Example: Ray-Triangle Intersection / Müller-Trumbore Algorithm

• Each point on the plane of a triangle can be expressed by a linear combination of

the corner points p0 , p1 , p2

p = p0 + β1 · (p1 − p0 ) + β2 · (p2 − p0 )
= (1 − β1 − β2 ) · p0 + β1 · p1 + β2 · p2
= β0 · p0 + β1 · p1 + β2 · p2

The weights βi are called barycentric coordinates

• By equating with the ray equation yields at 3 × 3 linear system

o + t · d = p0 + β1 · (p1 − p0 ) + β2 · (p2 − p0 )

• The point of intersection is inside the triangle if βi ≥ 0 ∀i.

Computer Graphics – Geometric Models – Rendering Polygonal Meshes 8–34

 Reminder: barycentric coordinates – ratios of triangle areas

p2

β0 = A 0 / A
β1 = A 1 / A
A0
A1 β2 = A2 / A

A2 p1
β0 + β1 + β2 = 1, βi ≥ 0

p0

Interpolation: f (p) = β0 f (p0 ) + β1 f (p1 ) + β2 f (p2 )

Computer Graphics – Geometric Models – Rendering Polygonal Meshes 8–35

 Pseudocode: Möller-Trumbore ray-triangle intersection

1 bool rayTriangleIntersect( 19 // compute 1st barycentric coord

2 vec3 o, vec3 d, 20 vec3 tvec = orig - v0;
3 vec3 p0, vec3 p1, vec3 p2, 21 b1 = dot( tvec, pvec ) * invDet;
4 float& t, float& b1, float& b2 22 if( b1 < 0 || b1 > 1 )
5 ) 23 return false;
6 { 24
7 vec3 v0v1 = v1 - v0; 25 // compute 2nd barycentric coord
8 vec3 v0v2 = v2 - v0; 26 vec3 qvec = cross( tvec, v0v1 );
9 vec3 pvec = cross( dir, v0v2 ); 27 b2 = dot(dir, qvec) * invDet;
10 float det = dot( v0v1, pvec ); 28 if (v < 0 || u + v > 1)
11 29 return false;
12 // ray and triangle are parallel 30
13 // if det is close to 0 31 // compute t
14 if( abs(det) < EPSILON ) 32 t = dot(v0v2, qvec) * invDet;
15 return false; 33
16 34 return true;
17 float invDet = 1 / det; 35 }

Computer Graphics – Geometric Models – Rendering Polygonal Meshes 8–36

 The angle with which a ray falls onto a surface depends on the orientation at the
intersection point. This is given by the surface normal, the unit vector orthogonal
to the local tangential plane.

Computer Graphics – Geometric Models – Rendering Polygonal Meshes 8–37

 The tangent plane at a point p on a surface is the plane in R3 that is spanned by
the tangential vectors of the surface at p.

For a plane, the normal vector is the

normal of the plane (cf. Hesse normal
form)

Computer Graphics – Geometric Models – Rendering Polygonal Meshes 8–38

 Computation of normal vectors at the vertices of a polygonal mesh:

• Per-polygon normals or face normal vectors can be directly computed as the plane
normal of the polygons
• Normal vectors at the vertices (per-vertex normals) can be computed, e. g. by
averaging of the face normals of the neighboring faces.
(In practice this is often unexpectedly difficult, since normals are defined only
modulo orientation)

k
P ~i
N
~v = i=1
N
k
P ~v
N
i=1

Computer Graphics – Geometric Models – Rendering Polygonal Meshes 8–39

 Typically, per-vertex normals vectors are stored alongside vertex positions in another
array.

• Therefore, they are another vertex attribute (i.e. a quantity associated with each
vertex).
• Other vertex attributes include: color, texture coordinates, . . .

v x y z Nx Ny Nz t i j k
0 1.0 1.0 1.0 ... ... ... 0 0 1 2
1 -1.0 1.0 -1.0 ... ... ... 1 0 2 3
2 -1.0 -1.0 1.0 ... ... ... 2 0 3 1
3 1.0 -1.0 -1.0 ... ... ... 3 3 2 1

Computer Graphics – Geometric Models – Rendering Polygonal Meshes 8–40

 During rendering per-vertex attributes have to be interpolated:

• E. g. ray tracing: ray hits inside a polygon

• E. g. rasterization: color of a pixel inside a polygon (scan conversion)

v x y z Nx Ny Nz Cr Cg Cb t i j k
0 1.0 1.0 1.0 ... ... ... ... ... ... 0 0 1 2
1 -1.0 1.0 -1.0 ... ... ... ... ... ... 1 0 2 3
2 -1.0 -1.0 1.0 ... ... ... ... ... ... 2 0 3 1
3 1.0 -1.0 -1.0 ... ... ... ... ... ... 3 3 2 1

This is often referred to as shading: what is the value of an attribute inside a

triangle?

Computer Graphics – Geometric Models – Rendering Polygonal Meshes 8–41

 Flat shading: attribute constant all over the polygon (e.g. taken from first vertex)

Smooth shading: variation of the attribute depicted on the polygon

• E. g. triangle/color: interpolation of per-vertex color with barycentric interpolation

Computer Graphics – Geometric Models – Rendering Polygonal Meshes 8–42

 Shading other polygon types

Quadrilaterals: bilinear interpolation

p2


f (p) = (1 − v) (1 − u)f (p0 ) + uf (p1 ) + u


v (1 − u)f (p2 ) + uf (p3 ) p0 1−
v
1−u
p
u p3
v
where u, v ∈ [0, 1] are determined such that
1−u
p = (1 − v)((1 − u))p0 + up1 ) + v((1 − u)p2 + up3 )
p1
( nonlinear 2 × 2 system). In essence, interpolate
linearly in u-direction, then again in v-direction.

Other polygons: triangulation, then barycentric

interpolation (→ course Computation Geometry).

Computer Graphics – Geometric Models – Rendering Polygonal Meshes 8–43

 Special case: Illumination
Normal vectors are required for the evaluation of local illumination models (→ Chapter 5)

Historical development:
• Flat shading:
Evaluation of illumination model (Phong)
with per-face normals of the triangles
• Gouraud (smooth) shading:
computation of the illumination model
(Phong) at the vertices, interpolation of
the resulting color
(Henri Gouraud, 1971)

Computer Graphics – Geometric Models – Rendering Polygonal Meshes 8–44

 Example: comparison of shading approaches:

flat shading Gouraud shading Phong shading

Computer Graphics – Geometric Models – Rendering Polygonal Meshes 8–45

 Phong shading:

Principle: Evaluation of the illumination model (Phong) with the interpolated normal (by
Bui Tong Phong, 1973).

flat shading → no interpolation

Gouraud shading → evaluation of lighing model, then interpolation of colors
Phong shading → interpolation of normals, then evaluation of lighting model

For a long time, this was only practical with specialized hardware, but it has become
ubiquitous since the advent of programmable graphics hardware.

Phong shading is often called “per-pixel lighting”;

this approach is also feasible for other illumination models.

Caution: do not confuse Phong lighting (model) and Phong shading

Computer Graphics – Geometric Models – Rendering Polygonal Meshes 8–46

 Level of detail (LOD)

Motivation: In many cases, the ratio between amount of polygons and projected surface
is far too large (e.g., polygons are rendered smaller than a pixel).

This overhead in storage, transfer, editing and visualization of “unnecessary” polygons is

coped with by different “polygonal resolutions” of object representation. This is called
level of detail (LOD).

Computer Graphics – Geometric Models – Rendering Polygonal Meshes 8–47

Implicit Surfaces
 Besides polygon meshes, surfaces with functional description are used in modeling.

• Such a description can be transformed into a polygonal mesh if necessary

(triangulation), or
• can be used directly in different scenarios, e. g. in ray tracing (computing of
intersections)

We will consider

• implicit surfaces
• parametric surfaces

Homework: implicit representation

Computer Graphics – Geometric Models – Implicit Surfaces 8–48

 Implicit surfaces are given as set of points for which a given function evaluates to
0, thus
S := p ∈ R3 | f (p) = 0


The surface can not be computed directly, but a “distance” can be computed by
inserting x.

Example: unit sphere

x 2 + y 2 + z3 − 1 = 0

Computer Graphics – Geometric Models – Implicit Surfaces 8–49

 Normal vector of an implicit surface

• The direction of the normal at point p is given by the gradient ∇f of the function
f (p). The normalized gradient is the normal.
• Intuition: the gradient of a function points in the direction of steepest ascent in the
function near p, and is thus orthogonal to the surface, on which f is constant.

Definition:  
∂f (p) ∂f (p) ∂f (p)
∇f (p) = , ,
∂x ∂y ∂z

Computer Graphics – Geometric Models – Implicit Surfaces 8–50

 Alternative interpretation:

• Assume f is evaluated at each point of an area

• The implicit suface f (p) = c represents the set of all points, where f evaluates to c,
for arbitrary values of c (level sets or iso-contours of f )

Computer Graphics – Geometric Models – Implicit Surfaces 8–51

 Explicit computation of a level set:
• Sampling of the function on a regular
grid
• Identification of level-set parts in each
cell of the grid

The Marching Cubes algorithms provides a

triangle approximation of the level set for
each cube.

Details: Data Visualization and Scientific

Visualization courses

Computer Graphics – Geometric Models – Implicit Surfaces 8–52

 Example: triangulation of implicit surfaces via level sets

Often encountered in medicine, “function” (e. g. density) from imaging procedures (CT,
MRI,. . . ) → lecture “Scientific Visualization”

Computer Graphics – Geometric Models – Implicit Surfaces 8–53

 Quadrics are given as set of zeros of quadratic equations:

Ax2 + By2 + Cz2 + Dxy + Exz + Fyz + Gx + Hy + Iz + J = 0

e. g. planes, spheres, cylinders, cones, ellipsoids, paraboloids, etc.

ellipsoid hyperboloids paraboloids

Computer Graphics – Geometric Models – Implicit Surfaces 8–54

 Ray-Quadric intersection:

Inserting into the ray equation p(t) = o + td yields a quadratic equation

Aq t2 + Bq t + C with the solution
q q
−Bq − B2q − 4Aq Cq −Bq + B2q − 4Aq Cq
t0 = t1 =
2Aq 2Aq

Cases:

1. Two real solutions → two intersections

2. One solution twice → one boundary point
3. No real solution (discriminiant) → no intersections

Intersections with t < 0 lie behind the ray origin and should be ignored.
Computer Graphics – Geometric Models – Implicit Surfaces 8–55
 The normal direction at a point p of a quadric is given by:

2Ax + Dy + Ez + G
  
∂f (p)/∂x
n = ∇f (p) = ∂f (p)/∂y = 2By + Dy + Fz + H
   

∂f (p)/∂z 2Cz + Ex + Fy + I

Example: sphere f (p) = (x − cx )2 + (y − cy )2 + (z − cz )2 − R2 = 0

2(x − cx )
   
∂f (p)/∂x
n = ∂f (p)/∂y = 2(y − cy ) = 2(p − c)
   

∂f (p)/∂z 2(z − cz )

Computer Graphics – Geometric Models – Implicit Surfaces 8–56

Parametric Surfaces
 Parametric surfaces are defined as a transformation of a subset of the plane
Ω ⊆ R2 (parameter space) in the form:

f (u, v) : Ω → R3
f (u, v) = (x(u, v), y(u, v), z(u, v))

Ω = [0, 1]2 is typical but not necessary.

Illustration:
(u, v) (x(u, v), y(u, v), z(u, v))
f

Computer Graphics – Geometric Models – Parametric Surfaces 8–57

 Example: parametric rectangle

f : R2 → R3
(u, v) → (u, v, 0)

Computer Graphics – Geometric Models – Parametric Surfaces 8–58

 Example: parametric cylinder

f : R2 → R3
(u, v) → (cos(2πu), sin(2πu), v)

1 2

Computer Graphics – Geometric Models – Parametric Surfaces 8–59

 Example:
parametric unit z

sphere
r̂

θ̂

θ : [0, 2π] azimuth r

ϕ : [0, π] zenith/elevation ϕ
z
ϕ̂

y
θ

x
y

x(θ, ϕ) = cos(θ) · sin(ϕ)

y(θ, ϕ) = sin(θ) · sin(ϕ) x

z(θ, ϕ) = cos(ϕ)

Computer Graphics – Geometric Models – Parametric Surfaces 8–60

 Bézier Surfaces: Especially intuitive to model parametric surfaces:

• The parameteric mapping is specified via control points

• Composing of complex surfaces by multiple Bézier surfaces (patches)
• Easy to compute

Bézier patch Model composed of multiple Bézier patches

Computer Graphics – Geometric Models – Parametric Surfaces 8–61

 Intersection of a ray with a parametric surface:

ox + tdx = x(u, v)
oy + tdy = y(u, v)
oz + tdz = z(u, v)

→ Three equations with three unknowns

→ Solution can be complex for not-trivial choices of x, y, z functions
• Iterative methods, e. g. Newton-method
• special techniques for specific types of surfaces

Computer Graphics – Geometric Models – Parametric Surfaces 8–62

 Illustration:

u = const or v = const yield curves

(u-curves and v-curves, or simply coordinate curves)

f
v0

u
u0

Computer Graphics – Geometric Models – Parametric Surfaces 8–63

 The tangent plane at the point p = f (u, v) is the plane in R3 that is spanned by the
tangential vectors of curves on the surface going through p

In the parametric case, these can be the tangents of the u-curve and v-curve through p.
These are given by the partial derivatives:

N
fv
δf δf
fu =
δu
and fv =
δv
fu

The unit vector orthogonal to fu

and fv is the normal:

fu × fv
N=
||fu × fv ||

Computer Graphics – Geometric Models – Parametric Surfaces 8–64

 Example: Cylinder

Parametric form:
   
x(u, v) cos(u)
y(u, v) =  sin(u) 
   
z(u, v) v

Normal:

0
     
− sin(u) cos(u)
 cos(u) × 0 =  sin(u) 
     
0 1 0

Computer Graphics – Geometric Models – Parametric Surfaces 8–65

 Conversion into polygonal meshes (meshing):

• E. g. via u- and v-curves at regular

intervals
• Not flexible, often no adaptivity
• Good results only with little warped
surfaces

• Triangulation/Quadrangulation
• many methods, with/without
adaptivity

Computer Graphics – Geometric Models – Parametric Surfaces 8–66

Constructive Solid Geometry
 Constructive Solid Geometry

• Set operations of solid bodies resp. volumes (intersection, difference, union)

Often used in the field of construction and is rather intuitive, e. g.

• Representation of complex objects via compositing of simple base objects

(primitives) via boolean set operations and transformations

• Displaying CSG objects requires special rendering techniques or conversion into

polygonal representation
• Ray tracing: can be applied implicitly
• Explicit algorithms for polyhedra

Computer Graphics – Geometric Models – Constructive Solid Geometry 8–67

 Examples:

• Union of a cuboid with a cylinder

• Difference operation with a further

cylinder

Computer Graphics – Geometric Models – Constructive Solid Geometry 8–68

 Examples:
• Intersection with a object that was
formed by the union of a cuboid and a
cylinder.

CSG representation as a tree:

• Inner nodes contain the boolean
operator and the information about the
spatial relationship of its children
• Leaves contain primitives and their
position

Computer Graphics – Geometric Models – Constructive Solid Geometry 8–69

Outlook & Recap
 Research topics: Geometry Compression

230 MB vs. 10 GB

Computer Graphics – Geometric Models – Outlook & Recap 8–70

 Research topics: Modeling Primitives

subdivision surfaces
Modern GPUs:
ad-hoc computation of subdivisions (tesselation shader)

Computer Graphics – Geometric Models – Outlook & Recap 8–71

 Research topics
• Remeshing
• Simplification
• Level-of-detail

Computer Graphics – Geometric Models – Outlook & Recap 8–72

 Research topics: Mesh Deformation

More research focus: Computer Graphics seminar

Computer Graphics – Geometric Models – Outlook & Recap 8–73
 Recap: things we learned in this chapter

• We considered polygonal meshes as a fundamental representation of geometry and

surface attributes, considered their properties (genus etc.), and discussed data
structures.
• We looked at rendering of polygonal meshes, including interpolation of attributes
and shading.
• We discussed alternative geometry representations through implicit surfaces and
parametric surfaces, and their conversion to polygonal models.
• We learned about some miscellaneous topics, such as normal computation and
constructive solid geometry.

Next: Coordinate Systems and Transformations

Computer Graphics – Geometric Models – Outlook & Recap 8–74