Triangle mesh: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 13:34, 16 July 2024

A triangle mesh created by contouring an implicit surface

In computer graphics, a triangle mesh is a type of polygon mesh. It comprises a set of triangles (typically in three dimensions) that are connected by their common edges or vertices.

Many graphics software packages and hardware devices can operate more efficiently on triangles that are grouped into meshes than on a similar number of triangles that are presented individually. This is typically because computer graphics do operations on the vertices at the corners of triangles. With individual triangles, the system has to operate on three vertices for every triangle. In a large mesh, there could be eight or more triangles meeting at a single vertex - by processing those vertices just once, it is possible to do a fraction of the work and achieve an identical effect.^{[citation needed]}

In many computer graphics applications it is necessary to manage a mesh of triangles. The mesh components are vertices, edges, and triangles. An application might require knowledge of the various connections between the mesh components. These connections can be managed independently of the actual vertex positions. This document describes a simple data structure that is convenient for managing the connections. This is not the only possible data structure. Many other types exist and have support for various queries about meshes.^{[citation needed]}

Representation

Various methods of storing and working with a mesh in computer memory are possible. With the OpenGL and DirectX APIs there are two primary ways of passing a triangle mesh to the graphics hardware, triangle strips and index arrays.^{[citation needed]}

Triangle strip

One way of sharing vertex data between triangles is the triangle strip. With strips of triangles each triangle shares one complete edge with one neighbour and another with the next. Another way is the triangle fan which is a set of connected triangles sharing one central vertex. With these methods vertices are dealt with efficiently resulting in the need to only process N+2 vertices in order to draw N triangles.^{[citation needed]}

Triangle strips are efficient, however the drawback is that it may not be obvious how or convenient to translate an arbitrary triangle mesh into strips.^{[citation needed]}

The Data Structure

The data structure representing the mesh provides support for two basic operations: inserting triangles and removing triangles. It also supports an edge collapse operation that is useful in triangle decimation schemes. The structure provides no support for the vertex positions, but it does assume that each vertex is assigned a unique integer identifier, typically the index of that vertex in an array of contiguous vertex positions. A mesh vertex is defined by a single integer and is denoted by hvi. A mesh edge is defined by a pair of integers hv0,v1i, each integer corresponding to an end point of the edge. To support edge maps, the 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, the triangles are stored so that v0 = min(v0,v1,v2). Observe that hv0,v1,v2i and hv0,v2,v1i are treated as different triangles. An application requiring double–sided triangles must insert both triples into the data structure. For the sake of avoiding constant reminders about order of indices, in the remainder of the document the pair/triple information does not imply the vertices are ordering in any way (although the implementation does handle the ordering).^{[citation needed]}

Connectivity between the components is completely 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 inverse connections are also known. Vertex v0 is adjacent to edges e0 and e2 and to triangle t. Vertex v1 is adjacent to edges e0 and e1 and to triangle t. Vertex v2 is adjacent to edges e1 and e2 and to triangle t. All three edges e0, e1, and e2 are adjacent to t.^{[citation needed]}

How much of this information a data structure stores is dependent on the needs of an application. Moreover, the application might want to have additional information stored at the components. The information stored at a vertex, edge, or triangle is referred to as the vertex attribute, edge attribute, or triangle attribute. The abstract representations of these for the simple data structure described here are^{[citation needed]}

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 = <VData, set<Edge>,set<Triangle>>; // data, eset, tset
EAttribute = <EData, set<Triangle>>; // data, tset
TAttribute = <TData>; // data
VPair = pair<Vertex,VAttribute>;
EPair = pair<Edge,EAttribute>;
TPair = pair<Triangle,TAttribute>;
VMap = map<VPair>;
EMap = map<EPair>;
TMap = map<TPair>;
Mesh = <VMap,EMap,TMap>; // vmap, emap, tmap

The maps support the standard insertion and removal functions for a hash table. Insertion occurs only if the item does not already exist. Removal occurs only if the item does exist.^{[citation needed]}

Edge collapse

