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.