brunolevy/geogram

a programming library with geometric algorithms

geogram

Geogram is a programming library with geometric algorithms. It has geometry-processing functionalities:

• surface reconstruction
• remeshing
• parameterization and texturing
• Boolean operations

It also has lower-level algorithm:

• Exact numbers / exact predicates
• Delaunay triangulations in 2D and highly efficient parallel Delaunay triangulations in 3D
• Memory efficient surfacic/volumetric/hybrid mesh data structure
• Efficient geometric search data structures for intersection and raytracing (AABBs, KdTrees, ...)
• Spectral mesh processing
• Linear solver on CPU and GPU

Geogram received the Symposium on Geometry Processing Software Award in 2023.

Geogram contains the main results in Geometry Processing from the former ALICE Inria project, that is, more than 30 research articles published in ACM SIGGRAPH, ACM Transactions on Graphics, Symposium on Geometry Processing and Eurographics. It was supported by two grants from the European Research Council (ERC): GOODSHAPE and VORPALINE.

Links

• Documentation, how to compile, tutorials....
• Programmer's reference manuals...
• Releases
• Projects with geogram
• Graphite, an experimental 3D modeler built around geogram.
• Geogram in-browser demos (How is it possible ? more on this here)
• Data

How does it compare to other geometry-processing libraries ?

See FAQ

geogram's Issues

Do we still need GLUPES2 ?

GLUPES2 is used by

• emscripten/webGL 1.0 / GLSLES 1.00 / GLSL 1.2
• android
• mac/OS default

GLSL 3.3 (or at least 1.5) is probably supported everywhere now. Then we could get rid of a lot of code in geogram-gfx.

Help compiling with gargantua?

Bruno: problem now fixed. Still need to add non-regression tests in GARGANTUA mode to avoid this type of issue in the future

Hi, thanks for your time addressing my question.
I am trying to compile with gargantua, but I am having a build failure. I am on redhat linux 64 bit. I have no problems compiling without gargantua. Here are my steps.

cp CMakeOptions.txt.gargantua CMakeOptions.txt
sh ./configure.sh Linux64-gcc-dynamic
cd ./build/Linux64-gcc-dynamic-Release/
make -j 1

The build reaches 76% and fails with the last statement being
[ 76%] Building CXX object src/lib/geogram/CMakeFiles/geogram.dir/NL/nl_amgcl.cpp.o
Followed by many GCC errors complaining about conflicting types. For example:

