Insight Journal (ISSN 2327-770X) - Walk In A Triangulation : Straight Walk

Walk In A Triangulation : Straight Walk

Image & Pervasive Access Lab, National Centre for Scientific Research (CNRS), Fusionopolis, Singapore

Please use this identifier to cite or link to this publication: http://hdl.handle.net/10380/3341

Published in The Insight Journal - 2012 January-December.

Submitted by Alexandre Gouaillard on 02-14-2012.

This document describes the implementation in ITK of the Straight Walk in a Triangulation algorithm proposed by Devillers et al. Using the exact discrete geometrical orientation predicate, and the itk::QuadEdgeMesh API of ITK, we propose an efficient implementation that locates a point in a triangulated mesh structure. This paper is accompanied with the source code and examples that should provide enough details for users. This work has for principal intended an exact and robust implementation of a Delaunay triangulation / Voronoi tesselation in ITK, which will be presented in a separate paper, once done.

Code

Automatic Testing Results by Insight-Journal Dashboard on Tue Jan 29 17:14:47 2013 for revision #1

expertise: 5 sensitivity: 3.5

CMake was unable to configure this project.
Click here for more details.

Go here to access the main testing dashboard.

Reviews

A useful function, but with some build difficulty. by Davis Vigneault on 2015-06-09 09:57:49 for revision #1

expertise: 2 sensitivity: 3.5

Summary:

The authors provide an implementation of the Straight Walk method for efficiently determining which cell in a mesh contains a specified point. This has particular application in reversing a mesh parameterization, among other tasks.

Hypothesis:

Evidence:

Open Science:

One function, OrientTest(), appeared to be missing. Other than that, all code was provided. This builds off a public domain code base for exact floating point calculations, cited in the article.

Reproducibility:

I downloaded, compiled, and ran the code, with some difficulty. Here are the steps I needed to take to get it working:

1. It appears that the submodule is not linked correctly in github. I needed to remove the .gitmodules file and add the submodule manually. Here is my StackOverflow question [3] which solved the problem.

2. I had to change WalkInTriangulation/CMakeLists.txt:6:

include( ${USE_ITK_FILE}) ==> include( ${ITK_USE_FILE})

3. At this point, CMake runs without errors; but when building I'm told that OrientationTest is missing. I assumed that OrientationTest is a wrapper for orient2d, and added the following function to itkWalkInTriangulationFunction.h:

template< typename TPoint >

double

OrientationTest( TPoint a, TPoint b, TPoint c )

{

double pa[2];

double pb[2];

double pc[2];

pa[0] = a[0];

pa[1] = a[1];

pb[0] = b[0];

pb[1] = b[1];

pc[0] = c[0];

pc[1] = c[1];

return orient2d(pa, pb, pc);

}

With those changes, the example seems to work correctly, though I haven't done thorough testing yet.

Use of Open Source Software:

This takes advantage of software currently in the public domain:

http://www.cs.cmu.edu/~quake/robust.html

Open source Contributions:

With some modification, this could be integrated into the toolkit. Integrating the provided floating point calculation software could be useful independent of this application.

Code Quality :

I have only compiled and run on Ubuntu. However, the library used is in C, and therefore is expected to be portable.

Quality of the data :

Interest:

This submission has implications for mesh processing, as noted in the authors' later work.

Comment by Corelickcolt Vigorda:

Comment by Lschelneli Vigorda:

Comment by Rthierrymeag Vigorda:

Comment by Itezziodiss Holland:

Comment by Ekabyesheri Holland:

Comment by Hyherscherwesle Vigorda:

Comment by Itezziodiss Holland:

Comment by Ekjamerkend Ken:

Comment by Rnseremmi Vigorda:

Comment by Mwangmajor Holland:

Comment by Ekjamerkend Ken:

Comment by Hyherscherwesle Vigorda:

Comment by Lschelneli Vigorda:

Comment by Tyamatriley Vigorda:

Comment by Rankeurensuan Ken:

Comment by Tyamatriley Vigorda:

Comment by Ekabyesheri Holland:

Comment by Hyherscherwesle Vigorda:

Comment by Tsmccathedema Ken:

Comment by Rthierrymeag Vigorda:

Comment by Tyamatriley Vigorda:

Comment by Umcglaufllind Olivier:

