src/glu/mesa/README1

   1
   2 Notes on the GLU polygon tesselation facility implemented by Bogdan Sikorski...
   3
   4
   5
   6 The tesselation module is provided under the same terms as the Mesa
   7 package.
   8
   9 This is the first release of polygon tesselation code for Mesa.
  10 It was written during my very little free time, so lets name it:
  11 "its not perfect". If someone hates pointers, don't look at the code.
  12 I preffer dynamic allocation versus static. But _all_ ideas, suggestions,
  13 bug reports and fixes are welcome (if You want, also flames). I am aware
  14 that many things could have been written using better techniques, but time
  15 that I could devote to this library was very limited. It is not well commented,
  16 excuse me. Also I am thinking of continuing working on this code to improve,
  17 fix and polish it. And make it as compliant as possible to the OpenGL, so
  18 software ports from OpenGL to Mesa will work correctly. If You know of any
  19 differences in behaviour, expected input/output between Mesa tesselation library
  20 and OpenGL, please send me a note. I explain later on why I am not
  21 confident with this code.
  22
  23 I tried to be fully compliant with the OpenGL routines. By "tried" I mean that
  24 up to my knowledge it behaves as OpenGL tesselation routines. Just recently
  25 I began to experiment with OpenGL (actually only Mesa), and also have
  26 no access to any machine providing official implementation of OpenGL,
  27 nor access to books (particulary Addison-Wesley publications). Thus my
  28 knowledge on how the original tesselation code works, what kind of data
  29 it expects etc. is based _only_ on the publicly available documentation
  30 provided by SGI. Namely:
  31
  32 * "The OpenGL Graphics System Utility Library" by K.P.Smith
  33         (Silicon Graphics, 1992)
  34 * "The OpenGL Graphics Interface" by M.Segal and K.Akeley
  35         (Silicon Graphics, 19??)
  36 * "OpenGL and X, Part 1: Introduction" by M.J.Kilgard
  37         (Silicon Graphics, 1994)
  38 * "OpenGL and X, Part 2: Using OpenGL with Xlib" by M.J.Kilgard
  39         (Silicon Graphics, 1994)
  40 * "OpenGL Graphics with the X Window System" by P.Karlton
  41         (Silicon Graphics, 1993)
  42 * Online Docs - Appendix C of OpenGL Programming Guide, Polygon Tesselation
  43          (partial text cut and sent by e-mail)
  44
  45
  46 The tesselation routines use slightly different prototypes than the ones
  47 specified in the mentioned above publications. The _only_ differences are
  48 the enumeration types which are not GLenum, but are GLUenum. So the
  49 implemented routines have following prototypes:
  50
  51 GLUtringulatorObj *gluNewTess(void);
  52
  53 void gluTessCallback(GLUtriangulatorObj *,GLUenum,void (*)());
  54                                           ^^^^^^^
  55 void gluBeginPolygon(GLUtriangulatorObj *);
  56
  57 void gluTessVertex(GLUtriangulatorObj *,GLdouble [3],void *);
  58
  59 void gluNextContour(GLUtriangulatorObj *,GLUenum);
  60                                          ^^^^^^^
  61 void gluEndPolygon(GLUtriangulatorObj *);
  62
  63 const GLubyte *gluErrorString(GLUenum);
  64                               ^^^^^^^
  65         prototypes for callback functions:
  66
  67 void <begin>(GLUenum);
  68              ^^^^^^^
  69 void <edgeFlag>(GLboolean);
  70 void <vertex>(void *);
  71 void <end>(void);
  72 void <error>(GLUenum);
  73              ^^^^^^^
  74
  75 The begin callback will be called only with GLU_TRIANGLES. No support
  76 for traingle fans or strips yet.
  77
  78 In case of errors an internal error variable is set to the appropiate
  79 error enum values (GLU_TESS_ERROR?). Initially it is set to GLU_NO_ERROR.
  80 The OpenGL library provides 8 error conditions, the tesselation code
  81 of Mesa provides 9. They are:
  82
  83 GLU_TESS_ERROR1: missing gluEndPolygon                  /* same as OpenGL */
  84 GLU_TESS_ERROR2: missing gluBeginPolygon                /* same as OpenGL */
  85 GLU_TESS_ERROR3: misoriented contour                    /* not used in Mesa
  86                          in OpenGL is bad orientation or intersecting edges */
  87 GLU_TESS_ERROR4: vertex/edge intersection               /* same as OpenGL */
  88 GLU_TESS_ERROR5: misoriented or self-intersecting loops /* same as OpenGL */
  89 GLU_TESS_ERROR6: coincident vertices                    /* same as OpenGL */
  90 GLU_TESS_ERROR7: colinear vertices                      /* OpenGL's illegal data */
  91 GLU_TESS_ERROR8: intersecting edges                     /* same as OpenGL */
  92 GLU_TESS_ERROR9: not coplanar contours                  /* new for Mesa */
  93
  94 The Mesa tesselation code ignores all data and calls after detecting an error
  95 codition. This means that a _new_ tesselation object must be used for further
  96 triangulations. Maybe this is too restrictive, and will be lifted in
  97 future versions.
  98
  99 The tesselation code completely ignores the type parameter passed in
 100 gluNextContour. It also doesn't check if the passed parameter is a legal
 101 enum value - ignores silently (maybe at least this should be checked).
 102 The reason I chose this behaviour is based on what I read in the
 103 beforementioned documents. I cite:
 104
 105 "....
 106 void gluNextContour(GLUtriangulatorObj *tessobj, GLenum type);
 107
 108 Marks the beginning of the next contour when multiple contours make up the
 109 boundary of the polygon to be tessellated. type can be GLU_EXTERIOR,
 110 GLU_INTERIOR, GLU_CCW, GLU_CW, or GLU_UNKNOWN. These serve only as
 111 to the tessellation. If you get them right, the tessellation might
 112 go faster. If you get them wrong, they're ignored, and the tesselation still
 113 works.
 114 ....."
 115
 116 I hope You agree with me that my decision was correct. Mesa tesselation
 117 _always_ checks by itself the interrelations between contours. Just as if
 118 all contours were specified with the type GLU_UNKNOWN.
 119
 120 One of OpenGL's policy is not to check all error conditions - rely sometimes
 121 that the user "got things right". This is justified, since exhausting
 122 error checking is timeconsuming, and would significantly slow down
 123 a correct application. The Mesa tesselation code assumes only _one_ condition
 124 when triangulating - all vertices in a contour are planar. This is _not_
 125 checked for correctness. Trying to tesselate such objects will lead to
 126 unpredictable output.
 127
 128 And now we arrive to the moment where I would like to list the required
 129 (but checked for) conditions for triangulation, as well as summarize the
 130 library:
 131
 132 * all contours in a single tesselation cycle _must_ be coplanar - if not
 133         an error is raised (and if provided a call to the error callback
 134         is made)
 135 * the contours can be passed in _any_ order, exteriors and holes can be
 136         intermixed within a tesselation cycle and the correct hierarchy
 137         will be determined by the library; thus specifying first holes then
 138         exteriors, then holes within holes form a valid input.
 139 * a hole within a hole is consider to be a yet another exterior contour
 140 * multiple exterior contours (polygons) can be tesselated in one cycle;
 141         _but_ this significantly degrades performance since many tests will be
 142         performed for every contour pair; if You want triangulation to be fast
 143         tesselate a single polygon (with possible holes) one at a time.
 144 * orientation of exterior contours is arbitray, but if it has holes,
 145         all interior holes of this particular exterior contour _must_ have an
 146         opposite orientation.
 147 * the output triangles have the same orientation as the exterior contour
 148         that forms them
 149 * each triangle is "enclosed" within the begin and end callbacks;
 150         this is not efficent, but was made on purpose; so if triangulation
 151         results in 2 triangles the following callbacks will be made in such
 152         order:
 153         <begin>(GLU_TRAINGLES)
 154         <vertex>(...) /* 3 vertices of first triangle */
 155         <vertex>(...)
 156         <vertex>(...)
 157         <end>()
 158         <begin>(GLU_TRAINGLES)
 159         <vertex>(...) /* 3 vertices of second triangle */
 160         <vertex>(...)
 161         <vertex>(...)
 162         <end>()
 163         Of course only when begin, vertex, and end callback were provided,
 164         otherwise no output is done (actually tesselation does not take place).
 165 * You will notice that some output traingles are very "thin"; there
 166         exist possible several ways to traingulate a polygon, but "smart" code
 167         avoiding such cases would require time to write, and will impact on
 168         execution speed.
 169 * like OpenGL, no new vertices are introduced during triangulation
 170 * if the edgeflag callback is provided it will be called whenever
 171         the just-about-to be output vertex begins a different type of edge
 172         than the previous vertices; always before the first output a call
 173         is made with GL_TRUE, to allow synchronization.
 174 * all intermediate computations are done using GLdouble type, and comparisons
 175         are biased with a precision value (EPSILON defined in tess.h)
 176 * the point_in_poly function is my adaptation of code from the
 177         comp.graphics.alg newsgroup FAQ (originally written by Mr. Wm. Randolph
 178         Franklin, modified by Scott Anguish).
 179 * the edge_edge_intersect test is also an adopted code from comp.graphics.alg
 180         newsgroup FAQ
 181 * the general idea for traingulation used in this library is described in
 182         the book "Computational Geometry in C" by Joseph O'Rourke.
 183
 184
 185 Excuse my English, its not my mother tongue. I should be available for some
 186 time uner the following e-mail address. But For how long I am not certain.
 187 Once I am settled in my new place, I'll post on the Mesa mailing list
 188 my new address.
 189
 190 (PS: today is my last day of work here, I'm changing my job).
 191
 192 Bogdan. ( bogdan@dia.unisa.it )
 193
 194 Apr 28, 1995.
 195