3.5 - Modeling Volumes¶

Defining Triangles¶

A triangle is defined using a combination of location and direction values.

Any 3 points (locations) in space define a triangle – as long as the 3 points do not lie on top of each other or along a straight line. You might think that 3 points on top of each other or along a straight line would be rare, but as you manipulate 3D objects these conditions can happen often. Therefore, as you develop computer graphics software you must continually test for such cases. Three points that do not define a valid triangle are called a “degenerate case”. Degenerate cases are problematic because they do not define an enclosed area or divide 3D space into 3 regions. But perhaps more importantly, degenerate cases cause the mathematics that manipulates the triangles to fail. To summarize,

• A triangle is defined by three points (locations).
• Degenerate cases:
  • The three points are not distinct. (Two or three of them are identical.)
  • The three points lie along a straight line.

The three points of a triangle define three edges or boundary line segments. The three points are the locations where the boundary line segments intersect. The intersection point of two curves, lines or edges is called a vertex. Modeling software refers to the points that define a triangle as vertices.

The surface of a triangle that is enclosed within its boundary edges is called a triangle face. (Notice that “face” is the suffix for sur”face”.) A triangle has two faces: a front face and a back face. A viewer can only see one face at a time. The front face is visible to a viewer if the viewer is on the front side of the triangle. Similarly, the back face is only visible if the viewer is on the back side of the triangle. This is important because in a scene with a single light source only one side of the triangle will get light. In addition, only one side of a triangle can be facing the scene’s camera. For triangles that are part of an object that fully encloses a 3D space, the orientation of the face can be used to determine if the face is visible to the camera.

The order of a triangle’s vertices are used to determine which side of a triangle is the front side. If you are looking at a triangle and the order of the vertices is counter-clockwise, then, by convention, you are looking at the front of the triangle. The order of a triangle’s vertices is called its winding order. There are two possible windings, as shown in the image to the left. If a triangle is not being rendered as you expect, it could be due to the triangle’s winding order.

A triangle has two vectors associated with it that are at right angles to every point on the triangle’s faces. One vector points away from the front face; the other vector points away from the back face. These vectors can be seen in the image to the right. You can calculate these vectors by taking the vector cross-product of any two edges of the triangle. Which edges you use and the order you perform the cross-product determines which vector you calculate. If a triangle’s vertices have a counter-clockwise winding order, and we take the cross product of edge 1 (between vertices 0 and 1) and edge 2 (between vertices 1 and 2) you will get the normal vector that is pointing away from the front face.

Remember that vectors have no location, just direction. Therefore a single vector can represent the direction of the front face for all points on the surface of the triangle.

Please note the following about the direction/orientation of a triangle:

• The vector that is pointing away from the front side of the triangle and is at a right-angle to every point in the surface of the triangle is called the normal vector. It is often just called the normal.
• The normal vector can be calculated “on the fly,” as needed, (assuming a triangle’s winding order is correct), or it can be calculated once and stored with the triangle’s definition. This is the classic computer science problem of resource allocation. If the normal is calculated as needed, the CPU (or GPU) has to do more work every time the triangle is rendered. If the normal is stored with the triangle definition, then more memory is required to store each triangle.
• If a normal vector is pre-calculated and stored with a model, it is always normalized to unit length. This minimizes the mathematical calculations needed during repeated rendering.
• There is never a need to calculate or store both the front and back facing normal vectors since they point in exactly opposite directions. If the front facing normal vector is <3,-2,5>, then the back facing normal vector is <-3,2,-5>.

Defining 3D Objects¶

The 3-dimensional form of an object can be approximated with a set of triangles called a triangle mesh. The accuracy of an object’s form is dependent on the number of triangles used to model it. The example triangular meshes on the right show how an object’s form can be more closely approximated as you increase the number of triangles. But there is always trade-offs:

