FreeWRL/FreeX3D  3.0.0
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 
PwlArc
Definition: pwlarc.h:44
Arc
Definition: arc.h:55
Bin
Definition: bin.h:43