Fast and Flexible Distance Transforms in CGAL

[tinavaz]

A wide variety of problems in scientific computing and data analysis need to compute accurate shortest paths and distances along curved domains (e.g., curved surfaces representing the boundary of three-dimensional objects). The Computational Geometry Algorithms Library (CGAL) is a broadly-used open source framework for a wide variety of problems in geometric data analysis, but currently does not incorporate state-of-the-art methods for distance transforms. The goal of this project is to implement and integrate such methods into CGAL, specifically using methods as described in the paper "The Heat Method for Distance Computation" by Crane et al.

Commit Log: on branch IntrinsicFaceGraph-V2 https://github.com/CGAL/cgal-public-dev/commit/87c147b fix for g10 and g50 https://github.com/CGAL/cgal-public-dev/commit/2c8ba2e user manual heat method algorithm https://github.com/CGAL/cgal-public-dev/commit/fff13c7 citations needed and intro of user manual https://github.com/CGAL/cgal-public-dev/commit/27deb43 mesh for obvious idt/non-idt comparison https://github.com/CGAL/cgal-public-dev/commit/f98359c reference solutions and updated validate to read in reference https://github.com/CGAL/cgal-public-dev/commit/ca6f7a2 edge summation fix https://github.com/CGAL/cgal-public-dev/commit/f472153 fixed dist files to be libgeodesic's distances instead of reference https://github.com/CGAL/cgal-public-dev/commit/d3a7729 kitten data https://github.com/CGAL/cgal-public-dev/commit/b7a2c91 bunny data https://github.com/CGAL/cgal-public-dev/commit/c9ff6f7 Merge branch 'IntrinsicFaceGraph-V2' of github.com:CGAL/cgal-public-dev into IntrinsicFaceGraph-V2 https://github.com/CGAL/cgal-public-dev/commit/9722887 deleted gargoyle mesh https://github.com/CGAL/cgal-public-dev/commit/f117234 adding meshes and fixed tests https://github.com/CGAL/cgal-public-dev/commit/858fbff bunny/kitten reference and sources https://github.com/CGAL/cgal-public-dev/commit/58badf9 fix merge conflicts https://github.com/CGAL/cgal-public-dev/commit/a9d4250 Revert "adding reference files for kitten/bunny" https://github.com/CGAL/cgal-public-dev/commit/99bb882 Merge branch 'IntrinsicFaceGraph-V2' of github.com:CGAL/cgal-public-dev into IntrinsicFaceGraph-V2 https://github.com/CGAL/cgal-public-dev/commit/b1e9fca adding reference files for kitten/bunny https://github.com/CGAL/cgal-public-dev/commit/d556198 fix for computing mass/cotan matrix in idt case https://github.com/CGAL/cgal-public-dev/commit/00dced3 Integrating iDT in to heat method https://github.com/CGAL/cgal-public-dev/commit/ca02ad7 changed structure to a halfedge map instead of 2 arrays https://github.com/CGAL/cgal-public-dev/commit/965e631 structures needed for heat method https://github.com/CGAL/cgal-public-dev/commit/6b13146 fix for IDT as well as structures needed for hm integration https://github.com/CGAL/cgal-public-dev/commit/e16be1d case for border edges https://github.com/CGAL/cgal-public-dev/commit/85b9612 Intrinsic Delunay Triangulation for borderless meshes https://github.com/CGAL/cgal-public-dev/commit/30a01ff iDT functions and tests https://github.com/CGAL/cgal-public-dev/commit/98e664f build test and fixes https://github.com/CGAL/cgal-public-dev/commit/5615cc3 set up and basic functionality for iDT class https://github.com/CGAL/cgal-public-dev/commit/1dc77e2 beginning to set up Intrinsic Delaunay Triangulation class/methods https://github.com/CGAL/cgal-public-dev/commit/8c10ff7 basic cache functionality https://github.com/CGAL/cgal-public-dev/commit/5f6ad33 fix for multiple sources https://github.com/CGAL/cgal-public-dev/commit/69b1290 functionality for multiple vertices in source set https://github.com/CGAL/cgal-public-dev/commit/5748dc4 visual demo for single source for heat method https://github.com/CGAL/cgal-public-dev/commit/f4c7db1 Third phase of Heat method https://github.com/CGAL/cgal-public-dev/commit/e1cc730 added tests for computing unit gradient https://github.com/CGAL/cgal-public-dev/commit/77061d2 added phase 2 of heat method, tests to come https://github.com/CGAL/cgal-public-dev/commit/99ba0f4 small fixes https://github.com/CGAL/cgal-public-dev/commit/106abe9 fixing structure of tests for readability https://github.com/CGAL/cgal-public-dev/commit/9660a40 little fixes https://github.com/CGAL/cgal-public-dev/commit/8e5428b Added solver for heat equation https://github.com/CGAL/cgal-public-dev/commit/97585c4 added face/index property map https://github.com/CGAL/cgal-public-dev/commit/0ebddcb tests for matrix construction https://github.com/CGAL/cgal-public-dev/commit/82f38ce Added Kronecker delta funcitonality/test https://github.com/CGAL/cgal-public-dev/commit/15581b8 added time step computation and test https://github.com/CGAL/cgal-public-dev/commit/264d6c2 source set tests https://github.com/CGAL/cgal-public-dev/commit/479332b Construct cotan matrix and mass matrix

[sloriot]

@tinavaz please provide the status of the project at the end of GSoC

[sloriot]

@afabri @tinavaz What is the status of gsoc2018-Distance_transform-cvaz vs IntrinsicFaceGraph-V2? Shall the former be overwritten by the latter?

[afabri]

yes.

[sloriot]

OK I removed both branches, I created the tag archive/gsoc2018-Distance_transform-cvaz and the branch Heat_methods_3-GF that is a filtered version to reduce the size of the history, that branch should be used for any further development.