This operation involves identifying an edge hvk, vti where vk is called the keep vertex and vt is called the throw vertex. The triangles that share this edge are removed from the mesh. The vertex vt is also removed from the mesh. Any triangles that shared vt have that vertex replaced by vk. Figure 1 ^[where?] shows a triangle mesh and a sequence of three edge collapses applied to the mesh.^{[citation needed]}

Index array

With index arrays, a mesh is represented by two separate arrays, one array holding the vertices, and another holding sets of three indices into that array which define a triangle. The graphics system processes the vertices first and renders the triangles afterwards, using the index sets working on the transformed data. In OpenGL, this is supported by the glDrawElements() primitive when using Vertex Buffer Object (VBO).^{[citation needed]}

With this method, any arbitrary set of triangles sharing any arbitrary number of vertices can be stored, manipulated, and passed to the graphics API, without any intermediary processing.^{[citation needed]}

@@ Line 1: / Line 1: @@
+{{Short description|Polygon mesh composed of triangles}}
+{{broader|Polygon mesh}}
 {{Unreferenced|date=December 2009}}
+[[File:Dolphin triangle mesh.png|thumb|250px|Example of a triangle mesh representing a dolphin]]
-{{Main|polygon mesh}}
+[[File:Impl-flaeche-geschl2.svg|thumb|A triangle mesh created by contouring an [[implicit surface]]]]
+In [[computer graphics]], a '''triangle mesh''' is a [[Types of mesh|type]] of [[polygon mesh]].  It comprises a set of [[triangle]]s (typically in [[three dimensions]]) that are connected by their common [[Edge (geometry)|edges]] or [[Vertex (geometry)|vertices]].
-[[File:Dolphin triangle mesh.png|thumb|250px|Example of a triangle mesh representing a dolphin.]]
-A '''triangle mesh''' is a [[Types of mesh|type]] of [[polygon mesh]] in [[computer graphics]].  It comprises a set of [[triangle]]s (typically in three [[dimension]]s) that are connected by their common edges or corners.
-Many graphics [[software]] packages and hardware devices can operate more efficiently on triangles that are grouped into meshes than on a similar number of triangles that are presented individually.  This is typically because computer graphics do operations on the vertices at the corners of triangles.  With individual triangles, the system has to operate on three vertices for every triangle.  In a large mesh, there could be eight or more triangles meeting at a single vertex - by processing those vertices just once, it is possible to do a fraction of the work and achieve an identical effect.
+Many [[graphics software]] packages and hardware devices can operate more efficiently on triangles that are grouped into meshes than on a similar number of triangles that are presented individually.  This is typically because computer graphics do operations on the vertices at the corners of triangles.  With individual triangles, the system has to operate on three vertices for every triangle.  In a large mesh, there could be eight or more triangles meeting at a single vertex - by processing those vertices just once, it is possible to do a fraction of the work and achieve an identical effect.{{fact|date=September 2023}}
-In many computer graphics applications it is necessary to manage a mesh of triangles. The mesh components are vertices, edges, and triangles. An application might require knowledge of the various connections between the mesh components. These connections can be managed independently of the actual vertex positions. This document describes a simple data structure that is convenient for managing the connections. This is not the only possible data structure. Many other types exist and have support for various queries about meshes.
+In many computer graphics applications it is necessary to manage a mesh of triangles. The mesh components are vertices, edges, and triangles. An application might require knowledge of the various connections between the mesh components. These connections can be managed independently of the actual vertex positions. This document describes a simple data structure that is convenient for managing the connections. This is not the only possible data structure. Many other types exist and have support for various queries about meshes.{{fact|date=September 2023}}
 ==Representation==
-Various methods of storing and working with a mesh in computer memory are possible. With the [[OpenGL]] and [[DirectX]] [[API]]s there are two primary ways of passing a triangle mesh to the graphics hardware, [[triangle strip]]s and index arrays.
+Various methods of storing and working with a mesh in computer memory are possible. With the [[OpenGL]] and [[DirectX]] [[API]]s there are two primary ways of passing a triangle mesh to the graphics hardware, [[triangle strip]]s and index arrays.{{fact|date=September 2023}}
 ===Triangle strip===
