summaryrefslogtreecommitdiff
path: root/src/glu/mesa/README1
diff options
context:
space:
mode:
Diffstat (limited to 'src/glu/mesa/README1')
-rw-r--r--src/glu/mesa/README1195
1 files changed, 195 insertions, 0 deletions
diff --git a/src/glu/mesa/README1 b/src/glu/mesa/README1
new file mode 100644
index 0000000000..75968572ff
--- /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. ( bogdan@dia.unisa.it )
+
+Apr 28, 1995.
+