01: Functions & Calculus
01: Mathematics of Surfaces
Dr. Hamish Carr
COMP 5812M: Foundations of Modelling & Rendering
Some Assumptions
All of our mathematics uses real numbers
Graphics uses floats, fixed-point, rationals
Storage & bandwidth affect bit lengths
So there are a variety of formats
Especially for mobile rendering
We will assume 4B floats for now
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Graph of a Function
Set of points defined by the function
Notice we are now in 2-D
The embedding space of the graph
Ran
Gr(
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
: Height Field
For every point in the plane, define a height
The graph is then a terrain
i.e. a surface in a 3D embedding space
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Vector Fields
Fields whose output is a vector
Range has same dimension as domain
And there is added semantic meaning
Frequently represents flow
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Manifolds
Generalisation of the idea of surfaces
Sets that are locally equivalent to surfaces
Defined for any dimension
1-manifold – a curve
2-manifold – a surface
3-manifold – a volume
Always exist in an embedding space
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Multi-D Derivatives
Slope & rate of change become ambiguous
We define them with respect to a variable
I.e. rate of change of f as x changes:
Notation:
Derived by fixing other variables:
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Gradient Vector
A vector made of the partial derivatives:
Defines a vector field
Direction & rate of steepest descent
So the idea of slope is still with us
As is the idea of distortion
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Higher-Order Partials
Notation specifies order of differentiation:
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Multiple Integrals
Integration can also be done repeatedly
Summation is now over a small rectangle
And can be rewritten:
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
: Planar Curve
Also known as a parametric curve
Assigns (x,y) coordinates to each t value
Can self-intersect, &c.
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
: Space Curve
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Definition of a Curve
A curve is a set of points given by a function:
, where n is usually 2 or 3
Multiple functions describe the same curve:
We will see more of this next term
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Definition of a Surface
where:
is the surface
is the (2-)manifold it is mapped from
is the embedding space of the surface
This is a slightly circular definition, but:
The position (x,y,z) is just an attribute of
And this is often useful later on
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Mathematical Ideal
Each surface is known analytically
Usually parametrised by texture cords u,v
(x,y,z) are function of (u,v)
Normal vectors are perfect
Any other property is parametrised by u,v
And can be determined when needed
But it’s not that neat in practice
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
The Reality
Can only parametrise simple surfaces
Parametrisation implies distortion
Computing intersections, &c. is expensive
And it’s hard to construct a surface
i.e. the infamous creative control
Artists want to decide what the surface is
So they need workable tools
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
The Compromise
We use meshes to represent geometry
Position, normals, tangents, &c.
We use textures & maps for properties
And store them in arrays
Using (u,v) as lookups into the arrays
And we can store any lookup we want
Heightmaps, lightmaps, shadowmaps, &c.
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Differential Geometry
Weierstrass Theorem:
Any smooth function can be approximated with polynomials to any desired accuracy
Two basic choices:
p-refinement: more complex polynomials
h-refinement: more individual pieces
We’ll deal with p-refinement next term
For now, we just add more triangles
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
H-Refinement
Just add more triangles / polygons
But how?
We will need data structures
Which means discussing some basics first
And identifying the operations required
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Approximation Error
Let h be the maximum edge length in M
The approximation error is O(h2)
Corollary: high curvature => more edges
Perceptual issues also kick in:
Humans pay more attention to:
Edges, movement, textural changes
Eyes, hands, …
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Formal Definition of Mesh
A mesh consists of:
V the vertex set (a set of indices)
E the edge set (pairs of indices)
F the face set (3+-tuples of indices)
P points – a geometric embedding of V
A attributes – extra properties
F, E, V are essentially a graph
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Mesh Attributes
Attributes can be:
Position (x,y,z,[w])
Normal vector (nx, ny, nz)
Colour (r,g,b)
Texture coordinates (u,v,w)
Material (r,g,b + lots of extra stuff)
&c., &c., &c.
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Attribute Location
Attributes can belong to:
Vertices
Edges
Faces
Or even to a given vertex on a given face
-> eg normal along sharp edges
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Fundamental Choice
We can store attributes on the mesh itself
Or we can store attributes in textures
And store texture coordinates in the mesh
We can even store positions in textures
But mostly we do positions directly
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Manifold Meshes
Triangle mesh is 2-manifold iff:
all edges share two faces
no pinch points at vertices
i.e. single cycle around each vertex
no self-intersections
A non-self-intersecting, closed polyhedron
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Unwrapping Meshes
Meshes unwrap to become (planar) graphs
Choose one face and cut a small circle in it
Expand it to infinity
I.e. reverse so-called one-point unification
F1
F2
F3
F4
F5
F6
F1
F2
F3
F4
F5
F6
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Simple Polyhedra Planar Graphs
Euler (18th c.)
But not all polyhedra are simple
There is a phenomenon called genus
The number of handles through the surface
Or the number of independent cycles
from wikipedia …
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Euler’s Formula
In any orientable mesh/polyhedron:
v is number of vertices
e is number of edges
f is number of faces
g is the genus
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Some Examples
v e f g
Tetrahedron 4 6 4 0
Cube 8 12 6 0
Octahedron 6 12 8 0
Dodecahedron 20 30 12 0
Icosahedron 12 30 20 0
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Sketch of Proof
Start with a single cycle with 2 faces:
Add in vertices one at a time
Keeping track of vertex count, &c.
Leads to inductive proof
The basis of nearly all planar graph algorithms
and all polygon mesh data structures, &c.
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Vertex-Face Duality
Put a vertex at the centre of each face
Connect faces if adjacent
Constructs new faces around vertices
Vertices & faces are dual
Tetrahedron is self-dual
Cube is dual to octahedron
Dodecahedron is dual to icosahedron
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Triangulation
A mesh all of whose faces are triangular
And therefore easy to work with
Vertices can be arbitrary degree
But not 0, 1, or 2
Can always be constructed
e.g. barycentric face refinement
Therefore, the base assumption for everything
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Edges & Faces
Each edge belongs to 2 faces
Each face has 3 edges, so:
Each edge also has 2 vertices
Each vertex has an arbitrary number of edges
So the sums get a bit messier
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Edges & Vertices
So sum up the vertex degrees:
Alternately, count vertices of each degree:
And count the vertices separately:
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Substitutions
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Consequences
There is always a vertex of degree 3, 4, or 5
at least in a planar graph / genus 0 surface
The only ways the mesh can get bigger
by adding degree 6 vertices
or balancing high & low degree vertices
If genus is low (and it always is)
so we mostly ignore it
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
More Consequences
3v per face, 6f per vertex means that:
f ~ 2v, e ~ 3v
and everything scales on the # of vertices
The formula is a checksum for correctness!
A genus 1 surface (torus) can be regular
i.e. all vertices the same degree (6)
No others can, except small ones
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Quad Meshes
A quad mesh is similar, starting with:
4f = 2e
Similar substitutions lead to:
A quad mesh mostly has degree 4 vertices
Other vertices are extraordinary
See subdivision surfaces . . .
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Helix = cos t, sin t, t( ) : 0 ≤ t ≤
5
2
π
⎧
⎨
⎩
⎫
⎬
⎭
Helix=cost, sint, t
( )
:0£t£
5
2
p
ì
í
î
ü
ý
þ
Brief Article
The Author
October 1, 2018
2e =
Pv
i=1 �(vi)
v � e+ f = 2� 2g
3v � 3e+ 3f = 6� 6g
3v � 3e+ 2e = 6� 6g
3v � e = 6� 6g
6v � 2e = 12� 12g
6
1X
i=3
1 · ni �
1X
i=3
i · ni = 12� 12g
1X
i=3
(6� i) · ni = 12� 12g
6X
i=3
(6� i) · ni = 12� 12g �
1X
i=7
(6� i) · ni
6X
i=3
(6� i) · ni = 12� 12g +
1X
i=7
(i� 6) · ni
3n3 + 2n4 + 1n5 + 0n6 = 12� 12g + 1n7 + 2n8 + 3n9 + . . .
1
Brief Article
The Author
October 1, 2018
2e =
Pv
i=1 �(vi)
v � e+ f = 2� 2g
3v � 3e+ 3f = 6� 6g
3v � 3e+ 2e = 6� 6g
3v � e = 6� 6g
6v � 2e = 12� 12g
6
1X
i=3
1 · ni �
1X
i=3
i · ni = 12� 12g
1X
i=3
(6� i) · ni = 12� 12g
6X
i=3
(6� i) · ni = 12� 12g �
1X
i=7
(6� i) · ni
6X
i=3
(6� i) · ni = 12� 12g +
1X
i=7
(i� 6) · ni
3n3 + 2n4 + 1n5 + 0n6 = 12� 12g + 1n7 + 2n8 + 3n9 + . . .
1