source: trunk/src/opengl/glu/nurbs/internals/ccw.cpp

Last change on this file was 2689, checked in by jeroen, 26 years ago

* empty log message *
File size: 13.7 KB
Line 
1/* $Id: ccw.cpp,v 1.1 2000-02-09 08:50:21 jeroen Exp $ */
2/*
3** License Applicability. Except to the extent portions of this file are
4** made subject to an alternative license as permitted in the SGI Free
5** Software License B, Version 1.0 (the "License"), the contents of this
6** file are subject only to the provisions of the License. You may not use
7** this file except in compliance with the License. You may obtain a copy
8** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
9** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
10**
11** http://oss.sgi.com/projects/FreeB
12**
13** Note that, as provided in the License, the Software is distributed on an
14** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
15** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
16** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
17** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
18**
19** Original Code. The Original Code is: OpenGL Sample Implementation,
20** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
21** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
22** Copyright in any portions created by third parties is as indicated
23** elsewhere herein. All Rights Reserved.
24**
25** Additional Notice Provisions: The application programming interfaces
26** established by SGI in conjunction with the Original Code are The
27** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
28** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
29** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
30** Window System(R) (Version 1.3), released October 19, 1998. This software
31** was created using the OpenGL(R) version 1.2.1 Sample Implementation
32** published by SGI, but has not been independently verified as being
33** compliant with the OpenGL(R) version 1.2.1 Specification.
34*/
35
36/*
37 * ccw.c++
38 *
39 * $Date: 2000-02-09 08:50:21 $ $Revision: 1.1 $
40 * $Header: /home/ktk/tmp/odin/2007/netlabs.cvs/odin32/src/opengl/glu/nurbs/internals/ccw.cpp,v 1.1 2000-02-09 08:50:21 jeroen Exp $
41 */
42
43#include <stdlib.h>
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#include "mysetjmp.h"
53
54inline int
55Subdivider::bbox( TrimVertex *a, TrimVertex *b, TrimVertex *c, int p )
56{
57 return bbox( a->param[p], b->param[p], c->param[p],
58 a->param[1-p], b->param[1-p], c->param[1-p] );
59}
60
61int
62Subdivider::ccwTurn_sr( Arc_ptr j1, Arc_ptr j2 ) // dir = 1
63{
64 register TrimVertex *v1 = &j1->pwlArc->pts[j1->pwlArc->npts-1];
65 register TrimVertex *v1last = &j1->pwlArc->pts[0];
66 register TrimVertex *v2 = &j2->pwlArc->pts[0];
67 register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
68 register TrimVertex *v1next = v1-1;
69 register TrimVertex *v2next = v2+1;
70 int sgn;
71
72 assert( v1 != v1last );
73 assert( v2 != v2last );
74
75#ifndef NDEBUG
76 dprintf( "arc_ccw_turn, p = %d\n", 0 );
77#endif
78
79 // the arcs lie on the line (0 == v1->param[0])
80 if( v1->param[0] == v1next->param[0] && v2->param[0] == v2next->param[0] )
81 return 0;
82
83 if( v2next->param[0] < v2->param[0] || v1next->param[0] < v1->param[0] )
84 ::mylongjmp( jumpbuffer, 28 );
85
86 if( v1->param[1] < v2->param[1] )
87 return 0;
88 else if( v1->param[1] > v2->param[1] )
89 return 1;
90
91 while( 1 ) {
92 if( v1next->param[0] < v2next->param[0] ) {
93#ifndef NDEBUG
94 dprintf( "case a\n" );
95#endif
96 assert( v1->param[0] <= v1next->param[0] );
97 assert( v2->param[0] <= v1next->param[0] );
98 switch( bbox( v2, v2next, v1next, 1 ) ) {
99 case -1:
100 return 0;
101 case 0:
102 sgn = ccw( v1next, v2, v2next );
103 if( sgn != -1 ) {
104 return sgn;
105 } else {
106#ifdef DEBUG
107 dprintf( "decr\n" );
108#endif
109 v1 = v1next--;
110 if( v1 == v1last ) {
111#ifdef DEBUG
112 dprintf( "no good results\n" );
113#endif
114 return 0; // ill-conditioned, guess answer
115 }
116 }
117 break;
118 case 1:
119 return 1;
120 }
121 } else if( v1next->param[0] > v2next->param[0] ) {
122#ifndef NDEBUG
123 dprintf( "case b\n" );
124#endif
125 assert( v1->param[0] <= v2next->param[0] );
126 assert( v2->param[0] <= v2next->param[0] );
127 switch( bbox( v1, v1next, v2next, 1 ) ) {
128 case -1:
129 return 1;
130 case 0:
131 sgn = ccw( v1next, v1, v2next );
132 if( sgn != -1 ) {
133 return sgn;
134 } else {
135#ifdef DEBUG
136 dprintf( "incr\n" );
137#endif
138 v2 = v2next++;
139 if( v2 == v2last ) {
140#ifdef DEBUG
141 dprintf( "no good results\n" );
142#endif
143 return 0; // ill-conditioned, guess answer
144 }
145 }
146 break;
147 case 1:
148 return 0;
149 }
150 } else {
151#ifndef NDEBUG
152 dprintf( "case ab\n" );
153#endif
154 if( v1next->param[1] < v2next->param[1] )
155 return 0;
156 else if( v1next->param[1] > v2next->param[1] )
157 return 1;
158 else {
159#ifdef DEBUG
160 dprintf( "incr\n" );
161#endif
162 v2 = v2next++;
163 if( v2 == v2last ) {
164#ifdef DEBUG
165 dprintf( "no good results\n" );
166#endif
167 return 0; // ill-conditioned, guess answer
168 }
169 }
170 }
171 }
172}
173
174int
175Subdivider::ccwTurn_sl( Arc_ptr j1, Arc_ptr j2 ) // dir = 0
176{
177 register TrimVertex *v1 = &j1->pwlArc->pts[j1->pwlArc->npts-1];
178 register TrimVertex *v1last = &j1->pwlArc->pts[0];
179 register TrimVertex *v2 = &j2->pwlArc->pts[0];
180 register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
181 register TrimVertex *v1next = v1-1;
182 register TrimVertex *v2next = v2+1;
183 int sgn;
184
185 assert( v1 != v1last );
186 assert( v2 != v2last );
187
188#ifndef NDEBUG
189 dprintf( "arc_ccw_turn, p = %d\n", 0 );
190#endif
191
192 // the arcs lie on the line (0 == v1->param[0])
193 if( v1->param[0] == v1next->param[0] && v2->param[0] == v2next->param[0] )
194 return 0;
195
196 if( v2next->param[0] > v2->param[0] || v1next->param[0] > v1->param[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 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 dprintf( "decr\n" );
222#endif
223 if( v1 == v1last ) {
224#ifdef DEBUG
225 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 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 dprintf( "incr\n" );
251#endif
252 if( v2 == v2last ) {
253#ifdef DEBUG
254 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 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 dprintf( "incr\n" );
275#endif
276 if( v2 == v2last ) {
277#ifdef DEBUG
278 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 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 ::mylongjmp( jumpbuffer, 28 );
311
312 if( v1->param[0] < v2->param[0] )
313 return 1;
314 else if( v1->param[0] > v2->param[0] )
315 return 0;
316
317 while( 1 ) {
318 if( v1next->param[1] < v2next->param[1] ) {
319#ifndef NDEBUG
320 dprintf( "case a\n" );
321#endif
322 assert( v1->param[1] <= v1next->param[1] );
323 assert( v2->param[1] <= v1next->param[1] );
324 switch( bbox( v2, v2next, v1next, 0 ) ) {
325 case -1:
326 return 1;
327 case 0:
328 sgn = ccw( v1next, v2, v2next );
329 if( sgn != -1 ) {
330 return sgn;
331 } else {
332#ifdef DEBUG
333 dprintf( "decr\n" );
334#endif
335 v1 = v1next--;
336 if( v1 == v1last ) {
337#ifdef DEBUG
338 dprintf( "no good results\n" );
339#endif
340 return 0; // ill-conditioned, guess answer
341 }
342 }
343 break;
344 case 1:
345 return 0;
346 }
347 } else if( v1next->param[1] > v2next->param[1] ) {
348#ifndef NDEBUG
349 dprintf( "case b\n" );
350#endif
351 assert( v1->param[1] <= v2next->param[1] );
352 assert( v2->param[1] <= v2next->param[1] );
353 switch( bbox( v1, v1next, v2next, 0 ) ) {
354 case -1:
355 return 0;
356 case 0:
357 sgn = ccw( v1next, v1, v2next );
358 if( sgn != -1 ) {
359 return sgn;
360 } else {
361#ifdef DEBUG
362 dprintf( "incr\n" );
363#endif
364 v2 = v2next++;
365 if( v2 == v2last ) {
366#ifdef DEBUG
367 dprintf( "no good results\n" );
368#endif
369 return 0; // ill-conditioned, guess answer
370 }
371 }
372 break;
373 case 1:
374 return 1;
375 }
376 } else {
377#ifdef DEBUG
378 dprintf( "case ab\n" );
379#endif
380 if( v1next->param[0] < v2next->param[0] )
381 return 1;
382 else if( v1next->param[0] > v2next->param[0] )
383 return 0;
384 else {
385#ifdef DEBUG
386 dprintf( "incr\n" );
387#endif
388 v2 = v2next++;
389 if( v2 == v2last ) {
390#ifdef DEBUG
391 dprintf( "no good results\n" );
392#endif
393 return 0; // ill-conditioned, guess answer
394 }
395 }
396 }
397 }
398}
399
400int
401Subdivider::ccwTurn_tl( Arc_ptr j1, Arc_ptr j2 )
402{
403 register TrimVertex *v1 = &j1->pwlArc->pts[j1->pwlArc->npts-1];
404 register TrimVertex *v1last = &j1->pwlArc->pts[0];
405 register TrimVertex *v2 = &j2->pwlArc->pts[0];
406 register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
407 register TrimVertex *v1next = v1-1;
408 register TrimVertex *v2next = v2+1;
409 int sgn;
410
411 assert( v1 != v1last );
412 assert( v2 != v2last );
413
414#ifndef NDEBUG
415 dprintf( "arc_ccw_turn, p = %d\n", 1 );
416#endif
417
418 // the arcs lie on the line (1 == v1->param[1])
419 if( v1->param[1] == v1next->param[1] && v2->param[1] == v2next->param[1] )
420 return 0;
421
422 if( v2next->param[1] > v2->param[1] || v1next->param[1] > v1->param[1] )
423 ::mylongjmp( jumpbuffer, 28 );
424
425 if( v1->param[0] < v2->param[0] )
426 return 0;
427 else if( v1->param[0] > v2->param[0] )
428 return 1;
429
430 while( 1 ) {
431 if( v1next->param[1] > v2next->param[1] ) {
432#ifndef NDEBUG
433 dprintf( "case c\n" );
434#endif
435 assert( v1->param[1] >= v1next->param[1] );
436 assert( v2->param[1] >= v1next->param[1] );
437 switch( bbox( v2next, v2, v1next, 0 ) ) {
438 case -1:
439 return 0;
440 case 0:
441 sgn = ccw( v1next, v2, v2next );
442 if( sgn != -1 )
443 return sgn;
444 else {
445 v1 = v1next--;
446#ifdef DEBUG
447 dprintf( "decr\n" );
448#endif
449 if( v1 == v1last ) {
450#ifdef DEBUG
451 dprintf( "no good results\n" );
452#endif
453 return 0; // ill-conditioned, guess answer
454 }
455 }
456 break;
457 case 1:
458 return 1;
459 }
460 } else if( v1next->param[1] < v2next->param[1] ) {
461#ifndef NDEBUG
462 dprintf( "case d\n" );
463 assert( v1->param[1] >= v2next->param[1] );
464 assert( v2->param[1] >= v2next->param[1] );
465#endif
466 switch( bbox( v1next, v1, v2next, 0 ) ) {
467 case -1:
468 return 1;
469 case 0:
470 sgn = ccw( v1next, v1, v2next );
471 if( sgn != -1 )
472 return sgn;
473 else {
474 v2 = v2next++;
475#ifdef DEBUG
476 dprintf( "incr\n" );
477#endif
478 if( v2 == v2last ) {
479#ifdef DEBUG
480 dprintf( "no good results\n" );
481#endif
482 return 0; // ill-conditioned, guess answer
483 }
484 }
485 break;
486 case 1:
487 return 0;
488 }
489 } else {
490#ifdef DEBUG
491 dprintf( "case cd\n" );
492#endif
493 if( v1next->param[0] < v2next->param[0] )
494 return 0;
495 else if( v1next->param[0] > v2next->param[0] )
496 return 1;
497 else {
498 v2 = v2next++;
499#ifdef DEBUG
500 dprintf( "incr\n" );
501#endif
502 if( v2 == v2last ) {
503#ifdef DEBUG
504 dprintf( "no good results\n" );
505#endif
506 return 0; // ill-conditioned, guess answer
507 }
508 }
509 }
510 }
511}
512
513
514#ifndef NDEBUG
515int
516Subdivider::bbox( register REAL sa, register REAL sb, register REAL sc,
517 register REAL ta, register REAL tb, register REAL tc )
518#else
519int
520Subdivider::bbox( register REAL sa, register REAL sb, register REAL sc,
521 register REAL , register REAL , register REAL )
522#endif
523{
524#ifndef NDEBUG
525 assert( tc >= ta );
526 assert( tc <= tb );
527#endif
528
529 if( sa < sb ) {
530 if( sc <= sa ) {
531 return -1;
532 } else if( sb <= sc ) {
533 return 1;
534 } else {
535 return 0;
536 }
537 } else if( sa > sb ) {
538 if( sc >= sa ) {
539 return 1;
540 } else if( sb >= sc ) {
541 return -1;
542 } else {
543 return 0;
544 }
545 } else {
546 if( sc > sa ) {
547 return 1;
548 } else if( sb > sc ) {
549 return -1;
550 } else {
551 return 0;
552 }
553 }
554}
555
556/*----------------------------------------------------------------------------
557 * ccw - determine how three points are oriented by computing their
558 * determinant.
559 * Return 1 if the vertices are ccw oriented,
560 * 0 if they are cw oriented, or
561 * -1 if the computation is ill-conditioned.
562 *----------------------------------------------------------------------------
563 */
564int
565Subdivider::ccw( TrimVertex *a, TrimVertex *b, TrimVertex *c )
566{
567 REAL d = det3( a, b, c );
568 if( abs(d) < 0.0001 ) return -1;
569 return (d < 0.0) ? 0 : 1;
570}
Note: See TracBrowser for help on using the repository browser.