Polygon mesh

Objects created using polygon meshes must store different types of elements, such as vertices, edges, faces, polygons, and surfaces. In many cases, only vertices, edges, and either faces or polygons are stored. The renderer can only support triangular faces, so polygons must be built from their set, as shown in Fig. 1. However, many renderers support polygons with four or more sides, or they can triangulate polygons into triangles on the fly, making it unnecessary to store the grid in triangulated form. Also in some cases, such as modeling a head, it is desirable to be able to create both three- and four-sided polygons.

A vertex is a position along with other information, such as color, normal vector, and texture coordinates. An edge is a connection between two vertices. A face is a closed set of edges in which the triangular face has three edges and the quadrangular has four. A polygon is a set of coplanar (lying in the same plane) faces. In systems that support multilateral faces, polygons and faces are equivalent. However, most rendering hardware only supports faces with three or four sides, so polygons are represented as multiple faces. Mathematically, a polygonal mesh can be represented as an unstructured mesh, or an undirected graph, with the addition of geometry, shape, and topology properties.

Surfaces , often referred to as smoothing groups , are useful, but not necessary for grouping smooth areas. Imagine a cylinder with lids, such as a can. For smooth shading of the sides, all normals should point horizontally from the center, while the normals of the covers should point in +/- (0,0,1) directions. If rendered as a single surface shaded by Phong , the vertices of the folds would have irregular normals. Therefore, we need a way to determine where to stop smoothing in order to group smooth parts of the grid, just as polygons group triangular faces. As an alternative to providing surfaces / smoothing groups, the grid may contain other information for calculating the same data, such as a dividing angle (polygons with normals above this limit are either automatically considered as separate smoothing groups, or some technique is applied to the edge between them such as splitting or mowing). Also, polygonal meshes with very high resolution are less susceptible to problems that require smoothing groups to solve, since their polygons are so small that their need disappears. In addition, an alternative is to simply detach the surfaces themselves from the rest of the grid. Renderers do not try to smooth edges between non-adjacent polygons.

The format of the polygon mesh can determine other useful data. Groups can be defined that define individual grid elements and are useful for establishing separate subobjects for skeletal animation or for individual subjects of non-skeleton animation. Usually materials are defined, allowing different parts of the grid to use different shaders when rendering. Most grid formats also assume UV coordinates , which are a separate two-dimensional representation of the polygonal mesh, “expanded” to show how much of the two-dimensional texture is applied to different mesh polygons.

Polygonal meshes can be represented in many ways, using different methods of storing vertices, edges and faces. They include:

• List of Faces: The description of faces is done using pointers to the list of vertices.
• “Winged” representation: in it, each point of an edge points to two vertices, two faces and four (clockwise and counterclockwise) edges that touch it. The winged performance allows you to bypass the surface for a constant time, but it has more storage requirements.
• Half-edge grids: the method is similar to the “winged” representation, except that only half of the face information is used to bypass.
• Four- edge grids ^{[ unknown term ]} , which store edges, half-edges and vertices without any indication of polygons. Polygons are not directly expressed in the view, and can be found by going around the structure. Memory requirements are similar to half-edge grids.
• A table of angles that store vertices in a predefined table, such that traversing the table implicitly defines polygons. In essence, this is a “ fan of triangles ” used in hardware rendering. The view is more compact and more productive for finding polygons, but the operations for changing them are slow. Moreover, the angle tables do not represent the grid completely. To represent most grids, you need several angle tables (fans of triangles).
• Vertex view: only vertices are shown that point to other vertices. Information about faces and edges is expressed implicitly in this view. However, the simplicity of the presentation allows you to conduct many effective operations on the grid.

Each of the views has its advantages and disadvantages. ^[one]

The choice of the data structure is determined by the application, the required performance, the size of the data, the operations that will be performed. For example, it is easier to deal with triangles than with general polygons, especially in computational geometry . For certain operations, it is necessary to have quick access to topological information, such as edges or adjacent faces; this requires more complex structures, such as a “winged” performance. Hardware rendering requires compact, simple structures; therefore, low-level APIs such as DirectX and OpenGL typically include a table of angles (a fan of triangles).

Vertex View

A vertex representation describes an object as a set of vertices connected to other vertices. This is the simplest representation, but it is not widely used, since information about faces and edges is not expressed explicitly. Therefore, you need to go around all the data in order to generate a list of faces for rendering. In addition, operations on edges and faces are not easy.

However, VI grids benefit from low memory usage and efficient transformation. Figure 2 shows an example of a box depicted using a VI grid. Each vertex indexes its neighboring vertices. Notice that the last two vertices, 8 and 9 above and below the box, have four connected vertices, not five. The main system must cope with an arbitrary number of vertices associated with any given vertex.

For a more detailed description of VP grids, see Smith (2006). ^[one]

List of Faces

A grid using a list of faces represents an object as multiple faces and multiple vertices. This is the most widely used representation, being input typically accepted by modern graphics equipment.

