preface

Drawing basic Map Elements in UE4/Unity — Line (Part 1)

Drawing basic Map elements in UE4/Unity — Line (Part 2)

Once you’ve done the drawing lines, it’s time to draw surfaces and volumes:

As one of the basic elements of map rendering, the surface can represent various forms of areas in the map, such as sea surface, green space, etc. Surface data is usually stored as a string of discrete points, so the main concern in rendering is how to present it as a closed graph.

Volume can be understood as a surface with height, representing various buildings in maps, usually from their top surface data and height data processing.

This paper records the process of drawing surface and volume and the scheme of solving flicker problem.

Draws a polygon area surface

Surface data is usually stored as a series of discrete points, and surface drawing is similar to line drawing. The basic unit for rendering is triangles, lines are rendered by constructing triangles by extending line widths, and faces are rendered by splitting polygons into multiple triangles.

The process of splitting into triangles is called triangulation. Ear Clipping is the commonly used triangulation algorithm, and earcut of Mapbox is a mature scheme. For a polygon with [formula] vertices, its time complexity is [formula]. Any subdivision method can be used to render the surface, but small triangles tend to make the same pixel in the surface drawn many times, resulting in Overdraw. Therefore, some subdivision order adjustment according to the characteristics of polygons can be used as an optimization point.

Once the color of each vertex is specified, the finished polygon region can be divided into solid colored faces. Similar to the z-fighting problem of lanes, zones also need to deal with the same height overlay display. At the same time, the two-dimensional path and the regional plane are also at the same height, so it is necessary to uniformly consider the hierarchical relationship and place all the path on the regional plane. Unified processing can be completed to get a two-dimensional map baseplate.

Draw polygonal building blocks

After the two-dimensional map board is completed, it is the turn of the building blocks on the map. In order to reduce the amount of data, the usual storage method is the top point string and its corresponding pull-up height, adding vertices to form closed body during rendering.

The rendering process of the top surface is consistent with the surface of the closed area, while the side is drawn according to the height of the building. A rectangle is rendered between each two adjacent vertices to form the side of the closed body. In order to reduce the number of drawing, only the side facing the outside is usually drawn, while the bottom can not be seen from the normal perspective.

The rendering of the building body only has more sides generated by elevation than the area surface, and the logic is relatively simple. After processing all the triangle data, the rendering can be completed by configuring the vertex color.

Weird building block Z-fighting issues

Theoretically, the top surfaces of the building data usually don’t overlap, so there is no z-fighting after unplugging the render, but oddly enough, some bodies still have side flicker issues after rendering. Through the investigation of the whole link, the problem was found to be polygon data.

There is a prerequisite for triangulation: the object must be a simple polygon, meaning that any two sides of the polygon can only intersect at the vertex. Polygons in figure (a) are simple polygons that meet the definition. Polygon edges 01 and 23 in Figure (b) intersect at non-vertices and are therefore non-simple polygons.

For non-simple polygons, using triangulation can only get satisfactory results, but can not guarantee its correctness. As can be seen from the triangulation result of the non-simple polygon formed by four vertices in the figure below, vertices will be lost and wrong triangles will be generated during polygon rendering, which cannot restore the real data.

According to this idea, edge intersection detection is carried out on the existing data, and a small part of polygons are indeed not simple polygons. While the elevation of the body element draws a rectangle between each set of adjacent vertices based on the original data, thus causing problems. Taking the non-simple polygon (b) mentioned above as an example, side 12 is pulled up to generate rectangle 1245, and side 23 is pulled up to generate rectangle 2364. The two side rectangles overlap completely on face 1245. When different textures are affixed to the facade, z-fighting phenomenon will occur. At the same time, because the facade is only drawn towards the outside, face 1245 disappears when viewed from the opposite side, creating a very strange effect.

There are three easy solutions to this problem:

1, direct filtration, simple and crude.

2. Calculate external rectangles according to polygons to reduce details

3. Eliminate redundant vertices according to triangulation results and regenerate simple polygons

The above three schemes keep the details of polygons from less to more, but they do not completely restore the real data. Especially for some complex buildings, errors in one aspect will result in incorrect renderings of the final assembly. Therefore, the ideal approach is to repair non-simple polygons, break them up into multiple simple polygons, and render them separately to restore the details.

Simple polygon determination and repair

Given the definition of a simple polygon, it’s easy to think of a violent solution: oneEdges areEdges. Each edge only needs to be associated with the othersThe purpose can be achieved by judging whether the non-adjacent edges intersect, and its time complexity isIs sufficient for static data that only needs to be cleaned once. However, for dynamic data that needs to be processed in real time, it needs to traverse all combinations, especially for the case that there may be only a few intersection points, so redundant calculation is too much, so it can be introducedIntersection decision algorithm with lower time complexityProcess.

For a non-simple polygon, after splitting it into multiple simple polygons, it is enough to draw all shapes with non-zero area. This scheme maximizes original data recovery and avoids flicker problems.

summary

Once the flicker problem caused by data is solved, the sides and top surfaces of the building can be decorated with solid color or texture maps, and decorated with sky boxes and some solid color elements, which can simply imitate the effect of the city. However, under the current pull-up rendering method of buildings, architectural details can only be expressed in the form of maps. If finer effects are needed, such as glass window structures and rooftop facilities, additional triangles are needed to present them.

Author: Atu, programmer

Link: zhuanlan.zhihu.com/p/266870185

Source: Zhihu

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