Geometry And Primitives In Game Development

The heart of 3D lies in using various geometric entities to represent the objects and environments of a virtual scene. In 3D video games this information is usually processed by a dedicated piece of hardware: the graphics card. This information moves through the rendering pipeline, which can be thought of as a series of algorithmic steps that operate on the data that make up the scene to be rendered. Once processed, the final image is displayed to the monitor and the next rendering pass can start. In this article we talk generally about some of the geometric primitives before moving onto the topic of general game and graphics mathematics.

Lines

A line is a simple primitive that has a starting location and an ending location that are connected as shown below. With two points, a line segment can be represented in 2D or 3D space and can take on the following form using two dimensions, for example:

struct Point { 
   int x; int y; 
} 

struct Line { 
   Point start; 
   Point end; 
}

Lines can be used to form mathematical rays where the starting point of a line is the ray’s origin and the ending point of the line can be used to determine the ray’s direction. Rays are discussed in more detail later on in this article and are used heavily in computer graphics and in game programming.

Lines are not used as often as polygons for rendering in video games. It is rare to come across a situation where a line is needed for rendering in a modern video game.

Polygons

Polygons form many, if not all, of the geometric shapes seen in today’s 3D games. A polygon is a geometric shape that is made up of three or more points, where the lines that connect the outer area of the shape are called edges. The area that makes up the surface within this shape is often filled in using various algorithms (e.g., lighting, texturing mapping, etc.) by the hardware that is assigned the rendering task. The more points that are used, the more complex a shape can look. An example of a polygon is shown below and can be represented in pseudo-code as follows:

The shape you see on the left is a simple polygon structure. The figure on the right is an example of a complex polygon structure.

struct Polygon { 
   int total_points; 
   array points;
}

The edges of a polygon are the lines that connect one point of the polygon to another point. With a line there are no real edges since the primitive does not enclose an area. Polygons, on the other hand, do enclose an area, and the edges that surround it can be easily identified.

Triangles

Triangles are the most common type of primitive used in 3D video games.Triangles are three-point polygons whose three edges are used to connect each of the points that make up the shape of the primitive. This is shown below with a single triangle object.

Graphics hardware is very efficient at processing triangle primitives. Although the specific algorithms that are discussed are not specific to triangles, the applications that demonstrate them use triangles for the geometry.

Games often use three types of triangles. Triangle lists are individual triangles specified in an array that is sometimes referred to as a buffer. In a triangle list each triangle is individually specified. Points of a triangle can be shared by using indices to reduce the amount of data that must be passed to the graphics hardware.

An index, which is the singular form of indices, is an array index into a list of points. An example of using indices is shown below, where four points are used to specify two distinct triangles.

There are also triangle strips, which are defined by specifying the first three points of the first triangle and then one point for each additional triangle that branches off the first. Using a triangle strip is a way to reduce the amount of data that must be passed to the graphics hardware. By using six points we can form four separate triangles, as shown below. Triangle strips are commonly used for terrain geometry, where a terrain is normally a rectangular grid with varying Y-axis (height) values for each of its polygons.

The visual you see on the left is an example of the Flat terrain structure. The image you see on the right is the same terrain with varying height values.

The last type of triangle is triangle fans, which are triangles that all connect to the same common point on the mesh. By specifying a common point that all triangles connect to, you can create various shapes that would require more information to create with triangle lists.

Convex and Concave Polygons

Polygons and shapes in computer graphics can be either convex or concave. A convex polygon, or shape, has a convex set for its surface, which means that if a line segment is created between any two points that make up the object, it cannot penetrate any edge of said object. If a line segment does penetrate one of the object’s edges, it is considered concave.

A strict convex polygon or shape is one that has at most a 180-degree angle between each edge that makes up the object.

Using convex geometry is a better choice for things such as collision detection because convex shapes and polygons are more efficient to calculate and work with mathematically on a processor. While physics and collision detection are not the focus of this article, we will discuss some of the principles used in calculating lightmaps and shadows later on.

