beltranamenabar / polylla-mesh-dcel

Polylla's algorithm as a library

Polylla: Polygonal meshing algorithm based on terminal-edge regions

New algorithm to generate polygonal meshes of arbitrary shape, using any kind of triangulation as input, adaptable to any kind of complex geometry, no addition of extra points and uses the classic Doubly connected edge list (Half edge data struct) easy to implement wih another programming language.

The algorithm needs a initial triangulation as input, any triangulations will work, in the following Figure the example of a Planar Straigh Line Graph (PSLG) with holes (left image), triangulizated (middle image) to generate a Polylla mesh (right image).

IO formats

The algorithm supports two file formats as input, the output is an .off file and an .ale file use for the VEM.

Input as .node, .ele, .neigh files

Triangulation is represented as a .node file with the nodes of the triangulations and the boundary marker, .ele file with the triangles of the triangulations and a .neigh file with the adjacencies of each triangle.

Input commands of polylla are:

./Polylla <input .node> <input .ele> <input .neigh> <output filename>

Example to generate pikachu

./Polylla ./Polylla pikachu.1.node pikachu.1.ele pikachu.1.neigh out

Input as a .off file

./Polylla <input .off> <output filename>

Shape of polygons

Note shape of the polygon depend on the initital triangulation, in the folowing Figure there is a example of a disk generate with a Delaunay Triangulation with random points (left image) vs a refined Delaunay triangulation with semi uniform points (right image).

Scripts

Scripts made to facilizate the process of test the algorithm:

• (in build folder) To generate random points, an initital triangulation and a poylla mesh

  ./generatemesh.sh <number of vertices of triangulation>
  

• (in build folder) To generate mesh from files .node, .ele, .neigh with the same name

  ./generatefromfile.sh <filename> <output name>
  

   ./generatefromfile.sh pikachu.1 out
  

Triangulazitation are generated with triangle with the command -zn.

TODO

TODO scripts

• Line 45 of plotting depends on a transpose, store edges directly as the transpose of edge vectors and remove it.
• Define an input and output folder scripts
• Define -n in plot_triangulation.py to avoid label edges and vertices
• Change name plot_triangulation.py to plot_mesh.py

TODO Poylla

• Travel phase does not work with over big meshes (10^7)
• Add high float point precision edge lenght comparision
• POSIBLE BUG: el algoritmo no viaja por todos los halfedges dentro de un poligono en la travel phase, por lo que pueden haber semillas que no se borren y tener poligonos repetidos de output
• Add arbitrary precision arithmetic in the label phase
• Add frontier-edge addition to constrained segmend and refinement (agregar método que dividida un polygono dado una arista especifica)
• hacer la función distance parte de cada halfedge y cambiar el ciclo por 3 comparaciones.
• Add way to store polygons.
• iterador de polygono
• Vector con los poligonos de malla
• Método para imprimir SVG
• Copy constructor
• half-edge constructor
• Change by triangle bitvector by triangle list
• Remove distance edge

TODO Halfedges

• edge_iterator;
• face_iterator;
• vertex_iterator;
• copy constructor;
• constructor indepent of triangle (any off file now works)
• default constructor
• definir mejor cuáles variables son unsigned int y cuáles no
• Change by triangle bitvector by triangle list
• Calculate distante edge
• Read node files with commentaries

TODO C++

• change to std::size_t to int
• change operator [] by .at()
• add #ifndef ALL_H_FILES #define ALL_H_FILES #endif to being and end header
• add google tests
• Add google benchmark

TODO github

• Add how generate mesh from OFF file
• Add images that show how the initial trangulization changes the output
• Add the triangulation of the disks
• Hacer el readme más explicativo
• Add example meshes
• Add .gitignore
• Poner en inglés uwu