Last Updated October 13, 2009

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 computaionaly; move, rotate, articulate, deform, strech...

3D Objects

Raw object data

Point cloud

An unstructured set of 3D point samples. Aquired 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.

Polygon Soup

A polygon soup is an unstructured set of polygons, usually created using an interactive modelling system (Blender, 3DStudio Max etc). The soup usuallyt consits of a list of unconnected triangles forming the skin of an object.

Surface Representaions

Mesh

Connected set of poygons (typically triangles).

3D Solid Object Representations

Voxels

BSp tree

CSG (Constructive solid geometry)

Sweep

Animation & Higher Level Structures

Skeleton

Scene Graph

Wire Frame Representaions

With a wireframe model we specify a set of points in space and we connect various pairs of these points to form edges. This representation only suggests the actual shape and doesn't really look solid. We need a method to make an object look solid and to be able to colour it's surface.

We can do this with polygon mesh models. A polygon mesh approximates the surface shape of an object by specifying a set of points in space these points representing vertices of various polygonal faces.

Simple Wireframe Model

Consider the mesh in the figure above, we have 8 vertices and 6 faces(polygons). A list of vertices for a polygon is created by looking at the polygon from the outside, listing the vertices in a counter-clockwise direction until a complete circle is made.

\[ $Poly_{1}=\{v_{1},v_{2},v_{3},v_{4}\}$ (front face)\] \[ $Poly_{2}=\{v_{4},v_{3},v_{6},v_{5}\}$ (right face)\]

This kind of mesh is known as a polyhedron>, which is a closed mesh (encloses a definite volume) and all the faces are planer>. A polyhedron can be used to represent almost any solid, but if the solid is highly curved, we must use a large number of faces to achieve the illusion of roundness and smoothness. In a polyhedron, no edges can be shared by more than 2 faces.

Data Structures for Representing a Mesh.

There are 3 main polygon mesh representations in use:

Explicit representation Each polygon is represented by a list of vertex coordinates: \[ $face_{1}=\big((u_{1},v_{1},n_{1}),(u_{2},v_{2},n_{2}),\ldots(u_{n},v_{n},n_{n})\big)$\]
The vertices are stored in counter clockwise order. There are edges between each pair of vertices and between the first and last vertices. This representation is not space efficient, because a shared vertex, will be stored many times. In a Cube for instance, each vertex is shared by 3 faces. Each edge is drawn twice. Also it is unclear from this representation, which faces are connected to which, this make manipulation difficult.
Pointer to Vertex List
In the representation we have a vertex list, which contains all the vertices in the mesh.

\[ $\textrm{Vertex List}=\big\{v_{1}=\{u_{1},v_{1},n_{1}\},v_{2}=\{u_{2},v_{2},n_{2}\},\ldots,v_{n}=\{u_{n},v_{n},n_{n}\}\big\}$\]
And a polygon is defined as a list of indices or pointers into the vertex list. e.g.

Simple Mesh

\[ $face_{1}=\{v_{2},v_{1},v_{6}\}$\]

\[ $face_{2}=\{v_{2},v_{6},v_{5},v_{4},v_{3}\}$\]

Each vertex is stored once. But each edge is stored twice and it is difficult to find polygons that share an edge.
Pointer to Edge List.
Again we have a vertex list V, but we also have an edge list E, in which each edge occurs just once. Each edge is stored as a pair of pointers into the vertex list, each edge also contains pointers to the polygons which share the edge. Polygons are defined as lists of pointer to the edge list.

Simple Mesh

\[ \textrm{Vertex List}&=&\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}\}\\ edge_{7}&=&\{v_{2},v_{6},P_{1},P_{2}\}\\ edge_{1}&=&\{v_{1},v_{2},P_{1},\lambda\}\\ face_{1}&=&\{e_{1},e_{6},e_{7}\}
To draw a wire frame in this representation, just draw all the edges in the edge list.