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 DirectXAPIs 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]
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]
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]
In computational geometry, a Delaunay triangulation or Delone triangulation of a set of points in the plane subdivides their convex hull into triangles whose circumcircles do not contain any of the points. This maximizes the size of the smallest angle in any of the triangles, and tends to avoid sliver triangles.
In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal.
A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The data associated with a leaf cell varies by application, but the leaf cell represents a "unit of interesting spatial information".
In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct. A directed path in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction.
In 3D computer graphics and solid modeling, a polygon mesh is a collection of vertices, edges and faces that defines the shape of a polyhedral object. The faces usually consist of triangles, quadrilaterals (quads), or other simple convex polygons (n-gons), since this simplifies rendering, but may also be more generally composed of concave polygons, or even polygons with holes.
In algebraic topology, simplicial homology is the sequence of homology groups of a simplicial complex. It formalizes the idea of the number of holes of a given dimension in the complex. This generalizes the number of connected components.
In geometry, a triangulation is a subdivision of a planar object into triangles, and by extension the subdivision of a higher-dimension geometric object into simplices. Triangulations of a three-dimensional volume would involve subdividing it into tetrahedra packed together.
Marching cubes is a computer graphics algorithm, published in the 1987 SIGGRAPH proceedings by Lorensen and Cline, for extracting a polygonal mesh of an isosurface from a three-dimensional discrete scalar field. The applications of this algorithm are mainly concerned with medical visualizations such as CT and MRI scan data images, and special effects or 3-D modelling with what is usually called metaballs or other metasurfaces. The marching cubes algorithm is meant to be used for 3-D; the 2-D version of this algorithm is called the marching squares algorithm.
In computer graphics, a triangle strip is a subset of triangles in a triangle mesh with shared vertices, and is a more memory-efficient method of storing information about the mesh. They are more efficient than un-indexed lists of triangles, but usually equally fast or slower than indexed triangle lists. The primary reason to use triangle strips is to 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.
In computer science, a deterministic acyclic finite state automaton (DAFSA), also called a directed acyclic word graph is a data structure that represents a set of strings, and allows for a query operation that tests whether a given string belongs to the set in time proportional to its length. Algorithms exist to construct and maintain such automata, while keeping them minimal.
In the mathematical field of graph theory, graph operations are operations which produce new graphs from initial ones. They include both unary and binary operations.
Expression templates are a C++ template metaprogramming technique that builds structures representing a computation at compile time, where expressions are evaluated only as needed to produce efficient code for the entire computation. Expression templates thus allow programmers to bypass the normal order of evaluation of the C++ language and achieve optimizations such as loop fusion.
OpenCTM is a 3D geometry technology for storing triangle-based meshes in a compact format.
Additive manufacturing file format (AMF) is an open standard for describing objects for additive manufacturing processes such as 3D printing. The official ISO/ASTM 52915:2016 standard is an XML-based format designed to allow any computer-aided design software to describe the shape and composition of any 3D object to be fabricated on any 3D printer via a computer-aided manufacturing software. Unlike its predecessor STL format, AMF has native support for color, materials, lattices, and constellations.
In computer graphics, tessellation is the dividing of datasets of polygons presenting objects in a scene into suitable structures for rendering. Especially for real-time rendering, data is tessellated into triangles, for example in OpenGL 4.0 and Direct3D 11.
3D Manufacturing Format or 3MF is an open source file format standard developed and published by the 3MF Consortium.
In graph theory, interval edge coloring is a type of edge coloring in which edges are labeled by the integers in some interval, every integer in the interval is used by at least one edge, and at each vertex the labels that appear on incident edges form a consecutive set of distinct numbers.
This is a glossary of terms relating to computer graphics.
In graph theory, a rainbow-independent set (ISR) is an independent set in a graph, in which each vertex has a different color.
JMesh is a JSON-based portable and extensible file format for the storage and interchange of unstructured geometric data, including discretized geometries such as triangular and tetrahedral meshes, parametric geometries such as NURBS curves and surfaces, and constructive geometries such as constructive solid geometry (CGS) of shape primitives and meshes. Built upon the JData specification, a JMesh file utilizes the JSON and Universal Binary JSON (UBJSON) constructs to serialize and encode geometric data structures, therefore, it can be directly processed by most existing JSON and UBJSON parsers. The JMesh specification defines a list of JSON-compatible constructs to encode geometric data, including N-dimensional (ND) vertices, curves, surfaces, solid elements, shape primitives, their interactions and spatial relations, together with their associated properties, such as numerical values, colors, normals, materials, textures and other properties related to graphics data manipulation, 3D fabrication, computer graphics rendering and animations.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
