1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
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.
|
