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 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 "trianglefunctions.h"
33 #include "constructorrepresentation.h"
39 using namespace Shapes
;
46 class ZBuf::IndexRepresentation
55 IndexRepresentation( );
56 void push_back( size_t i
);
57 Lang::ZBuf::PolyIndices
toPolyIndices( const std::vector
< Concrete::Coords2D
> & cornerMem
) const;
58 size_t getDifferent( size_t notThis1
, size_t notThis2
) const;
59 void addEdges( Computation::UndirectedEdgeMatrix
< std::pair
< bool, std::list
< Lang::ZBuf::IndexRepresentation
* > > > * edgeMatrix
, std::list
< Computation::UndirectedEdge
> * jobQueue
, const std::vector
< Concrete::Coords2D
> & cornerMem
);
60 void removeEdges( Computation::UndirectedEdgeMatrix
< std::pair
< bool, std::list
< Lang::ZBuf::IndexRepresentation
* > > > * edgeMatrix
);
61 void pushTriangle( std::list
< Computation::ZBufTriangle
> * triangles
, const std::vector
< Concrete::Coords2D
> & cornerMem
, const Computation::PaintedPolygon3D
* painter
, const RefCountPtr
< const Computation::ZBufTriangle::ZMap
> zMap
);
62 void show( std::ostream
& os
) const;
63 void show( std::ostream
& os
, const std::vector
< Concrete::Coords2D
> & cornerMem
) const;
64 Computation::UndirectedEdge
getEdge( char pos
) const;
65 size_t getDifferent( char pos
) const;
66 bool isMember( const size_t i
) const;
71 Lang::ZBuf::IndexRepresentation::IndexRepresentation( )
72 : end_( 0 ), pushed_( false )
76 Lang::ZBuf::IndexRepresentation::push_back( size_t i
)
93 throw Exceptions::InternalError( "IndexRepresentation overflow" );
97 Lang::ZBuf::PolyIndices
98 Lang::ZBuf::IndexRepresentation::toPolyIndices( const std::vector
< Concrete::Coords2D
> & cornerMem
) const
101 const Concrete::Coords2D d1
= cornerMem
[ i1
] - cornerMem
[ i0
];
102 const Concrete::Coords2D d2
= cornerMem
[ i2
] - cornerMem
[ i0
];
103 if( d1
.x_
* d2
.y_
- d1
.y_
* d2
.x_
> 0 )
105 // we have counter-clockwise ordering
120 Lang::ZBuf::IndexRepresentation::getDifferent( size_t notThis1
, size_t notThis2
) const
122 if( i0
!= notThis1
&& i0
!= notThis2
)
126 if( i1
!= notThis1
&& i1
!= notThis2
)
134 Lang::ZBuf::IndexRepresentation::isMember( const size_t i
) const
143 return i
== i0
|| i
== i1
;
145 return i
== i0
|| i
== i1
|| i
== i2
;
147 throw Exceptions::InternalError( "IndexRepresentation end out of range." );
152 Lang::ZBuf::IndexRepresentation::addEdges( Computation::UndirectedEdgeMatrix
< std::pair
< bool, std::list
< Lang::ZBuf::IndexRepresentation
* > > > * edgeMatrix
, std::list
< Computation::UndirectedEdge
> * jobQueue
, const std::vector
< Concrete::Coords2D
> & cornerMem
)
154 // When adding edges, we must be prepared to accept that the triangle may be rejected at any edge because it
155 // competes with a bigger triangle on the same side of the edge.
157 // We should remember that the triangle may first knock out other triangles when being added to the first edges,
158 // and then be knocked out itself at a later edge. Then it seems that the triangles it knocked out first shouldn't
159 // have been knocked out. However, they wouldn't have been knocked out if they were not very small, so it's
160 // probably not a big loss anyway.
162 if( ! addEdge( edgeMatrix
, Computation::UndirectedEdge( i0
, i1
), this, jobQueue
, cornerMem
) )
166 if( ! addEdge( edgeMatrix
, Computation::UndirectedEdge( i1
, i2
), this, jobQueue
, cornerMem
) )
168 // We know that this was push_back'ed, so we don't have to search using removeEdge.
170 std::pair
< bool, std::list
< Lang::ZBuf::IndexRepresentation
* > > & p
= (*edgeMatrix
)[ Computation::UndirectedEdge( i0
, i1
) ];
172 p
.second
.pop_back( );
176 if( ! addEdge( edgeMatrix
, Computation::UndirectedEdge( i2
, i0
), this, jobQueue
, cornerMem
) )
178 // We know that this was push_back'ed, so we don't have to search using removeEdge.
180 std::pair
< bool, std::list
< Lang::ZBuf::IndexRepresentation
* > > & p
= (*edgeMatrix
)[ Computation::UndirectedEdge( i0
, i1
) ];
182 p
.second
.pop_back( );
185 std::pair
< bool, std::list
< Lang::ZBuf::IndexRepresentation
* > > & p
= (*edgeMatrix
)[ Computation::UndirectedEdge( i1
, i2
) ];
187 p
.second
.pop_back( );
194 Lang::ZBuf::IndexRepresentation::removeEdges( Computation::UndirectedEdgeMatrix
< std::pair
< bool, std::list
< Lang::ZBuf::IndexRepresentation
* > > > * edgeMatrix
)
196 removeEdge( edgeMatrix
, Computation::UndirectedEdge( i0
, i1
), this );
197 removeEdge( edgeMatrix
, Computation::UndirectedEdge( i1
, i2
), this );
198 removeEdge( edgeMatrix
, Computation::UndirectedEdge( i2
, i0
), this );
202 Lang::ZBuf::IndexRepresentation::pushTriangle( std::list
< Computation::ZBufTriangle
> * triangles
, const std::vector
< Concrete::Coords2D
> & cornerMem
, const Computation::PaintedPolygon3D
* painter
, const RefCountPtr
< const Computation::ZBufTriangle::ZMap
> zMap
)
210 triangles
->push_back( Computation::ZBufTriangle( painter
,
212 cornerMem
[ i0
], cornerMem
[ i1
], cornerMem
[ i2
] ) );
216 Lang::ZBuf::IndexRepresentation::show( std::ostream
& os
) const
224 os
<< "1 point: " << i0
;
227 os
<< "2 points: " << i0
<< " -- " << i1
;
230 os
<< "3 points: " << i0
<< " -- " << i1
<< " -- " << i2
;
233 os
<< "end_ out of range!" ;
238 Lang::ZBuf::IndexRepresentation::show( std::ostream
& os
, const std::vector
< Concrete::Coords2D
> & cornerMem
) const
243 os
<< "|** No points" ;
246 os
<< "|** 1 point: " << cornerMem
[ i0
] ;
249 os
<< "|** 2 points: " << cornerMem
[ i0
] << " -- " << cornerMem
[ i1
] ;
252 os
<< "@<< @width:0.3bp | stroke [] " << Helpers::shapesFormat( cornerMem
[ i0
] ) << "--" << Helpers::shapesFormat( cornerMem
[ i1
] ) << "--" << Helpers::shapesFormat( cornerMem
[ i2
] ) << "--cycle" << std::endl
;
255 os
<< "end_ out of range!" ;
259 Computation::UndirectedEdge
260 Lang::ZBuf::IndexRepresentation::getEdge( char pos
) const
265 return Computation::UndirectedEdge( i0
, i1
);
267 return Computation::UndirectedEdge( i1
, i2
);
269 return Computation::UndirectedEdge( i2
, i0
);
271 throw Exceptions::InternalError( "getEdge: pos out of range." );
276 Lang::ZBuf::IndexRepresentation::getDifferent( char pos
) const
287 throw Exceptions::InternalError( "getEdge: pos out of range." );
293 Lang::ZBuf::mergeTriangles( std::list
< Computation::ZBufTriangle
> * triangles
)
295 if( triangles
->size( ) <= 1 )
300 const Computation::PaintedPolygon3D
* painter
= triangles
->front( ).painter_
;
301 const RefCountPtr
< const Computation::ZBufTriangle::ZMap
> zMap
= triangles
->front( ).zMap_
;
303 std::vector
< Lang::ZBuf::IndexRepresentation
> indexRepMem
;
304 indexRepMem
.reserve( 2 * triangles
->size( ) ); // This is crucial!
306 // One needs to be careful here. The reuse of points based on distances being less than the tolerance
307 // may cause two points on the same triangle to be approximated by the very _same_ point. This will
308 // lead to a degenerate triangle, and must be avoided in order to prevent confusion later on
311 // Even worse, the triangles being "disjoint" does not mean they are perfectly disjoint (perhaps due to some
312 // point approximations somewhere), but only overlaping by at most some tolerance value. Hence, we may
313 // even find triangles included in other triangles and similar phenomena.
314 // This would be interesting to design better with more powerful invariants so that one could guarantee
315 // stronger properties. However, as the current state of affairs when writing this desperate note is
316 // that we may find ourselves with more than two triangles sharing the same edge!
317 // The solution to this problem is to discard, on each side of the edge (a zero tolerance test is used to determine the side
318 // of a triangle) discard all but the triangle with the biggest area. Luckily, this can be done incrementaly by
319 // always keeping track of the biggest triangle on each side.
320 // Need I say it feels like this algorithm is running out of control?
322 std::vector
< Concrete::Coords2D
> cornerMem
;
323 while( ! triangles
->empty( ) )
325 const std::vector
< Concrete::Coords2D
> & points
= triangles
->front( ).points_
;
326 indexRepMem
.push_back( IndexRepresentation( ) );
327 Lang::ZBuf::IndexRepresentation
& current
= indexRepMem
.back( );
328 for( std::vector
< Concrete::Coords2D
>::const_iterator i
= points
.begin( ); i
!= points
.end( ); ++i
)
330 Concrete::Coords2D tmp
= *i
;
333 typedef typeof cornerMem MemType
;
334 for( MemType::const_iterator j
= cornerMem
.begin( ); j
!= cornerMem
.end( ); ++j
, ++memIdx
)
336 if( ( tmp
- *j
).norm( ) < Computation::theTrixelizeSplicingTol
)
338 if( current
.isMember( memIdx
) )
340 // This is the error situation when we are just about to reuse a point which is already part of this triangle.
341 // The solution is to abort the creation of the current triangle.
342 indexRepMem
.pop_back( );
346 current
.push_back( memIdx
);
352 current
.push_back( cornerMem
.size( ) );
353 cornerMem
.push_back( tmp
);
357 triangles
->pop_front( );
360 const size_t pointCount
= cornerMem
.size( );
362 Computation::UndirectedEdgeMatrix
< std::pair
< bool, std::list
< Lang::ZBuf::IndexRepresentation
* > > >
363 edgeMatrix( pointCount
,
364 std::pair
< bool, std::list
< Lang::ZBuf::IndexRepresentation
* > >( false,
365 std::list
< Lang::ZBuf::IndexRepresentation
* >( ) ) );
367 std::list
< Computation::UndirectedEdge
> jobQueue
;
370 typedef typeof indexRepMem ListType
;
371 for( ListType::iterator i
= indexRepMem
.begin( ); i
!= indexRepMem
.end( ); ++i
)
373 i
->addEdges( & edgeMatrix
, & jobQueue
, cornerMem
);
377 while( ! jobQueue
.empty( ) )
379 Computation::UndirectedEdge edge
= jobQueue
.front( );
380 jobQueue
.pop_front( );
382 // Elements can be removed from the jobQueue by unflagging them; only flagged elements that appear in the jobQueue
383 // are really waiting to be processed.
384 if( ! edgeMatrix
[ edge
].first
)
388 edgeMatrix
[ edge
].first
= false; // Flag that this is no longer waiting to be processed.
390 typedef std::list
< Lang::ZBuf::IndexRepresentation
* > ListType
;
391 ListType
& meetingTriangles
= edgeMatrix
[ edge
].second
;
393 if( meetingTriangles
.size( ) < 2 )
395 // One situation I can think of when this could happen is when three triangles have been
396 // found to be on the same side of the edge during addEdge. Then two of them are removed,
397 // but the edge is still in the jobQueue since it was queued when the second triange was added
402 if( meetingTriangles
.size( ) > 2 )
404 std::ostringstream oss
;
405 oss
<< "Only two (not " << meetingTriangles
.size( ) << ") edges can share a pair of points!" ;
406 oss
<< std::endl
<< "|** Triangles in queue: " ;
407 for( ListType::const_iterator i
= meetingTriangles
.begin( ); i
!= meetingTriangles
.end( ); ++i
)
410 (*i
)->show( oss
, cornerMem
);
412 throw Exceptions::InternalError( oss
);
415 Concrete::Coords2D cornerLow
= cornerMem
[ edge
.low( ) ];
416 Concrete::Coords2D cornerHigh
= cornerMem
[ edge
.high( ) ];
418 ListType::iterator src
= meetingTriangles
.begin( );
419 Lang::ZBuf::IndexRepresentation
* triangle1
= *src
;
420 Concrete::Coords2D differentPoint1
= cornerMem
[ triangle1
->getDifferent( edge
.low( ), edge
.high( ) ) ];
423 Lang::ZBuf::IndexRepresentation
* triangle2
= *src
;
424 Concrete::Coords2D differentPoint2
= cornerMem
[ triangle2
->getDifferent( edge
.low( ), edge
.high( ) ) ];
425 bool aligned
= false;
426 size_t keepPoint
= 0; /* Initialized with dummy value only because it is hard for the compiler to see that it won't be used uninitialized. */
427 if( areAligned( cornerLow
, differentPoint1
, differentPoint2
) )
430 keepPoint
= edge
.high( );
432 else if( areAligned( cornerHigh
, differentPoint1
, differentPoint2
) )
435 keepPoint
= edge
.low( );
440 triangle1
->removeEdges( & edgeMatrix
);
441 triangle2
->removeEdges( & edgeMatrix
);
442 indexRepMem
.push_back( IndexRepresentation( ) );
443 Lang::ZBuf::IndexRepresentation
& current
= indexRepMem
.back( );
444 current
.push_back( triangle1
->getDifferent( edge
.low( ), edge
.high( ) ) );
445 current
.push_back( triangle2
->getDifferent( edge
.low( ), edge
.high( ) ) );
446 current
.push_back( keepPoint
);
447 current
.addEdges( & edgeMatrix
, & jobQueue
, cornerMem
);
451 for( Computation::UndirectedEdge edge
= Computation::UndirectedEdge::begin( ); edge
!= Computation::UndirectedEdge::end( ); edge
.increment( pointCount
) )
453 std::list
< Lang::ZBuf::IndexRepresentation
* > & lst
= edgeMatrix
[ edge
].second
;
454 for( std::list
< Lang::ZBuf::IndexRepresentation
* >::iterator i
= lst
.begin( ); i
!= lst
.end( ); ++i
)
456 // The IndexRepresentation keeps a state to ensure that is is really pushed only once.
457 (*i
)->pushTriangle( triangles
, cornerMem
, painter
, zMap
);
462 // recombineTriangles generalizes mergeTriangles, but is more expensive and should be called less often.
464 Lang::ZBuf::recombineTriangles( std::list
< Computation::ZBufTriangle
> * mergedTriangles
)
466 if( mergedTriangles
->size( ) <= 1 )
471 const Computation::PaintedPolygon3D
* painter
= mergedTriangles
->front( ).painter_
;
472 const RefCountPtr
< const Computation::ZBufTriangle::ZMap
> zMap
= mergedTriangles
->front( ).zMap_
;
474 std::list
< Lang::ZBuf::IndexRepresentation
> indexRepMem
;
476 std::vector
< Concrete::Coords2D
> cornerMem
;
477 while( ! mergedTriangles
->empty( ) )
479 const std::vector
< Concrete::Coords2D
> & points
= mergedTriangles
->front( ).points_
;
480 indexRepMem
.push_back( IndexRepresentation( ) );
481 Lang::ZBuf::IndexRepresentation
& current
= indexRepMem
.back( );
482 for( std::vector
< Concrete::Coords2D
>::const_iterator i
= points
.begin( ); i
!= points
.end( ); ++i
)
484 Concrete::Coords2D tmp
= *i
;
487 typedef typeof cornerMem MemType
;
488 for( MemType::const_iterator j
= cornerMem
.begin( ); j
!= cornerMem
.end( ); ++j
, ++memIdx
)
490 if( ( tmp
- *j
).norm( ) < Computation::theTrixelizeSplicingTol
)
492 if( current
.isMember( memIdx
) )
494 // This is the error situation when we are just about to reuse a point which is already part of this triangle.
495 // The solution is to abort the creation of the current triangle.
496 indexRepMem
.pop_back( );
500 current
.push_back( memIdx
);
506 current
.push_back( cornerMem
.size( ) );
507 cornerMem
.push_back( tmp
);
511 mergedTriangles
->pop_front( );
514 const size_t pointCount
= cornerMem
.size( );
516 std::vector
< PolyIndices
> polyMem
;
517 polyMem
.reserve( indexRepMem
.size( ) ); // this is crucial to avoid reallocation!
519 Computation::UndirectedEdgeMatrix
< std::list
< PolyIndices
* > > edgeMatrix( pointCount
);
521 while( ! indexRepMem
.empty( ) )
523 bool foundExtension
= false;
524 typedef typeof indexRepMem TrianglesType
;
525 for( TrianglesType::iterator i
= indexRepMem
.begin( ); i
!= indexRepMem
.end( ) && ! foundExtension
; ++i
)
527 for( char e
= 0; e
< 3; ++e
)
529 Computation::UndirectedEdge edge
= i
->getEdge( e
);
530 std::list
< PolyIndices
* > & polys
= edgeMatrix
[ edge
];
531 if( polys
.size( ) == 1 ) // By the way, it is an error if the size is greater than 1
533 if( ! extendPoly( polys
.front( ), edge
, i
->getDifferent( e
), & edgeMatrix
, cornerMem
, true ) ) // true for convex
537 foundExtension
= true;
538 indexRepMem
.erase( i
);
543 if( ! foundExtension
)
545 polyMem
.push_back( indexRepMem
.front( ).toPolyIndices( cornerMem
) );
546 indexRepMem
.pop_front( );
547 PolyIndices
* newPoly
= & polyMem
.back( );
548 addEdges( newPoly
, & edgeMatrix
);
552 while( ! polyMem
.empty( ) )
554 PolyIndices
& poly
= polyMem
.back( );
555 // First we remove unnecessary points on straight segments
556 if( poly
.size( ) > 3 )
558 for( PolyIndices::iterator i0
= poly
.begin( ); i0
!= poly
.end( ); ++i0
)
560 Concrete::Coords2D p0
= cornerMem
[ *i0
];
561 PolyIndices::iterator i1
= i0
;
563 if( i1
== poly
.end( ) )
567 Concrete::Coords2D p1
= cornerMem
[ *i1
];
568 PolyIndices::iterator i2
= i1
;
570 if( i2
== poly
.end( ) )
574 Concrete::Coords2D p2
= cornerMem
[ *i2
];
576 // We do the usual inscribed circle test to test alignment
577 while( Computation::triangleArea( p0
, p1
, p2
) < Computation::theTrixelizeOverlapTol
* Computation::triangleSemiPerimeter( p0
, p1
, p2
) )
579 PolyIndices::iterator iRemove
= i1
;
582 poly
.erase( iRemove
);
583 if( poly
.size( ) < 3 )
588 if( i2
== poly
.end( ) )
592 p2
= cornerMem
[ *i2
];
596 if( poly
.size( ) < 3 )
604 PolyIndices::const_iterator src
= poly
.begin( );
609 for( ; src
!= poly
.end( ); ++src
)
612 mergedTriangles
->push_back( Computation::ZBufTriangle( painter
,
614 cornerMem
[ i0
], cornerMem
[ i1
], cornerMem
[ i2
] ) );
623 Lang::ZBuf::trianglesToPolys( std::list
< Computation::ZBufTriangle
> * triangles
, Lang::Clipped2D
* dst
)
625 if( triangles
->empty( ) )
630 const bool DEBUGME
= false;
633 while( ! triangles
->empty( ) )
635 const std::vector
< Concrete::Coords2D
> & points
= triangles
->front( ).points_
;
637 Lang::ElementaryPath2D
* newPath
= new Lang::ElementaryPath2D
;
639 for( std::vector
< Concrete::Coords2D
>::const_iterator src
= points
.begin( ); src
!= points
.end( ); ++src
)
641 newPath
->push_back( new Concrete::PathPoint2D( new Concrete::Coords2D( *src
) ) );
644 dst
->addSubPath( RefCountPtr
< const Lang::ElementaryPath2D
>( newPath
) );
646 triangles
->pop_front( );
651 std::list
< Lang::ZBuf::IndexRepresentation
> indexRepMem
;
652 std::vector
< Concrete::Coords2D
> cornerMem
;
655 std::list
< Lang::ZBuf::IndexRepresentation
> indexRepQueue
;
656 while( ! triangles
->empty( ) )
658 const std::vector
< Concrete::Coords2D
> & points
= triangles
->front( ).points_
;
659 indexRepQueue
.push_back( IndexRepresentation( ) );
660 Lang::ZBuf::IndexRepresentation
& current
= indexRepQueue
.back( );
661 for( std::vector
< Concrete::Coords2D
>::const_iterator i
= points
.begin( ); i
!= points
.end( ); ++i
)
663 Concrete::Coords2D tmp
= *i
;
666 typedef typeof cornerMem MemType
;
667 for( MemType::const_iterator j
= cornerMem
.begin( ); j
!= cornerMem
.end( ); ++j
, ++memIdx
)
669 if( ( tmp
- *j
).norm( ) < Computation::theTrixelizeSplicingTol
)
671 if( current
.isMember( memIdx
) )
673 // This is the error situation when we are just about to reuse a point which is already part of this triangle.
674 // The solution is to abort the creation of the current triangle.
675 indexRepMem
.pop_back( );
679 current
.push_back( memIdx
);
685 current
.push_back( cornerMem
.size( ) );
686 cornerMem
.push_back( tmp
);
690 triangles
->pop_front( );
693 while( ! indexRepQueue
.empty( ) )
695 Lang::ZBuf::IndexRepresentation
& current
= indexRepQueue
.front( );
697 bool wasSplit
= false;
698 for( char e
= 0; e
< 3 && ! wasSplit
; ++e
)
700 Computation::UndirectedEdge edge
= current
.getEdge( e
);
701 size_t iLow
= edge
.low( );
702 size_t iHigh
= edge
.high( );
703 size_t iOther
= current
.getDifferent( e
);
704 Concrete::Coords2D pLow
= cornerMem
[ iLow
];
705 Concrete::Coords2D pHigh
= cornerMem
[ iHigh
];
706 for( size_t i
= 0; i
< cornerMem
.size( ) && ! wasSplit
; ++i
)
708 if( i
== iLow
|| i
== iHigh
|| i
== iOther
)
712 if( areAlignedAndOrdered( pLow
, cornerMem
[ i
], pHigh
) )
714 // To avoid infinite loops, we make sure that the triangles get smaller each time
715 // they are splitted. Otherwise, four points in a row can cause an infinite loop.
717 Concrete::Coords2D pOther
= cornerMem
[ iOther
];
718 Concrete::Coords2D pi
= cornerMem
[ i
];
720 Concrete::Area area0
= Computation::triangleArea( pLow
, pHigh
, pOther
);
722 const double AREA_TOL
= 1e-3;
725 const double relArea
= Computation::triangleArea( pOther
, pLow
, pi
) / area0
;
726 if( AREA_TOL
< relArea
&& relArea
< 1 - AREA_TOL
)
728 indexRepQueue
.push_back( IndexRepresentation( ) );
729 Lang::ZBuf::IndexRepresentation
& newTriangle
= indexRepQueue
.back( );
730 newTriangle
.push_back( iOther
);
731 newTriangle
.push_back( iLow
);
732 newTriangle
.push_back( i
);
737 const double relArea
= Computation::triangleArea( pOther
, pi
, pHigh
) / area0
;
738 if( AREA_TOL
< relArea
&& relArea
< 1 - AREA_TOL
)
740 indexRepQueue
.push_back( IndexRepresentation( ) );
741 Lang::ZBuf::IndexRepresentation
& newTriangle
= indexRepQueue
.back( );
742 newTriangle
.push_back( iOther
);
743 newTriangle
.push_back( i
);
744 newTriangle
.push_back( iHigh
);
754 indexRepMem
.push_back( current
);
757 indexRepQueue
.pop_front( );
761 const size_t pointCount
= cornerMem
.size( );
763 std::vector
< PolyIndices
> polyMem
;
764 polyMem
.reserve( indexRepMem
.size( ) ); // this is crucial to avoid reallocation!
766 Computation::UndirectedEdgeMatrix
< std::list
< PolyIndices
* > > edgeMatrix( pointCount
);
768 while( ! indexRepMem
.empty( ) )
770 bool foundExtension
= false;
771 typedef typeof indexRepMem TrianglesType
;
772 for( TrianglesType::iterator i
= indexRepMem
.begin( ); i
!= indexRepMem
.end( ) && ! foundExtension
; ++i
)
774 for( char e
= 0; e
< 3; ++e
)
776 Computation::UndirectedEdge edge
= i
->getEdge( e
);
777 std::list
< PolyIndices
* > & polys
= edgeMatrix
[ edge
];
778 if( polys
.size( ) == 1 ) // By the way, it is an error if the size is greater than 1
780 if( ! extendPoly( polys
.front( ), edge
, i
->getDifferent( e
), & edgeMatrix
, cornerMem
, false ) ) // false to not require convex
784 foundExtension
= true;
785 indexRepMem
.erase( i
);
790 if( ! foundExtension
)
792 polyMem
.push_back( indexRepMem
.front( ).toPolyIndices( cornerMem
) );
793 indexRepMem
.pop_front( );
794 PolyIndices
* newPoly
= & polyMem
.back( );
795 addEdges( newPoly
, & edgeMatrix
);
799 while( ! polyMem
.empty( ) )
801 PolyIndices
& poly
= polyMem
.back( );
802 if( poly
.size( ) > 3 )
804 // First we remove insections, that is sequences like 4-5-4 et c.
806 PolyIndices::iterator theEnd
= poly
.begin( );
807 PolyIndices::iterator i0
= poly
.begin( );
808 while( poly
.size( ) >= 5 ) // it would be pathological to have insection in polygons with four corners or less
810 PolyIndices::iterator i1
= i0
;
812 if( i1
== poly
.end( ) )
816 PolyIndices::iterator i2
= i1
;
818 if( i2
== poly
.end( ) )
825 // We found an insection
832 if( i0
== poly
.end( ) )
842 // Then we remove unnecessary points on straight segments
843 for( PolyIndices::iterator i0
= poly
.begin( ); i0
!= poly
.end( ); ++i0
)
845 Concrete::Coords2D p0
= cornerMem
[ *i0
];
846 PolyIndices::iterator i1
= i0
;
848 if( i1
== poly
.end( ) )
852 Concrete::Coords2D p1
= cornerMem
[ *i1
];
853 PolyIndices::iterator i2
= i1
;
855 if( i2
== poly
.end( ) )
859 Concrete::Coords2D p2
= cornerMem
[ *i2
];
861 // We do the usual inscribed circle test to test alignment
862 while( Computation::triangleArea( p0
, p1
, p2
) < Computation::theTrixelizeOverlapTol
* Computation::triangleSemiPerimeter( p0
, p1
, p2
) )
864 PolyIndices::iterator iRemove
= i1
;
867 poly
.erase( iRemove
);
868 if( poly
.size( ) < 3 )
873 if( i2
== poly
.end( ) )
877 p2
= cornerMem
[ *i2
];
881 if( poly
.size( ) < 3 )
890 Lang::ElementaryPath2D
* newPath
= new Lang::ElementaryPath2D
;
892 for( PolyIndices::const_iterator src
= poly
.begin( ); src
!= poly
.end( ); ++src
)
894 newPath
->push_back( new Concrete::PathPoint2D( new Concrete::Coords2D( cornerMem
[ *src
] ) ) );
897 dst
->addSubPath( RefCountPtr
< const Lang::ElementaryPath2D
>( newPath
) );
905 Lang::ZBuf::addEdge( Computation::UndirectedEdgeMatrix
< std::pair
< bool, std::list
< Lang::ZBuf::IndexRepresentation
* > > > * edgeMatrix
, const Computation::UndirectedEdge
& edge
, Lang::ZBuf::IndexRepresentation
* indRep
, std::list
< Computation::UndirectedEdge
> * jobQueue
, const std::vector
< Concrete::Coords2D
> & cornerMem
)
907 typedef typeof (*edgeMatrix
)[ edge
].second ListType
;
908 ListType
& trianglesAtEdge
= (*edgeMatrix
)[ edge
].second
;
909 trianglesAtEdge
.push_back( indRep
);
911 bool alreadyInQueue
= false;
913 if( trianglesAtEdge
.size( ) > 2 )
915 // This is a problematic case. I've written about it elsewhere. The decision I took was to discard
916 // the smaller if the triangles being on the same side of the edge.
917 // Since we only do this when there are already three triangles sharing the edge, there's a risk
918 // that all three are on the same side. Then we may even drop two of them.
920 alreadyInQueue
= true;
922 Concrete::UnitFloatPair edgeNormalNotNormalized
= cornerMem
[ edge
.low( ) ].unNormalizedOrthogonal( cornerMem
[ edge
.high( ) ] );
923 double m
= Concrete::innerScalar( cornerMem
[ edge
.low( ) ], edgeNormalNotNormalized
);
925 Lang::ZBuf::IndexRepresentation
* posMax
= 0;
926 Lang::ZBuf::IndexRepresentation
* negMax
= 0;
927 Concrete::Area posArea
= -1;
928 Concrete::Area negArea
= -1;
930 for( ListType::iterator i
= trianglesAtEdge
.begin( ); i
!= trianglesAtEdge
.end( ); ++i
)
932 Concrete::Area tmpArea
= Computation::triangleArea( cornerMem
[ (*i
)->i0
], cornerMem
[ (*i
)->i1
], cornerMem
[ (*i
)->i2
] );
933 if( Concrete::innerScalar( cornerMem
[ (*i
)->getDifferent( edge
.low( ), edge
.high( ) ) ], edgeNormalNotNormalized
) > m
)
935 if( tmpArea
> posArea
)
943 if( tmpArea
> negArea
)
951 // *** It is required that the new triangle appears at the end of trianglesAtEdge in case we add it. ***
953 // We temporarily remove the newly added triangle...
954 trianglesAtEdge
.pop_back( );
956 // Now we remove those of the old triangles that were knocked out.
957 // Note that removing triangles from edges clears the job flags at their edges, so we don't have to do that here.
959 // We must be careful since trianglesAtEdge might change when triangles are removed!
960 ListType::iterator i
= trianglesAtEdge
.begin( );
961 Lang::ZBuf::IndexRepresentation
* t1
= *i
;
963 Lang::ZBuf::IndexRepresentation
* t2
= *i
;
965 if( t1
!= posMax
&& t1
!= negMax
)
967 t1
->removeEdges( edgeMatrix
);
969 if( t2
!= posMax
&& t2
!= negMax
)
971 t2
->removeEdges( edgeMatrix
);
975 // Next, we consider the new triangle.
976 if( indRep
!= posMax
&& indRep
!= negMax
)
978 // The new triangle couldn't compete with the old ones, so we shall return false.
982 // ... and now we put it back if it passed the test.
983 trianglesAtEdge
.push_back( indRep
);
988 if( trianglesAtEdge
.size( ) == 2 && ! (*edgeMatrix
)[ edge
].first
)
990 if( ! alreadyInQueue
)
992 jobQueue
->push_back( edge
);
994 (*edgeMatrix
)[ edge
].first
= true; // Flag that this pair is in the queue.
1001 Lang::ZBuf::removeEdge( Computation::UndirectedEdgeMatrix
< std::pair
< bool, std::list
< Lang::ZBuf::IndexRepresentation
* > > > * edgeMatrix
, const Computation::UndirectedEdge
& edge
, Lang::ZBuf::IndexRepresentation
* indRep
)
1003 std::pair
< bool, std::list
< Lang::ZBuf::IndexRepresentation
* > > & p
= (*edgeMatrix
)[ edge
];
1005 // An edge can have at most two triangles, so when one is removed, the edge cannot be queued for work.
1006 // If this was the only triangle at the edge, this will be a no-op.
1009 std::list
< Lang::ZBuf::IndexRepresentation
* > & lst
= p
.second
;
1010 std::list
< Lang::ZBuf::IndexRepresentation
* >::iterator i
= find( lst
.begin( ), lst
.end( ), indRep
);
1011 if( i
== lst
.end( ) )
1013 throw Exceptions::InternalError( "Attempt to remove nonexistent edge." );
1019 Lang::ZBuf::areAligned( const Concrete::Coords2D p0
, const Concrete::Coords2D p1
, const Concrete::Coords2D p2
)
1021 // We test alignment by looking at the radius of the inscribed circle.
1022 return Computation::triangleArea( p0
, p1
, p2
) < Computation::theTrixelizeSplicingTol
* Computation::triangleSemiPerimeter( p0
, p1
, p2
);
1026 Lang::ZBuf::areAlignedAndOrdered( const Concrete::Coords2D p0
, const Concrete::Coords2D p1
, const Concrete::Coords2D p2
)
1028 // We test alignment by looking at the radius of the inscribed circle.
1029 if( Computation::triangleArea( p0
, p1
, p2
) > Computation::theTrixelizeSplicingTol
* Computation::triangleSemiPerimeter( p0
, p1
, p2
) )
1034 // We then test that p1 is between p0 and p2 by computing a projection onto an unnormalized vector...
1035 // With dHat = d.normalized( ) = d * ( 1 / d.norm( ) ), the condition
1036 // dHat.inner( p1 - p0 ) < d.norm( )
1038 // d.inner( p1 - p0 ) < d.norm( ) * d.norm( )
1039 Concrete::UnitFloatPair
d( ( p2
.x_
- p0
.x_
).offtype
< 1, 0 >( ), ( p2
.y_
- p0
.y_
).offtype
< 1, 0 >( ), bool( ) );
1040 Concrete::Length c
= Concrete::inner( d
, p1
- p0
);
1041 if( c
< Concrete::ZERO_LENGTH
)
1045 if( c
> d
.normSquaredThatOughtToBeOne( ) )
1053 Lang::ZBuf::addEdges( PolyIndices
* poly
, Computation::UndirectedEdgeMatrix
< std::list
< PolyIndices
* > > * edgeMatrix
)
1055 PolyIndices::const_iterator src1
= poly
->begin( );
1056 PolyIndices::const_iterator src2
= src1
;
1058 for( ; src2
!= poly
->end( ); ++src1
, ++src2
)
1060 addEdge( edgeMatrix
, *src1
, *src2
, poly
);
1062 src2
= poly
->begin( );
1063 addEdge( edgeMatrix
, *src1
, *src2
, poly
);
1067 Lang::ZBuf::addEdge( Computation::UndirectedEdgeMatrix
< std::list
< PolyIndices
* > > * edgeMatrix
, size_t ia
, size_t ib
, PolyIndices
* indRep
)
1069 (*edgeMatrix
)[ Computation::UndirectedEdge( ia
, ib
) ].push_back( indRep
);
1072 // Return true when extension was really performed
1074 Lang::ZBuf::extendPoly( PolyIndices
* poly
, const Computation::UndirectedEdge
& edge
, size_t iNew
, Computation::UndirectedEdgeMatrix
< std::list
< PolyIndices
* > > * edgeMatrix
, const std::vector
< Concrete::Coords2D
> & cornerMem
, bool convex
)
1076 const PolyIndices::iterator src0
= std::find( poly
->begin( ), poly
->end( ), edge
.low( ) );
1077 if( src0
== poly
->end( ) )
1082 PolyIndices::iterator src1
;
1083 PolyIndices::iterator src2
;
1084 // First we try the previous point
1085 if( src0
== poly
->begin( ) )
1087 if( poly
->back( ) == edge
.high( ) )
1090 src1
= poly
->end( );
1100 if( *src1
== edge
.high( ) )
1106 // Then we try the next point
1111 if( src2
== poly
->end( ) )
1113 src2
= poly
->begin( );
1115 if( *src2
== edge
.high( ) )
1123 // Before we replace the old edge by the new ones we check convexity, if that's what the caller wants
1126 PolyIndices::iterator srcBack
= src1
;
1127 if( srcBack
== poly
->begin( ) )
1129 srcBack
= poly
->end( );
1133 Concrete::UnitFloatPair inHat
= cornerMem
[ *srcBack
].normalizedOrthogonal( cornerMem
[ *src1
] );
1134 if( Concrete::inner( inHat
, cornerMem
[ iNew
] - cornerMem
[ *src1
] ) < - Computation::theTrixelizeSplicingTol
)
1140 PolyIndices::iterator srcForward
= src2
;
1142 if( srcForward
== poly
->end( ) )
1144 srcForward
= poly
->begin( );
1147 Concrete::UnitFloatPair inHat
= cornerMem
[ *src2
].normalizedOrthogonal( cornerMem
[ *srcForward
] );
1148 if( Concrete::inner( inHat
, cornerMem
[ iNew
] - cornerMem
[ *src2
] ) < - Computation::theTrixelizeSplicingTol
)
1155 poly
->insert( src2
, iNew
);
1156 (*edgeMatrix
)[ edge
].remove( poly
);
1157 (*edgeMatrix
)[ Computation::UndirectedEdge( edge
.low( ), iNew
) ].push_back( poly
);
1158 (*edgeMatrix
)[ Computation::UndirectedEdge( edge
.high( ), iNew
) ].push_back( poly
);