Triangles, because of the number of points that make them up, are always convex. This is because no line connecting any of a triangle’s points can possibly cross an edge of the triangle.

Spheres and Boxes

Spheres and boxes are commonly used in video games, not just for rendering but also for physics and collision calculations. A sphere is a mathematical object with a position and a radius, which specifies the circular region that surrounds the position. Spheres can take on the following form in pseudo-code:

struct Sphere { 
   int radius; 
   Point position; 
}

Spheres and boxes are used to surround complex objects in virtual scenes. If a complex object such as a character model is surrounded with a sphere or box primitive, which are much simpler shapes, they can be used in the collision and physics tests as a fast way to determine what action needs to be taken. For example, the test between two spheres colliding in a virtual scene is much faster than testing two triangles, let alone two sets of thousands of triangles, which are common in today’s character models. By testing two simple spheres you can quickly determine if a collision is even possible between two complex character models. This is shown below.

Simplified shapes such as sphere or box objects can be used to test if they potentially collide with one another. The term potentially is used because most simplified objects have some wasted space, which means some collision checks might return true when there is no collision.

When it comes to collision detection against spheres, spheres are much faster than other basic primitives such as triangles, boxes, and so forth. This speed comes at a cost of accuracy because the region that surrounds most objects tends to have a lot of wasted space, as shown below.

Without simplifying these tests and by using models with hundreds or thousands of polygons the CPU power required to calculate the average game physics using triangle-to-triangle tests would be so vast that games like Halo 3, Assassins Creed, Metal Gear Solid 4, and even Super Mario 64 (during its time) would be impossible. The triangle-to-triangle collision test is so expensive that game developers avoid them altogether and instead perform collisions on groups of very simple shapes.

An example of this is shown below, where a hierarchy of simple shapes can be used to represent a more complex model with acceptable accuracy. In video games, performance and accuracy/realism are often balanced based on the target hardware’s abilities.

Modern video games must have various scene management techniques like this to be able to render the vast amount of data at an acceptable rate, and in some games to be able to render at all.

Boxes and cubes are used a lot in video games. They offer a more accurate bounding volume than a sphere, but, although fast, they are not as fast to process as spheres. They are also used in many game editors for building game worlds. You can combine a box and other primitives to create entire game worlds using simple shapes. In Half-Life 2, Valve used their Hammer editor, which comes with the game to create the game levels. By building a game world essentially out of boxes and other primitives, the creators of the game were able to create every level you see in the game. Terrain, on the other hand, is often modeled differently than the rest of the geometry, but for interiors, buildings, and so forth using boxes can be very powerful.

The difference between a box and a cube is that a box can have different values for its width, height, and depth (length), whereas a cube has the same value for all three of its properties, thus creating a shape that is even on all sides. A box and a cube in general could take on the following form, where position is the center of the object:

struct Box {
   int width, height, depth; 
   Point position; 
}

struct Cube { 
   int size; 
   Point position;
}

Groups of convex polygons in most game editors are called brushes. The term brush is often used as the name of these groups of polygons, which form a convex shape.

Additional Geometric Objects

A vast number of additional geometric objects exist mathematically. Some of these objects can be found in video games, but if they are, they are often created using triangles rather than some mathematical equation.

Other geometric shapes are usually:

• Cones
• Pyramids
• Cylinders
• Toruses
• Torus knots
• Disks
• Ellipsoids
• Bezier curves
• Bezier patches
• Nurbs

Loading Geometry

In video games, geometry is usually loaded into an application during runtime from an external file. Games use many types of files. These files can include but are not limited to the following:

• Static models
• Animation files
• Terrains
• Environment files
• Collision meshes

Throughout our guide many of the samples on the CD-ROM load geometry from a very simple file format called the Wavefront OBJ file. This format is optional and is only used to store and load complex models that would not be efficient or practical to hand-code in the source files. An extensive overview and C++ loader for the file format can be found in Appendix D, “The OBJ File Format.” The Wavefront OBJ file format is used by many modeling applications such as Milkshape 3D, 3D Studio Max, and ZBrush. If you prefer to use another geometry file format, then by all means use that.