ReactOS 0.4.15-dev-8428-g6910fa6
ccw.cc
Go to the documentation of this file.
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
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
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
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
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
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
512#else
513int
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
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}
static struct sockaddr_in sa
Definition: adnsresfilter.c:69
static int ccw(TrimVertex *, TrimVertex *, TrimVertex *)
Definition: ccw.cc:558
int ccwTurn_sr(Arc_ptr, Arc_ptr)
Definition: ccw.cc:57
int bbox(TrimVertex *, TrimVertex *, TrimVertex *, int)
Definition: ccw.cc:50
int ccwTurn_tl(Arc_ptr, Arc_ptr)
Definition: ccw.cc:396
JumpBuffer * jumpbuffer
Definition: subdivider.h:119
int ccwTurn_sl(Arc_ptr, Arc_ptr)
Definition: ccw.cc:170
int ccwTurn_tr(Arc_ptr, Arc_ptr)
Definition: ccw.cc:283
REAL param[2]
Definition: trimvertex.h:45
class Arc * Arc_ptr
Definition: arc.h:50
float REAL
Definition: types.h:41
#define assert(x)
Definition: debug.h:53
superblock * sb
Definition: btrfs.c:4261
FT_BBox bbox
Definition: ftbbox.c:446
const GLfloat * tc
Definition: glext.h:8925
const GLubyte * c
Definition: glext.h:8905
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
GLfloat GLfloat p
Definition: glext.h:8902
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
GLfloat GLfloat v1
Definition: glext.h:6062
GLfloat GLfloat GLfloat v2
Definition: glext.h:6063
#define d
Definition: ke_i.h:81
static const WCHAR tb[]
Definition: suminfo.c:285
REAL glu_abs(REAL x)
Definition: simplemath.h:50
REAL det3(TrimVertex *a, TrimVertex *b, TrimVertex *c)
Definition: trimvertex.h:56
long sgn(REAL x)
Definition: varray.cc:48