src/glu/sgi/libnurbs/internals/arc.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  * arc.c++
  37  *
  38  */
  39
  40 #include <stdio.h>
  41 #include "glimports.h"
  42 #include "mystdio.h"
  43 #include "myassert.h"
  44 #include "arc.h"
  45 #include "bin.h"
  46 #include "pwlarc.h"
  47 #include "simplemath.h"
  48
  49 /* local preprocessor definitions */
  50 #define ZERO            0.00001/*0.000001*/
  51
  52 const int       Arc::bezier_tag = (1<<13);
  53 const int       Arc::arc_tag = (1<<3);
  54 const int       Arc::tail_tag = (1<<6);
  55
  56 /*--------------------------------------------------------------------------
  57  * makeSide - attach a pwl arc to an arc and mark it as a border arc
  58  *--------------------------------------------------------------------------
  59  */
  60
  61 void
  62 Arc::makeSide( PwlArc *pwl, arc_side side )
  63 {
  64     assert( pwl != 0);
  65     assert( pwlArc == 0 );
  66     assert( pwl->npts > 0 );
  67     assert( pwl->pts != 0);
  68     pwlArc = pwl;
  69     clearbezier();
  70     setside( side );
  71 }
  72
  73
  74 /*--------------------------------------------------------------------------
  75  * numpts - count number of points on arc loop
  76  *--------------------------------------------------------------------------
  77  */
  78
  79 int
  80 Arc::numpts( void )
  81 {
  82     Arc_ptr jarc = this;
  83     int npts = 0;
  84     do {
  85         npts += jarc->pwlArc->npts;
  86         jarc = jarc->next;
  87     } while( jarc != this );
  88     return npts;
  89 }
  90
  91 /*--------------------------------------------------------------------------
  92  * markverts - mark each point with id of arc
  93  *--------------------------------------------------------------------------
  94  */
  95
  96 void
  97 Arc::markverts( void )
  98 {
  99     Arc_ptr jarc = this;
 100
 101     do {
 102         TrimVertex *p = jarc->pwlArc->pts;
 103         for( int i=0; i<jarc->pwlArc->npts; i++ )
 104             p[i].nuid = jarc->nuid;
 105         jarc = jarc->next;
 106     } while( jarc != this );
 107 }
 108
 109 /*--------------------------------------------------------------------------
 110  * getextrema - find axis extrema on arc loop
 111  *--------------------------------------------------------------------------
 112  */
 113
 114 void
 115 Arc::getextrema( Arc_ptr extrema[4] )
 116 {
 117     REAL leftpt, botpt, rightpt, toppt;
 118
 119     extrema[0] = extrema[1] = extrema[2] = extrema[3] = this;
 120
 121     leftpt = rightpt = this->tail()[0];
 122     botpt  = toppt   = this->tail()[1];
 123
 124     for( Arc_ptr jarc = this->next; jarc != this; jarc = jarc->next ) {
 125         if ( jarc->tail()[0] <  leftpt ||
 126             (jarc->tail()[0] <= leftpt && jarc->rhead()[0]<=leftpt))  {
 127             leftpt = jarc->pwlArc->pts->param[0];
 128             extrema[1] = jarc;
 129         }
 130         if ( jarc->tail()[0] >  rightpt ||
 131             (jarc->tail()[0] >= rightpt && jarc->rhead()[0] >= rightpt)) {
 132             rightpt = jarc->pwlArc->pts->param[0];
 133             extrema[3] = jarc;
 134         }
 135         if ( jarc->tail()[1] <  botpt ||
 136             (jarc->tail()[1] <= botpt && jarc->rhead()[1] <= botpt ))  {
 137             botpt = jarc->pwlArc->pts->param[1];
 138             extrema[2] = jarc;
 139         }
 140         if ( jarc->tail()[1] >  toppt ||
 141             (jarc->tail()[1] >= toppt && jarc->rhead()[1] >= toppt))  {
 142             toppt = jarc->pwlArc->pts->param[1];
 143             extrema[0] = jarc;
 144         }
 145     }
 146 }
 147
 148
 149 /*-------------------------------------------------------------------------
 150  * show - print to the stdout the vertices of a pwl arc
 151  *-------------------------------------------------------------------------
 152  */
 153
 154 void
 155 Arc::show()
 156 {
 157 #ifndef NDEBUG
 158     _glu_dprintf( "\tPWLARC NP: %d FL: 1\n", pwlArc->npts );
 159     for( int i = 0; i < pwlArc->npts; i++ ) {
 160          _glu_dprintf( "\t\tVERTEX %f %f\n", pwlArc->pts[i].param[0],
 161                         pwlArc->pts[i].param[1] );
 162     }
 163 #endif
 164 }
 165
 166 /*-------------------------------------------------------------------------
 167  * print - print out the vertices of all pwl arcs on a loop
 168  *-------------------------------------------------------------------------
 169  */
 170
 171 void
 172 Arc::print( void )
 173 {
 174     Arc_ptr jarc = this;
 175
 176 #ifndef NDEBUG
 177     _glu_dprintf( "BGNTRIM\n" );
 178 #endif
 179     do {
 180         jarc->show( );
 181         jarc = jarc->next;
 182     } while (jarc != this);
 183 #ifndef NDEBUG
 184     _glu_dprintf("ENDTRIM\n" );
 185 #endif
 186 }
 187
 188 /*-------------------------------------------------------------------------
 189  * isDisconnected - check if tail of arc and head of prev meet
 190  *-------------------------------------------------------------------------
 191  */
 192
 193 int
 194 Arc::isDisconnected( void )
 195 {
 196     if( pwlArc == 0 ) return 0;
 197     if( prev->pwlArc == 0 ) return 0;
 198
 199     REAL *p0 = tail();
 200     REAL *p1 = prev->rhead();
 201
 202     if( ((p0[0] - p1[0]) > ZERO) || ((p1[0] - p0[0]) > ZERO) ||
 203         ((p0[1] - p1[1]) > ZERO) || ((p1[1] - p0[1]) > ZERO)  ) {
 204 #ifndef NDEBUG
 205         _glu_dprintf( "x coord = %f %f %f\n", p0[0], p1[0], p0[0] - p1[0] );
 206         _glu_dprintf( "y coord = %f %f %f\n", p0[1], p1[1], p0[1] - p1[1] );
 207 #endif
 208         return 1;
 209     } else {
 210         /* average two points together */
 211         p0[0] = p1[0] = (p1[0] + p0[0]) * 0.5;
 212         p0[1] = p1[1] = (p1[1] + p0[1]) * 0.5;
 213         return 0;
 214     }
 215 }
 216
 217 /*-------------------------------------------------------------------------
 218  * neq_vert - assert that two 2D vertices are not equal
 219  *-------------------------------------------------------------------------
 220  */
 221
 222 inline static int
 223 neq_vert( REAL  *v1, REAL *v2 )
 224 {
 225      return ((v1[0] != v2[0]) || (v1[1] != v2[1] )) ? 1 : 0;
 226 }
 227
 228 /*-------------------------------------------------------------------------
 229  * check - verify consistency of a loop, including
 230  *              1) if pwl, no two consecutive vertices are identical
 231  *              2) the circular link pointers are valid
 232  *              3) the geometric info at the head and tail are consistent
 233  *-------------------------------------------------------------------------
 234  */
 235
 236 int
 237 Arc::check( void )
 238 {
 239     if( this == 0 ) return 1;
 240     Arc_ptr jarc = this;
 241     do {
 242         assert( (jarc->pwlArc != 0) || (jarc->bezierArc != 0) );
 243
 244         if (jarc->prev == 0 || jarc->next == 0) {
 245 #ifndef NDEBUG
 246             _glu_dprintf( "checkjarc:null next/prev pointer\n");
 247             jarc->print( );
 248 #endif
 249             return 0;
 250         }
 251
 252         if (jarc->next->prev != jarc) {
 253 #ifndef NDEBUG
 254             _glu_dprintf( "checkjarc: pointer linkage screwed up\n");
 255             jarc->print( );
 256 #endif
 257             return 0;
 258         }
 259
 260         if( jarc->pwlArc ) {
 261 #ifndef NDEBUG
 262             assert( jarc->pwlArc->npts >= 1 );
 263             assert( jarc->pwlArc->npts < 100000 );
 264 /*
 265             for( int i=0; i < jarc->pwlArc->npts-1; i++ )
 266                 assert( neq_vert( jarc->pwlArc->pts[i].param,
 267                              jarc->pwlArc->pts[i+1].param) );
 268 */
 269 #endif
 270             if( jarc->prev->pwlArc ) {
 271                 if( jarc->tail()[1] != jarc->prev->rhead()[1] ) {
 272 #ifndef NDEBUG
 273                     _glu_dprintf( "checkjarc: geometric linkage screwed up 1\n");
 274                     jarc->prev->show();
 275                     jarc->show();
 276 #endif
 277                     return 0;
 278                 }
 279                 if( jarc->tail()[0] != jarc->prev->rhead()[0] ) {
 280
 281 #ifndef NDEBUG
 282                     _glu_dprintf( "checkjarc: geometric linkage screwed up 2\n");
 283                     jarc->prev->show();
 284                     jarc->show();
 285 #endif
 286                     return 0;
 287                 }
 288             }
 289             if( jarc->next->pwlArc ) {
 290                 if( jarc->next->tail()[0] != jarc->rhead()[0] ) {
 291 #ifndef NDEBUG
 292                         _glu_dprintf( "checkjarc: geometric linkage screwed up 3\n");
 293                         jarc->show();
 294                         jarc->next->show();
 295 #endif
 296                         return 0;
 297                 }
 298                 if( jarc->next->tail()[1] != jarc->rhead()[1] ) {
 299 #ifndef NDEBUG
 300                         _glu_dprintf( "checkjarc: geometric linkage screwed up 4\n");
 301                         jarc->show();
 302                         jarc->next->show();
 303 #endif
 304                         return 0;
 305                 }
 306             }
 307             if( jarc->isbezier() ) {
 308                 assert( jarc->pwlArc->npts == 2 );
 309                 assert( (jarc->pwlArc->pts[0].param[0] == \
 310                         jarc->pwlArc->pts[1].param[0]) ||\
 311                         (jarc->pwlArc->pts[0].param[1] == \
 312                         jarc->pwlArc->pts[1].param[1]) );
 313             }
 314         }
 315         jarc = jarc->next;
 316     } while (jarc != this);
 317     return 1;
 318 }
 319
 320
 321 #define TOL 0.00001
 322
 323 inline long tooclose( REAL x, REAL y )
 324 {
 325     return (glu_abs(x-y) < TOL) ?  1 : 0;
 326 }
 327
 328
 329 /*--------------------------------------------------------------------------
 330  * append - append a jordan arc to a circularly linked list
 331  *--------------------------------------------------------------------------
 332  */
 333
 334 Arc_ptr
 335 Arc::append( Arc_ptr jarc )
 336 {
 337     if( jarc != 0 ) {
 338         next = jarc->next;
 339         prev = jarc;
 340         next->prev = prev->next = this;
 341     } else {
 342         next = prev = this;
 343     }
 344     return this;
 345 }
 346