Walk In A Triangulation : Straight Walk
logo

Please use this identifier to cite or link to this publication: http://hdl.handle.net/10380/3341
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
minus Automatic Testing Results by Insight-Journal Dashboard on Tue Jan 29 17:14:47 2013 for revision #1
starstarstarstarstar expertise: 5 sensitivity: 3.5
yellow CMake was unable to configure this project.
Click here for more details.

Go here to access the main testing dashboard.

Reviews
minus A useful function, but with some build difficulty. by Davis Vigneault on 2015-06-09 09:57:49 for revision #1
starstarstarstarstar expertise: 2 sensitivity: 3.5
yellow
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:

NA

Evidence:

NA

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 :

NA

Interest:

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


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Ntlnoel Holland: yellow


Comment by Ntlnoel Holland: yellow


Comment by Ntlnoel Holland: yellow


Comment by Rnseremmi Vigorda: yellow


Comment by Rnseremmi Vigorda: yellow


Comment by Rnseremmi Vigorda: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Ntlnoel Holland: yellow


Comment by Ntlnoel Holland: yellow


Comment by Ntlnoel Holland: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Rsalbarrantravi Olivier: yellow


Comment by Rsalbarrantravi Olivier: yellow


Comment by Rsalbarrantravi Olivier: yellow


Comment by Rsalbarrantravi Olivier: yellow


Comment by Rsalbarrantravi Olivier: yellow


Comment by Rsalbarrantravi Olivier: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Tsmccathedema Ken: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Nndnilandraymo Ken: yellow


Comment by Nndnilandraymo Ken: yellow


Comment by Nndnilandraymo Ken: yellow


Comment by Ohnatowgabr Ken: yellow


Comment by Ohnatowgabr Ken: yellow


Comment by Ohnatowgabr Ken: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Rankeurensuan Ken: yellow


Comment by Rankeurensuan Ken: yellow


Comment by Rankeurensuan Ken: yellow


Comment by Rsalbarrantravi Olivier: yellow


Comment by Rsalbarrantravi Olivier: yellow


Comment by Rsalbarrantravi Olivier: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Nhuskinsaran Ken: yellow


Comment by Nhuskinsaran Ken: yellow


Comment by Nhuskinsaran Ken: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Ekjamerkend Ken: yellow


Comment by Ekjamerkend Ken: yellow


Comment by Ekjamerkend Ken: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Pshopgolf Olivier: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Bridesmaidbride Ken: yellow


Comment by Ohnatowgabr Ken: yellow


Comment by Ohnatowgabr Ken: yellow


Comment by Ohnatowgabr Ken: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Elissierdeon Olivier: yellow


Comment by Aaccajohn Holland: yellow


Comment by Aaccajohn Holland: yellow


Comment by Aaccajohn Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Ntlnoel Holland: yellow


Comment by Ntlnoel Holland: yellow


Comment by Ntlnoel Holland: yellow


Comment by Milbluemelsherr Ken: yellow


Comment by Milbluemelsherr Ken: yellow


Comment by Milbluemelsherr Ken: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Mwangmajor Holland: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Tyamatriley Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Aollwaymyrt Vigorda: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Uejesusrodg Holland: yellow


Comment by Uejesusrodg Holland: yellow


Comment by Uejesusrodg Holland: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Defeldanni Vigorda: yellow


Comment by Uejesusrodg Holland: yellow


Comment by Uejesusrodg Holland: yellow


Comment by Uejesusrodg Holland: yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Umcglaufllind Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by Lheeralalkris Olivier: yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Itezziodiss Holland: yellow


Comment by Nolsingaubr Holland: yellow


Comment by Nolsingaubr Holland: yellow


Comment by Nolsingaubr Holland: yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by : yellow


Comment by Rankeurensuan Ken: yellow

Add a new review
Quick Comments


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

Statistics more
backyellow
Global rating: starstarstarstarstar
Review rating: starstarstarstarstar [review]
Code rating: starstarstarstarstar
Paper Quality: plus minus

Information more
backyellow
Categories: Code speed optimization, Data Representation, Mesh
Keywords: QuadEdgeMesh, ITK, Planar Mesh, Search
Toolkits: ITK, CMake
Export citation:

Share
backyellow
Share

Linked Publications more
backyellow
Diffeomorphic Demons Using ITK's Finite Difference Solver Hierarchy Diffeomorphic Demons Using ITK's Finite Difference Solver Hierarchy
by Vercauteren T., Pennec X., Perchant A., Ayache N.
Laplace Beltrami Filter on QuadEdge Meshes Laplace Beltrami Filter on QuadEdge Meshes
by Bowers M., Younes L.

View license
Loading license...

Send a message to the author
main_flat
ISSN 2327-770X
Powered by Midas