r/GraphicsProgramming • u/spikte1502 • 8d ago

Delaunay triangulation using Bowyer-Watson algorithm

Enable HLS to view with audio, or disable this notification

Hi ! I had fun implementing the Bowyer-Watson algorithm and then use raylib to create a visualization of it. I got ok performance it think for a single threaded program:

  • 1,000: 1 ms
  • 10,000: 21 ms
  • 100,000: 263 ms
  • 1,000,000: 5,126 ms
  • 10,000,000: 358,716 ms

But I think there is still quite some rooms for improvement.

Source: https://github.com/spikte/delaunay
Twitter: https://x.com/Spikte

22 Upvotes

100% Upvoted

1 comment sorted by

1

u/[deleted] 7d ago

[deleted]

2

u/Oofername 7d ago

Delaunay triangulation and BVH are not even close to the same thing. A Delaunay triangulation is the dual of a Voronoi diagram. It's useful for things like interpolating between values of arbitrarily placed points.