In file included from geogram/src/lib/geogram/NL/nl.h:1455,
from geogram/src/lib/geogram/NL/nl_amgcl.h:43,
from geogram/src/lib/geogram/NL/nl_amgcl.cpp:6:
geogram/src/lib/geogram/NL/nl_64.h:59:15: error: conflicting declaration of C function ‘double nlGetVariable(NLulong)’
59 | inline double nlGetVariable(NLulong i) {
| ^~~~~~~~~~~~~
In file included from geogram/src/lib/geogram/NL/nl_amgcl.h:43,
from geogram/src/lib/geogram/NL/nl_amgcl.cpp:6:
geogram/src/lib/geogram/NL/nl.h:1006:31: note: previous declaration ‘NLdouble nlGetVariable(NLuint)’
1006 | NLAPI NLdouble NLAPIENTRY nlGetVariable(NLuint i);

Consider replacing logger with spdlog

spdlog is an awesome logging library offering tons of feature. It is super lightweight as well, thread-safe, etc. We use it in Lagrange, where it is exposed as a single logger object, which under the hood uses a global static logger.

Using spdlog would simplify integration of geogram in third-party codebase. It has a very well-designed API and offers lots of ways to control logger sinks and redirect logging messages where we need them.

Thick lines in GLUP

I miss glLineWidth() ...
Need to write a geometry shader or something to be able to draw thick lines.

night builds

Seems that something changed in github actions, night builds no longer built.

doubts in multithreaded compute_RVD

Could you please clarify some of my doubts regarding computing the restricted voronoi diagram in multithreaded mode?

In the documentation for the function "for_each_polyhedron()" there is a boolean parameter called "parallel" that, if true, tentatively parallelizes the computation.

1. First, how does it pick the number of threads to run the computation? I noticed that the parallel implementation of the Delaunay triangulation runs with 16 threads on my mac and the RVD computation is restricted to 2 threads if the parallel flag is active.

2. Is there a reason fro the choice of wording "tentatively" in the documentation? Are there restrictions to the parallelization of this operation?

3. I have noticed that the parallelization fails if the mesh that is used to restrict the voronoi diagram has a hole inside. One example of such a mesh would be one used for the computation of the flow around a sphere. Is there a workaround to use the parallel flag in such a case? I could provide the .stl that gives the error if that would be useful.

Thank you for your assistance.

Which repo is the main one is unclear

Hi. I'm looking to package this (and then alicevision) for Debian. I see this repo and the alicevision one:

https://github.com/alicevision/geogram/

It would be helpful to know which one is the main repo, and which one is the fork. Alicevision claims that their geogram is version 1.7.9 but your VORPALINE_VERSION_... variables indicate that you are version 1.8.1. So is your repository is more recent? Would either one be expected to work as the alicevision dependency? Are the APIs supposed to be stable? I.e. if alicevision can build with geogram 1.7.9, will it also build with geogram 1.8.1?

It would also be very helpful to have release tags, so that we could clearly see which commit, exactly, is "geogram 1.8.1".

Thanks!

In what situation will CDT failed

I provide a mesh as consatrains for tetgen delaunay, while in this situation delaunay 3D will failed with providing "Warning: Only 0 vertices, may be not enough". I has checked the constrains with assert_is_valid(), and assert is not triggered.
The constraint mesh is as follows.
Best wishes!
2.zip

third-party libs as submodules

Replace bundled third-party libs with submodules

lib/third_party

• glfw
• numerics/(LIBF2C,CBLAS,CLAPACK,ARPACK,SUPERLU): this will be another project with tools for generating the libs automatically from their github repository and f2c:
  • SUPERLU is on github (@starseeker)
  • ARPACK (ARPACK-NG) is on github

lib/geogram/third_party

• amgcl
• libMeshb: done
• HLBFGS
• lua
• PoissonRecon: probably won't do (lots of local fixes...)
• rply
• stb_image
• tetgen: no officiel github repo (but there is a mirror in libigl)
• triangle
• xatlas: lots of third party code in repo (libigl, eigen, ...), can we include just a few files as submodule ?
• zlib: local changes (include path to make sure the right includes are used)

lib/geogram_gfx/third_party

• glad
• imgui
• ImguiColorTextEdit: probably won't do (lots of local fixes...)
• imgui_fonts (can do ?)
• imgui_lua_bindings: probably won't do (lots of local fixes...)

surface boundary shrinkage after remeshing

Hello, I tried the isotropic remeshing algorithm (tri_size_adapt=0, tri_shape_adapt=0) on a surface mesh with boundary and found that the surface boundary shrinks after remeshing, as shown in the below screenshot. Do you have any idea why that happened? Is there any way to preserve the original surface boundary as much as possible? Thank you!

Clarification on compute_RVC() documentation

I'm confused about the wording on the documentation of the 4th input parameter of compute_RVC() within the RestrictedVoronoiDiagram class. It reads as

[in] copy_symbolic_info if true, symbolic information is copied. An attribute "id" is attached to the facets. The value of id[f] is either 1 + the index of the Voronoi vertex that generated with i the bisector that created the facet, or -1-g if the facet was an original facet of mesh M, where g is the index of the original facet in M.

It says "Voronoi vertex" but then mentions the bisecting plane. However, don't the vertices of the Delaunay graph generate the bisecting planes? Does this actually refer to the generating seed point for a voronoi cell or a vert of the voronoi graph? Or perhaps I am misunderstanding something else. Thanks for any clarification.

How to build for iOS?

Is it possible to build this for iOS?

Suggestion: Upload images & gifs to the wiki

I suggest using the wiki feature (which is another git repository on its own!) to upload gifs & images for the documentation/tutorials. Storing binary assets in the main repo will quickly inflate the repo size over time, and there's no way to undo this later on!

Question about Co3Ne and mesh repair

I doubt that this is an issue - more of a question/confirmation request about what the expected capabilities and limitations are of the geogram algorithms.

One of our CAD system's fallback facetization routines for implicit boolean geometry is to shoot rays, generate a point cloud, and then do surface reconstruction. Usually we use PoissonRecon, but that fails fairly miserably for super thin, large surface area solids. I tried such an example with geogram's Co3Ne and got very interesting results (see images below). However, the mesh doesn't appear to be (quite) fully manifold and surface repair seems to be unable to completely resolve the issues. Is this normal/expected for this type of input data set?

size adaptation

Hello, I tried the size adaption (from 0 to 1) of the remeshing algorithm while setting the anisotropy parameter as 0. When the size adaptation approaches 1, the resulting mesh has some strange dense distribution of triangles in some region, highlighted by the red circle in the below screenshot. The background color indicates the surface curvature. The curvature in the highlighted region is similar to the surrounding in the horizontal direction but has very dense mesh distribution. Do you have any idea why this happened or suggestions about how to mitigate it? Thank you!

GEO::mesh_make_atlas() very slow

I finally was able to call and extract all data I need from GEO::mesh_make_atlas() however when trying it on any real mesh (number of faces > 500k) the method becomes very slow, basically unusable in any real wold application. Is there something I do wrong in compiling the library or the function in known to be slow?

Update: I tested the functionality in GraphiteThree and same problem.

Visualize a per-cell-facets attribute in Vorpaview

Hello,
I'm trying to display a tetra mesh with a per-cell-facets attribute (for walls, in case of volume decomposition).
It seems Vorpaview/Graphite cannot render this kind of attribute, despite listing them and allowing to autorange.
As a simpler example, here is a sphere tetra mesh in a geogram file (just remove ".zip")
sphere_with_random_attributes.geogram.zip
It contains 4 attributes with random values (doubles, between -1 and 1) : per vertex / per cell / per cell facets / per cell corners

In Vorpaview:

Vertex attribute : ✔️

Cell attribute : ✔️

Cell facets attribute : ❌

Cell corners attribute : ✔️

Is this an issue related to Vorpaview?
Thank you for your help

Packer::total_area_3d_ is unused

Packer::total_area_3d_ seems unused, could be removed

problem of delaunay

I'm having issues with GEO::delaunay, the resulting mesh is of poor quality, even -1 in the cell_to_v array. I have read your demo carefully and found no problem with my code usage, I hope to get your help, best wishes!
Code is as follows:

    GEO::CmdLine::import_arg_group("standard");
    GEO::CmdLine::import_arg_group("pre");
    GEO::CmdLine::import_arg_group("algo");

    GEO::Delaunay::initialize();
	GEO::Delaunay_var T = GEO::Delaunay::create(3, "BDEL");
    //T->set_reorder(true);
	//T->set_thread_safe(true);
	T->set_keeps_infinite(true);
	T->set_vertices(vd_.size() / 3, vd_.data());

	std::vector<Vector4i> indice;
	indice.resize(T->nb_cells());
	const auto& tet2v = T->cell_to_v();
	for (int i = 0; i < indice.size(); ++i) {
		for (int j = 0; j < 4; ++j) {
			indice[i][j] = T->cell_vertex(i, j);
		}
	}

unexpected behaviour in triangle_intersection algorithm

I have the two triangles t0 and t1 below
t0={p0, p1, p2}; with p0={1898.68 775 1158.48} , p1={2000 775 1166.7}, p2={1898.68 675 1148.6}
t1={q0, q1, q2}; with q0={1966.41 675 1163.79}, q1={1971.63 675 1166.95}, q2={1967.56 684.554 1166.67}

When I call the api:
bool GEOGRAM_API triangles_intersections(
const vec3& p0, const vec3& p1, const vec3& p2,
const vec3& q0, const vec3& q1, const vec3& q2,
vector& result
);
I got this error (run in windows):
| o-[Assert ] Error: Control should not have reached this point. |
| File: \Geogram\src\lib\geogram\mesh\triangle_intersection.cpp, |
| Line: 475 |

I except to get no intersection as depicted in the attached image.

Primitive filtering does not work in vertex gather mode (GLUP150)

Everything is in the title !

Find a way of displaying status in tests dashboard

Find a way of displaying test status in dashboard matrix (unfortunately images are cached by github, which makes my ok.png/ko.png trick fail... Maybe some "badges" can do the job...

vector segfaults on out-of-memory error

If the system does not have enough memory to allocate a GEO::vector, it will segfault.
The reason for this is that GEO::vector is essentially an std::vector that uses the Geogram aligned allocator, and the contract for allocators for STL container classes requires that if they return (i.e. do not throw) they return a valid block of memory (https://stackoverflow.com/questions/4826838/do-standard-library-stl-containers-support-a-form-of-nothrow-allocation).

The Geogram aligned allocator does not fulfill this contract; if it cannot allocate, aligned_malloc will return 0, and this will be returned by the allocator, causing a segfault.

This could be fixed by having the allocate() method check for nullptr and throw std::bad_alloc if it is; that way, the contract will be fulfilled, and an out-of-memory will throw an exception that can be caught higher up.

Version string shouldn't have "-rc" if using the release

Hi. I'm packaging the new 1.8.1 release, and I'm having to apply this patch: https://salsa.debian.org/science-team/geogram/-/blob/master/debian/patches/no-rc-version.patch

The version is "1.8.1" not "1.8.1-rc". Would you like to merge the patch?

Thanks!

How to compile for Android?

Hello,

I was wondering if there was a way to compile this library for Android?
I have managed to generate a visual studio solution for Android with cmake for now but I have not been successful in building it.

Thank you!

gcov

Create gcov job that publishes human-readable status to tests dashboard

Weekly tests

Reactivate weekly tests with complete database

Repository tags

Hello, I would like to know, if tags are going to be introduced in this repository. As some comments show, users want to have tags to distinguish different versions. Also, it will be handy to see actual releases rather than intermediate ongoing work.

MacOS Valgrind

Create job for MacOS Valgrind tests

GLUP_PYRAMIDS under GLUP150 profile generate a warning

On my board (NVidia quadro T2000), using the GLUP150 profile with pyramids does not work:
In GLUP_context.cpp, line 1500, it tries to generate 20 vertex attributes, and it seems that
implementation is limited to 16.
But there does not seem to be any problem with GLUP440 (to be verified)

Make geogram initialization less intrusive.

Currently geogram requires a call to GEO::initialize(), which is very intrusive:

• Sets its own env variable LC_NUMERIC on Unix system
• Register its own atexit() function.
• Process::initialize will install new signal handlers by default
• The initialization function cannot be called concurrently either
• Etc.

Ideally such an initialization function should not be needed for a library integrated in a larger system. My recommendation:

• Use a single "Context" object to register global objects that are necessary (e.g. io plugins).
• Use Meyer’s Singleton to ensure thread-safe initialization and proper termination functions are called at program exit, without a specific atexit() function.
• Remove all intrusive registrations by default (signals, env variables, fpe, etc.)
• Remove the need to call GEO::initialize() altogether (e.g. have each system call their own singleton struct as needed, or rework systems to remove the need for globals altogether).

Windows compilation

Hello,

Does Geogram can be compiled with Visual Studio ? Is there window binary asset ?
I tried to configure with cmake but i got an error cause glfw folder is empty

Thanks for your help

Texturing mesh from images?

Hi,
Thanks for working on this and making it available for us. I've been trying to get Poisson reconstruction for some time and I couldn't be happier to see it's working in your implementations!

I have a question about texturing from here. I am trying to texture the surface from the photos. I have a depth map form the Lidar scan and corresponding RGB images. I can use your pipeline to convert it from depth map to point cloud to mesh and generate mesh atlas. Is geogram supporting texture mapping from the images?

Licensing: can we remove all the requirements to provide notice of modifications?

Hi. I'm looking at packaging the new 1.8.1 release. It looks like you simplified many of the licenses; thanks for doing that! But many files still contain requirements to provide notice of modifications. For instance here:

geogram/src/lib/exploragram/hexdom/geometry.cpp

Line 19 in 3b85746

* If you modify this software, you should include a notice giving the

Can we remove those extra clauses? The ones applying to GPL licenses (such as the above link) are particularly problematic. The GPL explicitly says that such additional restrictions are not allowed and any license that is GPL + extra such restrictions can be treated as just "GPL":

All other non-permissive additional terms are considered “further restrictions” within the meaning of section 10. If the Program as you received it, or any part of it, contains a notice stating that it is governed by this License along with a term that is a further restriction, you may remove that term.

Can you release 1.8.2 with this license update?

Thanks

Global face indices that form a cell?

Hi,

Is there a way of obtaining the global indices of the faces that form a particular cell? i.e. if there are 100 faces in total in the mesh, numbered from 1 to 100, which of those faces forms cell 5, for eg.? Could you point out the lines in the source code where this info is? Thanks.

LM7 license

Hi! Looking at the 3rd party code, I notice that the LM7 copy included with geogram is LGPL, even though the newest upstream code is MIT licensed. Does geogram need the older version, or could it be upgraded to the MIT version?

Impossible to rotate objects with trackpad on OS X

Hi,

I have just built the project and it looks awesome.
I was playing with the examples and I have an issue : I can only translate the objects in the window.
I am unable to rotate anything.
I am on OS X 12.2.1

I have installed and built glfw separately to test and I have no issue to rotate the 3d objects with glfw examples.

But, for instance, with example geogram_demo_Delaunay3d, I can only translate the object in the window.

I hope you have an idea how to correct this.

Does geogram support power diagram？

Hi, thanks for offer such excellent algorithm library?
Does geogram support power diagram？
I only find function about RVD in geogram.

How to use delaunay using tetgen

Sorry to bother again.
The same method got the correct result in BDEL, but got the wrong result in tetgen, don't know if it's a problem with my use.

Code is just like this

  GEO::initialize();
  GEO::CmdLine::import_arg_group("standard");
  GEO::CmdLine::import_arg_group("pre");
  GEO::CmdLine::import_arg_group("algo");
  
  GEO::Delaunay::initialize();
  GEO::Delaunay_var T = GEO::Delaunay::create(3, "tetgen");//or use "BDEL"

  T->set_vertices(vertex.size() / 3, vertex.data());//vertex is the points
  //Then use T->cell_to_v() to get information of tets

Another problem is that I can't find a method for tetrahedral division of the point set using constraint delaunay. Can you give a demo easily?

Non-regression tests for graphic applications

Would be great to be able to launch non-regression tests for graphic applications, generate snapshots, publish them in test results (and even do some stats on pixel values to automatically detect some issues)

Windows build: sccache deactivated

In the "Prepare sccache" step it says:

Initializing...
Invoke-Expression: D:\a\_temp\ff2ee3ee-f101-4b64-b0b3-df1f0e660f49.ps1:2
Line |
   2 |  Invoke-Expression (New-Object System.Net.WebClient).DownloadString('h …
     |  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     | The term 'Select-CurrentVersion' is not recognized as a name of a cmdlet, function, script file, or
     | executable program. Check the spelling of the name, or if a path was included, verify that the path is
     | correct and try again.

Error: Process completed with exit code 1.

Do you have any hint @jdumas ?
(note: I've added yesterday github actions to build Doxygen doc and publish it on gh-pages, but I think it is unrelated)

Using mesh_make_atlas

I'm trying to create the charts and parametrize them using mesh_make_atlas but all it does is to make one chart per triangle and parametrize that :)
What am I doing wrong?

	GEO::Logger::initialize();
	GEO::FileSystem::initialize();
	GEO::CmdLine::initialize();
	GEO::CmdLine::import_arg_group("standard");
	GEO::CmdLine::import_arg_group("algo");
	GEO::mesh_io_initialize ();
	GEO::Mesh gmesh(3, false);
	gmesh.vertices.create_vertices(mesh.vertices.size());
	FOREACHIDX(Mesh::VIndex, i, mesh.vertices)
		Eigen::Map<Point3d>(gmesh.vertices.point_ptr(i)) = mesh.vertices[i].cast<double>();
	GEO::vector<GEO::index_t> triangles(mesh.faces.size() * 3);
	AC_ASSERT_EQ(sizeof(GEO::index_t), sizeof(Mesh::VIndex));
	FOREACHIDX(Mesh::FIndex, i, mesh.faces)
		memcpy(&triangles[i * 3], mesh.faces[i].data(), 3 * sizeof(GEO::index_t));
	gmesh.facets.assign_triangle_mesh(triangles, true);
	GEO::mesh_make_atlas(
		gmesh, 45.0 /* hard_angles_threshold */,
		GEO::ChartParameterizer::PARAM_ABF,
		GEO::ChartPacker::PACK_TETRIS
	);
	GEO::mesh_save(gmesh, "_mesh.obj");
	GEO::CmdLine::terminate();
	GEO::FileSystem::terminate();
	GEO::Logger::terminate();

callgrind

Reactivate callgrind job

Publish test results to gh-pages

Each test job publishes individually to test-results, which causes sometimes some concurrency issues.
The way to go is probably to create a job executed once all tests are finished, and that downloads all the artifacts, then publishes everything to gh-pages. The difficulty is to make sure this job is always executed, even when one of the test fails...
Success/failure flag could be raised by the last job in the loop (the one that publishes), but then it will be harder to see which jobs succeeded/failed (until we manage to publish a page with the status of all jobs at the same time)

Vorpaline?

Looking over the build system, there are quite a number of references to variables using the VORPALINE_ convention... Does GEOGRAM need to retain the ability to build as either project(Vorpaline) or project(Geogram)?

If not, would pull requests removing the VORPALINE variable name/conditionals be of interest?

source tarball for 1.8.2 doesn't build as the tests dir is missing

Executing cmake naively, I get

CMake Error at CMakeLists.txt:144 (add_subdirectory):
  add_subdirectory given source "tests" which is not an existing directory.

The reason is that the tests/ directory appears to be missing from the release tarball despite it being in this repository. I assume this is a packaging problem when assembling the release source package.

Incorrect info in file header comments

Looks like the following files have obsolete info:

tests/lib/VorpatestLibrary.py
tools/testenv.sh.in
tools/testenv.bat.in

Unused configuration files in geogram/cmake/platforms/

See what can be removed in geogram/cmake/platforms/

Making your own PSM?

Hi, I find the Pluggable Software Module feature quite useful. I'd like to customize the Delaunay PSM to also include the features from the Restricted Voronoi Diagram implementation. Is there a straightforward way to go about this?

Data structure wiki notes feedback

Reading through the code and the design notes (because I'm thinking to implement my own AIF structure) and I have some questions that weren't answered in the admittedly amazingly written wiki page.

1. Why the idea of local edge and local vertex? Why not just use the global indices?
2. You claim half edges use more memory, what's the memory footprint of this data structure? Halfedges are 4 pointers (or indices) per edge, 1 per face (the adjacident edge) and 1 per vertex (the incident edge)