source/drawabletypes.h

   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 Henrik Tidefelt
  17  */
  18
  19 #pragma once
  20
  21 #include "Shapes_Lang_decls.h"
  22 #include "Shapes_Ast_decls.h"
  23 #include "Shapes_Computation_decls.h"
  24 #include "Shapes_Kernel_decls.h"
  25
  26 #include "ptrowner.h"
  27 #include "refcount.h"
  28 #include "pdfstructure.h"
  29 #include "shapesvalue.h"
  30 #include "environment.h"
  31 #include "charptrless.h"
  32 #include "functiontypes.h"
  33 #include "elementarycoords.h"
  34 #include "concretecolors.h"
  35 #include "bezier.h"
  36
  37 #include <list>
  38 #include <iostream>
  39 #include <stack>
  40 #include <set>
  41
  42 namespace Shapes
  43 {
  44         namespace Lang
  45         {
  46
  47                 class FacetNormalGray : public NoOperatorOverloadValue
  48                 {
  49                         Concrete::Coords3D position_;
  50                         RefCountPtr< const Lang::SpecularReflection > reflections_;
  51                         Concrete::UnitFloatTriple reflectionUnitNormal_;
  52                         Concrete::Gray lightMultiply_;
  53                         RefCountPtr< const Lang::SpecularReflection > autoScattering_;
  54                         Concrete::Gray autoIntensity_;
  55                 public:
  56                         FacetNormalGray( const Concrete::Coords3D & position,
  57                                                                                          const RefCountPtr< const Lang::SpecularReflection > & reflections,
  58                                                                                          const Concrete::UnitFloatTriple & reflectionUnitNormal,
  59                                                                                          const Concrete::Gray lightMultiply,
  60                                                                                          const RefCountPtr< const Lang::SpecularReflection > & autoScattering,
  61                                                                                          const Concrete::Gray autoIntensity );
  62                         virtual ~FacetNormalGray( );
  63                         virtual void gcMark( Kernel::GCMarkedSet & marked );
  64
  65                         Concrete::Gray compute( const Concrete::Coords3D & point, const Concrete::UnitFloatTriple normal, const Lang::Transform3D & tf, const Concrete::Length eyez, const std::list< RefCountPtr< const Lang::LightSource > > & lights ) const;
  66                         Concrete::Gray compute( const Concrete::Coords3D & point, const Lang::Transform3D & tf, const Concrete::Length eyez, const std::list< RefCountPtr< const Lang::LightSource > > & lights ) const;
  67                         const Concrete::Coords3D & position( ) const { return position_; }
  68                         const Concrete::UnitFloatTriple & normal( ) const { return reflectionUnitNormal_; }
  69                         Concrete::Gray getDebugColor( ) const;
  70                         RefCountPtr< const Lang::FacetNormalGray > transformed( const Lang::Transform3D & tf ) const;
  71                         TYPEINFODECL;
  72                 };
  73
  74                 class FacetNormalRGB : public NoOperatorOverloadValue
  75                 {
  76                         Concrete::Coords3D position_;
  77                         RefCountPtr< const Lang::SpecularReflection > reflections_;
  78                         Concrete::UnitFloatTriple reflectionUnitNormal_;
  79                         Concrete::RGB lightMultiply_;
  80                         RefCountPtr< const Lang::SpecularReflection > autoScattering_;
  81                         Concrete::RGB autoIntensity_;
  82                 public:
  83                         FacetNormalRGB( const Concrete::Coords3D & position,
  84                                                                                         const RefCountPtr< const Lang::SpecularReflection > & reflections,
  85                                                                                         const Concrete::UnitFloatTriple & reflectionUnitNormal,
  86                                                                                         const Concrete::RGB & lightMultiply,
  87                                                                                         const RefCountPtr< const Lang::SpecularReflection > & autoScattering,
  88                                                                                         const Concrete::RGB & autoIntensity );
  89                         virtual ~FacetNormalRGB( );
  90                         virtual void gcMark( Kernel::GCMarkedSet & marked );
  91
  92                         Concrete::RGB compute( const Concrete::Coords3D & point, const Concrete::UnitFloatTriple normal, const Lang::Transform3D & tf, const Concrete::Length eyez, const std::list< RefCountPtr< const Lang::LightSource > > & lights ) const;
  93                         Concrete::RGB compute( const Concrete::Coords3D & point, const Lang::Transform3D & tf, const Concrete::Length eyez, const std::list< RefCountPtr< const Lang::LightSource > > & lights ) const;
  94                         const Concrete::Coords3D & position( ) const { return position_; }
  95                         const Concrete::UnitFloatTriple & normal( ) const { return reflectionUnitNormal_; }
  96                         Concrete::RGB getDebugColor( ) const;
  97                         RefCountPtr< const Lang::FacetNormalRGB > transformed( const Lang::Transform3D & tf ) const;
  98                         TYPEINFODECL;
  99                 };
 100
 101         }
 102
 103         namespace Computation
 104         {
 105                 class ZBufTriangle
 106                 {
 107                 public:
 108                         class ZMap
 109                         {
 110                                 Concrete::UnitFloatTriple normal_;
 111
 112                                 // The first group of members are used to compute the depth
 113                                 double k_x_;
 114                                 double k_y_;
 115                                 double k_z_;
 116                                 Concrete::Length m_;
 117                                 Physical< -1, 0 > eyezInv_;
 118
 119                                 // To break ties, one shall consult this member:
 120                                 Concrete::Length tiebreaker_;
 121
 122                                 // The next group of members are used to find plane intersections
 123                                 Concrete::Length eyez_;
 124                         public:
 125                                 ZMap( const Concrete::UnitFloatTriple & normal,
 126                                                         Concrete::Length m,
 127                                                         Concrete::Length tiebreaker,
 128                                                         Concrete::Length eyez );
 129
 130                                 Concrete::Length operator () ( const Concrete::Coords2D & p ) const;
 131
 132                                 void writeToMatrices( double a[3], Concrete::Length * b ) const;
 133                                 Concrete::Length eyez( ) const { return eyez_; }
 134                                 const Concrete::UnitFloatTriple & getNormal( ) const { return normal_; }
 135                                 Concrete::Length getM( ) const { return m_; }
 136                                 Concrete::Length getTiebreaker( ) const { return tiebreaker_; }
 137                         };
 138
 139                         const Computation::PaintedPolygon3D * painter_;
 140                         std::vector< Concrete::Coords2D > points_;
 141                         RefCountPtr< const ZMap > zMap_;
 142
 143                         std::list< RefCountPtr< const Lang::LightSource > > shadowLights_;
 144
 145                         ZBufTriangle( const Computation::PaintedPolygon3D * painter, const RefCountPtr< const Computation::ZBufTriangle::ZMap > & zMap, const Concrete::Coords2D & p1, const Concrete::Coords2D & p2, const Concrete::Coords2D & p3 );
 146                         Concrete::Length zAt( const Concrete::Coords2D & p ) const;
 147                         bool isOnTopOfAt( const Computation::ZBufTriangle & other, const Concrete::Coords2D & p ) const;
 148                         bool overlaps( const ZBufTriangle & other ) const;
 149                         bool overlaps( const ZBufTriangle & other, Concrete::Coords2D * commonPoint, Concrete::Length tol ) const; // tol shall be positive, and gives the smallest acceptable distance from commonPoint to the intersection boundary.
 150                         bool intersection( const Computation::ZBufTriangle & other, Computation::SplicingLine * line ) const;
 151                         bool overlapsAlong( const ZBufTriangle & other, const Computation::SplicingLine & line, Concrete::Length tol ) const; // tol shall be positive, and gives the smallest acceptable distance from commonPoint to the intersection boundary.
 152                         bool contains( const Concrete::Coords2D & p ) const;
 153                         bool contains( const Concrete::Coords2D & p, Concrete::Length tol ) const;
 154                         static void splice( const ZBufTriangle & tOld, const ZBufTriangle & tNew, std::list< Computation::ZBufTriangle > * oldDisjointTriangles, std::list< Computation::ZBufTriangle > * oldOccludedTriangles, std::list< Computation::ZBufTriangle > * newDisjointTriangles, std::list< Computation::ZBufTriangle > * newOccludedTriangles, std::list< Computation::ZBufTriangle > * triangleQueue );
 155                         std::list< Computation::ZBufTriangle >::iterator spliceAlong( const Computation::SplicingLine & line, std::list< Computation::ZBufTriangle > * dst ) const;
 156                         RefCountPtr< const Lang::ElementaryPath2D > toPath( ) const;
 157                         RefCountPtr< const Lang::Drawable2D > debugFrame( ) const;
 158                         void pushLines( std::vector< Computation::SplicingLine > * dst ) const;
 159                         void pushIntersection( std::vector< Computation::SplicingLine > * dst, const Computation::ZBufTriangle & other ) const;
 160
 161                         void addTriangleConstraints( Concrete::Coords2D llCorner, double * a, double * b ) const; // To be used by overlaps.
 162
 163                         Concrete::Area area( ) const;
 164
 165                 private:
 166                         static bool oneWayOverlap( const std::vector< Concrete::Coords2D > & poly1, const std::vector< Concrete::Coords2D > & poly2 );
 167                         void pushIfUnique( std::vector< Computation::SplicingLine > * dst, const Concrete::Coords3D p0, const Concrete::Coords3D p1, bool isTriangleSide = true ) const;
 168                         bool intersectionLinePoints( const Computation::ZBufTriangle & other, Concrete::Coords3D * p0, Concrete::Coords3D * p1 ) const;
 169                         friend std::ostream & operator << ( std::ostream & os, const Computation::ZBufTriangle & self );
 170                 };
 171
 172                 std::ostream & operator << ( std::ostream & os, const Computation::ZBufTriangle & self );
 173
 174                 class ZBufLine
 175                 {
 176                 public:
 177                         class ZMap
 178                         {
 179                                 Concrete::Coords3D p0_;
 180                                 Concrete::UnitFloatTriple d_;
 181
 182                                 // The first group of members are used to compute the depth
 183                                 double k_x_;
 184                                 double k_y_;
 185                                 double k_z_;
 186                                 //                              Physical< -1, 0 > eyezInv_;
 187
 188                                 // The next group of members are used to find plane intersections
 189                                 Concrete::Length eyez_;
 190                         public:
 191                                 ZMap( Concrete::Coords3D p0, const Concrete::UnitFloatTriple & d,
 192                                                         Concrete::Length eyez );
 193
 194                                 // It is assumed that this funciton is only called with points that actually are on the line.
 195                                 Concrete::Length operator () ( const Concrete::Coords2D & p ) const;
 196                                 Concrete::Coords3D intersection( const Computation::ZBufTriangle::ZMap & plane ) const;
 197
 198                                 Concrete::Length eyez( ) const { return eyez_; }
 199                         };
 200
 201                         const Computation::StrokedLine3D * painter_;
 202                         RefCountPtr< const Bezier::PolyCoeffs< Concrete::Coords2D > > bezierView_;
 203
 204                         Concrete::Coords2D p0_;
 205                         Concrete::Coords2D p1_;
 206                         Concrete::Coords2D d_; // this is just p1_ - p0_
 207                         RefCountPtr< const ZMap > zMap_;
 208
 209                         ZBufLine( const Computation::StrokedLine3D * painter, const RefCountPtr< const Computation::ZBufLine::ZMap > & zMap, const RefCountPtr< const Bezier::PolyCoeffs< Concrete::Coords2D > > & bezierView, const Concrete::Coords2D & p0, const Concrete::Coords2D & p1 );
 210                         Concrete::Length zAt( const Concrete::Coords2D & p ) const;
 211                         bool overlaps( const ZBufTriangle & other ) const;
 212                         bool overlaps( const ZBufLine & other ) const;
 213                         void splice( const ZBufTriangle & triangle, std::list< const Computation::ZBufLine * > * myLines ) const;
 214                         static void splice( const ZBufLine * line1, const ZBufLine * line2 , std::list< const Computation::ZBufLine * > * line1Container, std::list< const Computation::ZBufLine * > * line2Container );
 215                         RefCountPtr< const Lang::PaintedPath2D > stroke2D( ) const;
 216
 217                 protected:
 218                         double intersectionTime( Concrete::Coords2D p0, Concrete::Coords2D p1 ) const;
 219                 };
 220
 221                 class FacetLatticeVertex
 222                 {
 223                 public:
 224                         Concrete::Coords3D p3D_;
 225                         Concrete::Coords2D p2D_;
 226                         size_t i_;
 227
 228                         FacetLatticeVertex( const Concrete::Coords3D & p3D, const Concrete::Length eyez, const size_t i );
 229                         ~FacetLatticeVertex( ){ }
 230
 231                         Concrete::Length distanceTo2D( const Computation::FacetLatticeVertex & other ) const
 232                         {
 233                                 return p2D_.distanceTo( other.p2D_ );
 234                         }
 235                 };
 236
 237                 class FacetLatticeEdge
 238                 {
 239                         mutable const FacetLatticeEdge * child1_;
 240                         mutable const FacetLatticeEdge * child2_;
 241                 public:
 242                         const Computation::FacetLatticeVertex * p0_;
 243                         const Computation::FacetLatticeVertex * p1_;
 244
 245                         FacetLatticeEdge( const Computation::FacetLatticeVertex * p0, const Computation::FacetLatticeVertex * p1 )
 246                                 : child1_( 0 ), child2_( 0 ), p0_( p0 ), p1_( p1 )
 247                         { }
 248
 249                         void split( const Concrete::Length eyez,
 250                                                                         PtrOwner_back_Access< std::list< const Computation::FacetLatticeEdge * > > * edgeMem,
 251                                                                         PtrOwner_back_Access< std::list< const Computation::FacetLatticeVertex * > > * vertexMem,
 252                                                                         const Computation::FacetLatticeEdge ** child1, const Computation::FacetLatticeEdge ** child2 ) const;
 253
 254                         const FacetLatticeVertex * getOther( const FacetLatticeEdge * e ) const;
 255                         bool sharePoint( const FacetLatticeEdge * e ) const;
 256                         Concrete::Length length2D( ) const
 257                         {
 258                                 return p0_->p2D_.distanceTo( p1_->p2D_ );
 259                         }
 260
 261                         const FacetLatticeVertex * midpoint( ) const
 262                         {
 263                                 return child1_->p1_;
 264                         }
 265                 };
 266
 267                 class FacetLatticeTriangle
 268                 {
 269                 public:
 270                         const Computation::FacetLatticeEdge * e0_;
 271                         const Computation::FacetLatticeEdge * e1_;
 272                         const Computation::FacetLatticeEdge * e2_;
 273                 private:
 274                         const Computation::FacetLatticeVertex * v0_;
 275                         const Computation::FacetLatticeVertex * v1_;
 276                         const Computation::FacetLatticeVertex * v2_;
 277                 public:
 278
 279                         FacetLatticeTriangle( const Computation::FacetLatticeEdge * e0, const Computation::FacetLatticeEdge * e1, const Computation::FacetLatticeEdge * e2 )
 280                                 : e0_( e0 ), e1_( e1 ), e2_( e2 ),
 281                                         v0_( e0_->p0_ ), v1_( e0_->p1_ ), v2_( e1_->getOther( e0_ ) )
 282                         { };
 283                         ~FacetLatticeTriangle( )
 284                         { };
 285
 286                         const FacetLatticeEdge * getOther( const Computation::FacetLatticeEdge * ea, const Computation::FacetLatticeEdge * eb ) const;
 287                         bool fitsResolution( const Concrete::Length resolution, const Concrete::Length eyez,
 288                                                                                                          PtrOwner_back_Access< std::list< const Computation::FacetLatticeEdge * > > * edgeMem,
 289                                                                                                          PtrOwner_back_Access< std::list< const Computation::FacetLatticeVertex * > > * vertexMem,
 290                                                                                                          const Computation::FacetLatticeTriangle ** child1, const Computation::FacetLatticeTriangle ** child2 ) const;
 291                         RefCountPtr< const Lang::Drawable2D > paint( const RefCountPtr< const Computation::FacetInterpolatorGray > & interpolator, const std::list< RefCountPtr< const Lang::LightSource > > & lights, const Concrete::Length eyez ) const;
 292                         RefCountPtr< const Lang::Drawable2D > paint( const RefCountPtr< const Computation::FacetInterpolatorRGB > & interpolator, const std::list< RefCountPtr< const Lang::LightSource > > & lights, const Concrete::Length eyez ) const;
 293                         void getVertexes( const Computation::FacetLatticeVertex ** va, const Computation::FacetLatticeVertex ** vb, const Computation::FacetLatticeVertex ** vc ) const;
 294                         unsigned char extendLattice( const Computation::FacetLatticeVertex ** va, const Computation::FacetLatticeVertex ** vb, const Computation::FacetLatticeVertex ** vc ) const;
 295                         void display2D( std::ostream & os ) const;
 296                         void display3D( std::ostream & os ) const;
 297                 };
 298
 299                 class StrokedLine3D
 300                 {
 301                 protected:
 302                         Concrete::Coords3D p0_;
 303                         Concrete::Coords3D p1_;
 304                         RefCountPtr< const Kernel::GraphicsState > metaState_;
 305                 public:
 306                         StrokedLine3D( const Concrete::Coords3D & p0, const Concrete::Coords3D & p1, const RefCountPtr< const Kernel::GraphicsState > metaState );
 307                         virtual ~StrokedLine3D( );
 308                         virtual void push_zBufLine( const Lang::Transform3D & tf, const Concrete::Length eyez, std::list< const Computation::ZBufLine * > * lineQueue ) const;
 309                         const RefCountPtr< const Kernel::GraphicsState > & getMetaState( ) const { return metaState_; }
 310                 };
 311
 312                 class StrokedSplineSegment3D : public StrokedLine3D
 313                 {
 314                         Concrete::Coords3D p0front_;
 315                         Concrete::Coords3D p1rear_;
 316                 public:
 317                         StrokedSplineSegment3D( const Concrete::Coords3D & p0, const Concrete::Coords3D & p0front, const Concrete::Coords3D & p1rear, const Concrete::Coords3D & p1, const RefCountPtr< const Kernel::GraphicsState > metaState );
 318                         ~StrokedSplineSegment3D( );
 319                         virtual void push_zBufLine( const Lang::Transform3D & tf, const Concrete::Length eyez, std::list< const Computation::ZBufLine * > * lineQueue ) const;
 320                 };
 321
 322                 class PaintedPolygon3D
 323                 {
 324                 protected:
 325                         std::list< Concrete::Coords3D > points_;
 326                         // The following two members define the plane in which all points are required to be
 327                         bool singleSided_; // If true, normal_ is the outward normal of the surface of a solid object.  I false, this area has two opposite outward normals.
 328                         Concrete::UnitFloatTriple normal_;
 329                         Concrete::Length m_;
 330                         Concrete::Length tiebreaker_;
 331                 public:
 332                         PaintedPolygon3D( bool singleSided, const Concrete::UnitFloatTriple & normal, Concrete::Length m, Concrete::Length tiebreaker );
 333                         virtual ~PaintedPolygon3D( );
 334                         void pushPoint( const Concrete::Coords3D & p );
 335                         void push_zBufTriangles( const Lang::Transform3D & tf, const Concrete::Length eyez, std::list< Computation::ZBufTriangle > * triangleQueue, bool respectSingleSided = false ) const;
 336
 337                         virtual RefCountPtr< const Lang::PaintedPolygon2D > polygon_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights ) const = 0;
 338                         virtual RefCountPtr< const Lang::Color > getColor( ) const = 0;
 339
 340                         void makeLattice( PtrOwner_back_Access< std::list< const Computation::FacetLatticeTriangle * > > * lattice,
 341                                                                                                 PtrOwner_back_Access< std::list< const Computation::FacetLatticeEdge * > > * edgeMem,
 342                                                                                                 PtrOwner_back_Access< std::list< const FacetLatticeVertex * > > * vertexMem,
 343                                                                                                 const Concrete::Length viewResolution,
 344                                                                                                 const Concrete::Length eyez, const Lang::Transform3D & tf ) const;
 345
 346                         virtual void gcMark( Kernel::GCMarkedSet & marked ) = 0;
 347                 protected:
 348                         Concrete::Coords3D computeMean( ) const;
 349                 private:
 350                         PaintedPolygon3D( const Computation::PaintedPolygon3D & orig );
 351                 };
 352
 353         class FacetInterpolatorGray
 354         {
 355         public:
 356                 FacetInterpolatorGray( ){ };
 357                 virtual ~FacetInterpolatorGray( );
 358                 virtual RefCountPtr< const Lang::Gray > compute( const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights, const Concrete::Coords3D & point, const Concrete::Length eyez ) const = 0;
 359                 virtual RefCountPtr< const Lang::Gray > getDebugColor( ) const = 0;
 360                 virtual RefCountPtr< const Computation::FacetInterpolatorGray > transformed( const Lang::Transform3D & tf ) const = 0;
 361                 virtual void gcMark( Kernel::GCMarkedSet & marked ) = 0;
 362         };
 363
 364                 class FacetInterpolatorGray1 : public FacetInterpolatorGray
 365         {
 366                 RefCountPtr< const Lang::FacetNormalGray > n1_;
 367         public:
 368                 FacetInterpolatorGray1( const RefCountPtr< const Lang::FacetNormalGray > & n1 )
 369                         : n1_( n1 )
 370                         { }
 371                 virtual ~FacetInterpolatorGray1( );
 372                 virtual RefCountPtr< const Lang::Gray > compute( const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights, const Concrete::Coords3D & point, const Concrete::Length eyez ) const;
 373                 virtual RefCountPtr< const Lang::Gray > getDebugColor( ) const;
 374                 virtual RefCountPtr< const Computation::FacetInterpolatorGray > transformed( const Lang::Transform3D & tf ) const;
 375                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 376         };
 377
 378         class FacetInterpolatorGray2 : public FacetInterpolatorGray
 379         {
 380                 RefCountPtr< const Lang::FacetNormalGray > n1_;
 381                 RefCountPtr< const Lang::FacetNormalGray > n2_;
 382
 383                 // We define members such that the weight of n2_ at point p is
 384                 //       ( < t_, p > - m_ ) / d_
 385                 // that is, at least as long as this number is in the range [ 0, 1 ].
 386                 Concrete::Length d_;
 387                 Concrete::UnitFloatTriple t_;
 388                 Concrete::Length m_;
 389
 390                 // We also define members that describe how the normal at n1_ is rotated to obtain the normal at n2_
 391                 double angle_;
 392                 Concrete::UnitFloatTriple rotationDirection_;
 393         public:
 394                 FacetInterpolatorGray2( const RefCountPtr< const Lang::FacetNormalGray > & n1,
 395                                                                                                                 const RefCountPtr< const Lang::FacetNormalGray > & n2 );
 396                 virtual ~FacetInterpolatorGray2( );
 397                 virtual RefCountPtr< const Lang::Gray > compute( const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights, const Concrete::Coords3D & point, const Concrete::Length eyez ) const;
 398                 virtual RefCountPtr< const Lang::Gray > getDebugColor( ) const;
 399                 virtual RefCountPtr< const Computation::FacetInterpolatorGray > transformed( const Lang::Transform3D & tf ) const;
 400                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 401         };
 402
 403         class FacetInterpolatorGray3 : public FacetInterpolatorGray
 404         {
 405                 RefCountPtr< const Lang::FacetNormalGray > n1_;
 406                 RefCountPtr< const Lang::FacetNormalGray > n2_;
 407                 RefCountPtr< const Lang::FacetNormalGray > n3_;
 408
 409                 // The interpolation here is much less sophisticated compared to the interpolation of two normals.
 410                 // We compute positive, unnormalized weights wuch that each weight is one at the point it belongs to, and vanishes
 411                 // at the line through the other points.        Then we normalize.      This should be subject to change in later versions!
 412                 Concrete::Coords3D p1_;
 413                 Concrete::Coords3D p2_;
 414                 Concrete::Coords3D p3_;
 415                 Concrete::UnitFloatTriple d1_;
 416                 Concrete::UnitFloatTriple d2_;
 417                 Concrete::UnitFloatTriple d3_;
 418                 Concrete::Length l1_;
 419                 Concrete::Length l2_;
 420                 Concrete::Length l3_;
 421         public:
 422                 FacetInterpolatorGray3( const RefCountPtr< const Lang::FacetNormalGray > & n1,
 423                                                                                                                 const RefCountPtr< const Lang::FacetNormalGray > & n2,
 424                                                                                                                 const RefCountPtr< const Lang::FacetNormalGray > & n3 );
 425                 virtual ~FacetInterpolatorGray3( );
 426                 virtual RefCountPtr< const Lang::Gray > compute( const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights, const Concrete::Coords3D & point, const Concrete::Length eyez ) const;
 427                 virtual RefCountPtr< const Lang::Gray > getDebugColor( ) const;
 428                 virtual RefCountPtr< const Computation::FacetInterpolatorGray > transformed( const Lang::Transform3D & tf ) const;
 429                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 430         };
 431
 432         class FacetInterpolatorRGB
 433         {
 434         public:
 435                 FacetInterpolatorRGB( ){ };
 436                 virtual ~FacetInterpolatorRGB( );
 437                 virtual RefCountPtr< const Lang::RGB > compute( const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights, const Concrete::Coords3D & point, const Concrete::Length eyez ) const = 0;
 438                 virtual RefCountPtr< const Lang::RGB > getDebugColor( ) const = 0;
 439                 virtual RefCountPtr< const Computation::FacetInterpolatorRGB > transformed( const Lang::Transform3D & tf ) const = 0;
 440                 virtual void gcMark( Kernel::GCMarkedSet & marked ) = 0;
 441         };
 442
 443                 class FacetInterpolatorRGB1 : public FacetInterpolatorRGB
 444         {
 445                 RefCountPtr< const Lang::FacetNormalRGB > n1_;
 446         public:
 447                 FacetInterpolatorRGB1( const RefCountPtr< const Lang::FacetNormalRGB > & n1 )
 448                         : n1_( n1 )
 449                         { }
 450                 virtual ~FacetInterpolatorRGB1( );
 451                 virtual RefCountPtr< const Lang::RGB > compute( const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights, const Concrete::Coords3D & point, const Concrete::Length eyez ) const;
 452                 virtual RefCountPtr< const Lang::RGB > getDebugColor( ) const;
 453                 virtual RefCountPtr< const Computation::FacetInterpolatorRGB > transformed( const Lang::Transform3D & tf ) const;
 454                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 455         };
 456
 457         class FacetInterpolatorRGB2 : public FacetInterpolatorRGB
 458         {
 459                 RefCountPtr< const Lang::FacetNormalRGB > n1_;
 460                 RefCountPtr< const Lang::FacetNormalRGB > n2_;
 461
 462                 // We define members such that the weight of n2_ at point p is
 463                 //       ( < t_, p > - m_ ) / d_
 464                 // that is, at least as long as this number is in the range [ 0, 1 ].
 465                 Concrete::Length d_;
 466                 Concrete::UnitFloatTriple t_;
 467                 Concrete::Length m_;
 468
 469                 // We also define members that describe how the normal at n1_ is rotated to obtain the normal at n2_
 470                 double angle_;
 471                 Concrete::UnitFloatTriple rotationDirection_;
 472         public:
 473                 FacetInterpolatorRGB2( const RefCountPtr< const Lang::FacetNormalRGB > & n1,
 474                                                                                                          const RefCountPtr< const Lang::FacetNormalRGB > & n2 );
 475                 virtual ~FacetInterpolatorRGB2( );
 476                 virtual RefCountPtr< const Lang::RGB > compute( const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights, const Concrete::Coords3D & point, const Concrete::Length eyez ) const;
 477                 virtual RefCountPtr< const Lang::RGB > getDebugColor( ) const;
 478                 virtual RefCountPtr< const Computation::FacetInterpolatorRGB > transformed( const Lang::Transform3D & tf ) const;
 479                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 480         };
 481
 482         class FacetInterpolatorRGB3 : public FacetInterpolatorRGB
 483         {
 484                 RefCountPtr< const Lang::FacetNormalRGB > n1_;
 485                 RefCountPtr< const Lang::FacetNormalRGB > n2_;
 486                 RefCountPtr< const Lang::FacetNormalRGB > n3_;
 487
 488                 // The interpolation here is much less sophisticated compared to the interpolation of two normals.
 489                 // We compute positive, unnormalized weights wuch that each weight is one at the point it belongs to, and vanishes
 490                 // at the line through the other points.        Then we normalize.      This should be subject to change in later versions!
 491                 Concrete::Coords3D p1_;
 492                 Concrete::Coords3D p2_;
 493                 Concrete::Coords3D p3_;
 494                 Concrete::UnitFloatTriple d1_;
 495                 Concrete::UnitFloatTriple d2_;
 496                 Concrete::UnitFloatTriple d3_;
 497                 Concrete::Length l1_;
 498                 Concrete::Length l2_;
 499                 Concrete::Length l3_;
 500         public:
 501                 FacetInterpolatorRGB3( const RefCountPtr< const Lang::FacetNormalRGB > & n1,
 502                                                                                                          const RefCountPtr< const Lang::FacetNormalRGB > & n2,
 503                                                                                                          const RefCountPtr< const Lang::FacetNormalRGB > & n3 );
 504                 virtual ~FacetInterpolatorRGB3( );
 505                 virtual RefCountPtr< const Lang::RGB > compute( const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights, const Concrete::Coords3D & point, const Concrete::Length eyez ) const;
 506                 virtual RefCountPtr< const Lang::RGB > getDebugColor( ) const;
 507                 virtual RefCountPtr< const Computation::FacetInterpolatorRGB > transformed( const Lang::Transform3D & tf ) const;
 508                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 509         };
 510
 511         class FilledPolygon3D : public PaintedPolygon3D
 512         {
 513                 RefCountPtr< const Kernel::GraphicsState > metaState_;
 514         public:
 515                 FilledPolygon3D( const RefCountPtr< const Kernel::GraphicsState > & metaState,
 516                                                                                  const Concrete::UnitFloatTriple & normal, Concrete::Length m,
 517                                                                                  Concrete::Length tiebreaker );
 518                 virtual ~FilledPolygon3D( );
 519                 virtual RefCountPtr< const Lang::PaintedPolygon2D > polygon_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights ) const;
 520                 virtual RefCountPtr< const Lang::Color > getColor( ) const;              // shall only be used for debugging!
 521                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 522         };
 523
 524         class NullPolygon3D : public PaintedPolygon3D
 525         {
 526         public:
 527                 NullPolygon3D( );
 528                 virtual ~NullPolygon3D( );
 529                 virtual RefCountPtr< const Lang::PaintedPolygon2D > polygon_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights ) const;
 530                 virtual RefCountPtr< const Lang::Color > getColor( ) const;              // shall only be used for debugging!
 531                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 532         };
 533
 534         class SingleSidedPolygon3DGray : public PaintedPolygon3D
 535         {
 536                 RefCountPtr< const Computation::FacetInterpolatorGray > interpolator_;
 537                 Concrete::Length viewResolution_;
 538                 Computation::FacetShadeOrder shadeOrder_;       // legal values: { 0, 1, 2 }
 539         public:
 540                 SingleSidedPolygon3DGray( const RefCountPtr< const Computation::FacetInterpolatorGray > & interpolator,
 541                                                                                                                         bool singleSided, // Confusingly, this type is sometimes used also for double-sided polygons.
 542                                                                                                                         const Concrete::UnitFloatTriple & polygonUnitNormal,
 543                                                                                                                         Concrete::Length m,
 544                                                                                                                         Concrete::Length tiebreaker,
 545                                                                                                                         Concrete::Length viewResolution,
 546                                                                                                                         Computation::FacetShadeOrder shadeOrder );
 547                 virtual ~SingleSidedPolygon3DGray( );
 548                 virtual RefCountPtr< const Lang::PaintedPolygon2D > polygon_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights ) const;
 549                 virtual RefCountPtr< const Lang::Color > getColor( ) const;              // shall only be used for debugging!
 550                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 551
 552         private:
 553                 RefCountPtr< const Lang::PaintedPolygon2D > simple_polygon_to2D( const Concrete::Length eyez, const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights ) const;
 554                 RefCountPtr< const Lang::PaintedPolygon2D > 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;
 555                 RefCountPtr< const Lang::PaintedPolygon2D > 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;
 556                 RefCountPtr< const Lang::PaintedPolygon2D > 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;
 557
 558         protected:
 559                 static void writePacked( std::ostream & os,
 560                                                                                                                  const size_t BITS_PER_COORDINATE, const size_t BITS_PER_COMPONENT, const size_t BITS_PER_FLAG,
 561                                                                                                                  const double x, const double y, const Concrete::Gray & color, const unsigned char flag );
 562                 static void writePackedValue( std::ostream & os, char * rest, size_t * restAvail,
 563                                                                                                                                         unsigned int val, size_t bits );
 564         };
 565
 566         class SingleSidedPolygon3DRGB : public PaintedPolygon3D
 567         {
 568                 RefCountPtr< const Computation::FacetInterpolatorRGB > interpolator_;
 569                 Concrete::Length viewResolution_;
 570                 Computation::FacetShadeOrder shadeOrder_;       // legal values: { 0, 1, 2 }
 571         public:
 572                 SingleSidedPolygon3DRGB( const RefCountPtr< const Computation::FacetInterpolatorRGB > & interpolator,
 573                                                                                                                  bool singleSided, // Confusingly, this type is sometimes used also for double-sided polygons.
 574                                                                                                                  const Concrete::UnitFloatTriple & polygonUnitNormal,
 575                                                                                                                  Concrete::Length m,
 576                                                                                                                  Concrete::Length tiebreaker,
 577                                                                                                                  Concrete::Length viewResolution,
 578                                                                                                                  Computation::FacetShadeOrder shadeOrder );
 579                 virtual ~SingleSidedPolygon3DRGB( );
 580                 virtual RefCountPtr< const Lang::PaintedPolygon2D > polygon_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights ) const;
 581                 virtual RefCountPtr< const Lang::Color > getColor( ) const;              // shall only be used for debugging!
 582                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 583
 584         private:
 585                 RefCountPtr< const Lang::PaintedPolygon2D > simple_polygon_to2D( const Concrete::Length eyez, const Lang::Transform3D & tf, const std::list< RefCountPtr< const Lang::LightSource > > & lights ) const;
 586                 RefCountPtr< const Lang::PaintedPolygon2D > 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;
 587                 RefCountPtr< const Lang::PaintedPolygon2D > 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;
 588                 RefCountPtr< const Lang::PaintedPolygon2D > 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;
 589
 590         protected:
 591                 static void writePacked( std::ostream & os,
 592                                                                                                                  const size_t BITS_PER_COORDINATE, const size_t BITS_PER_COMPONENT, const size_t BITS_PER_FLAG,
 593                                                                                                                  const double x, const double y, const Concrete::RGB & color, const unsigned char flag );
 594                 static void writePackedValue( std::ostream & os, char * rest, size_t * restAvail,
 595                                                                                                                                         unsigned int val, size_t bits );
 596         };
 597
 598         class UndirectedEdge
 599         {
 600                 size_t low_;
 601                 size_t high_;
 602         public:
 603         UndirectedEdge( size_t i0, size_t i1 )
 604                 : low_( i0 ), high_( i1 )
 605                 {
 606                         if( low_ > high_ )
 607                                 {
 608                                         low_ = i1;
 609                                         high_ = i0;
 610                                 }
 611                 }
 612                 size_t low( ) const { return low_; }
 613                 size_t high( ) const { return high_; }
 614                 static UndirectedEdge begin( )
 615                 {
 616                         return UndirectedEdge( 0, 0 );
 617                 }
 618                 static UndirectedEdge end( )
 619                 {
 620                         return UndirectedEdge( INT_MAX, INT_MAX );
 621                 }
 622                 void increment( size_t size )
 623                 {
 624                         ++high_;
 625                         if( high_ >= size )
 626                                 {
 627                                         ++low_;
 628                                         if( low_ >= size )
 629                                                 {
 630                                                         low_ = INT_MAX;
 631                                                         high_ = INT_MAX;
 632                                                         return;
 633                                                 }
 634                                         high_ = low_;
 635                                 }
 636                 }
 637                 bool operator == ( const Computation::UndirectedEdge & other ) const
 638                 {
 639                         return low_ == other.low_ && high_ == other.high_;
 640                 }
 641                 bool operator != ( const Computation::UndirectedEdge & other ) const
 642                 {
 643                         return low_ != other.low_ || high_ != other.high_;
 644                 }
 645         };
 646         bool operator < ( const Computation::UndirectedEdge & p1, const Computation::UndirectedEdge & p2 );
 647
 648         template< class T >
 649                 class UndirectedEdgeMatrix
 650                 {
 651                         size_t size_;
 652                         std::vector< std::vector< T > > mem_;
 653                 public:
 654                         UndirectedEdgeMatrix( size_t size );
 655                         UndirectedEdgeMatrix( size_t size, const T & elem );
 656                         ~UndirectedEdgeMatrix( );
 657                         T & operator [] ( const UndirectedEdge & idx );
 658                         const T & operator [] ( const UndirectedEdge & idx ) const;
 659                 };
 660
 661         }
 662
 663         namespace Lang
 664         {
 665
 666         class Drawable2D : public Lang::Geometric2D
 667         {
 668         public:
 669                 typedef enum { BOUNDING, BLEED } BoxType;
 670         public:
 671                 Drawable2D( );
 672                 virtual ~Drawable2D( );
 673                 virtual void shipout( std::ostream & os, Kernel::PageContentStates * pdfState, const Lang::Transform2D & tf ) const = 0;
 674                 virtual RefCountPtr< const Lang::ElementaryPath2D > bbox( Lang::Drawable2D::BoxType boxType ) const = 0;
 675                 RefCountPtr< const Lang::Transformed2D > typed_transformed( const Lang::Transform2D & tf, const RefCountPtr< const Lang::Drawable2D > & self ) const;
 676                 virtual RefCountPtr< const Lang::Geometric2D > transformed( const Lang::Transform2D & tf, const RefCountPtr< const Lang::Geometric2D > & self ) const;
 677                 virtual RefCountPtr< const Lang::Geometric3D > to3D( const RefCountPtr< const Lang::Geometric2D > & self ) const;
 678                 virtual void findTags( std::vector< Kernel::ValueRef > * dst, const Kernel::PassedDyn & dyn, Lang::Symbol::KeyType key, const Lang::Transform2D & tf ) const;
 679                 virtual bool findOneTag( Kernel::EvalState * evalState, Lang::Symbol::KeyType key, const Lang::Transform2D & tf ) const;
 680                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 681                 TYPEINFODECL;
 682
 683                 DISPATCHDECL;
 684         };
 685
 686         class Group2D : public Lang::Drawable2D
 687         {
 688         public:
 689                 Group2D( );
 690                 virtual ~Group2D( );
 691                 TYPEINFODECL;
 692                 virtual bool isNull( ) const = 0;
 693                 virtual RefCountPtr< const Lang::Group2D > removeShallow( Lang::Symbol::KeyType key ) const = 0;
 694         };
 695
 696         class GroupPair2D : public Lang::Group2D
 697         {
 698                 RefCountPtr< const Kernel::GraphicsState > metaState_;
 699                 RefCountPtr< const Lang::Drawable2D > car_;
 700                 RefCountPtr< const Lang::Group2D > cdr_;
 701         public:
 702                 GroupPair2D( RefCountPtr< const Lang::Drawable2D > car, RefCountPtr< const Lang::Group2D > cdr, const RefCountPtr< const Kernel::GraphicsState > & metaState );
 703                 virtual ~GroupPair2D( );
 704                 virtual bool isNull( ) const;
 705                 virtual void shipout( std::ostream & os, Kernel::PageContentStates * pdfState, const Lang::Transform2D & tf ) const;
 706                 virtual RefCountPtr< const Lang::ElementaryPath2D > bbox( Lang::Drawable2D::BoxType boxType ) const;
 707                 virtual void findTags( std::vector< Kernel::ValueRef > * dst, const Kernel::PassedDyn & dyn, Lang::Symbol::KeyType key, const Lang::Transform2D & tf ) const;
 708                 virtual bool findOneTag( Kernel::EvalState * evalState, Lang::Symbol::KeyType key, const Lang::Transform2D & tf ) const;
 709                 virtual RefCountPtr< const Lang::Group2D > removeShallow( Lang::Symbol::KeyType key ) const;
 710                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 711         protected:
 712                 RefCountPtr< const Lang::ElementaryPath2D > bbox( const RefCountPtr< const Lang::ElementaryPath2D > & carbbox, const RefCountPtr< const Lang::ElementaryPath2D > & cdrbbox ) const;
 713         };
 714
 715         class GroupNull2D : public Lang::Group2D
 716         {
 717         public:
 718                 GroupNull2D( );
 719                 virtual ~GroupNull2D( );
 720                 virtual bool isNull( ) const;
 721                 virtual RefCountPtr< const Lang::Group2D > removeShallow( Lang::Symbol::KeyType key ) const;
 722                 virtual void shipout( std::ostream & os, Kernel::PageContentStates * pdfState, const Lang::Transform2D & tf ) const;
 723                 virtual RefCountPtr< const Lang::ElementaryPath2D > bbox( Lang::Drawable2D::BoxType boxType ) const;
 724         };
 725
 726         class XObject : public Lang::Drawable2D
 727         {
 728                 RefCountPtr< const Kernel::GraphicsState > metaState_;
 729                 RefCountPtr< SimplePDF::PDF_Object > resource_;
 730                 RefCountPtr< const Lang::ElementaryPath2D > boundingbox_;
 731                 RefCountPtr< const Lang::ElementaryPath2D > bleedbox_;
 732                 std::string debugStr_;
 733         public:
 734                 XObject( const RefCountPtr< SimplePDF::PDF_Object > & resource, const RefCountPtr< const Lang::ElementaryPath2D > & boundingbox );
 735                 XObject( const RefCountPtr< SimplePDF::PDF_Object > & resource, const RefCountPtr< const Lang::ElementaryPath2D > & boundingbox, const RefCountPtr< const Lang::ElementaryPath2D > & bleedbox, const RefCountPtr< const Kernel::GraphicsState > & metaState );
 736                 virtual ~XObject( );
 737                 virtual void shipout( std::ostream & os, Kernel::PageContentStates * pdfState, const Lang::Transform2D & tf ) const;
 738                 virtual RefCountPtr< const Lang::ElementaryPath2D > bbox( Lang::Drawable2D::BoxType boxType ) const;
 739                 RefCountPtr< const Lang::XObject > cloneWithState( const RefCountPtr< const Kernel::GraphicsState > & _metaState, Concrete::Length bleedMargin ) const;
 740                 void setDebugStr( const std::string & _debugStr );
 741                 const std::string & getDebugStr( ) const;
 742                 virtual void show( std::ostream & os ) const;
 743                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 744
 745                 RefCountPtr< SimplePDF::PDF_Object > getResource( ) const;
 746         };
 747
 748         class TransparencyGroup : public Lang::XObject
 749         {
 750                 RefCountPtr< const Lang::ColorSpace > colorSpace_;
 751                 RefCountPtr< SimplePDF::PDF_Indirect_out > indirection_;
 752         public:
 753                 TransparencyGroup( const RefCountPtr< SimplePDF::PDF_Indirect_out > & indirection, RefCountPtr< const Lang::ElementaryPath2D > _mybbox, const RefCountPtr< const Lang::ColorSpace > & colorSpace );
 754                 virtual ~TransparencyGroup( );
 755                 RefCountPtr< const Lang::ColorSpace > colorSpace( ) const;
 756                 RefCountPtr< SimplePDF::PDF_Indirect_out > getPDF_Object( ) const;
 757         };
 758
 759         class PaintedPath2D : public Lang::Drawable2D
 760         {
 761         protected:
 762                 RefCountPtr< const Kernel::GraphicsState > metaState_;
 763                 std::list< RefCountPtr< const Lang::ElementaryPath2D > > path_;
 764                 const char * paintCmd_;
 765         public:
 766                 PaintedPath2D( const RefCountPtr< const Kernel::GraphicsState > & metaState,
 767                                                                          const char * paintCmd );
 768                 PaintedPath2D( const RefCountPtr< const Kernel::GraphicsState > & metaState,
 769                                                                          RefCountPtr< const Lang::ElementaryPath2D > path,
 770                                                                          const char * paintCmd );
 771                 PaintedPath2D( const RefCountPtr< const Kernel::GraphicsState > & metaState,
 772                                                                          RefCountPtr< const Lang::MultiPath2D > paths,
 773                                                                          const char * paintCmd );
 774                 virtual ~PaintedPath2D( );
 775                 TYPEINFODECL;
 776                 void addSubPath( RefCountPtr< const Lang::ElementaryPath2D > subpath );
 777                 virtual void shipout( std::ostream & os, Kernel::PageContentStates * pdfState, const Lang::Transform2D & tf ) const;
 778                 virtual RefCountPtr< const Lang::ElementaryPath2D > bbox( Lang::Drawable2D::BoxType boxType ) const;
 779                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 780                 bool isContainedIn( const Lang::Clipped2D * clipping ) const;
 781         };
 782
 783         class PaintedPolygon2D : public Lang::PaintedPath2D
 784         {
 785         public:
 786                 PaintedPolygon2D( RefCountPtr< const Kernel::GraphicsState > metaState, RefCountPtr< const Lang::ElementaryPath2D > path );
 787                 virtual ~PaintedPolygon2D( );
 788                 RefCountPtr< const Lang::Drawable2D > clip( std::list< Computation::ZBufTriangle > * regions, const RefCountPtr< const Lang::PaintedPolygon2D > selfRef ) const;
 789         };
 790
 791         class BBoxed2D : public Lang::PaintedPolygon2D
 792         {
 793         public:
 794                 typedef enum { BOUNDING = 0, BLEED, BOTH } BoxType;
 795         private:
 796                 RefCountPtr< const Lang::ElementaryPath2D > mybbox_;
 797                 RefCountPtr< const Lang::Drawable2D > element_;
 798                 BoxType boxType_;
 799         public:
 800                 BBoxed2D( RefCountPtr< const Lang::Drawable2D > element, RefCountPtr< const Lang::ElementaryPath2D > mybbox, BoxType boxType = BOUNDING );
 801                 virtual ~BBoxed2D( );
 802                 virtual void shipout( std::ostream & os, Kernel::PageContentStates * pdfState, const Lang::Transform2D & tf ) const;
 803                 virtual RefCountPtr< const Lang::ElementaryPath2D > bbox( Lang::Drawable2D::BoxType boxType ) const;
 804                 virtual void findTags( std::vector< Kernel::ValueRef > * dst, const Kernel::PassedDyn & dyn, Lang::Symbol::KeyType key, const Lang::Transform2D & tf ) const;
 805                 virtual bool findOneTag( Kernel::EvalState * evalState, Lang::Symbol::KeyType key, const Lang::Transform2D & tf ) const;
 806                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 807         };
 808
 809         class Transformed2D : public Lang::Drawable2D
 810         {
 811                 Lang::Transform2D mytf_;
 812                 RefCountPtr< const Lang::Drawable2D > element_;
 813         public:
 814                 Transformed2D( RefCountPtr< const Lang::Drawable2D > element, const Lang::Transform2D & mytf );
 815                 virtual ~Transformed2D( );
 816                 virtual void shipout( std::ostream & os, Kernel::PageContentStates * pdfState, const Lang::Transform2D & tf ) const;
 817                 virtual RefCountPtr< const Lang::ElementaryPath2D > bbox( Lang::Drawable2D::BoxType boxType ) const;
 818                 virtual void findTags( std::vector< Kernel::ValueRef > * dst, const Kernel::PassedDyn & dyn, Lang::Symbol::KeyType key, const Lang::Transform2D & tf ) const;
 819                 virtual bool findOneTag( Kernel::EvalState * evalState, Lang::Symbol::KeyType key, const Lang::Transform2D & tf ) const;
 820                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 821         };
 822
 823         class Clipped2D : public Lang::Drawable2D
 824         {
 825                 std::list< RefCountPtr< const Lang::ElementaryPath2D > > clipList_;
 826                 RefCountPtr< const Lang::Drawable2D > element_;
 827                 const char * clipCommand_;
 828         public:
 829                 Clipped2D( const RefCountPtr< const Lang::Drawable2D > & element, const char * clipCommand );
 830                 virtual ~Clipped2D( );
 831                 void addSubPath( const RefCountPtr< const Lang::ElementaryPath2D > & subpath );
 832                 virtual void shipout( std::ostream & os, Kernel::PageContentStates * pdfState, const Lang::Transform2D & tf ) const;
 833                 virtual RefCountPtr< const Lang::ElementaryPath2D > bbox( Lang::Drawable2D::BoxType boxType ) const;
 834                 virtual void findTags( std::vector< Kernel::ValueRef > * dst, const Kernel::PassedDyn & dyn, Lang::Symbol::KeyType key, const Lang::Transform2D & tf ) const;
 835                 virtual bool findOneTag( Kernel::EvalState * evalState, Lang::Symbol::KeyType key, const Lang::Transform2D & tf ) const;
 836                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 837                 RefCountPtr< const Lang::Drawable2D > debugPolys( ) const;
 838                 bool isSingleConvexPoly( Concrete::Length tol ) const;
 839                 bool convexPolyContains( const Concrete::Coords2D & p, Concrete::Length tol ) const;
 840         protected:
 841                 RefCountPtr< const Lang::ElementaryPath2D > bbox( const RefCountPtr< const Lang::ElementaryPath2D > & elem_bbox ) const;
 842         };
 843
 844         class TextMasked2D : public Lang::Drawable2D
 845         {
 846                 RefCountPtr< const Lang::Drawable2D > element_;
 847                 RefCountPtr< const Lang::Text > mask_;
 848         public:
 849                 TextMasked2D( const RefCountPtr< const Lang::Drawable2D > & element, const RefCountPtr< const Lang::Text > & mask );
 850                 virtual ~TextMasked2D( );
 851                 virtual void shipout( std::ostream & os, Kernel::PageContentStates * pdfState, const Lang::Transform2D & tf ) const;
 852                 virtual RefCountPtr< const Lang::ElementaryPath2D > bbox( Lang::Drawable2D::BoxType boxType ) const;
 853                 virtual void findTags( std::vector< Kernel::ValueRef > * dst, const Kernel::PassedDyn & dyn, Lang::Symbol::KeyType key, const Lang::Transform2D & tf ) const;
 854                 virtual bool findOneTag( Kernel::EvalState * evalState, Lang::Symbol::KeyType key, const Lang::Transform2D & tf ) const;
 855                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 856         };
 857
 858         class SoftMasked2D : public Lang::Drawable2D
 859         {
 860                 RefCountPtr< const Lang::Drawable2D > element_;
 861                 RefCountPtr< const Lang::SoftMask > mask_;
 862         public:
 863                 SoftMasked2D( const RefCountPtr< const Lang::Drawable2D > & element, const RefCountPtr< const Lang::SoftMask > & mask );
 864                 virtual ~SoftMasked2D( );
 865                 virtual void shipout( std::ostream & os, Kernel::PageContentStates * pdfState, const Lang::Transform2D & tf ) const;
 866                 virtual RefCountPtr< const Lang::ElementaryPath2D > bbox( Lang::Drawable2D::BoxType boxType ) const;
 867                 virtual void findTags( std::vector< Kernel::ValueRef > * dst, const Kernel::PassedDyn & dyn, Lang::Symbol::KeyType key, const Lang::Transform2D & tf ) const;
 868                 virtual bool findOneTag( Kernel::EvalState * evalState, Lang::Symbol::KeyType key, const Lang::Transform2D & tf ) const;
 869                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 870         };
 871
 872         class Drawable3D : public Lang::Geometric3D
 873         {
 874         public:
 875                 Drawable3D( );
 876                 virtual ~Drawable3D( );
 877                 RefCountPtr< const Lang::Transformed3D > typed_transformed( const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
 878                 virtual RefCountPtr< const Lang::Geometric3D > transformed( const Lang::Transform3D & tf, const RefCountPtr< const Lang::Geometric3D > & self ) const;
 879                 virtual RefCountPtr< const Lang::Geometric2D > to2D( const Kernel::PassedDyn & dyn, const RefCountPtr< const Lang::Geometric3D > & self ) const;
 880                 virtual RefCountPtr< const Lang::Drawable2D > typed_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const = 0;
 881                 virtual void polygonize( std::list< RefCountPtr< Computation::PaintedPolygon3D > > * zBufPile, std::list< RefCountPtr< Computation::StrokedLine3D > > * linePile, const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const = 0;
 882                 virtual void findTags( std::vector< Kernel::ValueRef > * dst, const Kernel::PassedDyn & dyn, Lang::Symbol::KeyType key, const Lang::Transform3D & tf ) const;
 883                 virtual bool findOneTag( Kernel::EvalState * evalState, Lang::Symbol::KeyType key, const Lang::Transform3D & tf ) const;
 884                 TYPEINFODECL;
 885                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 886                 DISPATCHDECL;
 887         };
 888
 889         class Group3D : public Lang::Drawable3D
 890         {
 891         public:
 892                 Group3D( );
 893                 virtual ~Group3D( );
 894                 TYPEINFODECL;
 895                 virtual bool isNull( ) const = 0;
 896                 virtual RefCountPtr< const Lang::Group3D > removeShallow( Lang::Symbol::KeyType key ) const = 0;
 897                 virtual RefCountPtr< const Lang::Drawable2D > typed_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
 898                 virtual RefCountPtr< const Lang::Group2D > group_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf ) const = 0;
 899         };
 900
 901         class GroupPair3D : public Lang::Group3D
 902         {
 903                 RefCountPtr< const Kernel::GraphicsState > metaState_;
 904                 RefCountPtr< const Lang::Drawable3D > car_;
 905                 RefCountPtr< const Lang::Group3D > cdr_;
 906         public:
 907                 GroupPair3D( const RefCountPtr< const Lang::Drawable3D > & car, const RefCountPtr< const Lang::Group3D > & cdr, const RefCountPtr< const Kernel::GraphicsState > & metaState );
 908                 virtual ~GroupPair3D( );
 909                 virtual bool isNull( ) const;
 910                 virtual RefCountPtr< const Lang::Group2D > group_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf ) const;
 911                 virtual void polygonize( std::list< RefCountPtr< Computation::PaintedPolygon3D > > * zBufPile, std::list< RefCountPtr< Computation::StrokedLine3D > > * linePile, const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
 912                 virtual void findTags( std::vector< Kernel::ValueRef > * dst, const Kernel::PassedDyn & dyn, Lang::Symbol::KeyType key, const Lang::Transform3D & tf ) const;
 913                 virtual bool findOneTag( Kernel::EvalState * evalState, Lang::Symbol::KeyType key, const Lang::Transform3D & tf ) const;
 914                 virtual RefCountPtr< const Lang::Group3D > removeShallow( Lang::Symbol::KeyType key ) const;
 915                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 916         };
 917
 918         class GroupNull3D : public Lang::Group3D
 919         {
 920         public:
 921                 GroupNull3D( );
 922                 virtual ~GroupNull3D( );
 923                 virtual bool isNull( ) const;
 924                 virtual RefCountPtr< const Lang::Group2D > group_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf ) const;
 925                 virtual void polygonize( std::list< RefCountPtr< Computation::PaintedPolygon3D > > * zBufPile, std::list< RefCountPtr< Computation::StrokedLine3D > > * linePile, const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
 926                 virtual RefCountPtr< const Lang::Group3D > removeShallow( Lang::Symbol::KeyType key ) const;
 927         };
 928
 929         class Drawable2Din3D : public Lang::Drawable3D
 930         {
 931                 RefCountPtr< const Lang::Drawable2D > element_;
 932         public:
 933                 Drawable2Din3D( RefCountPtr< const Lang::Drawable2D > element );
 934                 virtual ~Drawable2Din3D( );
 935                 virtual RefCountPtr< const Lang::Drawable2D > typed_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
 936                 virtual void polygonize( std::list< RefCountPtr< Computation::PaintedPolygon3D > > * zBufPile, std::list< RefCountPtr< Computation::StrokedLine3D > > * linePile, const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
 937                 virtual void findTags( std::vector< Kernel::ValueRef > * dst, const Kernel::PassedDyn & dyn, Lang::Symbol::KeyType key, const Lang::Transform3D & tf ) const;
 938                 virtual bool findOneTag( Kernel::EvalState * evalState, Lang::Symbol::KeyType key, const Lang::Transform3D & tf ) const;
 939                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 940         };
 941
 942         class Facing2Din3D : public Lang::Drawable3D
 943         {
 944                 RefCountPtr< const Lang::Drawable2D > element_;
 945                 bool scale_;
 946                 bool distort_;
 947         public:
 948                 Facing2Din3D( RefCountPtr< const Lang::Drawable2D > element, bool scale, bool distort );
 949                 virtual ~Facing2Din3D( );
 950                 virtual RefCountPtr< const Lang::Drawable2D > typed_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
 951                 virtual void polygonize( std::list< RefCountPtr< Computation::PaintedPolygon3D > > * zBufPile, std::list< RefCountPtr< Computation::StrokedLine3D > > * linePile, const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
 952                 virtual void findTags( std::vector< Kernel::ValueRef > * dst, const Kernel::PassedDyn & dyn, Lang::Symbol::KeyType key, const Lang::Transform3D & tf ) const;
 953                 virtual bool findOneTag( Kernel::EvalState * evalState, Lang::Symbol::KeyType key, const Lang::Transform3D & tf ) const;
 954                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 955         };
 956
 957         class FacingFunction3D : public Lang::Drawable3D
 958         {
 959                 Kernel::PassedDyn dyn_;
 960                 RefCountPtr< const Lang::Function > generator_;
 961         public:
 962                 FacingFunction3D( Kernel::PassedDyn dyn, RefCountPtr< const Lang::Function > generator );
 963                 virtual ~FacingFunction3D( );
 964                 virtual RefCountPtr< const Lang::Drawable2D > typed_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
 965                 virtual void polygonize( std::list< RefCountPtr< Computation::PaintedPolygon3D > > * zBufPile, std::list< RefCountPtr< Computation::StrokedLine3D > > * linePile, const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
 966                 virtual void findTags( std::vector< Kernel::ValueRef > * dst, const Kernel::PassedDyn & dyn, Lang::Symbol::KeyType key, const Lang::Transform3D & tf ) const;
 967                 virtual bool findOneTag( Kernel::EvalState * evalState, Lang::Symbol::KeyType key, const Lang::Transform3D & tf ) const;
 968                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 969         };
 970
 971         class PaintedPath3D : public Lang::Drawable3D
 972         {
 973                 RefCountPtr< const Kernel::GraphicsState > metaState_;
 974                 std::list< RefCountPtr< const Lang::ElementaryPath3D > > path_;
 975                 const char * paintCmd_;
 976         protected:
 977                 Concrete::Length tiebreaker_;   // This is used to break ties in the z-buffer.
 978         public:
 979                 PaintedPath3D( RefCountPtr< const Kernel::GraphicsState > metaState,
 980                                                                          const char * paintCmd,
 981                                                                          Concrete::Length tiebreaker = Concrete::ZERO_LENGTH );
 982                 PaintedPath3D( RefCountPtr< const Kernel::GraphicsState > metaState,
 983                                                                          RefCountPtr< const Lang::ElementaryPath3D > path,
 984                                                                          const char * paintCmd,
 985                                                                          Concrete::Length tiebreaker = Concrete::ZERO_LENGTH );
 986                 PaintedPath3D( RefCountPtr< const Kernel::GraphicsState > metaState,
 987                                                                          RefCountPtr< const Lang::MultiPath3D > paths,
 988                                                                          const char * paintCmd,
 989                                                                          Concrete::Length tiebreaker = Concrete::ZERO_LENGTH );
 990                 virtual ~PaintedPath3D( );
 991                 TYPEINFODECL;
 992                 void addSubPath( RefCountPtr< const Lang::ElementaryPath3D > subpath );
 993                 virtual RefCountPtr< const Lang::Drawable2D > typed_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
 994                 virtual void polygonize( std::list< RefCountPtr< Computation::PaintedPolygon3D > > * zBufPile, std::list< RefCountPtr< Computation::StrokedLine3D > > * linePile, const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
 995                 virtual void gcMark( Kernel::GCMarkedSet & marked );
 996         };
 997
 998         class SingleSided3DGray : public Lang::Drawable3D
 999         {
1000                 // This is a historical note worth to remember.
1001                 // It doesn't make sense to store Computation::PaintedPolygon3D in a Lang:: object, since a Computation::PaintedPolygon3D cannot be transformed
1002                 // but must be created at its final position, while a Lang:: object can be transformed.
1003                 // In a class like this, one can only store stuff that enables us to create the Computation:: object later when the Transform3D is known.
1004
1005                 RefCountPtr< const Lang::ElementaryPath3D > points_;
1006                 RefCountPtr< const Computation::FacetInterpolatorGray > interpolator_;
1007                 bool singleSided_;
1008                 Concrete::UnitFloatTriple polygonUnitNormal_;
1009                 Concrete::Length m_;
1010                 Concrete::Length tiebreaker_;   // This is used to break ties in the z-buffer.
1011                 Concrete::Length viewResolution_;
1012                 Computation::FacetShadeOrder shadeOrder_;
1013         public:
1014                 SingleSided3DGray( const RefCountPtr< const Lang::ElementaryPath3D > & points,
1015                                                                                          const RefCountPtr< const Computation::FacetInterpolatorGray > & interpolator,
1016                                                                                          bool singleSided,      // Confusing, but true; this type is curretly sometimes used also for double-sided objects.
1017                                                                                          const Concrete::UnitFloatTriple & polygonUnitNormal,
1018                                                                                          Concrete::Length m,
1019                                                                                          Concrete::Length tiebreaker,
1020                                                                                          Concrete::Length viewResolution,
1021                                                                                          Computation::FacetShadeOrder shadeOrder );
1022                 virtual ~SingleSided3DGray( );
1023                 TYPEINFODECL;
1024                 virtual RefCountPtr< const Lang::Drawable2D > typed_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
1025                 virtual void polygonize( std::list< RefCountPtr< Computation::PaintedPolygon3D > > * zBufPile, std::list< RefCountPtr< Computation::StrokedLine3D > > * linePile, const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
1026                 virtual void gcMark( Kernel::GCMarkedSet & marked );
1027         };
1028
1029         class SingleSided3DRGB : public Lang::Drawable3D
1030         {
1031                 // This is a historical note worth to remember.
1032                 // It doesn't make sense to store Computation::PaintedPolygon3D in a Lang:: object, since a Computation::PaintedPolygon3D cannot be transformed
1033                 // but must be created at its final position, while a Lang:: object can be transformed.
1034                 // In a class like this, one can only store stuff that enables us to create the Computation:: object later when the Transform3D is known.
1035
1036                 RefCountPtr< const Lang::ElementaryPath3D > points_;
1037                 RefCountPtr< const Computation::FacetInterpolatorRGB > interpolator_;
1038                 bool singleSided_;
1039                 Concrete::UnitFloatTriple polygonUnitNormal_;
1040                 Concrete::Length m_;
1041                 Concrete::Length tiebreaker_;   // This is used to break ties in the z-buffer.
1042                 Concrete::Length viewResolution_;
1043                 Computation::FacetShadeOrder shadeOrder_;
1044         public:
1045                 SingleSided3DRGB( const RefCountPtr< const Lang::ElementaryPath3D > & points,
1046                                                                                          const RefCountPtr< const Computation::FacetInterpolatorRGB > & interpolator,
1047                                                                                          bool singleSided,      // Confusing, but true; this type is curretly sometimes used also for double-sided objects.
1048                                                                                          const Concrete::UnitFloatTriple & polygonUnitNormal,
1049                                                                                          Concrete::Length m,
1050                                                                                          Concrete::Length tiebreaker,
1051                                                                                          Concrete::Length viewResolution,
1052                                                                                          Computation::FacetShadeOrder shadeOrder );
1053                 virtual ~SingleSided3DRGB( );
1054                 TYPEINFODECL;
1055                 virtual RefCountPtr< const Lang::Drawable2D > typed_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
1056                 virtual void polygonize( std::list< RefCountPtr< Computation::PaintedPolygon3D > > * zBufPile, std::list< RefCountPtr< Computation::StrokedLine3D > > * linePile, const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
1057                 virtual void gcMark( Kernel::GCMarkedSet & marked );
1058         };
1059
1060         class ZBuf : public Lang::Drawable3D
1061         {
1062                 const RefCountPtr< const Kernel::GraphicsState > metaState_;
1063                 const RefCountPtr< std::list< RefCountPtr< Computation::PaintedPolygon3D > > > pile_;
1064                 const RefCountPtr< std::list< RefCountPtr< Computation::StrokedLine3D > > > linePile_;
1065                 const RefCountPtr< std::list< RefCountPtr< const Lang::LightSource > > > lightPile_;
1066         public:
1067                 ZBuf( const RefCountPtr< std::list< RefCountPtr< Computation::PaintedPolygon3D > > > & pile, const RefCountPtr< std::list< RefCountPtr< Computation::StrokedLine3D > > > & linePile, const RefCountPtr< std::list< RefCountPtr< const Lang::LightSource > > > & lightPile, const RefCountPtr< const Kernel::GraphicsState > & metaState );
1068                 virtual ~ZBuf( );
1069                 virtual RefCountPtr< const Lang::Drawable2D > typed_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
1070                 virtual void polygonize( std::list< RefCountPtr< Computation::PaintedPolygon3D > > * zBufPile, std::list< RefCountPtr< Computation::StrokedLine3D > > * linePile, const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
1071                 virtual void gcMark( Kernel::GCMarkedSet & marked );
1072                 typedef std::list< size_t > PolyIndices;
1073                 class IndexRepresentation;
1074         private:
1075                 static void mergeTriangles( std::list< Computation::ZBufTriangle > * triangles );
1076                 static void recombineTriangles( std::list< Computation::ZBufTriangle > * mergedTriangles );
1077
1078                 // The return value is false if the edge was not added due to a conflict.
1079                 static bool addEdge( Computation::UndirectedEdgeMatrix< std::pair< bool, std::list< IndexRepresentation * > > > * edgeMarix, const Computation::UndirectedEdge & edge, IndexRepresentation * indRep, std::list< Computation::UndirectedEdge > * jobQueue, const std::vector< Concrete::Coords2D > & cornerMem );
1080
1081                 static void removeEdge( Computation::UndirectedEdgeMatrix< std::pair< bool, std::list< IndexRepresentation * > > > * edgeMarix, const Computation::UndirectedEdge & edge, IndexRepresentation * indRep );
1082                 static bool areAligned( const Concrete::Coords2D p0, const Concrete::Coords2D p1, const Concrete::Coords2D p2 );
1083                 static bool areAlignedAndOrdered( const Concrete::Coords2D p0, const Concrete::Coords2D p1, const Concrete::Coords2D p2 );
1084                 static void addEdges( PolyIndices * poly, Computation::UndirectedEdgeMatrix< std::list< PolyIndices * > > * edgeMatrix );
1085                 static void addEdge( Computation::UndirectedEdgeMatrix< std::list< PolyIndices * > > * edgeMatrix, size_t ia, size_t ib, PolyIndices * indRep );
1086                 static bool extendPoly( PolyIndices * poly, const Computation::UndirectedEdge & edge, size_t iNew, Computation::UndirectedEdgeMatrix< std::list< PolyIndices * > > * edgeMatrix, const std::vector< Concrete::Coords2D > & cornerMem, bool convex );
1087         public:
1088                 static void trianglesToPolys( std::list< Computation::ZBufTriangle > * triangles, Lang::Clipped2D * dst );
1089         };
1090
1091                 // The ZSorter class is very similar to ZBuf, but uses another algorithm to display itself
1092         class ZSorter : public Lang::Drawable3D
1093         {
1094                 const RefCountPtr< const Kernel::GraphicsState > metaState_;
1095                 const RefCountPtr< std::list< RefCountPtr< Computation::PaintedPolygon3D > > > pile_;
1096                 const RefCountPtr< std::list< RefCountPtr< Computation::StrokedLine3D > > > linePile_;
1097                 const RefCountPtr< std::list< RefCountPtr< const Lang::LightSource > > > lightPile_;
1098         public:
1099                 ZSorter( const RefCountPtr< std::list< RefCountPtr< Computation::PaintedPolygon3D > > > & pile, const RefCountPtr< std::list< RefCountPtr< Computation::StrokedLine3D > > > & linePile, const RefCountPtr< std::list< RefCountPtr< const Lang::LightSource > > > & lightPile, const RefCountPtr< const Kernel::GraphicsState > & metaState );
1100                 virtual ~ZSorter( );
1101                 virtual RefCountPtr< const Lang::Drawable2D > typed_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
1102                 virtual void polygonize( std::list< RefCountPtr< Computation::PaintedPolygon3D > > * zBufPile, std::list< RefCountPtr< Computation::StrokedLine3D > > * linePile, const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
1103                 virtual void gcMark( Kernel::GCMarkedSet & marked );
1104         };
1105
1106         class Transformed3D : public Lang::Drawable3D
1107         {
1108                 Lang::Transform3D mytf_;
1109                 RefCountPtr< const Lang::Drawable3D > element_;
1110         public:
1111                 Transformed3D( RefCountPtr< const Lang::Drawable3D > element, const Lang::Transform3D & mytf );
1112                 virtual ~Transformed3D( );
1113                 virtual RefCountPtr< const Lang::Drawable2D > typed_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
1114                 virtual void polygonize( std::list< RefCountPtr< Computation::PaintedPolygon3D > > * zBufPile, std::list< RefCountPtr< Computation::StrokedLine3D > > * linePile, const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const;
1115                 virtual void findTags( std::vector< Kernel::ValueRef > * dst, const Kernel::PassedDyn & dyn, Lang::Symbol::KeyType key, const Lang::Transform3D & tf ) const;
1116                 virtual bool findOneTag( Kernel::EvalState * evalState, Lang::Symbol::KeyType key, const Lang::Transform3D & tf ) const;
1117                 virtual void gcMark( Kernel::GCMarkedSet & marked );
1118         };
1119
1120         class Text : public Lang::Drawable2D
1121         {
1122                 RefCountPtr< const Kernel::GraphicsState > metaState_;
1123                 RefCountPtr< const Kernel::TextState > textState_;
1124                 RefCountPtr< const std::list< RefCountPtr< const Lang::TextOperation > > > elements_;
1125                 RefCountPtr< const Lang::ElementaryPath2D > mybbox_;
1126         public:
1127                 Text( const RefCountPtr< const Kernel::GraphicsState > & metaState, const RefCountPtr< const Kernel::TextState > & textState, const RefCountPtr< const std::list< RefCountPtr< const Lang::TextOperation > > > & elements, const RefCountPtr< const Lang::ElementaryPath2D > & mybbox );
1128                 virtual ~Text( );
1129                 virtual void shipout( std::ostream & os, Kernel::PageContentStates * pdfState, const Lang::Transform2D & tf ) const;
1130                 void shipout_clip( std::ostream & os, Kernel::PageContentStates * pdfState, const Lang::Transform2D & tf ) const;
1131                 virtual RefCountPtr< const Lang::ElementaryPath2D > bbox( Lang::Drawable2D::BoxType boxType ) const;
1132                 virtual void gcMark( Kernel::GCMarkedSet & marked );
1133         };
1134
1135         }
1136
1137         namespace Helpers
1138         {
1139
1140         RefCountPtr< const Lang::Group2D >
1141                 newGroup2D( const RefCountPtr< const Kernel::GraphicsState > & metaState, const RefCountPtr< const Lang::Drawable2D > & obj2, const RefCountPtr< const Lang::Drawable2D > & obj1 );
1142         RefCountPtr< const Lang::Group2D >
1143                 newGroup2D( const RefCountPtr< const Kernel::GraphicsState > & metaState, const RefCountPtr< const Lang::Drawable2D > & obj3, const RefCountPtr< const Lang::Drawable2D > & obj2, const RefCountPtr< const Lang::Drawable2D > & obj1 );
1144
1145         RefCountPtr< const Lang::Group3D >
1146                 newGroup3D( const RefCountPtr< const Kernel::GraphicsState > & metaState, const RefCountPtr< const Lang::Drawable3D > & obj2, const RefCountPtr< const Lang::Drawable3D > & obj1 );
1147         RefCountPtr< const Lang::Group3D >
1148                 newGroup3D( const RefCountPtr< const Kernel::GraphicsState > & metaState, const RefCountPtr< const Lang::Drawable3D > & obj3, const RefCountPtr< const Lang::Drawable3D > & obj2, const RefCountPtr< const Lang::Drawable3D > & obj1 );
1149
1150
1151         RefCountPtr< const Lang::TransparencyGroup >
1152                 newTransparencyGroup( const RefCountPtr< const Lang::Group2D > & content, bool isolated, bool knockout, const RefCountPtr< const Lang::ColorSpace > & blendSpace );
1153
1154         RefCountPtr< const Lang::TransparencyGroup >
1155                 newSolidTransparencyGroup( const RefCountPtr< const Lang::Drawable2D > & obj2, const RefCountPtr< const Lang::Drawable2D > & obj1 );
1156         RefCountPtr< const Lang::TransparencyGroup >
1157                 newSolidTransparencyGroup( const RefCountPtr< const Lang::Drawable2D > & obj3, const RefCountPtr< const Lang::Drawable2D > & obj2, const RefCountPtr< const Lang::Drawable2D > & obj1 );
1158
1159         }
1160
1161 }
1162
1163
1164 template< class T >
1165 ::Shapes::Computation::UndirectedEdgeMatrix< T >::UndirectedEdgeMatrix( size_t size )
1166 : size_( size )
1167 {
1168         mem_.reserve( size_ );
1169         for( size_t row = 0; row < size_; ++row )
1170                 {
1171                         mem_.push_back( std::vector< T >( ) );
1172                         mem_.back( ).resize( size_ - row );
1173                 }
1174 }
1175
1176 template< class T >
1177 ::Shapes::Computation::UndirectedEdgeMatrix< T >::UndirectedEdgeMatrix( size_t size, const T & elem )
1178 : size_( size )
1179 {
1180         mem_.reserve( size_ );
1181         for( size_t row = 0; row < size_; ++row )
1182                 {
1183                         mem_.push_back( std::vector< T >( ) );
1184                         mem_.back( ).resize( size_ - row, elem );
1185                 }
1186 }
1187
1188 template< class T >
1189 ::Shapes::Computation::UndirectedEdgeMatrix< T >::~UndirectedEdgeMatrix( )
1190 { }
1191
1192 template< class T >
1193 T &
1194 ::Shapes::Computation::UndirectedEdgeMatrix< T >::operator [] ( const UndirectedEdge & idx )
1195 {
1196         size_t low = idx.low( );
1197         return mem_[ low ][ idx.high( ) - low ];
1198 }
1199
1200 template< class T >
1201 const T &
1202 ::Shapes::Computation::UndirectedEdgeMatrix< T >::operator [] ( const UndirectedEdge & idx ) const
1203 {
1204         size_t low = idx.low( );
1205         return mem_[ low ][ idx.high( ) - low ];
1206 }