Computer Science › Section K · Computer graphics › Topic K.2
Modeling objects
Before anything can be rendered, every object in a virtual scene has to be described as data. Most of that description is a mesh of small flat triangles, built from formulas, measurements or programs, then dressed with colour and arranged into a scene.
Scenes, objects and how much detail
Making a 3D image starts the way a theatre company prepares a play, by building a set and collecting props. In graphics the set is the scene and the props are objects, all stored as data. A prop need only be as real as its role demands: a car far in the background needs much less detail than one in close-up. Detail costs time to render and space to store, so modellers leave out what the camera will not show. Every model is an abstraction, and the skill lies in choosing what to keep.
Polygonal meshes
Shapes are usually described by a polygonal mesh: many small flat faces, called planar patches, that together approximate the surface, more closely as they get smaller. Patches are usually triangles, because three points not in a line always fix exactly one plane, while four points may not lie in a plane at all. A mesh is commonly stored as two lists: the vertices, each an \((x, y, z)\) point, and the faces, each a list of vertex numbers. Neighbouring triangles share vertices, so each corner is stored once.
Worked example: a cube as a mesh
Build a triangle mesh for a cube and estimate its storage. 1. A cube has 8 corners, so there are 8 vertices. 2. Each of its 6 square faces splits along a diagonal into 2 triangles: 12 triangles. 3. Each triangle has 3 edges, each shared by 2 triangles, so there are 12 × 3 ÷ 2 = 18 edges. 4. Check with Euler's formula \(V - E + F = 2\), true for a closed mesh with no holes through it: 8 − 18 + 12 = 2. 5. With 4-byte numbers, vertices take 8 × 3 × 4 = 96 bytes and faces 12 × 3 × 4 = 144 bytes, 240 in all, against 12 × 9 × 4 = 432 bytes if every triangle stored its own corners.
Which side is outside
Rendering needs to know which way each patch faces, so vertices are commonly listed anticlockwise as seen from outside. For vertices A, B, C in that order, let \(\mathbf{u} = B - A\) and \(\mathbf{v} = C - A\). Their cross product
is perpendicular to the patch and points outwards: the patch's normal vector. To check perpendicularity, use the dot product \(\mathbf{a} \cdot \mathbf{b} = a_1b_1 + a_2b_2 + a_3b_3\), which is 0 exactly when the vectors are at right angles. Listing the vertices clockwise reverses \(\mathbf{n}\), so a mesh with inconsistent ordering can render with faces apparently missing.
Worked example: a patch's normal
A triangle has vertices A(1, 0, 0), B(0, 2, 0) and C(0, 0, 2), listed anticlockwise from outside; the object lies on the origin's side of it. 1. \(\mathbf{u} = (-1, 2, 0)\) and \(\mathbf{v} = (-1, 0, 2)\). 2. Cross product: \((2 \cdot 2 - 0,\; 0 - (-1)(2),\; 0 - 2(-1)) = (4, 2, 2)\). 3. Check: \(\mathbf{n} \cdot \mathbf{u} = -4 + 4 + 0 = 0\) and \(\mathbf{n} \cdot \mathbf{v} = -4 + 0 + 4 = 0\). 4. Every component is positive, so \(\mathbf{n}\) points away from the origin, out of the object. 5. Its length is \(\sqrt{24} \approx 4.90\), so the unit normal is about (0.816, 0.408, 0.408).
From exact shapes to meshes
A sphere of radius \(r\) centred at the origin has the exact formula \(x^2 + y^2 + z^2 = r^2\). Lines of longitude and latitude cross at grid points on it, which become vertices. With \(m\) longitude lines and \(n\) latitude bands there are \(n - 1\) rings of \(m\) vertices plus two poles, and \(2m(n - 1)\) triangles: \(m = 8, n = 4\) gives 26 vertices and 48 triangles; \(m = 16, n = 8\) gives a rounder 114 and 224. Free-form shapes such as car bodies use Bézier curves, developed around 1960 by Pierre Bézier at Renault and, independently, Paul de Casteljau at Citroën. For the rendering pipeline, exact shapes still become meshes, because one representation lets one renderer handle every object.
Worked example: a point on a Bézier curve
A cubic Bézier curve with control points \(\mathbf{p}_0, \dots, \mathbf{p}_3\) starts at \(\mathbf{p}_0\), ends at \(\mathbf{p}_3\) and is pulled towards the middle two. Its point at \(t\), for \(0 \le t \le 1\), weights them by \((1-t)^3\), \(3t(1-t)^2\), \(3t^2(1-t)\) and \(t^3\). Take (0, 0), (0, 4), (6, 4), (6, 0) and \(t = \tfrac{1}{2}\). 1. The weights are 1/8, 3/8, 3/8, 1/8. 2. \(x = (0 + 0 + 18 + 6)/8 = 3\) and \(y = (0 + 12 + 12 + 0)/8 = 3\). 3. Check by repeated midpoints: (0, 2), (3, 4), (6, 2); then (1.5, 3), (4.5, 3); then (3, 3). 4. The curve peaks at height 3, below the middle control points. "Curves and surfaces" in Linear Algebra extends this to Bézier surfaces.
Measured and procedural models
A shape that defies formulas can be measured: a physical model is digitised by touching it with a probe that records 3D positions, or scanned with lasers or photographs. Trees, mountains, clouds and fire are too intricate even for that, so procedural models, programs that generate shapes, build them. A fractal mountain starts with one triangle, joins its edge midpoints into 4 smaller triangles, nudges the midpoints up or down at random, and repeats: after \(k\) rounds there are \(4^k\) triangles. Trees grow from branching rules, a grammar like those in "Language implementation: translation and compilers". Particle systems treat water, smoke or crowds as many particles moved by rules.
Surface properties and texture mapping
A mesh records only shape. To control appearance, a model can store a colour at each vertex or use texture mapping: like wallpaper, a stored image is attached to the surface. Each vertex gets texture coordinates \((u, v)\) from 0 to 1 saying which point of the image sits there; in a 512 × 512 texture, (0.25, 0.75) is the point 128 pixels across and 384 up. A brick image on a long box makes a cheap, convincing wall. Textures look wrong when stretched over strongly curved surfaces or where edges meet at a seam. Realism research targets skin, which light partly enters, cloth and hair, with about 100,000 strands on a head.
The scene graph
Each object is given a position, size and orientation, using the transformations of "Matrices in computer graphics", and everything is linked into a data structure called a scene graph, together with the lights and a camera. Scene graphs are often trees: a wheel is stored relative to its car, so moving the car moves its wheels. Virtual reality renders the scene from two cameras, one per eye, to give depth. Completing the scene graph ends modelling; rendering starts from it.
Common mistakes to avoid
First, assuming four corners always make a flat patch: (0, 0, 0), (2, 0, 0), (2, 2, 0) and (0, 2, 1) do not lie in one plane. Second, ordering a triangle's vertices clockwise by accident, which flips its normal inwards. Third, expecting a Bézier curve to pass through its middle control points. Fourth, thinking the rendering pipeline draws a sphere from its formula: it draws the mesh. Fifth, thinking a mesh alone fixes appearance: colour and texture are extra data.
Key takeaways
Models carry only the detail their role needs. Shapes are triangle meshes stored as shared vertices plus faces. Anticlockwise order from outside makes (B − A) × (C − A) an outward normal. Meshes come from formulas, Bézier curves, digitising, or procedural models: fractals, grammars, particle systems. Vertex colours and textures add appearance. A scene graph places objects, lights and camera.
Flashcards
Flashcard
The virtual set and the props placed in it
Test your understanding
Question 1 of 5
A closed triangle mesh with no holes has 20 vertices. Each triangle has 3 edges, each shared by 2 triangles. How many triangles does it have?
Question 2 of 5
A triangle's vertices are listed anticlockwise from outside as A(0, 0, 0), B(3, 0, 0), C(0, 3, 0). Which is its outward normal (B − A) × (C − A)?
Question 3 of 5
A cubic Bézier curve has control points (0, 0), (2, 6), (4, 6), (6, 0). What is its point at t = 1/2?
Question 4 of 5
Why are shapes that have exact formulas, such as spheres, usually converted into polygonal meshes before rendering?
Question 5 of 5
A fractal mountain starts as one triangle, and each round splits every triangle into 4. How many triangles are there after 5 rounds?
