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
Mesher(Backend & b)55 Mesher::Mesher( Backend& b )
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
~Mesher(void)67 Mesher::~Mesher( void )
68 {
69 if( vdata ) delete[] vdata;
70 }
71
72 void
init(unsigned int npts)73 Mesher::init( unsigned int npts )
74 {
75 p.clear();
76 if( stacksize < npts ) {
77 stacksize = 2 * npts;
78 if( vdata ) delete[] vdata;
79 vdata = new GridTrimVertex_p[stacksize];
80 }
81 }
82
83 inline void
push(GridTrimVertex * gt)84 Mesher::push( GridTrimVertex *gt )
85 {
86 assert( itop+1 != (int)stacksize );
87 vdata[++itop] = gt;
88 }
89
90 inline void
pop(long)91 Mesher::pop( long )
92 {
93 }
94
95 inline void
openMesh()96 Mesher::openMesh()
97 {
98 backend.bgntmesh( "addedge" );
99 }
100
101 inline void
closeMesh()102 Mesher::closeMesh()
103 {
104 backend.endtmesh();
105 }
106
107 inline void
swapMesh()108 Mesher::swapMesh()
109 {
110 backend.swaptmesh();
111 }
112
113 inline void
clearStack()114 Mesher::clearStack()
115 {
116 itop = -1;
117 last[0] = 0;
118 }
119
120 void
finishLower(GridTrimVertex * gtlower)121 Mesher::finishLower( GridTrimVertex *gtlower )
122 {
123 for( push(gtlower);
124 nextlower( gtlower=new(p) GridTrimVertex );
125 push(gtlower) )
126 addLower();
127 addLast();
128 }
129
130 void
finishUpper(GridTrimVertex * gtupper)131 Mesher::finishUpper( GridTrimVertex *gtupper )
132 {
133 for( push(gtupper);
134 nextupper( gtupper=new(p) GridTrimVertex );
135 push(gtupper) )
136 addUpper();
137 addLast();
138 }
139
140 void
mesh(void)141 Mesher::mesh( 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
isCcw(int ilast)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
isCw(int ilast)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
equal(int x,int y)240 Mesher::equal( int x, int y )
241 {
242 return( last[0] == vdata[x] && last[1] == vdata[y] );
243 }
244
245 inline void
copy(int x,int y)246 Mesher::copy( int x, int y )
247 {
248 last[0] = vdata[x]; last[1] = vdata[y];
249 }
250
251 inline void
move(int x,int y)252 Mesher::move( int x, int y )
253 {
254 vdata[x] = vdata[y];
255 }
256
257 inline void
output(int x)258 Mesher::output( int x )
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
addLast()277 Mesher::addLast( )
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
340 void
addUpper()341 Mesher::addUpper( )
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
414 void
addLower()415 Mesher::addLower()
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
490