preface

This article is the beginning of an exploration of map visualization using a game engine. Traditional map rendering is usually done on iOS/Android/Web platforms. In order to explore a cool map display, we will record the exploration process of map rendering based on UE4/Unity.

Map base elements – Lines

As a basic element of map rendering, lines can represent various forms of roads in maps. Road data is usually stored in the form of discrete points, so how to draw the points into a wide line is the most concerned problem in rendering. This paper records the method of drawing lines with width and describes the various caps and corners to optimize the line display effect.

Draw lines with width

Road data is usually stored as a string of discrete points and their corresponding line widths, which need to be expanded into wide lines for display in the game engine. UE4 and Unity can use Procedural Mesh generated code to render basic elements (UE4 uses Procedural Mesh Components, Unity uses MeshFilter and MeshRenderer), and the basic unit of Mesh is a triangle. So the problem becomes how to construct a set of triangles based on the string of points and the width of the line so that they can be pieced together to produce lines with width.

For a line with only two points, obtain the vector perpendicular to the line and extend the lineWidth/2 length in both directions to generate vertices, which can be divided into triangles.

For lines composed of multiple discrete points, there are two problems when drawing:

  • Only adjacent points are used to calculate the vertical vector, resulting in a fracture at the corner of the expanded line, as shown in the figure below. As you can see, it is not enough to expand each adjacent line segment; you also need to consider how to handle the corners of the line.

  • Consider the corner of the processing line, but the direction and size of the vertex extension vector are not correct, resulting in unequal lines drawn. The following figure determines the extension vectors according to the perpendicular lines separating the vertices, but the vectors vary with the position of the vertices, so they cannot be used as the basis for generating equal width lines.

With that thought in mind, the task becomes to extend lines of equal width and corners: the positions of the vertices separated by them change, but the vector directions determined by them remain constant, so that a unique extension vector can be determined by the unit vectors of the line segments on either side of the vertex. After determining the expansion direction, we also need to determine the size of the expansion vector so that the final line is equal in width.

The pseudocode is as follows, and the extension direction can be determined by the combination of line segment unit vectors. It should be noted that the extension length is not lineWidth/2, but needs to be calculated and adjusted according to the included Angle of line segment. After the extension vector is calculated, the vertices can be extended according to the sequence of discrete points, divided into triangles according to the vertex coordinates, and constructed Mesh for rendering.

