Lecture
In computer graphics, a triangle mesh is a type of polygon mesh . It consists of a set of triangles (usually in three dimensions ) connected by shared edges or vertices .
Many graphics software packages and hardware devices can work more efficiently with triangles grouped into meshes than with an equivalent number of triangles represented individually. This is usually because computer graphics performs operations on the vertices at the corners of triangles. With individual triangles, the system must work with three vertices for each triangle. In a large mesh, there may be eight or more triangles meeting at a single vertex — by processing these vertices only once, part of the work can be done once and an identical effect achieved.
An example of a triangle mesh representing a dolphin
A triangle mesh created by contouring an implicit surface
Many computer graphics applications need to manage a mesh of triangles. The components of a mesh are vertices, edges, and triangles. An application may need to know the various relationships between mesh components. These relationships can be managed independently of the actual positions of the vertices. This document describes a simple data structure that is convenient for managing these relationships. It is not the only possible data structure. There are many other types that support various queries about meshes.
There are various ways to store and work with a mesh in computer memory. With the OpenGL and DirectX APIs, there are two main ways to pass a triangle mesh to graphics hardware: triangle strips and index arrays.
One way of sharing vertex data between triangles is a triangle strip. In triangle strips, each triangle shares one full edge with one neighbor and another edge with the next. Another approach is the triangle fan , which is a set of connected triangles sharing a single central vertex. With these methods, vertices are processed efficiently, so that only N+2 vertices need to be processed to draw N triangles.
Triangle strips are efficient, but their drawback is that it may not be obvious how, or convenient, to convert an arbitrary triangle mesh into strips.
The data structure representing the mesh provides support for two main operations: inserting triangles and deleting triangles. It also supports an edge collapse operation, which is useful in triangle decimation schemes. The structure does not provide support for vertex positions, but assumes that each vertex is assigned a unique integer identifier, typically the index of that vertex in an array of adjacent vertex positions. A mesh vertex is defined by a single integer and denoted hvi. A mesh edge is defined by a pair of integers hv0,v1i, each integer corresponding to an endpoint of the edge. To support edge maps, edges are stored so that v0 = min(v0,v1). A triangle component is defined by a triple of integers hv0,v1,v2i, each integer corresponding to a vertex of the triangle. To support triangle maps, triangles are stored so that v0 = min(v0,v1,v2). Note that hv0,v1,v2i and hv0,v2,v1i are treated as different triangles. An application requiring two-sided triangles must insert both triples into the data structure. To avoid constantly reminding the reader about index order, in the remainder of this document, information about a pair/triple does not imply that vertices are ordered in any particular way (although the implementation handles the ordering).
Connectivity between components is entirely determined by the set of triples representing the triangles. A triangle t = hv0,v1,v2i has vertices v0, v1, and v2. It has edges e0 = hv0,v1i, e1 = hv1,v2i, and e2 = hv2,v0i. The reverse relationships are also known. Vertex v0 is adjacent to edges e0 and e2 and triangle t. Vertex v1 is adjacent to edges e0 and e1 and triangle t. Vertex v2 is adjacent to edges e1 and e2 and triangle t. All three edges e0, e1, and e2 are adjacent to t.
How much of this information the data structure stores depends on the needs of the application. Moreover, the application may want to store additional information in the components. Information stored on a vertex, edge, or triangle is called a vertex attribute, edge attribute, or triangle attribute. Abstract representations of this data for the simple data structure described here,
Vertex = <integer>; // v Edge = <integer, integer>; // v0, v1 Triangle <integer,integer,integer>; // v0, v1, v2 VData = <application-specific vertex data>; EData = <application-specific edge data>; TData = <application-specific triangle data>; VAttribute = ,set>; // data, eset, tset EAttribute = >; // data, tset TAttribute = ; // data VPair = pair<Vertex,VAttribute>; EPair = pair; TPair = pair<Triangle,TAttribute>; VMap = map; EMap = map; TMap = map; Mesh = ; // vmap, emap, tmap
Maps support standard insert and delete functions for a hash table. Insertion occurs only if the element does not already exist. Deletion occurs only if the element exists.
This operation involves identifying an edge hvk, vti, where vk is called the keep vertex, and vt is called the discard vertex. Triangles that share this edge are removed from the mesh. Vertex vt is also removed from the mesh. Any triangles that share vt replace this vertex with vk. Figure 1 shows a triangle mesh and a sequence of three edge collapses applied to the mesh.
With index arrays, the mesh is represented by two separate arrays: one array contains the vertices, and the other contains sets of three indices into that array, which define a triangle. The graphics system first processes the vertices, then renders the triangles using the index sets, working with the transformed data. In OpenGL, this is supported by the glDrawElements() primitive when using a Vertex Buffer Object (VBO).
With this method, any arbitrary set of triangles with an arbitrary number of vertices can be stored, processed, and passed to the graphics API without any intermediate processing.
Comments