Map Basics – Lines (Part 2)

Map Basics – Lines (Part 1)

preface

The first part recorded the basic process of line drawing, and the second part mainly describes the performance and effect problems encountered in line drawing. When you draw a line and want to style it with a stroke, you encounter the inevitable flicker problem. When a large number of staggered roads are drawn, the drawing performance and flicker problems should be considered simultaneously. This paper summarizes the efficient method of drawing stroke line, and expounds the investigated solution to z-fighting flicker.

Performance optimization for pixel rounded corner rendering

In the previous chapter, I introduced the method of fillet-by-pixel culling. Generally speaking, in order to achieve the purpose of dynamic fillet-by-pixel, the original CPU mathematical calculation is moved into the chip shader. Doing so, while achieving the smoothest results, also puts pressure on the GPU. Take rounded line cap code as an example. Affected by GPU processing mode, dynamic branch if/else instructions need to be fully executed, and discard instructions will also affect GPU Early Z optimization, both of which will affect performance.

fixed4 frag (v2f i) : If (dot(float2(i.geometryinfo.x, i.geometryinfo.y), float2(i.geometryInfo.x, i.geometryInfo.y)) > 1) { discard; If (dot(float2(i.geometryinfo.x - 1, i.geometryinfo.y)); if(dot(i.geometryinfo.x - 1, i.Geometryinfo.y)); float2(i.geometryInfo.x - 1, i.geometryInfo.y)) > 1) { discard; } } return i.color; }Copy the code

Therefore, in terms of the performance optimization of the instructions in the chip shader, the logic was changed to linear, the dynamic branches were removed, and the Alpha Blending theory was used to replace discard. The main tools to simplify the process are CG standard functions step/ Clamp/LERP, which are defined as follows and can be used flexibly to avoid dynamic branching.

After simplifying the process, the fragment shader code is as follows, reducing the performance overhead by eliminating dynamic branch statements and discard instructions, sacrificing the readability of part of the code, but improving the parallelism efficiency. In order to determine whether the pixel belongs to the line cap, a quadratic function is constructed. In fact, other types of functions can be constructed to achieve the purpose.

fixed4 frag (v2f i) : SV_Target { fixed4 clearColor = 0; fixed isClear = 0; fixed origin = clamp(i.geometryInfo.z, 0 ,1); IsCap = step(0, origin * (origin - 1)); Dist = fixed2(i.geometryinfo.z-origin, i.geometryinfo.w); dist = fixed2(i.geometryinfo.z-origin, i.geometryinfo.w); IsClear = step(1, dot(dist, dist)) * isCap; Return lerp(i.color, clearColor, isClear); return lerp(i.color, clearColor, isClear); return lerp(i.color, clearColor, isClear); }Copy the code

Draw the stroke of the line

After drawing a line from the previous part, it is usually necessary to make the line stroke style in order to make it easy to see. In fact, the lines shown in the previous article were all stroked for aesthetic purposes, but additional drawing is required to make the line stroked.

In order to reduce the number of vertices increase and simplify the calculation of triangulation, the same extended drawing is usually performed using the stroke line width under the drawing fill line. The stroke line width structure produces larger surfaces, so that the superposition of the surfaces formed by two lines can achieve the effect of line stroke. This scheme has a sideline width-linewidth / 2 stroke width.

The basic principles of stroke lines are described above, but in actual drawing the rendering logic can be optimized for the characteristics of fill lines and stroke lines. In practice, the following exploration has been carried out:

1. Extract the change point

It can be seen that the expansion direction of stroke line and fill line is the same when drawing, the difference is that the line width is different according to the expansion vector. Therefore, the calculation of extended vertices can be separated into vertex shaders for parallel processing, and only the extended reference vector can be calculated during data processing, which is passed into shader together with the line width information by uv structure, so that the two parts of the line can be rendered using the same Shader. But a two-part line still needs to be drawn twice, consuming two Draw calls.

2. Statistically improve to a Draw Call

Based on the thinking of vertex shader, two lines can be drawn only with the difference of vertex position and color. Therefore, Batching operation can be simulated, and the mesh data of two lines can be merged to Draw in a Draw Call. As can be seen, only the triangle index needs to be adjusted according to the number of vertices in the process of merging the two mesh, and the rest data can be directly merged.

