Home

Awesome

GeodesicGraph: DGG and SVG

This is the source code for the graph-based discrete geodesic algorithms in the following paper:

Fast Construction of Discrete Geodesic Graphs
YOHANES YUDHI ADIKUSUMA, ZHENG FANG, and YING HE, Nanyang Technological University
ACM Trans. Graph., Vol. 39, No. 2, Article 14, Publication date: March 2020.

A more efficient method for constructing Discrete Geodesic Graph (DGG)—a sparse graph for computing approximate discrete geodesics on triangle meshes. This code also includes the implementation of Saddle Vertex Graph (SVG).

alt text

Compling the code

  1. Please check ProjectDependencies.txt for the configuration of the project

  2. The code has been tested on:

    • Windows 10 with Microsoft Visual Studio 2017 and 2015

  3. The code implements the following commands:

    • DGG_Precompute for computing the geodesic graph
    • DGG_Solution for computing geodesic distance (single-source-all-destination or multiple-source-all-destination)

Usage of commands

  1. To compute the geodesic graph, use the command

    DGG_Precompute [method] [model] [accuracy_control_parameter] [number_of_threads]
    • method: 'f' for FastDGG or 's' for SVG
    • model: .obj/.off format mesh file
    • accuracy_control_parameter: an expected relative mean error ε ('0.01' represents ε= 1%)
    • number_of_threads: using multiple threads to accelerate the process

    Example command line:

    DGG_Precompute f bunny.obj 0.01 8

    This command generates the precomputed geodesic graph bunny_FD0.0100000000_c5.binary.

  2. To compute the geodesic distance, use the command

    DGG_Solution [method] [model] [graph_binary_file] [source] [output_distance_file]
    • method: 'SSAD' for single-source-all-destination or 'MSAD' for multiple-source-all-destination
    • model: .obj/.off format mesh file
    • graph_binary_file: the precomputed geodesic graph in .binary format
    • source: 0-based source vertex id for single source or source file name for multiple sources
    • output_distance_file: a file saving the distance field

    Example command line:

    DGG_Solution SSAD bunny.obj bunny_FD0.0100000000_c5.binary 0 bunny.distance.txt

    This command generates the distance field bunny.distance.txt.

Citation

Please cite the following paper if you use FastDGG:

@article{10.1145/3144567,
author = {Adikusuma, Yohanes Yudhi and Fang, Zheng and He, Ying},
title = {Fast Construction of Discrete Geodesic Graphs},
year = {2020},
issue_date = {March 2020},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {39},
number = {2},
issn = {0730-0301},
url = {https://doi.org/10.1145/3144567},
doi = {10.1145/3144567},
journal = {ACM Trans. Graph.},
month = mar,
articleno = {Article 14},
numpages = {14},
keywords = {geodesic path, Geodesic distance, anisotropic meshes, accuracy-aware window propagation, discrete geodesic graph, polyhedral surfaces, complexity analysis}
}

Please cite the following paper if you use SVG:

@article{10.1145/2508363.2508379,
author = {Ying, Xiang and Wang, Xiaoning and He, Ying},
title = {Saddle Vertex Graph (SVG): A Novel Solution to the Discrete Geodesic Problem},
year = {2013},
issue_date = {November 2013},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {32},
number = {6},
issn = {0730-0301},
url = {https://doi.org/10.1145/2508363.2508379},
doi = {10.1145/2508363.2508379},
journal = {ACM Trans. Graph.},
month = nov,
articleno = {Article 170},
numpages = {12},
keywords = {shortest path, discrete geodesic, saddle vertex graph}
}