ccw.cc revision e7980a23 
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
49inline int
50Subdivider::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
56int
57Subdivider::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
169int
170Subdivider::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
282int
283Subdivider::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
395int
396Subdivider::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
510int
511Subdivider::bbox( REAL sa, REAL sb, REAL sc, REAL ta, REAL tb, REAL tc )
512#else
513int
514Subdivider::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 */
557int
558Subdivider::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