PowerPoint Presentation
Geometric Modeling
The slides adapted in part courtesy of Angel’s Interactive Computer Graphics 6E © Addison-Wesley 2012.
Computer Graphics
Instructor: Sungkil Lee
2
Today
• Fundamental elements of geometry
• Points, scalars, and vectors
• Vector, Euclidean, and affine spaces
• Additional elements of geometry
• Geometric modeling
Prerequisites: Vector Spaces
4
Vector Spaces
• Formal definition of a vector space
• A vector space over a field 𝐹 is a set 𝑉 together with addition and
multiplication that satisfy the eight axioms.
• Elements of 𝑉 and 𝐹 are called vectors and scalars.
5
Vector Spaces
• More simply:
• Vectors can be added, and such a sum is also a vector.
• There is a zero vector and an inverse on vector addition.
• Vectors can be multiplied by a scalar.
• Identity exists for scalar multiplication (i.e., 1).
6
More on Algebra
• Mathematical structures related to the concept of a field can
be tracked as follows:
Geometric Elements
8
Geometry and Fundamental Elements
• Geometry:
• The study of the relationships among objects in an 𝑛-dimensional space
• In CG, we work with sets of geometric objects, such as points,
lines, triangles, and quads.
• Such objects exist in a 3D space.
• We can define them and their relationships using a limited set of
primitives.
• Three fundamental types of elements:
• Points, scalars, and vectors
9
Fundamental Elements (1): Points
• Point: a location in space
• a mathematical point has neither a size nor a shape.
• Points are useful in specifying geometric objects but are
insufficient by themselves
• We need real numbers to specify quantities such as the distance between
two points
• Such real numbers are examples of scalars.
10
Fundamental Elements (2): Scalars
• Scalars:
• Objects that obey a set of rules that abstractions of the operations of
ordinary arithmetic.
• Addition and multiplication are well defined and obey fundamental axioms
(associativity, commutativity, inverse, and identity).
• Examples of scalars:
• real numbers
• complex numbers
• Scalars alone have no geometric properties
11
Fundamental Elements (3): Vectors
• A physical definition of vectors:
• A quantity with direction and magnitude.
• Vectors do not have a fixed location in space.
• Examples:
• Force, velocity, and directed line segments
• Directed line segments, connecting two points, will be often used
synonymously to the term vector.
12
Operations on Vectors and Points
• Vectors are insufficient for geometry
• We need to represent a location in space.
• Points necessary
• Operations allowed between points and vectors
• 𝑣 = 𝑃 − 𝑄: point-point subtraction yields a vector
• 𝑃 = 𝑄 + 𝑣: equivalent to point-vector addition
13
Computer Science View on Geom. Elements
• We may need to define abstract data types for points, scalars,
and vectors independently.
• The operations allowed between elements can be exactly implemented
with operator overloading (in C++).
• We can overload only allowed operators among them, and do not
overload others (e.g., do not define point-point addition).
• Notes on GLSL: confusion with vec2,vec3,vec4.
• Unfortunately, this choice of names by GLSL can cause some confusion.
• They are actually not geometric types but rather storage types.
• Hence, we can use them to store a point, a vector, or a color.
Extensions of Vector Spaces
15
Euclidean Space
• Euclidean space
• Vector space + a measure of distance (i.e., Euclidean distance)
• Euclidean distance allows us to define size or distance as the length of a
line segment.
• When we also have the notion of point (i.e., affine space),
a Euclidean distance between two points can be defined as (in 3D):
𝑥1− 𝑥2
2+ 𝑦1− 𝑦2
2+ 𝑧1− 𝑧2
2
16
Affine Space
• Affine space
• Vector space (scalars and vectors only) + points
• Operations
• Vector-vector addition
• Scalar-vector multiplication
• Scalar-scalar operations
• Vector-point addition (newly defined in affine space)
• New points are defined by vector-point addition
• Alternatively, we can say there is point-point subtraction
(equivalent to vector-point addition).
• Note that there are no operations between points or scalars.
17
Representations
• In these abstract spaces (vector space, Euclidean space, and
affine space),
• Objects can be defined independently of any particular representations.
• Representation (the lecture covered later) provides the tie between the
abstract objects and their implementation (in real spaces).
• Conversion between representations leads us to geometric
transformations.
Additional Elements of Geometry
19
Lines
• The sum of a point and a vector (or the subtraction of two
points) leads to the notion of a line in an affine space.
• Consider all points of the parametric form
𝑃(𝛼) = 𝑃0 + 𝛼𝒅
• Here, a line can be defined as a set of all points that pass through 𝑃0 in the
direction of the vector 𝒅
20
Rays and Line Segments
𝑃 𝛼 = 𝑄 + 𝛼𝒅 = 𝑄 + 𝛼(𝑅 − 𝑄)
• If we restrict 𝜶 to semi-positive values (𝜶 ≥ 𝟎), this defines a
ray emanating from 𝑄.
• If we restrict 𝜶 to [0,1], this defines a line segment between Q
and R.
21
Affine Sum
• In an affine space, the addition of two arbitrary points and
multiplication of a point by a scalar are not defined.
• However, we have a limited form of an operation that has certain
elements of the two operations, affine addition.
22
Affine Sum
• Affine addition:
P = 𝑄 + 𝛼𝒗 = 𝑄 + 𝛼 𝑅 − 𝑄 = (1 − 𝛼)𝑄 + 𝛼𝑅
• This operation looks like the addition of two points and leads to the
equivalent form.
P = 𝛼1𝑄 + 𝛼2𝑅, where 𝛼1+ 𝛼2 = 1
• Then, this defines the two operations, not allowed in an affine space:
• (1) addition of two points and (2) multiplication of a point by a scalar
• yet only with the limited condition (the sum of scalars=0).
23
Affine Sum
• Affine sum:
• By extending such a point-vector addition to include 𝑛 points, we have the
following sum:
𝑃 = 𝛼1𝑃1 + 𝛼2𝑃2 +⋯+ 𝛼𝑛𝑃𝑛, where 𝛼1 + 𝛼2 +⋯+ 𝛼𝑛 = 1
• We call this kind of sum the affine sum.
• By this way, we can define the addition of points as well as the
multiplication of points by scalars.
24
Convex Hull
• Given a set of points, {P𝑖}, one more constraint, 𝛼𝑖 ≥ 0,
defines its convex hull, 𝐻, as:
𝐻 =
𝑖
𝛼𝑖 P𝑖
𝑖
𝛼𝑖 = 1, 𝛼𝑖 ≥ 0}
• The convex hull is the smallest convex object containing {P1, P2, … , P𝑛}.
• Convex object: for any two points in the object, all points on the line
segment between these points are also in the object.
25
Triangles: Barycentric Coordinates
• Also, we are able to write the plane in terms of affine sum as:
𝑇 𝛼, 𝛽, 𝛾 = 𝛼𝑃 + 𝛽𝑄 + 𝛾𝑅, where 𝛼 + 𝛽 + 𝛾 = 1.
• When 𝛼, 𝛽, 𝛾 > 𝟎, this represents a triangle and its internal
points.
• Hence, triangles are convex by default.
• This representation of a point is called the barycentric
coordinate representations.
• c.f., Barycenter: the center of mass
Geometric Modeling
27
Models
• Models:
• Mathematical abstraction of the real world or virtual worlds.
• Geometric Models:
• In CG, we model our worlds with geometric objects.
• Building blocks: a set of simple 3D primitives (Point, lines, triangles, …)
• Triangular meshes are common, which comprises a set of triangles
connected by their common edges or corners.
28
3D Primitives
• 3D objects that fit well with graphics HW and SW:
• described by their 2D surfaces and can be thought of as being hollow.
• c.f., objects with 3D surfaces are called the volumetric objects (e.g., CT).
• can be specified through a set of vertices.
• either are composed of or can be approximated by flat, convex polygons.
• e.g., a circle/sphere approximated by flat triangles.
29
3D Primitives
• Why we set these conditions?
• Modern graphics systems are optimized for rendering triangles or
meshes of triangles (e.g., more than 100 M triangles / sec.).
• Points and lines are also supported well.
• Vertices can be processed with the pipeline architecture, independently.
• Why are triangles fundamental primitives?
• The triangles are always flat.
• General polygons might not lie in the same plane, and then, there is no
simple way to define interior of the object.
• Also, general polygons can be decomposed into a set of triangles:
• then, we can apply the same pipeline on the triangles.
30
Triangular Mesh Representation
• Consider a mesh as a graph
• There are 8 vertices and 12 edges
• 5 interior polygons and 6 interior (shared) edges
• Decompose non-triangular polygons to triangles
v1
v2
v7
v6
v8
v5
v4
v3
e1
e8
e3
e2
e11
e6
e7
e10
e5
e4
e9
e12
v1
v2
v7
v6
v5
v4
v3
e1
e8
e3
e2
e11
e6
e7
e10
e5
e4
e9
e12
v8
31
Triangular Mesh Representation
• A simple list-based representation
• Define each polygon by the geometric locations of its vertices, leading to
OpenGL code such as.
• A simple list-based representation is often inefficient and unstructured.
• When a vertex moves to a new location, we must search and replace it for
all the occurrences.
…
vertex[i+0].pos = vec3(x1, y1, z1);
vertex[i+1].pos = vec3(x2, y2, z2);
vertex[i+2].pos = vec3(x7, y7, z7);
i+=3;
vertex[i+0].pos = vec3(x2, y2, z2);
vertex[i+1].pos = vec3(x3, y3, z3);
vertex[i+2].pos = vec3(x7, y7, z7);
i+=3;
…
32
Geometry vs. Topology
• Generally, it is a good idea to look for data structures that
separate the geometry from the topology
• Geometry: locations of the vertices
• Topology: structural organization of the vertices and edges
• Connectedness is preserved under continuous deformation
• Topology holds even if geometry changes
The cup and torus share the same topology.
33
Vertex Lists
• Geometries are put into an array
• Use indices from the vertices into this array.
• Topology maintains a triangle list regardless of geometry.
x1 y1 z1
x2 y2 z2
x3 y3 z3
x4 y4 z4
x5 y5 z5.
x6 y6 z6
x7 y7 z7
x8 y8 z8
Triangle 1
Triangle 2
Triangle 3
Triangle 4
Triangle 5
v1
v7
v6
v8
v5
v6
topology geometry