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