View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Getting the true convex hull with Bowyer-Watson algorithm

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

No replies to this topic

### #1timthereaper  Members

Posted 09 April 2012 - 02:30 PM

I'm trying to make a visualization module for Bezier and NURBS surfaces. I figured I'd start with a simple 2D Delaunay triangulation to understand how to divide up the surfaces. I made an implementation of the Bowyer-Watson incremental algorithm and started with a "super triangle" at (3M,0) (0,3M) (-3M,3M), where M is the largest value in X or Y in the set of points. It seems I did the algorithm right because I get a similar triangulation as the Delaunay() function in MATLAB, except I don't get the true convex hull. I've researched for a while and it seems that the "super triangle" method can produce this sort of problem, but I don't know of a good alternative. I tried using the Graham scan algorithm to get the convex hull and somehow combine the two, but I can't figure out how. If anyone is familiar with this problem, please let me know.
"Hofstadter's Law: It always takes longer than you expect, even when you take into account Hofstadter's Law."

-- Douglas Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.