Comment by Mwangmajor Holland:

Comment by Aollwaymyrt Vigorda:

Comment by Milbluemelsherr Ken:

Comment by Hyherscherwesle Vigorda:

Comment by Lschelneli Vigorda:

Comment by Tsmccathedema Ken:

Comment by Umcglaufllind Olivier:

Comment by Corelickcolt Vigorda:

Comment by Rnseremmi Vigorda:

Comment by Hyherscherwesle Vigorda:

Comment by Pshopgolf Olivier:

Comment by Rthierrymeag Vigorda:

Comment by Lheeralalkris Olivier:

Comment by Defeldanni Vigorda:

Comment by Hyherscherwesle Vigorda:

Comment by Corelickcolt Vigorda:

Comment by Milbluemelsherr Ken:

Comment by Umcglaufllind Olivier:

Comment by Defeldanni Vigorda:

Comment by Aaccajohn Holland:

Comment by Hyherscherwesle Vigorda:

Comment by Defeldanni Vigorda:

Comment by Pshopgolf Olivier:

Comment by Umcglaufllind Olivier:

Comment by Pshopgolf Olivier:

Comment by Elissierdeon Olivier:

Comment by Hyherscherwesle Vigorda:

Comment by Rthierrymeag Vigorda:

Comment by Lithrailesmered Olivier:

Comment by Defeldanni Vigorda:

Comment by Rsalbarrantravi Olivier:

Comment by Mwangmajor Holland:

Comment by Bridesmaidbride Ken:

Comment by Hyherscherwesle Vigorda:

Comment by Ohnatowgabr Ken:

Comment by Milbluemelsherr Ken:

Comment by Lheeralalkris Olivier:

Comment by Mwangmajor Holland:

Comment by Rnseremmi Vigorda:

Comment by Ntlnoel Holland:

Comment by Hyherscherwesle Vigorda:

Comment by Lschelneli Vigorda:

Comment by Elissierdeon Olivier:

Comment by Rsalbarrantravi Olivier:

Comment by Tsmccathedema Ken:

Comment by Corelickcolt Vigorda:

Comment by Bridesmaidbride Ken:

Comment by Ntlnoel Holland:

Comment by Nhuskinsaran Ken:

Comment by Rankeurensuan Ken:

Comment by Lheeralalkris Olivier:

Comment by Aollwaymyrt Vigorda:

Comment by Hyherscherwesle Vigorda:

Comment by Pshopgolf Olivier:

Comment by Corelickcolt Vigorda:

Comment by Nhuskinsaran Ken:

Comment by Lschelneli Vigorda:

Comment by Corelickcolt Vigorda:

Comment by Nhuskinsaran Ken:

Comment by Ohnatowgabr Ken:

Comment by Nhuskinsaran Ken:

Comment by Ntlnoel Holland:

Comment by Lheeralalkris Olivier:

Comment by Itezziodiss Holland:

Comment by Elissierdeon Olivier:

Comment by Ekjamerkend Ken:

Comment by Elissierdeon Olivier:

Comment by Tyamatriley Vigorda:

Comment by Elissierdeon Olivier:

Comment by Lschelneli Vigorda:

Comment by Rankeurensuan Ken:

Comment by Defeldanni Vigorda:

Comment by Rankeurensuan Ken:

Comment by Lschelneli Vigorda:

Comment by Umcglaufllind Olivier:

Comment by Rankeurensuan Ken:

Comment by Milbluemelsherr Ken:

Comment by Corelickcolt Vigorda:

Comment by Defeldanni Vigorda:

Comment by Elissierdeon Olivier:

Comment by Umcglaufllind Olivier:

Comment by Ekjamerkend Ken:

Comment by Itezziodiss Holland:

Comment by Nhuskinsaran Ken:

Comment by Ekjamerkend Ken:

Comment by Lschelneli Vigorda:

Comment by Rankeurensuan Ken:

Comment by Bridesmaidbride Ken:

Comment by Hyherscherwesle Vigorda:

Comment by Aaccajohn Holland:

Comment by Lithrailesmered Olivier:

Comment by Pshopgolf Olivier:

Comment by Hyherscherwesle Vigorda:

Comment by Defeldanni Vigorda:

Comment by Pshopgolf Olivier:

