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