Skip to content
Implementation of SIGGRAPH 2019 paper: Progressive Embedding
C++ CMake Python C
Branch: master
Clone or download
Latest commit 02b7596 Aug 19, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
cmake update libigl cmake config file path Oct 15, 2018
cut_mesh clean up collapsing Apr 13, 2019
data upload example data Jun 12, 2019
figure
local_smooth update data and figure Aug 19, 2019
slim point constraints optmization Apr 16, 2019
.gitignore update data and figure Aug 19, 2019
.gitmodules Update README to include a commit hash. Feb 18, 2018
CMakeLists.txt update data and figure Aug 19, 2019
LICENSE Initial commit Dec 2, 2015
README.md change format Aug 19, 2019
argh.h basic Shor Apr 7, 2019
decompose_polygon.cpp put PE inside postprecessing of MM May 1, 2019
decompose_polygon.h rewrite convexation Apr 18, 2019
edge_split.cpp include <vector> Apr 11, 2019
edge_split.h include <vector> Apr 11, 2019
embed_points.cpp set up experiment Apr 8, 2019
embed_points.h
genus_zero_tutte.cpp extract code for running experiments May 1, 2019
is_simple_polygon.cpp basic Shor Apr 7, 2019
is_simple_polygon.h basic Shor Apr 7, 2019
loader.cpp update data and figure Aug 19, 2019
loader.h set up experiment Apr 8, 2019
local_operation.cpp
local_operation.h clean up collapsing Apr 13, 2019
main.cpp upload example data Jun 12, 2019
matchmaker.cpp update data and figure Aug 19, 2019
matchmaker.h integrate matchmaker Apr 7, 2019
mst.cpp integrate matchmaker Apr 7, 2019
mst.h integrate matchmaker Apr 7, 2019
path_tracing.cpp
path_tracing.h integrate matchmaker Apr 7, 2019
plot.cpp update covexation Apr 18, 2019
plot.h further clean up Apr 13, 2019
progressive_embedding.cpp update data and figure Aug 19, 2019
progressive_embedding.h update data and figure Aug 19, 2019
random_init.cpp upload example data Jun 12, 2019
shor.cpp extract individual steps for progressive embedding Apr 9, 2019
shor.h basic Shor Apr 7, 2019
target_polygon.cpp extract code for running experiments May 1, 2019
target_polygon.h
untangling.cpp update data and figure Aug 19, 2019
validity_check.cpp gather validity check functions Apr 14, 2019
validity_check.h update data and figure Aug 19, 2019

README.md

Progressive Embedding

Hanxiao Shen Zhongshi Jiang, Denis Zorin, Daniele Panozzo
ACM Transaction on Graphics (Proceedings of SIGGRAPH 2019)
DOI: 10.1145/3306346.3323012

Abstract

Tutte embedding is one of the most common building blocks in geome- try processing algorithms due to its simplicity and provable guarantees. Although provably correct in infinite precision arithmetic, it fails in chal- lenging cases when implemented using floating point arithmetic, largely due to the induced exponential area changes. We propose Progressive Embedding, with similar theoretical guarantees to Tutte embedding, but more resilient to the rounding error of floating point arithmetic. Inspired by progressive meshes, we collapse edges on an invalid embedding to a valid, simplified mesh, then insert points back while maintaining validity. We demonstrate the robustness of our method by computing embeddings for a large collection of disk topology meshes. By combining our robust embedding with a variant of the matchmaker algorithm, we propose a general algorithm for the problem of mapping multiply connected domains with arbitrary hard constraints to the plane, with applications in texture mapping and remeshing.

Dependency

This implementation currently is based on my forked version of libigl. Please use the following cmds to get libigl and swtich to shor branch:

git clone https://github.com/hankstag/libigl.git
cd libigl
git fetch
git checkout Shor

To compile

Use the following cmds:

mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make

To run

There are 4 executable files genearted as the compilation finishes:

  • untangle_bin
  • genus_zero_tutte_bin
  • random_init_bin
  • matchmaker_bin

Generate a failed case on Tutte's Embedding and then use it as initialization to generate a non-flip mapping with Progressive Embedding:

mkdir output
./genus_zero_tutte_bin --in ../data/62415_sf.obj -o ../data/62415_tutte_fail.obj
./untangle_bin --in ../data/62415_tutte_fail.obj -o output/62415_no_flip.obj

Genearte a random initialization with convex boundary and then use Progressive Embedding to fix the flips:

./random_init_bin --in ../data/retinal_miq.obj
./untangle_bin --in ../data/retinal_miq.obj_rand.obj -e 1

Randomly pick three vertices on mesh, pin them on the 2D plane, then generate a map strictly satisfying the constraints using Matchmaker++:

./matchmaker_bin --in ../data/camel_miq.obj

Data

To download the result data in our paper, please checkout this link.

You can’t perform that action at this time.