Map text rendering

takeaway

After reading this article, you will know:

1. Commonly used methods of WebGL rendering text; 2. Strategies for camera orientation; 3

rendering

Rendering text in WebGL is not an easy task.

DOM

A simple and common way to render text is to generate HTML elements through the DOM. This method only needs to understand how a 3D coordinate point is projected to the screen coordinates, and every time the camera or coordinates change, change the coordinate or transform in its CSS style, to achieve a text effect with all DOM elements that should have CSS style.

More computing can refer to: WebGL text – HTMLwebglfundamentals.org

DOM words

This approach is suitable for scenarios where there are not many text styles required.

TextGeometry

Students who have just learned three.js will have some exotic methods, which directly generate a three-dimensional text grid through TextGeometry. The resulting effect is very three-dimensional, suitable for highlighting text display scenes, but not suitable for text auxiliary information display occasions, and the generated text grid vertices are also large.

Canvas

The more universal way is to use text map. The method of uploading texture to make text map is more suitable to do a large number of text rendering scenes. The following is an example of text Sprite diagram of early Baidu Map. The technology they use is to render the text Sprite diagram of tile tiles to the front end according to the style requirements at the back end.

Using Canvas dynamic text mapping, text needs to be rendered to a large image in order to reduce the number of texture uploads. A simple way to generate a Sprite image is to save a grid of data, record the horizontal ruler for each row of the current Sprite image, as well as the height of the row, and find the appropriate slot for each POI rendering.

Calculate texture map:

grid = [{ left, height, bottom }] const getGridRow = function (text, fontSize) { const gridLength = grid.length const tWidth = text.length * fontSize const tHeight = fontSize let rowIndex =  grid.findIndex((d, i) => { return ((canvasWidth - d.left) >= tWidth) && (d.height >= tHeight) }) if (rowIndex < 0) { const bottom = grid[gridLength - 1].bottom + height grid.push({ left: 0, bottom: bottom, height: height }) rowIndex = gridLength } return grid[rowIndex] }Copy the code

For each POI, maintain a copy of its coordinates range on the Sprite diagram: starting coordinates and width and height to calculate its UV. The text height was measured using fontSize, and the text width was measured using measureText.

Const getPoiUvOffset = function (text, fontSize) {const fontSizeBuf = fontSize * 1.2 const row = getGridRow(text, fontSizeBuf) ctx.font = fontSize ctx.textBaseline = 'middle' const tHeight = fontSizeBuf const tWidth = ctx.measureText(text).width const poi = { text: text, startX: row.left, startY: row.bottom - fontSizeBuf, width: tWidth / 2, height: tHeight / 2 } ctx.fillText(poi.text, poi.startX, row.bottom - tHeight / 2) return [ startX / canvasWidth, 1 - startY / canvasHeight, tWidth / canvasWidth, tHeight / canvasHeight const getPoiUvOffset = function (text, Const fontSizeBuf = fontSize * 1.2 const row = getGridRow(text, fontSizeBuf) ctx.font = fontSize ctx.textBaseline = 'middle' const tHeight = fontSizeBuf const tWidth = ctx.measureText(text).width const poi = { text: text, startX: row.left, startY: row.bottom - fontSizeBuf, width: tWidth / 2, height: tHeight / 2 } ctx.fillText(poi.text, poi.startX, row.bottom - tHeight / 2) return [ startX / canvasWidth, 1 - startY / canvasHeight, tWidth / canvasWidth, tHeight / canvasHeight ] }] }Copy the code

When making Sprite text images, we found that different browsers have slightly different representations of the baseline. If fontSize is used highly, it is easy to see text with “heads” chopped off or “feet” chopped off. Therefore, when calculating Sprite text, we will use middle alignment, with line spacing *1.2 times, to leave a buffer for browser compatibility.

Character set

In addition, for English limited enumerable character scenes, character set methods are usually used, that is, upload all character textures at one time, record the positions of all characters, and splice character by character to achieve the effect when rendering the text. The advantage of this method is that once the texture map is generated, it does not need to be updated, but when zoomed in, it will appear to be more blurred.

SDF

SDF (directed distance field) characters are often used in geographical scenes to solve the problem of sharpness when characters are scaled. SDF’s approach is designed to solve the problem of text rendering at all scales with a smaller number of pixels. To be specific, the distance field is used to record the distance between each point and the edge of the pixel grid. The symbol is external negative and internal positive, so the edge of the character is described by the vector distance. In the shader, the edge can be easily resolved by smoothstep.

