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 
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 
67 Mesher::~Mesher( void )
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;
79 	vdata = new GridTrimVertex_p[stacksize];
80     }
81 }
82 
83 inline void
84 Mesher::push( GridTrimVertex *gt )
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
96 Mesher::openMesh()
97 {
98     backend.bgntmesh( "addedge" );
99 }
100 
101 inline void
102 Mesher::closeMesh()
103 {
104     backend.endtmesh();
105 }
106 
107 inline void
108 Mesher::swapMesh()
109 {
110     backend.swaptmesh();
111 }
112 
113 inline void
114 Mesher::clearStack()
115 {
116     itop = -1;
117     last[0] = 0;
118 }
119 
120 void
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
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
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
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
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
277 Mesher::addLast( )
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
341 Mesher::addUpper( )
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
415 Mesher::addLower()
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 
490