From a0c4815433ccd57322f4f7703ca35e9ccfa59250 Mon Sep 17 00:00:00 2001 From: marha Date: Thu, 8 Oct 2009 13:15:52 +0000 Subject: Added MesaLib-7.6 --- .../src/glu/sgi/libnurbs/internals/monotonizer.cc | 260 +++++++++++++++++++++ 1 file changed, 260 insertions(+) create mode 100644 mesalib/src/glu/sgi/libnurbs/internals/monotonizer.cc (limited to 'mesalib/src/glu/sgi/libnurbs/internals/monotonizer.cc') diff --git a/mesalib/src/glu/sgi/libnurbs/internals/monotonizer.cc b/mesalib/src/glu/sgi/libnurbs/internals/monotonizer.cc new file mode 100644 index 000000000..5845d310b --- /dev/null +++ b/mesalib/src/glu/sgi/libnurbs/internals/monotonizer.cc @@ -0,0 +1,260 @@ +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +*/ + +/* + * monotonizer.c++ + * + */ + +#include "glimports.h" +#include "mystdio.h" +#include "myassert.h" +#include "arc.h" +#include "arctess.h" +#include "bezierarc.h" +#include "bin.h" +#include "mapdesc.h" +#include "nurbsconsts.h" +#include "subdivider.h" + +/*----------------------------------------------------------------------------- + * Subdivider::decompose - break all curves into monotone arcs + *----------------------------------------------------------------------------- + */ +int +Subdivider::decompose( Bin& bin, REAL geo_stepsize ) +{ + Arc_ptr jarc; + for( jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) { + if( ! jarc->isTessellated() ) { + /* points have not been transformed, therefore they may be either + homogeneous or inhomogeneous */ + tessellate( jarc, geo_stepsize ); + if( jarc->isDisconnected() || jarc->next->isDisconnected() ) + return 1; + } + } + + for( jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) { + monotonize( jarc, bin ); + } + +#ifndef NDEBUG + for( jarc=bin.firstarc(); jarc; jarc=bin.nextarc() ) { + assert( isMonotone( jarc ) != 0 ); + } +#endif + + return 0; +} + +void +Subdivider::tessellate( Arc_ptr jarc, REAL geo_stepsize ) +{ + BezierArc *b = jarc->bezierArc; + Mapdesc *mapdesc = b->mapdesc; + + if( mapdesc->isRational() ) { + REAL max = mapdesc->calcVelocityRational( b->cpts, b->stride, b->order ); + REAL arc_stepsize = (max > 1.0) ? (1.0/max) : 1.0; + if( jarc->bezierArc->order != 2 ) + arctessellator.tessellateNonlinear( jarc, geo_stepsize, arc_stepsize, 1 ); + else { + arctessellator.tessellateLinear( jarc, geo_stepsize, arc_stepsize, 1 ); + } + } else { + REAL max = mapdesc->calcVelocityNonrational( b->cpts, b->stride, b->order ); + REAL arc_stepsize = (max > 1.0) ? (1.0/max) : 1.0; + if( jarc->bezierArc->order != 2 ) + arctessellator.tessellateNonlinear( jarc, geo_stepsize, arc_stepsize, 0 ); + else { + arctessellator.tessellateLinear( jarc, geo_stepsize, arc_stepsize, 0 ); + } + } +} + +/*------------------------------------------------------------------------- + * Subdivider::monotonize - break up a jordan arc into s,t-monotone + * components. This code will remove degenerate segments, including + * arcs of only a single point. + *------------------------------------------------------------------------- + */ +void +Subdivider::monotonize( Arc_ptr jarc, Bin& bin ) +{ + TrimVertex *firstvert = jarc->pwlArc->pts; + TrimVertex *lastvert = firstvert + (jarc->pwlArc->npts - 1); + long uid = jarc->nuid; + arc_side side = jarc->getside(); + dir sdir = none; + dir tdir = none; + int degenerate = 1; + + int nudegenerate; + int change; + + TrimVertex *vert; + for( vert = firstvert; vert != lastvert; vert++ ) { + + nudegenerate = 1; + change = 0; + + /* check change relative to s axis, clear degenerate bit if needed */ + REAL sdiff = vert[1].param[0] - vert[0].param[0]; + if( sdiff == 0 ) { + if( sdir != same ) { + sdir = same; + change = 1; + } + } else if( sdiff < 0.0 ) { + if( sdir != down ) { + sdir = down; + change = 1; + } + nudegenerate = 0; + } else { + if( sdir != up ) { + sdir = up; + change = 1; + } + nudegenerate = 0; + } + + /* check change relative to t axis, clear degenerate bit if needed */ + REAL tdiff = vert[1].param[1] - vert[0].param[1]; + if( tdiff == 0 ) { + if( tdir != same ) { + tdir = same; + change = 1; + } + } else if( tdiff < 0.0 ) { + if( tdir != down ) { + tdir = down; + change = 1; + } + nudegenerate = 0; + } else { + if( tdir != up ) { + tdir = up; + change = 1; + } + nudegenerate = 0; + } + + if( change ) { + if( ! degenerate ) { + /* make last segment into separate pwl curve */ + jarc->pwlArc->npts = vert - firstvert + 1; + jarc = (new(arcpool) Arc( side, uid ))->append( jarc ); + jarc->pwlArc = new(pwlarcpool) PwlArc(); + bin.addarc( jarc ); + } + firstvert = jarc->pwlArc->pts = vert; + degenerate = nudegenerate; + } + } + jarc->pwlArc->npts = vert - firstvert + 1; + + if( degenerate ) { + /* remove jarc from circularly linked list */ + jarc->prev->next = jarc->next; + jarc->next->prev = jarc->prev; + + assert( jarc->prev->check( ) != 0 ); + assert( jarc->next->check( ) != 0 ); + + /* remove jarc from bin */ + bin.remove_this_arc( jarc ); + + jarc->pwlArc->deleteMe( pwlarcpool ); jarc->pwlArc = 0; + jarc->deleteMe( arcpool ); + } +} + +/*------------------------------------------------------------------------- + * Subdivider::isMonotone - return true if arc is monotone AND non-degenerate + *------------------------------------------------------------------------- + */ +int +Subdivider::isMonotone( Arc_ptr jarc ) +{ + TrimVertex *firstvert = jarc->pwlArc->pts; + TrimVertex *lastvert = firstvert + (jarc->pwlArc->npts - 1); + + if( firstvert == lastvert ) return 1; + + TrimVertex *vert = firstvert; + enum dir sdir; + enum dir tdir; + + REAL diff = vert[1].param[0] - vert[0].param[0]; + if( diff == 0.0 ) + sdir = same; + else if( diff < 0.0 ) + sdir = down; + else + sdir = up; + + diff = vert[1].param[1] - vert[0].param[1]; + if( diff == 0.0 ) + tdir = same; + else if( diff < 0.0 ) + tdir = down; + else + tdir = up; + + if( (sdir == same) && (tdir == same) ) return 0; + + for( ++vert ; vert != lastvert; vert++ ) { + diff = vert[1].param[0] - vert[0].param[0]; + if( diff == 0.0 ) { + if( sdir != same ) return 0; + } else if( diff < 0.0 ) { + if( sdir != down ) return 0; + } else { + if( sdir != up ) return 0; + } + + diff = vert[1].param[1] - vert[0].param[1]; + if( diff == 0.0 ) { + if( tdir != same ) return 0; + } else if( diff < 0.0 ) { + if( tdir != down ) return 0; + } else { + if( tdir != up ) return 0; + } + } + return 1; +} + -- cgit v1.2.3