Data processing

Before beginning development on the navigation system itself, it is essential that the provided world data is refined before use. Refinement can mean several things, but the general goals of processing are to reduce file-size, reduce required system memory, and to make internal data formats easy to work with. Data formats may differ drastically from application to application, but the general approaches outlined in this whitepaper should be broadly applicable and illustrate common concepts.

Most datasets will provide road and structure information in a simplified format, allowing the target platform to implement a custom solution for geometry representation. This will be the primary focus of this whitepaper. Some vendors may provide full 3D models and textures for use in navigation software, but most of the illustrated optimisation principles discussed can still be applied, albeit with modifications.

The sample data used in demo illustrations is largely provided by Open Street Map (https://www.openstreetmap.org). OSM is an open-source platform that creates and distributes free geographical data, which is freely available to download in an XML format.

To reduce memory usage, only essential OSM XML data is required for an application. Namely information tagged "node" or "way". To use an OSM XML file, its contents are read using a document model XML parser called pugixml, which is shipped as part of the SDK. Temporary objects are created to hold this information, which can then be loaded into the navigation system.

OSM Nodes

OSM defines a node as a single point in space which consists of a unique ID and its coordinates in space, represented by latitude and longitude. For efficient use by internal algorithms, coordinates have been converted into meters. A single node can represent things such as points of interest. Multiple nodes can be chained together to form more complex structures called "ways".

OSM Ways

OSM defines a "way" as an ordered list of nodes, used to define complex objects such as roads or buildings. Ways also commonly hold a list of tags providing extra information such as a road name. Ways can either be considered "open" or "closed". A "closed" way shares the last node with the first node, forming a circuit, such as with roundabouts. An open way is a linear feature which does not share the first and last nodes, such as a section of road.

Note: Internally, navigation software should extend the way storage structure so that instead of being represented as connected one-dimensional lines, they are converted to a triangle strip or polygon. These structures create a 2D representation of an object such as a road or building area and are essential for the rending process. As seen in the memory management section of this document, these triangle strips can be partitioned into chunks to be loaded in and rendered more selectively.