• If you use a minimal number of triangles, the object’s form is a rough approximation, but rendering is very fast and you don’t use very much memory.
• If you use many triangles, the object’s form is more accurate, but rendering takes more time and the RAM and GPU memory requirements are larger.

Face Culling¶

A triangle mesh that defines a solid object will have only some of its triangles visible from a particular point of view. If the density of the triangles is uniform over the entire surface of the object, then, on average, only half of a model’s triangles will be visible at any given time. There is a simple test to determine if a triangle is visible. Calculate the angle between a vector that is pointing in the virtual camera’s direction of view, and a triangle’s normal vector. If the angle is greater than 90 degrees, then the triangle’s front face is oriented away from the camera and will not be visible because it will be hidden by other triangles in the model that are facing towards the camera. The angle between two vectors can be calculated by taking their dot-product. This simple test is called face culling and can potentially speed up rendering by a factor of two.

Please note that face culling can only be done on models of solid objects. If a model does not completely enclose the interior of a model, some back faces may need to be rendered. For example, a box with its top open may have some back-faces of triangles visible when looking into the box.

WebGL Triangle Rendering Modes¶

In WebGL you always define a set of triangles using an array of vertices. There are three drawing modes that determine how the vertices are interpreted:

• gl.TRIANGLE_STRIP - After the initial three vertices, each additional vertex defines one more triangle. Defining n triangles requires (n + 2) vertices.
• g.TRIANGLE_FAN - All triangles share the first vertex. After the first two vertices, each new vertex creates one triangle. Defining n triangles requires (n + 2) vertices.
• gl.TRIANGLES - The array of vertices contains three vertices for each triangle. Defining n triangles requires 3n vertices.

Dividing a triangle mesh into the most efficient groups of TRIANGLES, TRIANGLE_STRIP, and TRIANGLE_FAN sets is a very difficult problem. You can save considerable amounts of memory by using TRIANGLE_STRIP, and TRIANGLE_FAN modes, but they are actually rarely used. Let’s consider a very simple example. A cube is defined by 8 vertices and 12 triangles (6 sides with 2 triangles per side). There are many ways the cube could be rendered, such as

• Use TRIANGLES mode for all triangles. This requires an array of 36 vertices (12 triangles * 3 vertices/triangle).
• Use 2 arrays and TRIANGLE_FAN mode. One fan would start with the lower-left corner; the other fan would start with the upper-right corner. Each fan would draw 6 triangles. This requires two arrays of 8 vertices each, for a total of 16 vertices.
• Use TRIANGLE_STRIP mode to draw the front, right, back and left sides. Then use 2 TRIANGLE_FAN modes: one for the top 2 faces and one for the bottom 2 faces. This requires an array of 10 vertices for the TRIANGLE_STRIP and 2 arrays for the top and bottom, each holding 4 vertices. This is a total of 18 vertices.
• Etc. (Many other combinations are possible.)

The optimization of triangle groups to minimize memory requirements is beyond the scope of this textbook. We will restrict ourselves to using TRIANGLES mode for all our renderings – at the cost of using more RAM and GPU memory.

Glossary¶

triangle

A polygon defined by 3 straight boundary edges.

vertex

The intersection point of two curves, lines or edges. Three vertices define a triangle.

normal vector

A vector that is perpendicular (90 degree angle) to every point on the surface of a triangle. Of the two possible such vectors, the normal vector is the one that points away from the front face.

front face

By convention, the side of a triangle that its normal vector points away from.

back face

By convention, the side of a triangle that is opposite its front face.

triangular mesh

A group of triangles that approximate the form of a 3D object.

gl.TRIANGLE_STRIP

A WebGL drawing mode that draws triangles where each new vertex uses the previous two vertices in an array to form a new triangle.

gl.TRIANGLE_FAN

A WebGL drawing mode that draws triangles that all share the first vertex in an array.

gl.TRIANGLES

A WebGL drawing mode that draws a separate triangle for every 3 vertices in an array.

Self Assessment¶