May 14, 2019 at 15:41Texture Indent Pixels
Introducing the fourth article in our series on working with 3D models in Unity. Previous articles: “Features of working with Mesh in Unity” , “Unity: procedural editing of Mesh” , “Import of 3D models into Unity and pitfalls” .
In the previous article, we mentioned checking the texture scan for the adequacy of pixel indentation at a given texture resolution. In this publication, we describe the essence of the problem with observing pixel indentation and the algorithm for tracking it. It will not be considered the code, but precisely the principle that can be implemented in any language and in any development environment.
An order for a 3D model is usually accompanied by a requirement for texture resolution. Due to the discrete nature of the raster image, the 3D artist must observe the indentation in pixels between parts of the texture scan. The absence of the necessary indentation leads to the fact that the same pixel is displayed on the model in completely different places when it is not needed.
It is especially important to track a sufficient indentation in the early stages of work. Most often, some people are engaged in the creation of geometry, including a texture scan, and others are engaged in drawing textures. The error detected by the 3D artist will cause less trouble than the one that the texture designer will find. In the latter case, the situation becomes even more complicated if the 3D package used does not provide tools for drawing over geometry (for example, a brush).
You should also consider two nuances, because of which between the elements of the sweep may require more space. The first is a decrease in texture resolution during mipmapping. The second is the use of a dilation filter when forming a lighting map . During the task of creating a UV- scan, a 3D artist needs to be guided by the requirements for texture resolution, and also take into account the nuances listed above. Nevertheless, many shortcomings simply can not be noticed without automated verification.
An example of the appearance of artifacts with a decrease in detail
For simple models, a texture scan can be generated using automatic tools. However, they are based on internal metrics and do not take pixel indentation into account, so shared pixels are often located along diagonal borders. Checking with checker textures does not show all errors, in addition, these textures often have a higher resolution than those that will be used in the project.
Shared pixels
The problem of insufficient pixel indentation in the UV scan is similar to the problem with overlays. In both cases, the so-called bleeding can occur - in the previous article we described what artifacts this generates.
However, the problem with pixel indentation depends on the minimum texture resolution requirement. A single check is sufficient to determine the overlays, while the requirements for texture resolution may change at the next stage of development. The situation is complicated by the fact that the 3D packages we use do not have tools for automatically detecting errors related to the proximity of parts of the UV scan. And do not forget that after the operation of the automatic shaper in Unity, you still need to check UV2 .
We decided to create a tool that can check for indentation in pixels and mark the places of potential gaps in the model. Indentation requirements will be determined based on the following parameters:
Since the sizes of the textures used by us are equal to powers of two, the formula for calculating the necessary indentation at the basic resolution is quite simple: (basic Resolution / minimum Resolution) * indent on the MinTexture.
Obviously, the solution to this problem is closely related to rasterization. For a clearer statement of requirements and development of an algorithm, we introduce several concepts.
Consider a UV space and a uniform grid of dimension NxM in the range 0.0–1.0. Cells 1 / N wide and 1 / M high form a partition of UV space.
NxM partition of the UV- space
We take two arbitrary points and denote Dn as the number of pixels occupied by the projection onto the U-axis of the segment connecting the given points. Similarly, Dm for the V axis. Then we define the pixel distance as the maximum between Dn and Dm.
Pixel distance
It should be noted that in Euclidean space, such motion operations as parallel transfer and rotation are not movements for the mesh, if the pixel distance is taken as the metric. This nuance complicated the development of our solution a bit.
We call a square with sides in the K pixel kernel K values . Then any two points with a pixel distance less than K can be covered by a kernel of K.
Examples of kernels of different sizes
Two edges of a polygon form a concavity of the contour if their midpoint (the center of mass at four vertices) lies to the left of these edges when going around the contour in a clockwise direction arrow. For counterclockwise traversal, the condition is to find a point to the right of the edges.
A pair of ribs forming a concavity of the contour
Now let's talk directly about checking pixel indentation. To implement it, we came up with an algorithm consisting of three independent fragments. The order of execution is not important. The result of each of the fragments is the NxM matrix, which is a buffer of the cells of the partition, where some cells are labeled. The addition of all three buffers is the general result.
First, consider the simplest snippet. It comes down to finding cells that intersect close to degenerate triangles and edges, whose length is less than the side of the nucleus of a given magnitude. All such cells are marked in the buffer.
The result of checking the sizes of elements
Before describing the other two fragments, we consider the general logic of their work. Both are related to the processing of clusters of triangles called shells ( shells) Or islands ( islands ). Shell for a 3D artist is a connected set of polygons, that is, each polygon in this set has a neighbor with which it shares common vertices. Also shell is an independent training ground. Further, by shell, island and cluster we mean the same thing.
To find all the shells, we use the search algorithm for all connected components of the graph, where the vertex of the graph is represented by a polygon and the edge by the presence of common vertices in a pair of polygons. Since the only polygon in Unityis a triangle defined by vertex indices; we consider triangles to be adjacent if at least one index of the vertex of the first coincides with the index of any vertex of the second. From the analogy with the graph and the method for determining edges, it follows that the set of indices of the vertices of one cluster does not intersect the set of vertices of the other.
With the common part finished. The second fragment, which we will consider, determines the locations of potential errors associated with the proximity or overlap of different clusters.
Many clusters are fed to the input in the form of sets of triangles on the UV- space, the dimension of the UV partitioncorresponding to the texture resolution (NxM), and the indentation value P as the number of pixels. For a given partition, it is necessary to find those areas in which the distance in pixels between the clusters is less than the required indent. A cell in the result matrix is marked if it enters at least one core of the value K = P + 1 , which intersects two different clusters.
The essence of the fragment is almost set out in the description of the result. It is necessary to find all kernels of magnitude K that intersect with triangles from different shells, and then mark the cells of these nuclei in the result buffer.
In our implementation, all pairs of clusters are considered in turn. For each pair, the intersection region of the sets of kernels of magnitude K is determinedcovered by these clusters. We choose some pair and denote such a set as Q.
Then we need to check all elements of Q according to the following criterion: does a given kernel intersect at least one triangle in each of the clusters of the selected pair. If so, then all the cells of the tested kernel are marked.
The buffer with marked cells for all pairs of clusters constitutes the result.
The result of checking the indent between the clusters
Now we will deal with the last fragment. Here you need to process one cluster. The input is a set of triangles on the UV space, the dimension of the UV splittingcorresponding to the texture resolution (NxM), and the indentation value P as the number of pixels. A cell can be marked in two cases: either the cluster is invalid or has holes, or the distance in pixels between the concavity edges is less than the required indent.
The inner part of the cluster does not interest us - for a start we will get its contour represented by a connected list of edges. Neighboring triangles duplicate the indices of the vertices, so the edge belongs to the contour if a pair of indices of its vertices is unique for the set of edges of the cluster. Having figured out which edges form the contour, it is necessary to compose them so that a linked list is obtained.
If after this step not all edges of the contour get into the list, then either the cluster has holes, or there is an error in the mesh data. In this case, it is necessary to appropriately mark all the cells of the nuclei intersected by the cluster.
If the contour is found, then processing continues. We formulated the following result requirement. Let the pair of edges forming the concavity of the contour intersect the kernel of K = P + 1 . Then the cells of the nucleus must be marked if both parts of the contour between the edges go beyond this nucleus.
Cluster Feature Test Result
We decided to implement this requirement through pairwise comparison of the edges of the contour. We start with the concavity condition, then for each pair all kernels that intersect both edges are checked. To test the kernel, traversals of each part of the contour between a pair of edges are performed. If each part contains at least one point beyond the boundaries of the nucleus, then all cells of the nucleus are marked.
The condition under which the cells of the checked kernel are marked
The above algorithm is very suitable for implementation using parallel computing. Processing of each pair of clusters and edges occurs independently. Since the checks are based on rasterization, if you start processing not with pairs of edges, but with cores, it is advisable to use the capabilities of the GPU .
We transform the result of the algorithm into a texture. For a given resolution, this allows you to graphically show the places of potential flaws in the UV scan. Also, the resulting texture can be applied to the model to see marks directly on the geometry.
In the examples below, we specially cut the rabbit and Suzanne with a Blender automatic toolso as to get more artifacts. The checked texture resolution is 256x256, the necessary indentation is 1.
Cells marked in blue cover clusters with holes, as well as triangles and edges that are too small. Green indicates the cell nuclei with the characteristics of each cluster individually. Kernels in which the indent between clusters is not observed are marked in red.
In the next article, we will consider an algorithm for optimizing 3D models in a scene by removing invisible geometry. Stay with us!
In the previous article, we mentioned checking the texture scan for the adequacy of pixel indentation at a given texture resolution. In this publication, we describe the essence of the problem with observing pixel indentation and the algorithm for tracking it. It will not be considered the code, but precisely the principle that can be implemented in any language and in any development environment.
Issue
An order for a 3D model is usually accompanied by a requirement for texture resolution. Due to the discrete nature of the raster image, the 3D artist must observe the indentation in pixels between parts of the texture scan. The absence of the necessary indentation leads to the fact that the same pixel is displayed on the model in completely different places when it is not needed.
It is especially important to track a sufficient indentation in the early stages of work. Most often, some people are engaged in the creation of geometry, including a texture scan, and others are engaged in drawing textures. The error detected by the 3D artist will cause less trouble than the one that the texture designer will find. In the latter case, the situation becomes even more complicated if the 3D package used does not provide tools for drawing over geometry (for example, a brush).
You should also consider two nuances, because of which between the elements of the sweep may require more space. The first is a decrease in texture resolution during mipmapping. The second is the use of a dilation filter when forming a lighting map . During the task of creating a UV- scan, a 3D artist needs to be guided by the requirements for texture resolution, and also take into account the nuances listed above. Nevertheless, many shortcomings simply can not be noticed without automated verification.
An example of the appearance of artifacts with a decrease in detail
For simple models, a texture scan can be generated using automatic tools. However, they are based on internal metrics and do not take pixel indentation into account, so shared pixels are often located along diagonal borders. Checking with checker textures does not show all errors, in addition, these textures often have a higher resolution than those that will be used in the project.
Shared pixels
The problem of insufficient pixel indentation in the UV scan is similar to the problem with overlays. In both cases, the so-called bleeding can occur - in the previous article we described what artifacts this generates.
However, the problem with pixel indentation depends on the minimum texture resolution requirement. A single check is sufficient to determine the overlays, while the requirements for texture resolution may change at the next stage of development. The situation is complicated by the fact that the 3D packages we use do not have tools for automatically detecting errors related to the proximity of parts of the UV scan. And do not forget that after the operation of the automatic shaper in Unity, you still need to check UV2 .
We decided to create a tool that can check for indentation in pixels and mark the places of potential gaps in the model. Indentation requirements will be determined based on the following parameters:
- The base resolution of the texture.
- The minimum resolution of the texture at which flowing is not allowed.
- The required indentation on the minimum texture.
Since the sizes of the textures used by us are equal to powers of two, the formula for calculating the necessary indentation at the basic resolution is quite simple: (basic Resolution / minimum Resolution) * indent on the MinTexture.
Obviously, the solution to this problem is closely related to rasterization. For a clearer statement of requirements and development of an algorithm, we introduce several concepts.
Key concepts
Consider a UV space and a uniform grid of dimension NxM in the range 0.0–1.0. Cells 1 / N wide and 1 / M high form a partition of UV space.
NxM partition of the UV- space
We take two arbitrary points and denote Dn as the number of pixels occupied by the projection onto the U-axis of the segment connecting the given points. Similarly, Dm for the V axis. Then we define the pixel distance as the maximum between Dn and Dm.
Pixel distance
It should be noted that in Euclidean space, such motion operations as parallel transfer and rotation are not movements for the mesh, if the pixel distance is taken as the metric. This nuance complicated the development of our solution a bit.
We call a square with sides in the K pixel kernel K values . Then any two points with a pixel distance less than K can be covered by a kernel of K.
Examples of kernels of different sizes
Two edges of a polygon form a concavity of the contour if their midpoint (the center of mass at four vertices) lies to the left of these edges when going around the contour in a clockwise direction arrow. For counterclockwise traversal, the condition is to find a point to the right of the edges.
A pair of ribs forming a concavity of the contour
Decision
Now let's talk directly about checking pixel indentation. To implement it, we came up with an algorithm consisting of three independent fragments. The order of execution is not important. The result of each of the fragments is the NxM matrix, which is a buffer of the cells of the partition, where some cells are labeled. The addition of all three buffers is the general result.
First, consider the simplest snippet. It comes down to finding cells that intersect close to degenerate triangles and edges, whose length is less than the side of the nucleus of a given magnitude. All such cells are marked in the buffer.
The result of checking the sizes of elements
Before describing the other two fragments, we consider the general logic of their work. Both are related to the processing of clusters of triangles called shells ( shells) Or islands ( islands ). Shell for a 3D artist is a connected set of polygons, that is, each polygon in this set has a neighbor with which it shares common vertices. Also shell is an independent training ground. Further, by shell, island and cluster we mean the same thing.
To find all the shells, we use the search algorithm for all connected components of the graph, where the vertex of the graph is represented by a polygon and the edge by the presence of common vertices in a pair of polygons. Since the only polygon in Unityis a triangle defined by vertex indices; we consider triangles to be adjacent if at least one index of the vertex of the first coincides with the index of any vertex of the second. From the analogy with the graph and the method for determining edges, it follows that the set of indices of the vertices of one cluster does not intersect the set of vertices of the other.
With the common part finished. The second fragment, which we will consider, determines the locations of potential errors associated with the proximity or overlap of different clusters.
Many clusters are fed to the input in the form of sets of triangles on the UV- space, the dimension of the UV partitioncorresponding to the texture resolution (NxM), and the indentation value P as the number of pixels. For a given partition, it is necessary to find those areas in which the distance in pixels between the clusters is less than the required indent. A cell in the result matrix is marked if it enters at least one core of the value K = P + 1 , which intersects two different clusters.
The essence of the fragment is almost set out in the description of the result. It is necessary to find all kernels of magnitude K that intersect with triangles from different shells, and then mark the cells of these nuclei in the result buffer.
In our implementation, all pairs of clusters are considered in turn. For each pair, the intersection region of the sets of kernels of magnitude K is determinedcovered by these clusters. We choose some pair and denote such a set as Q.
Then we need to check all elements of Q according to the following criterion: does a given kernel intersect at least one triangle in each of the clusters of the selected pair. If so, then all the cells of the tested kernel are marked.
The buffer with marked cells for all pairs of clusters constitutes the result.
The result of checking the indent between the clusters
Now we will deal with the last fragment. Here you need to process one cluster. The input is a set of triangles on the UV space, the dimension of the UV splittingcorresponding to the texture resolution (NxM), and the indentation value P as the number of pixels. A cell can be marked in two cases: either the cluster is invalid or has holes, or the distance in pixels between the concavity edges is less than the required indent.
The inner part of the cluster does not interest us - for a start we will get its contour represented by a connected list of edges. Neighboring triangles duplicate the indices of the vertices, so the edge belongs to the contour if a pair of indices of its vertices is unique for the set of edges of the cluster. Having figured out which edges form the contour, it is necessary to compose them so that a linked list is obtained.
If after this step not all edges of the contour get into the list, then either the cluster has holes, or there is an error in the mesh data. In this case, it is necessary to appropriately mark all the cells of the nuclei intersected by the cluster.
If the contour is found, then processing continues. We formulated the following result requirement. Let the pair of edges forming the concavity of the contour intersect the kernel of K = P + 1 . Then the cells of the nucleus must be marked if both parts of the contour between the edges go beyond this nucleus.
Cluster Feature Test Result
We decided to implement this requirement through pairwise comparison of the edges of the contour. We start with the concavity condition, then for each pair all kernels that intersect both edges are checked. To test the kernel, traversals of each part of the contour between a pair of edges are performed. If each part contains at least one point beyond the boundaries of the nucleus, then all cells of the nucleus are marked.
The condition under which the cells of the checked kernel are marked
Summary
The above algorithm is very suitable for implementation using parallel computing. Processing of each pair of clusters and edges occurs independently. Since the checks are based on rasterization, if you start processing not with pairs of edges, but with cores, it is advisable to use the capabilities of the GPU .
We transform the result of the algorithm into a texture. For a given resolution, this allows you to graphically show the places of potential flaws in the UV scan. Also, the resulting texture can be applied to the model to see marks directly on the geometry.
In the examples below, we specially cut the rabbit and Suzanne with a Blender automatic toolso as to get more artifacts. The checked texture resolution is 256x256, the necessary indentation is 1.
Cells marked in blue cover clusters with holes, as well as triangles and edges that are too small. Green indicates the cell nuclei with the characteristics of each cluster individually. Kernels in which the indent between clusters is not observed are marked in red.
Examples
In the next article, we will consider an algorithm for optimizing 3D models in a scene by removing invisible geometry. Stay with us!