Synchronize with trunk's revision r57629.
[reactos.git] / dll / opengl / glu32 / src / libnurbs / internals / 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 }