-One way of sharing vertex data between triangles is the triangle strip.  With [[Triangle strip|strips of triangles]] each triangle shares one complete edge with one neighbour and another with the next.  Another way is the [[triangle fan|triangle ''fan'']] which is a set of connected triangles sharing one central vertex.  With these methods [[vertex (computer graphics)|vertices]] are dealt with efficiently resulting in the need to only process N+2 vertices in order to draw N triangles.
+One way of sharing vertex data between triangles is the triangle strip.  With [[Triangle strip|strips of triangles]] each triangle shares one complete edge with one neighbour and another with the next.  Another way is the [[triangle fan|triangle ''fan'']] which is a set of connected triangles sharing one central vertex.  With these methods [[vertex (computer graphics)|vertices]] are dealt with efficiently resulting in the need to only process N+2 vertices in order to draw N triangles.{{fact|date=September 2023}}
-Triangle strips are efficient, however the drawback is that it may not be obvious how or convenient to translate an arbitrary triangle mesh into strips.
+Triangle strips are efficient, however the drawback is that it may not be obvious how or convenient to translate an arbitrary triangle mesh into strips.{{fact|date=September 2023}}
 ===The Data Structure===
-The data structure representing the mesh provides support for two basic operations, inserting triangles and removing triangles. It also supports an edge collapse operation that is useful in triangle decimation schemes. The structure provides no support for the vertex positions, but it does assume that each vertex is assigned a unique integer identifier, typically the index of that vertex in an array of contiguous vertex positions. A mesh vertex is defined by a single integer and is denoted by hvi. A mesh edge is defined by a pair of integers hv0,v1i, each integer corresponding to an end point of the edge. To support edge maps, the 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, the triangles are stored so that v0 = min(v0,v1,v2). Observe that hv0,v1,v2i and hv0,v2,v1i are treated as different triangles. An application requiring double–sided triangles must insert both triples into the data structure. For the sake of avoiding constant reminders about order of indices, in the remainder of the document the pair/triple information does not imply the vertices are ordering in any way (although the implementation does handle the ordering).
+The data structure representing the mesh provides support for two basic operations: inserting triangles and removing triangles. It also supports an edge collapse operation that is useful in triangle decimation schemes. The structure provides no support for the vertex positions, but it does assume that each vertex is assigned a unique integer identifier, typically the index of that vertex in an array of contiguous vertex positions. A mesh vertex is defined by a single integer and is denoted by hvi. A mesh edge is defined by a pair of integers hv0,v1i, each integer corresponding to an end point of the edge. To support edge maps, the 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, the triangles are stored so that v0 = min(v0,v1,v2). Observe that hv0,v1,v2i and hv0,v2,v1i are treated as different triangles. An application requiring double–sided triangles must insert both triples into the data structure. For the sake of avoiding constant reminders about order of indices, in the remainder of the document the pair/triple information does not imply the vertices are ordering in any way (although the implementation does handle the ordering).{{fact|date=September 2023}}
-Connectivity between the components is completely 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 inverse connections are also known. Vertex v0 is adjacent to edges e0 and e2 and to triangle t. Vertex v1 is adjacent to edges e0 and e1 and to triangle t. Vertex v2 is adjacent to edges e1 and e2 and to triangle t. All three edges e0, e1, and e2 are adjacent to t.
+Connectivity between the components is completely 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 inverse connections are also known. Vertex v0 is adjacent to edges e0 and e2 and to triangle t. Vertex v1 is adjacent to edges e0 and e1 and to triangle t. Vertex v2 is adjacent to edges e1 and e2 and to triangle t. All three edges e0, e1, and e2 are adjacent to t.{{fact|date=September 2023}}
-How much of this information a data structure stores is dependent on the needs of an application. Moreover, the application might want to have additional information stored at the components. The information stored at a vertex, edge, or triangle is referred to as the vertex attribute, edge attribute, or triangle attribute. The abstract representations of these for the simple data structure described here are
+How much of this information a data structure stores is dependent on the needs of an application. Moreover, the application might want to have additional information stored at the components. The information stored at a vertex, edge, or triangle is referred to as the vertex attribute, edge attribute, or triangle attribute. The abstract representations of these for the simple data structure described here are{{fact|date=September 2023}}
 <pre>
 Vertex = <integer>; // v
