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.
38 * $Date: 2006/03/14 15:08:52 $ $Revision: 1.2 $
39 * $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libnurbs/internals/splitarcs.cc,v 1.2 2006/03/14 15:08:52 brianp Exp $
42 #include "glimports.h"
46 #include "subdivider.h"
47 #include "arcsorter.h"
51 /* local preprocessor definitions */
54 /*----------------------------------------------------------------------------
55 * Subdivider::split - split trim regions in source bin by line (param == value).
56 *----------------------------------------------------------------------------
60 Subdivider::split( Bin
& bin
, Bin
& left
, Bin
& right
, int param
, REAL value
)
62 Bin intersections
, unknown
;
64 partition( bin
, left
, intersections
, right
, unknown
, param
, value
);
66 int count
= intersections
.numarcs();
70 intersections
.show( "intersections" );
71 right
.show( "right" );
73 ::mylongjmp( jumpbuffer
, 29 );
76 Arc_ptr arclist
[MAXARCS
], *list
;
77 if( count
>= MAXARCS
) {
78 list
= new Arc_ptr
[count
];
83 Arc_ptr jarc
, *last
, *lptr
;
84 for( last
= list
; (jarc
=intersections
.removearc()) != NULL
; last
++ )
87 if( param
== 0 ) { /* sort into increasing t order */
88 ArcSdirSorter
sorter(*this);
89 sorter
.qsort( list
, count
);
91 //::qsort ((void *)list, count, sizeof(Arc_ptr), (cmpfunc)compare_s);
92 for( lptr
=list
; lptr
<last
; lptr
+=2 )
93 check_s ( lptr
[0], lptr
[1] );
94 for( lptr
=list
; lptr
<last
; lptr
+=2 )
95 join_s ( left
, right
, lptr
[0], lptr
[1] );
96 for( lptr
=list
; lptr
!= last
; lptr
++ ) {
97 if( ((*lptr
)->head()[0] <= value
) && ((*lptr
)->tail()[0] <= value
) )
100 right
.addarc( *lptr
);
102 } else { /* sort into decreasing s order */
103 ArcTdirSorter
sorter(*this);
104 sorter
.qsort( list
, count
);
105 //::qsort ((void *)list, count, sizeof(Arc_ptr), (cmpfunc)compare_t);
106 for( lptr
=list
; lptr
<last
; lptr
+=2 )
107 check_t ( lptr
[0], lptr
[1] );
108 for( lptr
=list
; lptr
<last
; lptr
+=2 )
109 join_t ( left
, right
, lptr
[0], lptr
[1] );
110 for( lptr
=list
; lptr
!= last
; lptr
++ ) {
111 if( ((*lptr
)->head()[1] <= value
) && ((*lptr
)->tail()[1] <= value
) )
112 left
.addarc( *lptr
);
114 right
.addarc( *lptr
);
118 if( list
!= arclist
) delete[] list
;
124 Subdivider::check_s( Arc_ptr jarc1
, Arc_ptr jarc2
)
126 assert( jarc1
->check( ) != 0 );
127 assert( jarc2
->check( ) != 0 );
128 assert( jarc1
->next
->check( ) != 0 );
129 assert( jarc2
->next
->check( ) != 0 );
130 assert( jarc1
!= jarc2
);
132 /* XXX - if these assertions fail, it is due to user error or
134 if( ! ( jarc1
->tail()[0] < (jarc1
)->head()[0] ) ) {
136 _glu_dprintf( "s difference %f\n", (jarc1
)->tail()[0] - (jarc1
)->head()[0] );
138 ::mylongjmp( jumpbuffer
, 28 );
141 if( ! ( jarc2
->tail()[0] > (jarc2
)->head()[0] ) ) {
143 _glu_dprintf( "s difference %f\n", (jarc2
)->tail()[0] - (jarc2
)->head()[0] );
145 ::mylongjmp( jumpbuffer
, 28 );
150 Subdivider::link( Arc_ptr jarc1
, Arc_ptr jarc2
, Arc_ptr up
, Arc_ptr down
)
152 up
->nuid
= down
->nuid
= 0; // XXX
156 up
->prev
= jarc1
->prev
;
157 down
->prev
= jarc2
->prev
;
159 down
->next
->prev
= down
;
161 down
->prev
->next
= down
;
166 Subdivider::simple_link( Arc_ptr jarc1
, Arc_ptr jarc2
)
168 Arc_ptr tmp
= jarc2
->prev
;
169 jarc2
->prev
= jarc1
->prev
;
171 jarc2
->prev
->next
= jarc2
;
172 jarc1
->prev
->next
= jarc1
;
176 /*----------------------------------------------------------------------------
177 * join - add a pair of oppositely directed jordan arcs between two arcs
178 *----------------------------------------------------------------------------
182 Subdivider::join_s( Bin
& left
, Bin
& right
, Arc_ptr jarc1
, Arc_ptr jarc2
)
184 assert( jarc1
->check( ) != 0);
185 assert( jarc2
->check( ) != 0);
186 assert( jarc1
!= jarc2
);
188 if( ! jarc1
->getitail() )
191 if( ! jarc2
->getitail() )
194 REAL s
= jarc1
->tail()[0];
195 REAL t1
= jarc1
->tail()[1];
196 REAL t2
= jarc2
->tail()[1];
199 simple_link( jarc1
, jarc2
);
201 Arc_ptr newright
= new(arcpool
) Arc( arc_right
, 0 );
202 Arc_ptr newleft
= new(arcpool
) Arc( arc_left
, 0 );
204 if( isBezierArcType() ) {
205 arctessellator
.bezier( newright
, s
, s
, t1
, t2
);
206 arctessellator
.bezier( newleft
, s
, s
, t2
, t1
);
208 arctessellator
.pwl_right( newright
, s
, t1
, t2
, stepsizes
[0] );
209 arctessellator
.pwl_left( newleft
, s
, t2
, t1
, stepsizes
[2] );
211 link( jarc1
, jarc2
, newright
, newleft
);
212 left
.addarc( newright
);
213 right
.addarc( newleft
);
216 assert( jarc1
->check( ) != 0 );
217 assert( jarc2
->check( ) != 0 );
218 assert( jarc1
->next
->check( ) != 0);
219 assert( jarc2
->next
->check( ) != 0);
223 Subdivider::check_t( Arc_ptr jarc1
, Arc_ptr jarc2
)
225 assert( jarc1
->check( ) != 0 );
226 assert( jarc2
->check( ) != 0 );
227 assert( jarc1
->next
->check( ) != 0 );
228 assert( jarc2
->next
->check( ) != 0 );
229 assert( jarc1
!= jarc2
);
231 /* XXX - if these assertions fail, it is due to user error or
233 if( ! ( jarc1
->tail()[1] < (jarc1
)->head()[1] ) ) {
235 _glu_dprintf( "t difference %f\n", jarc1
->tail()[1] - (jarc1
)->head()[1] );
237 ::mylongjmp( jumpbuffer
, 28 );
240 if( ! ( jarc2
->tail()[1] > (jarc2
)->head()[1] ) ) {
242 _glu_dprintf( "t difference %f\n", jarc2
->tail()[1] - (jarc2
)->head()[1] );
244 ::mylongjmp( jumpbuffer
, 28 );
248 /*----------------------------------------------------------------------------
249 * join_t - add a pair of oppositely directed jordan arcs between two arcs
250 *----------------------------------------------------------------------------
254 Subdivider::join_t( Bin
& bottom
, Bin
& top
, Arc_ptr jarc1
, Arc_ptr jarc2
)
256 assert( jarc1
->check( ) != 0 );
257 assert( jarc2
->check( ) != 0 );
258 assert( jarc1
->next
->check( ) != 0 );
259 assert( jarc2
->next
->check( ) != 0 );
260 assert( jarc1
!= jarc2
);
262 if( ! jarc1
->getitail() )
265 if( ! jarc2
->getitail() )
268 REAL s1
= jarc1
->tail()[0];
269 REAL s2
= jarc2
->tail()[0];
270 REAL t
= jarc1
->tail()[1];
273 simple_link( jarc1
, jarc2
);
275 Arc_ptr newtop
= new(arcpool
) Arc( arc_top
, 0 );
276 Arc_ptr newbot
= new(arcpool
) Arc( arc_bottom
, 0 );
278 if( isBezierArcType() ) {
279 arctessellator
.bezier( newtop
, s1
, s2
, t
, t
);
280 arctessellator
.bezier( newbot
, s2
, s1
, t
, t
);
282 arctessellator
.pwl_top( newtop
, t
, s1
, s2
, stepsizes
[1] );
283 arctessellator
.pwl_bottom( newbot
, t
, s2
, s1
, stepsizes
[3] );
285 link( jarc1
, jarc2
, newtop
, newbot
);
286 bottom
.addarc( newtop
);
287 top
.addarc( newbot
);
290 assert( jarc1
->check( ) != 0 );
291 assert( jarc2
->check( ) != 0 );
292 assert( jarc1
->next
->check( ) != 0 );
293 assert( jarc2
->next
->check( ) != 0 );