Comment by Rankeurensuan Ken:

Comment by Ohnatowgabr Ken:

Comment by Rnseremmi Vigorda:

Comment by Elissierdeon Olivier:

Comment by Hyherscherwesle Vigorda:

Comment by Defeldanni Vigorda:

Comment by Mwangmajor Holland:

Comment by Rankeurensuan Ken:

Comment by Rnseremmi Vigorda:

Comment by Ekjamerkend Ken:

Comment by Mwangmajor Holland:

Comment by Ntlnoel Holland:

Comment by Itezziodiss Holland:

Comment by Ohnatowgabr Ken:

Comment by Lheeralalkris Olivier:

Comment by Tyamatriley Vigorda:

Comment by Lheeralalkris Olivier:

Comment by Rankeurensuan Ken:

Comment by Ntlnoel Holland:

Comment by Aollwaymyrt Vigorda:

Comment by Ekjamerkend Ken:

Comment by Itezziodiss Holland:

Comment by Milbluemelsherr Ken:

Comment by Ekjamerkend Ken:

Comment by Mwangmajor Holland:

Comment by Lheeralalkris Olivier:

Comment by Hyherscherwesle Vigorda:

Comment by Itezziodiss Holland:

Comment by Lheeralalkris Olivier:

Comment by Lithrailesmered Olivier:

Comment by Milbluemelsherr Ken:

Comment by Aollwaymyrt Vigorda:

Comment by Ntlnoel Holland:

Comment by Milbluemelsherr Ken:

Comment by Corelickcolt Vigorda:

Comment by Nhuskinsaran Ken:

Comment by Itezziodiss Holland:

Comment by Ntlnoel Holland:

Comment by Rankeurensuan Ken:

Comment by Aollwaymyrt Vigorda:

Comment by Pshopgolf Olivier:

Comment by Nhuskinsaran Ken:

Comment by Lithrailesmered Olivier:

Comment by Mwangmajor Holland:

Comment by Ekjamerkend Ken:

Comment by Defeldanni Vigorda:

Comment by Tsmccathedema Ken:

Comment by Ekjamerkend Ken:

Comment by Aollwaymyrt Vigorda:

Comment by Ntlnoel Holland:

Comment by Defeldanni Vigorda:

Comment by Aollwaymyrt Vigorda:

Comment by Itezziodiss Holland:

Comment by Rsalbarrantravi Olivier:

Comment by Bridesmaidbride Ken:

Comment by Ohnatowgabr Ken:

Comment by Milbluemelsherr Ken:

Comment by Tsmccathedema Ken:

Comment by Itezziodiss Holland:

Comment by Tsmccathedema Ken:

Comment by Lithrailesmered Olivier:

Comment by Pshopgolf Olivier:

Comment by Aaccajohn Holland:

Comment by Itezziodiss Holland:

Comment by Ekjamerkend Ken:

Comment by Rsalbarrantravi Olivier:

Comment by Aollwaymyrt Vigorda:

Comment by Ekjamerkend Ken:

Comment by Mwangmajor Holland:

Comment by Lheeralalkris Olivier:

Comment by Aollwaymyrt Vigorda:

Comment by Rsalbarrantravi Olivier:

Comment by Dfeedaro Ken:

Comment by Dsfordthad Holland:

Comment by Ohnatowgabr Ken:

Comment by Ekjamerkend Ken:

Comment by Mwangmajor Holland:

Comment by Elissierdeon Olivier:

Comment by Edesignerparty Holland:

Comment by Elissierdeon Olivier:

Comment by Rankeurensuan Ken:

Comment by Itezziodiss Holland:

Comment by Lheeralalkris Olivier:

Comment by Bridesmaidbride Ken:

Comment by Aaccajohn Holland:

Comment by Ekjamerkend Ken:

Comment by Tyamatriley Vigorda:

Comment by Itezziodiss Holland:

Comment by Elissierdeon Olivier:

Comment by Mwangmajor Holland:

Comment by Tnboydstunmerly Ken:

Comment by Milbluemelsherr Ken:

Comment by Icozzisandy Holland:

Comment by Lheeralalkris Olivier:

Comment by Nshmangayl Olivier:

Comment by Aollwaymyrt Vigorda:

Comment by Aeternaeterna Holland:

