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  * coveandtiler.c++
37  *
38  */
39 
40 //#include "glimports.h"
41 //#include "myassert.h"
42 //#include "mystdio.h"
43 #include "coveandtiler.h"
44 //#include "gridvertex.h"
45 //#include "gridtrimvertex.h"
46 //#include "uarray.h"
47 #include "backend.h"
48 
49 
50 const int CoveAndTiler::MAXSTRIPSIZE = 1000;
51 
52 CoveAndTiler::CoveAndTiler( Backend& b )
53 	    : backend( b )
54 { }
55 
56 CoveAndTiler::~CoveAndTiler( void )
57 { }
58 
59 inline void
60 CoveAndTiler::output( GridVertex &gv )
61 {
62     backend.tmeshvert( &gv );
63 }
64 
65 inline void
66 CoveAndTiler::output( TrimVertex *tv )
67 {
68     backend.tmeshvert( tv );
69 }
70 
71 inline void
72 CoveAndTiler::output( GridTrimVertex& g )
73 {
74     backend.tmeshvert( &g );
75 }
76 
77 void
78 CoveAndTiler::coveAndTile( void )
79 {
80     long ustart = (top.ustart >= bot.ustart) ? top.ustart : bot.ustart;
81     long uend	= (top.uend <= bot.uend)     ? top.uend   : bot.uend;
82     if( ustart <= uend ) {
83 	tile( bot.vindex, ustart, uend );
84 	if( top.ustart >= bot.ustart )
85 	    coveUpperLeft();
86 	else
87 	    coveLowerLeft();
88 
89 	if( top.uend <= bot.uend )
90 	    coveUpperRight();
91 	else
92 	    coveLowerRight();
93     } else {
94 	TrimVertex blv, tlv, *bl, *tl;
95 	GridTrimVertex bllv, tllv;
96 	TrimVertex *lf = left.first();
97 	TrimVertex *ll = left.last();
98 	if( lf->param[0] >= ll->param[0] ) {
99 	    blv.param[0] = lf->param[0];
100 	    blv.param[1] = ll->param[1];
101 	    blv.nuid = 0; // XXX
102 	    assert( blv.param[1] == bot.vval );
103 	    bl = &blv;
104 	    tl = lf;
105 	    tllv.set( lf );
106 	    if( ll->param[0] > uarray.uarray[top.ustart-1] ) {
107 		bllv.set( ll );
108 		assert( ll->param[0] <= uarray.uarray[bot.ustart] );
109 	    } else {
110 		bllv.set( top.ustart-1, bot.vindex );
111 	    }
112 	    coveUpperLeftNoGrid( bl );
113 	} else {
114 	    tlv.param[0] = ll->param[0];
115 	    tlv.param[1] = lf->param[1];
116 	    tlv.nuid = 0; // XXX
117 	    assert( tlv.param[1] == top.vval );
118 	    tl = &tlv;
119 	    bl = ll;
120 	    bllv.set( ll );
121 	    if( lf->param[0] > uarray.uarray[bot.ustart-1] ) {
122 		assert( lf->param[0] <= uarray.uarray[bot.ustart] );
123 		tllv.set( lf );
124 	    } else {
125 		tllv.set( bot.ustart-1, top.vindex );
126 	    }
127 	    coveLowerLeftNoGrid( tl );
128 	}
129 
130 	TrimVertex brv, trv, *br, *tr;
131 	GridTrimVertex brrv, trrv;
132 	TrimVertex *rf = right.first();
133 	TrimVertex *rl = right.last();
134 
135 	if( rf->param[0] <= rl->param[0] ) {
136 	    brv.param[0] = rf->param[0];
137 	    brv.param[1] = rl->param[1];
138 	    brv.nuid = 0; // XXX
139 	    assert( brv.param[1] == bot.vval );
140 	    br = &brv;
141 	    tr = rf;
142 	    trrv.set( rf );
143 	    if( rl->param[0] < uarray.uarray[top.uend+1] ) {
144 		assert( rl->param[0] >= uarray.uarray[top.uend] );
145 		brrv.set( rl );
146 	    } else {
147 		brrv.set( top.uend+1, bot.vindex );
148 	    }
149 	    coveUpperRightNoGrid( br );
150 	} else {
151 	    trv.param[0] = rl->param[0];
152 	    trv.param[1] = rf->param[1];
153 	    trv.nuid = 0; // XXX
154 	    assert( trv.param[1] == top.vval );
155 	    tr = &trv;
156 	    br = rl;
157 	    brrv.set( rl );
158 	    if( rf->param[0] < uarray.uarray[bot.uend+1] ) {
159 		assert( rf->param[0] >= uarray.uarray[bot.uend] );
160 		trrv.set( rf );
161 	    } else {
162 		trrv.set( bot.uend+1, top.vindex );
163 	    }
164 	    coveLowerRightNoGrid( tr );
165 	}
166 
167 	backend.bgntmesh( "doit" );
168 	output(trrv);
169 	output(tllv);
170 	output( tr );
171 	output( tl );
172 	output( br );
173 	output( bl );
174 	output(brrv);
175 	output(bllv);
176 	backend.endtmesh();
177     }
178 }
179 
180 void
181 CoveAndTiler::tile( long vindex, long ustart, long uend )
182 {
183     long numsteps = uend - ustart;
184 
185     if( numsteps == 0 ) return;
186 
187     if( numsteps > MAXSTRIPSIZE ) {
188 	long umid = ustart + (uend - ustart) / 2;
189 	tile( vindex, ustart, umid );
190 	tile( vindex, umid, uend );
191     } else {
192 	backend.surfmesh( ustart, vindex-1, numsteps, 1 );
193     }
194 }
195 
196 void
197 CoveAndTiler::coveUpperRight( void )
198 {
199     GridVertex tgv( top.uend, top.vindex );
200     GridVertex gv( top.uend, bot.vindex );
201 
202     right.first();
203     backend.bgntmesh( "coveUpperRight" );
204     output( right.next() );
205     output( tgv );
206     backend.swaptmesh();
207     output( gv );
208 	coveUR();
209     backend.endtmesh();
210 }
211 
212 void
213 CoveAndTiler::coveUpperRightNoGrid( TrimVertex* br )
214 {
215     backend.bgntmesh( "coveUpperRight" );
216     output( right.first() );
217     output( right.next() );
218     backend.swaptmesh();
219     output( br );
220 	coveUR();
221     backend.endtmesh();
222 }
223 
224 void
225 CoveAndTiler::coveUR( )
226 {
227     GridVertex gv( top.uend, bot.vindex );
228     TrimVertex *vert = right.next();
229     if( vert == NULL ) return;
230 
231     assert( vert->param[0] >= uarray.uarray[gv.gparam[0]]  );
232 
233     if( gv.nextu() >= bot.uend ) {
234 	for( ; vert; vert = right.next() ) {
235 	    output( vert );
236 	    backend.swaptmesh();
237 	}
238     } else while( 1 ) {
239 	if( vert->param[0] < uarray.uarray[gv.gparam[0]]  ) {
240 	    output( vert );
241 	    backend.swaptmesh();
242 	    vert = right.next();
243 	    if( vert == NULL ) break;
244 	} else {
245 	    backend.swaptmesh();
246 	    output( gv );
247 	    if( gv.nextu() == bot.uend ) {
248 		for( ; vert; vert = right.next() ) {
249 		    output( vert );
250 		    backend.swaptmesh();
251 		}
252 		break;
253 	    }
254 	}
255     }
256 }
257 
258 void
259 CoveAndTiler::coveUpperLeft( void )
260 {
261     GridVertex tgv( top.ustart, top.vindex );
262     GridVertex gv( top.ustart, bot.vindex );
263 
264     left.first();
265     backend.bgntmesh( "coveUpperLeft" );
266     output( tgv );
267     output( left.next() );
268     output( gv );
269     backend.swaptmesh();
270 	coveUL();
271     backend.endtmesh();
272 }
273 
274 void
275 CoveAndTiler::coveUpperLeftNoGrid( TrimVertex* bl )
276 {
277     backend.bgntmesh( "coveUpperLeftNoGrid" );
278     output( left.first() );
279     output( left.next() );
280     output( bl );
281     backend.swaptmesh();
282 	coveUL();
283     backend.endtmesh();
284 }
285 
286 void
287 CoveAndTiler::coveUL()
288 {
289     GridVertex gv( top.ustart, bot.vindex );
290     TrimVertex *vert = left.next();
291     if( vert == NULL ) return;
292     assert( vert->param[0] <= uarray.uarray[gv.gparam[0]]  );
293 
294     if( gv.prevu() <= bot.ustart ) {
295 	for( ; vert; vert = left.next() ) {
296 	    backend.swaptmesh();
297 	    output( vert );
298 	}
299     } else while( 1 ) {
300 	if( vert->param[0] > uarray.uarray[gv.gparam[0]]  ) {
301 	    backend.swaptmesh();
302 	    output( vert );
303 	    vert = left.next();
304 	    if( vert == NULL ) break;
305 	} else {
306 	    output( gv );
307 	    backend.swaptmesh();
308 	    if( gv.prevu() == bot.ustart ) {
309 		for( ; vert; vert = left.next() ) {
310 		    backend.swaptmesh();
311 		    output( vert );
312 		}
313 		break;
314 	    }
315 	}
316     }
317 }
318 
319 void
320 CoveAndTiler::coveLowerLeft( void )
321 {
322     GridVertex bgv( bot.ustart, bot.vindex );
323     GridVertex gv( bot.ustart, top.vindex );
324 
325     left.last();
326     backend.bgntmesh( "coveLowerLeft" );
327     output( left.prev() );
328     output( bgv );
329     backend.swaptmesh();
330     output( gv );
331 	coveLL();
332     backend.endtmesh();
333 }
334 
335 void
336 CoveAndTiler::coveLowerLeftNoGrid( TrimVertex* tl )
337 {
338     backend.bgntmesh( "coveLowerLeft" );
339     output( left.last() );
340     output( left.prev() );
341     backend.swaptmesh();
342     output( tl );
343 	coveLL( );
344     backend.endtmesh();
345 }
346 
347 void
348 CoveAndTiler::coveLL()
349 {
350     GridVertex gv( bot.ustart, top.vindex );
351     TrimVertex *vert = left.prev();
352     if( vert == NULL ) return;
353     assert( vert->param[0] <= uarray.uarray[gv.gparam[0]]  );
354 
355     if( gv.prevu() <= top.ustart ) {
356 	for( ; vert; vert = left.prev() ) {
357 	    output( vert );
358 	    backend.swaptmesh();
359 	}
360     } else while( 1 ) {
361 	if( vert->param[0] > uarray.uarray[gv.gparam[0]] ){
362 	    output( vert );
363 	    backend.swaptmesh();
364 	    vert = left.prev();
365 	    if( vert == NULL ) break;
366 	} else {
367 	    backend.swaptmesh();
368 	    output( gv );
369 	    if( gv.prevu() == top.ustart ) {
370 		for( ; vert; vert = left.prev() ) {
371 		    output( vert );
372 		    backend.swaptmesh();
373 		}
374 		break;
375 	    }
376 	}
377     }
378 }
379 
380 void
381 CoveAndTiler::coveLowerRight( void )
382 {
383     GridVertex bgv( bot.uend, bot.vindex );
384     GridVertex gv( bot.uend, top.vindex );
385 
386     right.last();
387     backend.bgntmesh( "coveLowerRight" );
388     output( bgv );
389     output( right.prev() );
390     output( gv );
391     backend.swaptmesh();
392 	coveLR();
393     backend.endtmesh( );
394 }
395 
396 void
397 CoveAndTiler::coveLowerRightNoGrid( TrimVertex* tr )
398 {
399     backend.bgntmesh( "coveLowerRIght" );
400     output( right.last() );
401     output( right.prev() );
402     output( tr );
403     backend.swaptmesh();
404 	coveLR();
405     backend.endtmesh();
406 }
407 
408 void
409 CoveAndTiler::coveLR( )
410 {
411     GridVertex gv( bot.uend, top.vindex );
412     TrimVertex *vert = right.prev();
413     if( vert == NULL ) return;
414     assert( vert->param[0] >= uarray.uarray[gv.gparam[0]]  );
415 
416     if( gv.nextu() >= top.uend ) {
417 	for( ; vert; vert = right.prev() ) {
418 	    backend.swaptmesh();
419 	    output( vert );
420 	}
421     } else while( 1 ) {
422 	if( vert->param[0] < uarray.uarray[gv.gparam[0]]  ) {
423 	    backend.swaptmesh();
424 	    output( vert );
425 	    vert = right.prev();
426 	    if( vert == NULL ) break;
427 	} else {
428 	    output( gv );
429 	    backend.swaptmesh();
430 	    if( gv.nextu() == top.uend ) {
431 		for( ; vert; vert = right.prev() ) {
432 		    backend.swaptmesh();
433 		    output( vert );
434 		}
435 		break;
436 	    }
437 	}
438     }
439 }
440 
441