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"
43 #include "subdivider.h"
47 #include "trimvertpool.h"
51 enum i_result { INTERSECT_VERTEX, INTERSECT_EDGE };
54 #ifndef NDEBUG // for asserts only
55 static int arc_classify( Arc_ptr, int, REAL );
57 static enum i_result pwlarc_intersect( PwlArc *, int, REAL, int, int[3] );
61 Subdivider::partition( Bin & bin, Bin & left, Bin & intersections,
62 Bin & right, Bin & unknown, int param, REAL value )
64 Bin headonleft, headonright, tailonleft, tailonright;
66 for( Arc_ptr jarc = bin.removearc(); jarc; jarc = bin.removearc() ) {
68 REAL tdiff = jarc->tail()[param] - value;
69 REAL hdiff = jarc->head()[param] - value;
74 } else if( hdiff == 0.0 ) {
75 tailonright.addarc( jarc );
78 switch( arc_split(jarc, param, value, 0) ) {
80 tailonright.addarc( jarc );
81 headonleft.addarc( jarc->next );
84 assert( jarc->head()[param] > value );
86 tailonright.addarc( jtemp = jarc->next );
87 headonleft.addarc( jtemp->next );
90 assert( jarc->head()[param] <= value );
91 tailonright .addarc( jarc );
92 headonleft.addarc( jtemp = jarc->next );
93 left.addarc( jtemp->next );
97 tailonright.addarc( jtemp = jarc->next );
98 headonleft.addarc( jtemp = jtemp->next );
99 left.addarc( jtemp->next );
102 } else if( tdiff == 0.0 ) {
104 headonright.addarc( jarc );
105 } else if( hdiff == 0.0 ) {
106 unknown.addarc( jarc );
108 headonleft.addarc( jarc );
113 switch( arc_split(jarc, param, value, 1) ) {
115 tailonleft.addarc( jarc );
116 headonright.addarc( jarc->next );
119 assert( jarc->head()[param] < value );
121 tailonleft.addarc( jtemp = jarc->next );
122 headonright.addarc( jtemp->next );
125 assert( jarc->head()[param] >= value );
126 tailonleft.addarc( jarc );
127 headonright.addarc( jtemp = jarc->next );
128 right.addarc( jtemp->next );
132 tailonleft.addarc( jtemp = jarc->next );
133 headonright.addarc( jtemp = jtemp->next );
134 right.addarc( jtemp->next );
136 } else if( hdiff == 0.0 ) {
137 tailonleft.addarc( jarc );
144 classify_headonleft_s( headonleft, intersections, left, value );
145 classify_tailonleft_s( tailonleft, intersections, left, value );
146 classify_headonright_s( headonright, intersections, right, value );
147 classify_tailonright_s( tailonright, intersections, right, value );
149 classify_headonleft_t( headonleft, intersections, left, value );
150 classify_tailonleft_t( tailonleft, intersections, left, value );
151 classify_headonright_t( headonright, intersections, right, value );
152 classify_tailonright_t( tailonright, intersections, right, value );
157 vert_interp( TrimVertex *n, TrimVertex *l, TrimVertex *r, int p, REAL val )
159 assert( val > l->param[p]);
160 assert( val < r->param[p]);
165 if( l->param[1-p] != r->param[1-p] ) {
166 REAL ratio = (val - l->param[p]) / (r->param[p] - l->param[p]);
167 n->param[1-p] = l->param[1-p] +
168 ratio * (r->param[1-p] - l->param[1-p]);
170 n->param[1-p] = l->param[1-p];
175 Subdivider::arc_split( Arc_ptr jarc, int param, REAL value, int dir )
177 int maxvertex = jarc->pwlArc->npts;
179 TrimVertex* v = jarc->pwlArc->pts;
182 switch( pwlarc_intersect( jarc->pwlArc, param, value, dir, loc ) ) {
184 // When the parameter value lands on a vertex, life is sweet
185 case INTERSECT_VERTEX: {
186 jarc1 = new(arcpool) Arc( jarc, new( pwlarcpool) PwlArc( maxvertex-loc[1], &v[loc[1]] ) );
187 jarc->pwlArc->npts = loc[1] + 1;
188 jarc1->next = jarc->next;
189 jarc1->next->prev = jarc1;
192 assert(jarc->check() != 0);
196 // When the parameter value intersects an edge, we have to
197 // interpolate a new vertex. There are special cases
198 // if the new vertex is adjacent to one or both of the
199 // endpoints of the arc.
200 case INTERSECT_EDGE: {
211 // The split is between vertices at index j and i, in that
214 // JEB: This code is my idea of how to do the split without
215 // increasing the number of links. I'm doing this so that
216 // the is_rect routine can recognize rectangles created by
217 // subdivision. In exchange for simplifying the curve list,
218 // however, it costs in allocated space and vertex copies.
220 TrimVertex *newjunk = trimvertexpool.get(maxvertex -i+1 /*-j*/);
222 for(k=0; k<maxvertex-i; k++)
224 newjunk[k+1] = v[i+k];
225 newjunk[k+1].nuid = jarc->nuid;
228 TrimVertex *vcopy = trimvertexpool.get(maxvertex);
229 for(k=0; k<maxvertex; k++)
231 vcopy[k].param[0] = v[k].param[0];
232 vcopy[k].param[1] = v[k].param[1];
234 jarc->pwlArc->pts=vcopy;
236 v[i].nuid = jarc->nuid;
237 v[j].nuid = jarc->nuid;
238 vert_interp( &newjunk[0], &v[loc[0]], &v[loc[2]], param, value );
240 if( showingDegenerate() )
241 backend.triangle( &v[i], &newjunk[0], &v[j] );
243 vcopy[j+1].param[0]=newjunk[0].param[0];
244 vcopy[j+1].param[1]=newjunk[0].param[1];
247 jarc1 = new(arcpool) Arc( jarc,
248 new(pwlarcpool) PwlArc(maxvertex-i+1 , newjunk ) );
250 jarc->pwlArc->npts = j+2;
251 jarc1->next = jarc->next;
252 jarc1->next->prev = jarc1;
255 assert(jarc->check() != 0);
259 // JEB: This is the original version:
261 Arc_ptr jarc2, jarc3;
263 TrimVertex *newjunk = trimvertexpool.get(3);
264 v[i].nuid = jarc->nuid;
265 v[j].nuid = jarc->nuid;
268 vert_interp( &newjunk[1], &v[loc[0]], &v[loc[2]], param, value );
270 if( showingDegenerate() )
271 backend.triangle( &newjunk[2], &newjunk[1], &newjunk[0] );
273 // New vertex adjacent to both endpoints
274 if (maxvertex == 2) {
275 jarc1 = new(arcpool) Arc( jarc, new(pwlarcpool) PwlArc( 2, newjunk+1 ) );
276 jarc->pwlArc->npts = 2;
277 jarc->pwlArc->pts = newjunk;
278 jarc1->next = jarc->next;
279 jarc1->next->prev = jarc1;
282 assert(jarc->check() != 0);
286 // New vertex adjacent to ending point of arc
287 } else if (maxvertex - j == 2) {
288 jarc1 = new(arcpool) Arc( jarc, new(pwlarcpool) PwlArc( 2, newjunk ) );
289 jarc2 = new(arcpool) Arc( jarc, new(pwlarcpool) PwlArc( 2, newjunk+1 ) );
290 jarc->pwlArc->npts = maxvertex-1;
291 jarc2->next = jarc->next;
292 jarc2->next->prev = jarc2;
297 assert(jarc->check() != 0);
300 // New vertex adjacent to starting point of arc
302 jarc1 = new(arcpool) Arc( jarc, new(pwlarcpool) PwlArc( 2, newjunk+1 ) );
303 jarc2 = new(arcpool) Arc( jarc,
304 new(pwlarcpool) PwlArc( maxvertex-1, &jarc->pwlArc->pts[1] ) );
305 jarc->pwlArc->npts = 2;
306 jarc->pwlArc->pts = newjunk;
307 jarc2->next = jarc->next;
308 jarc2->next->prev = jarc2;
313 assert(jarc->check() != 0);
316 // It's somewhere in the middle
318 jarc1 = new(arcpool) Arc( jarc, new(pwlarcpool) PwlArc( 2, newjunk ) );
319 jarc2 = new(arcpool) Arc( jarc, new(pwlarcpool) PwlArc( 2, newjunk+1 ) );
320 jarc3 = new(arcpool) Arc( jarc, new(pwlarcpool) PwlArc( maxvertex-i, v+i ) );
321 jarc->pwlArc->npts = j + 1;
322 jarc3->next = jarc->next;
323 jarc3->next->prev = jarc3;
330 assert(jarc->check() != 0);
336 return -1; //picked -1 since it's not used
340 /*----------------------------------------------------------------------------
341 * pwlarc_intersect - find intersection of pwlArc and isoparametric line
342 *----------------------------------------------------------------------------
353 assert( pwlArc->npts > 0 );
356 TrimVertex *v = pwlArc->pts;
358 int imax = pwlArc->npts - 1;
359 assert( value > v[imin].param[param] );
360 assert( value < v[imax].param[param] );
361 while( (imax - imin) > 1 ) {
362 int imid = (imax + imin)/2;
363 if( v[imid].param[param] > value )
365 else if( v[imid].param[param] < value )
369 return INTERSECT_VERTEX;
374 return INTERSECT_EDGE;
376 TrimVertex *v = pwlArc->pts;
378 int imin = pwlArc->npts - 1;
379 assert( value > v[imin].param[param] );
380 assert( value < v[imax].param[param] );
381 while( (imin - imax) > 1 ) {
382 int imid = (imax + imin)/2;
383 if( v[imid].param[param] > value )
385 else if( v[imid].param[param] < value )
389 return INTERSECT_VERTEX;
394 return INTERSECT_EDGE;
398 /*----------------------------------------------------------------------------
399 * arc_classify - determine which side of a line a jarc lies
400 *----------------------------------------------------------------------------
403 #ifndef NDEBUG // for asserts only
405 arc_classify( Arc_ptr jarc, int param, REAL value )
409 tdiff = jarc->tail()[0] - value;
410 hdiff = jarc->head()[0] - value;
412 tdiff = jarc->tail()[1] - value;
413 hdiff = jarc->head()[1] - value;
419 } else if( hdiff == 0.0 ) {
424 } else if( tdiff == 0.0 ) {
427 } else if( hdiff == 0.0 ) {
435 } else if( hdiff == 0.0 ) {
445 Subdivider::classify_tailonleft_s( Bin& bin, Bin& in, Bin& out, REAL val )
447 /* tail at left, head on line */
450 while( (j = bin.removearc()) != NULL ) {
451 assert( arc_classify( j, 0, val ) == 0x02 );
454 REAL diff = j->next->head()[0] - val;
457 } else if( diff < 0.0 ) {
458 if( ccwTurn_sl( j, j->next ) )
463 if( j->next->tail()[1] > j->next->head()[1] )
472 Subdivider::classify_tailonleft_t( Bin& bin, Bin& in, Bin& out, REAL val )
474 /* tail at left, head on line */
477 while( (j = bin.removearc()) != NULL ) {
478 assert( arc_classify( j, 1, val ) == 0x02 );
481 REAL diff = j->next->head()[1] - val;
484 } else if( diff < 0.0 ) {
485 if( ccwTurn_tl( j, j->next ) )
490 if (j->next->tail()[0] > j->next->head()[0] )
499 Subdivider::classify_headonleft_s( Bin& bin, Bin& in, Bin& out, REAL val )
501 /* tail on line, head at left */
504 while( (j = bin.removearc()) != NULL ) {
505 assert( arc_classify( j, 0, val ) == 0x20 );
509 REAL diff = j->prev->tail()[0] - val;
512 } else if( diff < 0.0 ) {
513 if( ccwTurn_sl( j->prev, j ) )
518 if( j->prev->tail()[1] > j->prev->head()[1] )
527 Subdivider::classify_headonleft_t( Bin& bin, Bin& in, Bin& out, REAL val )
529 /* tail on line, head at left */
532 while( (j = bin.removearc()) != NULL ) {
533 assert( arc_classify( j, 1, val ) == 0x20 );
536 REAL diff = j->prev->tail()[1] - val;
539 } else if( diff < 0.0 ) {
540 if( ccwTurn_tl( j->prev, j ) )
545 if( j->prev->tail()[0] > j->prev->head()[0] )
555 Subdivider::classify_tailonright_s( Bin& bin, Bin& in, Bin& out, REAL val )
557 /* tail at right, head on line */
560 while( (j = bin.removearc()) != NULL ) {
561 assert( arc_classify( j, 0, val ) == 0x12);
565 REAL diff = j->next->head()[0] - val;
567 if( ccwTurn_sr( j, j->next ) )
571 } else if( diff < 0.0 ) {
574 if( j->next->tail()[1] > j->next->head()[1] )
583 Subdivider::classify_tailonright_t( Bin& bin, Bin& in, Bin& out, REAL val )
585 /* tail at right, head on line */
588 while( (j = bin.removearc()) != NULL ) {
589 assert( arc_classify( j, 1, val ) == 0x12);
593 REAL diff = j->next->head()[1] - val;
595 if( ccwTurn_tr( j, j->next ) )
599 } else if( diff < 0.0 ) {
602 if( j->next->tail()[0] > j->next->head()[0] )
611 Subdivider::classify_headonright_s( Bin& bin, Bin& in, Bin& out, REAL val )
613 /* tail on line, head at right */
616 while( (j = bin.removearc()) != NULL ) {
617 assert( arc_classify( j, 0, val ) == 0x21 );
621 REAL diff = j->prev->tail()[0] - val;
623 if( ccwTurn_sr( j->prev, j ) )
627 } else if( diff < 0.0 ) {
630 if( j->prev->tail()[1] > j->prev->head()[1] )
639 Subdivider::classify_headonright_t( Bin& bin, Bin& in, Bin& out, REAL val )
641 /* tail on line, head at right */
644 while( (j = bin.removearc()) != NULL ) {
645 assert( arc_classify( j, 1, val ) == 0x21 );
649 REAL diff = j->prev->tail()[1] - val;
651 if( ccwTurn_tr( j->prev, j ) )
655 } else if( diff < 0.0 ) {
658 if( j->prev->tail()[0] > j->prev->head()[0] )