diff options
Diffstat (limited to 'src/glu/mesa/README1')
| -rw-r--r-- | src/glu/mesa/README1 | 195 |
1 files changed, 195 insertions, 0 deletions
diff --git a/src/glu/mesa/README1 b/src/glu/mesa/README1 new file mode 100644 index 00000000000..75968572ff6 --- /dev/null +++ b/src/glu/mesa/README1 @@ -0,0 +1,195 @@ + +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. ( [email protected] ) + +Apr 28, 1995. + |