The opaque nature of all the machine learning today has made me appreciate analytic algorithms more. For a number of years I've been exploring 2D representation using triangulations [1]. Working with analytic algorithms is like playing around with synthesizers whereas ML is more like using a sampler.
I love the ReadMe of your project. It is like the other extreme when compared with Geogram. I tried to find out what Geogram was about and what it does better but I lost interest before I could find out. The ReadMe needs some work and the wiki didn't seem much better at first glance. You already have to know what you are looking before using Geogram.
Ooohh yes, I need to do some work on Geogram's readme (targeted towards a super-specific audience of folks who know already what they are looking for there, you are perfectly right).
The algorithms are awesome. For instance, their Delaunay tetrahedralization algorithms are state of the art, in terms of both accuracy and performance.
However, software engineering and API design could have been much better. That’s not quite a library IMO, it’s a large OO-based framework. Geogram implements stuff like logging, multi-threading, reference counting, class factories, memory management, asserts, Boolean type, atomics, and more. This makes it relatively hard to integrate, especially for Windows OS where the OS kernel is very different from all others.
This is an under-discussed problem with C++, the lack of a granular package manager leads to huge numbers of what are essentially incomplete Boost variants, and not due to the developers being bad; Boost is so huge that sometimes it makes sense to re-implement 5% of it.
It was a big difficulty: I've been developing and maintaining this codebase since Y2K, and to make it portable on different OSes (Linux, Mac, Windows, Emscripten, Android), we often had to "reinvent the wheel". At the very beginning in the 90's, we did not even have std::string !
As time passes, I can get rid of some code. For instance, FileSystem will be replaced by std::filesystem, spinlocks with std::atomic (if they are as efficient) and so on and so forth...
It is always difficult to compare different "swiss army knives" with a completely different set of blades, and in the end this type of comparison often becomes something like "my library is better than theirs", which I don't like. This is why I do not have a "comparison table" with "this library does this and that". But I admit the list of features is not directly visible, I'll work on the main README.
A good starting point to see the list of high-level operations supported by geogram:
https://github.com/BrunoLevy/geogram/wiki#mini-tutorials-and...
CGAL is GPL, while Geogram is BSD. That has a lot of practical consequences in how they can be used. Plus it's nice from an educational standpoint to have independent open-source implementations.
Merging Geogram into CGAL would be difficult, because besides the question of the license, they are developed with a rather incompatible programming style:
- CGAL is fully generic and makes an extensive use of modern C++ / generic programming / templates.
- Geogram is targeted towards several specific scenarii, with no compromise regarding efficiency and memory consumption. For instance, Geogram's data structures are based on contiguous arrays of values and indices, compact in memory, with fully parallel code, whereas CGAL uses for instance "property maps", that are more "generic" but that introduce a log(n) penalty for each individual access.
TL;DR: CGAL is configurable/generic/has many tuning buttons. Geogram is highly optimized in terms of memory usage and speed for some specific applications. Which one is best for you ? Depends on what you want to do !
Does anyone know how this library maintains geometric robustness in the face of rounding errors? E.g. if you rotate a unit square by 45 degrees (giving irrational coordinates), then rotate it back and subtract it from the original, you are left with exactly nothing?
Exactness is not "advertized" on the main page or as a "design principle" but it is there !
Geogram uses "arithmetic expansions", arrays of floating point numbers that can represent numbers with arbitrary precision while being reasonably performant (it is the same thing used by Jonathan Shewchuk in his predicates). In addition, besides predicates, Geogram can use arithmetic expansions to represent intermediary results of computation (I'm currently developing boolean operations that extensively make use of this feature).
Thank you very much for discussing about geogram !
To answer some of the questions I see in the comments:
TL;DR: if you need a generalist library, use CGAL or libigl, if you have very specific needs of performance / compactness of the code / low memory consumption for specific functionalities, then you may need Geogram.
1) comparison between geogram and other libraries (CGAL, libigl)
Is is very difficult to compare different "swiss army knives" that have a completely different set of blades. Geogram specificities are:
- focusing on a small set of algorithms and use cases, and optimizing them (whereas the other libraries are more general-use). This includes:
- Delaunay/Voronoi/Power diagrams in 2D and 3D, with optional periodic conditions. For instance, it is used in my research on cosmology, that has diagrams of astronomical size, with hundred millions points (the other libraries no longer fit in memory). The price to pay: geogram does not support vertex suppression (if you need that, you can use CGAL).
- Mesh parameterization and segmentation, texture generation
- Baking (transfer attributes between textured meshes / generate normal maps)
- Mesh repair
- Remeshing
- Restricted Voronoi diagrams for surfaces and volumes embedded in space of arbitrary dimension. Not everybody will need that, but it is used internally by the surface remesher (that works in dimension 6)
Geogram has nearly no dependency. Geogram does not use Boost (that I don't like, I find it too heavy, that's personal choice). Geogram is not a "header only" library and moderately uses modern C++ constructs. Design choices are explained in this presentation: https://fr.slideshare.net/BrunoLevy4/the-joy-of-computer-gra...
In the end, the compiled library is very small (a few megabytes) and can be easily embedded in other applications (a list here of usages in industry and academy: https://github.com/BrunoLevy/geogram/wiki/Publications)
Of course ! It has exact predicates and exact geometric constructs. They are implemented using arithmetic expansions (https://brunolevy.github.io/geogram/multi__precision_8h.html) (that uses array of doubles internally), and it is fast. It has its tool to automatically generate exact geometric predicates from their formulas.
PSM includes the dependencies, instead of getting rid of them. Not flexible enough.
An example is logging. Geogram includes a logger implementation which uses console streams. GUI apps don't have these streams, they sometimes even deadlock, when an app prints too many characters no one is reading on the other end of the pipe. Geogram includes another file logging implementation in FileLogger class. It uses std::string for path, which doesn’t work on Windows because Windows paths are using UTF-16 encoding.
Also, many parts of Geogram are bypassing the logger API, they directly printing text into std::cerr.
Here’s a possible example of an API which allows to inject custom loggers into DLL libraries:
// Log level for messages
enum struct eLogLevel : uint8_t
{
Error = 0, Warning = 1, Info = 2, Debug = 3
};
// C function pointer to receive log messages from the library. The messages are encoded in UTF-8.
using pfnLoggerSink = void( __cdecl* )( void* context, eLogLevel lvl, const char* message );
About using std::string as path under Windows, I understand that it may cause some problems with users who use general characters in their directories, but it does not prevent the application from running and from loading/writing files. In the future, when std::filesystem is well standardized, I plan to get read of my FileSystem implementation.
Not trying to take away from it, but it's scope seems elementary. Maybe I missed it, but did not see any more advanced operations. Wider adoption might be in the cards if at least some of the following are present:
Mesh analysis (how many manifolds, how many holes, self-Intersection detection, flipped triangles, etc)
This is the thing underlying AliceVision. As far as I can tell it was built together with and for AliceVision. It's not a nice, standalone library today, and I cannot imagine using it in any other way.
- Seeing some comments, I understand that some global objects in Geogram (Logger, Bibliography manager) are annoying for some use cases. I will add some options to deactivate them in the next release. Feel free to create issues here: https://github.com/BrunoLevy/geogram/issues
Oooh that's interesting, thanks for the detailed feedback. I'll add an option to get rid of all the stuff that annoys you in the next release of the PSMs.
Feel free also to create issues on github: https://github.com/BrunoLevy/geogram/issues
[1] https://github.com/mpihlstrom/femton