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