Computer Graphics and Geometric Modeling | Malone Math

The Central Idea

Computer graphics begins with a geometric model and produces an image.

A simplified pipeline is

\[ \boxed{ \text{model} \rightarrow \text{transform} \rightarrow \text{project} \rightarrow \text{clip} \rightarrow \text{rasterize} \rightarrow \text{shade} }. \]

Each stage uses geometric and algebraic tools developed throughout Malone Math.

What Is a Geometric Model?

A geometric model is a mathematical description of an object or scene.

It may contain:

points and vertices;
line segments;
polygons;
meshes;
curves;
surfaces;
solids;
transformations;
connectivity and topology.

Modeling and Rendering Are Different Tasks

Geometric modeling defines the object.

Rendering determines how that object appears in an image.

The same model can be rendered from different viewpoints, under different lighting, with different materials, and at different resolutions.

Model Space

An object is often created in its own local coordinate system.

These coordinates are called model coordinates or object coordinates.

For example, a cube may be defined around the origin before being placed anywhere in a larger scene.

World Space

A model transformation places an object into the global scene.

If local point \(P\) is transformed by matrix \(M\), then

\[ \boxed{ P_{\text{world}}=MP }. \]

Different objects can use different model transformations.

View Space

The scene is then expressed relative to the camera.

A view transformation converts world coordinates into camera or view coordinates:

\[ \boxed{ P_{\text{view}}=VP_{\text{world}} }. \]

Conceptually, we can think of this as moving the entire world so that the camera occupies a convenient standard position.

Projection Space

A projection transformation maps three-dimensional view coordinates toward a two-dimensional image plane.

Two major projection families are:

orthographic projection;
perspective projection.

Orthographic Projection

In a simple orthographic view looking along the \(z\)-axis,

\[ \boxed{ (x,y,z) \mapsto (x,y) }. \]

Depth does not make distant objects appear smaller.

Parallel directions remain parallel in the projected image.

Perspective Projection

Perspective projection models the visual effect that distant objects appear smaller.

In a simple pinhole model with focal distance \(f\),

\[ \boxed{ x'=\frac{fx}{z}, \qquad y'=\frac{fy}{z} }. \]

The division by depth is the key geometric feature.

Perspective Foreshortening

If two objects have the same physical width but one has larger depth \(z\), then

\[ \frac{f}{z} \]

is smaller.

The more distant object therefore occupies less image space.

Homogeneous Coordinates

Graphics pipelines use homogeneous coordinates so that translation, rotation, scaling, and projection can be represented with matrix multiplication.

A three-dimensional point becomes

\[ \boxed{ (x,y,z,1). } \]

Combining Transformations

Suppose a point passes through model, view, and projection transformations.

Then

\[ \boxed{ P_{\text{clip}} = PVM P_{\text{model}} } \]

when column-vector notation and the appropriate multiplication order are used.

The matrices can often be multiplied in advance.

Transformation Order Matters

Matrix multiplication is generally not commutative.

\[ AB\ne BA. \]

Rotating an object and then translating it usually produces a different result from translating first and rotating second.

Translation

A translation by vector

\[ \mathbf{t}=(t_x,t_y,t_z) \]

maps

