ReactOS  0.4.14-dev-815-ge410a12
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 
53 const 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 
72 void
73 Mesher::init( unsigned int npts )
74 {
75  p.clear();
76  if( stacksize < npts ) {
77  stacksize = 2 * npts;
78  if( vdata ) delete[] vdata;
80  }
81 }
82 
83 inline void
85 {
86  assert( itop+1 != (int)stacksize );
87  vdata[++itop] = gt;
88 }
89 
90 inline void
91 Mesher::pop( long )
92 {
93 }
94 
95 inline void
97 {
98  backend.bgntmesh( "addedge" );
99 }
100 
101 inline void
103 {
104  backend.endtmesh();
105 }
106 
107 inline void
109 {
110  backend.swaptmesh();
111 }
112 
113 inline void
115 {
116  itop = -1;
117  last[0] = 0;
118 }
119 
120 void
122 {
123  for( push(gtlower);
124  nextlower( gtlower=new(p) GridTrimVertex );
125  push(gtlower) )
126  addLower();
127  addLast();
128 }
129 
130 void
132 {
133  for( push(gtupper);
134  nextupper( gtupper=new(p) GridTrimVertex );
135  push(gtupper) )
136  addUpper();
137  addLast();
138 }
139 
140 void
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 
225 inline int
226 Mesher::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 
232 inline int
233 Mesher::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 
239 inline int
240 Mesher::equal( int x, int y )
241 {
242  return( last[0] == vdata[x] && last[1] == vdata[y] );
243 }
244 
245 inline void
246 Mesher::copy( int x, int y )
247 {
248  last[0] = vdata[x]; last[1] = vdata[y];
249 }
250 
251 inline void
252 Mesher::move( int x, int y )
253 {
254  vdata[x] = vdata[y];
255 }
256 
257 inline void
259 {
260  backend.tmeshvert( vdata[x] );
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 
276 void
278 {
279  register int ilast = itop;
280 
281  if( lastedge == 0 ) {
282  if( equal( 0, 1 ) ) {
283  output( ilast );
284  swapMesh();
285  for( register 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( register 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( register 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( register 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( register 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( register int i = 1; i < ilast; i++ ) {
330  output( i );
331  swapMesh();
332  }
333  copy( ilast-1, ilast );
334  }
335  }
336  closeMesh();
337  //for( register long k=0; k<=ilast; k++ ) pop( k );
338 }
339 
340 void
342 {
343  register int ilast = itop;
344 
345  if( lastedge == 0 ) {
346  if( equal( 0, 1 ) ) {
347  output( ilast );
348  swapMesh();
349  for( register 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( register 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( register int i = 1; i < ilast; i++ ) {
367  swapMesh();
368  output( i );
369  }
370  copy( ilast, ilast-1 );
371  }
372  lastedge = 1;
373  //for( register 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( register 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( register 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( register int i=ilast-2; i>=itop-1; i-- ) {
404  swapMesh();
405  output( i );
406  }
407  copy( ilast, itop-1 );
408  }
409  //for( register int k=itop; k<ilast; k++ ) pop( k );
410  move( itop, ilast );
411  }
412 }
413 
414 void
416 {
417  register int ilast = itop;
418 
419  if( lastedge == 1 ) {
420  if( equal( 1, 0) ) {
421  swapMesh();
422  output( ilast );
423  for( register 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( register 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( register int i = 1; i < ilast; i++ ) {
441  output( i );
442  swapMesh();
443  }
444  copy( ilast-1, ilast );
445  }
446 
447  lastedge = 0;
448  //for( register 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( register 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( register 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( register int i=ilast-2; i>=itop-1; i-- ) {
479  output( i );
480  swapMesh( );
481  }
482  copy( itop-1, ilast );
483  }
484  //for( register int k=itop; k<ilast; k++ ) pop( k );
485  move( itop, ilast );
486  }
487 }
488 
489 
int lastedge
Definition: mesher.h:63
void pop(long)
Definition: mesher.cc:91
Backend & backend
Definition: mesher.h:56
void bgntmesh(const char *)
Definition: backend.cc:246
static const float ZERO
Definition: mesher.h:55
ActualNumberDriverObjects * sizeof(PDRIVER_OBJECT)) PDRIVER_OBJECT *DriverObjectList
TrimVertex * t
GridTrimVertex * nextupper(GridTrimVertex *)
Definition: hull.cc:116
void endtmesh(void)
Definition: backend.cc:460
GridTrimVertex ** vdata
Definition: mesher.h:60
GLdouble GLdouble t
Definition: gl.h:2047
#define assert(x)
Definition: debug.h:53
void mesh(void)
Definition: mesher.cc:141
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
REAL det3(TrimVertex *a, TrimVertex *b, TrimVertex *c)
Definition: trimvertex.h:56
void addLast(void)
Definition: mesher.cc:277
unsigned int stacksize
Definition: mesher.h:59
void tmeshvert(GridTrimVertex *)
Definition: backend.cc:269
int isCcw(int)
Definition: mesher.cc:226
GridTrimVertex * last[2]
Definition: mesher.h:61
void swaptmesh(void)
Definition: backend.cc:442
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
void closeMesh(void)
Definition: mesher.cc:102
GridTrimVertex * nextlower(GridTrimVertex *)
Definition: hull.cc:142
void copy(int, int)
Definition: mesher.cc:246
int isCw(int)
Definition: mesher.cc:233
void finishLower(GridTrimVertex *)
Definition: mesher.cc:121
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
void finishUpper(GridTrimVertex *)
Definition: mesher.cc:131
Mesher(Backend &)
Definition: mesher.cc:55
void clearStack(void)
Definition: mesher.cc:114
void init(void)
Definition: hull.cc:63
void move(int, int)
Definition: mesher.cc:252
int equal(int, int)
Definition: mesher.cc:240
void addLower(void)
Definition: mesher.cc:415
void push(GridTrimVertex *)
Definition: mesher.cc:84
~Mesher(void)
Definition: mesher.cc:67
static Real area(Real A[2], Real B[2], Real C[2])
Definition: polyDBG.cc:50
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
REAL param[2]
Definition: trimvertex.h:45
void swapMesh(void)
Definition: mesher.cc:108
GLfloat GLfloat p
Definition: glext.h:8902
float REAL
Definition: types.h:41
void addUpper(void)
Definition: mesher.cc:341
void output(int)
Definition: mesher.cc:258
void openMesh(void)
Definition: mesher.cc:96
int itop
Definition: mesher.h:62