lowp vec4 color=fill_color; highp float gamma=EDGE_GAMMA/(fontScale*u_gamma_scale); Lowp float buff = (256.0 64.0) / 256.0; if (u_is_halo) { color=halo_color; Gamma = (1.19 / SDF_PX + EDGE_GAMMA halo_blur *)/(fontScale * u_gamma_scale); Buff = (6.0 - halo_width/fontScale)/SDF_PX; } lowp float dist=texture2D(u_texture,tex).a; highp float gamma_scaled=gamma*gamma_scale; highp float alpha=smoothstep(buff-gamma_scaled,buff+gamma_scaled,dist); gl_FragColor=color*(alpha*opacity*fade_opacity);Copy the code

For the SDF generation method, see github.com/mapbox/tiny… .

Using the SDF method, you also need to generate a character set. Here is the SDF character set for Amap.

Amap character set

On the whole, the SDF approach works well when fonts are large, but it makes corners too smooth when fonts are small. In our business scenario, POI is usually no more than 20px, and the commonly used Chinese character set is 5000+. If the final character set is 32px, five character sets of 1024* 1024 are required. Therefore, after a brief attempt with SDF method, It uses the method of rendering the font twice as large on Canvas.

POI towards

POI needs to always face the camera like Billboard, and the fontSize entered by the user is usually a pixel value. When calculating the grid surface, it needs to convert its 3D coordinates to screen coordinates and dimensions in the VS part.

We represent all the vertices of the grid surface by (0,0), and attach an anchor value to represent the stretching direction of its 4 vertices, so the final vertex position of one surface is vec2(position) + vec2(anchor) * vec2(width, height). The following vertex transformation is obtained:

vec4 projected_position = projectionMatrix * modelViewMatrix * vec4(position.xyz, 1.); Gl_Position = vec4(projected_position.xy/projected_position.w + (a_anchor * a_size) * 2.0 / u_resolution, 0.0,1.0);Copy the code

Vertex calculation method

Collision detection

POI text generated by Canvas map is pasted onto the Mesh in 3d scene in the form of texture, and finally converted into 2d coordinates towards the screen in shader. The POIS in the map scene are crowded and overlapping. This requires some collision detection to hide overlapping POIs.

In the figure, red characters are POI and white characters are road names. Before collision detection, there will be many overlapping situations between the text, which will affect the reading experience; After collision detection, it looks orderly and the experience is better. Next, we introduce the algorithm of collision detection and the optimization of display effect.

algorithm

Each text has a rectangular bounding box, which can be rotated, and whether the text is visible on the map can be determined by detecting whether there are collisions between these bounding boxes. Maintains an array visibleArray that stores text that can be displayed on a map. On the map, start with the first text, and store the first text in visibleArray; In the future, every time I place new text, I will do collision detection with visibleArray Chinese text. If there is a text in A0 that collides with this text, the text cannot be visible on the map. Otherwise, the text will be visible on the map and placed in visibleArray.

