Integration of SFCGAL Library

[lbartoletti]

QGIS Enhancement: Integration of SFCGAL Library

Date 2024/10/17
Author Loïc Bartoletti (@lbartoletti), Benoit De Mezzo (@benoitdm-oslandia), Jean Felder (@ptitjano)
Contact loic dot bartoletti at oslandia dot com, benoit dot de dot mezzo at oslandia dot com, jean dot felder 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 has a proven track record of use cases, particularly in geology and urban planning.
3. It is already well-integrated with PostGIS and GDAL, two key components in the QGIS ecosystem.
4. The integration can be implemented conditionally, allowing users to enable or disable it as needed.
5. It has minimal dependencies, with CGAL (header-only) and Boost (already required by other libraries in QGIS).
6. It is well-packaged and supported across major distributions (Windows, Mac, Linux, *BSD, etc.).
7. The integration is expected to have a low impact on the existing QGIS codebase.
8. It enables the addition of new processing algorithms and expressions, building upon existing proof-of-concept work in the QSFCGAL plugin.
9. 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.
10. In elevation profile (or for example, with geological data), the cut through intersections of several 3D volumes may be needed and are no available with GEOS.
11. As an added benefit, it provides advanced 2D functionality not available in GEOS.
12. Unlike GEOS) which drops Z/M, SFCGAL can handle Z computations (distance, 3D algorithms, etc.) and potentially M and nD.
13. In the elevation profile tool we sometimes have to hack the geometries to compute the intersected geometries.

Proposed Solution

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

1. Create a new QgsSfcgalEngine class that inherits from QgsGeometryEngine.
2. Implement a QgsSfcgalGeometry class that inherits from QgsAbstractGeometry.
3. Add a CMake option ENABLE_SFCGAL to allow conditional compilation of SFCGAL support.
4. Implement new processing algorithms and expressions that leverage SFCGAL's capabilities.
5. Ensure proper handling of 3D geometries, including TIN and PolyhedralSurface, in accordance with OGC standards.

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.

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

[rouault]

+1

Questions:

