Skip to content

This will be a bevy version of the constrained denaulay triangulation, which can be used to create 2d navmeshes

License

Notifications You must be signed in to change notification settings

Arne-Berner/constrained-denaulay-triangulation

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Constrained Delaunay Triangulation

This will seperate any mesh system with holes in it into nicely spaced triangles with only a few vertices.

Source

I mostly used jailbrokengames code and the referenced paper. Also bevy was a heavy inspiration for some data types, but has been stripped to be smaller and more efficient.

TODO

  • refactor things into functions, so that they can be tested (e.g. swap)
  • use impl trait Vector instead, so that consuming libs can impl Vector for their Vec
  • remove all TODO comments
  • Polygons should not need to be in a specific order
  • look for edge cases (hole outside of polygon, half/half, bigger than poly, hole in hole, hole overlapping)
  • only use errors to the outside, that are relevant to the user
  • make the API just the "triangulate" function
  • derive all the important derives
  • test bigger than first polygon input
  • inline functions
  • check what happens if hole point and polygon point are the same
  • use robust crate for float
  • what happens, if any new point is on the line of another triangle?
  • safe the contour of the point cloud, for an "hole out of bounds" error

Holes outside of bounds

If the holes are stretched out outside of the point cloud, then they cannot be triangulated, unless we would keep track of all the actual connections to those very nodes. That would make the algorithm much slower.

About

This will be a bevy version of the constrained denaulay triangulation, which can be used to create 2d navmeshes

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages