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: 2001/03/17 00:25:40 $ $Revision: 1.1 $
  39  * $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libnurbs/internals/arc.cc,v 1.1 2001/03/17 00:25:40 brianp 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     if( ! this ) {
 180 #ifndef NDEBUG
 181         dprintf( "\n\nEMPTY TRIM\n\n" );
 182 #endif
 183         return;
 184     }
 185
 186 #ifndef NDEBUG
 187     dprintf( "BGNTRIM\n" );
 188 #endif
 189     do {
 190         jarc->show( );
 191         jarc = jarc->next;
 192     } while (jarc != this);
 193 #ifndef NDEBUG
 194     dprintf("ENDTRIM\n" );
 195 #endif
 196 }
 197
 198 /*-------------------------------------------------------------------------
 199  * isDisconnected - check if tail of arc and head of prev meet
 200  *-------------------------------------------------------------------------
 201  */
 202
 203 int
 204 Arc::isDisconnected( void )
 205 {
 206     if( pwlArc == 0 ) return 0;
 207     if( prev->pwlArc == 0 ) return 0;
 208
 209     REAL *p0 = tail();
 210     REAL *p1 = prev->rhead();
 211
 212     if( ((p0[0] - p1[0]) > ZERO) || ((p1[0] - p0[0]) > ZERO) ||
 213         ((p0[1] - p1[1]) > ZERO) || ((p1[1] - p0[1]) > ZERO)  ) {
 214 #ifndef NDEBUG
 215         dprintf( "x coord = %f %f %f\n", p0[0], p1[0], p0[0] - p1[0] );
 216         dprintf( "y coord = %f %f %f\n", p0[1], p1[1], p0[1] - p1[1] );
 217 #endif
 218         return 1;
 219     } else {
 220         /* average two points together */
 221         p0[0] = p1[0] = (p1[0] + p0[0]) * 0.5;
 222         p0[1] = p1[1] = (p1[1] + p0[1]) * 0.5;
 223         return 0;
 224     }
 225 }
 226
 227 /*-------------------------------------------------------------------------
 228  * neq_vert - assert that two 2D vertices are not equal
 229  *-------------------------------------------------------------------------
 230  */
 231
 232 inline static int
 233 neq_vert( REAL  *v1, REAL *v2 )
 234 {
 235      return ((v1[0] != v2[0]) || (v1[1] != v2[1] )) ? 1 : 0;
 236 }
 237
 238 /*-------------------------------------------------------------------------
 239  * check - verify consistency of a loop, including
 240  *              1) if pwl, no two consecutive vertices are identical
 241  *              2) the circular link pointers are valid
 242  *              3) the geometric info at the head and tail are consistent
 243  *-------------------------------------------------------------------------
 244  */
 245
 246 int
 247 Arc::check( void )
 248 {
 249     if( this == 0 ) return 1;
 250     Arc_ptr jarc = this;
 251     do {
 252         assert( (jarc->pwlArc != 0) || (jarc->bezierArc != 0) );
 253
 254         if (jarc->prev == 0 || jarc->next == 0) {
 255 #ifndef NDEBUG
 256             dprintf( "checkjarc:null next/prev pointer\n");
 257             jarc->print( );
 258 #endif
 259             return 0;
 260         }
 261
 262         if (jarc->next->prev != jarc) {
 263 #ifndef NDEBUG
 264             dprintf( "checkjarc: pointer linkage screwed up\n");
 265             jarc->print( );
 266 #endif
 267             return 0;
 268         }
 269
 270         if( jarc->pwlArc ) {
 271 #ifndef NDEBUG
 272             assert( jarc->pwlArc->npts >= 1 );
 273             assert( jarc->pwlArc->npts < 100000 );
 274 /*
 275             for( int i=0; i < jarc->pwlArc->npts-1; i++ )
 276                 assert( neq_vert( jarc->pwlArc->pts[i].param,
 277                              jarc->pwlArc->pts[i+1].param) );
 278 */
 279 #endif
 280             if( jarc->prev->pwlArc ) {
 281                 if( jarc->tail()[1] != jarc->prev->rhead()[1] ) {
 282 #ifndef NDEBUG
 283                     dprintf( "checkjarc: geometric linkage screwed up 1\n");
 284                     jarc->prev->show();
 285                     jarc->show();
 286 #endif
 287                     return 0;
 288                 }
 289                 if( jarc->tail()[0] != jarc->prev->rhead()[0] ) {
 290
 291 #ifndef NDEBUG
 292                     dprintf( "checkjarc: geometric linkage screwed up 2\n");
 293                     jarc->prev->show();
 294                     jarc->show();
 295 #endif
 296                     return 0;
 297                 }
 298             }
 299             if( jarc->next->pwlArc ) {
 300                 if( jarc->next->tail()[0] != jarc->rhead()[0] ) {
 301 #ifndef NDEBUG
 302                         dprintf( "checkjarc: geometric linkage screwed up 3\n");
 303                         jarc->show();
 304                         jarc->next->show();
 305 #endif
 306                         return 0;
 307                 }
 308                 if( jarc->next->tail()[1] != jarc->rhead()[1] ) {
 309 #ifndef NDEBUG
 310                         dprintf( "checkjarc: geometric linkage screwed up 4\n");
 311                         jarc->show();
 312                         jarc->next->show();
 313 #endif
 314                         return 0;
 315                 }
 316             }
 317             if( jarc->isbezier() ) {
 318                 assert( jarc->pwlArc->npts == 2 );
 319                 assert( (jarc->pwlArc->pts[0].param[0] == \
 320                         jarc->pwlArc->pts[1].param[0]) ||\
 321                         (jarc->pwlArc->pts[0].param[1] == \
 322                         jarc->pwlArc->pts[1].param[1]) );
 323             }
 324         }
 325         jarc = jarc->next;
 326     } while (jarc != this);
 327     return 1;
 328 }
 329
 330
 331 #define TOL 0.00001
 332
 333 inline long tooclose( REAL x, REAL y )
 334 {
 335     return (abs(x-y) < TOL) ?  1 : 0;
 336 }
 337
 338
 339 /*--------------------------------------------------------------------------
 340  * append - append a jordan arc to a circularly linked list
 341  *--------------------------------------------------------------------------
 342  */
 343
 344 Arc_ptr
 345 Arc::append( Arc_ptr jarc )
 346 {
 347     if( jarc != 0 ) {
 348         next = jarc->next;
 349         prev = jarc;
 350         next->prev = prev->next = this;
 351     } else {
 352         next = prev = this;
 353     }
 354     return this;
 355 }
 356