• What exactly QgsSfcgalGeometry represents/does? (related to point "2. Implement a QgsSfcgalGeometry class that inherits from QgsAbstractGeometry.)
• Perhaps related to above question: do you intend to have geometry classes specific of solids/volumes that would require SFCGAL ? In which case, the optional dependency on SFCGAL might be tricky, and it could be easier for it to be a required one.

Slightly out-of-scope remark: for the purpose of conda-forge based QGIS builds, it could be worth that SFCGAL to be available in conda-forge. As far as I can see from https://github.com/search?q=org%3Aconda-forge%20sfcgal&type=code , it is not currently

[benoitdm-oslandia]

* What exactly QgsSfcgalGeometry represents/does? (related to point "2.  Implement a `QgsSfcgalGeometry` class that inherits from `QgsAbstractGeometry`.)

* Perhaps related to above question: do you intend to have geometry classes specific of solids/volumes that would require SFCGAL ? In which case, the optional dependency on SFCGAL might be tricky, and it could be easier for it to be a required one.

We need to implement a new daughter class of QgsAbstractGeometry to link a geometry with an instantiation of the SFCGAL engine. This allows us to optimize processings that can be chained together, by reducing the number of times an SFCGAL engine has to be recreated (and therefore to recreate SFCGAL geometry from QGIS data).

[rouault]

We need to implement a new daughter class of QgsAbstractGeometry to link a geometry with an instantiation of the SFCGAL engine

ok, so not directly a user-facing subtype of QgsAbstractGeometry but more an implementation detail?

[sebastic]

SFCGAL development is not in a healthy state. Consider contributing development and/or monetary resources to correct that before depending on it.

[rouault]

SFCGAL development is not in a healthy state.

This comment is a bit mysterious to me. Can you give more details?
Looking at https://gitlab.com/sfcgal/SFCGAL/-/releases, it has received a 2.0.0 release a few days ago and a 1.5.2 one 2 monhs ago
I see you've packaged both in Debian and looking at https://salsa.debian.org/debian-gis-team/sfcgal/-/commits/master?ref_type=heads , I can see comments like "Drop cgal6.patch, included upstream" which seems to demonstrate a good cooperation between Debian and upstream SFCGAL. So not obvious what wouldn't be healthy...

[m-kuhn]

Minor comments:

• cmake/findSCFGAL.txt there's a typo.
• joking: it would be great if sfcgal could export a package config instead so not all downstream project need to provide additional FindSFCGAL.cmake files. See https://cmake.org/cmake/help/latest/module/CMakePackageConfigHelpers.html (not a strong requirement, just a wish)
• The new QgsAbstractGeometry child class is also not yet completely clear to me (what API's would make use of that?)

[troopa81]

Great news!

I also don't see why we need a QgsSfcgalGeometry. Would that mean that we have then a QgsSfcgalPoint, QgsSfcgalPolygon... ?

At the moment, there is no direct link between geos and QgsAbstractGeometry and this is QgsGeos implementing QgsGeometryEngine which make that link. Why not keep it the same way but with a Sfcgal engine.

[troopa81]

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

QGIS has so far no direct dependencies with boost, meaning that you can build QGIS without it. Would it become a required dependency ? Would QGIS have to use boost to correctly use CGAL API? If so, do you know which part?

[sebastic]

SFCGAL development is not in a healthy state.

This comment is a bit mysterious to me. Can you give more details?

It breaks with pretty much every new CGAL release, which then takes time to get patched.

See for example the recent issue about CGAL 6 support:

What's the ETA for SFCGAL 2.x?

Time, Money and/or Contributions to bump SFCGAL with CGAL 6 (+ refacto/improvements).
So "when it's done" (c) Blizzard
https://gitlab.com/sfcgal/SFCGAL/-/issues/267#note_1973298009

Fortunately Sébastien Loriot came along and contributed the CGAL 6 support like he has done several times before, without his contributions SFCGAL would have remained broken with newer CGAL.

I've disabled SFCGAL support in PostGIS so many times now, that I won't consider enabling the dependency in GDAL, the same goes for QGIS.

[darkblue-b]

in #postgis, I have done low-level (GDB) debugging of SFCGAL .. the libraries are filled with technical debt. The SF part is only a wrapper over the old, very large, very messy CGAL project. CGAL has all the problems of a multi-generational academic project.. no one understands all of it.. there is no unified architecture, only layers of industrious graduate students, separated by the years of implementation.

Proceed with caution IMHO

[benoitdm-oslandia]

Minor comments:

* `cmake/findSCFGAL.txt` there's a typo.

Indeed 😁!

* joking: it would be great if sfcgal could export a package config instead so not all downstream project need to provide additional `FindSFCGAL.cmake` files. See https://cmake.org/cmake/help/latest/module/CMakePackageConfigHelpers.html (not a strong requirement, just a wish)

For our current test we add a FindSFCGAL.cmake which look for a package config. This is may be not the good solution, we will investigate your suggestion!

* The new `QgsAbstractGeometry` child class is also not yet completely clear to me (what API's would make use of that?)

The engine functions often return QgsAbstractGeometry as required by the QgsGeometryEngine. So if we want to call 2 successives SFCGAL operations (like QsgSfcgalEngine(geomA).triangulate().difference(geomB)) we will have to go forth and back from Qgis to SFCGAL for each call to the engine (ie. copying data and converting them to one format to another). The QgsSfcgalGeometry solves this issue by encapsulating the dedicated SFCGAL engine, the geometry in SFCGAL and Qgis formats.

[rouault]

This is may be not the good solution, we will investigate your suggestion!

I also second @m-kuhn suggestion. Dealing with CMake Config files is the way to go for clean CMake integration.
A few (non necessarily normative) examples in projects I'm familiar with:

• https://github.com/OSGeo/gdal/blob/c044df7020787c0284d6a19811ef079126c5a044/gdal.cmake#L481
• https://github.com/OSGeo/PROJ/blob/54a7662dbc52963da70303ac8c9124966f4cf6b4/cmake/CMakeLists.txt#L105
• https://github.com/OSGeo/shapelib/blob/a279d13c2db61fe58afd443d3be56a997624cdf5/CMakeLists.txt#L105

[lbartoletti]

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

QGIS has so far no direct dependencies with boost, meaning that you can build QGIS without it. Would it become a required dependency ? Would QGIS have to use boost to correctly use CGAL API? If so, do you know which part?

QGIS does not use boost, and we don't have to use it in QGIS. For packager, yes we have to install some boost-libs for SFCGAL. However, it's already the case when your system install GDAL with libkml (at least on the most used QGIS version, and maybe other sub-dependency.

[lbartoletti]

Slightly out-of-scope remark: for the purpose of conda-forge based QGIS builds, it could be worth that SFCGAL to be available in conda-forge. As far as I can see from https://github.com/search?q=org%3Aconda-forge%20sfcgal&type=code , it is not currently

I have planned, but not yet taken the time to, contribute to conda for the addition of SFCGAL (and its Python binding).
Generally speaking, whenever I can help packagers, I'm happy to do so, as we've done for Windows (vcpkg, mingw/msys2) and others *nix

[m-kuhn]

* The new `QgsAbstractGeometry` child class is also not yet completely clear to me (what API's would make use of that?)

The engine functions often return QgsAbstractGeometry as required by the QgsGeometryEngine. So if we want to call 2 successives SFCGAL operations (like QsgSfcgalEngine(geomA).triangulate().difference(geomB)) we will have to go forth and back from Qgis to SFCGAL for each call to the engine (ie. copying data and converting them to one format to another). The QgsSfcgalGeometry solves this issue by encapsulating the dedicated SFCGAL engine, the geometry in SFCGAL and Qgis formats.

How would qgsgeometry_cast work with that, which is often used to test the type of geometry?

[ptitjano]

SFCGAL development is not in a healthy state.

This comment is a bit mysterious to me. Can you give more details?

It breaks with pretty much every new CGAL release, which then takes time to get patched.

See for example the recent issue about CGAL 6 support:

What's the ETA for SFCGAL 2.x?

Time, Money and/or Contributions to bump SFCGAL with CGAL 6 (+ refacto/improvements).
So "when it's done" (c) Blizzard
https://gitlab.com/sfcgal/SFCGAL/-/issues/267#note_1973298009

Fortunately Sébastien Loriot came along and contributed the CGAL 6 support like he has done several times before, without his contributions SFCGAL would have remained broken with newer CGAL.

I've disabled SFCGAL support in PostGIS so many times now, that I won't consider enabling the dependency in GDAL, the same goes for QGIS.

I fail to see your point based on this example. I would even argue that it proves that SFCGAL development is in a healthy state. Here is my take:

• you created an issue to explain that SFCGAL does not compile with CGAL 6. At this moment, CGAL 6 was still in beta
• the maintainer quickly responded that unfortunately he did not have the resources to work on it at the moment
• A few days later, an other contributor jumped in and created a Merge Request to add CGAL 6 which was still in beta
• The maintainer quickly reviewed the MR and worked with the author to maintain CGAL 5 compatibility. The MR was then merged
• The CI has then updated to compile and test SFCGAL with CGAL 5 and 6 with the help of other contributors. CGAL 6 was still in beta
• Then, CGAL 6 was released 3 weeks ago
• SFCGAL 2.0 with CGAL support for version 5 and 6 was released last week.

To sum it up:

• the maintainer of SFCGAL is not alone, he can rely on other contributors. Besides, he responds quickly and dedicates time to review the different Merge Requests
• SFCGAL is automatically compiled and tested on different CGAL versions and on different operating systems
• The project tries to maintain backward CGAL compatibility when possible
• Release are done quickly when necessary
• All the discussions and decisions are taking place in the open

I think these are the signs of an healthy project.

Besides, the proposed integration is similar to the one already done in GDAL and its maintainer thinks that it's a good idea to add it to QGIS. I also think it is a sign that SFCGAL development is in an healthy state and that it can work and integrate well with the whole osgeo ecosystem.

[nyalldawson]

This sounds good, but I'm not at all convinced by the need for a new geometry subclass. Can you please detail EXACTLY what that would look like, including the relevant bits from it's header ?

[nyalldawson]

Sorry, missed this reply:

"engine functions often return QgsAbstractGeometry as required by the QgsGeometryEngine. So if we want to call 2 successives SFCGAL operations (like QsgSfcgalEngine(geomA).triangulate().difference(geomB)) we will have to go forth and back from Qgis to SFCGAL for each call to the engine (ie. copying data and converting them to one format to another). The QgsSfcgalGeometry solves this issue by encapsulating the dedicated SFCGAL engine, the geometry in SFCGAL and Qgis formats."

Subclassing QgsAbstractGeometry is the wrong approach to handle this. Rather you should develop some method for attaching extra objects to a geometry, allowing for sfcgal representations (and GEOS representations + prepared GEOS objects) to be attached. This should probably be done at the QgsGeometry level instead of QgsAbstractGeometry, so that we get the benefit of the implicit sharing of these representations too.

But before proceeding with this approach, please detail the actual changes to be made to the classes 👍

[nyalldawson]

Actually, thinking a bit more about this: Create a new QgsSfcgalEngine class that inherits from QgsGeometryEngine.

I'd suggest NOT doing this, and just creating the new QgsSfcgalEngine without the QgsGeometryEngine base class. That base class was originally introduced with the thinking that maybe at some stage we'd have an alternative to GEOS, but that use case has never eventuated and now the QgsGeometryEngine interface is just getting in the way. You'll see many methods in QgsGeos which aren't in the QgsGeometryEngine interface, and accordingly aren't accessible to Python (even though they'd be useful!).

In short: I think trying to keep a common interface between GEOS/SFCGAL is just a pointless exercise, and we're better off with specific classes exposing API which makes sense to each individual backend.

So I'd suggest rewording this as something like Create a new QgsSfcgalEngine class modelled off the existing QgsGeos class, but with methods which specifically relate to the SFCGAL library functionality.

[benoitdm-oslandia]

Thanks @nyalldawson for your reply! If you think, we do not need to extend the QgsGeometryEngine class, it will be simpler for us! We will rewrite asap the QEP description accordingly.

[benoitdm-oslandia]

How would qgsgeometry_cast work with that, which is often used to test the type of geometry?

good point! The suggestion made by @nyalldawson changes a lot of things, we will rework it asap.

[m-kuhn]

+1 for the adjustments suggested by @nyalldawson

[sebastic]

I fail to see your point based on this example. I would even argue that it proves that SFCGAL development is in a healthy state.

The activity and contributors graphs don't inspire confidence in the health of the project:

https://openhub.net/p/sfcgal

The fact that the SFCGAL core developers repeatedly aren't the ones that contribute the changes to make it compatible with newer CGAL is very concerning. The project has a bus factor of 1 for its ability to support newer CGAL releases. When Sébastien Loriot stops contributing those changes SFCGAL will remain broken for quite some time leading to its removal from Debian and Ubuntu releases which will require conditional logic in the QGIS packaging to enable support on the release where it's still available.

It seems that Oslandia needs to be paid to do the work to support newer CGAL releases, which is something QGIS could fund when it choses to depend on SFCGAL. SFGAL needs more developers contributing changes to improve its health and long term viability, projects that choose to depend on SFGAL like PostGIS and QGIS are obvious sources for these additional contributions.