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:
10 ** http://oss.sgi.com/projects/FreeB
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.
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.
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.
40 #include "glimports.h"
44 #include "subdivider.h"
45 #include "arcsorter.h"
49 /* local preprocessor definitions */
52 /*----------------------------------------------------------------------------
53 * Subdivider::split - split trim regions in source bin by line (param == value).
54 *----------------------------------------------------------------------------
58 Subdivider::split( Bin
& bin
, Bin
& left
, Bin
& right
, int param
, REAL value
)
60 Bin intersections
, unknown
;
62 partition( bin
, left
, intersections
, right
, unknown
, param
, value
);
64 int count
= intersections
.numarcs();
68 intersections
.show( "intersections" );
69 right
.show( "right" );
71 ::mylongjmp( jumpbuffer
, 29 );
74 Arc_ptr arclist
[MAXARCS
], *list
;
75 if( count
>= MAXARCS
) {
76 list
= new Arc_ptr
[count
];
81 Arc_ptr jarc
, *last
, *lptr
;
82 for( last
= list
; (jarc
=intersections
.removearc()) != NULL
; last
++ )
85 if( param
== 0 ) { /* sort into increasing t order */
86 ArcSdirSorter
sorter(*this);
87 sorter
.qsort( list
, count
);
89 //::qsort ((void *)list, count, sizeof(Arc_ptr), (cmpfunc)compare_s);
90 for( lptr
=list
; lptr
<last
; lptr
+=2 )
91 check_s ( lptr
[0], lptr
[1] );
92 for( lptr
=list
; lptr
<last
; lptr
+=2 )
93 join_s ( left
, right
, lptr
[0], lptr
[1] );
94 for( lptr
=list
; lptr
!= last
; lptr
++ ) {
95 if( ((*lptr
)->head()[0] <= value
) && ((*lptr
)->tail()[0] <= value
) )
98 right
.addarc( *lptr
);
100 } else { /* sort into decreasing s order */
101 ArcTdirSorter
sorter(*this);
102 sorter
.qsort( list
, count
);
103 //::qsort ((void *)list, count, sizeof(Arc_ptr), (cmpfunc)compare_t);
104 for( lptr
=list
; lptr
<last
; lptr
+=2 )
105 check_t ( lptr
[0], lptr
[1] );
106 for( lptr
=list
; lptr
<last
; lptr
+=2 )
107 join_t ( left
, right
, lptr
[0], lptr
[1] );
108 for( lptr
=list
; lptr
!= last
; lptr
++ ) {
109 if( ((*lptr
)->head()[1] <= value
) && ((*lptr
)->tail()[1] <= value
) )
110 left
.addarc( *lptr
);
112 right
.addarc( *lptr
);
116 if( list
!= arclist
) delete[] list
;
122 Subdivider::check_s( Arc_ptr jarc1
, Arc_ptr jarc2
)
124 assert( jarc1
->check( ) != 0 );
125 assert( jarc2
->check( ) != 0 );
126 assert( jarc1
->next
->check( ) != 0 );
127 assert( jarc2
->next
->check( ) != 0 );
128 assert( jarc1
!= jarc2
);
130 /* XXX - if these assertions fail, it is due to user error or
132 if( ! ( jarc1
->tail()[0] < (jarc1
)->head()[0] ) ) {
134 _glu_dprintf( "s difference %f\n", (jarc1
)->tail()[0] - (jarc1
)->head()[0] );
136 ::mylongjmp( jumpbuffer
, 28 );
139 if( ! ( jarc2
->tail()[0] > (jarc2
)->head()[0] ) ) {
141 _glu_dprintf( "s difference %f\n", (jarc2
)->tail()[0] - (jarc2
)->head()[0] );
143 ::mylongjmp( jumpbuffer
, 28 );
148 Subdivider::link( Arc_ptr jarc1
, Arc_ptr jarc2
, Arc_ptr up
, Arc_ptr down
)
150 up
->nuid
= down
->nuid
= 0; // XXX
154 up
->prev
= jarc1
->prev
;
155 down
->prev
= jarc2
->prev
;
157 down
->next
->prev
= down
;
159 down
->prev
->next
= down
;
164 Subdivider::simple_link( Arc_ptr jarc1
, Arc_ptr jarc2
)
166 Arc_ptr tmp
= jarc2
->prev
;
167 jarc2
->prev
= jarc1
->prev
;
169 jarc2
->prev
->next
= jarc2
;
170 jarc1
->prev
->next
= jarc1
;
174 /*----------------------------------------------------------------------------
175 * join - add a pair of oppositely directed jordan arcs between two arcs
176 *----------------------------------------------------------------------------
180 Subdivider::join_s( Bin
& left
, Bin
& right
, Arc_ptr jarc1
, Arc_ptr jarc2
)
182 assert( jarc1
->check( ) != 0);
183 assert( jarc2
->check( ) != 0);
184 assert( jarc1
!= jarc2
);
186 if( ! jarc1
->getitail() )
189 if( ! jarc2
->getitail() )
192 REAL s
= jarc1
->tail()[0];
193 REAL t1
= jarc1
->tail()[1];
194 REAL t2
= jarc2
->tail()[1];
197 simple_link( jarc1
, jarc2
);
199 Arc_ptr newright
= new(arcpool
) Arc( arc_right
, 0 );
200 Arc_ptr newleft
= new(arcpool
) Arc( arc_left
, 0 );
202 if( isBezierArcType() ) {
203 arctessellator
.bezier( newright
, s
, s
, t1
, t2
);
204 arctessellator
.bezier( newleft
, s
, s
, t2
, t1
);
206 arctessellator
.pwl_right( newright
, s
, t1
, t2
, stepsizes
[0] );
207 arctessellator
.pwl_left( newleft
, s
, t2
, t1
, stepsizes
[2] );
209 link( jarc1
, jarc2
, newright
, newleft
);
210 left
.addarc( newright
);
211 right
.addarc( newleft
);
214 assert( jarc1
->check( ) != 0 );
215 assert( jarc2
->check( ) != 0 );
216 assert( jarc1
->next
->check( ) != 0);
217 assert( jarc2
->next
->check( ) != 0);
221 Subdivider::check_t( Arc_ptr jarc1
, Arc_ptr jarc2
)
223 assert( jarc1
->check( ) != 0 );
224 assert( jarc2
->check( ) != 0 );
225 assert( jarc1
->next
->check( ) != 0 );
226 assert( jarc2
->next
->check( ) != 0 );
227 assert( jarc1
!= jarc2
);
229 /* XXX - if these assertions fail, it is due to user error or
231 if( ! ( jarc1
->tail()[1] < (jarc1
)->head()[1] ) ) {
233 _glu_dprintf( "t difference %f\n", jarc1
->tail()[1] - (jarc1
)->head()[1] );
235 ::mylongjmp( jumpbuffer
, 28 );
238 if( ! ( jarc2
->tail()[1] > (jarc2
)->head()[1] ) ) {
240 _glu_dprintf( "t difference %f\n", jarc2
->tail()[1] - (jarc2
)->head()[1] );
242 ::mylongjmp( jumpbuffer
, 28 );
246 /*----------------------------------------------------------------------------
247 * join_t - add a pair of oppositely directed jordan arcs between two arcs
248 *----------------------------------------------------------------------------
252 Subdivider::join_t( Bin
& bottom
, Bin
& top
, Arc_ptr jarc1
, Arc_ptr jarc2
)
254 assert( jarc1
->check( ) != 0 );
255 assert( jarc2
->check( ) != 0 );
256 assert( jarc1
->next
->check( ) != 0 );
257 assert( jarc2
->next
->check( ) != 0 );
258 assert( jarc1
!= jarc2
);
260 if( ! jarc1
->getitail() )
263 if( ! jarc2
->getitail() )
266 REAL s1
= jarc1
->tail()[0];
267 REAL s2
= jarc2
->tail()[0];
268 REAL t
= jarc1
->tail()[1];
271 simple_link( jarc1
, jarc2
);
273 Arc_ptr newtop
= new(arcpool
) Arc( arc_top
, 0 );
274 Arc_ptr newbot
= new(arcpool
) Arc( arc_bottom
, 0 );
276 if( isBezierArcType() ) {
277 arctessellator
.bezier( newtop
, s1
, s2
, t
, t
);
278 arctessellator
.bezier( newbot
, s2
, s1
, t
, t
);
280 arctessellator
.pwl_top( newtop
, t
, s1
, s2
, stepsizes
[1] );
281 arctessellator
.pwl_bottom( newbot
, t
, s2
, s1
, stepsizes
[3] );
283 link( jarc1
, jarc2
, newtop
, newbot
);
284 bottom
.addarc( newtop
);
285 top
.addarc( newbot
);
288 assert( jarc1
->check( ) != 0 );
289 assert( jarc2
->check( ) != 0 );
290 assert( jarc1
->next
->check( ) != 0 );
291 assert( jarc2
->next
->check( ) != 0 );