\[ \boxed{ P'=P+\mathbf{t} }. \]

Scaling

Scaling can act independently along coordinate axes:

\[ \boxed{ (x,y,z) \mapsto (s_xx,s_yy,s_zz) }. \]

Equal scale factors produce uniform scaling.

Unequal factors produce nonuniform scaling.

Rotation

A rotation around the \(z\)-axis by angle \(\theta\) uses

\[ \boxed{ R_z(\theta)= \begin{bmatrix} \cos\theta & -\sin\theta & 0\\ \sin\theta & \cos\theta & 0\\ 0 & 0 & 1 \end{bmatrix} }. \]

Similar matrices rotate around the \(x\)- and \(y\)-axes.

Screen Space

After projection and perspective division, coordinates are eventually mapped to screen coordinates.

A viewport transformation converts normalized coordinates into pixel positions.

This is where continuous geometry meets the finite raster display.

Clipping

Geometry outside the visible region should not be sent unchanged to later rendering stages.

Clipping removes or trims geometry that lies outside the viewing volume.

Line Clipping

A line segment may lie:

entirely inside the viewport;
entirely outside;
partly inside and partly outside.

In the third case, intersection points with the clipping boundary determine the visible subsegment.

Polygon Clipping

A polygon intersecting the view boundary may need to be split or trimmed.

A clipping algorithm can process the polygon against one boundary half-plane at a time.

This resembles the repeated half-plane clipping used to construct Voronoi cells.

Visibility

In a three-dimensional scene, many surfaces may project onto the same image location.

The renderer must determine which surface is visible from the camera.

Depth

If two fragments map to the same pixel, the one closer to the camera usually hides the farther one.

Depth testing therefore compares a stored depth value with the new candidate depth.

The Depth Buffer

A depth buffer stores one depth value per pixel.

For each new fragment:

compare its depth with the stored depth;
keep the closer fragment according to the chosen convention;
update the stored color and depth.

Painter's Algorithm

Another visibility idea draws distant surfaces first and nearer surfaces later.

This is conceptually similar to painting the background before the foreground.

Cyclic overlaps can make pure depth ordering difficult.

Meshes as Graphics Models

Polygon meshes are among the most common graphics representations.

A mesh stores:

vertex positions;
face connectivity;
normals;
texture coordinates;
colors or material data.

Why Triangles Dominate Graphics

Triangles are simple, planar, and always convex.

Three noncollinear vertices determine one plane.

This makes triangles convenient for:

rasterization;
interpolation;
visibility;
mesh processing;
hardware implementation.

Triangle Area and Orientation

For projected triangle vertices \(A,B,C\), the sign of

\[ \operatorname{orient}(A,B,C) \]

indicates winding direction.

This can be used in face-orientation tests and rasterization.

Back-Face Culling

For a closed consistently oriented mesh, surfaces facing away from the camera often need not be rendered.

Back-face culling rejects such faces before rasterization.

This reduces work but depends on correct face orientation.

Surface Normals

For triangle vertices \(A,B,C\), two edge vectors are

\[ \mathbf{u}=B-A \]

and

\[ \mathbf{v}=C-A. \]

A normal vector is

\[ \boxed{ \mathbf{n}= \mathbf{u}\times\mathbf{v} }. \]

Unit Normals

For many lighting calculations, the normal is normalized:

\[ \boxed{ \hat{\mathbf{n}} = \frac{\mathbf{n}} {\|\mathbf{n}\|} }. \]

Degenerate zero-area triangles have \(\mathbf{n}=\mathbf{0}\) and cannot produce a valid unit normal.

Vertex Normals

A mesh vertex shared by several faces may store a normal that approximates the local smooth surface direction.

One simple approach averages neighboring face normals, often with weights based on area or angle.

Flat and Smooth Shading

Flat shading uses one normal per face.

Smooth shading interpolates vertex-level quantities across the face.

The underlying geometry may remain identical while the visual appearance changes significantly.

Barycentric Coordinates

For triangle \(ABC\), any point \(P\) in the triangle can be written

\[ \boxed{ P= \alpha A+ \beta B+ \gamma C } \]

with

\[ \alpha+\beta+\gamma=1. \]

Inside the triangle,

\[ \alpha,\beta,\gamma\ge0. \]

Attribute Interpolation

If values \(q_A,q_B,q_C\) are stored at triangle vertices, barycentric interpolation gives

\[ \boxed{ q(P)= \alpha q_A+ \beta q_B+ \gamma q_C }. \]

The quantity might represent color, depth, a normal component, or another vertex attribute.

Texture Coordinates

Texture mapping assigns coordinates such as

\[ (u,v) \]

to mesh vertices.

These coordinates indicate where a point on the surface samples a two-dimensional image or procedural texture.

Texture Mapping Is a Coordinate Map

A surface position and texture position are connected through a mapping:

\[ \boxed{ \text{surface point} \longrightarrow (u,v) \longrightarrow \text{texture sample} }. \]

Distortion occurs when the mapping stretches or compresses areas.

Rasterization

Rasterization determines which pixels are covered by a projected primitive.

For a triangle, this means identifying screen samples inside the projected triangular region and generating corresponding fragments.

Inside-Triangle Tests during Rasterization

A screen sample can be classified using:

edge functions;
orientation signs;
barycentric coordinates.

These are different formulations of closely related geometry.

Edge Functions

For directed edge \(AB\), an edge function can be written as

\[ E_{AB}(P) = \operatorname{orient}(A,B,P). \]

The sign tells which side of the projected edge contains \(P\).

Sampling and Pixel Coverage

A projected geometric shape is continuous, but the display contains only discrete pixel samples.

Rasterization therefore requires a sampling rule.

This is the same representation issue explored in the Raster and Vector Representation lesson.

Aliasing in Graphics

Finite sampling can create artifacts such as:

jagged diagonal edges;
flickering fine patterns;
missing thin features;
unstable texture detail.

These are forms of aliasing.

Antialiasing

Antialiasing estimates a better representation of continuous coverage or signal variation.

Methods may use:

multiple samples per pixel;
coverage estimates;
filtering;
postprocessing.

Lighting Geometry

Many lighting models depend on angles between vectors.

Let

\[ \hat{\mathbf{n}} \]

be a unit surface normal and

\[ \hat{\mathbf{l}} \]

a unit direction toward a light.

Their dot product measures directional alignment.

Diffuse Lighting

A simple diffuse term is proportional to

\[ \boxed{ \max( 0, \hat{\mathbf{n}}\cdot\hat{\mathbf{l}} ) }. \]

A surface facing the light receives a larger value than one turned away.

View Direction

Specular effects and reflection models may also use a view direction

\[ \hat{\mathbf{v}}. \]

Graphics therefore relies heavily on the vector geometry of directions, normals, reflections, and angular relationships.

Reflection Direction

If \(\mathbf{d}\) points toward a surface and \(\hat{\mathbf{n}}\) is a unit normal, one reflection formula is

\[ \boxed{ \mathbf{r} = \mathbf{d} - 2(\mathbf{d}\cdot\hat{\mathbf{n}}) \hat{\mathbf{n}} }. \]

Geometric Modeling with Curves

Smooth graphics models often begin with parametric curves:

\[ \boxed{ C(t)= \bigl(x(t),y(t),z(t)\bigr) }. \]

Bézier curves, B-splines, and NURBS are common examples.

Bézier Curves

A cubic Bézier curve with control points

\[ P_0,P_1,P_2,P_3 \]

\[ \boxed{ B(t)= (1-t)^3P_0+ 3(1-t)^2tP_1+ 3(1-t)t^2P_2+ t^3P_3 }. \]

Here

\[ 0\le t\le1. \]

Control Points Guide Shape

Bézier control points do not all lie on the curve.

Instead, they shape the curve through weighted combinations.

The first and last control points are the curve endpoints.

Piecewise Curves

Long complicated shapes are often constructed from several curve segments.

Adjacent pieces may be joined with:

positional continuity;
tangent continuity;
curvature continuity.

Geometric Modeling with Surfaces

A parametric surface has the form

\[ \boxed{ S(u,v)= \bigl( x(u,v), y(u,v), z(u,v) \bigr) }. \]

Surface patches provide smooth geometric models before tessellation.

Surface Tangents

Partial derivatives

\[ S_u= \frac{\partial S}{\partial u} \]

and

\[ S_v= \frac{\partial S}{\partial v} \]

provide tangent directions along the surface parameter lines.

Surface Normal from Derivatives

A normal direction can be obtained from

\[ \boxed{ \mathbf{n} = S_u\times S_v }. \]

If the cross product is zero, the parameterization is locally degenerate.

Tessellation of Curved Surfaces

Smooth surfaces are commonly approximated by triangles before rendering.

Smaller triangles provide a closer approximation, especially in regions of high curvature.

Adaptive Tessellation

A renderer or modeling system need not subdivide every surface region equally.

More triangles can be used where:

curvature is high;
the surface is close to the camera;
silhouettes require detail;
displacement creates fine structure.

Level of Detail

A graphics system may use different geometric resolutions depending on viewing conditions.

Distant objects may use fewer polygons because their fine detail would project to very few pixels.

Silhouettes

The silhouette of a three-dimensional object is the visible boundary separating the object's projection from the background.

Silhouette quality strongly affects perceived shape.

Coarse meshes can produce visibly faceted silhouettes.

Hidden Geometry and Culling

Rendering systems often try to avoid processing geometry that cannot contribute to the final image.

Examples include:

view-frustum culling;
back-face culling;
occlusion culling;
hierarchical visibility tests.

View-Frustum Culling

Objects completely outside the camera's viewing volume cannot appear in the image.

Bounding volumes can be tested against the frustum before detailed geometry is processed.

Bounding Volumes Reappear

The same bounding boxes and spheres used in collision detection also help graphics systems reject invisible objects.

Computational geometry repeatedly reuses simple spatial approximations to reduce expensive work.

Ray Casting

A ray from the camera can be written

\[ \boxed{ R(t)=O+t\mathbf{d}, \qquad t\ge0 }. \]

Intersecting this ray with scene geometry determines what lies along that viewing direction.

Ray Tracing

Ray tracing extends ray casting by recursively considering effects such as:

reflection;
refraction;
shadows;
indirect light paths.

Geometric intersection remains the central operation.

Ray-Plane Intersection

Let a plane satisfy

\[ \mathbf{n}\cdot X=d \]

and a ray satisfy

\[ X=O+t\mathbf{d_r}. \]

Substitution gives

\[ \mathbf{n}\cdot(O+t\mathbf{d_r})=d. \]

Solving Ray-Plane Intersection

When

\[ \mathbf{n}\cdot\mathbf{d_r}\ne0, \]

the parameter is

\[ \boxed{ t= \frac{ d-\mathbf{n}\cdot O }{ \mathbf{n}\cdot\mathbf{d_r} } }. \]

The sign and range of \(t\) determine whether the intersection lies along the forward ray.

Ray-Triangle Intersection

A ray-triangle test can be viewed as two stages:

intersect the ray with the triangle's plane;
test whether the resulting point lies inside the triangle.

Efficient algorithms combine these calculations.

Acceleration Structures

A scene may contain millions of triangles.

Testing every ray against every triangle would be prohibitively expensive.

Spatial acceleration structures organize geometry so most primitives can be rejected quickly.

Bounding-Volume Hierarchies in Graphics

A bounding-volume hierarchy encloses groups of primitives in a tree of simple volumes.

A ray that misses a parent volume automatically misses every primitive inside that branch.

Spatial Trees

Other graphics acceleration structures partition space using:

kd-trees;
octrees;
binary space partitions;
uniform grids.

These structures reduce the number of detailed intersection tests.

Geometric Modeling and Topology

A mesh has geometric information and topological information.

Geometry specifies where vertices and surfaces lie.

Topology specifies adjacency and connectivity.

Many modeling algorithms require both.

Manifold Meshes

A well-behaved closed surface mesh often models a two-dimensional manifold embedded in three-dimensional space.

An ordinary interior edge is shared by exactly two faces.

Nonmanifold edges can complicate rendering, normals, subdivision, and solid interpretation.

Subdivision Surfaces

Subdivision methods repeatedly refine a coarse mesh according to local rules.

The refined meshes approach a smoother limiting surface.

This provides a bridge between polygonal control meshes and smooth geometric form.

Geometry Processing

Geometric modeling also includes algorithms that modify existing models:

mesh smoothing;
simplification;
remeshing;
hole filling;
surface reconstruction;
deformation.

Mesh Simplification

A detailed mesh can sometimes be approximated with fewer triangles.

The simplification algorithm seeks to reduce complexity while keeping geometric error below an acceptable level.

Geometric Error

If original surface \(S\) is approximated by \(\tilde S\), one may seek a bound such as

\[ \boxed{ d(S,\tilde S)\le\varepsilon }. \]

Different algorithms use different distance measures and perceptual criteria.

Deformation

A geometric model may be changed by a deformation map

\[ \boxed{ F:\mathbb{R}^3\to\mathbb{R}^3. } \]

Every point \(P\) moves to

\[ P'=F(P). \]

Rigid transformations preserve distances; general deformations need not.

Skeletal and Articulated Models

Animated models may use a hierarchy of coordinate frames representing an articulated skeleton.

Vertex positions are transformed according to one or more controlling bones or joints.

Interpolation in Animation

Motion between two positions \(P_0\) and \(P_1\) can use linear interpolation:

\[ \boxed{ P(t)= (1-t)P_0+tP_1 }. \]

Here

\[ 0\le t\le1. \]

Rotation Interpolation Requires Care

Rotation is not always best interpolated by independently blending matrix entries.

Specialized rotation representations, including quaternions, are commonly used to interpolate orientations smoothly.

The full theory belongs later in more advanced mathematical study.

Numerical Robustness

Graphics and modeling depend on numerical decisions involving:

depth comparisons;
line and ray intersections;
triangle orientation;
normalization;
clipping boundaries;
nearly coincident surfaces.

Near-Plane and Far-Plane Precision

Perspective depth mappings can distribute numerical precision unevenly across the viewing range.

Very large ratios between near and far distances can reduce useful depth precision and contribute to visibility artifacts.

Z-Fighting

Two nearly coincident surfaces may produce unstable depth comparisons.

Different pixels may alternate between the surfaces, creating a flickering pattern commonly called z-fighting.

Degenerate Triangles

If three triangle vertices are collinear, then

\[ \operatorname{orient}(A,B,C)=0 \]

in projection, or the three-dimensional cross product may vanish.

Such a triangle has zero area and should generally not be rasterized as an ordinary face.

Normal Transformation

Under nonuniform scaling, surface normals do not generally transform in the same way as position vectors.

Correct normal transformation requires special treatment so that the transformed normal remains perpendicular to the transformed surface.

Common Error: Confusing Model Space with World Space

A vertex coordinate such as

\[ (1,0,0) \]

has meaning only relative to its coordinate system.

The same object-space point may occupy a very different world-space location after transformation.

Common Error: Applying Transformations in the Wrong Order

Translation, rotation, and scaling do not generally commute.

Reversing transformation order can rotate around the wrong center or move an object to an unintended position.

Common Error: Treating Perspective as Simple Coordinate Deletion

Orthographic projection can resemble dropping the depth coordinate.

Perspective projection requires division by depth, which changes apparent scale.

Common Error: Normalizing a Zero Vector

A degenerate face may have

\[ \mathbf{n}=\mathbf{0}. \]

Since its magnitude is zero, no unit normal exists.

Common Error: Assuming a Smoothly Shaded Mesh Is Geometrically Smooth

Interpolated normals can make a coarse polygonal mesh appear smooth.

The underlying surface may still consist of flat triangles.

Common Error: Ignoring Sampling Resolution

Fine geometric detail can disappear when projected below pixel scale.

A correct geometric model does not guarantee a perfectly sampled image.

Common Error: Testing Every Ray against Every Primitive

Large scenes require acceleration structures.

Bounding hierarchies and spatial partitions eliminate most impossible intersection tests before detailed geometry is considered.

A Reliable Procedure for Transforming a Model to the Screen

Start with model-space vertex coordinates.
Apply the model transformation.
Apply the view transformation.
Apply the projection transformation.
Clip against the visible volume.
Perform perspective division when required.
Map normalized coordinates to the viewport.
Rasterize visible primitives.

A Reliable Procedure for Triangle Rasterization

Project the triangle into screen space.
Reject degenerate projected triangles.
Compute a screen-space bounding box.
Visit candidate pixel samples inside that box.
Use edge functions or barycentric coordinates to test coverage.
Interpolate depth and other attributes.
Apply depth testing.
Shade accepted fragments.

A Reliable Procedure for Geometric Model Verification

Check vertex and face connectivity.
Check for zero-area faces.
Check consistent orientation where required.
Check manifold assumptions.
Check normals and tangent data.
Check transformation consistency.
Check tessellation error against the intended model.
Check numerical edge cases near clipping and visibility boundaries.

Practice 1: Coordinate Spaces

Which coordinate space usually describes an object before it is placed into the larger scene?

Practice 2: Projection

Which projection type makes distant objects appear smaller?

Practice 3: Perspective Formula

\[ f=2,\qquad x=6,\qquad z=3, \]

what is

\[ x'=\frac{fx}{z}? \]

Practice 4: Triangle Normal

Which vector operation produces a normal from two nonparallel triangle edge vectors?

Practice 5: Barycentric Coordinates

What must

\[ \alpha+\beta+\gamma \]

equal in barycentric coordinates?

Practice 6: Visibility

What common per-pixel structure stores depth so that nearer fragments can hide farther fragments?

Practice 7: Rasterization

What does rasterization determine for a projected triangle?

Practice 8: Degenerate Triangle

What happens to the cross-product normal when the triangle's three vertices are collinear?

Practice 9: Ray

Write the standard parametric form of a ray beginning at \(O\) in direction \(\mathbf{d}\).

Practice 10: Acceleration Structure

Why is a bounding-volume hierarchy useful in ray tracing?

Practice Answers

Practice 1

\[ \boxed{\text{model space or object space}} \]

Practice 2

\[ \boxed{\text{perspective projection}} \]

Practice 3

\[ x'= \frac{2(6)}{3} = \boxed{4}. \]

Practice 4

The required operation is

\[ \boxed{\text{the cross product}}. \]

Practice 5

\[ \boxed{ \alpha+\beta+\gamma=1 }. \]

Practice 6

\[ \boxed{\text{the depth buffer or z-buffer}} \]

Practice 7

Rasterization determines which screen samples or pixels are covered and generates the fragments needed for later depth and shading calculations.

Practice 8

The edge vectors are linearly dependent, so

\[ \boxed{ \mathbf{u}\times\mathbf{v} = \mathbf{0} }. \]

Practice 9

\[ \boxed{ R(t)=O+t\mathbf{d}, \qquad t\ge0 }. \]

Practice 10

It rejects large groups of geometry when the ray misses their bounding volumes, avoiding unnecessary ray-primitive intersection tests.

What to Remember

Computer graphics combines geometric modeling with a sequence of spatial transformations and sampling operations.

models begin in local coordinates and are transformed into world and view spaces;
orthographic and perspective projections map three-dimensional geometry toward the image plane;
homogeneous matrices combine transformations efficiently;
clipping removes geometry outside the visible region;
depth testing resolves visibility among overlapping projections;
triangles dominate raster graphics because they are planar, convex, and easy to interpolate across;
surface normals come from cross products or surface derivatives;
barycentric coordinates interpolate depth, color, normals, and texture data;
curves and surfaces provide smooth geometric models before tessellation;
ray tracing reduces visibility and lighting questions to geometric intersection problems;
acceleration structures make large scenes computationally manageable;
sampling, numerical precision, and degeneracy affect the final image as much as ideal geometry does.

The larger computational principle is that an image is the end result of a chain of geometric representations. Each stage changes how the same spatial object is expressed, tested, approximated, or sampled.

Where We Go Next

Computer graphics and geometric modeling show how mathematical geometry becomes a visual computational scene. The final lesson in this section applies many of the same ideas to real-world geographic space.

Geographic Information Systems develops coordinate-based spatial data, map layers, projections, raster and vector models, topology, spatial queries, overlays, and computational analysis of geographic information.