TextCollision (texts) {const visibleArray = [] // Store visible text for (let I = 0; i < texts.length; i++) { if ((i === 0) || (! visibleArray.some(item => isCollision(texts[i].bbox, Item)))) {// The first text or text that does not collide with the already visible text is marked as visible texts[I]. Visible = true Visiblearray.push (texts[I])}}}Copy the code

To implement isCollision(), we need to know the three relationships of bounding boxes:

Text collision detection is to detect whether there is an inclusion and intersection relationship between text bounding boxes.

Detection of inclusion relation

If a bounding box is inside another bounding box, then all four vertices of the bounding box are inside the other bounding box.

If the conditions are met:

(0 < dot(PV0,V1V0) < dot(V1V0,V1V0)) && (0 < dot(PV0,V3V0) < dot(V3V0,V3V0))
Copy the code

So point P is inside rectangle V0V1V2V3.

Check four vertices. If all four vertices meet the above conditions, then the two rectangles have an inclusive relationship.

/ / function isPointInRect (rect, P) {const [V0, V1, V2, const [V0, V1, V2, const [V0, V1, V2, const [V0, V1, V2, const] V3] = rect.getVertexes() return (0 <= dot(PV0, V1V0) <= dot(V1V0, V1V0)) && (0 <= dot(PV0, V3V0) <= dot(V3V0, Function getContainedVertexesNum (V3V0))} /** * getContainedVertexesNum (V3V0))} rect1) { const vertexes1 = rect1.getVertexes() let count = 0 for (let i = 0; i < vertexes1.length; i++) { if (isPointInRect(rect0, Vertexes1 [I]) {count++}} return count} / / function isContained (rect0, rect1) { return (getContainedVertexesNum(rect0, rect1) === 4) || (getContainedVertexesNum(rect1, rect0) === 4) }Copy the code

If two rectangular bounding boxes intersect, the two rectangles can detect at least one set of edges intersecting. If segment AB intersects CD, points A and B must be on both sides of segment CD, and points C and D must also be on both sides of segment AB.

If the conditions are met:

cross(ab, ac) * cross(ab, ad) <= 0
Copy the code

So point C and point D are on either side of line segment AB.

If both:

(cross(ab, ac) * cross(ab, ad) <= 0) && (cross(cd, ca) * cross(cd, cb) <= 0)
Copy the code

So line segment AB intersects line segment CD.

Test whether the rectangular bounding box edge intersects:

/ / function isRectIntersect (rect0, rect1) { const borders0 = this.getBorders() const borders1 = rect.getBorders() for (let i = 0; i < borders0.length; i++) { for (let j = 0; j < borders1.length; j++) { if (isLineIntersect(borders0[i], Borders1 [j])) {return true}}} return false} */ function isLineIntersect (line0, line1) { const v0 = { x: line0.v1.x - line0.v0.x, y: line0.v1.y - line0.v0.y } const v1 = { x: line1.v1.x - line1.v0.x, y: line1.v1.y - line1.v0.y } const ret0 = cross(v0, line1.v0) * cross(v0, line1.v1) <= 0 const ret1 = cross(v1, line0.v0) * cross(v1, line0.v1) <= 0 return ret0 && ret1 } function cross (v0, v1) { return v0.x * v1.y - v0.y * v1.x }Copy the code

The isCollision() function can finally be implemented as:

Rectangular whether collision / * * * * / function isCollision (rect0 rect1) {return isRectIntersect (rect0 rect1) | | isContained (rect0, rect1) }Copy the code

Collision detection optimization

Collision detection is very time-consuming and seriously affects user experience. We have optimized it from the following aspects.

Reduce the amount of text data to perform collision detection

Reducing the amount of text can be done from two aspects: one is to set which text types need to be displayed at different levels in the map style editor, and the other is to develop a text reduction strategy.

At different levels, people pay attention to different texts. For example, at a lower level, people only pay attention to high-speed names, national road names, etc., and at a higher level, they pay attention to more specific road names, such as village road names. During the style configuration, you need to set which level to display which type of text, and then the text displayed in the style configuration will be filtered in the next step.

Collision detection timing

The first collision detection occurs after all tiles in the current screen are loaded, and then the collision detection is performed after all tiles are loaded in each scene accompanied by the replacement of new and old tiles.

When users interact, text collision detection is not necessary during the interaction, but at the end of the interaction, collision detection is carried out.

conclusion

After the above optimization of reducing the amount of data and collision detection timing, the time of each collision detection is reduced from 100ms to less than 10ms, which improves the user interaction experience.

Text background color

The text drawn with canvas always has a lingering black edge, which has nothing to do with canvas and is presumably caused when the texture is uploaded.

To solve the black edge problem, we need to accurately identify the boundary between the word and the background. Assuming that the background is black (0x000000), then two specific colors represent the fill color and the border color respectively, so that the boundary can be accurately found and used for color mixing. This method needs to adjust the text filling method from canvas to FS. We use the G channel to distinguish the filled and border colors of the word, and the R channel to distinguish the filled and non-filled parts of the word. So there is:

vec4 textColor = texture2D( texture, uv );
vec4 fontColor = mix(v_strokecolor, v_fillcolor, textColor.g);
fontColor.a *= fontColor.r;
Copy the code

Where fontColor is combined with g channel, mixed fontColor, its transparency by multiplying the texture color r value, get the font boundary, and outside the boundary is not displayed.

In some scenarios, you also need to give the text some background color, background image.

This requires simulating the process of rendering a transparent object from back to front in a shader, the color blending theory.

Color blending formula by formula:

We can get:

vec3 rgb = mix(backgroundColor.rgb * backgroundColor.a, fontColor.rgb, fontColor.a);
float a = fontColor.a + backgroundColor.a * (1. - fontColor.a);
vec4 color = vec4(rgb / a, a);
Copy the code

The reason for the final division is that the font color has transparency, and the background color also has transparency, so the superimposed color should also have transparency.

With this mixed logic, you can add whatever you want to the end of the text, like a background image:

So much for text rendering. At the end of the day, vector fonts (SDF) are a very popular way to render fonts. The optimization of collision detection can also be done in worker, or the calculation of detection can be divided into multi-frame calculation to avoid blocking UI. A variety of optimization methods, interested friends can discuss ~

Please look forward to the next issue: Map Architectural Rendering

Review past

Creating a Cool 3D Map Visualization Product for B-end Clients

Data Sources and Stored Computing

Map Interaction and Pose Control