Triangle Strip - AbsoluteAstronomy.com

A triangle strip is a series of connected triangles, sharing vertices

Vertex (geometry)

In geometry, a vertex is a special kind of point that describes the corners or intersections of geometric shapes.-Of an angle:...

, allowing for faster rendering

Rendering (computer graphics)

Rendering is the process of generating an image from a model , by means of computer programs. A scene file contains objects in a strictly defined language or data structure; it would contain geometry, viewpoint, texture, lighting, and shading information as a description of the virtual scene...

and more efficient memory usage for computer graphics

Computer graphics

Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....

. They are optimized on most graphics cards, making them the most efficient way of describing an object. There are two primary reasons to use triangle strips:

Triangle strips increase code efficiency. After the first triangle is defined using three vertices, each new triangle can be defined by only one additional vertex, sharing the last two vertices defined for the previous triangle.
Triangle strips reduce the amount of data needed to create a series of triangles. The number of vertices stored in memory is reduced from 3N to N+2, where N is the number of triangles to be drawn. This allows for less use of disk space, as well as making them faster to load into RAM
Ram
-Animals:*Ram, an uncastrated male sheep*Ram cichlid, a species of freshwater fish endemic to Colombia and Venezuela-Military:*Battering ram*Ramming, a military tactic in which one vehicle runs into another...

.

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 then every even-numbered (with counting starting from one) triangle would be reversed resulting in the original triangles.

OpenGL implementation

OpenGL

OpenGL is a standard specification defining a cross-language, cross-platform API for writing applications that produce 2D and 3D computer graphics. The interface consists of over 250 different function calls which can be used to draw complex three-dimensional scenes from simple primitives. OpenGL...

has innate support for triangle strips using the glBegin, glVertex*, and glEnd functions. To draw a triangle strip, glBegin must be passed the argument GL_TRIANGLE_STRIP, which notifies OpenGL a triangle strip is about to be drawn. The glVertex* family of functions specify the coordinates for each vertex in the triangle strip. For more information, consult The OpenGL Redbook.

To draw the triangle strip in the diagram, the code is as follows:

//Vertices below are in Clockwise orientation
//Default setting for glFrontFace is Counter-clockwise
glFrontFace(GL_CW);

glBegin(GL_TRIANGLE_STRIP);
glVertex3f( 0.0f, 0.0f, 0.0f ); //vertex 1
glVertex3f( 0.0f, 1.0f, 0.0f ); //vertex 2
glVertex3f( 1.0f, 0.0f, 0.0f ); //vertex 3
glVertex3f( 1.5f, 1.0f, 0.0f ); //vertex 4
glEnd;

Note that only one additional vertex is needed to draw the second triangle.
In OpenGL, the order in which the vertices are specified is important so that surface normal

Surface normal

A surface normal, or simply normal, to a flat surface is a vector that is perpendicular to that surface. A normal to a non-flat surface at a point P on the surface is a vector perpendicular to the tangent plane to that surface at P. The word "normal" is also used as an adjective: a line normal to a...

s are consistent.

Quoted directly from the OpenGL Programming Guide:

GL_TRIANGLE_STRIP
Draws a series of triangles (three-sided polygons) using vertices v0, v1, v2, then v2, v1, v3 (note the order), then v2, v3, v4, and so on. The ordering is to ensure that the triangles are all drawn with the same orientation so that the strip can correctly form part of a surface.

The above code sample and diagram demonstrate triangles drawn in a clockwise orientation. For those to be considered front-facing, a preceding call to glFrontFace(GL_CW) is necessary, which otherwise has an initial value of GL_CCW (meaning that triangles drawn counter-clockwise are front-facing by default). This is significant if glEnable(GL_CULL_FACE) and glCullFace(GL_BACK) are already active (GL_BACK by default), because back-facing triangles will be culled, so will not be drawn and will not appear on-screen at all.

Properties and construction

It follows from definition that a subsequence of vertices of a triangle strip also represents a triangle strip. However, if this substrip starts at an even (with 1-based counting) vertex, then the resulting triangles will change their orientation. For example a substrip BCDEF would represent triangles: BCD,CED,DEF.

Similarly, reversal of strip's vertices will result in the same set of triangles if the strip has even number of vertices. (e.g. strip FEDCBA will represent the same triangles FED,ECD,DCB,CAB as the original strip). However, if a strip has odd number of vertices then the reversed strip will represent triangles with opposite orientation. For example, reversal of a strip ABCDE will result in strip EDCBA which represents triangles EDC, DBC, CBA).

Converting a general polygon mesh

Polygon mesh

A polygon mesh or unstructured grid is a collection of vertices, edges and faces that defines the shape of a polyhedral object in 3D computer graphics and solid modeling...

to a single long strip was until recently generally not possible. Usually the triangle strips are analogous to a set of edge loops

Edge loops

An edge loop, in computer graphics, can loosely be defined as a set of connected edges across a surface. Usually the last edge meets again with the first edge, thus forming a loop...

, and poles on the model are represented by triangle fan

Triangle fan

frame|Set of connected triangles described by vertices A through F.A triangle fan is a primitive in 3D computer graphics that saves on storage and processing time. It describes a set of connected triangles that share one central vertex...

s. Tools such as Stripe or FTSG represent the model as several strips. Optimally grouping a set of triangles into sequential strips has been proven NP-complete

NP-complete

In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

.

Alternatively, a complete object can be described as a degenerate strip, which contains zero-area triangles that the processing software or hardware will discard. The degenerate triangles effectively introduce discontinuities or "jumps" to the strip. For example, the mesh in the diagram could also be represented as ABCDDFFEDC, which would be interpreted as triangles ABC CBD CDD DDF DFF FFE FED DEC (degenerate triangles marked with italics). Notice how this strip first builds two triangles from the left, then restarts and builds the remaining two from the right.

While discontinuities in triangle strips can always be implemented by resending vertices, APIs sometimes explicitly support this feature. IRIS GL

IRIS GL

IRIS GL was a proprietary graphics API created by Silicon Graphics for producing 2D and 3D computer graphics on their IRIX-based IRIS graphical workstations...

supported Swaps (flipping two subsequent vertices in a strip), a feature relied on by early algorithms such as the SGI algorithm

SGI algorithm

The SGI algorithm creates triangle strips from a set of triangles. It was published by K. Akeley, P. Haeberli, and D. Burns as a C program named "tomesh.c" for use with Silicon Graphics' IRIS GL API....

. Recently OpenGL/DirectX can render multiple triangle strips without degenerated triangles using Primitive Restart feature.

OpenGL implementation

Properties and construction

See also