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
196
197
198
199
200
201
202
203
204
205
206
207
208
209
|
/*
** SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
** Copyright (C) [dates of first publication] Silicon Graphics, Inc.
** All Rights Reserved.
**
** Permission is hereby granted, free of charge, to any person obtaining a copy
** of this software and associated documentation files (the "Software"), to deal
** in the Software without restriction, including without limitation the rights
** to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
** of the Software, and to permit persons to whom the Software is furnished to do so,
** subject to the following conditions:
**
** The above copyright notice including the dates of first publication and either this
** permission notice or a reference to http://oss.sgi.com/projects/FreeB/ shall be
** included in all copies or substantial portions of the Software.
**
** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
** INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
** PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL SILICON GRAPHICS, INC.
** BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
** TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE
** OR OTHER DEALINGS IN THE SOFTWARE.
**
** Except as contained in this notice, the name of Silicon Graphics, Inc. shall not
** be used in advertising or otherwise to promote the sale, use or other dealings in
** this Software without prior written authorization from Silicon Graphics, Inc.
*/
/*
** Author: Mikko Mononen, July 2009.
*/
#ifndef TESSELATOR_H
#define TESSELATOR_H
#ifdef __cplusplus
extern "C" {
#endif
// See OpenGL Red Book for description of the winding rules
// http://www.glprogramming.com/red/chapter11.html
enum TessWindingRule
{
TESS_WINDING_ODD,
TESS_WINDING_NONZERO,
TESS_WINDING_POSITIVE,
TESS_WINDING_NEGATIVE,
TESS_WINDING_ABS_GEQ_TWO,
};
// The contents of the tessGetElements() depends on element type being passed to tessTesselate().
// Tesselation result element types:
// TESS_POLYGONS
// Each element in the element array is polygon defined as 'polySize' number of vertex indices.
// If a polygon has than 'polySize' vertices, the remaining indices are stored as TESS_UNDEF.
// Example, drawing a polygon:
// const int nelems = tessGetElementCount(tess);
// const TESSindex* elems = tessGetElements(tess);
// for (int i = 0; i < nelems; i++) {
// const TESSindex* poly = &elems[i * polySize];
// glBegin(GL_POLYGON);
// for (int j = 0; j < polySize; j++) {
// if (poly[j] == TESS_UNDEF) break;
// glVertex2fv(&verts[poly[j]*vertexSize]);
// }
// glEnd();
// }
//
// TESS_CONNECTED_POLYGONS
// Each element in the element array is polygon defined as 'polySize' number of vertex indices,
// followed by 'polySize' indices to neighour polygons, that is each element is 'polySize' * 2 indices.
// If a polygon has than 'polySize' vertices, the remaining indices are stored as TESS_UNDEF.
// If a polygon edge is a boundary, that is, not connected to another polygon, the neighbour index is TESS_UNDEF.
// Example, flood fill based on seed polygon:
// const int nelems = tessGetElementCount(tess);
// const TESSindex* elems = tessGetElements(tess);
// unsigned char* visited = (unsigned char*)calloc(nelems);
// TESSindex stack[50];
// int nstack = 0;
// stack[nstack++] = seedPoly;
// visited[startPoly] = 1;
// while (nstack > 0) {
// TESSindex idx = stack[--nstack];
// const TESSindex* poly = &elems[idx * polySize * 2];
// const TESSindex* nei = &poly[polySize];
// for (int i = 0; i < polySize; i++) {
// if (poly[i] == TESS_UNDEF) break;
// if (nei[i] != TESS_UNDEF && !visited[nei[i]])
// stack[nstack++] = nei[i];
// visited[nei[i]] = 1;
// }
// }
// }
//
// TESS_BOUNDARY_CONTOURS
// Each element in the element array is [base index, count] pair defining a range of vertices for a contour.
// The first value is index to first vertex in contour and the second value is number of vertices in the contour.
// Example, drawing contours:
// const int nelems = tessGetElementCount(tess);
// const TESSindex* elems = tessGetElements(tess);
// for (int i = 0; i < nelems; i++) {
// const TESSindex base = elems[i * 2];
// const TESSindex count = elems[i * 2 + 1];
// glBegin(GL_LINE_LOOP);
// for (int j = 0; j < count; j++) {
// glVertex2fv(&verts[(base+count) * vertexSize]);
// }
// glEnd();
// }
//
enum TessElementType
{
TESS_POLYGONS,
TESS_CONNECTED_POLYGONS,
TESS_BOUNDARY_CONTOURS,
};
typedef float TESSreal;
typedef int TESSindex;
typedef struct TESStesselator TESStesselator;
typedef struct TESSalloc TESSalloc;
#define TESS_UNDEF (~(TESSindex)0)
// Custom memory allocator interface.
// The internal memory allocator allocates mesh edges, vertices and faces
// as well as dictionary nodes and active regions in buckets and uses simple
// freelist to speed up the allocation. The bucket size should roughly match your
// expected input data. For example if you process only hundreds of vertices,
// a bucket size of 128 might be ok, where as when processing thousands of vertices
// bucket size of 1024 might be approproate. The bucket size is a compromise between
// how often to allocate memory from the system versus how much extra space the system
// should allocate. Reasonable defaults are show in commects below, they will be used if
// the bucket sizes are zero.
//
// The use may left the memrealloc to be null. In that case, the tesselator will not try to
// dynamically grow int's internal arrays. The tesselator only needs the reallocation when it
// has found intersecting segments and needs to add new vertex. This defency can be cured by
// allocating some extra vertices beforehand. The 'extraVertices' variable allows to specify
// number of expected extra vertices.
struct TESSalloc
{
void *(*memalloc)( void *userData, unsigned int size );
void *(*memrealloc)( void *userData, void* ptr, unsigned int size );
void (*memfree)( void *userData, void *ptr );
void* userData; // User data passed to the allocator functions.
int meshEdgeBucketSize; // 512
int meshVertexBucketSize; // 512
int meshFaceBucketSize; // 256
int dictNodeBucketSize; // 512
int regionBucketSize; // 256
int extraVertices; // Number of extra vertices allocated for the priority queue.
};
// tessNewTess() - Creates a new tesselator.
// Use tessDeleteTess() to delete the tesselator.
// Returns:
// new tesselator object.
TESStesselator* tessNewTess( TESSalloc* alloc );
// tessDeleteTess() - Deletes a tesselator.
// Parameters:
// tess - pointer to tesselator object to be deleted.
void tessDeleteTess( TESStesselator *tess );
// tessAddContour() - Adds a contour to be tesselated.
// The type of the vertex coordinates is assumed to be TESSreal.
// Parameters:
// tess - pointer to tesselator object.
// size - number of coordinates per vertex. Must be 2 or 3.
// pointer - pointer to the first coordinate of the first vertex in the array.
// stride - defines offset in bytes between consecutive vertices.
// count - number of vertices in contour.
void tessAddContour( TESStesselator *tess, int size, const void* pointer, int stride, int count );
// tessTesselate() - tesselate contours.
// Parameters:
// tess - pointer to tesselator object.
// windingRule - winding rules used for tesselation, must be one of TessWindingRule.
// elementType - defines the tesselation result element type, must be one of TessElementType.
// polySize - defines maximum vertices per polygons if output is polygons.
// vertexSize - defines the number of coordinates in tesselation result vertex, must be 2 or 3.
// normal - defines the normal of the input contours, of null the normal is calculated automatically.
// Returns:
// 1 if succeed, 0 if failed.
int tessTesselate( TESStesselator *tess, int windingRule, int elementType, int polySize, int vertexSize, const TESSreal* normal );
// tessGetVertexCount() - Returns number of vertices in the tesselated output.
int tessGetVertexCount( TESStesselator *tess );
// tessGetVertices() - Returns pointer to first coordinate of first vertex.
const TESSreal* tessGetVertices( TESStesselator *tess );
// tessGetVertexIndices() - Returns pointer to first vertex index.
// Vertex indices can be used to map the generated vertices to the original vertices.
// Every point added using tessAddContour() will get a new index starting at 0.
// New vertices generated at the intersections of segments are assigned value TESS_UNDEF.
const TESSindex* tessGetVertexIndices( TESStesselator *tess );
// tessGetElementCount() - Returns number of elements in the the tesselated output.
int tessGetElementCount( TESStesselator *tess );
// tessGetElements() - Returns pointer to the first element.
const TESSindex* tessGetElements( TESStesselator *tess );
#ifdef __cplusplus
}
#endif
#endif // TESSELATOR_H
|
