FreeWRL/FreeX3D  3.0.0
ccw.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  * ccw.c++
37  *
38  */
39 
40 #include "glimports.h"
41 #include "mystdio.h"
42 #include "myassert.h"
43 #include "subdivider.h"
44 #include "types.h"
45 #include "arc.h"
46 #include "trimvertex.h"
47 #include "simplemath.h"
48 
49 inline int
50 Subdivider::bbox( TrimVertex *a, TrimVertex *b, TrimVertex *c, int p )
51 {
52  return bbox( a->param[p], b->param[p], c->param[p],
53  a->param[1-p], b->param[1-p], c->param[1-p] );
54 }
55 
56 int
57 Subdivider::ccwTurn_sr( Arc_ptr j1, Arc_ptr j2 ) // dir = 1
58 {
59  register TrimVertex *v1 = &j1->pwlArc->pts[j1->pwlArc->npts-1];
60  register TrimVertex *v1last = &j1->pwlArc->pts[0];
61  register TrimVertex *v2 = &j2->pwlArc->pts[0];
62  register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
63  register TrimVertex *v1next = v1-1;
64  register TrimVertex *v2next = v2+1;
65  int sgn;
66 
67  assert( v1 != v1last );
68  assert( v2 != v2last );
69 
70 #ifndef NDEBUG
71  _glu_dprintf( "arc_ccw_turn, p = %d\n", 0 );
72 #endif
73 
74  // the arcs lie on the line (0 == v1->param[0])
75  if( v1->param[0] == v1next->param[0] && v2->param[0] == v2next->param[0] )
76  return 0;
77 
78  if( v2next->param[0] < v2->param[0] || v1next->param[0] < v1->param[0] )
79  ::mylongjmp( jumpbuffer, 28 );
80 
81  if( v1->param[1] < v2->param[1] )
82  return 0;
83  else if( v1->param[1] > v2->param[1] )
84  return 1;
85 
86  while( 1 ) {
87  if( v1next->param[0] < v2next->param[0] ) {
88 #ifndef NDEBUG
89  _glu_dprintf( "case a\n" );
90 #endif
91  assert( v1->param[0] <= v1next->param[0] );
92  assert( v2->param[0] <= v1next->param[0] );
93  switch( bbox( v2, v2next, v1next, 1 ) ) {
94  case -1:
95  return 0;
96  case 0:
97  sgn = ccw( v1next, v2, v2next );
98  if( sgn != -1 ) {
99  return sgn;
100  } else {
101 #ifdef DEBUG
102  _glu_dprintf( "decr\n" );
103 #endif
104  v1 = v1next--;
105  if( v1 == v1last ) {
106 #ifdef DEBUG
107  _glu_dprintf( "no good results\n" );
108 #endif
109  return 0; // ill-conditioned, guess answer
110  }
111  }
112  break;
113  case 1:
114  return 1;
115  }
116  } else if( v1next->param[0] > v2next->param[0] ) {
117 #ifndef NDEBUG
118  _glu_dprintf( "case b\n" );
119 #endif
120  assert( v1->param[0] <= v2next->param[0] );
121  assert( v2->param[0] <= v2next->param[0] );
122  switch( bbox( v1, v1next, v2next, 1 ) ) {
123  case -1:
124  return 1;
125  case 0:
126  sgn = ccw( v1next, v1, v2next );
127  if( sgn != -1 ) {
128  return sgn;
129  } else {
130 #ifdef DEBUG
131  _glu_dprintf( "incr\n" );
132 #endif
133  v2 = v2next++;
134  if( v2 == v2last ) {
135 #ifdef DEBUG
136  _glu_dprintf( "no good results\n" );
137 #endif
138  return 0; // ill-conditioned, guess answer
139  }
140  }
141  break;
142  case 1:
143  return 0;
144  }
145  } else {
146 #ifndef NDEBUG
147  _glu_dprintf( "case ab\n" );
148 #endif
149  if( v1next->param[1] < v2next->param[1] )
150  return 0;
151  else if( v1next->param[1] > v2next->param[1] )
152  return 1;
153  else {
154 #ifdef DEBUG
155  _glu_dprintf( "incr\n" );
156 #endif
157  v2 = v2next++;
158  if( v2 == v2last ) {
159 #ifdef DEBUG
160  _glu_dprintf( "no good results\n" );
161 #endif
162  return 0; // ill-conditioned, guess answer
163  }
164  }
165  }
166  }
167 }
168 
169 int
170 Subdivider::ccwTurn_sl( Arc_ptr j1, Arc_ptr j2 ) // dir = 0
171 {
172  register TrimVertex *v1 = &j1->pwlArc->pts[j1->pwlArc->npts-1];
173  register TrimVertex *v1last = &j1->pwlArc->pts[0];
174  register TrimVertex *v2 = &j2->pwlArc->pts[0];
175  register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
176  register TrimVertex *v1next = v1-1;
177  register TrimVertex *v2next = v2+1;
178  int sgn;
179 
180  assert( v1 != v1last );
181  assert( v2 != v2last );
182 
183 #ifndef NDEBUG
184  _glu_dprintf( "arc_ccw_turn, p = %d\n", 0 );
185 #endif
186 
187  // the arcs lie on the line (0 == v1->param[0])
188  if( v1->param[0] == v1next->param[0] && v2->param[0] == v2next->param[0] )
189  return 0;
190 
191  if( v2next->param[0] > v2->param[0] || v1next->param[0] > v1->param[0] )
192  ::mylongjmp( jumpbuffer, 28 );
193 
194  if( v1->param[1] < v2->param[1] )
195  return 1;
196  else if( v1->param[1] > v2->param[1] )
197  return 0;
198 
199  while( 1 ) {
200  if( v1next->param[0] > v2next->param[0] ) {
201 #ifndef NDEBUG
202  _glu_dprintf( "case c\n" );
203 #endif
204  assert( v1->param[0] >= v1next->param[0] );
205  assert( v2->param[0] >= v1next->param[0] );
206  switch( bbox( v2next, v2, v1next, 1 ) ) {
207  case -1:
208  return 1;
209  case 0:
210  sgn = ccw( v1next, v2, v2next );
211  if( sgn != -1 )
212  return sgn;
213  else {
214  v1 = v1next--;
215 #ifdef DEBUG
216  _glu_dprintf( "decr\n" );
217 #endif
218  if( v1 == v1last ) {
219 #ifdef DEBUG
220  _glu_dprintf( "no good results\n" );
221 #endif
222  return 0; // ill-conditioned, guess answer
223  }
224  }
225  break;
226  case 1:
227  return 0;
228  }
229  } else if( v1next->param[0] < v2next->param[0] ) {
230 #ifndef NDEBUG
231  _glu_dprintf( "case d\n" );
232 #endif
233  assert( v1->param[0] >= v2next->param[0] );
234  assert( v2->param[0] >= v2next->param[0] );
235  switch( bbox( v1next, v1, v2next, 1 ) ) {
236  case -1:
237  return 0;
238  case 0:
239  sgn = ccw( v1next, v1, v2next );
240  if( sgn != -1 )
241  return sgn;
242  else {
243  v2 = v2next++;
244 #ifdef DEBUG
245  _glu_dprintf( "incr\n" );
246 #endif
247  if( v2 == v2last ) {
248 #ifdef DEBUG
249  _glu_dprintf( "no good results\n" );
250 #endif
251  return 0; // ill-conditioned, guess answer
252  }
253  }
254  break;
255  case 1:
256  return 1;
257  }
258  } else {
259 #ifdef DEBUG
260  _glu_dprintf( "case cd\n" );
261 #endif
262  if( v1next->param[1] < v2next->param[1] )
263  return 1;
264  else if( v1next->param[1] > v2next->param[1] )
265  return 0;
266  else {
267  v2 = v2next++;
268 #ifdef DEBUG
269  _glu_dprintf( "incr\n" );
270 #endif
271  if( v2 == v2last ) {
272 #ifdef DEBUG
273  _glu_dprintf( "no good results\n" );
274 #endif
275  return 0; // ill-conditioned, guess answer
276  }
277  }
278  }
279  }
280 }
281 
282 int
283 Subdivider::ccwTurn_tr( Arc_ptr j1, Arc_ptr j2 ) // dir = 1
284 {
285  register TrimVertex *v1 = &j1->pwlArc->pts[j1->pwlArc->npts-1];
286  register TrimVertex *v1last = &j1->pwlArc->pts[0];
287  register TrimVertex *v2 = &j2->pwlArc->pts[0];
288  register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
289  register TrimVertex *v1next = v1-1;
290  register TrimVertex *v2next = v2+1;
291  int sgn;
292 
293  assert( v1 != v1last );
294  assert( v2 != v2last );
295 
296 #ifndef NDEBUG
297  _glu_dprintf( "arc_ccw_turn, p = %d\n", 1 );
298 #endif
299 
300  // the arcs lie on the line (1 == v1->param[1])
301  if( v1->param[1] == v1next->param[1] && v2->param[1] == v2next->param[1] )
302  return 0;
303 
304  if( v2next->param[1] < v2->param[1] || v1next->param[1] < v1->param[1] )
305  ::mylongjmp( jumpbuffer, 28 );
306 
307  if( v1->param[0] < v2->param[0] )
308  return 1;
309  else if( v1->param[0] > v2->param[0] )
310  return 0;
311 
312  while( 1 ) {
313  if( v1next->param[1] < v2next->param[1] ) {
314 #ifndef NDEBUG
315  _glu_dprintf( "case a\n" );
316 #endif
317  assert( v1->param[1] <= v1next->param[1] );
318  assert( v2->param[1] <= v1next->param[1] );
319  switch( bbox( v2, v2next, v1next, 0 ) ) {
320  case -1:
321  return 1;
322  case 0:
323  sgn = ccw( v1next, v2, v2next );
324  if( sgn != -1 ) {
325  return sgn;
326  } else {
327 #ifdef DEBUG
328  _glu_dprintf( "decr\n" );
329 #endif
330  v1 = v1next--;
331  if( v1 == v1last ) {
332 #ifdef DEBUG
333  _glu_dprintf( "no good results\n" );
334 #endif
335  return 0; // ill-conditioned, guess answer
336  }
337  }
338  break;
339  case 1:
340  return 0;
341  }
342  } else if( v1next->param[1] > v2next->param[1] ) {
343 #ifndef NDEBUG
344  _glu_dprintf( "case b\n" );
345 #endif
346  assert( v1->param[1] <= v2next->param[1] );
347  assert( v2->param[1] <= v2next->param[1] );
348  switch( bbox( v1, v1next, v2next, 0 ) ) {
349  case -1:
350  return 0;
351  case 0:
352  sgn = ccw( v1next, v1, v2next );
353  if( sgn != -1 ) {
354  return sgn;
355  } else {
356 #ifdef DEBUG
357  _glu_dprintf( "incr\n" );
358 #endif
359  v2 = v2next++;
360  if( v2 == v2last ) {
361 #ifdef DEBUG
362  _glu_dprintf( "no good results\n" );
363 #endif
364  return 0; // ill-conditioned, guess answer
365  }
366  }
367  break;
368  case 1:
369  return 1;
370  }
371  } else {
372 #ifdef DEBUG
373  _glu_dprintf( "case ab\n" );
374 #endif
375  if( v1next->param[0] < v2next->param[0] )
376  return 1;
377  else if( v1next->param[0] > v2next->param[0] )
378  return 0;
379  else {
380 #ifdef DEBUG
381  _glu_dprintf( "incr\n" );
382 #endif
383  v2 = v2next++;
384  if( v2 == v2last ) {
385 #ifdef DEBUG
386  _glu_dprintf( "no good results\n" );
387 #endif
388  return 0; // ill-conditioned, guess answer
389  }
390  }
391  }
392  }
393 }
394 
395 int
396 Subdivider::ccwTurn_tl( Arc_ptr j1, Arc_ptr j2 )
397 {
398  register TrimVertex *v1 = &j1->pwlArc->pts[j1->pwlArc->npts-1];
399  register TrimVertex *v1last = &j1->pwlArc->pts[0];
400  register TrimVertex *v2 = &j2->pwlArc->pts[0];
401  register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
402  register TrimVertex *v1next = v1-1;
403  register TrimVertex *v2next = v2+1;
404  int sgn;
405 
406  assert( v1 != v1last );
407  assert( v2 != v2last );
408 
409 #ifndef NDEBUG
410  _glu_dprintf( "arc_ccw_turn, p = %d\n", 1 );
411 #endif
412 
413  // the arcs lie on the line (1 == v1->param[1])
414  if( v1->param[1] == v1next->param[1] && v2->param[1] == v2next->param[1] )
415  return 0;
416 
417  if( v2next->param[1] > v2->param[1] || v1next->param[1] > v1->param[1] )
418  ::mylongjmp( jumpbuffer, 28 );
419 
420  if( v1->param[0] < v2->param[0] )
421  return 0;
422  else if( v1->param[0] > v2->param[0] )
423  return 1;
424 
425  while( 1 ) {
426  if( v1next->param[1] > v2next->param[1] ) {
427 #ifndef NDEBUG
428  _glu_dprintf( "case c\n" );
429 #endif
430  assert( v1->param[1] >= v1next->param[1] );
431  assert( v2->param[1] >= v1next->param[1] );
432  switch( bbox( v2next, v2, v1next, 0 ) ) {
433  case -1:
434  return 0;
435  case 0:
436  sgn = ccw( v1next, v2, v2next );
437  if( sgn != -1 )
438  return sgn;
439  else {
440  v1 = v1next--;
441 #ifdef DEBUG
442  _glu_dprintf( "decr\n" );
443 #endif
444  if( v1 == v1last ) {
445 #ifdef DEBUG
446  _glu_dprintf( "no good results\n" );
447 #endif
448  return 0; // ill-conditioned, guess answer
449  }
450  }
451  break;
452  case 1:
453  return 1;
454  }
455  } else if( v1next->param[1] < v2next->param[1] ) {
456 #ifndef NDEBUG
457  _glu_dprintf( "case d\n" );
458  assert( v1->param[1] >= v2next->param[1] );
459  assert( v2->param[1] >= v2next->param[1] );
460 #endif
461  switch( bbox( v1next, v1, v2next, 0 ) ) {
462  case -1:
463  return 1;
464  case 0:
465  sgn = ccw( v1next, v1, v2next );
466  if( sgn != -1 )
467  return sgn;
468  else {
469  v2 = v2next++;
470 #ifdef DEBUG
471  _glu_dprintf( "incr\n" );
472 #endif
473  if( v2 == v2last ) {
474 #ifdef DEBUG
475  _glu_dprintf( "no good results\n" );
476 #endif
477  return 0; // ill-conditioned, guess answer
478  }
479  }
480  break;
481  case 1:
482  return 0;
483  }
484  } else {
485 #ifdef DEBUG
486  _glu_dprintf( "case cd\n" );
487 #endif
488  if( v1next->param[0] < v2next->param[0] )
489  return 0;
490  else if( v1next->param[0] > v2next->param[0] )
491  return 1;
492  else {
493  v2 = v2next++;
494 #ifdef DEBUG
495  _glu_dprintf( "incr\n" );
496 #endif
497  if( v2 == v2last ) {
498 #ifdef DEBUG
499  _glu_dprintf( "no good results\n" );
500 #endif
501  return 0; // ill-conditioned, guess answer
502  }
503  }
504  }
505  }
506 }
507 
508 
509 #ifndef NDEBUG
510 int
511 Subdivider::bbox( register REAL sa, register REAL sb, register REAL sc,
512  register REAL ta, register REAL tb, register REAL tc )
513 #else
514 int
515 Subdivider::bbox( register REAL sa, register REAL sb, register REAL sc,
516  register REAL , register REAL , register REAL )
517 #endif
518 {
519 #ifndef NDEBUG
520  assert( tc >= ta );
521  assert( tc <= tb );
522 #endif
523 
524  if( sa < sb ) {
525  if( sc <= sa ) {
526  return -1;
527  } else if( sb <= sc ) {
528  return 1;
529  } else {
530  return 0;
531  }
532  } else if( sa > sb ) {
533  if( sc >= sa ) {
534  return 1;
535  } else if( sb >= sc ) {
536  return -1;
537  } else {
538  return 0;
539  }
540  } else {
541  if( sc > sa ) {
542  return 1;
543  } else if( sb > sc ) {
544  return -1;
545  } else {
546  return 0;
547  }
548  }
549 }
550 
551 /*----------------------------------------------------------------------------
552  * ccw - determine how three points are oriented by computing their
553  * determinant.
554  * Return 1 if the vertices are ccw oriented,
555  * 0 if they are cw oriented, or
556  * -1 if the computation is ill-conditioned.
557  *----------------------------------------------------------------------------
558  */
559 int
560 Subdivider::ccw( TrimVertex *a, TrimVertex *b, TrimVertex *c )
561 {
562  REAL d = det3( a, b, c );
563  if( glu_abs(d) < 0.0001 ) return -1;
564  return (d < 0.0) ? 0 : 1;
565 }