← Back to branch summary

~ubuntu-branches/ubuntu/raring/qtwebkit-source/raring-proposed

« back to all changes in this revision

Viewing changes to Source/ThirdParty/glu/libtess/alg-outline

  • Committer: Package Import Robot
  • Author(s): Jonathan Riddell
  • Date: 2013-02-18 14:24:18 UTC
  • Revision ID: package-import@ubuntu.com-20130218142418-eon0jmjg3nj438uy
Tags: upstream-2.3
Import upstream version 2.3

Show diffs side-by-side

added added

removed removed

Lines of Context:
Source/ThirdParty/glu/libtess/alg-outline
 
1
/*
 
2
** $Header: /cvs/projects/ogl-sample/main/gfx/lib/glu/libtess/alg-outline,v 1.1 2000/04/26 05:53:59 ljp Exp $
 
3
*/
 
4
 
 
5
This is only a very brief overview.  There is quite a bit of
 
6
additional documentation in the source code itself.
 
7
 
 
8
 
 
9
Goals of robust tesselation
 
10
---------------------------
 
11
 
 
12
The tesselation algorithm is fundamentally a 2D algorithm.  We
 
13
initially project all data into a plane; our goal is to robustly
 
14
tesselate the projected data.  The same topological tesselation is
 
15
then applied to the input data.
 
16
 
 
17
Topologically, the output should always be a tesselation.  If the
 
18
input is even slightly non-planar, then some triangles will
 
19
necessarily be back-facing when viewed from some angles, but the goal
 
20
is to minimize this effect.
 
21
 
 
22
The algorithm needs some capability of cleaning up the input data as
 
23
well as the numerical errors in its own calculations.  One way to do
 
24
this is to specify a tolerance as defined above, and clean up the
 
25
input and output during the line sweep process.  At the very least,
 
26
the algorithm must handle coincident vertices, vertices incident to an
 
27
edge, and coincident edges.
 
28
 
 
29
 
 
30
Phases of the algorithm
 
31
-----------------------
 
32
 
 
33
1. Find the polygon normal N.
 
34
2. Project the vertex data onto a plane.  It does not need to be
 
35
   perpendicular to the normal, eg. we can project onto the plane
 
36
   perpendicular to the coordinate axis whose dot product with N
 
37
   is largest.
 
38
3. Using a line-sweep algorithm, partition the plane into x-monotone
 
39
   regions.  Any vertical line intersects an x-monotone region in
 
40
   at most one interval.
 
41
4. Triangulate the x-monotone regions.
 
42
5. Group the triangles into strips and fans.
 
43
 
 
44
 
 
45
Finding the normal vector
 
46
-------------------------
 
47
 
 
48
A common way to find a polygon normal is to compute the signed area
 
49
when the polygon is projected along the three coordinate axes.  We
 
50
can't do this, since contours can have zero area without being
 
51
degenerate (eg. a bowtie).
 
52
 
 
53
We fit a plane to the vertex data, ignoring how they are connected
 
54
into contours.  Ideally this would be a least-squares fit; however for
 
55
our purpose the accuracy of the normal is not important.  Instead we
 
56
find three vertices which are widely separated, and compute the normal
 
57
to the triangle they form.  The vertices are chosen so that the
 
58
triangle has an area at least 1/sqrt(3) times the largest area of any
 
59
triangle formed using the input vertices.  
 
60
 
 
61
The contours do affect the orientation of the normal; after computing
 
62
the normal, we check that the sum of the signed contour areas is
 
63
non-negative, and reverse the normal if necessary.
 
64
 
 
65
 
 
66
Projecting the vertices
 
67
-----------------------
 
68
 
 
69
We project the vertices onto a plane perpendicular to one of the three
 
70
coordinate axes.  This helps numerical accuracy by removing a
 
71
transformation step between the original input data and the data
 
72
processed by the algorithm.  The projection also compresses the input
 
73
data; the 2D distance between vertices after projection may be smaller
 
74
than the original 2D distance.  However by choosing the coordinate
 
75
axis whose dot product with the normal is greatest, the compression
 
76
factor is at most 1/sqrt(3).
 
77
 
 
78
Even though the *accuracy* of the normal is not that important (since
 
79
we are projecting perpendicular to a coordinate axis anyway), the
 
80
*robustness* of the computation is important.  For example, if there
 
81
are many vertices which lie almost along a line, and one vertex V
 
82
which is well-separated from the line, then our normal computation
 
83
should involve V otherwise the results will be garbage.
 
84
 
 
85
The advantage of projecting perpendicular to the polygon normal is
 
86
that computed intersection points will be as close as possible to
 
87
their ideal locations.  To get this behavior, define TRUE_PROJECT.
 
88
 
 
89
 
 
90
The Line Sweep
 
91
--------------
 
92
 
 
93
There are three data structures: the mesh, the event queue, and the
 
94
edge dictionary.
 
95
 
 
96
The mesh is a "quad-edge" data structure which records the topology of
 
97
the current decomposition; for details see the include file "mesh.h".
 
98
 
 
99
The event queue simply holds all vertices (both original and computed
 
100
ones), organized so that we can quickly extract the vertex with the
 
101
minimum x-coord (and among those, the one with the minimum y-coord).
 
102
 
 
103
The edge dictionary describes the current intersection of the sweep
 
104
line with the regions of the polygon.  This is just an ordering of the
 
105
edges which intersect the sweep line, sorted by their current order of
 
106
intersection.  For each pair of edges, we store some information about
 
107
the monotone region between them -- these are call "active regions"
 
108
(since they are crossed by the current sweep line).
 
109
 
 
110
The basic algorithm is to sweep from left to right, processing each
 