Vec2f a = (P1-P0) * normalized() Vec2f b = (p2-P1) * normalized() Vec2f AVg = a + b Vec2f direction = Vec2f(-avg.y, Float t = Abs(Asin(a × b)) / 2 // Unit vector cross product sine of the included Angle float length = lineWidth / 2 / Cos(t) // Extend the length according to the AngleCopy the code

Draw LineCap LineCap

From the previous section, you can draw a line with width, but you can also see that the lines are rectangular at the beginning and end, which is not elegant. Therefore, this section will mainly solve the problem of drawing line caps.

There are three types of LineCap that are commonly used:

  • Butt Wireless cap mode. The line drawn in the previous section defaults to Butt
  • Round Add additional semicircles at both ends of the line with radius lineWidth/2
  • Square adds extra rectangles at both ends of the line with a height of lineWidth/2

The drawing of the line cap in Square form is relatively simple. You only need to add additional rectangles at the beginning and end according to the extension direction. The two rectangles can be easily divided into four triangles and rendered together in the line drawing mesh. The drawing of the semicircle hat in the form of Round is a lot of trouble. In practice, the following three schemes are mainly explored:

1. Use triangles to approximate semicircles

The most intuitive way is to draw the semicircle cap directly, but the smallest unit of rendering is a triangle, so the semicircle can only be approximated by adding multiple triangles. This way need to add the number of triangles, carries on the geometric operation to determine each vertex coordinates, through combination into a semicircle, triangle although the method is feasible, but in order to make smooth line cap, add more vertices and a large number of mathematical operations will effect on performance, performance and effect of trade-offs.

2. Use pictures to approximate the semicircle

The second scheme can save the steps of adding extra vertices and mathematical calculation by using pictures, and get the semicircle line cap approximately.

The image tool is 16 by 16 pixels, and the left and right parts draw a semicircle and a rectangle, respectively. For the semicircle part, the transparency of the inner points is set to 1. For the pixels covered on the arc, the jagged feel is weakened by lowering the transparency value. For the part outside the arc, the transparency is set to 0, and the approximate semicircle is constructed by using transparency as a whole. The rectangular part is used as a tool to fill the non-line cap part.

This approach is consistent with Square’s approach to line Mesh construction, but requires binding texture UV values to vertices as well. The Square line cap adds an extra rectangle bound to the left semicircular UV of the image, while the original line part is bound to the right rectangle UV. During rendering, the color value of the mapped image can be extracted pixel by pixel in the pixel shader. The output color uses the vertex primary color, but the transparency value uses the opacity value of the image, thus excluding the outer pixels of the arc. Using this scheme requires opacity blending to be turned on so that the outer pixels of the arc are not displayed.

This scheme is also an approximate representation of the semicircle. When observed at a closer distance, the arc cap will appear to be false, because it is limited by the size of the picture. If the size of the picture is increased, the problem can be alleviated, but it will also increase the cost, and it is necessary to balance the performance and effect.

3. Draw a semicircle per pixel

The third scheme is evolved from the second scheme. Instead of using pictures to eliminate pixels, it uses the characteristics of semicircle to eliminate all pixels that do not meet the conditions in the chip shader to draw pixel-level semicircle line caps. The main principle is that after the Square line cap is added, the pixel is judged to be the distance from the starting vertex of the line during rendering. If the pixel exceeds lineWidth/2 (the red part), the pixel is removed and the semicircle line cap is drawn pixel by pixel.

Pixels out will be conducted in parallel in a fragment shader, high efficiency, but should not be stored context information and eliminate logic need to retrieve information center, at the same time of the coordinates of the fragment shader has been converted to cut out space of homogeneous coordinates, to the geometric operations, so you need to transfer some auxiliary information to operate in a fragment shader.

The auxiliary information is defined as a two-dimensional vector geometryInfo, which means the relative positions of vertices in the line, with the beginning of the point string as (0,0), the end as (1,0), and the middle points converted to values between [0,1] depending on the distance. Based on the vertices obtained by extending the vector, the vector y value is assigned either 1 or -1, depending on the direction of extension. Because the relative coordinate system with line width of 2 has been artificially defined, the auxiliary information X value of the vertex on the line cap can be transformed into -1 and 2, so that any X value less than 0 and greater than 1 can indicate that the point is part of the line cap, and the distance can be easily calculated with (0,0) and (1,0), and compared with the semicircle radius 1.

The geometryInfo binding interpolates linearly in the slice shader pixel by pixel after passing the shader to each vertex, so each pixel gets an auxiliary information that identifies its local position, which is used to determine the distance for pixel elimination. Here is the Unity Shader code. UE4 can restore logic in Material.

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

The rounded corners generated by this scheme do not appear blurred or jagged when viewed up close because of the increased pixels rendered by the line cap.

Draw line corner LineJoin

After the line cap has been rounded and elegant, it is also found that there will be bad cases in the corners of the drawn lines in some extreme cases. For example, as shown in the figure below, a line with a small Angle will produce a very large sharp Angle; And the right Angle to the line segment is also displayed as a right Angle corner, not quite fruity and beautiful. This section focuses on the problem of drawing line corners.

Commonly used LineJoin mainly includes the following three types:

  • Miter pointy style, the line drawn in the previous section belongs to Miter
  • Bevel angular style, with cross sections instead of sharp corners
  • Round style, with circular arc instead of sharp Angle

With experience in drawing extension lines and line caps, it can be seen from the figure above that the Bevel and Round styles do not need to calculate extension vectors according to the Angle between line segments. After extending as a rectangle when drawing, Bevel style only needs to complete a triangle according to the extended vertices to form the section. For the Round style, in addition to the start and end points, each vertex extension draws two semicirons in the direction of the rectangle to create a Round corner effect.

The semicircle is drawn in the same way that the semicircle is drawn by adding rectangles and then removing extra pixels, so the geometryInfo needs to be expanded to a four-dimensional vector with the last two bits representing the relative positions of the vertices in the current segment. Pixel removal is also performed in the slice shader. The code logic of the fragment shader is similar to that of the rounded line cap and will not be described here. The final corner effect is shown below.

The overall drawing process can be simply summarized as the following figure, with the same width line as the main body of line rendering, and the line cap/corner as the effect optimization item of line rendering. In practice, the line cap/corner style can be easily changed by setting configuration items.

Author: Atu, programmer

Link: zhuanlan.zhihu.com/p/266026334

Source: Zhihu

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