Skip to content

Latest commit

 

History

History
199 lines (109 loc) · 10.4 KB

qep-340-SFCGAL-integration.md

File metadata and controls

199 lines (109 loc) · 10.4 KB

QGIS Enhancement: Integration of SFCGAL Library

Date 2024/10/17 Author Loïc Bartoletti (@lbartoletti), Benoit De Mezzo (@benoitdm-oslandia), Jean Felder (@ptitjano), Julien Cabieces (@troopa81) Contact loic dot bartoletti at oslandia dot com, benoit dot de dot mezzo at oslandia dot com, jean dot felder at oslandia dot com, julien dot cabieces at oslandia dot com Version QGIS 3.XX

Summary

This enhancement proposal outlines the integration of SFCGAL (Simple Features for Computational Geometry Algorithms Library) into QGIS. SFCGAL is an open-source library that provides advanced 3D geometry capabilities and is already well-integrated with PostGIS and GDAL.

This integration aims to enhance QGIS's 3D geometry (and 2D advanced) processing capabilities, particularly for applications in geology and urban planning.

Background and Motivation

SFCGAL offers several compelling advantages for integration into QGIS:

  1. It is the only open-source and OSGeo-compliant library capable of handling 3D geometry operations.

  2. It handles, by default, geometry data as fractions of integers instead of decimal numbers to gain performance and precision

  3. It has a proven track record of use cases, particularly in geology and urban planning.

  4. It is already well-integrated with PostGIS and GDAL, two key components in the QGIS ecosystem.

  5. It is well-packaged and supported across major distributions (Windows, Mac, Linux, *BSD, etc.).

  6. It has minimal dependencies, with CGAL (header-only) and Boost (already required by other libraries in QGIS).

  7. The integration is expected to have a low impact on the existing QGIS codebase and can be implemented conditionally, allowing users to enable or disable it as needed.

  8. It enables the addition of new processing algorithms, expressions and advanced 2D functionalities not available in GEOS. See the proof-of-concept work in the QSFCGAL plugin.

  9. It brings the possibility to have 3D analyst toolbox as other 3D softwares

  10. It supports 3D calculations and adheres to OGC standards for TIN and PolyhedralSurface (including SOLID: BrepSolid). Today, we have to implement hacks for some operations and some are not possible to reimplement in QGIS. This is one of the reasons why SFCGAL is used in PostGIS and GDAL.

  11. Unlike GEOS which drops Z/M data, SFCGAL can handle Z calculations (distance, 3D algorithms, etc.) and potentially M and nD. For example, in the Elevation Profile tool, it is sometimes necessary to hack the calculation of intersecting geometries due to the removal of Z/M data.

  12. Also in the elevation profile tool (for example, with geological data), the cut through intersections of several 3D volumes is not available with GEOS but is available in SFCGAL.

  13. A last example workflow: operations may fail with GEOS (by using a decimal geometry data) but will succeed with SFCGAL (by using a fration kernel and preserving precision).

Proposed Solution

The integration of SFCGAL into QGIS will involve the following key components:

  • CMake flag to enable/disable SFCGAL compilation
  • stateless class QgsSfcgalEngine
  • geometry cached class QgsSfcgalGeometry

CMake

We plan to add a CMake option WITH_SFCGAL to allow conditional compilation of SFCGAL support.

QgsSfcgalEngine

We propose to create a new low-level stateless class QgsSfcgalEngine. This class will bind the SFCGAL C library structures and functions in the QGIS code base. It will also provide memory and error management tools.

This class will not be available in Python.

QgsSfcgalGeometry

We propose to create a new high-level class QgsSfcgalGeometry to expose SFCGAL functions to QGIS in a similar way to QgsGeos.

This class will produce geometry objects in the SFCGAL format and also functions to convert them back and forth to QgsAbstractGeometry.

By keeping the SFCGAL geometry object during the whole object life, we can chain SFCGAL operations bypassing the need to transform geometries from/to SFCGAL/QGIS and thus we can continue to perform operation using the CGAL fraction computation kernel.

This key feature will enable more efficient processing in terms of time and accuracy.

For example we can chain calls to QgsSfcgalGeometry without losing precision:

QgsSfcalGeometry poly2D_A(myWKTStringA);
QgsSfcalGeometry poly2D_B(myWKTStringB);
QgsSfcalGeometry poly3D_A = poly2DA.extrude(5);

QgsSfcalGeometry intersection = poly3D_A.intersection( poly2D_B.extrude( 5 ) );

As it was previously discussed, we don't plan to make QgsSfcgalGeometry inherit from QgsGeometryEngine because the different set of algorithm offered by GEOS and SFCGAL would imply a different API, and we see no advantages in having a common interface.

