projects / mesa.git / blob
? search:


b39ea2121eff5f72d2962da7679cdeeb65f8c67e
[mesa.git] / src / glu / sgi / libnurbs / internals / intersect.cc
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 * intersect.c++
37 *
38 */
39
40 #include "glimports.h"
41 #include "myassert.h"
42 #include "mystdio.h"
43 #include "subdivider.h"
44 #include "arc.h"
45 #include "bin.h"
46 #include "backend.h"
47 #include "trimvertpool.h"
48
49 /*#define NOTDEF*/
50
51 enum i_result { INTERSECT_VERTEX, INTERSECT_EDGE };
52
53 /* local functions */
54 #ifndef NDEBUG // for asserts only
55 static int arc_classify( Arc_ptr, int, REAL );
56 #endif
57 static enum i_result pwlarc_intersect( PwlArc *, int, REAL, int, int[3] );
58
59
60 void
61 Subdivider::partition( Bin & bin, Bin & left, Bin & intersections,
62 Bin & right, Bin & unknown, int param, REAL value )
63 {
64 Bin headonleft, headonright, tailonleft, tailonright;
65
66 for( Arc_ptr jarc = bin.removearc(); jarc; jarc = bin.removearc() ) {
67
68 REAL tdiff = jarc->tail()[param] - value;
69 REAL hdiff = jarc->head()[param] - value;
70
71 if( tdiff > 0.0 ) {
72 if( hdiff > 0.0 ) {
73 right.addarc( jarc );
74 } else if( hdiff == 0.0 ) {
75 tailonright.addarc( jarc );
76 } else {
77 Arc_ptr jtemp;
78 switch( arc_split(jarc, param, value, 0) ) {
79 case 2:
80 tailonright.addarc( jarc );
81 headonleft.addarc( jarc->next );
82 break;
83 case 31:
84 assert( jarc->head()[param] > value );
85 right.addarc( jarc );
86 tailonright.addarc( jtemp = jarc->next );
87 headonleft.addarc( jtemp->next );
88 break;
89 case 32:
90 assert( jarc->head()[param] <= value );
91 tailonright .addarc( jarc );
92 headonleft.addarc( jtemp = jarc->next );
93 left.addarc( jtemp->next );
94 break;
95 case 4:
96 right.addarc( jarc );
97 tailonright.addarc( jtemp = jarc->next );
98 headonleft.addarc( jtemp = jtemp->next );
99 left.addarc( jtemp->next );
100 }
101 }
102 } else if( tdiff == 0.0 ) {
103 if( hdiff > 0.0 ) {
104 headonright.addarc( jarc );
105 } else if( hdiff == 0.0 ) {
106 unknown.addarc( jarc );
107 } else {
108 headonleft.addarc( jarc );
109 }
110 } else {
111 if( hdiff > 0.0 ) {
112 Arc_ptr jtemp;
113 switch( arc_split(jarc, param, value, 1) ) {
114 case 2:
115 tailonleft.addarc( jarc );
116 headonright.addarc( jarc->next );
117 break;
118 case 31:
119 assert( jarc->head()[param] < value );
120 left.addarc( jarc );
121 tailonleft.addarc( jtemp = jarc->next );
122 headonright.addarc( jtemp->next );
123 break;
124 case 32:
125 assert( jarc->head()[param] >= value );
126 tailonleft.addarc( jarc );
127 headonright.addarc( jtemp = jarc->next );
128 right.addarc( jtemp->next );
129 break;
130 case 4:
131 left.addarc( jarc );
132 tailonleft.addarc( jtemp = jarc->next );
133 headonright.addarc( jtemp = jtemp->next );
134 right.addarc( jtemp->next );
135 }
136 } else if( hdiff == 0.0 ) {
137 tailonleft.addarc( jarc );
138 } else {
139 left.addarc( jarc );
140 }
141 }
142 }
143 if( param == 0 ) {
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 );
148 } else {
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 );
153 }
154 }
155
156 inline static void
157 vert_interp( TrimVertex *n, TrimVertex *l, TrimVertex *r, int p, REAL val )
158 {
159 assert( val > l->param[p]);
160 assert( val < r->param[p]);
161
162 n->nuid = l->nuid;
163
164 n->param[p] = val;
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]);
169 } else {
170 n->param[1-p] = l->param[1-p];
171 }
172 }
173
174 int
175 Subdivider::arc_split( Arc_ptr jarc, int param, REAL value, int dir )
176 {
177 int maxvertex = jarc->pwlArc->npts;
178 Arc_ptr jarc1;
179 TrimVertex* v = jarc->pwlArc->pts;
180
181 int loc[3];
182 switch( pwlarc_intersect( jarc->pwlArc, param, value, dir, loc ) ) {
183
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;
190 jarc->next = jarc1;
191 jarc1->prev = jarc;
192 assert(jarc->check() != 0);
193 return 2;
194 }
195
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: {
201 int i, j;
202 if( dir == 0 ) {
203 i = loc[0];
204 j = loc[2];
205 } else {
206 i = loc[2];
207 j = loc[0];
208 }
209
210 #ifndef NOTDEF
211 // The split is between vertices at index j and i, in that
212 // order (j < i)
213
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.
219
220 TrimVertex *newjunk = trimvertexpool.get(maxvertex -i+1 /*-j*/);
221 int k;
222 for(k=0; k<maxvertex-i; k++)
223 {
224 newjunk[k+1] = v[i+k];
225 newjunk[k+1].nuid = jarc->nuid;
226 }
227
228 TrimVertex *vcopy = trimvertexpool.get(maxvertex);
229 for(k=0; k<maxvertex; k++)
230 {
231 vcopy[k].param[0] = v[k].param[0];
232 vcopy[k].param[1] = v[k].param[1];
233 }
234 jarc->pwlArc->pts=vcopy;
235
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 );
239
240 if( showingDegenerate() )
241 backend.triangle( &v[i], &newjunk[0], &v[j] );
242
243 vcopy[j+1].param[0]=newjunk[0].param[0];
244 vcopy[j+1].param[1]=newjunk[0].param[1];
245
246
247 jarc1 = new(arcpool) Arc( jarc,
248 new(pwlarcpool) PwlArc(maxvertex-i+1 , newjunk ) );
249
250 jarc->pwlArc->npts = j+2;
251 jarc1->next = jarc->next;
252 jarc1->next->prev = jarc1;
253 jarc->next = jarc1;
254 jarc1->prev = jarc;
255 assert(jarc->check() != 0);
256
257 return 2;
258 #endif //not NOTDEF
259 // JEB: This is the original version:
260 #ifdef NOTDEF
261 Arc_ptr jarc2, jarc3;
262
263 TrimVertex *newjunk = trimvertexpool.get(3);
264 v[i].nuid = jarc->nuid;
265 v[j].nuid = jarc->nuid;
266 newjunk[0] = v[j];
267 newjunk[2] = v[i];
268 vert_interp( &newjunk[1], &v[loc[0]], &v[loc[2]], param, value );
269
270 if( showingDegenerate() )
271 backend.triangle( &newjunk[2], &newjunk[1], &newjunk[0] );
272
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;
280 jarc->next = jarc1;
281 jarc1->prev = jarc;
282 assert(jarc->check() != 0);
283
284 return 2;
285
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;
293 jarc->next = jarc1;
294 jarc1->prev = jarc;
295 jarc1->next = jarc2;
296 jarc2->prev = jarc1;
297 assert(jarc->check() != 0);
298 return 31;
299
300 // New vertex adjacent to starting point of arc
301 } else if (i == 1) {
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;
309 jarc->next = jarc1;
310 jarc1->prev = jarc;
311 jarc1->next = jarc2;
312 jarc2->prev = jarc1;
313 assert(jarc->check() != 0);
314 return 32;
315
316 // It's somewhere in the middle
317 } else {
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;
324 jarc->next = jarc1;
325 jarc1->prev = jarc;
326 jarc1->next = jarc2;
327 jarc2->prev = jarc1;
328 jarc2->next = jarc3;
329 jarc3->prev = jarc2;
330 assert(jarc->check() != 0);
331 return 4;
332 }
333 #endif // NOTDEF
334 }
335 default:
336 return -1; //picked -1 since it's not used
337 }
338 }
339
340 /*----------------------------------------------------------------------------
341 * pwlarc_intersect - find intersection of pwlArc and isoparametric line
342 *----------------------------------------------------------------------------
343 */
344
345 static enum i_result
346 pwlarc_intersect(
347 PwlArc *pwlArc,
348 int param,
349 REAL value,
350 int dir,
351 int loc[3] )
352 {
353 assert( pwlArc->npts > 0 );
354
355 if( dir ) {
356 TrimVertex *v = pwlArc->pts;
357 int imin = 0;
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 )
364 imax = imid;
365 else if( v[imid].param[param] < value )
366 imin = imid;
367 else {
368 loc[1] = imid;
369 return INTERSECT_VERTEX;
370 }
371 }
372 loc[0] = imin;
373 loc[2] = imax;
374 return INTERSECT_EDGE;
375 } else {
376 TrimVertex *v = pwlArc->pts;
377 int imax = 0;
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 )
384 imax = imid;
385 else if( v[imid].param[param] < value )
386 imin = imid;
387 else {
388 loc[1] = imid;
389 return INTERSECT_VERTEX;
390 }
391 }
392 loc[0] = imin;
393 loc[2] = imax;
394 return INTERSECT_EDGE;
395 }
396 }
397
398 /*----------------------------------------------------------------------------
399 * arc_classify - determine which side of a line a jarc lies
400 *----------------------------------------------------------------------------
401 */
402
403 #ifndef NDEBUG // for asserts only
404 static int
405 arc_classify( Arc_ptr jarc, int param, REAL value )
406 {
407 REAL tdiff, hdiff;
408 if( param == 0 ) {
409 tdiff = jarc->tail()[0] - value;
410 hdiff = jarc->head()[0] - value;
411 } else {
412 tdiff = jarc->tail()[1] - value;
413 hdiff = jarc->head()[1] - value;
414 }
415
416 if( tdiff > 0.0 ) {
417 if( hdiff > 0.0 ) {
418 return 0x11;
419 } else if( hdiff == 0.0 ) {
420 return 0x12;
421 } else {
422 return 0x10;
423 }
424 } else if( tdiff == 0.0 ) {
425 if( hdiff > 0.0 ) {
426 return 0x21;
427 } else if( hdiff == 0.0 ) {
428 return 0x22;
429 } else {
430 return 0x20;
431 }
432 } else {
433 if( hdiff > 0.0 ) {
434 return 0x01;
435 } else if( hdiff == 0.0 ) {
436 return 0x02;
437 } else {
438 return 0;
439 }
440 }
441 }
442 #endif
443
444 void
445 Subdivider::classify_tailonleft_s( Bin& bin, Bin& in, Bin& out, REAL val )
446 {
447 /* tail at left, head on line */
448 Arc_ptr j;
449
450 while( (j = bin.removearc()) != NULL ) {
451 assert( arc_classify( j, 0, val ) == 0x02 );
452 j->clearitail();
453
454 REAL diff = j->next->head()[0] - val;
455 if( diff > 0.0 ) {
456 in.addarc( j );
457 } else if( diff < 0.0 ) {
458 if( ccwTurn_sl( j, j->next ) )
459 out.addarc( j );
460 else
461 in.addarc( j );
462 } else {
463 if( j->next->tail()[1] > j->next->head()[1] )
464 in.addarc(j);
465 else
466 out.addarc(j);
467 }
468 }
469 }
470
471 void
472 Subdivider::classify_tailonleft_t( Bin& bin, Bin& in, Bin& out, REAL val )
473 {
474 /* tail at left, head on line */
475 Arc_ptr j;
476
477 while( (j = bin.removearc()) != NULL ) {
478 assert( arc_classify( j, 1, val ) == 0x02 );
479 j->clearitail();
480
481 REAL diff = j->next->head()[1] - val;
482 if( diff > 0.0 ) {
483 in.addarc( j );
484 } else if( diff < 0.0 ) {
485 if( ccwTurn_tl( j, j->next ) )
486 out.addarc( j );
487 else
488 in.addarc( j );
489 } else {
490 if (j->next->tail()[0] > j->next->head()[0] )
491 out.addarc( j );
492 else
493 in.addarc( j );
494 }
495 }
496 }
497
498 void
499 Subdivider::classify_headonleft_s( Bin& bin, Bin& in, Bin& out, REAL val )
500 {
501 /* tail on line, head at left */
502 Arc_ptr j;
503
504 while( (j = bin.removearc()) != NULL ) {
505 assert( arc_classify( j, 0, val ) == 0x20 );
506
507 j->setitail();
508
509 REAL diff = j->prev->tail()[0] - val;
510 if( diff > 0.0 ) {
511 out.addarc( j );
512 } else if( diff < 0.0 ) {
513 if( ccwTurn_sl( j->prev, j ) )
514 out.addarc( j );
515 else
516 in.addarc( j );
517 } else {
518 if( j->prev->tail()[1] > j->prev->head()[1] )
519 in.addarc( j );
520 else
521 out.addarc( j );
522 }
523 }
524 }
525
526 void
527 Subdivider::classify_headonleft_t( Bin& bin, Bin& in, Bin& out, REAL val )
528 {
529 /* tail on line, head at left */
530 Arc_ptr j;
531
532 while( (j = bin.removearc()) != NULL ) {
533 assert( arc_classify( j, 1, val ) == 0x20 );
534 j->setitail();
535
536 REAL diff = j->prev->tail()[1] - val;
537 if( diff > 0.0 ) {
538 out.addarc( j );
539 } else if( diff < 0.0 ) {
540 if( ccwTurn_tl( j->prev, j ) )
541 out.addarc( j );
542 else
543 in.addarc( j );
544 } else {
545 if( j->prev->tail()[0] > j->prev->head()[0] )
546 out.addarc( j );
547 else
548 in.addarc( j );
549 }
550 }
551 }
552
553
554 void
555 Subdivider::classify_tailonright_s( Bin& bin, Bin& in, Bin& out, REAL val )
556 {
557 /* tail at right, head on line */
558 Arc_ptr j;
559
560 while( (j = bin.removearc()) != NULL ) {
561 assert( arc_classify( j, 0, val ) == 0x12);
562
563 j->clearitail();
564
565 REAL diff = j->next->head()[0] - val;
566 if( diff > 0.0 ) {
567 if( ccwTurn_sr( j, j->next ) )
568 out.addarc( j );
569 else
570 in.addarc( j );
571 } else if( diff < 0.0 ) {
572 in.addarc( j );
573 } else {
574 if( j->next->tail()[1] > j->next->head()[1] )
575 out.addarc( j );
576 else
577 in.addarc( j );
578 }
579 }
580 }
581
582 void
583 Subdivider::classify_tailonright_t( Bin& bin, Bin& in, Bin& out, REAL val )
584 {
585 /* tail at right, head on line */
586 Arc_ptr j;
587
588 while( (j = bin.removearc()) != NULL ) {
589 assert( arc_classify( j, 1, val ) == 0x12);
590
591 j->clearitail();
592
593 REAL diff = j->next->head()[1] - val;
594 if( diff > 0.0 ) {
595 if( ccwTurn_tr( j, j->next ) )
596 out.addarc( j );
597 else
598 in.addarc( j );
599 } else if( diff < 0.0 ) {
600 in.addarc( j );
601 } else {
602 if( j->next->tail()[0] > j->next->head()[0] )
603 in.addarc( j );
604 else
605 out.addarc( j );
606 }
607 }
608 }
609
610 void
611 Subdivider::classify_headonright_s( Bin& bin, Bin& in, Bin& out, REAL val )
612 {
613 /* tail on line, head at right */
614 Arc_ptr j;
615
616 while( (j = bin.removearc()) != NULL ) {
617 assert( arc_classify( j, 0, val ) == 0x21 );
618
619 j->setitail();
620
621 REAL diff = j->prev->tail()[0] - val;
622 if( diff > 0.0 ) {
623 if( ccwTurn_sr( j->prev, j ) )
624 out.addarc( j );
625 else
626 in.addarc( j );
627 } else if( diff < 0.0 ) {
628 out.addarc( j );
629 } else {
630 if( j->prev->tail()[1] > j->prev->head()[1] )
631 out.addarc( j );
632 else
633 in.addarc( j );
634 }
635 }
636 }
637
638 void
639 Subdivider::classify_headonright_t( Bin& bin, Bin& in, Bin& out, REAL val )
640 {
641 /* tail on line, head at right */
642 Arc_ptr j;
643
644 while( (j = bin.removearc()) != NULL ) {
645 assert( arc_classify( j, 1, val ) == 0x21 );
646
647 j->setitail();
648
649 REAL diff = j->prev->tail()[1] - val;
650 if( diff > 0.0 ) {
651 if( ccwTurn_tr( j->prev, j ) )
652 out.addarc( j );
653 else
654 in.addarc( j );
655 } else if( diff < 0.0 ) {
656 out.addarc( j );
657 } else {
658 if( j->prev->tail()[0] > j->prev->head()[0] )
659 in.addarc( j );
660 else
661 out.addarc( j );
662 }
663 }
664 }
665