Comment by Defeldanni Vigorda:

Comment by Ntlnoel Holland:

Comment by Rnseremmi Vigorda:

Comment by Pshopgolf Olivier:

Comment by Ntlnoel Holland:

Comment by Umcglaufllind Olivier:

Comment by Elissierdeon Olivier:

Comment by Tsmccathedema Ken:

Comment by Aollwaymyrt Vigorda:

Comment by Itezziodiss Holland:

Comment by Elissierdeon Olivier:

Comment by Defeldanni Vigorda:

Comment by Umcglaufllind Olivier:

Comment by Rsalbarrantravi Olivier:

Comment by Tsmccathedema Ken:

Comment by Itezziodiss Holland:

Comment by Nndnilandraymo Ken:

Comment by Ohnatowgabr Ken:

Comment by Pshopgolf Olivier:

Comment by Rankeurensuan Ken:

Comment by Rsalbarrantravi Olivier:

Comment by Defeldanni Vigorda:

Comment by Aollwaymyrt Vigorda:

Comment by Nhuskinsaran Ken:

Comment by Mwangmajor Holland:

Comment by Umcglaufllind Olivier:

Comment by Ekjamerkend Ken:

Comment by Lheeralalkris Olivier:

Comment by Umcglaufllind Olivier:

Comment by Pshopgolf Olivier:

Comment by Mwangmajor Holland:

Comment by Bridesmaidbride Ken:

Comment by Ohnatowgabr Ken:

Comment by Tyamatriley Vigorda:

Comment by Elissierdeon Olivier:

Comment by Aollwaymyrt Vigorda:

Comment by Itezziodiss Holland:

Comment by Lheeralalkris Olivier:

Comment by Elissierdeon Olivier:

Comment by Aaccajohn Holland:

Comment by Mwangmajor Holland:

Comment by Ntlnoel Holland:

Comment by Milbluemelsherr Ken:

Comment by Mwangmajor Holland:

Comment by Aollwaymyrt Vigorda:

Comment by Mwangmajor Holland:

Comment by Tyamatriley Vigorda:

Comment by Aollwaymyrt Vigorda:

Comment by Itezziodiss Holland:

Comment by Uejesusrodg Holland:

Comment by Defeldanni Vigorda:

Comment by Uejesusrodg Holland:

Comment by :

Comment by Umcglaufllind Olivier:

Comment by Lheeralalkris Olivier:

Comment by :

Comment by Itezziodiss Holland:

Comment by Nolsingaubr Holland:

Comment by :

Comment by Rankeurensuan Ken:

Add a new review

Quick Comments

Resources


Download All
Download Paper , View Paper
Download Source code
Source code repository
Github

Statistics more


Global rating:
Review rating:	[review]
Code rating:
Views:	3693
Downloads:	4534
Paper Quality:

Information more


Paper Id:	851
Categories:	Code speed optimization, Data Representation, Mesh
Keywords:	QuadEdgeMesh, ITK, Planar Mesh, Search
Toolkits:	ITK, CMake
Revision:
Export citation:
Status:	Open for public review

Share

Linked Publications more


Diffeomorphic Demons Using ITK's Finite Difference Solver Hierarchy by Vercauteren T., Pennec X., Perchant A., Ayache N.
Reader/Writer for Analyze Object Maps for ITK by Hawley J., Johnson H.
Laplace Beltrami Filter on QuadEdge Meshes by Bowers M., Younes L.
Importing Contours from DICOM-RT Structure Sets by Dowling J., Malaterre M., Greer P.B., Salvado O.
Scalable Simple Linear Iterative Clustering (SSLIC) Using a Generic and Parallel Approach by Lowekamp B., Chen D., Yaniv Z., Yoo T.
Computing Bone Morphometric Feature Maps from 3-Dimensional Images by Vimort J., McCormick M., Paniagua B.
Anisotropic Fast Marching in ITK by Mirebeau J.
ITK in Biomedical Research and Commercial Applications by McCormick M., Aylward S., Johnson H., Lowekamp B.
A Skull-Stripping Filter for ITK by Bauer S., Fejes T., Reyes M.
A Tutorial on Combining Nonlinear Optimization with CUDA by Hatt C.

View license

Loading license...

Send a message to the author