source/singlesidedpolygons.cc

   1 /* This file is part of Shapes.
   2  *
   3  * Shapes is free software: you can redistribute it and/or modify
   4  * it under the terms of the GNU General Public License as published by
   5  * the Free Software Foundation, either version 3 of the License, or
   6  * any later version.
   7  *
   8  * Shapes is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public License
  14  * along with Shapes.  If not, see <http://www.gnu.org/licenses/>.
  15  *
  16  * Copyright 2008, 2010 Henrik Tidefelt
  17  */
  18
  19 #include <cmath>
  20
  21 #include "shapestypes.h"
  22 #include "shapesexceptions.h"
  23 #include "astexpr.h"
  24 #include "consts.h"
  25 #include "astvar.h"
  26 #include "astclass.h"
  27 #include "statetypes.h"
  28 #include "lighttypes.h"
  29 #include "shadingtypes.h"
  30 #include "globals.h"
  31 #include "trianglefunctions.h"
  32 #include "warn.h"
  33
  34 #include <list>
  35 #include <algorithm>
  36
  37 using namespace Shapes;
  38
  39
  40 std::string
  41 binaryFormat( unsigned int value, size_t bits )
  42 {
  43         std::ostringstream oss;
  44         for( int i = bits - 1; i >= 0; --i )
  45                 {
  46                         oss << ( ( ( ( value >> i ) & (size_t)( 1 ) ) != 0 ) ? '1' : 'o' ) ;
  47                 }
  48         return oss.str( );
  49 }
  50
  51
  52 Computation::SingleSidedPolygon3DGray::SingleSidedPolygon3DGray( const RefCountPtr< const Computation::FacetInterpolatorGray > & interpolator,
  53                                                                                                                                                                                                                                                                  bool singleSided,
  54                                                                                                                                                                                                                                                                  const Concrete::UnitFloatTriple & polygonUnitNormal,
  55                                                                                                                                                                                                                                                                  Concrete::Length m,
  56                                                                                                                                                                                                                                                                  Concrete::Length tiebreaker,
  57                                                                                                                                                                                                                                                                  Concrete::Length viewResolution,
  58                                                                                                                                                                                                                                                                  Computation::FacetShadeOrder shadeOrder )
  59         : Computation::PaintedPolygon3D( singleSided, polygonUnitNormal, m, tiebreaker ),
  60                 interpolator_( interpolator ),
  61                 viewResolution_( viewResolution ),
  62                 shadeOrder_( shadeOrder )
  63 { }
  64
  65 Computation::SingleSidedPolygon3DGray::~SingleSidedPolygon3DGray( )
  66 { }
  67
  68 RefCountPtr< const Lang::PaintedPolygon2D >
  69 Computation::SingleSidedPolygon3DGray::polygon_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights ) const
  70 {
  71         // In the current implementation, the color is only computed at one point.      Later, this
  72         // shall be extended to nice shadings.
  73
  74         Concrete::Length eyez = dyn->getEyeZ( );
  75
  76         if( viewResolution_ == Concrete::HUGE_LENGTH &&
  77                         shadeOrder_ == 0 )
  78                 {
  79                         return simple_polygon_to2D( eyez, tf, lights );
  80                 }
  81
  82         PtrOwner_back_Access< std::list< const FacetLatticeVertex * > > vertexMem;
  83         PtrOwner_back_Access< std::list< const FacetLatticeEdge * > > edgeMem;
  84         PtrOwner_back_Access< std::list< const Computation::FacetLatticeTriangle * > > lattice;
  85
  86         makeLattice( & lattice, & edgeMem, & vertexMem, viewResolution_, eyez, tf );
  87
  88         switch( shadeOrder_ )
  89                 {
  90                 case 0:
  91                         return render0( eyez, tf, lights, & lattice );
  92                 case 1:
  93                         {
  94                                 const SimplePDF::PDF_Version::Version SHADE_VERSION = SimplePDF::PDF_Version::PDF_1_3;
  95                                 if( Kernel::the_PDF_version.greaterOrEqual( SHADE_VERSION ) )
  96                                         {
  97                                                 return render1( eyez, tf, lights, & lattice );
  98                                         }
  99                                 else
 100                                         {
 101                                                 Kernel::the_PDF_version.message( SHADE_VERSION, "Replacing shade order 1 by 0." );
 102                                                 return render0( eyez, tf, lights, & lattice );
 103                                         }
 104                         }
 105                 case 2:
 106                         {
 107                                 const SimplePDF::PDF_Version::Version SHADE_VERSION = SimplePDF::PDF_Version::PDF_1_3;
 108                                 if( Kernel::the_PDF_version.greaterOrEqual( SHADE_VERSION ) )
 109                                         {
 110                                                 return render2( eyez, tf, lights, & lattice, vertexMem );
 111                                         }
 112                                 else
 113                                         {
 114                                                 Kernel::the_PDF_version.message( SHADE_VERSION, "Replacing shade order 2 by 0." );
 115                                                 return render0( eyez, tf, lights, & lattice );
 116                                         }
 117                         }
 118                 default:
 119                         throw Exceptions::InternalError( "SingleSidedPolygon3DGray::polygon_to2D: shadeOrder_ out of range." );
 120                 }
 121 }
 122
 123 RefCountPtr< const Lang::PaintedPolygon2D >
 124 Computation::SingleSidedPolygon3DGray::simple_polygon_to2D( const Concrete::Length eyez, const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights ) const
 125 {
 126         Kernel::GraphicsState * metaStatePtr = new Kernel::GraphicsState( true );
 127
 128         metaStatePtr->nonStrokingColor_ = interpolator_->compute( tf, lights, computeMean( ).transformed( tf ), eyez );
 129
 130         RefCountPtr< const Kernel::GraphicsState > metaState( metaStatePtr );
 131
 132         RefCountPtr< Lang::ElementaryPath2D > path = RefCountPtr< Lang::ElementaryPath2D >( new Lang::ElementaryPath2D( ) );
 133         path->close( );
 134         if( tf.isIdentity( ) )
 135                 {
 136                         typedef typeof points_ ListType;
 137                         for( ListType::const_iterator i = points_.begin( ); i != points_.end( ); ++i )
 138                                 {
 139                                         path->push_back( new Concrete::PathPoint2D( i->make2D( eyez ) ) );
 140                                 }
 141                 }
 142         else
 143                 {
 144                         typedef typeof points_ ListType;
 145                         for( ListType::const_iterator i = points_.begin( ); i != points_.end( ); ++i )
 146                                 {
 147                                         path->push_back( new Concrete::PathPoint2D( i->transformed( tf ).make2D( eyez ) ) );
 148                                 }
 149                 }
 150
 151         return RefCountPtr< const Lang::PaintedPolygon2D >( new Lang::PaintedPolygon2D( metaState, path ) );
 152 }
 153
 154 RefCountPtr< const Lang::PaintedPolygon2D >
 155 Computation::SingleSidedPolygon3DGray::render0( const Concrete::Length eyez, const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights, PtrOwner_back_Access< std::list< const Computation::FacetLatticeTriangle * > > * lattice ) const
 156 {
 157         RefCountPtr< const Lang::Group2D > contents = Lang::THE_NULL2D;
 158
 159         while( ! lattice->empty( ) )
 160                 {
 161                         const Computation::FacetLatticeTriangle * triangle = lattice->back( );
 162                         contents = RefCountPtr< const Lang::Group2D >( new Lang::GroupPair2D( triangle->paint( interpolator_, lights, eyez ),
 163                                                                                                                                                                                                                                                                                                                 contents,
 164                                                                                                                                                                                                                                                                                                                 Kernel::THE_DEFAULT_STATE ) );
 165                         delete triangle;
 166                         lattice->pop_back( );
 167                 }
 168
 169         RefCountPtr< Lang::ElementaryPath2D > path = RefCountPtr< Lang::ElementaryPath2D >( new Lang::ElementaryPath2D( ) );
 170         path->close( );
 171         if( tf.isIdentity( ) )
 172                 {
 173                         typedef typeof points_ ListType;
 174                         for( ListType::const_iterator i = points_.begin( ); i != points_.end( ); ++i )
 175                                 {
 176                                         path->push_back( new Concrete::PathPoint2D( i->make2D( eyez ) ) );
 177                                 }
 178                 }
 179         else
 180                 {
 181                         typedef typeof points_ ListType;
 182                         for( ListType::const_iterator i = points_.begin( ); i != points_.end( ); ++i )
 183                                 {
 184                                         path->push_back( new Concrete::PathPoint2D( i->transformed( tf ).make2D( eyez ) ) );
 185                                 }
 186                 }
 187
 188         return RefCountPtr< const Lang::PaintedPolygon2D >( new Lang::BBoxed2D( contents, path ) );
 189 }
 190
 191 RefCountPtr< const Lang::PaintedPolygon2D >
 192 Computation::SingleSidedPolygon3DGray::render1( const Concrete::Length eyez, const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights, PtrOwner_back_Access< std::list< const Computation::FacetLatticeTriangle * > > * lattice ) const
 193 {
 194         throw Exceptions::NotImplemented( "SingleSidedPolygon3DGray::render1" );
 195 }
 196
 197 RefCountPtr< const Lang::PaintedPolygon2D >
 198 Computation::SingleSidedPolygon3DGray::render2( const Concrete::Length eyez, const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights, PtrOwner_back_Access< std::list< const Computation::FacetLatticeTriangle * > > * lattice, const PtrOwner_back_Access< std::list< const FacetLatticeVertex * > > & vertexMem ) const
 199 {
 200         RefCountPtr< Lang::ElementaryPath2D > bbox = RefCountPtr< Lang::ElementaryPath2D >( new Lang::ElementaryPath2D( ) );
 201         bbox->close( );
 202         if( tf.isIdentity( ) )
 203                 {
 204                         typedef typeof points_ ListType;
 205                         for( ListType::const_iterator i = points_.begin( ); i != points_.end( ); ++i )
 206                                 {
 207                                         bbox->push_back( new Concrete::PathPoint2D( i->make2D( eyez ) ) );
 208                                 }
 209                 }
 210         else
 211                 {
 212                         typedef typeof points_ ListType;
 213                         for( ListType::const_iterator i = points_.begin( ); i != points_.end( ); ++i )
 214                                 {
 215                                         bbox->push_back( new Concrete::PathPoint2D( i->transformed( tf ).make2D( eyez ) ) );
 216                                 }
 217                 }
 218
 219
 220         std::vector< RefCountPtr< const Lang::Gray > > vertexColors;
 221         {
 222                 vertexColors.reserve( vertexMem.size( ) );
 223                 typedef typeof vertexMem ListType;
 224                 for( ListType::const_iterator i = vertexMem.begin( ); i != vertexMem.end( ); ++i )
 225                         {
 226                                 vertexColors.push_back( interpolator_->compute( tf, lights, (*i)->p3D_.transformed( tf ), eyez ) );
 227                         }
 228         }
 229
 230         RefCountPtr< const Lang::ColorSpace > colorSpace = Lang::THE_COLOR_SPACE_DEVICE_GRAY;
 231
 232         RefCountPtr< SimplePDF::PDF_Stream_out > form;
 233
 234         RefCountPtr< SimplePDF::PDF_Object > indirection = SimplePDF::indirect( form, & Kernel::theIndirectObjectCount );
 235
 236         (*form)[ "Subtype" ] = SimplePDF::newName( "Shading" );
 237         (*form)[ "ShadingType" ] = SimplePDF::newInt( 4 );
 238         (*form)[ "ColorSpace" ] = colorSpace->name( );
 239         //      (*form)[ "BBox" ] =
 240         //      (*form)[ "AntiAlias" ] =
 241
 242         const size_t BITS_PER_COORDINATE = 32;
 243         const size_t BITS_PER_COMPONENT = 12;
 244         const size_t BITS_PER_FLAG = 4;
 245         const size_t NUMBER_OF_COMPONENTS = colorSpace->numberOfComponents( );
 246         const size_t NUMBER_OF_COORDINATES = 2; // don't change!
 247
 248         if( ( NUMBER_OF_COORDINATES * BITS_PER_COORDINATE + NUMBER_OF_COMPONENTS* BITS_PER_COMPONENT + BITS_PER_FLAG ) % 8 != 0 )
 249                 {
 250                         throw Exceptions::InternalError( "The sizes of thins don't add upp to a whole number of bytes!" );
 251                 }
 252
 253         (*form)[ "BitsPerCoordinate" ] = SimplePDF::newInt( BITS_PER_COORDINATE );
 254         (*form)[ "BitsPerComponent" ] = SimplePDF::newInt( BITS_PER_COMPONENT );
 255         (*form)[ "BitsPerFlag" ] = SimplePDF::newInt( BITS_PER_FLAG );
 256
 257         Concrete::Coords2D x0y0( 0, 0 );
 258         Concrete::Coords2D x1y1( 0, 0 );
 259
 260         if( ! bbox->boundingRectangle( & x0y0, & x1y1 ) )
 261                 {
 262                         throw Exceptions::InternalError( "SingleSidedPolygon3DGray::render2: Polygon without bounding box!" );
 263                 }
 264         Concrete::Length bboxWidth = x1y1.x_ - x0y0.x_;
 265         Concrete::Length bboxHeight = x1y1.y_ - x0y0.y_;
 266
 267         RefCountPtr< SimplePDF::PDF_Vector > decodeArray = RefCountPtr< SimplePDF::PDF_Vector >( new SimplePDF::PDF_Vector( ) );
 268
 269         (*form)[ "Decode" ] = decodeArray;
 270
 271         decodeArray->vec.push_back( SimplePDF::newFloat( Concrete::Length::offtype( x0y0.x_ ) ) );
 272         decodeArray->vec.push_back( SimplePDF::newFloat( Concrete::Length::offtype( x1y1.x_ ) ) );
 273         decodeArray->vec.push_back( SimplePDF::newFloat( Concrete::Length::offtype( x0y0.y_ ) ) );
 274         decodeArray->vec.push_back( SimplePDF::newFloat( Concrete::Length::offtype( x1y1.y_ ) ) );
 275         for( size_t i = 0; i < NUMBER_OF_COMPONENTS; ++i )
 276                 {
 277                         decodeArray->vec.push_back( SimplePDF::newFloat( 0. ) );
 278                         decodeArray->vec.push_back( SimplePDF::newFloat( 1. ) );
 279                 }
 280
 281         const Computation::FacetLatticeVertex * va = 0;
 282         const Computation::FacetLatticeVertex * vb = 0;
 283         const Computation::FacetLatticeVertex * vc = 0;
 284
 285         {
 286                 // The first triangle is chosen at random.      We have no previous vertexes to consider.
 287                 const Computation::FacetLatticeTriangle * current = lattice->front( );
 288                 lattice->pop_front( );
 289                 current->getVertexes( & va, & vb, & vc );
 290                 delete current;
 291
 292                 writePacked( form->data,
 293                                                                  BITS_PER_COORDINATE, BITS_PER_COMPONENT, BITS_PER_FLAG,
 294                                                                  ( va->p2D_.x_ - x0y0.x_ ) / bboxWidth,
 295                                                                  ( va->p2D_.y_ - x0y0.y_ ) / bboxHeight,
 296                                                                  vertexColors[ va->i_ ]->components( ), 0 );
 297                 writePacked( form->data,
 298                                                                  BITS_PER_COORDINATE, BITS_PER_COMPONENT, BITS_PER_FLAG,
 299                                                                  ( vb->p2D_.x_ - x0y0.x_ ) / bboxWidth,
 300                                                                  ( vb->p2D_.y_ - x0y0.y_ ) / bboxHeight,
 301                                                                  vertexColors[ vb->i_ ]->components( ), 0 );
 302                 writePacked( form->data,
 303                                                                  BITS_PER_COORDINATE, BITS_PER_COMPONENT, BITS_PER_FLAG,
 304                                                                  ( vc->p2D_.x_ - x0y0.x_ ) / bboxWidth,
 305                                                                  ( vc->p2D_.y_ - x0y0.y_ ) / bboxHeight,
 306                                                                  vertexColors[ vc->i_ ]->components( ), 0 );
 307         }
 308
 309         while( ! lattice->empty( ) )
 310                 {
 311                         typedef typeof *lattice ListType;
 312                         bool found = false;
 313                         for( ListType::iterator i = lattice->begin( ); i != lattice->end( ); ++i ) // we could almost have used a const_iterator here,
 314                                 // but since the last thing we do is erase at i, a non-const iterator must be used.
 315                                 {
 316                                         const Computation::FacetLatticeTriangle * current = *i;
 317                                         unsigned char flag = current->extendLattice( & va, & vb, & vc );
 318                                         if( flag != 3 )
 319                                                 {
 320                                                         found = true;
 321
 322                                                         lattice->erase( i );
 323
 324                                                         writePacked( form->data,
 325                                                                                                          BITS_PER_COORDINATE, BITS_PER_COMPONENT, BITS_PER_FLAG,
 326                                                                                                          ( vc->p2D_.x_ - x0y0.x_ ) / bboxWidth,
 327                                                                                                          ( vc->p2D_.y_ - x0y0.y_ ) / bboxHeight,
 328                                                                                                          vertexColors[ vc->i_ ]->components( ), flag );
 329
 330                                                         delete current;
 331                                                         break;
 332                                                 }
 333                                 }
 334
 335                         if( ! found )
 336                                 {
 337                                         // The first triangle is chosen at random.      We have no previous vertexes to consider.
 338                                         const Computation::FacetLatticeTriangle * current = lattice->front( );
 339                                         lattice->pop_front( );
 340                                         current->getVertexes( & va, & vb, & vc );
 341                                         delete current;
 342
 343                                         writePacked( form->data,
 344                                                                                          BITS_PER_COORDINATE, BITS_PER_COMPONENT, BITS_PER_FLAG,
 345                                                                                          ( va->p2D_.x_ - x0y0.x_ ) / bboxWidth,
 346                                                                                          ( va->p2D_.y_ - x0y0.y_ ) / bboxHeight,
 347                                                                                          vertexColors[ va->i_ ]->components( ), 0 );
 348                                         writePacked( form->data,
 349                                                                                          BITS_PER_COORDINATE, BITS_PER_COMPONENT, BITS_PER_FLAG,
 350                                                                                          ( vb->p2D_.x_ - x0y0.x_ ) / bboxWidth,
 351                                                                                          ( vb->p2D_.y_ - x0y0.y_ ) / bboxHeight,
 352                                                                                          vertexColors[ vb->i_ ]->components( ), 0 );
 353                                         writePacked( form->data,
 354                                                                                          BITS_PER_COORDINATE, BITS_PER_COMPONENT, BITS_PER_FLAG,
 355                                                                                          ( vc->p2D_.x_ - x0y0.x_ ) / bboxWidth,
 356                                                                                          ( vc->p2D_.y_ - x0y0.y_ ) / bboxHeight,
 357                                                                                          vertexColors[ vc->i_ ]->components( ), 0 );
 358                                 }
 359                 }
 360
 361         RefCountPtr< const Lang::Type4Shading > contents
 362                 = RefCountPtr< const Lang::Type4Shading >( new Lang::Type4Shading( indirection, bbox ) );
 363
 364         return RefCountPtr< const Lang::PaintedPolygon2D >( new Lang::BBoxed2D( contents, bbox ) );
 365
 366 }
 367
 368 void
 369 Computation::SingleSidedPolygon3DGray::writePacked( std::ostream & os,
 370                                                                                                                                                                                                                 const size_t BITS_PER_COORDINATE, const size_t BITS_PER_COMPONENT, const size_t BITS_PER_FLAG,
 371                                                                                                                                                                                                                 const double x, const double y, const Concrete::Gray & color, const unsigned char flag )
 372 {
 373         char rest = 0;  // Unused bits must be zero!
 374         size_t restAvail = 8;           // Number of unused bits in <rest>.
 375
 376         {
 377                 size_t BITS = BITS_PER_FLAG;
 378                 writePackedValue( os, & rest, & restAvail, flag, BITS );
 379         }
 380
 381         {
 382                 size_t BITS = BITS_PER_COORDINATE;
 383                 unsigned int MAX = UINT_MAX >> ( 8 * sizeof( unsigned int ) - BITS ) ;
 384                 writePackedValue( os, & rest, & restAvail, (unsigned int)( x * MAX ), BITS );
 385                 writePackedValue( os, & rest, & restAvail, (unsigned int)( y * MAX ), BITS );
 386         }
 387
 388         {
 389                 size_t BITS = BITS_PER_COMPONENT;
 390                 unsigned int MAX = UINT_MAX >> ( 8 * sizeof( unsigned int ) - BITS ) ;
 391                 writePackedValue( os, & rest, & restAvail, (unsigned int)( color.gr_ * MAX ), BITS );
 392         }
 393
 394         if( restAvail < 8 )
 395                 {
 396                         os.write( & rest, 1 );
 397                 }
 398
 399 }
 400
 401 void
 402 Computation::SingleSidedPolygon3DGray::writePackedValue( std::ostream & os, char * rest, size_t * restAvail,
 403                                                                                                                                                                                                                                  unsigned int val, size_t bits )
 404 {
 405         if( bits >= *restAvail )
 406                 {
 407                         char tmp = ( val >> ( bits - *restAvail ) );
 408                         *rest |= tmp;
 409
 410                         val %= ( 1 << ( bits - *restAvail ) );
 411                         bits -= *restAvail;
 412
 413                         os.write( rest, 1 );
 414                         *rest = 0;
 415                         *restAvail = 8;
 416
 417                         while( bits >= 8 )
 418                                 {
 419                                         char tmp = ( val >> ( bits - 8 ) );
 420                                         os.write( & tmp, 1 );
 421                                         val %= ( 1 << ( bits - 8 ) );
 422
 423                                         bits -= 8;
 424                                 }
 425                 }
 426
 427         // By now we know that bits <= 7
 428         if( bits > *restAvail )
 429                 {
 430                         char tmp = ( val >> ( bits - *restAvail ) );
 431                         *rest |= tmp;
 432
 433                         bits -= *restAvail;
 434
 435                         os.write( rest, 1 );
 436                         *rest = 0;
 437                         *restAvail = 8;
 438
 439                         // This time there are no full bytes to write.
 440                 }
 441
 442         // By now we know that bits <= 6 and *restavail == 8
 443         if( bits > 0 )
 444                 {
 445                         char tmp = ( val << ( 8 - bits ) );
 446                         *rest |= tmp;
 447                         *restAvail -= bits;
 448                 }
 449 }
 450
 451
 452 RefCountPtr< const Lang::Color >
 453 Computation::SingleSidedPolygon3DGray::getColor( ) const
 454 {
 455         static bool warned = false;
 456         if( ! warned )
 457                 {
 458                         // This color is only used for debugging, so it doesn't matter that we don't care about lightening.
 459                         WARN_OR_THROW( Exceptions::InternalError( "SingleSidedPolygon3DGray::getColor just returns the lightMultiply coefficients as a color.", true ) )
 460                         WARN_OR_THROW( Exceptions::InternalError( "The warning above will be suppressed from now on.", true ) )
 461                         warned = true;
 462                 }
 463         return interpolator_->getDebugColor( );
 464 }
 465
 466 void
 467 Computation::SingleSidedPolygon3DGray::gcMark( Kernel::GCMarkedSet & marked )
 468 {
 469         const_cast< Computation::FacetInterpolatorGray * >( interpolator_.getPtr( ) )->gcMark( marked );
 470 }
 471
 472
 473 Computation::SingleSidedPolygon3DRGB::SingleSidedPolygon3DRGB( const RefCountPtr< const Computation::FacetInterpolatorRGB > & interpolator,
 474                                                                                                                                                                                                                                                                  bool singleSided,
 475                                                                                                                                                                                                                                                                  const Concrete::UnitFloatTriple & polygonUnitNormal,
 476                                                                                                                                                                                                                                                                  Concrete::Length m,
 477                                                                                                                                                                                                                                                                  Concrete::Length tiebreaker,
 478                                                                                                                                                                                                                                                                  Concrete::Length viewResolution,
 479                                                                                                                                                                                                                                                                  Computation::FacetShadeOrder shadeOrder )
 480         : Computation::PaintedPolygon3D( singleSided, polygonUnitNormal, m, tiebreaker ),
 481                 interpolator_( interpolator ),
 482                 viewResolution_( viewResolution ),
 483                 shadeOrder_( shadeOrder )
 484 { }
 485
 486 Computation::SingleSidedPolygon3DRGB::~SingleSidedPolygon3DRGB( )
 487 { }
 488
 489 RefCountPtr< const Lang::PaintedPolygon2D >
 490 Computation::SingleSidedPolygon3DRGB::polygon_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights ) const
 491 {
 492         // In the current implementation, the color is only computed at one point.      Later, this
 493         // shall be extended to nice shadings.
 494
 495         Concrete::Length eyez = dyn->getEyeZ( );
 496
 497         if( viewResolution_ == Concrete::HUGE_LENGTH &&
 498                         shadeOrder_ == 0 )
 499                 {
 500                         return simple_polygon_to2D( eyez, tf, lights );
 501                 }
 502
 503         PtrOwner_back_Access< std::list< const FacetLatticeVertex * > > vertexMem;
 504         PtrOwner_back_Access< std::list< const FacetLatticeEdge * > > edgeMem;
 505         PtrOwner_back_Access< std::list< const Computation::FacetLatticeTriangle * > > lattice;
 506
 507         makeLattice( & lattice, & edgeMem, & vertexMem, viewResolution_, eyez, tf );
 508
 509         switch( shadeOrder_ )
 510                 {
 511                 case 0:
 512                         return render0( eyez, tf, lights, & lattice );
 513                 case 1:
 514                         {
 515                                 const SimplePDF::PDF_Version::Version SHADE_VERSION = SimplePDF::PDF_Version::PDF_1_3;
 516                                 if( Kernel::the_PDF_version.greaterOrEqual( SHADE_VERSION ) )
 517                                         {
 518                                                 return render1( eyez, tf, lights, & lattice );
 519                                         }
 520                                 else
 521                                         {
 522                                                 Kernel::the_PDF_version.message( SHADE_VERSION, "Replacing shade order 1 by 0." );
 523                                                 return render0( eyez, tf, lights, & lattice );
 524                                         }
 525                         }
 526                 case 2:
 527                         {
 528                                 const SimplePDF::PDF_Version::Version SHADE_VERSION = SimplePDF::PDF_Version::PDF_1_3;
 529                                 if( Kernel::the_PDF_version.greaterOrEqual( SHADE_VERSION ) )
 530                                         {
 531                                                 return render2( eyez, tf, lights, & lattice, vertexMem );
 532                                         }
 533                                 else
 534                                         {
 535                                                 Kernel::the_PDF_version.message( SHADE_VERSION, "Replacing shade order 2 by 0." );
 536                                                 return render0( eyez, tf, lights, & lattice );
 537                                         }
 538                         }
 539                 default:
 540                         throw Exceptions::InternalError( "SingleSidedPolygon3DRGB::polygon_to2D: shadeOrder_ out of range." );
 541                 }
 542 }
 543
 544 RefCountPtr< const Lang::PaintedPolygon2D >
 545 Computation::SingleSidedPolygon3DRGB::simple_polygon_to2D( const Concrete::Length eyez, const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights ) const
 546 {
 547         Kernel::GraphicsState * metaStatePtr = new Kernel::GraphicsState( true );
 548
 549         metaStatePtr->nonStrokingColor_ = interpolator_->compute( tf, lights, computeMean( ).transformed( tf ), eyez );
 550
 551         RefCountPtr< const Kernel::GraphicsState > metaState( metaStatePtr );
 552
 553         RefCountPtr< Lang::ElementaryPath2D > path = RefCountPtr< Lang::ElementaryPath2D >( new Lang::ElementaryPath2D( ) );
 554         path->close( );
 555         if( tf.isIdentity( ) )
 556                 {
 557                         typedef typeof points_ ListType;
 558                         for( ListType::const_iterator i = points_.begin( ); i != points_.end( ); ++i )
 559                                 {
 560                                         path->push_back( new Concrete::PathPoint2D( i->make2D( eyez ) ) );
 561                                 }
 562                 }
 563         else
 564                 {
 565                         typedef typeof points_ ListType;
 566                         for( ListType::const_iterator i = points_.begin( ); i != points_.end( ); ++i )
 567                                 {
 568                                         path->push_back( new Concrete::PathPoint2D( i->transformed( tf ).make2D( eyez ) ) );
 569                                 }
 570                 }
 571
 572         return RefCountPtr< const Lang::PaintedPolygon2D >( new Lang::PaintedPolygon2D( metaState, path ) );
 573 }
 574
 575 RefCountPtr< const Lang::PaintedPolygon2D >
 576 Computation::SingleSidedPolygon3DRGB::render0( const Concrete::Length eyez, const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights, PtrOwner_back_Access< std::list< const Computation::FacetLatticeTriangle * > > * lattice ) const
 577 {
 578         RefCountPtr< const Lang::Group2D > contents = Lang::THE_NULL2D;
 579
 580         while( ! lattice->empty( ) )
 581                 {
 582                         const Computation::FacetLatticeTriangle * triangle = lattice->back( );
 583                         contents = RefCountPtr< const Lang::Group2D >( new Lang::GroupPair2D( triangle->paint( interpolator_, lights, eyez ),
 584                                                                                                                                                                                                                                                                                                                 contents,
 585                                                                                                                                                                                                                                                                                                                 Kernel::THE_DEFAULT_STATE ) );
 586                         delete triangle;
 587                         lattice->pop_back( );
 588                 }
 589
 590         RefCountPtr< Lang::ElementaryPath2D > path = RefCountPtr< Lang::ElementaryPath2D >( new Lang::ElementaryPath2D( ) );
 591         path->close( );
 592         if( tf.isIdentity( ) )
 593                 {
 594                         typedef typeof points_ ListType;
 595                         for( ListType::const_iterator i = points_.begin( ); i != points_.end( ); ++i )
 596                                 {
 597                                         path->push_back( new Concrete::PathPoint2D( i->make2D( eyez ) ) );
 598                                 }
 599                 }
 600         else
 601                 {
 602                         typedef typeof points_ ListType;
 603                         for( ListType::const_iterator i = points_.begin( ); i != points_.end( ); ++i )
 604                                 {
 605                                         path->push_back( new Concrete::PathPoint2D( i->transformed( tf ).make2D( eyez ) ) );
 606                                 }
 607                 }
 608
 609         return RefCountPtr< const Lang::PaintedPolygon2D >( new Lang::BBoxed2D( contents, path ) );
 610 }
 611
 612 RefCountPtr< const Lang::PaintedPolygon2D >
 613 Computation::SingleSidedPolygon3DRGB::render1( const Concrete::Length eyez, const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights, PtrOwner_back_Access< std::list< const Computation::FacetLatticeTriangle * > > * lattice ) const
 614 {
 615         throw Exceptions::NotImplemented( "SingleSidedPolygon3DRGB::render1" );
 616 }
 617
 618 RefCountPtr< const Lang::PaintedPolygon2D >
 619 Computation::SingleSidedPolygon3DRGB::render2( const Concrete::Length eyez, const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights, PtrOwner_back_Access< std::list< const Computation::FacetLatticeTriangle * > > * lattice, const PtrOwner_back_Access< std::list< const FacetLatticeVertex * > > & vertexMem ) const
 620 {
 621         RefCountPtr< Lang::ElementaryPath2D > bbox = RefCountPtr< Lang::ElementaryPath2D >( new Lang::ElementaryPath2D( ) );
 622         bbox->close( );
 623         if( tf.isIdentity( ) )
 624                 {
 625                         typedef typeof points_ ListType;
 626                         for( ListType::const_iterator i = points_.begin( ); i != points_.end( ); ++i )
 627                                 {
 628                                         bbox->push_back( new Concrete::PathPoint2D( i->make2D( eyez ) ) );
 629                                 }
 630                 }
 631         else
 632                 {
 633                         typedef typeof points_ ListType;
 634                         for( ListType::const_iterator i = points_.begin( ); i != points_.end( ); ++i )
 635                                 {
 636                                         bbox->push_back( new Concrete::PathPoint2D( i->transformed( tf ).make2D( eyez ) ) );
 637                                 }
 638                 }
 639
 640
 641         std::vector< RefCountPtr< const Lang::RGB > > vertexColors;
 642         {
 643                 vertexColors.reserve( vertexMem.size( ) );
 644                 typedef typeof vertexMem ListType;
 645                 for( ListType::const_iterator i = vertexMem.begin( ); i != vertexMem.end( ); ++i )
 646                         {
 647                                 vertexColors.push_back( interpolator_->compute( tf, lights, (*i)->p3D_.transformed( tf ), eyez ) );
 648                         }
 649         }
 650
 651         RefCountPtr< const Lang::ColorSpace > colorSpace = Lang::THE_COLOR_SPACE_DEVICE_RGB;
 652
 653         RefCountPtr< SimplePDF::PDF_Stream_out > form;
 654
 655         RefCountPtr< SimplePDF::PDF_Object > indirection = SimplePDF::indirect( form, & Kernel::theIndirectObjectCount );
 656
 657         (*form)[ "Subtype" ] = SimplePDF::newName( "Shading" );
 658         (*form)[ "ShadingType" ] = SimplePDF::newInt( 4 );
 659         (*form)[ "ColorSpace" ] = colorSpace->name( );
 660         //      (*form)[ "BBox" ] =
 661         //      (*form)[ "AntiAlias" ] =
 662
 663         const size_t BITS_PER_COORDINATE = 32;
 664         const size_t BITS_PER_COMPONENT = 12;
 665         const size_t BITS_PER_FLAG = 4;
 666         const size_t NUMBER_OF_COMPONENTS = colorSpace->numberOfComponents( );
 667         const size_t NUMBER_OF_COORDINATES = 2; // don't change!
 668
 669         if( ( NUMBER_OF_COORDINATES * BITS_PER_COORDINATE + NUMBER_OF_COMPONENTS* BITS_PER_COMPONENT + BITS_PER_FLAG ) % 8 != 0 )
 670                 {
 671                         throw Exceptions::InternalError( "The sizes of thins don't add upp to a whole number of bytes!" );
 672                 }
 673
 674         (*form)[ "BitsPerCoordinate" ] = SimplePDF::newInt( BITS_PER_COORDINATE );
 675         (*form)[ "BitsPerComponent" ] = SimplePDF::newInt( BITS_PER_COMPONENT );
 676         (*form)[ "BitsPerFlag" ] = SimplePDF::newInt( BITS_PER_FLAG );
 677
 678         Concrete::Coords2D x0y0( 0, 0 );
 679         Concrete::Coords2D x1y1( 0, 0 );
 680
 681         if( ! bbox->boundingRectangle( & x0y0, & x1y1 ) )
 682                 {
 683                         throw Exceptions::InternalError( "SingleSidedPolygon3DRGB::render2: Polygon without bounding box!" );
 684                 }
 685         Concrete::Length bboxWidth = x1y1.x_ - x0y0.x_;
 686         Concrete::Length bboxHeight = x1y1.y_ - x0y0.y_;
 687
 688         RefCountPtr< SimplePDF::PDF_Vector > decodeArray = RefCountPtr< SimplePDF::PDF_Vector >( new SimplePDF::PDF_Vector( ) );
 689
 690         (*form)[ "Decode" ] = decodeArray;
 691
 692         decodeArray->vec.push_back( SimplePDF::newFloat( Concrete::Length::offtype( x0y0.x_ ) ) );
 693         decodeArray->vec.push_back( SimplePDF::newFloat( Concrete::Length::offtype( x1y1.x_ ) ) );
 694         decodeArray->vec.push_back( SimplePDF::newFloat( Concrete::Length::offtype( x0y0.y_ ) ) );
 695         decodeArray->vec.push_back( SimplePDF::newFloat( Concrete::Length::offtype( x1y1.y_ ) ) );
 696         for( size_t i = 0; i < NUMBER_OF_COMPONENTS; ++i )
 697                 {
 698                         decodeArray->vec.push_back( SimplePDF::newFloat( 0. ) );
 699                         decodeArray->vec.push_back( SimplePDF::newFloat( 1. ) );
 700                 }
 701
 702         const Computation::FacetLatticeVertex * va = 0;
 703         const Computation::FacetLatticeVertex * vb = 0;
 704         const Computation::FacetLatticeVertex * vc = 0;
 705
 706         {
 707                 // The first triangle is chosen at random.      We have no previous vertexes to consider.
 708                 const Computation::FacetLatticeTriangle * current = lattice->front( );
 709                 lattice->pop_front( );
 710                 current->getVertexes( & va, & vb, & vc );
 711                 delete current;
 712
 713                 writePacked( form->data,
 714                                                                  BITS_PER_COORDINATE, BITS_PER_COMPONENT, BITS_PER_FLAG,
 715                                                                  ( va->p2D_.x_ - x0y0.x_ ) / bboxWidth,
 716                                                                  ( va->p2D_.y_ - x0y0.y_ ) / bboxHeight,
 717                                                                  vertexColors[ va->i_ ]->components( ), 0 );
 718                 writePacked( form->data,
 719                                                                  BITS_PER_COORDINATE, BITS_PER_COMPONENT, BITS_PER_FLAG,
 720                                                                  ( vb->p2D_.x_ - x0y0.x_ ) / bboxWidth,
 721                                                                  ( vb->p2D_.y_ - x0y0.y_ ) / bboxHeight,
 722                                                                  vertexColors[ vb->i_ ]->components( ), 0 );
 723                 writePacked( form->data,
 724                                                                  BITS_PER_COORDINATE, BITS_PER_COMPONENT, BITS_PER_FLAG,
 725                                                                  ( vc->p2D_.x_ - x0y0.x_ ) / bboxWidth,
 726                                                                  ( vc->p2D_.y_ - x0y0.y_ ) / bboxHeight,
 727                                                                  vertexColors[ vc->i_ ]->components( ), 0 );
 728         }
 729
 730         while( ! lattice->empty( ) )
 731                 {
 732                         typedef typeof *lattice ListType;
 733                         bool found = false;
 734                         for( ListType::iterator i = lattice->begin( ); i != lattice->end( ); ++i ) // we could almost have used a const_iterator here,
 735                                 // but since the last thing we do is erase at i, a non-const iterator must be used.
 736                                 {
 737                                         const Computation::FacetLatticeTriangle * current = *i;
 738                                         unsigned char flag = current->extendLattice( & va, & vb, & vc );
 739                                         if( flag != 3 )
 740                                                 {
 741                                                         found = true;
 742
 743                                                         lattice->erase( i );
 744
 745                                                         writePacked( form->data,
 746                                                                                                          BITS_PER_COORDINATE, BITS_PER_COMPONENT, BITS_PER_FLAG,
 747                                                                                                          ( vc->p2D_.x_ - x0y0.x_ ) / bboxWidth,
 748                                                                                                          ( vc->p2D_.y_ - x0y0.y_ ) / bboxHeight,
 749                                                                                                          vertexColors[ vc->i_ ]->components( ), flag );
 750
 751                                                         delete current;
 752                                                         break;
 753                                                 }
 754                                 }
 755
 756                         if( ! found )
 757                                 {
 758                                         // The first triangle is chosen at random.      We have no previous vertexes to consider.
 759                                         const Computation::FacetLatticeTriangle * current = lattice->front( );
 760                                         lattice->pop_front( );
 761                                         current->getVertexes( & va, & vb, & vc );
 762                                         delete current;
 763
 764                                         writePacked( form->data,
 765                                                                                          BITS_PER_COORDINATE, BITS_PER_COMPONENT, BITS_PER_FLAG,
 766                                                                                          ( va->p2D_.x_ - x0y0.x_ ) / bboxWidth,
 767                                                                                          ( va->p2D_.y_ - x0y0.y_ ) / bboxHeight,
 768                                                                                          vertexColors[ va->i_ ]->components( ), 0 );
 769                                         writePacked( form->data,
 770                                                                                          BITS_PER_COORDINATE, BITS_PER_COMPONENT, BITS_PER_FLAG,
 771                                                                                          ( vb->p2D_.x_ - x0y0.x_ ) / bboxWidth,
 772                                                                                          ( vb->p2D_.y_ - x0y0.y_ ) / bboxHeight,
 773                                                                                          vertexColors[ vb->i_ ]->components( ), 0 );
 774                                         writePacked( form->data,
 775                                                                                          BITS_PER_COORDINATE, BITS_PER_COMPONENT, BITS_PER_FLAG,
 776                                                                                          ( vc->p2D_.x_ - x0y0.x_ ) / bboxWidth,
 777                                                                                          ( vc->p2D_.y_ - x0y0.y_ ) / bboxHeight,
 778                                                                                          vertexColors[ vc->i_ ]->components( ), 0 );
 779                                 }
 780                 }
 781
 782         RefCountPtr< const Lang::Type4Shading > contents
 783                 = RefCountPtr< const Lang::Type4Shading >( new Lang::Type4Shading( indirection, bbox ) );
 784
 785         return RefCountPtr< const Lang::PaintedPolygon2D >( new Lang::BBoxed2D( contents, bbox ) );
 786
 787 }
 788
 789 void
 790 Computation::SingleSidedPolygon3DRGB::writePacked( std::ostream & os,
 791                                                                                                                                                                                                                 const size_t BITS_PER_COORDINATE, const size_t BITS_PER_COMPONENT, const size_t BITS_PER_FLAG,
 792                                                                                                                                                                                                                 const double x, const double y, const Concrete::RGB & color, const unsigned char flag )
 793 {
 794         char rest = 0;  // Unused bits must be zero!
 795         size_t restAvail = 8;           // Number of unused bits in <rest>.
 796
 797         {
 798                 size_t BITS = BITS_PER_FLAG;
 799                 writePackedValue( os, & rest, & restAvail, flag, BITS );
 800         }
 801
 802         {
 803                 size_t BITS = BITS_PER_COORDINATE;
 804                 unsigned int MAX = UINT_MAX >> ( 8 * sizeof( unsigned int ) - BITS ) ;
 805                 writePackedValue( os, & rest, & restAvail, (unsigned int)( x * MAX ), BITS );
 806                 writePackedValue( os, & rest, & restAvail, (unsigned int)( y * MAX ), BITS );
 807         }
 808
 809         {
 810                 size_t BITS = BITS_PER_COMPONENT;
 811                 unsigned int MAX = UINT_MAX >> ( 8 * sizeof( unsigned int ) - BITS ) ;
 812                 writePackedValue( os, & rest, & restAvail, (unsigned int)( color.r_ * MAX ), BITS );
 813                 writePackedValue( os, & rest, & restAvail, (unsigned int)( color.g_ * MAX ), BITS );
 814                 writePackedValue( os, & rest, & restAvail, (unsigned int)( color.b_ * MAX ), BITS );
 815         }
 816
 817         if( restAvail < 8 )
 818                 {
 819                         os.write( & rest, 1 );
 820                 }
 821
 822 }
 823
 824 void
 825 Computation::SingleSidedPolygon3DRGB::writePackedValue( std::ostream & os, char * rest, size_t * restAvail,
 826                                                                                                                                                                                                                                  unsigned int val, size_t bits )
 827 {
 828         if( bits >= *restAvail )
 829                 {
 830                         char tmp = ( val >> ( bits - *restAvail ) );
 831                         *rest |= tmp;
 832
 833                         val %= ( 1 << ( bits - *restAvail ) );
 834                         bits -= *restAvail;
 835
 836                         os.write( rest, 1 );
 837                         *rest = 0;
 838                         *restAvail = 8;
 839
 840                         while( bits >= 8 )
 841                                 {
 842                                         char tmp = ( val >> ( bits - 8 ) );
 843                                         os.write( & tmp, 1 );
 844                                         val %= ( 1 << ( bits - 8 ) );
 845
 846                                         bits -= 8;
 847                                 }
 848                 }
 849
 850         // By now we know that bits <= 7
 851         if( bits > *restAvail )
 852                 {
 853                         char tmp = ( val >> ( bits - *restAvail ) );
 854                         *rest |= tmp;
 855
 856                         bits -= *restAvail;
 857
 858                         os.write( rest, 1 );
 859                         *rest = 0;
 860                         *restAvail = 8;
 861
 862                         // This time there are no full bytes to write.
 863                 }
 864
 865         // By now we know that bits <= 6 and *restavail == 8
 866         if( bits > 0 )
 867                 {
 868                         char tmp = ( val << ( 8 - bits ) );
 869                         *rest |= tmp;
 870                         *restAvail -= bits;
 871                 }
 872 }
 873
 874
 875 RefCountPtr< const Lang::Color >
 876 Computation::SingleSidedPolygon3DRGB::getColor( ) const
 877 {
 878         static bool warned = false;
 879         if( ! warned )
 880                 {
 881                         // This color is only used for debugging, so it doesn't matter that we don't care about lightening.
 882                         WARN_OR_THROW( Exceptions::InternalError( "SingleSidedPolygon3DRGB::getColor just returns the lightMultiply coefficients as a color.", true ) )
 883                         WARN_OR_THROW( Exceptions::InternalError( "The warning above will be suppressed from now on.", true ) )
 884                         warned = true;
 885                 }
 886         return interpolator_->getDebugColor( );
 887 }
 888
 889 void
 890 Computation::SingleSidedPolygon3DRGB::gcMark( Kernel::GCMarkedSet & marked )
 891 {
 892         const_cast< Computation::FacetInterpolatorRGB * >( interpolator_.getPtr( ) )->gcMark( marked );
 893 }