This class will be available in Python.

Integration into QgsGeometry

At first, there is no plan to use SFCGAL algorithm within QgsGeometry. But some geometry functionalities in QgsGeometry are limited with GEOS due to Z/M drop or unmanaged kind of geometries (TIN, SOLID, etc.). Theses functionalities could be improved by using SFCGAL. To do so, some functions (like intersects, intersection, buffer (2D), offset, convexhull, combine, difference) will have an extra parameter to set the backend. The backend parameter will be an enum with values in [GEOS, SFCGAL].

Others functions will be dedicated to SFCGAL (like buffer3D, centroid3D, area3D or Constrained Delaunay Triangulation Simplification) and others dedicated to GEOS.

In case the functionality is available in both backends but there is no need to actually expose a particular backend (bug or inefficiency), the choice will be made to expose only one backend.

Use cases that leverage SFCGAL's capabilities

Implement new processing algorithms and new expressions

Cross section extraction

The 3D intersection algorithm can be used in the elevation tool to extract the cross section data even when the capture curve has multiple segments.

Medial axis 2D

SFCGAL can calculate the centre line in longitudinal direction for 2D polygon features (e.g. road axis):

Straight skeleton extrusion

One features in SFCGAL is the ability to generate “false” roofs by extruding the straight skeleton of a polygon. Methods to convert 2D building footprints into 3D existed previously, but the quality and efficiency of the algorithm provided by CGAL allow for a significantly more effective solution for this use case, ensuring a precise and functional roof design.

Here is a example to do this operation:

QgsVectorLayer outputLayer;
for (auto feat: features) {
    QgsSfcgalGeometry building (*feat.geometry().constGet());
    QgsSfcgalGeometry polySurf = building.extrudePolygonStraightSkeleton(feat.attribute("build_height").toDouble(), feat.attribute("roof_height").toDouble());

    QgsFeature outFeat;
    outFeat.setGeometry(QgsGeometry(polySurf.asQgisGeometry()));
    outputLayer.addFeature(outFeat);
}

Visibility algorithms

These algorithms enhance the capability to analyze visibility between geometric objects; a crucial feature in a wide array of applications, from urban planning to robotics.

These algorithms enable determining visible areas from a point or an edge, as illustrated in the following example.

Deliverables

  1. Implementation of QgsSfcgalEngine and QgsSfcgalGeometry classes.

  2. CMake configuration for conditional SFCGAL support.

  3. A set of new processing algorithms and expressions that utilize SFCGAL functionality.

  4. Documentation for developers and users on how to use SFCGAL features in QGIS.

  5. Unit tests to ensure proper functioning of the SFCGAL integration.

Affected Files

  • src/core/geometry/qgsgeometryengine.h

  • src/core/geometry/qgsabstractgeometry.h

  • src/core/geometry/qgssfcgalengine.h (new file)

  • src/core/geometry/qgssfcgalengine.cpp (new file)

  • src/core/geometry/qgssfcgalgeometry.h (new file)

  • src/core/geometry/qgssfcgalgeometry.cpp (new file)

  • CMakeLists.txt

  • cmake/findSCFGAL.txt

  • Various files in the src/analysis directory for new processing algorithms

  • Various files in the src/core/expression directory for new expressions

Risks

  1. Potential increase in build complexity due to the additional dependency.

  2. Low: Maintenance burden of keeping SFCGAL integration up-to-date with future QGIS versions. Like other dependencies.

  3. Thread safety: CGAL is mainly thread safe and SFCGAL is just the simple feature overhead. It has no static nor global variables. The library can be called with multiple thread to create geometries or to retrieve data from the same geometry object. But concurrent calls to modify the same geometry object will result in unexpected behaviour.

Performance Implications

The performance impact is expected to be minimal for users who do not enable SFCGAL functionality. For those who do use SFCGAL features, there may be a slight increase in memory usage and processing time for complex 3D operations. However, this is offset by the significant capabilities gained in 3D geometry processing.

Further Considerations/Improvements

  1. Explore the possibility of extending QGIS's 3D capabilities to leverage SFCGAL's 3D geometry support.

  2. Consider developing a dedicated SFCGAL toolbox in the QGIS processing framework.

  3. Investigate potential synergies between SFCGAL and other QGIS components.

Backwards Compatibility

The proposed implementation should not affect existing QGIS functionality. All SFCGAL-related features will be optional and can be disabled at compile-time or runtime. Existing GEOS-based geometry operations will remain unchanged.

Issue Tracking ID(s)

(To be assigned upon acceptance of this proposal)

Funded by: CEA/DAM @renardf, CP4SC/France Relance/European Union