Geogram: Programming Library with Geometric Algorithms | Hacker News Reader

Geogram: Programming Library with Geometric Algorithms

github.com

138 pointsmbustamanter32 comments

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.

[1] https://github.com/mpihlstrom/femton

Do you have plans for a license? Impressive either way.

Thanks. A license has been added now.

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.

Thanks. I have a low attention span with GitHub repos, so I felt I should at least try to meet the expectations of someone like myself.

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).

For now, if you want an overview of that Geogram does, the following link gives a description of several sets of functionalities: https://github.com/BrunoLevy/geogram/wiki#mini-tutorials-and...

> Working with analytic algorithms is like playing around with synthesizers whereas ML is more like using a sampler.

Amazing analogy that really helps me understand these algorithms better. Thanks for that.

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.

This is exactly where Rust shines, even more than the borrow checker stuff IMO

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...

I'd be interested to know what is a true "showstopper" for you, do not hesitate to post issues here: https://github.com/BrunoLevy/geogram/issues

See also libigl for geometric processing:

https://libigl.github.io/

I wish there was a better description of how geometry processing libraries differ - what does this do that say, open3d or CGAL doesn't?

Exactly my thought. If anything I would have merged this into CGAL. "30 research articles" is just the tip of the iceberg of what CGAL does.

Also, Open3D is looking very cool, good pointer.

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 !

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...

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 of results is not listed among its design principles:

https://brunolevy.github.io/geogram/geogram_design.html

CGAL offers exact algorithms:

https://doc.cgal.org/latest/Kernel_23/index.html#Chapter_2D_...

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).

Geogram uses arithmetic expansions and filtered predicates, as explained in the following publication: https://hal.inria.fr/hal-01225202

I’ve had some very positive interactions with Bruno levy online. He’s incredibly nice and happy to share his deep domain knowledge.

Thanks :-)

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)

- Semi-discrete optimal transport

Some features are presented here: https://github.com/BrunoLevy/geogram/wiki#mini-tutorials-and... It does not have mesh deformation (you can use libIGL if you need them)

It also has lower-level components:

- sparse linear solver OpenNL CPU/GPU

- easy-to-use 3D graphics API on top of OpenGL3

- minimalist framework around Dear ImGui to develop applications with GUIs

- focusing on portability and ease of compilation Geogram works on Linux/Mac/Windows/Emscripten/Android

You can run some demos in your browser (thanks to Emscripten): https://github.com/BrunoLevy/geogram/wiki/compiling_Emscript...

- programming API and design choices

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)

- It has an interactive application here: https://github.com/BrunoLevy/GraphiteThree (you can load your meshes, repair them, remesh them etc...)

2) Does it support exact geometric computations ?

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.

3) Boolean operations ?

They are on their way (https://twitter.com/BrunoLevy01/status/1623347815307960321). Current version is here: https://github.com/BrunoLevy/Experiment (Graphite plugin). Most models from Thingy10K are OK, currently focussing on a couple of "monsters" that push the limit.

4) I want to only use a subset of the library

Geogram has a system to extract "pluggable software modules", that is, a .h/.cpp pair with a single functionality. There are PSMs for:

- exact arithmetics and predicates https://github.com/BrunoLevy/geogram.psm.Predicates

- Delaunay triangulations https://github.com/BrunoLevy/geogram.psm.Delaunay

- OpenNL linear solver (CPU and GPU) https://github.com/BrunoLevy/geogram.psm.OpenNL

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 );

Thank you very much for this feedback, it is super useful. Do not hesitate to post this type of comment to geogram's github (https://github.com/BrunoLevy/geogram/issues)

Please note that the Logger mechanism can be redirected to a GUI, it is used for instance in the GUI applications made with Geogram (https://github.com/BrunoLevy/geogram/wiki/Applications) and in Graphite (https://github.com/BrunoLevy/GraphiteThree)

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)

Mesh healing algorithms to fix above artifacts

Boolean operations

Laplacian Deformation / smoothing

Offset calculation

Sewing meshes together

Mesh tagging to guide certain operations

Mesh matching

Convex Hull computation

Hi, no the scope of Geogram is not elementary, it has the following functionalities:

- Mesh reconstruction from 3D pointsets

- Mesh analysis

- Mesh repair

- Anisotropic remeshing

- Texture atlas generation

- Texture baking, normal map generation, ambient occlusion map

- Tetrahedral meshing (with tetgen)

- Boolean operations (upcoming)

- Delaunay, Voronoi, Laguerre diagrams, convex hulls in 2D and 3D. Highly optimized parallel implementation (used e.g. in cosmological simulations)

- Manifold Harmonics (Laplacian Eigenvalues)

- Parallel linear solver (CPU and GPU)

See the following link for examples: https://github.com/BrunoLevy/geogram/wiki#mini-tutorials-and...

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.

> I cannot imagine using it in any other way

The good thing about that library is the permissive license. Here’s a project where I managed to reuse substantial parts of that library by copy-pasting and reworking the code: https://github.com/Const-me/fTetWild/tree/master/MeshRepair/...

It wasn’t pretty https://github.com/Const-me/fTetWild/blob/master/MeshRepair/... but it worked fine for the use case I had at that time.

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

- No, Geogram was not developed for AliceVision. AliceVision uses geogram, but is completely independent.

- Geogram is used in several projects and libraries, see the list here: https://github.com/BrunoLevy/geogram/wiki/Publications

- 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

Reply on news.ycombinator.com