ReactOS Development > Doxygen

00001 /*
00002 ** License Applicability. Except to the extent portions of this file are
00003 ** made subject to an alternative license as permitted in the SGI Free
00004 ** Software License B, Version 1.1 (the "License"), the contents of this
00005 ** file are subject only to the provisions of the License. You may not use
00006 ** this file except in compliance with the License. You may obtain a copy
00007 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
00008 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
00009 **
00010 ** http://oss.sgi.com/projects/FreeB
00011 **
00012 ** Note that, as provided in the License, the Software is distributed on an
00013 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
00014 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
00015 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
00016 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
00017 **
00018 ** Original Code. The Original Code is: OpenGL Sample Implementation,
00019 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
00020 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
00021 ** Copyright in any portions created by third parties is as indicated
00022 ** elsewhere herein. All Rights Reserved.
00023 **
00024 ** Additional Notice Provisions: The application programming interfaces
00025 ** established by SGI in conjunction with the Original Code are The
00026 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
00027 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
00028 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
00029 ** Window System(R) (Version 1.3), released October 19, 1998. This software
00030 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
00031 ** published by SGI, but has not been independently verified as being
00032 ** compliant with the OpenGL(R) version 1.2.1 Specification.
00033 */
00034 
00035 /*
00036  * ccw.c++
00037  *
00038  * $Date: 2006-03-12 00:07:02 +0000 (Sun, 12 Mar 2006) $ $Revision: 1.1 $
00039  * $Header: /cygdrive/c/RCVS/CVS/ReactOS/reactos/lib/glu32/libnurbs/internals/ccw.cc,v 1.1 2004/02/02 16:39:11 navaraf Exp $
00040  */
00041 
00042 #include "glimports.h"
00043 #include "mystdio.h"
00044 #include "myassert.h"
00045 #include "subdivider.h"
00046 #include "types.h"
00047 #include "arc.h"
00048 #include "trimvertex.h"
00049 #include "simplemath.h"
00050 
00051 inline int 
00052 Subdivider::bbox( TrimVertex *a, TrimVertex *b, TrimVertex *c, int p )
00053 {
00054     return bbox( a->param[p], b->param[p], c->param[p], 
00055              a->param[1-p], b->param[1-p], c->param[1-p] ); 
00056 }
00057 
00058 int
00059 Subdivider::ccwTurn_sr( Arc_ptr j1, Arc_ptr j2 ) // dir = 1
00060 {
00061     register TrimVertex *v1 = &j1->pwlArc->pts[j1->pwlArc->npts-1];
00062     register TrimVertex *v1last = &j1->pwlArc->pts[0];
00063     register TrimVertex *v2 = &j2->pwlArc->pts[0];
00064     register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
00065     register TrimVertex *v1next = v1-1;
00066     register TrimVertex *v2next = v2+1;
00067     int sgn;
00068 
00069     assert( v1 != v1last );
00070     assert( v2 != v2last );
00071 
00072 #ifndef NDEBUG
00073     dprintf( "arc_ccw_turn, p = %d\n", 0 );
00074 #endif
00075 
00076     // the arcs lie on the line (0 == v1->param[0])
00077     if( v1->param[0] == v1next->param[0] && v2->param[0] == v2next->param[0] )
00078     return 0;
00079 
00080     if( v2next->param[0] < v2->param[0] || v1next->param[0] < v1->param[0] )
00081     ::mylongjmp( jumpbuffer, 28 );
00082 
00083     if( v1->param[1] < v2->param[1] )
00084     return 0;
00085     else if( v1->param[1] > v2->param[1] )
00086     return 1;
00087 
00088     while( 1 ) {
00089     if( v1next->param[0] < v2next->param[0] ) {
00090 #ifndef NDEBUG
00091         dprintf( "case a\n" );
00092 #endif
00093         assert( v1->param[0] <= v1next->param[0] );
00094         assert( v2->param[0] <= v1next->param[0] );
00095         switch( bbox( v2, v2next, v1next, 1 ) ) {
00096         case -1:
00097             return 0;
00098         case 0:
00099            sgn = ccw( v1next, v2, v2next );
00100            if( sgn != -1 ) {
00101             return sgn;
00102            } else {
00103 #ifdef DEBUG
00104             dprintf( "decr\n" );
00105 #endif
00106             v1 = v1next--;
00107             if( v1 == v1last ) {
00108 #ifdef DEBUG
00109                 dprintf( "no good results\n" );
00110 #endif
00111                 return 0; // ill-conditioned, guess answer
00112             }
00113             }
00114             break;
00115         case 1:
00116             return 1;
00117         }
00118     } else if( v1next->param[0] > v2next->param[0] ) {
00119 #ifndef NDEBUG
00120         dprintf( "case b\n" );
00121 #endif
00122         assert( v1->param[0] <= v2next->param[0] );
00123         assert( v2->param[0] <= v2next->param[0] );
00124         switch( bbox( v1, v1next, v2next, 1 ) ) {
00125         case -1:
00126             return 1;
00127         case 0:
00128            sgn = ccw( v1next, v1, v2next );
00129            if( sgn != -1 ) { 
00130             return sgn;
00131            } else {
00132 #ifdef DEBUG
00133             dprintf( "incr\n" );
00134 #endif
00135             v2 = v2next++;
00136             if( v2 == v2last ) {
00137 #ifdef DEBUG
00138                 dprintf( "no good results\n" );
00139 #endif
00140                 return 0; // ill-conditioned, guess answer
00141             }
00142             }
00143             break;
00144         case 1:
00145             return 0;
00146         }
00147     } else {
00148 #ifndef NDEBUG
00149         dprintf( "case ab\n" );
00150 #endif
00151         if( v1next->param[1] < v2next->param[1] )
00152         return 0;
00153         else if( v1next->param[1] > v2next->param[1] )
00154         return 1;
00155         else {
00156 #ifdef DEBUG
00157         dprintf( "incr\n" );
00158 #endif
00159         v2 = v2next++;
00160         if( v2 == v2last ) {
00161 #ifdef DEBUG
00162             dprintf( "no good results\n" );
00163 #endif
00164             return 0; // ill-conditioned, guess answer
00165         }
00166         }
00167     }
00168     }
00169 }
00170 
00171 int
00172 Subdivider::ccwTurn_sl( Arc_ptr j1, Arc_ptr j2 ) // dir = 0
00173 {
00174     register TrimVertex *v1 = &j1->pwlArc->pts[j1->pwlArc->npts-1];
00175     register TrimVertex *v1last = &j1->pwlArc->pts[0];
00176     register TrimVertex *v2 = &j2->pwlArc->pts[0];
00177     register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
00178     register TrimVertex *v1next = v1-1;
00179     register TrimVertex *v2next = v2+1;
00180     int sgn;
00181 
00182     assert( v1 != v1last );
00183     assert( v2 != v2last );
00184 
00185 #ifndef NDEBUG
00186     dprintf( "arc_ccw_turn, p = %d\n", 0 );
00187 #endif
00188 
00189     // the arcs lie on the line (0 == v1->param[0])
00190     if( v1->param[0] == v1next->param[0] && v2->param[0] == v2next->param[0] )
00191     return 0;
00192 
00193     if( v2next->param[0] > v2->param[0] || v1next->param[0] > v1->param[0] ) 
00194     ::mylongjmp( jumpbuffer, 28 );
00195 
00196     if( v1->param[1] < v2->param[1] )
00197     return 1;
00198     else if( v1->param[1] > v2->param[1] )
00199     return 0;
00200 
00201     while( 1 ) {
00202     if( v1next->param[0] > v2next->param[0] ) {
00203 #ifndef NDEBUG
00204         dprintf( "case c\n" );
00205 #endif
00206         assert( v1->param[0] >= v1next->param[0] );
00207         assert( v2->param[0] >= v1next->param[0] );
00208         switch( bbox( v2next, v2, v1next, 1 ) ) {
00209         case -1:
00210             return 1;
00211         case 0:
00212             sgn = ccw( v1next, v2, v2next );
00213             if( sgn != -1 ) 
00214             return sgn;
00215             else {
00216             v1 = v1next--;
00217 #ifdef DEBUG
00218             dprintf( "decr\n" );
00219 #endif
00220             if( v1 == v1last ) {
00221 #ifdef DEBUG
00222                 dprintf( "no good results\n" );
00223 #endif
00224                 return 0; // ill-conditioned, guess answer
00225             }
00226             }
00227             break;
00228         case 1:
00229             return 0;
00230         }
00231     } else if( v1next->param[0] < v2next->param[0] ) {
00232 #ifndef NDEBUG
00233         dprintf( "case d\n" );
00234 #endif
00235         assert( v1->param[0] >= v2next->param[0] );
00236         assert( v2->param[0] >= v2next->param[0] );
00237         switch( bbox( v1next, v1, v2next, 1 ) ) {
00238         case -1:
00239             return 0;
00240         case 0:
00241             sgn = ccw( v1next, v1, v2next );
00242             if( sgn != -1 ) 
00243             return sgn;
00244             else {
00245             v2 = v2next++;
00246 #ifdef DEBUG
00247             dprintf( "incr\n" );
00248 #endif
00249             if( v2 == v2last ) {
00250 #ifdef DEBUG
00251                 dprintf( "no good results\n" );
00252 #endif
00253                 return 0; // ill-conditioned, guess answer
00254             }
00255             }
00256             break;
00257         case 1:
00258             return 1;
00259         }
00260     } else {
00261 #ifdef DEBUG
00262         dprintf( "case cd\n" );
00263 #endif
00264         if( v1next->param[1] < v2next->param[1] )
00265         return 1;
00266         else if( v1next->param[1] > v2next->param[1] )
00267         return 0;
00268         else {
00269         v2 = v2next++;
00270 #ifdef DEBUG
00271         dprintf( "incr\n" );
00272 #endif
00273         if( v2 == v2last ) {
00274 #ifdef DEBUG
00275             dprintf( "no good results\n" );
00276 #endif
00277             return 0; // ill-conditioned, guess answer
00278         }
00279         }
00280     }
00281     }
00282 }
00283 
00284 int
00285 Subdivider::ccwTurn_tr( Arc_ptr j1, Arc_ptr j2 ) // dir = 1
00286 {
00287     register TrimVertex *v1 = &j1->pwlArc->pts[j1->pwlArc->npts-1];
00288     register TrimVertex *v1last = &j1->pwlArc->pts[0];
00289     register TrimVertex *v2 = &j2->pwlArc->pts[0];
00290     register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
00291     register TrimVertex *v1next = v1-1;
00292     register TrimVertex *v2next = v2+1;
00293     int sgn;
00294 
00295     assert( v1 != v1last );
00296     assert( v2 != v2last );
00297 
00298 #ifndef NDEBUG
00299     dprintf( "arc_ccw_turn, p = %d\n", 1 );
00300 #endif
00301 
00302     // the arcs lie on the line (1 == v1->param[1])
00303     if( v1->param[1] == v1next->param[1] && v2->param[1] == v2next->param[1] )
00304     return 0;
00305 
00306     if( v2next->param[1] < v2->param[1] || v1next->param[1] < v1->param[1] )
00307     ::mylongjmp( jumpbuffer, 28 );
00308 
00309     if( v1->param[0] < v2->param[0] )
00310     return 1;
00311     else if( v1->param[0] > v2->param[0] )
00312     return 0;
00313 
00314     while( 1 ) {
00315     if( v1next->param[1] < v2next->param[1] ) {
00316 #ifndef NDEBUG
00317         dprintf( "case a\n" );
00318 #endif
00319         assert( v1->param[1] <= v1next->param[1] );
00320         assert( v2->param[1] <= v1next->param[1] );
00321         switch( bbox( v2, v2next, v1next, 0 ) ) {
00322         case -1:
00323             return 1;
00324         case 0:
00325            sgn = ccw( v1next, v2, v2next );
00326            if( sgn != -1 ) {
00327             return sgn;
00328            } else {
00329 #ifdef DEBUG
00330             dprintf( "decr\n" );
00331 #endif
00332             v1 = v1next--;
00333             if( v1 == v1last ) {
00334 #ifdef DEBUG
00335                 dprintf( "no good results\n" );
00336 #endif
00337                 return 0; // ill-conditioned, guess answer
00338             }
00339             }
00340             break;
00341         case 1:
00342             return 0;
00343         }
00344     } else if( v1next->param[1] > v2next->param[1] ) {
00345 #ifndef NDEBUG
00346         dprintf( "case b\n" );
00347 #endif
00348         assert( v1->param[1] <= v2next->param[1] );
00349         assert( v2->param[1] <= v2next->param[1] );
00350         switch( bbox( v1, v1next, v2next, 0 ) ) {
00351         case -1:
00352             return 0;
00353         case 0:
00354            sgn = ccw( v1next, v1, v2next );
00355            if( sgn != -1 ) { 
00356             return sgn;
00357            } else {
00358 #ifdef DEBUG
00359             dprintf( "incr\n" );
00360 #endif
00361             v2 = v2next++;
00362             if( v2 == v2last ) {
00363 #ifdef DEBUG
00364                 dprintf( "no good results\n" );
00365 #endif
00366                 return 0; // ill-conditioned, guess answer
00367             }
00368             }
00369             break;
00370         case 1:
00371             return 1;
00372         }
00373     } else {
00374 #ifdef DEBUG
00375         dprintf( "case ab\n" );
00376 #endif
00377         if( v1next->param[0] < v2next->param[0] )
00378         return 1;
00379         else if( v1next->param[0] > v2next->param[0] )
00380         return 0;
00381         else {
00382 #ifdef DEBUG
00383         dprintf( "incr\n" );
00384 #endif
00385         v2 = v2next++;
00386         if( v2 == v2last ) {
00387 #ifdef DEBUG
00388             dprintf( "no good results\n" );
00389 #endif
00390             return 0; // ill-conditioned, guess answer
00391         }
00392         }
00393     }
00394     }
00395 }
00396 
00397 int
00398 Subdivider::ccwTurn_tl( Arc_ptr j1, Arc_ptr j2 )
00399 {
00400     register TrimVertex *v1 = &j1->pwlArc->pts[j1->pwlArc->npts-1];
00401     register TrimVertex *v1last = &j1->pwlArc->pts[0];
00402     register TrimVertex *v2 = &j2->pwlArc->pts[0];
00403     register TrimVertex *v2last = &j2->pwlArc->pts[j2->pwlArc->npts-1];
00404     register TrimVertex *v1next = v1-1;
00405     register TrimVertex *v2next = v2+1;
00406     int sgn;
00407 
00408     assert( v1 != v1last );
00409     assert( v2 != v2last );
00410 
00411 #ifndef NDEBUG
00412     dprintf( "arc_ccw_turn, p = %d\n", 1 );
00413 #endif
00414 
00415     // the arcs lie on the line (1 == v1->param[1])
00416     if( v1->param[1] == v1next->param[1] && v2->param[1] == v2next->param[1] )
00417     return 0;
00418 
00419     if( v2next->param[1] > v2->param[1] || v1next->param[1] > v1->param[1] ) 
00420     ::mylongjmp( jumpbuffer, 28 );
00421 
00422     if( v1->param[0] < v2->param[0] )
00423     return 0;
00424     else if( v1->param[0] > v2->param[0] )
00425     return 1;
00426 
00427     while( 1 ) {
00428     if( v1next->param[1] > v2next->param[1] ) {
00429 #ifndef NDEBUG
00430         dprintf( "case c\n" );
00431 #endif
00432         assert( v1->param[1] >= v1next->param[1] );
00433         assert( v2->param[1] >= v1next->param[1] );
00434         switch( bbox( v2next, v2, v1next, 0 ) ) {
00435         case -1:
00436             return 0;
00437         case 0:
00438             sgn = ccw( v1next, v2, v2next );
00439             if( sgn != -1 ) 
00440             return sgn;
00441             else {
00442             v1 = v1next--;
00443 #ifdef DEBUG
00444             dprintf( "decr\n" );
00445 #endif
00446             if( v1 == v1last ) {
00447 #ifdef DEBUG
00448                 dprintf( "no good results\n" );
00449 #endif
00450                 return 0; // ill-conditioned, guess answer
00451             }
00452             }
00453             break;
00454         case 1:
00455             return 1;
00456         }
00457     } else if( v1next->param[1] < v2next->param[1] ) {
00458 #ifndef NDEBUG
00459         dprintf( "case d\n" );
00460         assert( v1->param[1] >= v2next->param[1] );
00461         assert( v2->param[1] >= v2next->param[1] );
00462 #endif
00463         switch( bbox( v1next, v1, v2next, 0 ) ) {
00464         case -1:
00465             return 1;
00466         case 0:
00467             sgn = ccw( v1next, v1, v2next );
00468             if( sgn != -1 ) 
00469             return sgn;
00470             else {
00471             v2 = v2next++;
00472 #ifdef DEBUG
00473             dprintf( "incr\n" );
00474 #endif
00475             if( v2 == v2last ) {
00476 #ifdef DEBUG
00477                 dprintf( "no good results\n" );
00478 #endif
00479                 return 0; // ill-conditioned, guess answer
00480             }
00481             }
00482             break;
00483         case 1:
00484             return 0;
00485         }
00486     } else {
00487 #ifdef DEBUG
00488         dprintf( "case cd\n" );
00489 #endif
00490         if( v1next->param[0] < v2next->param[0] )
00491         return 0;
00492         else if( v1next->param[0] > v2next->param[0] )
00493         return 1;
00494         else {
00495         v2 = v2next++;
00496 #ifdef DEBUG
00497         dprintf( "incr\n" );
00498 #endif
00499         if( v2 == v2last ) {
00500 #ifdef DEBUG
00501             dprintf( "no good results\n" );
00502 #endif
00503             return 0; // ill-conditioned, guess answer
00504         }
00505         }
00506     }
00507     }
00508 }
00509 
00510 
00511 #ifndef NDEBUG
00512 int
00513 Subdivider::bbox( register REAL sa, register REAL sb, register REAL sc,
00514       register REAL ta, register REAL tb, register REAL tc )
00515 #else
00516 int
00517 Subdivider::bbox( register REAL sa, register REAL sb, register REAL sc,
00518       register REAL   , register REAL   , register REAL    )
00519 #endif
00520 {
00521 #ifndef NDEBUG
00522     assert( tc >= ta );
00523     assert( tc <= tb );
00524 #endif
00525 
00526     if( sa < sb ) {
00527     if( sc <= sa ) {
00528         return -1;
00529     } else if( sb <= sc ) {
00530         return 1;
00531     } else {
00532         return 0;
00533     }
00534     } else if( sa > sb ) {
00535     if( sc >= sa ) {
00536         return 1;
00537     } else if( sb >= sc ) {
00538         return -1;
00539     } else {
00540         return 0;
00541     }
00542     } else {
00543     if( sc > sa ) {
00544         return 1;
00545     } else if( sb > sc ) {
00546         return -1;
00547     } else {
00548         return 0;
00549     }
00550     }
00551 }
00552 
00553 /*----------------------------------------------------------------------------
00554  * ccw - determine how three points are oriented by computing their
00555  *   determinant.  
00556  *   Return 1 if the vertices are ccw oriented, 
00557  *      0 if they are cw oriented, or 
00558  *      -1 if the computation is ill-conditioned.
00559  *----------------------------------------------------------------------------
00560  */
00561 int
00562 Subdivider::ccw( TrimVertex *a, TrimVertex *b, TrimVertex *c )
00563 {
00564     REAL d = det3( a, b, c );
00565     if( glu_abs(d) < 0.0001 ) return -1;
00566     return (d < 0.0) ? 0 : 1;
00567 }
Generated on Sat May 26 2012 04:22:15 for ReactOS by
1.7.6.1