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     TrimVertex *v1	= &j1->pwlArc->pts[j1->pwlArc->npts-1];
60     TrimVertex *v1last	= &j1->pwlArc->pts[0];
61     TrimVertex *v2	= &j2->pwlArc->pts[0];
62     TrimVertex *v2last	= &j2->pwlArc->pts[j2->pwlArc->npts-1];
63     TrimVertex *v1next	= v1-1;
64     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     TrimVertex *v1	= &j1->pwlArc->pts[j1->pwlArc->npts-1];
173     TrimVertex *v1last	= &j1->pwlArc->pts[0];
174     TrimVertex *v2	= &j2->pwlArc->pts[0];
175     TrimVertex *v2last	= &j2->pwlArc->pts[j2->pwlArc->npts-1];
176     TrimVertex *v1next	= v1-1;
177     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     TrimVertex *v1	= &j1->pwlArc->pts[j1->pwlArc->npts-1];
286     TrimVertex *v1last	= &j1->pwlArc->pts[0];
287     TrimVertex *v2	= &j2->pwlArc->pts[0];
288     TrimVertex *v2last	= &j2->pwlArc->pts[j2->pwlArc->npts-1];
289     TrimVertex *v1next	= v1-1;
290     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     TrimVertex *v1	= &j1->pwlArc->pts[j1->pwlArc->npts-1];
399     TrimVertex *v1last	= &j1->pwlArc->pts[0];
400     TrimVertex *v2	= &j2->pwlArc->pts[0];
401     TrimVertex *v2last	= &j2->pwlArc->pts[j2->pwlArc->npts-1];
402     TrimVertex *v1next	= v1-1;
403     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( REAL sa, REAL sb, REAL sc, REAL ta, REAL tb, REAL tc )
512 #else
513 int
514 Subdivider::bbox( REAL sa, REAL sb, REAL sc, REAL   , REAL   , REAL    )
515 #endif
516 {
517 #ifndef NDEBUG
518     assert( tc >= ta );
519     assert( tc <= tb );
520 #endif
521 
522     if( sa < sb ) {
523 	if( sc <= sa ) {
524 	    return -1;
525 	} else if( sb <= sc ) {
526 	    return 1;
527 	} else {
528 	    return 0;
529 	}
530     } else if( sa > sb ) {
531 	if( sc >= sa ) {
532 	    return 1;
533 	} else if( sb >= sc ) {
534 	    return -1;
535 	} else {
536 	    return 0;
537 	}
538     } else {
539 	if( sc > sa ) {
540 	    return 1;
541 	} else if( sb > sc ) {
542 	    return -1;
543 	} else {
544 	    return 0;
545 	}
546     }
547 }
548 
549 /*----------------------------------------------------------------------------
550  * ccw - determine how three points are oriented by computing their
551  *	 determinant.
552  *	 Return 1 if the vertices are ccw oriented,
553  *		0 if they are cw oriented, or
554  *		-1 if the computation is ill-conditioned.
555  *----------------------------------------------------------------------------
556  */
557 int
558 Subdivider::ccw( TrimVertex *a, TrimVertex *b, TrimVertex *c )
559 {
560     REAL d = det3( a, b, c );
561     if( glu_abs(d) < 0.0001 ) return -1;
562     return (d < 0.0) ? 0 : 1;
563 }
564