111
vertex.  The processed portion of the mesh (left of the sweep line) is
 
112
a planar decomposition.  As we cross each vertex, we update the mesh
 
113
and the edge dictionary, then we check any newly adjacent pairs of
 
114
edges to see if they intersect.
 
115
 
 
116
A vertex can have any number of edges.  Vertices with many edges can
 
117
be created as vertices are merged and intersection points are
 
118
computed.  For unprocessed vertices (right of the sweep line), these
 
119
edges are in no particular order around the vertex; for processed
 
120
vertices, the topological ordering should match the geometric ordering.
 
121
 
 
122
The vertex processing happens in two phases: first we process are the
 
123
left-going edges (all these edges are currently in the edge
 
124
dictionary).  This involves:
 
125
 
 
126
 - deleting the left-going edges from the dictionary;
 
127
 - relinking the mesh if necessary, so that the order of these edges around
 
128
   the event vertex matches the order in the dictionary;
 
129
 - marking any terminated regions (regions which lie between two left-going
 
130
   edges) as either "inside" or "outside" according to their winding number.
 
131
 
 
132
When there are no left-going edges, and the event vertex is in an
 
133
"interior" region, we need to add an edge (to split the region into
 
134
monotone pieces).  To do this we simply join the event vertex to the
 
135
rightmost left endpoint of the upper or lower edge of the containing
 
136
region.
 
137
 
 
138
Then we process the right-going edges.  This involves:
 
139
 
 
140
 - inserting the edges in the edge dictionary;
 
141
 - computing the winding number of any newly created active regions.
 
142
   We can compute this incrementally using the winding of each edge
 
143
   that we cross as we walk through the dictionary.
 
144
 - relinking the mesh if necessary, so that the order of these edges around
 
145
   the event vertex matches the order in the dictionary;
 
146
 - checking any newly adjacent edges for intersection and/or merging.
 
147
 
 
148
If there are no right-going edges, again we need to add one to split
 
149
the containing region into monotone pieces.  In our case it is most
 
150
convenient to add an edge to the leftmost right endpoint of either
 
151
containing edge; however we may need to change this later (see the
 
152
code for details).
 
153
 
 
154
 
 
155
Invariants
 
156
----------
 
157
 
 
158
These are the most important invariants maintained during the sweep.
 
159
We define a function VertLeq(v1,v2) which defines the order in which
 
160
vertices cross the sweep line, and a function EdgeLeq(e1,e2; loc)
 
161
which says whether e1 is below e2 at the sweep event location "loc".
 
162
This function is defined only at sweep event locations which lie
 
163
between the rightmost left endpoint of {e1,e2}, and the leftmost right
 
164
endpoint of {e1,e2}.
 
165
 
 
166
Invariants for the Edge Dictionary.
 
167
 
 
168
 - Each pair of adjacent edges e2=Succ(e1) satisfies EdgeLeq(e1,e2)
 
169
   at any valid location of the sweep event.
 
170
 - If EdgeLeq(e2,e1) as well (at any valid sweep event), then e1 and e2
 
171
   share a common endpoint.
 
172
 - For each e in the dictionary, e->Dst has been processed but not e->Org.
 
173
 - Each edge e satisfies VertLeq(e->Dst,event) && VertLeq(event,e->Org)
 
174
   where "event" is the current sweep line event.
 
175
 - No edge e has zero length.
 
176
 - No two edges have identical left and right endpoints.
 
177
 
 
178
Invariants for the Mesh (the processed portion).
 
179
 
 
180
 - The portion of the mesh left of the sweep line is a planar graph,
 
181
   ie. there is *some* way to embed it in the plane.
 
182
 - No processed edge has zero length.
 
183
 - No two processed vertices have identical coordinates.
 
184
 - Each "inside" region is monotone, ie. can be broken into two chains
 
185
   of monotonically increasing vertices according to VertLeq(v1,v2)
 
186
   - a non-invariant: these chains may intersect (slightly) due to
 
187
     numerical errors, but this does not affect the algorithm's operation.
 
188
 
 
189
Invariants for the Sweep.
 
190
 
 
191
 - If a vertex has any left-going edges, then these must be in the edge
 
192
   dictionary at the time the vertex is processed.
 
193
 - If an edge is marked "fixUpperEdge" (it is a temporary edge introduced
 
194
   by ConnectRightVertex), then it is the only right-going edge from
 
195
   its associated vertex.  (This says that these edges exist only
 
196
   when it is necessary.)
 
197
 
 
198
 
 
199
Robustness
 
200
----------
 
201
 
 
202
The key to the robustness of the algorithm is maintaining the
 
203
invariants above, especially the correct ordering of the edge
 
204
dictionary.  We achieve this by:
 
205
 
 
206
  1. Writing the numerical computations for maximum precision rather
 
207
     than maximum speed.
 
208
     
 
209
  2. Making no assumptions at all about the results of the edge
 
210
     intersection calculations -- for sufficiently degenerate inputs,
 
211
     the computed location is not much better than a random number.
 
212
     
 
213
  3. When numerical errors violate the invariants, restore them
 
214
     by making *topological* changes when necessary (ie. relinking
 
215
     the mesh structure).
 
216
     
 
217
     
 
218
Triangulation and Grouping
 
219
--------------------------
 
220
 
 
221
We finish the line sweep before doing any triangulation.  This is
 
222
because even after a monotone region is complete, there can be further
 
223
changes to its vertex data because of further vertex merging.
 
224
 
 
225
After triangulating all monotone regions, we want to group the
 
226
triangles into fans and strips.  We do this using a greedy approach.
 
227
The triangulation itself is not optimized to reduce the number of
 
228
primitives; we just try to get a reasonable decomposition of the
 
229
computed triangulation.