src/glu/mesa/README1

Notes on the GLU polygon tesselation facility implemented by Bogdan Sikorski...



The tesselation module is provided under the same terms as the Mesa
package.

This is the first release of polygon tesselation code for Mesa.
It was written during my very little free time, so lets name it:
"its not perfect". If someone hates pointers, don't look at the code.
I preffer dynamic allocation versus static. But _all_ ideas, suggestions,
bug reports and fixes are welcome (if You want, also flames). I am aware
that many things could have been written using better techniques, but time
that I could devote to this library was very limited. It is not well commented,
excuse me. Also I am thinking of continuing working on this code to improve,
fix and polish it. And make it as compliant as possible to the OpenGL, so
software ports from OpenGL to Mesa will work correctly. If You know of any
differences in behaviour, expected input/output between Mesa tesselation library
and OpenGL, please send me a note. I explain later on why I am not
confident with this code.

I tried to be fully compliant with the OpenGL routines. By "tried" I mean that
up to my knowledge it behaves as OpenGL tesselation routines. Just recently
I began to experiment with OpenGL (actually only Mesa), and also have
no access to any machine providing official implementation of OpenGL,
nor access to books (particulary Addison-Wesley publications). Thus my
knowledge on how the original tesselation code works, what kind of data
it expects etc. is based _only_ on the publicly available documentation
provided by SGI. Namely:

* "The OpenGL Graphics System Utility Library" by K.P.Smith
	(Silicon Graphics, 1992)
* "The OpenGL Graphics Interface" by M.Segal and K.Akeley
	(Silicon Graphics, 19??)
* "OpenGL and X, Part 1: Introduction" by M.J.Kilgard
	(Silicon Graphics, 1994)
* "OpenGL and X, Part 2: Using OpenGL with Xlib" by M.J.Kilgard
	(Silicon Graphics, 1994)
* "OpenGL Graphics with the X Window System" by P.Karlton
	(Silicon Graphics, 1993)
* Online Docs - Appendix C of OpenGL Programming Guide, Polygon Tesselation
	 (partial text cut and sent by e-mail)


The tesselation routines use slightly different prototypes than the ones
specified in the mentioned above publications. The _only_ differences are
the enumeration types which are not GLenum, but are GLUenum. So the
implemented routines have following prototypes:

GLUtringulatorObj *gluNewTess(void);

void gluTessCallback(GLUtriangulatorObj *,GLUenum,void (*)());
                                          ^^^^^^^
void gluBeginPolygon(GLUtriangulatorObj *);

void gluTessVertex(GLUtriangulatorObj *,GLdouble [3],void *);

void gluNextContour(GLUtriangulatorObj *,GLUenum);
                                         ^^^^^^^
void gluEndPolygon(GLUtriangulatorObj *);

const GLubyte *gluErrorString(GLUenum);
                              ^^^^^^^
	prototypes for callback functions:

void <begin>(GLUenum);
             ^^^^^^^
void <edgeFlag>(GLboolean);
void <vertex>(void *);
void <end>(void);
void <error>(GLUenum);
             ^^^^^^^

The begin callback will be called only with GLU_TRIANGLES. No support
for traingle fans or strips yet.	 

In case of errors an internal error variable is set to the appropiate 
error enum values (GLU_TESS_ERROR?). Initially it is set to GLU_NO_ERROR.
The OpenGL library provides 8 error conditions, the tesselation code
of Mesa provides 9. They are:

GLU_TESS_ERROR1: missing gluEndPolygon                  /* same as OpenGL */
GLU_TESS_ERROR2: missing gluBeginPolygon                /* same as OpenGL */
GLU_TESS_ERROR3: misoriented contour                    /* not used in Mesa
                         in OpenGL is bad orientation or intersecting edges */
GLU_TESS_ERROR4: vertex/edge intersection               /* same as OpenGL */
GLU_TESS_ERROR5: misoriented or self-intersecting loops /* same as OpenGL */
GLU_TESS_ERROR6: coincident vertices                    /* same as OpenGL */
GLU_TESS_ERROR7: colinear vertices                      /* OpenGL's illegal data */
GLU_TESS_ERROR8: intersecting edges                     /* same as OpenGL */
GLU_TESS_ERROR9: not coplanar contours                  /* new for Mesa */

