1 /* This file is part of Shapes.
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
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.
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/>.
16 * Copyright 2008, 2010 Henrik Tidefelt
21 #include "shapestypes.h"
22 #include "shapesexceptions.h"
25 #include "angleselect.h"
28 #include "statetypes.h"
29 #include "lighttypes.h"
30 #include "shadingtypes.h"
32 #include "zbufinternals.h"
33 #include "constructorrepresentation.h"
40 using namespace Shapes
;
49 // This is not the most natural place to define CompoundObject, but since we need it...
50 typedef std::list
< Computation::ZBufTriangle
> CompoundObject
;
52 CompoundObject::iterator splitted_
;
53 std::vector
< CompoundObject
* >::iterator splittingObject_
;
54 CompoundObject::iterator splitting_
;
56 SplitJob( const CompoundObject::iterator
& splitted
, const std::vector
< CompoundObject
* >::iterator
& splittingObject
, const CompoundObject::iterator
& splitting
)
57 : splitted_( splitted
), splittingObject_( splittingObject
), splitting_( splitting
)
64 RefCountPtr
< const Lang::Drawable2D
>
65 Lang::ZSorter::typed_to2D( const Kernel::PassedDyn
& dyn
, const Lang::Transform3D
& tf
, const RefCountPtr
< const Lang::Drawable3D
> & self
) const
67 Concrete::Length eyez
= dyn
->getEyeZ( );
69 std::list
< RefCountPtr
< const Lang::LightSource
> > commonLights
;
70 std::list
< RefCountPtr
< const Lang::LightSource
> > allShadowLights
;
73 typedef typeof *lightPile_ PileType
;
74 for( PileType::const_iterator src
= lightPile_
->begin( ); src
!= lightPile_
->end( ); ++src
)
76 if( (*src
)->shadows( ) )
78 allShadowLights
.push_back( (*src
)->typed_transformed( tf
) );
82 commonLights
.push_back( (*src
)->typed_transformed( tf
) );
87 if( ! allShadowLights
.empty( ) )
89 throw Exceptions::MiscellaneousRequirement( "Shadow lights cannot be used in a z-sorter." );
92 // There is one queue per original object. This structure will be where all the
93 // triangles resides at the beginning of the treatment of each shadow light or the
94 // view occlusion computation.
96 // We begin by initializing these queues.
97 typedef Computation::SplitJob::CompoundObject CompoundObject
; // It is a bit unnatural to define the type somewhere but here...
99 const size_t pileSize
= pile_
->size( );
100 size_t triangleCount
= 0;
102 // Now the main storage for triangles is set up
103 typedef PtrOwner_back_Access
< std::vector
< CompoundObject
* > > CompoundMemType
;
104 CompoundMemType compoundMem
;
105 compoundMem
.reserve( pileSize
);
107 // Then we fill it with triangles that don't intersect.
108 // Note that it is a responsibility of push_zBufTriangles to not push any tiny triangles.
110 Computation::SplicingLine spliceLine
;
111 std::list
< Computation::SplitJob
> job
;
112 typedef typeof *pile_ PileType
;
113 for( PileType::const_iterator src
= pile_
->begin( ); src
!= pile_
->end( ); ++src
)
115 std::list
< Computation::ZBufTriangle
> * tmpList
= new std::list
< Computation::ZBufTriangle
>;
116 // Since there cannot be shadow lights in a z sorter, it is OK not to include the backsides of single sided facets.
117 (*src
)->push_zBufTriangles( tf
, eyez
, tmpList
, true ); // true means allow dropping back sides of single sided objects
118 for( CompoundObject::iterator i
= tmpList
->begin( ); i
!= tmpList
->end( ); ++i
)
120 typedef std::vector
< CompoundObject
* >::iterator ObjectIterator
;
121 for( ObjectIterator o
= compoundMem
.begin( ); o
!= compoundMem
.end( ); ++o
)
123 for( CompoundObject::iterator j
= (*o
)->begin( ); j
!= (*o
)->end( ); ++j
)
125 if( j
->intersection( *i
, & spliceLine
) &&
126 j
->overlapsAlong( *i
, spliceLine
, Computation::theTrixelizeOverlapTol
) )
128 job
.push_back( Computation::SplitJob( i
, o
, j
) );
134 continue; // this is just a no-op to make this a valid jump destination
136 while( ! job
.empty( ) )
138 Computation::SplitJob
& currentJob
= job
.front( );
139 if( ! currentJob
.splitted_
->intersection( *currentJob
.splitting_
, & spliceLine
) )
141 throw Exceptions::InternalError( "These triangles were known to intsersect, and now they're parallel!" );
144 // New triangles are added to the end of tmpList, and the iterator to the first new triangle is returned.
145 CompoundObject::iterator i
= currentJob
.splitted_
->spliceAlong( spliceLine
, tmpList
);
147 // Now the procedure from above is repeated, but not comparing against triangles that have already been checked.
148 for( ; i
!= tmpList
->end( ); ++i
)
150 CompoundObject::iterator j
= currentJob
.splitting_
;
152 typedef std::vector
< CompoundObject
* >::iterator ObjectIterator
;
153 for( ObjectIterator o
= currentJob
.splittingObject_
; o
!= compoundMem
.end( ); ++o
)
155 // For the splitting object object (the first in this loop), the first triangle to compare against
156 // was set above. For the other object, all triangles shall be compared against (that is, j starts from
158 if( o
!= currentJob
.splittingObject_
)
162 for( ; j
!= (*o
)->end( ); ++j
)
164 if( j
->intersection( *i
, & spliceLine
) &&
165 j
->overlapsAlong( *i
, spliceLine
, Computation::theTrixelizeOverlapTol
) )
167 job
.push_back( Computation::SplitJob( i
, o
, j
) );
173 continue; // this is just a no-op to make this a valid jump destination
176 tmpList
->erase( currentJob
.splitted_
);
179 compoundMem
.push_back( tmpList
);
180 triangleCount
+= tmpList
->size( );
185 // In order to be able to deal with the triangles efficiently from here on, I put them all in a long vector.
186 // This has one drawback, though, being that we will lose track of the fact that triangles belonging to the same
187 // facet does not have to be checked for depth order. However, I count on them not being ordered thanks to the
188 // tolerance used in the overlap test.
189 std::vector
< const Computation::ZBufTriangle
* > triangleMem
;
190 triangleMem
.reserve( triangleCount
);
191 for( std::vector
< CompoundObject
* >::iterator o
= compoundMem
.begin( ); o
!= compoundMem
.end( ); ++o
)
193 for( CompoundObject::iterator j
= (*o
)->begin( ); j
!= (*o
)->end( ); ++j
)
195 triangleMem
.push_back( & *j
);
198 if( triangleMem
.size( ) != triangleCount
)
200 throw Exceptions::InternalError( "Some triangles are missing!" );
204 // I keep track of which objects an object has to be drawn after. The objects that are not
205 // waiting for other objects to be drawn are kept in a special list.
206 // To do this efficiently, each object need to know how many objects it is waiting for to be
207 // drawn. It must also know what objects to update when it has been drawn. An object is identified
208 // by the pointer to its list, so the additional information must be kept in a separate structure.
209 // As usual, objects are identified by their position in a memory vector.
210 // At this state, "to draw" an object means to place it in drawOrder.
212 std::list
< const Computation::ZBufTriangle
* > drawOrder
;
213 if( triangleCount
> 0 ) // This avoids a bug that would otherwise occur due to computing triangleCount - 1
215 std::vector
< size_t > waitCounters
;
216 waitCounters
.resize( triangleCount
, 0 );
217 std::vector
< std::list
< size_t > > waitingObjects
;
218 waitingObjects
.resize( triangleCount
);
220 // We begin by setting up waitingObjects and waitCounters.
221 // This involves testing each object against all other objects.
222 for( size_t i0
= 0; i0
< triangleCount
- 1; ++i0
) // Ugly bug if triangleCount == 0
224 const Computation::ZBufTriangle
* t0
= triangleMem
[ i0
];
225 for( size_t i1
= i0
+ 1; i1
< triangleCount
; ++i1
)
227 const Computation::ZBufTriangle
* t1
= triangleMem
[ i1
];
228 if( t0
->overlaps( *t1
) )
230 Concrete::Coords2D
commonPoint( 0, 0 );
231 if( ! t0
->overlaps( *t1
, & commonPoint
, Computation::theTrixelizeOverlapTol
) )
233 // Too little overlap.
236 if( t0
->isOnTopOfAt( *t1
, commonPoint
) )
238 waitingObjects
[ i1
].push_back( i0
);
239 ++waitCounters
[ i0
];
243 waitingObjects
[ i0
].push_back( i1
);
244 ++waitCounters
[ i1
];
250 // Then the queue of objects to be "drawn" is initialized.
251 std::list
< size_t > drawQueue
;
252 std::map
< const Computation::PaintedPolygon3D
*, size_t > trianglesInPolygon
;
254 std::vector
< size_t >::iterator wi
= waitCounters
.begin( );
255 for( size_t i
= 0; i
< triangleCount
; ++i
, ++wi
)
259 drawQueue
.push_back( i
);
260 ++trianglesInPolygon
[ triangleMem
[ i
]->painter_
];
265 // Now, when the triangles are "drawn", that is, placed in drawOrder, they shall be placed so
266 // in such a way that triangles that belong to the same polygon appear in sequence as often as possible.
267 // While there is probably accurate ways to treat this problem, I resort to some simple heuristics here.
268 // The question is basically how to pick a polygon among those than contain a triangle that may be drawn.
270 size_t drawnCount
= 0;
271 while( drawnCount
< triangleCount
)
273 while( ! drawQueue
.empty( ) )
275 // First, use find the polygon whith the most triangles in drawQueue.
276 const Computation::PaintedPolygon3D
* painter
= 0;
278 // Note that triangles that belong to the same polygon will never overlap, and hence drawing triangles that belong
279 // to painter will not make other triangles that belong to painter ready to be drawn. This algorithm depends on
282 size_t bestCount
= 0;
284 typedef typeof trianglesInPolygon MapType
;
285 MapType::iterator best_j
;
286 for( MapType::iterator j
= trianglesInPolygon
.begin( ); j
!= trianglesInPolygon
.end( ); ++j
)
288 if( j
->second
> bestCount
)
290 bestCount
= j
->second
;
294 painter
= best_j
->first
;
295 trianglesInPolygon
.erase( best_j
); // If we need this again it will be re-created.
298 // Soon, bestCount triangles will have been drawn, but the value of bestCount will then be destroyed.
299 drawnCount
+= bestCount
;
301 // There shall be bestCount triangles to draw, so by counting the number of triangles we find we may not
302 // have to search all of drawQueue.
303 for( std::list
< size_t >::iterator ii
= drawQueue
.begin( ); bestCount
> 0; )
306 if( triangleMem
[ i
]->painter_
!= painter
)
312 std::list
< size_t >::iterator erase_i
= ii
;
314 drawQueue
.erase( erase_i
);
317 drawOrder
.push_back( triangleMem
[ i
] );
318 triangleMem
[ i
] = 0;
320 const std::list
< size_t > & waitList
= waitingObjects
[ i
];
321 for( std::list
< size_t >::const_iterator j
= waitList
.begin( ); j
!= waitList
.end( ); ++j
)
323 --waitCounters
[ *j
];
324 if( waitCounters
[ *j
] == 0 )
326 drawQueue
.push_back( *j
);
327 // Note that it is assumed that ( triangleMem[ *j ]->painter_ != painter ) !
328 // if( triangleMem[ *j ]->painter_ == painter )
330 // throw Exceptions::InternalError( "Triangle waiting for another triangle in the same polygon!" );
332 ++trianglesInPolygon
[ triangleMem
[ *j
]->painter_
];
339 if( drawnCount
< triangleCount
)
341 // Resolve cyclic overlap the hard way...
342 WARN_OR_THROW( Exceptions::MiscellaneousRequirement( "Cyclic overlaps are not allowed in a z sorter; a small triangle had to be drawn too deep." ) )
343 Concrete::Area bestArea
= HUGE_VAL
;
345 // This search is a somewhat expensive since we must search the whole list.
346 typedef typeof triangleMem ListType
;
347 ListType::iterator ti
= triangleMem
.begin( );
348 for( size_t i
= 0; i
< triangleCount
; ++i
, ++ti
)
354 Concrete::Area tmpArea
= (*ti
)->area( );
355 if( tmpArea
< bestArea
)
361 drawQueue
.push_back( besti
);
362 ++trianglesInPolygon
[ triangleMem
[ besti
]->painter_
];
363 waitCounters
[ besti
] = 0; // This will avoid that this is drawn again, since the counter will never _reach_ 0 now.
369 // It is now time to take care of the lines.
370 // The first thing we shall do is to remove what is occluded by triangles.
371 // Note that triangles will be drawn before the lines, and that is the only way lines
372 // can occlude triangles.
373 // Then, we make sure that the lines are drawn in back-to-front order, clipping occluded lines
374 // behind the line occluding them to avoid cyclic locking.
376 std::list
< const Computation::ZBufLine
* > lineQueue
;
378 typedef typeof *linePile_ PileType
;
379 for( PileType::const_iterator src
= linePile_
->begin( ); src
!= linePile_
->end( ); ++src
)
381 (*src
)->push_zBufLine( tf
, eyez
, & lineQueue
);
385 std::list
< const Computation::ZBufLine
* > disjointLines
;
386 while( ! lineQueue
.empty( ) )
389 std::list
< const Computation::ZBufLine
* > queue1
;
390 std::list
< const Computation::ZBufLine
* > queue2
;
392 std::list
< const Computation::ZBufLine
* > * currentQueue
= & queue1
;
393 std::list
< const Computation::ZBufLine
* > * otherQueue
= & queue2
;
395 currentQueue
->push_back( lineQueue
.front( ) );
396 lineQueue
.pop_front( );
398 typedef typeof drawOrder ListType
;
399 for( ListType::const_iterator i
= drawOrder
.begin( ); i
!= drawOrder
.end( ); ++i
)
401 while( ! currentQueue
->empty( ) )
403 const Computation::ZBufLine
* currentLine
= currentQueue
->front( );
404 currentQueue
->pop_front( );
405 if( currentLine
->overlaps( **i
) )
407 currentLine
->splice( **i
, otherQueue
);
412 otherQueue
->push_back( currentLine
);
418 std::list
< const Computation::ZBufLine
* > * tmp
= currentQueue
;
419 currentQueue
= otherQueue
;
424 // When we reach here the line segments are in currentQueue.
425 // These segments are ready to be inserted in the line z buffer.
427 // The algorithm below is inefficient, because it will generally make the overlap comparison
428 // several times for any overlaping pair of line segments.
429 while( ! currentQueue
->empty( ) )
431 const Computation::ZBufLine
* current
= currentQueue
->front( );
432 currentQueue
->pop_front( );
434 bool foundOverlap
= false;
435 typedef typeof disjointLines ListType
;
436 for( ListType::iterator i
= disjointLines
.begin( ); i
!= disjointLines
.end( );
439 if( current
->overlaps( **i
) )
441 const Computation::ZBufLine
* line
= *i
;
442 disjointLines
.erase( i
);
443 // Note that splice is responsible for deleting that of *i and current which is not used.
444 Computation::ZBufLine::splice( line
, current
,
453 disjointLines
.push_back( current
);
459 RefCountPtr
< const Lang::Group2D
> res
= Lang::THE_NULL2D
;
461 const bool SHOW_TRIXELS
= false;
464 // This is a debug mode
466 typedef typeof drawOrder ListType
;
467 for( ListType::const_iterator i
= drawOrder
.begin( ); i
!= drawOrder
.end( ); ++i
)
469 res
= RefCountPtr
< const Lang::Group2D
>( new Lang::GroupPair2D( (*i
)->debugFrame( ),
476 // This is the standard mode
478 // Remember that the grouping of triangles into polygons can probably be improved!
480 typedef typeof drawOrder ListType
;
481 for( ListType::iterator i
= drawOrder
.begin( ); i
!= drawOrder
.end( ); ) // Note that i shall not be incremented here.
483 const Computation::PaintedPolygon3D
* painter
= (*i
)->painter_
;
484 if( painter
->getColor( ) == Lang::THE_OCCLUDING_WHITE
)
490 std::list
< Computation::ZBufTriangle
> regions
;
491 // This is a hideous copy!
492 regions
.push_back( **i
);
494 // Now we'll simply join the triangle **i with the immediately following triangles sharing the same painter.
495 // The job of joining triangles thus consists in placing them in a good order in drawOrder.
498 for( ; i
!= drawOrder
.end( ) && (*i
)->painter_
== painter
; ++i
)
500 // Another hideous copy!
501 regions
.push_back( **i
);
504 // If this would have been a z-buffer, we should add the common lights to the shadow lights here,
505 // but in a z-sorter there are no shadow lights.
506 RefCountPtr
< const Lang::PaintedPolygon2D
> tmp
= painter
->polygon_to2D( dyn
, tf
, commonLights
);
508 // The following statement will consume the objects in regions.
509 res
= RefCountPtr
< const Lang::Group2D
>( new Lang::GroupPair2D( tmp
->clip( & regions
, tmp
),
516 // Memory cleanup of the triangles should be taken care of by compoundMem.
519 // Finally we draw the lines.
520 while( ! disjointLines
.empty( ) )
522 const Computation::ZBufLine
* current
= disjointLines
.front( );
523 disjointLines
.pop_front( );
524 res
= RefCountPtr
< const Lang::Group2D
>( new Lang::GroupPair2D( current
->stroke2D( ),