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
50const int CoveAndTiler::MAXSTRIPSIZE = 1000;
51
52CoveAndTiler::CoveAndTiler( Backend& b )
53	    : backend( b )
54{ }
55
56CoveAndTiler::~CoveAndTiler( void )
57{ }
58
59inline void
60CoveAndTiler::output( GridVertex &gv )
61{
62    backend.tmeshvert( &gv );
63}
64
65inline void
66CoveAndTiler::output( TrimVertex *tv )
67{
68    backend.tmeshvert( tv );
69}
70
71inline void
72CoveAndTiler::output( GridTrimVertex& g )
73{
74    backend.tmeshvert( &g );
75}
76
77void
78CoveAndTiler::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
180void
181CoveAndTiler::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
196void
197CoveAndTiler::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
212void
213CoveAndTiler::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
224void
225CoveAndTiler::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
258void
259CoveAndTiler::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
274void
275CoveAndTiler::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
286void
287CoveAndTiler::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
319void
320CoveAndTiler::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
335void
336CoveAndTiler::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
347void
348CoveAndTiler::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
380void
381CoveAndTiler::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
396void
397CoveAndTiler::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
408void
409CoveAndTiler::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