-Edge = <integer,integer>; // v0, v1
+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 = <VData,set<Edge>,set<Triangle>>; // data, eset, tset
+VAttribute = <VData, set<Edge>,set<Triangle>>; // data, eset, tset
-EAttribute = <EData,set<Triangle>>; // data, tset
+EAttribute = <EData, set<Triangle>>; // data, tset
 TAttribute = <TData>; // data
 VPair = pair<Vertex,VAttribute>;
@@ Line 40: / Line 45: @@
 </pre>
-The maps support the standard insertion and removal functions for a hash table. Insertion occurs only if the item does not already exist. Removal occurs only if the item does exist.
+The maps support the standard insertion and removal functions for a hash table. Insertion occurs only if the item does not already exist. Removal occurs only if the item does exist.{{fact|date=September 2023}}
-===Edge Collapse===
+===Edge collapse===
-This operation involves identifying an edge hvk,vti where vk is called the keep vertex and vt is called the throw vertex. The triangles that share this edge are removed from the mesh. The vertex vt is also removed from the mesh. Any triangles that shared vt have that vertex replaced by vk. Figure 1 shows a triangle mesh and a sequence of three edge collapses applied to the mesh.
+This operation involves identifying an edge hvk, vti where vk is called the keep vertex and vt is called the throw vertex. The triangles that share this edge are removed from the mesh. The vertex vt is also removed from the mesh. Any triangles that shared vt have that vertex replaced by vk. Figure 1 {{Where|date=February 2024}} shows a triangle mesh and a sequence of three edge collapses applied to the mesh.{{fact|date=September 2023}}
 ===Index array===
 {{See also|Polygon mesh#Face-vertex meshes|l1=Face-vertex meshes}}
-With index arrays, a mesh is represented by two separate arrays, one array holding the vertices, and another holding sets of three indices into that array which define a triangle.  The graphics system processes the vertices first and renders the triangles afterwards, using the index sets working on the transformed data. In OpenGL, this is supported by the '''glDrawElements()''' primitive when using [[Vertex Buffer Object]] (VBO).
+With index arrays, a mesh is represented by two separate arrays, one array holding the vertices, and another holding sets of three indices into that array which define a triangle.  The graphics system processes the vertices first and renders the triangles afterwards, using the index sets working on the transformed data. In OpenGL, this is supported by the '''glDrawElements()''' primitive when using [[Vertex Buffer Object]] (VBO).{{fact|date=September 2023}}
-With this method, any arbitrary set of triangles sharing any arbitrary number of vertices can be stored, manipulated, and passed to the graphics API, without any intermediary processing.
+With this method, any arbitrary set of triangles sharing any arbitrary number of vertices can be stored, manipulated, and passed to the graphics API, without any intermediary processing.{{fact|date=September 2023}}
 ==See also==
-* [[Polygon mesh]]
+* [[Hypergraph]]
+* [[Möller-Trumbore algorithm]] for ray-triangle intersection
 * [[Nonobtuse mesh]]
 * [[Nonuniform rational B-spline]]
 * [[Point cloud]]
+* [[Polygon mesh]]
-* [[Möller-Trumbore algorithm]] for ray-triangle intersection
+* [[Triangulation (topology)]]
-* [[Hypergraph]]
+* [[Triangulation (geometry)]]
+** [[Delaunay triangulation]]
+** [[Triangulated irregular network]]
+{{Mesh generation|state=autocollapse}}
 {{DEFAULTSORT:Triangle Mesh}}
 [[Category:Computer graphics data structures]]

v t e Mesh generation
Types of mesh	Polygon mesh Triangle mesh Volume mesh
Methods	Laplacian smoothing Parallel mesh generation Stretched grid method
Related	Chew's second algorithm Image-based meshing Marching cubes Marching tetrahedra Principles of Grid Generation Regular grid Ruppert's algorithm Tessellation Unstructured grid