2 posts tagged with "rendering"

We have published the polygon triangulator of our map engine as a small library, earstrip, under the ISC license, the same one earcut uses. It is one C++ header, and a WebAssembly build on npm that takes the same arguments as earcut. In C++ it is 14% faster than earcut.hpp, in the browser 1.4 to 2.1 times as fast as earcut.js, and the comparison is near the end. This post is about how we got there.

A GPU fills triangles and nothing else. A map, on the other hand, is mostly polygons: buildings, parks, parking lots, the strip of grass between two tram tracks. Here are a few blocks of Śródmieście in Warsaw the way our renderer reads them from a map file, as outlines:

Before any of this gets a fill, every outline has to be cut into triangles. Hover over a polygon, or tap it, to see what it turns into. These blocks hold 331 polygons with 5,151 vertices, and they become 4,514 triangles.

Zoom level 13 of our offline map of the Masovian Voivodeship, the region around Warsaw, has 3,740,425 polygons. On one core of an M4 Pro, the constrained Delaunay triangulator in our engine needs 2.93 seconds to cut all of them. This October I replaced it with ear clipping. To write this post I rebuilt the ear clipper one idea at a time, one commit per idea, and timed every commit on those same 3.7 million polygons, so each section below ends with a number.

GLMap SDK 2.0 can raise the map into the shape of the ground. The same vector map, with its roads, labels, tracks and markers, lies on the terrain instead of on a flat plane. Here is Chamonix going from flat to 3D and back:

Terrain is one of the larger features of the GLMap 2.0 release. This post shows what an application changes to use it and how the renderer draws it.