Initial revision

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.
+