The Mesa tesselation code ignores all data and calls after detecting an error
codition. This means that a _new_ tesselation object must be used for further
triangulations. Maybe this is too restrictive, and will be lifted in
future versions.

The tesselation code completely ignores the type parameter passed in
gluNextContour. It also doesn't check if the passed parameter is a legal
enum value - ignores silently (maybe at least this should be checked).
The reason I chose this behaviour is based on what I read in the 
beforementioned documents. I cite:

"....
void gluNextContour(GLUtriangulatorObj *tessobj, GLenum type);

Marks the beginning of the next contour when multiple contours make up the
boundary of the polygon to be tessellated. type can be GLU_EXTERIOR,
GLU_INTERIOR, GLU_CCW, GLU_CW, or GLU_UNKNOWN. These serve only as 
to the tessellation. If you get them right, the tessellation might
go faster. If you get them wrong, they're ignored, and the tesselation still
works.
....."

I hope You agree with me that my decision was correct. Mesa tesselation
_always_ checks by itself the interrelations between contours. Just as if
all contours were specified with the type GLU_UNKNOWN.

One of OpenGL's policy is not to check all error conditions - rely sometimes
that the user "got things right". This is justified, since exhausting
error checking is timeconsuming, and would significantly slow down
a correct application. The Mesa tesselation code assumes only _one_ condition
when triangulating - all vertices in a contour are planar. This is _not_
checked for correctness. Trying to tesselate such objects will lead to
unpredictable output.

And now we arrive to the moment where I would like to list the required
(but checked for) conditions for triangulation, as well as summarize the
library:

* all contours in a single tesselation cycle _must_ be coplanar - if not
	an error is raised (and if provided a call to the error callback
	is made)
* the contours can be passed in _any_ order, exteriors and holes can be
	intermixed within a tesselation cycle and the correct hierarchy
	will be determined by the library; thus specifying first holes then
	exteriors, then holes within holes form a valid input.
* a hole within a hole is consider to be a yet another exterior contour
* multiple exterior contours (polygons) can be tesselated in one cycle;
	_but_ this significantly degrades performance since many tests will be
	performed for every contour pair; if You want triangulation to be fast
	tesselate a single polygon (with possible holes) one at a time.
* orientation of exterior contours is arbitray, but if it has holes,
	all interior holes of this particular exterior contour _must_ have an
	opposite orientation.
* the output triangles have the same orientation as the exterior contour
	that forms them
* each triangle is "enclosed" within the begin and end callbacks;
	this is not efficent, but was made on purpose; so if triangulation
	results in 2 triangles the following callbacks will be made in such
	order:
	<begin>(GLU_TRAINGLES)
	<vertex>(...) /* 3 vertices of first triangle */
	<vertex>(...)
	<vertex>(...)
	<end>()
	<begin>(GLU_TRAINGLES)
	<vertex>(...) /* 3 vertices of second triangle */
	<vertex>(...)
	<vertex>(...)
	<end>()
	Of course only when begin, vertex, and end callback were provided,
	otherwise no output is done (actually tesselation does not take place).
* You will notice that some output traingles are very "thin"; there
	exist possible several ways to traingulate a polygon, but "smart" code
	avoiding such cases would require time to write, and will impact on
	execution speed.
* like OpenGL, no new vertices are introduced during triangulation
* if the edgeflag callback is provided it will be called whenever
	the just-about-to be output vertex begins a different type of edge
	than the previous vertices; always before the first output a call
	is made with GL_TRUE, to allow synchronization.
* all intermediate computations are done using GLdouble type, and comparisons
	are biased with a precision value (EPSILON defined in tess.h)
* the point_in_poly function is my adaptation of code from the
	comp.graphics.alg newsgroup FAQ (originally written by Mr. Wm. Randolph
	Franklin, modified by Scott Anguish).
* the edge_edge_intersect test is also an adopted code from comp.graphics.alg
	newsgroup FAQ
* the general idea for traingulation used in this library is described in
	the book "Computational Geometry in C" by Joseph O'Rourke.


Excuse my English, its not my mother tongue. I should be available for some
time uner the following e-mail address. But For how long I am not certain.
Once I am settled in my new place, I'll post on the Mesa mailing list
my new address.

(PS: today is my last day of work here, I'm changing my job).

Bogdan. ( bogdan@dia.unisa.it )

Apr 28, 1995.