Debian Codegraph @

lib/database/src/so/nodes/nurbs/libnurbs/ccw.c++

raw
1 /*
2 *
3 * Copyright (C) 2000 Silicon Graphics, Inc. All Rights Reserved.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * Further, this software is distributed without any warranty that it is
16 * free of the rightful claim of any third person regarding infringement
17 * or the like. Any license provided herein, whether implied or
18 * otherwise, applies only to this software file. Patent licenses, if
19 * any, provided herein do not apply to combinations of this program with
20 * other software, or any other product whatsoever.
21 *
22 * You should have received a copy of the GNU Lesser General Public
23 * License along with this library; if not, write to the Free Software
24 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
25 *
26 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
27 * Mountain View, CA 94043, or:
28 *
29 * http://www.sgi.com
30 *
31 * For further information regarding this notice, see:
32 *
33 * http://oss.sgi.com/projects/GenInfo/NoticeExplan/
34 *
35 */
36
37 /*
38 * ccw.c++ - $Revision: 1.1.1.1 $
39 * Derrick Burns - 1991
40 */
41
42 #include "glimports.h"
43 #include "mystdio.h"
44 #include "myassert.h"
45 #include "subdivider.h"
46 #include "types.h"
47 #include "arc.h"
48 #include "trimvertex.h"
49 #include "simplemath.h"
50
51 inline int
52 Subdivider::bbox( TrimVertex *a, TrimVertex *b, TrimVertex *c, int p )
53 {
54 return bbox( a->param[p], b->param[p], c->param[p],
55 a->param[1-p], b->param[1-p], c->param[1-p] );
56 }
57
58 int
59 Subdivider::ccwTurn_sr( Arc_ptr j1, Arc_ptr j2 ) // dir = 1
60 {
61 register TrimVertex *v1 = &j1->pwlArc->pts[j1->pwlArc->npts-1];
62 register TrimVertex *v1last = &j1->pwlArc->pts[0];
63 register TrimVertex *v2 = &j2->pwlArc->pts[0];
64 register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
65 register TrimVertex *v1next = v1-1;
66 register TrimVertex *v2next = v2+1;
67 int sgn;
68
69 assert( v1 != v1last );
70 assert( v2 != v2last );
71
72 #ifndef NDEBUG
73 dprintf( "arc_ccw_turn, p = %d\n", 0 );
74 #endif
75
76 // the arcs lie on the line (0 == v1->param[0])
77 if( v1->param[0] == v1next->param[0] && v2->param[0] == v2next->param[0] )
78 return 0;
79
80 if( v2next->param[0] < v2->param[0] || v1next->param[0] < v1->param[0] )
81 ::mylongjmp( jumpbuffer, 28 );
82
83 if( v1->param[1] < v2->param[1] )
84 return 0;
85 else if( v1->param[1] > v2->param[1] )
86 return 1;
87
88 while( 1 ) {
89 if( v1next->param[0] < v2next->param[0] ) {
90 #ifndef NDEBUG
91 dprintf( "case a\n" );
92 #endif
93 assert( v1->param[0] <= v1next->param[0] );
94 assert( v2->param[0] <= v1next->param[0] );
95 switch( bbox( v2, v2next, v1next, 1 ) ) {
96 case -1:
97 return 0;
98 case 0:
99 sgn = ccw( v1next, v2, v2next );
100 if( sgn != -1 ) {
101 return sgn;
102 } else {
103 dprintf( "decr\n" );
104 v1 = v1next--;
105 if( v1 == v1last ) {
106 dprintf( "no good results\n" );
107 return 0; // ill-conditioned, guess answer
108 }
109 }
110 break;
111 case 1:
112 return 1;
113 }
114 } else if( v1next->param[0] > v2next->param[0] ) {
115 #ifndef NDEBUG
116 dprintf( "case b\n" );
117 #endif
118 assert( v1->param[0] <= v2next->param[0] );
119 assert( v2->param[0] <= v2next->param[0] );
120 switch( bbox( v1, v1next, v2next, 1 ) ) {
121 case -1:
122 return 1;
123 case 0:
124 sgn = ccw( v1next, v1, v2next );
125 if( sgn != -1 ) {
126 return sgn;
127 } else {
128 dprintf( "incr\n" );
129 v2 = v2next++;
130 if( v2 == v2last ) {
131 dprintf( "no good results\n" );
132 return 0; // ill-conditioned, guess answer
133 }
134 }
135 break;
136 case 1:
137 return 0;
138 }
139 } else {
140 #ifndef NDEBUG
141 dprintf( "case ab\n" );
142 #endif
143 if( v1next->param[1] < v2next->param[1] )
144 return 0;
145 else if( v1next->param[1] > v2next->param[1] )
146 return 1;
147 else {
148 dprintf( "incr\n" );
149 v2 = v2next++;
150 if( v2 == v2last ) {
151 dprintf( "no good results\n" );
152 return 0; // ill-conditioned, guess answer
153 }
154 }
155 }
156 }
157 }
158
159 int
160 Subdivider::ccwTurn_sl( Arc_ptr j1, Arc_ptr j2 ) // dir = 0
161 {
162 register TrimVertex *v1 = &j1->pwlArc->pts[j1->pwlArc->npts-1];
163 register TrimVertex *v1last = &j1->pwlArc->pts[0];
164 register TrimVertex *v2 = &j2->pwlArc->pts[0];
165 register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
166 register TrimVertex *v1next = v1-1;
167 register TrimVertex *v2next = v2+1;
168 int sgn;
169
170 assert( v1 != v1last );
171 assert( v2 != v2last );
172
173 #ifndef NDEBUG
174 dprintf( "arc_ccw_turn, p = %d\n", 0 );
175 #endif
176
177 // the arcs lie on the line (0 == v1->param[0])
178 if( v1->param[0] == v1next->param[0] && v2->param[0] == v2next->param[0] )
179 return 0;
180
181 if( v2next->param[0] > v2->param[0] || v1next->param[0] > v1->param[0] )
182 ::mylongjmp( jumpbuffer, 28 );
183
184 if( v1->param[1] < v2->param[1] )
185 return 1;
186 else if( v1->param[1] > v2->param[1] )
187 return 0;
188
189 while( 1 ) {
190 if( v1next->param[0] > v2next->param[0] ) {
191 #ifndef NDEBUG
192 dprintf( "case c\n" );
193 #endif
194 assert( v1->param[0] >= v1next->param[0] );
195 assert( v2->param[0] >= v1next->param[0] );
196 switch( bbox( v2next, v2, v1next, 1 ) ) {
197 case -1:
198 return 1;
199 case 0:
200 sgn = ccw( v1next, v2, v2next );
201 if( sgn != -1 )
202 return sgn;
203 else {
204 v1 = v1next--;
205 dprintf( "decr\n" );
206 if( v1 == v1last ) {
207 dprintf( "no good results\n" );
208 return 0; // ill-conditioned, guess answer
209 }
210 }
211 break;
212 case 1:
213 return 0;
214 }
215 } else if( v1next->param[0] < v2next->param[0] ) {
216 #ifndef NDEBUG
217 dprintf( "case d\n" );
218 #endif
219 assert( v1->param[0] >= v2next->param[0] );
220 assert( v2->param[0] >= v2next->param[0] );
221 switch( bbox( v1next, v1, v2next, 1 ) ) {
222 case -1:
223 return 0;
224 case 0:
225 sgn = ccw( v1next, v1, v2next );
226 if( sgn != -1 )
227 return sgn;
228 else {
229 v2 = v2next++;
230 dprintf( "incr\n" );
231 if( v2 == v2last ) {
232 dprintf( "no good results\n" );
233 return 0; // ill-conditioned, guess answer
234 }
235 }
236 break;
237 case 1:
238 return 1;
239 }
240 } else {
241 dprintf( "case cd\n" );
242 if( v1next->param[1] < v2next->param[1] )
243 return 1;
244 else if( v1next->param[1] > v2next->param[1] )
245 return 0;
246 else {
247 v2 = v2next++;
248 dprintf( "incr\n" );
249 if( v2 == v2last ) {
250 dprintf( "no good results\n" );
251 return 0; // ill-conditioned, guess answer
252 }
253 }
254 }
255 }
256 }
257
258 int
259 Subdivider::ccwTurn_tr( Arc_ptr j1, Arc_ptr j2 ) // dir = 1
260 {
261 register TrimVertex *v1 = &j1->pwlArc->pts[j1->pwlArc->npts-1];
262 register TrimVertex *v1last = &j1->pwlArc->pts[0];
263 register TrimVertex *v2 = &j2->pwlArc->pts[0];
264 register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
265 register TrimVertex *v1next = v1-1;
266 register TrimVertex *v2next = v2+1;
267 int sgn;
268
269 assert( v1 != v1last );
270 assert( v2 != v2last );
271
272 #ifndef NDEBUG
273 dprintf( "arc_ccw_turn, p = %d\n", 1 );
274 #endif
275
276 // the arcs lie on the line (1 == v1->param[1])
277 if( v1->param[1] == v1next->param[1] && v2->param[1] == v2next->param[1] )
278 return 0;
279
280 if( v2next->param[1] < v2->param[1] || v1next->param[1] < v1->param[1] )
281 ::mylongjmp( jumpbuffer, 28 );
282
283 if( v1->param[0] < v2->param[0] )
284 return 1;
285 else if( v1->param[0] > v2->param[0] )
286 return 0;
287
288 while( 1 ) {
289 if( v1next->param[1] < v2next->param[1] ) {
290 #ifndef NDEBUG
291 dprintf( "case a\n" );
292 #endif
293 assert( v1->param[1] <= v1next->param[1] );
294 assert( v2->param[1] <= v1next->param[1] );
295 switch( bbox( v2, v2next, v1next, 0 ) ) {
296 case -1:
297 return 1;
298 case 0:
299 sgn = ccw( v1next, v2, v2next );
300 if( sgn != -1 ) {
301 return sgn;
302 } else {
303 dprintf( "decr\n" );
304 v1 = v1next--;
305 if( v1 == v1last ) {
306 dprintf( "no good results\n" );
307 return 0; // ill-conditioned, guess answer
308 }
309 }
310 break;
311 case 1:
312 return 0;
313 }
314 } else if( v1next->param[1] > v2next->param[1] ) {
315 #ifndef NDEBUG
316 dprintf( "case b\n" );
317 #endif
318 assert( v1->param[1] <= v2next->param[1] );
319 assert( v2->param[1] <= v2next->param[1] );
320 switch( bbox( v1, v1next, v2next, 0 ) ) {
321 case -1:
322 return 0;
323 case 0:
324 sgn = ccw( v1next, v1, v2next );
325 if( sgn != -1 ) {
326 return sgn;
327 } else {
328 dprintf( "incr\n" );
329 v2 = v2next++;
330 if( v2 == v2last ) {
331 dprintf( "no good results\n" );
332 return 0; // ill-conditioned, guess answer
333 }
334 }
335 break;
336 case 1:
337 return 1;
338 }
339 } else {
340 dprintf( "case ab\n" );
341 if( v1next->param[0] < v2next->param[0] )
342 return 1;
343 else if( v1next->param[0] > v2next->param[0] )
344 return 0;
345 else {
346 dprintf( "incr\n" );
347 v2 = v2next++;
348 if( v2 == v2last ) {
349 dprintf( "no good results\n" );
350 return 0; // ill-conditioned, guess answer
351 }
352 }
353 }
354 }
355 }
356
357 int
358 Subdivider::ccwTurn_tl( Arc_ptr j1, Arc_ptr j2 )
359 {
360 register TrimVertex *v1 = &j1->pwlArc->pts[j1->pwlArc->npts-1];
361 register TrimVertex *v1last = &j1->pwlArc->pts[0];
362 register TrimVertex *v2 = &j2->pwlArc->pts[0];
363 register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
364 register TrimVertex *v1next = v1-1;
365 register TrimVertex *v2next = v2+1;
366 int sgn;
367
368 assert( v1 != v1last );
369 assert( v2 != v2last );
370
371 #ifndef NDEBUG
372 dprintf( "arc_ccw_turn, p = %d\n", 1 );
373 #endif
374
375 // the arcs lie on the line (1 == v1->param[1])
376 if( v1->param[1] == v1next->param[1] && v2->param[1] == v2next->param[1] )
377 return 0;
378
379 if( v2next->param[1] > v2->param[1] || v1next->param[1] > v1->param[1] )
380 ::mylongjmp( jumpbuffer, 28 );
381
382 if( v1->param[0] < v2->param[0] )
383 return 0;
384 else if( v1->param[0] > v2->param[0] )
385 return 1;
386
387 while( 1 ) {
388 if( v1next->param[1] > v2next->param[1] ) {
389 #ifndef NDEBUG
390 dprintf( "case c\n" );
391 #endif
392 assert( v1->param[1] >= v1next->param[1] );
393 assert( v2->param[1] >= v1next->param[1] );
394 switch( bbox( v2next, v2, v1next, 0 ) ) {
395 case -1:
396 return 0;
397 case 0:
398 sgn = ccw( v1next, v2, v2next );
399 if( sgn != -1 )
400 return sgn;
401 else {
402 v1 = v1next--;
403 dprintf( "decr\n" );
404 if( v1 == v1last ) {
405 dprintf( "no good results\n" );
406 return 0; // ill-conditioned, guess answer
407 }
408 }
409 break;
410 case 1:
411 return 1;
412 }
413 } else if( v1next->param[1] < v2next->param[1] ) {
414 #ifndef NDEBUG
415 dprintf( "case d\n" );
416 assert( v1->param[1] >= v2next->param[1] );
417 assert( v2->param[1] >= v2next->param[1] );
418 #endif
419 switch( bbox( v1next, v1, v2next, 0 ) ) {
420 case -1:
421 return 1;
422 case 0:
423 sgn = ccw( v1next, v1, v2next );
424 if( sgn != -1 )
425 return sgn;
426 else {
427 v2 = v2next++;
428 dprintf( "incr\n" );
429 if( v2 == v2last ) {
430 dprintf( "no good results\n" );
431 return 0; // ill-conditioned, guess answer
432 }
433 }
434 break;
435 case 1:
436 return 0;
437 }
438 } else {
439 dprintf( "case cd\n" );
440 if( v1next->param[0] < v2next->param[0] )
441 return 0;
442 else if( v1next->param[0] > v2next->param[0] )
443 return 1;
444 else {
445 v2 = v2next++;
446 dprintf( "incr\n" );
447 if( v2 == v2last ) {
448 dprintf( "no good results\n" );
449 return 0; // ill-conditioned, guess answer
450 }
451 }
452 }
453 }
454 }
455
456
457 #ifndef NDEBUG
458 int
459 Subdivider::bbox( register REAL sa, register REAL sb, register REAL sc,
460 register REAL ta, register REAL tb, register REAL tc )
461 #else
462 int
463 Subdivider::bbox( register REAL sa, register REAL sb, register REAL sc,
464 register REAL , register REAL , register REAL )
465 #endif
466 {
467 #ifndef NDEBUG
468 assert( tc >= ta );
469 assert( tc <= tb );
470 #endif
471
472 if( sa < sb ) {
473 if( sc <= sa ) {
474 return -1;
475 } else if( sb <= sc ) {
476 return 1;
477 } else {
478 return 0;
479 }
480 } else if( sa > sb ) {
481 if( sc >= sa ) {
482 return 1;
483 } else if( sb >= sc ) {
484 return -1;
485 } else {
486 return 0;
487 }
488 } else {
489 if( sc > sa ) {
490 return 1;
491 } else if( sb > sc ) {
492 return -1;
493 } else {
494 return 0;
495 }
496 }
497 }
498
499 /*----------------------------------------------------------------------------
500 * ccw - determine how three points are oriented by computing their
501 * determinant.
502 * Return 1 if the vertices are ccw oriented,
503 * 0 if they are cw oriented, or
504 * -1 if the computation is ill-conditioned.
505 *----------------------------------------------------------------------------
506 */
507 int
508 Subdivider::ccw( TrimVertex *a, TrimVertex *b, TrimVertex *c )
509 {
510 REAL d = det3( a, b, c );
511 if( abs(d) < 0.0001 ) return -1;
512 return (d < 0.0) ? 0 : 1;
513 }