public LineMesh CombineLineMesh(LineMesh appendMesh)
{
    int index = this.vertices.Count;
    for (int i = 0; i < appendMesh.triangles.Count; ++i)
    {
        appendMesh.triangles[i] += index;
    }

    this.triangles.AddRange(appendMesh.triangles);
    this.vertices.AddRange(appendMesh.vertices);
    this.color32s.AddRange(appendMesh.color32s);
    this.geometrys.AddRange(appendMesh.geometrys);
    this.parameters.AddRange(appendMesh.parameters);

    return this;
}
Copy the code

3. Improve the drawing method to a Draw Call

Although a Draw Call has been reached for rendering in Exploration 2, stroke line and fill line are rendered using two sets of vertices. In the spirit of saving money, in order to reduce the number of vertices, it can be considered to Draw the whole line in one set of vertices according to the proportion information of stroke line width and fill line width. This approach requires the use of geometry information introduced in the previous article to plot the rounded corners, where x information identifies the length and y value identifies the width. If ratio is defined as the ratio of line width, the render color can be determined based on the distribution of y values in the fragment shader.

Ratio = lineWidth/sideLineWidth ABS (y)∈[0,ratio] -> color ABS (y)∈(Ratio,1] -> sideColorCopy the code

It is possible to draw the stroke line using only one set of vertices, but there are some problems:

1. Concentric circle drawing logic is required in support of line caps and rounded corners, which requires the introduction of additional conditional judgment, which affects both logic complexity and performance.

2. When drawing a large number of interlaced lines, the capping order of the lines needs to be adjusted dynamically. It will encounter that all the filling parts of some interlaced lines need to capping all the stroke parts, and the line drawn at one time cannot support this effect.

To sum up, the improvement of drawing method has its limitations, and the drawing method of Exploration 2 is more appropriate.

Fixed flicker Z-fighting

After the drawing scheme is determined, the next problem encountered during the drawing is the z-fighting problem of the line, that is, the line keeps flashing when observing. The reason is that the world coordinates of the overlapping part of the stroke line and the filling line are exactly the same. After coordinate transformation, affected by the depth buffer accuracy, the pixels will pass the depth detection disordered during rendering, and finally show the problem of surface flicker.

Z-fighting is the last obstacle for drawing lines, which involves a lot of basic knowledge of graphics. In the process of exploring solutions, I have gained more understanding of the whole process of rendering. The explored solutions are summarized as follows:

1. Adjust the world coordinates of vertices

The first step to solving the Z-fighting problem is to locate the object of the deep value conflict. In the scene of drawing a line with stroke, the cause of flicker is that the world coordinate heights of the overlapping parts of the stroke line and the filling line are the same, resulting in the same pixel depth values after coordinate transformation. Therefore, a slight offset can be added to the height value of the conflicting planes, and the converted depth value can be affected by changing the local coordinates, and finally the flicker phenomenon can be seen to disappear.

As discussed above, modifying local coordinates can be done in parallel in the Shader, using Unity as an example, by setting a priority variable to fine-tune the y-direction offset of vertices, thereby controlling the display priority.

fillLineMesh.priority = 1; v2f vert (a2v v) { v2f o; float4 pos = v.vertex + float4(v.parameter.x, 0, v.parameter.y, 0) * v.parameter.z; Pos += float4(0, priority / 100, 0, 0); O.pos = UnityObjectToClipPos(pos); o.color = v.color; o.geometry = v.geometry; return o; }Copy the code

This fixes the flicker temporarily, but it still appears when the camera is pulled further away. The reason is that the accuracy of depth buffer is limited, so the farther away from the camera, the larger the offset is required. The offset of fine tuning needs to be dynamically adjusted according to the distance between the vertices and the camera. In practice, the line of sight direction and vertex fine-tuning direction are not the same in most cases. When solving z-fighting with a large number of overlapping lines, the accumulation of a large number of offset may visually observe that lines are not coplanar, which is inconsistent with the map display mode of all lines in the same plane. Therefore, scheme 1 is usually only used as a tool to preliminarily verify the cause of Z-fighting.

