ReactOS 0.4.15-dev-7889-g76290a6
mesher.cc
Go to the documentation of this file.
1/*
2** License Applicability. Except to the extent portions of this file are
3** made subject to an alternative license as permitted in the SGI Free
4** Software License B, Version 1.1 (the "License"), the contents of this
5** file are subject only to the provisions of the License. You may not use
6** this file except in compliance with the License. You may obtain a copy
7** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
8** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
9**
10** http://oss.sgi.com/projects/FreeB
11**
12** Note that, as provided in the License, the Software is distributed on an
13** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
14** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
15** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
16** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
17**
18** Original Code. The Original Code is: OpenGL Sample Implementation,
19** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
20** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
21** Copyright in any portions created by third parties is as indicated
22** elsewhere herein. All Rights Reserved.
23**
24** Additional Notice Provisions: The application programming interfaces
25** established by SGI in conjunction with the Original Code are The
26** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
27** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
28** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
29** Window System(R) (Version 1.3), released October 19, 1998. This software
30** was created using the OpenGL(R) version 1.2.1 Sample Implementation
31** published by SGI, but has not been independently verified as being
32** compliant with the OpenGL(R) version 1.2.1 Specification.
33*/
34
35/*
36 * mesher.c++
37 *
38 */
39
40//#include "glimports.h"
41//#include "myassert.h"
42//#include "mystdio.h"
43//#include "gridvertex.h"
44//#include "gridtrimvertex.h"
45//#include "jarcloc.h"
46//#include "gridline.h"
47//#include "trimline.h"
48//#include "uarray.h"
49#include "backend.h"
50#include "mesher.h"
51
52
53const float Mesher::ZERO = 0.0;
54
56 : backend( b ),
57 p( sizeof( GridTrimVertex ), 100, "GridTrimVertexPool" )
58{
59 stacksize = 0;
60 vdata = 0;
61 last[0] = 0;
62 last[1] = 0;
63 itop = 0;
64 lastedge = 0; //needed to prevent purify UMR
65}
66
68{
69 if( vdata ) delete[] vdata;
70}
71
72void
73Mesher::init( unsigned int npts )
74{
75 p.clear();
76 if( stacksize < npts ) {
77 stacksize = 2 * npts;
78 if( vdata ) delete[] vdata;
80 }
81}
82
83inline void
85{
86 assert( itop+1 != (int)stacksize );
87 vdata[++itop] = gt;
88}
89
90inline void
92{
93}
94
95inline void
97{
98 backend.bgntmesh( "addedge" );
99}
100
101inline void
103{
105}
106
107inline void
109{
111}
112
113inline void
115{
116 itop = -1;
117 last[0] = 0;
118}
119
120void
122{
123 for( push(gtlower);
124 nextlower( gtlower=new(p) GridTrimVertex );
125 push(gtlower) )
126 addLower();
127 addLast();
128}
129
130void
132{
133 for( push(gtupper);
134 nextupper( gtupper=new(p) GridTrimVertex );
135 push(gtupper) )
136 addUpper();
137 addLast();
138}
139
140void
142{
143 GridTrimVertex *gtlower, *gtupper;
144
145 Hull::init( );
146 nextupper( gtupper = new(p) GridTrimVertex );
147 nextlower( gtlower = new(p) GridTrimVertex );
148
149 clearStack();
150 openMesh();
151 push(gtupper);
152
153 nextupper( gtupper = new(p) GridTrimVertex );
154 nextlower( gtlower );
155
156 assert( gtupper->t && gtlower->t );
157
158 if( gtupper->t->param[0] < gtlower->t->param[0] ) {
159 push(gtupper);
160 lastedge = 1;
161 if( nextupper( gtupper=new(p) GridTrimVertex ) == 0 ) {
162 finishLower(gtlower);
163 return;
164 }
165 } else if( gtupper->t->param[0] > gtlower->t->param[0] ) {
166 push(gtlower);
167 lastedge = 0;
168 if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
169 finishUpper(gtupper);
170 return;
171 }
172 } else {
173 if( lastedge == 0 ) {
174 push(gtupper);
175 lastedge = 1;
176 if( nextupper(gtupper=new(p) GridTrimVertex) == 0 ) {
177 finishLower(gtlower);
178 return;
179 }
180 } else {
181 push(gtlower);
182 lastedge = 0;
183 if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
184 finishUpper(gtupper);
185 return;
186 }
187 }
188 }
189
190 while ( 1 ) {
191 if( gtupper->t->param[0] < gtlower->t->param[0] ) {
192 push(gtupper);
193 addUpper();
194 if( nextupper( gtupper=new(p) GridTrimVertex ) == 0 ) {
195 finishLower(gtlower);
196 return;
197 }
198 } else if( gtupper->t->param[0] > gtlower->t->param[0] ) {
199 push(gtlower);
200 addLower();
201 if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
202 finishUpper(gtupper);
203 return;
204 }
205 } else {
206 if( lastedge == 0 ) {
207 push(gtupper);
208 addUpper();
209 if( nextupper( gtupper=new(p) GridTrimVertex ) == 0 ) {
210 finishLower(gtlower);
211 return;
212 }
213 } else {
214 push(gtlower);
215 addLower();
216 if( nextlower( gtlower=new(p) GridTrimVertex ) == 0 ) {
217 finishUpper(gtupper);
218 return;
219 }
220 }
221 }
222 }
223}
224
225inline int
226Mesher::isCcw( int ilast )
227{
228 REAL area = det3( vdata[ilast]->t, vdata[itop-1]->t, vdata[itop-2]->t );
229 return (area < ZERO) ? 0 : 1;
230}
231
232inline int
233Mesher::isCw( int ilast )
234{
235 REAL area = det3( vdata[ilast]->t, vdata[itop-1]->t, vdata[itop-2]->t );
236 return (area > -ZERO) ? 0 : 1;
237}
238
239inline int
240Mesher::equal( int x, int y )
241{
242 return( last[0] == vdata[x] && last[1] == vdata[y] );
243}
244
245inline void
246Mesher::copy( int x, int y )
247{
248 last[0] = vdata[x]; last[1] = vdata[y];
249}
250
251inline void
252Mesher::move( int x, int y )
253{
254 vdata[x] = vdata[y];
255}
256
257inline void
259{
261}
262
263/*---------------------------------------------------------------------------
264 * addedge - addedge an edge to the triangulation
265 *
266 * This code has been re-written to generate large triangle meshes
267 * from a monotone polygon. Although smaller triangle meshes
268 * could be generated faster and with less code, larger meshes
269 * actually give better SYSTEM performance. This is because
270 * vertices are processed in the backend slower than they are
271 * generated by this code and any decrease in the number of vertices
272 * results in a decrease in the time spent in the backend.
273 *---------------------------------------------------------------------------
274 */
275
276void
278{
279 int ilast = itop;
280
281 if( lastedge == 0 ) {
282 if( equal( 0, 1 ) ) {
283 output( ilast );
284 swapMesh();
285 for( int i = 2; i < ilast; i++ ) {
286 swapMesh();
287 output( i );
288 }
289 copy( ilast, ilast-1 );
290 } else if( equal( ilast-2, ilast-1) ) {
291 swapMesh();
292 output( ilast );
293 for( int i = ilast-3; i >= 0; i-- ) {
294 output( i );
295 swapMesh();
296 }
297 copy( 0, ilast );
298 } else {
299 closeMesh(); openMesh();
300 output( ilast );
301 output( 0 );
302 for( int i = 1; i < ilast; i++ ) {
303 swapMesh();
304 output( i );
305 }
306 copy( ilast, ilast-1 );
307 }
308 } else {
309 if( equal( 1, 0) ) {
310 swapMesh();
311 output( ilast );
312 for( int i = 2; i < ilast; i++ ) {
313 output( i );
314 swapMesh();
315 }
316 copy( ilast-1, ilast );
317 } else if( equal( ilast-1, ilast-2) ) {
318 output( ilast );
319 swapMesh();
320 for( int i = ilast-3; i >= 0; i-- ) {
321 swapMesh();
322 output( i );
323 }
324 copy( ilast, 0 );
325 } else {
326 closeMesh(); openMesh();
327 output( 0 );
328 output( ilast );
329 for( int i = 1; i < ilast; i++ ) {
330 output( i );
331 swapMesh();
332 }
333 copy( ilast-1, ilast );
334 }
335 }
336 closeMesh();
337 //for( long k=0; k<=ilast; k++ ) pop( k );
338}
339
340void
342{
343 int ilast = itop;
344
345 if( lastedge == 0 ) {
346 if( equal( 0, 1 ) ) {
347 output( ilast );
348 swapMesh();
349 for( int i = 2; i < ilast; i++ ) {
350 swapMesh();
351 output( i );
352 }
353 copy( ilast, ilast-1 );
354 } else if( equal( ilast-2, ilast-1) ) {
355 swapMesh();
356 output( ilast );
357 for( int i = ilast-3; i >= 0; i-- ) {
358 output( i );
359 swapMesh();
360 }
361 copy( 0, ilast );
362 } else {
363 closeMesh(); openMesh();
364 output( ilast );
365 output( 0 );
366 for( int i = 1; i < ilast; i++ ) {
367 swapMesh();
368 output( i );
369 }
370 copy( ilast, ilast-1 );
371 }
372 lastedge = 1;
373 //for( long k=0; k<ilast-1; k++ ) pop( k );
374 move( 0, ilast-1 );
375 move( 1, ilast );
376 itop = 1;
377 } else {
378 if( ! isCcw( ilast ) ) return;
379 do {
380 itop--;
381 } while( (itop > 1) && isCcw( ilast ) );
382
383 if( equal( ilast-1, ilast-2 ) ) {
384 output( ilast );
385 swapMesh();
386 for( int i=ilast-3; i>=itop-1; i-- ) {
387 swapMesh();
388 output( i );
389 }
390 copy( ilast, itop-1 );
391 } else if( equal( itop, itop-1 ) ) {
392 swapMesh();
393 output( ilast );
394 for( int i = itop+1; i < ilast; i++ ) {
395 output( i );
396 swapMesh();
397 }
398 copy( ilast-1, ilast );
399 } else {
400 closeMesh(); openMesh();
401 output( ilast );
402 output( ilast-1 );
403 for( int i=ilast-2; i>=itop-1; i-- ) {
404 swapMesh();
405 output( i );
406 }
407 copy( ilast, itop-1 );
408 }
409 //for( int k=itop; k<ilast; k++ ) pop( k );
410 move( itop, ilast );
411 }
412}
413
414void
416{
417 int ilast = itop;
418
419 if( lastedge == 1 ) {
420 if( equal( 1, 0) ) {
421 swapMesh();
422 output( ilast );
423 for( int i = 2; i < ilast; i++ ) {
424 output( i );
425 swapMesh();
426 }
427 copy( ilast-1, ilast );
428 } else if( equal( ilast-1, ilast-2) ) {
429 output( ilast );
430 swapMesh();
431 for( int i = ilast-3; i >= 0; i-- ) {
432 swapMesh();
433 output( i );
434 }
435 copy( ilast, 0 );
436 } else {
437 closeMesh(); openMesh();
438 output( 0 );
439 output( ilast );
440 for( int i = 1; i < ilast; i++ ) {
441 output( i );
442 swapMesh();
443 }
444 copy( ilast-1, ilast );
445 }
446
447 lastedge = 0;
448 //for( long k=0; k<ilast-1; k++ ) pop( k );
449 move( 0, ilast-1 );
450 move( 1, ilast );
451 itop = 1;
452 } else {
453 if( ! isCw( ilast ) ) return;
454 do {
455 itop--;
456 } while( (itop > 1) && isCw( ilast ) );
457
458 if( equal( ilast-2, ilast-1) ) {
459 swapMesh();
460 output( ilast );
461 for( int i=ilast-3; i>=itop-1; i--) {
462 output( i );
463 swapMesh( );
464 }
465 copy( itop-1, ilast );
466 } else if( equal( itop-1, itop) ) {
467 output( ilast );
468 swapMesh();
469 for( int i=itop+1; i<ilast; i++ ) {
470 swapMesh( );
471 output( i );
472 }
473 copy( ilast, ilast-1 );
474 } else {
475 closeMesh(); openMesh();
476 output( ilast-1 );
477 output( ilast );
478 for( int i=ilast-2; i>=itop-1; i-- ) {
479 output( i );
480 swapMesh( );
481 }
482 copy( itop-1, ilast );
483 }
484 //for( int k=itop; k<ilast; k++ ) pop( k );
485 move( itop, ilast );
486 }
487}
488
489
void swaptmesh(void)
Definition: backend.cc:442
void tmeshvert(GridTrimVertex *)
Definition: backend.cc:269
void endtmesh(void)
Definition: backend.cc:460
void bgntmesh(const char *)
Definition: backend.cc:246
TrimVertex * t
void init(void)
Definition: hull.cc:63
GridTrimVertex * nextupper(GridTrimVertex *)
Definition: hull.cc:116
GridTrimVertex * nextlower(GridTrimVertex *)
Definition: hull.cc:142
void addLast(void)
Definition: mesher.cc:277
int isCw(int)
Definition: mesher.cc:233
void copy(int, int)
Definition: mesher.cc:246
void addLower(void)
Definition: mesher.cc:415
GridTrimVertex ** vdata
Definition: mesher.h:60
int isCcw(int)
Definition: mesher.cc:226
void output(int)
Definition: mesher.cc:258
void finishUpper(GridTrimVertex *)
Definition: mesher.cc:131
GridTrimVertex * last[2]
Definition: mesher.h:61
void swapMesh(void)
Definition: mesher.cc:108
void push(GridTrimVertex *)
Definition: mesher.cc:84
void openMesh(void)
Definition: mesher.cc:96
void clearStack(void)
Definition: mesher.cc:114
static const float ZERO
Definition: mesher.h:55
int lastedge
Definition: mesher.h:63
void closeMesh(void)
Definition: mesher.cc:102
int itop
Definition: mesher.h:62
void mesh(void)
Definition: mesher.cc:141
Backend & backend
Definition: mesher.h:56
unsigned int stacksize
Definition: mesher.h:59
void pop(long)
Definition: mesher.cc:91
void addUpper(void)
Definition: mesher.cc:341
void move(int, int)
Definition: mesher.cc:252
~Mesher(void)
Definition: mesher.cc:67
Mesher(Backend &)
Definition: mesher.cc:55
int equal(int, int)
Definition: mesher.cc:240
void finishLower(GridTrimVertex *)
Definition: mesher.cc:121
REAL param[2]
Definition: trimvertex.h:45
float REAL
Definition: types.h:41
#define assert(x)
Definition: debug.h:53
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
GLdouble GLdouble t
Definition: gl.h:2047
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
GLfloat GLfloat p
Definition: glext.h:8902
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
static Real area(Real A[2], Real B[2], Real C[2])
Definition: polyDBG.cc:50
#define equal(x, y)
Definition: reader.cc:56
REAL det3(TrimVertex *a, TrimVertex *b, TrimVertex *c)
Definition: trimvertex.h:56
ActualNumberDriverObjects * sizeof(PDRIVER_OBJECT)) PDRIVER_OBJECT *DriverObjectList