Polygon Mesh Data Structure for 3D Graphics

Introduction

The polygon mesh data structure is the most common and oldest modeling method for computer graphics. 

Here is a wireframe teapot.
Here is a pen and ink drawing of a wireframe chalice ("Perspective Study of a Chalice"), done by Paolo Uccelloin 1430-1440, Florence, Italy.

Data Structure

Look at a 3D cube in a right-handed coordinate system

One Possible Data Structure:

Point3D   =	record
			x, y, z : real;
		end ;
Figure    =        array (1..8, 1..8) of Point3D;
Map       = array (1..8, 1..8) of boolean;
Map(i, j) = true if i, j connected else Map(i, J) = false 

Example Map(1, 4) = true but Map(1, 8) = false

Then to draw cube can do

for I in 1..8 loop                                               
	for J in 1..8 loop  
		if Map (I,J) then Draw line between point I and point J

Advantages: using a Map array is a simple data structure. Disadvantages: There is no way to identify points with the appropriate polygon. We will need to identify polygons for hidden line removal and for shading computations. So we want to keep track of the polygons. Relabel figure with explicit polygons Pi composed of vertices Vi.

Then we could have a list of polygons P1, P2, ..., where each polygon Pi is represented by a list of its vertex coordinates:

	P1 = (x1, y1, z1), (x2, y2, z2), (x3, y3, z3), (x4, y4, z4) 

Advantage: simple. Disadvantage: stores each set of vertex coordinates several times (3 times in this case). If use single precision then each point requires 3 * 4 bytes = 12 bytes.

If we had a figure with 10,000 4-sided polygons then would require 10,000 * 4 * 12 = 480,000 bytes. Too wasteful.

Another method would be to store a single vertex list:

	V = (V1 (x1, y1, z1), V2(x2, y2, z2) ....)

then a polygon is a list of its vertices e.g.:

	P1 = (V1, V2, V3, V4) 

Advantage: eliminates multiple storage of vertices. Disadvantage: shared edges are drawn twice, e.g. V2, V3 in P1 & P3. But this is not a problem unless we are only drawing wireframe figures.   We could use an explicit edge array to avoid redrawing edges multiple times. Then, a polygon is a list of edges: P1 = (E1, E2, E3, E4) and an edge consists of its vertices: E1 = (V1, V2).   Sometimes we need to know what the neighbors of a polygon are so might store the Polygons that share the edge, e.g.

	E1 = (V1, V2, P1, P2)

Either of the last two data structures is good depending on the particular application. In both cases, we are describing a 3D object as a polygon mesh.   So appropriate data declarations (in Pascal):

const
	MaxNumPts = 600;    {total max # of points allowed for surface} 
	MaxNumPolys = 900;   {maximum # of polygons allowed}  
	NumSidesPoly = 4;   {# of sides = # points for all polygons}
	MaxNumFigures = 20;  {maximum number of individual figures} 

type  
	PolyRange = 1..MaxNumPolys;
	Point_3D = record
			X, Y, Z: single
		end;{ record }
	Points_3D = array[1..MaxNumPts] of Point_3D;
	Vertex = 0..MaxNumPts;   pointer to polygon points 
	Polygon = record
			Vertices: array[1..NumSidesPoly] of Vertex;
		end; { Polygon }
	Polygons = array[PolyRange] of Polygon;
	FigureAttributes = record
				FigureColor: byte;
				CenterX, CenterY, CenterZ: single;
				Xscale, Yscale, Zscale: single;
			end;  {FigureAttributes}

 	 FigAttrArray = array[1.. MaxNumFigures] of FigureAttributes;

	FigureType   =   record
			 	NumberofFigures: byte;
				FigProps: FigAttrArray;
				 NumPtsFig, NumPolysFig: integer;
				FigPolys: Polygons;
				FigPoints: Points_3D;
				Zmin: single;   for perspective computation 
			end;   {FigureType}

Modeling in Computer Graphics
HyperGraph home page