The list of faces is better for modeling than the vertex representation in that it allows an explicit search for the vertices of the face and the faces surrounding the vertex. Figure 3 shows an example of a grid box using a list of faces. Vertex v5 is highlighted to show the edges that surround it. Note that in this example, each face has 3 vertices. However, this does not mean that each vertex has the same number of surrounding faces.

For rendering, the face is usually sent to the GPU as a set of vertex indices, and the vertices are sent as the position / color / normal structure (only the position is given in the figure). Therefore, changes in shape, but not geometry, can be dynamically updated simply by sending vertex data without updating the connectivity of the faces.

Modeling requires easy traversal of all structures. With a grid using a list of faces, it is very easy to find the vertices of a face. Also, the list of vertices contains a list of all faces associated with each vertex. In contrast to the vertex representation, both faces and vertices are clearly represented, so finding adjacent faces and vertices is constant in time. However, the edges are not explicitly defined, so a search is still needed to find all the faces surrounding the given face. Other dynamic operations, such as breaking or combining a face, are also complex with a list of faces.

Winged View

Introduced by Bruce Baumgart in 1975, the “Winged” view clearly represents the vertices, faces, and edges of the grid. This representation is widely used in simulation programs to provide the highest flexibility in dynamically changing mesh geometry because tear and join operations can be quickly performed. Their main drawback is high memory requirements and increased complexity due to the content of many indexes.

The “winged” representation solves the problem of going around from edge to edge and provides an ordered set of faces around the edge. For any given edge, the number of outgoing edges can be arbitrary. To simplify this, the “winged” view provides only four, the nearest edges, clockwise and counterclockwise at each end of the edge. Other ribs can be circumvented gradually. Therefore, the information about each rib resembles a butterfly, so the presentation is called “winged”. Figure 4 shows an example of a parallelepiped in a “winged” view. Complete data for an edge consists of two vertices (end points), two faces (on each side), and four edges ("wings" of the rib).

Rendering a “winged” representation of graphic equipment requires generating a list of face indices. This is usually done only when the geometry changes. The winged view is ideal for dynamic geometry, such as subdivision of surfaces and interactive modeling, since mesh changes can occur locally. Walking around the grid, which can be useful for collision detection, can be effectively performed.

See Baumgart (1975) for details. ^[2]

In the table above, it clearly indicates that the operation can be performed in constant time, as direct data is stored; comparison of lists indicates that the comparison of two lists must be performed to complete the operation; and a pair search indicates that two indexes should be searched. The designation avg (V, V) means the average number of vertices connected to a given vertex; avg (E, V) means the average number of edges connected to a given vertex, and avg (F, V) is the average number of faces connected to a given vertex.

The designation “V → f1, f2, f3, ... → v1, v2, v3, ...” indicates that to perform the operation, it is necessary to go around several elements. For example, to get “all vertices around a given vertex V” using a list of faces, you must first find faces around a given vertex V using a list of vertices. Then, from these faces, using the list of faces, find the vertices around them. Note that the “winged” view stores almost all of the information explicitly, and other operations always go around the edge first to get additional information. A vertex view is the only view that explicitly stores neighboring vertices of a given vertex.

With increasing complexity of representations (from left to right in the summary), the amount of information stored explicitly grows. This gives a more direct, constant in time access to the crawl and topology of various elements, but at the cost of increasing the occupied memory in order to preserve the indices properly.

As a general rule, meshes using a list of faces are used whenever an object needs to be rendered using hardware that does not change geometry (connections) but can deform or transform (vertex positions), for example, in rendering static or transformable objects in real time. The “winged” representation is used when the geometry changes, for example, in interactive modeling packages or for calculating subdivided surfaces. Vertex representation is ideal for efficient, complex changes in geometry or topology, as long as hardware rendering is not important.

Flow meshes keep faces ordered, but independently so that the mesh can be sent in parts. The order of faces can be spatial, spectral, or based on other properties of the grid. Stream grids allow you to render very large grids even when they are still loading.

Progressive meshes transmit data about vertices and faces with increasing levels of detail. Unlike flow meshes , progressive meshes give the overall shape of an entire object, but at a low level of detail. Additional data, new edges and faces, progressively increase the detail of the mesh.

Normal grids convey gradual grid changes as a set of normal offsets from the base grid. Using this technique, a number of textures display the desired incremental changes. Normal grids are compact, since only one scalar value is needed to express the displacement. However, the technique requires a number of complex transformations to create shear textures.

Polygonal grids can be stored in a variety of file formats :

• .blend (Blender) [1]
• Fbx
• 3B (3D-Coat)
• 3DS
• Ms3d
• Collada
• Dxf
• Obj
• PLY
• STL
• VRML
• X3d
• C4d
• MSH (file format)
• iED 3D / VR
• A3D (Alternativa3D8)

• Wireframe model
• Euler Operators
• Outline representation
• Simplex
• Triangulation (geometry)
• Variety (a grid can be varied or a little varied)