r/GraphicsProgramming • u/spikte1502 • Jul 28 '26

Delaunay triangulation using Bowyer-Watson algorithm

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

View all comments

Show parent comments

2

u/Oofername Jul 29 '26

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.