Sent: Thursday, December 25, 2008 9:39 PM To: Ben Discoe Subject: Narkhede Triangulation == Bad Hi Ben, You mentioned Narkhede's implementation of triangulation code: http://vterrain.org/Implementation/Libs/triangulate.html You raised some reservations. I'll raise some more... :-) I've been trying to get a triangulation working and chose Narkhede. Quickly ran into problems, so I introduced runtime array range checking it. I've found enough errors to give me concern. e.g. Take a look at the below code; it looks at *EVERY* single slot in the trapezoid tr array: > /* First locate a trapezoid which lies inside the polygon */ > /* and which is triangular */ > for (i = 0; i < TRSIZE; i++) > if (inside_polygon(&tr[i])) > break; > tr_start = i; TRSIZE itself is a "pick a really big number" constant, so this is inefficient for starters, but note how he sets tr_start at the end of the loop. If it combed the entire thing and picked nothing, it would be TRSIZE and so out of bounds of tr[TRSIZE] Then right below he does this: > /* traverse the polygon */ > if (tr[tr_start].u0 > 0) > traverse_polygon(0, tr_start, tr[tr_start].u0, TR_FROM_UP); Bingo. Out of bounds error. I actually fixed this, but got a little further and found two other bounds bugs elsewhere. I've blown about a week on this thing. The whole point of books like 'Graphics Gems' is they're supposed to save you the time and effort of duplicating and debugging the very same wheel. I googled around and found Narkhede's implementation in Graphics gems described as "buggy" (though no explanation of *what* or how to fix it). Yet all the 'Graphics Gems' errata for this chapter only says: p. 394: Atul Narkhede's email address is now atul@yamuna.asd.sgi.com http://tog.acm.org/GraphicsGems/Errata.GraphicsGemsV Ugh. [..] I'm off to try something else, but thought you might want to update the triangulation code with a 'lose hope ye who enter'. [..] cheers