source/zbufto2D.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 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 "angleselect.h"
  26 #include "astvar.h"
  27 #include "astclass.h"
  28 #include "statetypes.h"
  29 #include "lighttypes.h"
  30 #include "shadingtypes.h"
  31 #include "globals.h"
  32
  33 #include <ctype.h>
  34 #include <list>
  35 #include <algorithm>
  36
  37 using namespace Shapes;
  38
  39 #define SPLICEDEBUG( code ) // code
  40
  41
  42 RefCountPtr< const Lang::Drawable2D >
  43 Lang::ZBuf::typed_to2D( const Kernel::PassedDyn & dyn, const Lang::Transform3D & tf, const RefCountPtr< const Lang::Drawable3D > & self ) const
  44 {
  45         Concrete::Length eyez = dyn->getEyeZ( );
  46
  47         std::list< RefCountPtr< const Lang::LightSource > > commonLights;
  48         std::list< RefCountPtr< const Lang::LightSource > > allShadowLights;
  49
  50         {
  51                 typedef typeof *lightPile_ PileType;
  52                 for( PileType::const_iterator src = lightPile_->begin( ); src != lightPile_->end( ); ++src )
  53                         {
  54                                 if( (*src)->shadows( ) )
  55                                         {
  56                                                 allShadowLights.push_back( (*src)->typed_transformed( tf ) );
  57                                         }
  58                                 else
  59                                         {
  60                                                 commonLights.push_back( (*src)->typed_transformed( tf ) );
  61                                         }
  62                         }
  63         }
  64
  65         if( ! allShadowLights.empty( ) )
  66                 {
  67                         throw Exceptions::NotImplemented( "Shadow lights in ZBuf::typed_to2D" );
  68                 }
  69
  70         size_t debugCounter = 0;
  71
  72         // There is one queue per original object.      This structure will be where all the
  73         // triangles resides at the beginning of the treatment of each shadow light or the
  74         // view occlusion computation.
  75         //
  76         // We begin by initializing these queues.
  77         std::list< std::list< Computation::ZBufTriangle > * > triangleQueues;
  78         {
  79                 typedef typeof *pile_ PileType;
  80                 for( PileType::const_iterator src = pile_->begin( ); src != pile_->end( ); ++src )
  81                         {
  82                                 std::list< Computation::ZBufTriangle > * triangleQueue = new std::list< Computation::ZBufTriangle >;
  83                                 (*src)->push_zBufTriangles( tf, eyez, triangleQueue );
  84                                 triangleQueues.push_back( triangleQueue );
  85                         }
  86         }
  87
  88         // The vectors triangleQueue and disjointTriangles share indices in the sense that same indices points to
  89         // triangles with the same origin.
  90         std::list< std::list< Computation::ZBufTriangle > * > disjointTriangles;
  91         std::list< std::list< Computation::ZBufTriangle > * > occludedTriangles;
  92
  93         for( std::list< std::list< Computation::ZBufTriangle > * >::iterator src = triangleQueues.begin( );
  94                          src != triangleQueues.end( ); ++src )
  95                 {
  96                         std::list< Computation::ZBufTriangle > * triangleQueue = *src;
  97
  98                         std::list< Computation::ZBufTriangle > * currentDisjoint = new std::list< Computation::ZBufTriangle >;
  99                         std::list< Computation::ZBufTriangle > * currentOccluded = new std::list< Computation::ZBufTriangle >;
 100
 101                         while( ! triangleQueue->empty( ) )
 102                                 {
 103                                         SPLICEDEBUG( std::cerr << "====( Debug step number " << debugCounter << " )====" << std::endl );
 104                                         Computation::ZBufTriangle current = triangleQueue->front( );
 105                                         triangleQueue->pop_front( );
 106
 107                                         typedef typeof disjointTriangles ListType;
 108                                         bool foundOverlap = false;
 109                                         ListType::iterator iOccluded = occludedTriangles.begin( );
 110                                         for( ListType::iterator iDisjoint = disjointTriangles.begin( ); iDisjoint != disjointTriangles.end( );
 111                                                          ++iDisjoint, ++iOccluded )
 112                                                 {
 113                                                         typedef typeof **iDisjoint SubListType;
 114                                                         for( SubListType::iterator j = (*iDisjoint)->begin( ); j != (*iDisjoint)->end( ); ++j )
 115                                                                 {
 116                                                                         if( current.overlaps( *j ) )
 117                                                                                 {
 118                                                                                         Computation::ZBufTriangle tOld( *j );
 119                                                                                         (*iDisjoint)->erase( j );
 120                                                                                         Computation::ZBufTriangle::splice( tOld, current,
 121                                                                                                                                                                                                                                  *iDisjoint, *iOccluded,
 122                                                                                                                                                                                                                                  currentDisjoint, currentOccluded,
 123                                                                                                                                                                                                                                  triangleQueue );
 124                                                                                         mergeTriangles( *iDisjoint );
 125                                                                                         recombineTriangles( *iOccluded );
 126                                                                                         foundOverlap = true;
 127                                                                                         goto doublebreak;
 128                                                                                 }
 129                                                                 }
 130                                                 }
 131                                 doublebreak:
 132                                         if( ! foundOverlap )
 133                                                 {
 134                                                         currentDisjoint->push_back( current );
 135                                                 }
 136                                 }
 137
 138                         mergeTriangles( currentDisjoint );
 139                         recombineTriangles( currentDisjoint );
 140                         disjointTriangles.push_back( currentDisjoint );
 141
 142                         mergeTriangles( currentOccluded );
 143                         recombineTriangles( currentOccluded );
 144                         occludedTriangles.push_back( currentOccluded );
 145
 146                         ++debugCounter;
 147                         if( debugCounter >= Interaction::debugStep )
 148                                 {
 149                                         //                                      break;
 150                                 }
 151                 }
 152
 153         {
 154                 size_t sum = 0;
 155                 typedef typeof disjointTriangles ListType;
 156                 for( ListType::const_iterator i = disjointTriangles.begin( ); i != disjointTriangles.end( ); ++i )
 157                         {
 158                                 sum += (*i)->size( );
 159                         }
 160         }
 161
 162         // It is now time to take care of the lines.
 163         // The first thing we shall do is to remove what is occluded by triangles.
 164         // Note that triangles will be drawn before the lines, and that is the only way lines
 165         // can occlude triangles.
 166         // Then, we make sure that the lines are drawn in back-to-front order, clipping occluded lines
 167         // behind the line occluding them to avoid cyclic locking.
 168
 169         std::list< const Computation::ZBufLine * > lineQueue;
 170         {
 171                 typedef typeof *linePile_ PileType;
 172                 for( PileType::const_iterator src = linePile_->begin( ); src != linePile_->end( ); ++src )
 173                         {
 174                                 (*src)->push_zBufLine( tf, eyez, & lineQueue );
 175                         }
 176         }
 177
 178         std::list< const Computation::ZBufLine * > disjointLines;
 179         while( ! lineQueue.empty( ) )
 180                 {
 181
 182                         std::list< const Computation::ZBufLine * > queue1;
 183                         std::list< const Computation::ZBufLine * > queue2;
 184
 185                         std::list< const Computation::ZBufLine * > * currentQueue = & queue1;
 186                         std::list< const Computation::ZBufLine * > * otherQueue = & queue2;
 187
 188                         currentQueue->push_back( lineQueue.front( ) );
 189                         lineQueue.pop_front( );
 190
 191                         typedef typeof disjointTriangles ListType;
 192                         for( ListType::const_iterator i = disjointTriangles.begin( ); i != disjointTriangles.end( ); ++i )
 193                                 {
 194                                         typedef typeof **i SubListType;
 195                                         for( SubListType::iterator j = (*i)->begin( ); j != (*i)->end( ); ++j )
 196                                                 {
 197                                                         while( ! currentQueue->empty( ) )
 198                                                                 {
 199                                                                         const Computation::ZBufLine * currentLine = currentQueue->front( );
 200                                                                         currentQueue->pop_front( );
 201                                                                         if( currentLine->overlaps( *j ) )
 202                                                                                 {
 203                                                                                         currentLine->splice( *j, otherQueue );
 204                                                                                         delete currentLine;
 205                                                                                 }
 206                                                                         else
 207                                                                                 {
 208                                                                                         otherQueue->push_back( currentLine );
 209                                                                                 }
 210                                                                 }
 211
 212                                                         {
 213                                                                 // swap the queues
 214                                                                 std::list< const Computation::ZBufLine * > * tmp = currentQueue;
 215                                                                 currentQueue = otherQueue;
 216                                                                 otherQueue = tmp;
 217                                                         }
 218                                                 }
 219                                 }
 220
 221                         // When we reach here the line segments are in currentQueue.
 222                         // These segments are ready to be inserted in the line z buffer.
 223
 224                         // The algorithm below is inefficient, because it will generally make the overlap comparison
 225                         // several times for any overlaping pair of line segments.
 226                         while( ! currentQueue->empty( ) )
 227                                 {
 228                                         const Computation::ZBufLine * current = currentQueue->front( );
 229                                         currentQueue->pop_front( );
 230
 231                                         bool foundOverlap = false;
 232                                         typedef typeof disjointLines ListType;
 233                                         for( ListType::iterator i = disjointLines.begin( ); i != disjointLines.end( );
 234                                                          ++i )
 235                                                 {
 236                                                         if( current->overlaps( **i ) )
 237                                                                 {
 238                                                                         disjointLines.erase( i );
 239                                                                         // Note that splice is responsible for deleting that of *i and current which is not used.
 240                                                                         Computation::ZBufLine::splice( *i, current,
 241                                                                                                                                                                                                  & disjointLines,
 242                                                                                                                                                                                                  currentQueue );
 243                                                                         foundOverlap = true;
 244                                                                         break;
 245                                                                 }
 246                                                 }
 247                                         if( ! foundOverlap )
 248                                                 {
 249                                                         disjointLines.push_back( current );
 250                                                 }
 251                                 }
 252                 }
 253
 254
 255         RefCountPtr< const Lang::Group2D > res = Lang::THE_NULL2D;
 256
 257         const bool SHOW_TRIXELS = false;
 258         if( SHOW_TRIXELS )
 259                 {
 260                         // This is a debug mode
 261
 262                         typedef typeof disjointTriangles ListType;
 263                         for( ListType::const_iterator i = disjointTriangles.begin( ); i != disjointTriangles.end( ); ++i )
 264                                 {
 265                                         typedef typeof **i SubListType;
 266                                         for( SubListType::iterator j = (*i)->begin( ); j != (*i)->end( ); ++j )
 267                                                 {
 268                                                         res = RefCountPtr< const Lang::Group2D >( new Lang::GroupPair2D( j->debugFrame( ),
 269                                                                                                                                                                                                                                                                                                                          res,
 270                                                                                                                                                                                                                                                                                                                          metaState_ ) );
 271                                                 }
 272                                 }
 273                 }
 274         else
 275                 {
 276                         // This is the standard mode
 277
 278                         size_t commonLightCount = commonLights.size( );
 279
 280                         typedef typeof disjointTriangles ListType;
 281                         for( ListType::iterator i = disjointTriangles.begin( ); i != disjointTriangles.end( ); ++i )
 282                                 {
 283                                         if( (*i)->empty( ) )
 284                                                 {
 285                                                         continue;
 286                                                 }
 287                                         typedef std::list< RefCountPtr< const Lang::LightSource > > ShadowLightListType;
 288                                         const ShadowLightListType & shadowLights = (*i)->front( ).shadowLights_;
 289                                         for( ShadowLightListType::const_iterator l = shadowLights.begin( ); l != shadowLights.end( ); ++l )
 290                                                 {
 291                                                         commonLights.push_back( *l );
 292                                                 }
 293                                         RefCountPtr< const Lang::PaintedPolygon2D > tmp = (*i)->front( ).painter_->polygon_to2D( dyn, tf, commonLights );
 294                                         while( commonLights.size( ) > commonLightCount )
 295                                                 {
 296                                                         commonLights.pop_back( );
 297                                                 }
 298
 299                                         // The following statement will consume the objects in the list pointed to by *i
 300                                         res = RefCountPtr< const Lang::Group2D >( new Lang::GroupPair2D( tmp->clip( *i, tmp ),
 301                                                                                                                                                                                                                                                                                                          res,
 302                                                                                                                                                                                                                                                                                                          metaState_ ) );
 303                                 }
 304                 }
 305
 306
 307         while( ! disjointTriangles.empty ( ) )
 308                 {
 309                         delete disjointTriangles.back( );
 310                         disjointTriangles.pop_back( );
 311
 312                         delete occludedTriangles.back( );
 313                         occludedTriangles.pop_back( );
 314                 }
 315
 316         while( ! triangleQueues.empty( ) )
 317                 {
 318                         delete triangleQueues.back( );
 319                         triangleQueues.pop_back( );
 320                 }
 321
 322
 323         // Finally we draw the lines.
 324         while( ! disjointLines.empty( ) )
 325                 {
 326                         const Computation::ZBufLine * current = disjointLines.front( );
 327                         disjointLines.pop_front( );
 328                         res = RefCountPtr< const Lang::Group2D >( new Lang::GroupPair2D( current->stroke2D( ),
 329                                                                                                                                                                                                                                                                                          res,
 330                                                                                                                                                                                                                                                                                          metaState_ ) );
 331                         delete current;
 332                 }
 333
 334
 335         return res;
 336 }
 337