2. Use the Offset command

Unity ShaderLab provides the Offset instruction for fine tuning Offset. The instruction definition and calculation formula are as follows:

Offset Factor, Units
offset = m * factor + r * units
Copy the code

Where, m is the maximum value of the slope of the polygon depth calculated by the system. The more the polygon is parallel to the near clipping plane, the closer m is to 0. R is the minimum distinguishable unit of the depth value and a constant specified by the system. If the polygon is parallel to the clipping surface, the combination of factor=0 and units=1 can be used to control the Offset. For polygons that have an Angle with the clipping surface, factor is required to control the Offset together. If the Offset is greater than 0, the polygon will be Offset away from the near clipping surface. Specific parameter values need to be explored and confirmed in practice.

The problem of Z-fighting between multiple objects can be solved by using the Offset instruction to apply the depth value of the clipping space. However, when all lines are merged into a mesh to reduce the Draw Call, it cannot be used. Therefore, the depth information of different lines in the same mesh needs to be manually regulated by using its principle.

3. Adjust the clipping coordinates of vertices

The depth information is computed after the slice shader and therefore cannot be changed directly through the programmable part of the shader. But the depth information is calculated from the homogeneous coordinate of the clipping space, so the depth can be adjusted by manipulating the coordinate of the clipping space.

Before rasterization, the coordinates are transformed from local coordinates to clipping coordinates by model-view-projection transformation. The homogeneous coordinates of the clipping space are obtained from the projection matrix transformation of the observation space, and the NDC coordinate Z value obtained by the transformation to screen space is obtained from the z/ W of the homogeneous coordinates, which determines the depth value. The following parameters are required to transform from observed space coordinates to clipping coordinates:

F: Far cut surface

N: Near clipping surface

Fov: perspective

Aspect: Camera aspect ratio

Let the observation space coordinate be ，

Then transform to the clipping space coordinates as:

According to the depth value rule, add the offset of -z*offset to the clipping coordinate Z value to fine-tune the depth back. In the MATERIAL of UE4, you can also adjust the Pixel Depth Offset to achieve the Offset effect.

v2f vert (a2v v) { v2f o; O.p OS = float4 (UnityObjectToViewPos (float3 (v.v ertex. Xyz)), 1.0); float z = o.pos.z; o.pos = mul(UNITY_MATRIX_P, o.pos); o.pos.z = o.pos.z - z * v.parameter.z/1E8; // Use parameter.z to store vertex offset information. }Copy the code

4. Adjust depth detection

All of the above schemes solve the z-fighting problem by constructing small offsets between different faces, while another idea is to not increase offsets. By specifying the capping rules during rendering, the first drawn face is capped by the later drawn face, and finally the correct image is displayed. This approach requires an understanding of the concept of depth detection.

The depth detection is carried out after the chip shader. Each chip carries its own depth value and the depth value in the depth buffer for comparison detection. If the detection passes, the value in the depth buffer will be set to the depth value. If the detection fails, the element is discarded. Unity ShaderLab uses the ZWrite and ZTest instructions to control this process:

• ZWrite Controls whether to write the chip depth into the depth buffer after the detection passes. This function is enabled by default (ZWrite On)
• ZTest defines the rule that the depth value passes the depth detection. The default is that the depth value passes the depth detection when the chip depth value is less than or equal to the depth value in the depth buffer (ZTest LEqual).

In the case of 2d map drawing, there is no need to change the writing strategy of depth buffer, only need to change the strategy of depth detection to all pass:

ZWrite On
ZTest Always
Copy the code

summary

As for the flicker problem, the core of the first three exploration schemes is to construct tiny offset. If the number of fighting faces is too much, a large number of small offset superimposed and quantitative changes are caused, which may affect the perspective display size of the graph. In this case, scheme 4 is recommended. For the case of multiple objects, scheme 2 and Scheme 4 can be used together to achieve better effect.

At this point, all the problems of drawing lines have been solved. The following image shows a path drawing using a variety of solid colors. If you are not satisfied with the result, you can also try texture mapping to make the path more cool.

Author: Atu, programmer

Link: zhuanlan.zhihu.com/p/266042561

Source: Zhihu

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.