Replace CGAL + VCG with GEOGRAM

[cdcseacave]

GEOGRAM is a powerful geometric library, containing very fast Delaunay triangulation and mesh cleaning/fix algorithms. Currently OpenMVS is depending on CGAL and VCG libraries to accomplish these tasks. Not only that two libraries can be replaced with only one light library, but the increase in speed resulted by using GEOGRAM library would be significant. The refactoring of the affected algorithms should be straightforward, as GEOGRAM directly supports all the functionality needed and in a very similar interface to CGAL (thanks to the GEOGRAM author for helping with this).

[cdcseacave]

Is anybody willing to help with this task?

[rjanvier]

Nice to see that you are finally convinced! I'm a very happy user of vorpalite/GEOGRAM. For what it worth I can helps with tests under Linux/MacOs and maybe build integration. I will be too busy in the comming months for low level things. Beware that I think that now GEOGRAM include Schewchuk's Triangle which have a kind of "research only" license scheme.

[cdcseacave]

Did you ever suggest using GEOGRAM? Sorry if I missed it. Anyway, it is indeed a very good library, and on top of that well written. Thank you for offering your help with testing, it will be valuable. For now though, I'd need help with rewriting SceneReconstruct.cpp

[pmoulon]

I will certainly be able to provide some help, but not until 2 weeks.

[cdcseacave]

Thanks Pierre, please post here when you'll be available to help, so that we avoid duplicate work.

[rjanvier]

Yes, I'm too [bu|la]zy to find the exact comment (and maybe it was in the openMVS/openMVS repo which is gone now) but I when we had a non-manifold issue I wrote you about vorpalite (which is build upon GEOGRAM and included in GEOGRAM distribution). I remember you tried it and found it cool but you were not so happy by the architecture and the inversion of normals.

[pmoulon]

@cdcseacave I have successfully added a findGEOGRAM.cmake to OpenMVS and I'm able to generate the 3D delaunay triangulation (in SceneReconstruct) on the point cloud (raw point cloud, smart initialization with neighborhood will be done in a second time). I will publish this WIP to my fork. We still have to do:

• init cells weights
• find all cells containing a camera
• Build the s-t graph & weight
• run graph-cut and extract the final mesh (extract surface formed by the facets between inside/outside cells)

[pmoulon]

Geogram can be build very easily with cmake and then be used in OpenMVS.(http://alice.loria.fr/software/geogram/doc/html/geogram_compiling.html) Once build, extract the archive (Geogram-1.0.0-TARGET-devkit-full.tar) with the source & libs and add the GEOGRAM_ROOT to the OpenMVS cmake command line.

-DGEOGRAM_ROOT="/home/pierre/Documents/Dev/Geogram/geogram_1.2-j/build/Linux64-gcc-dynamic-Release/geogram_install/Geogram-1.0.0/"

[cdcseacave]

Great work, Pierre! Thx! There is still lot of work left to be done; do you think you will have time to continue any time soon?

[pmoulon]

Thanks @cdcseacave I won't have time until 2 weeks, perhaps we will have time to help each other. I added you to my fork as a collaborator. The most consuming task will be to see which routines we must use (since before it was CGAL based) and now we have to find how perform the same task in GEOGRAM or in OpenMVS existing code.

[C8PAN]

Hi, I hope to be of any help to this work and help with this task. I have been using and studying OpenMVG and OpenMVS for quite a few days. I really want to make it faster and more scalable. To make it faster, one can use parallel architecture, like MPI, OpenMP, multi-threading, GPU etc. To make it more scalable, for the DensifyPointCloud module, the input images are decomposed into a set of image clusters of reasonable size and a divide-and-conquer strategy is used just as the clustered version of PMVS. But for the ReconstrutMesh module, no similar strategy is used and the program sometimes is terminated with a bad_alloc because the memory is exhausted.

Does anyone knows how to make the ReconstructMesh module more scalable? Is it possible to improve the scalability of this module by replacing GEOGRAM with CGAL and VCG?

[cdcseacave]

Hi @C8PAN! Thank you for offering to help. Regarding this topic: replacing CGAL and VCG with GEOGRAM (you got it wrong) the main goal is to make ReconstructMesh faster (GEOGRAM uses a parallel implementation of Delaunay triangulation) and simpler (all functionality is in one library). If you can help here, I suggest to start from where Pierre took the transition. Regarding making it scalable, there is an algorithm I have in mind, and I will create a new enhancement topic as soon as this task is completed (cause it depends on this one).

[pmoulon]

@C8PAN Thank for your message and detailed interest about our project (OpenMVG & OpenVS). We are definitively interested to have contributor. Welcome to "Join the OpenX forces!"

The idea to go larger scale is to split the scene into smaller chunk.

DensifyPointCloud:

• [cons] => the point cloud cleaning is the step that is using the most of the memory.
• [pros] => computing the disparity map & selecting the pair is doing a great job

ReconstructMesh:

• [cons] => some steps are not yet run in parallel -> That's why we are trying to use GEOGRAM -> since geogram does not have the same interface as CGAL we have to rewrite or find a way to redo the various needed task for the weight computation.
• [cons] => load the whole scene
• [pros] => s-t graph cut code is efficient

One viewpoint on enhancing the scalability would be the following: Since handling a large scene is not feasible, a divide and conquer approach must be chosen.

• 1. we load all the scene, and compute pairs & disparity maps as it is done.
• 2. cut the scene in boxes (using a Octree up to a certain level of recursion).
• 3. We process each box independently (one day perhaps on clusters)
     • for each box (get all the depth map that define some content in this box, less data need to be loaded)
     • simplify the point cloud (as done in the end of DensifyPointCloud)
     • compute the Surface ...
     • each box can use a margin in order to avoid loading to much data and ensure overlapping of the meshes.

[C8PAN]

Hi @cdcseacave @pmoulon , Thanks for your reply. I will start by installing GEOGRAM and find out all the routines that CGAL is used.

[pmoulon]

That the right way to start :+1: "Identify in Geogram how to use the spatial search data structures & compute intersections (ray, triangles)."

here the first step: http://alice.loria.fr/software/geogram/doc/html/index.html

Once you have installed GEOGRAM (locally or on your system), you can checkout my fork https://github.com/pmoulon/openmvs/tree/develop_geogram If you use a local install you will need to update the path [local install are a local unzip from the cmake GEOGRAM CPACK archive], else GEOGRAM will be find automatically in system libraries.

-DGEOGRAM_ROOT="/home/pierre/Documents/Dev/Geogram/geogram_1.2-j/build/Linux64-gcc-dynamic-Release/geogram_install/Geogram-1.0.0/"

I will have some day off, let's make a new point next Friday.

[sweeneychris]

Regarding scalable mesh extraction, Hoang Hiep Vu's PhD thesis has excellent suggestions for scalable mesh processing: http://www.theses.fr/2011PEST1058.pdf

[Just5D]

There is bug in Vu's mesh merging code, a bit unstable

[sweeneychris]

What do you mean there is a bug in the code? There is no open source code for this method (that I know of). If you know of code available could you please point me to it?

[Just5D]

I tried the code 3 years ago,now i can not find it! just mesh merging,no surface reconstruction

[rjanvier]

the code was on Hiep Vu homepage. It's offline since last year. I guess we should open a topic on scalability on keep this one related to Geogram specific issues.

[jwingnut]

Anything happening on either front?

[cdcseacave]

No, neither me nor Pierre had time to work on this topic anymore.

[pmoulon]

I made some commits here that was a WIP about the tetrahedra triangulation but actually I don't have more time to work on it. https://github.com/pmoulon/openMVS/tree/develop_geogram