3D Object Representations

How are 3D objects represented in a computer?

The representations need to be space efficient and amenable to quick computational processing.

We need to manipulate the objects computationally; Project, clip, move, rotate, articulate, deform, stretch...

Eventually the object needs to be drawn on screen.

 

3D Objects

(flash app)
screenshot
Cut Scene

Polygon Meshes

Most objects in computer games are stored as "Polygonal Meshes", which is a collection of polygons or "faces", that form the surface or "skin" of the object.

Benefits of using meshes

Problems with meshes

tetrahedron, represented perfectly by a mesh
a human face is only approximated by a mesh

Meshes can be used to model both solid shapes and thin "skins". The object is solid if the faces fit together to completely enclose a space or a volume, this is called a closed surface. Most of the pictures of meshes on this page show objects made of white or grey triangles with black borders. This is done to show the structure of the mesh. When the object is drawn so that all the edges are visible and the object is transparent, this is called a wireframe. Later in the course we will learn how to colour and smooth the triangles when drawing so the object looks more realistic.

This dolphin is a "solid" object (a closed surface)

 

For a mesh model we specify a set of points in space and we connect various pairs of these points to form edges. A set of 3 or more points (vertices) will form a polygon. A number of polygons may form a surface. And a number of surfaces will form an object.

Properties of meshes

Polygon meshes can be used to approximate almost any kind of object, these meshes will have a number of properties which allow us to discuss and compare different meshes. The properties will also affect how a mesh can be rendered

What are the key properties of the these meshes?

 

Generally, graphics algorithms require that faces be planar (flat). A triangle between 3 points is guaranteed to be planer, other polygons (squares, quads, pentagons etc.) might not be flat. This is one of the reasons that graphics renderers will only draw triangles. If you want to draw other polygons they often must be broken(tessellated) into triangles. For example, OpenGL will allow you to draw quads and convex polygons, but internally these are rendered as a number of triangles. By limiting rendering to triangles, the drawing algorithms can be highly optimised.

 

Simple Mesh Model

Consider the mesh in the figure above, we have 8 vertices and 12 faces (polygons).

This kind of mesh is known as a polyhedron, which is a solid mesh (encloses a definite volume) and all the faces are planer and it is simple (no holes). Polyhedrons are typically the simplest types of meshed to process and render, so many graphics systems will restrict meshes to polyhedrons.

In a polyhedron, no edges can be shared by more than 2 faces.

The number of vertices (V), edges(E) and Faces (F) on a polyhedron are related as follows; This is only true if the polyhedron has no holes (e.g. this not work for a doughnut)

\[ 2=V-E+F \]

this is known as Euler's formula.

Backfaces

On a close sd mesh, each polygon has two "sides". On side facing into the inside of the mesh (back face) and another side facing outward (frontface). A view can only see one side of a polygon at at time. If the mesh is closed, a viewer will never see a back face unless she is inside the object. Later on it will become necessary to figure out if we are looking at a front face or a backface. This is done by adopting a convention about how we list the vertices of a polygon. When listing the vertices for a polygon we imagine that we are looking at the frontface and list the vertices in counter clockwise order. We will use this information later to determine if we are looking at a backface or a frontface (see Backface Removal).

Another way to think about it; if walking on the outside of the mesh, around the polygon, the centre of the polygon will be on your left when CCW order.

Mesh Information

To describe a polygon mesh, two distinct types of information are required;

Data Structures for Representing a Mesh.

A good mesh representation must primarily be space efficient. In addition, if the topology of the mesh is to change (e.g. in a 3D modeling package) where polygons have to be split and merged and removed and inserted, there must be efficient access to the following kinds of information;

All vertices around vertex
All edges of a face
All vertices of a face
All faces around a vertex
All edges around a vertex
Both faces of an edge
Both vertices of an edge
Find face with given vertices

There are 3 main polygon mesh representations in use.

Example .X file

 

Other 3D Solid Object Representations

Voxels

BSp tree

 

CSG (Constructive solid geometry)

 

Sweep

 

Acquiring raw object data

Point cloud

An unstructured set of 3D point samples. Acquired from a range finder, laser, computer vision, 3D Scanner. Point clouds themselves are generally not directly usable in most 3D applications, and therefore are usually converted to triangle mesh models.

 

Range Image

Range imaging is the name for a collection of techniques which are used to produce a 2D image showing the distance to points in a scene from a specific point, normally associated with some type of sensor device.

 

Triangle strips

Most meshes consist of many connected triangles forming a smooth surface. One way to take advantage of this to use a triangle strip.

triangle strip

For example, the four triangles in the diagram, without using triangle strips, would have to be stored and interpreted as four separate triangles: ABC, CBD, CDE, and EDF. However, using a triangle strip, they can be stored simply as a sequence of vertices ABCDEF. This sequence would be decoded as a set of triangles ABC, BCD, CDE and DEF.

Note however, that triangle strips can only be used over a smooth mesh where vertex properties (colour, normal, etc) are shared between triangles. Triangle strips cannot be used where two of the triangles meet at a "seam", where the mesh surface changes abruptly. For example it would not be appropriate to render an entire cube as a triangle strip as each side of a cube would have different properties.

Cylinder

Can we draw the sides with one triangle strip? Another example would be the cylinder above. We could use 3 triangle strips to form the sides of the cylinder. We should not create a strip which contains triangles from the sides and the top as there is a seam and the vertices for the top will require different properties than the sides. The side and top do not form one smooth surface. The tops could be drawn using a triangle strip, but more appropriate would be a triangle fan.

Sample Mesh questions