Skip to content

The what and the why

What is Cassini

Cassini is a software that generates highly accurate topographic maps from LiDAR data and Shapefile vector data. The maps produced by Cassini follow the ISOM Specification , witch is one of the most detailed specification for topographic maps.

This project is heavily inspired by Karttapullautin and Terje Mathisen’s pipeline for generating orienteering maps. Unlike them, it uses PDAL (The Point Data Abstraction Library) and GDAL (The Geospatial Data Abstraction Library) to preprocess the LiDAR data.

Why does Cassini exist

Cassini is developped to be the main rendering engine for the Mapant.fr project. The project goal is to generate the most precise topographic map of France out of freely available LiDAR data and Shapefile data. It is inspired by its predecessors:

All of these projects somehow used Jarkko Ryyppö’s awsome Karttapullautin original Perl program to generate the map (at the exeption of Mapant.ch that used the OCAD mapping software). Now that Karttapullautin has been rewritten in Rust by Raphaël Stefanini, the performances are better than ever.

However, there is some reasons that pushed me to develop my own rendering engine for Mapant.fr.

The point cloud reading bottleneck

A LiDAR file is basically just a list of millions of 3 dimensions points (with some metadata). To process it, a program should at some point loop over all these points, witch is very time consuming. Karttapullautin uses the popular las Rust library to do so. For some reason (that I ignore), this library performs worst than the C++ equivalent programs ( PDAL , The Point Data Abstraction Library or LASTools ).

The edges artifacts problem

The surface area of France is 551,695 square kilometers. This means that there is 551,695 one kilometer large tiles to process to generate the Mapant.fr map. This is way too much work for one computer, so it should be distributed on several machines.

To easily distribute the computing, a worker node should be able to render one tile after another independently. But this is easier said than done because of the edges artifacts problem.

An exemple of a LiDAR generated map with artifacts on the edges

On the right border of the LiDAR generated map above, you can see artifacts on contours and vegetation. There are artificially more formlines, and there is a thin vertical white band. This is because the contours and the vegetation generation algorithms need to know about the close neighborhood of a cell during computing, and this neighborhood is incomplete at the edges of a LiDAR file.

To remedy this problem, a classic approach is to add a buffer to every tiles:

  • You download the 8 adjacent LiDAR tiles.
  • You generate a new LiDAR tile with a 200 meters buffer all around it.
  • You generate the map for this tile (for example with Karttapullautin ).
  • You crop the resulting image to the original tile extent

A schema of a tile extent with a 200 metters buffer

This way the artifacts are cropped away from the resulting image. This technique has the advantage of being simple. However, it is very inefficient. The problem is that:

  • All the points of the 9 tiles (the targeted tile and the 8 adjacent ones) have to be read to create the buffered tile.
  • Then, all the points from the buffered tile have to be read again during the map generation.

As mentioned in the previous paragraph, reading LiDAR points is very time consuming. It takes up a large part of the calculation time. With this approach, 10 times more points have to be read, compared to if you could just directly process the original tile without buffer.

The Cassini approach

Cassini is designed to adress these two problems. To improve the point cloud reading speed, it simply uses the PDAL library to read and preprocess the LiDAR data.

To solve the edges artifacts problem, it uses a much more efficient approach than the one described above. First, all LiDAR tiles are processed once with PDAL . During this step, the program produces temporary files that are not subject to the edges artifacts problem:

These rasters are not subject to the edges artifacts problem because:

  • The tile’s extent area is clipped to one meter by one meter cells.
  • A value is attributed to each of these cells depending only on the points that it contains.
  • Thus the value does not depend on the neighborhood of the cell.

In a second step, Cassini generates the final map from these rasters . It uses the Digital Elevation Model to generate contours and cliffs, and the vegetation density rasters to generate the vegetation map.

To prevent edges artifacts, a buffer is added to these rasters using the 8 adjacent rasters . Then the map is generated and the artifacts are cropped away from the resulting image. The key difference is that the buffer is added to the intermediary raster files, and not to the LiDAR files at the begining. As these rasters are much smaller and much faster to read than the LiDAR files, it drastically reduces the total computing time.

With this approach, each LiDAR point is only read once, during the fist step to generate the intermediary raster files. In the approach described in the paragraph above, There are 10 times more points to read to generate a single tile:

  • The points from the processed tile and the 8 adjacent ones are read to generate a LiDAR tile with a buffer.
  • The points of this LiDAR tile are then read once again to generate the map.

The tradeoffs

As mentioned, Cassini uses the PDAL and the GDAL libraries to process LiDAR and raster data. These libraries are very fast and efficient, but they are implemented in C++. As for now, their is no stable integration in the Rust programming language for PDAL and GDAL . Thus, they should be installed separately on the computer (using Miniconda). This is much more complexe and less beginner friendly than Karttapullautin for example, that is a standalone program with no external runtime dependencies.

Alternatives to Cassini

Karttapullautin

Karttapullautin is the project that inspired Cassini. It is an all-in-one tool to generate highly accurate topographic maps from LiDAR data and Shapefile data. It originally was implemented in Perl by Jarkko Ryyppö, but has recently been rewritten in Rust by Raphaël Stefanini. It is pretty simple to start with, with a lot of configuration and customisation possibilities. It is however a Command-Line Interface (like Cassini), so it requires using a terminal.

Terje Mathisen’s pipeline

In 2013, Terje Mathisen wrote an article about a pipeline he developed to generate maps from LiDAR data. Being an orienteering mapper, his main goal was to output a base map to help him during his mapping surveys. His pipeline uses the LASTools library to preprocess the LiDAR files, the same way that Cassini uses PDAL to do so. LASTools being a licenced software, it constraints the usage of this pipeline. However, the accompanying article is very interesting by explaining the process step by step.

OCAD

The OCAD mapping software supports map generation from LiDAR data in its latest versions. Unlike the previously mentioned tools, OCAD is a desktop application with a Graphical User Interface (GUI). It makes it accessible to users with less knowledges of Computer Science and programming. However, OCAD is a licenced software.