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
; )
528 for( char e
= 0; e
< 3; ++e
)
530 Computation::UndirectedEdge edge
= i
->getEdge( e
);
531 std::list
< PolyIndices
* > & polys
= edgeMatrix
[ edge
];
532 if( polys
.size( ) == 1 ) // By the way, it is an error if the size is greater than 1
534 if( ! extendPoly( polys
.front( ), edge
, i
->getDifferent( e
), & edgeMatrix
, cornerMem
, true ) ) // true for convex
538 foundExtension
= true;
544 TrianglesType::iterator iErase
= i
;
546 indexRepMem
.erase( iErase
);
551 if( ! foundExtension
)
553 polyMem
.push_back( indexRepMem
.front( ).toPolyIndices( cornerMem
) );
554 indexRepMem
.pop_front( );
555 PolyIndices
* newPoly
= & polyMem
.back( );
556 addEdges( newPoly
, & edgeMatrix
);
560 while( ! polyMem
.empty( ) )
562 PolyIndices
& poly
= polyMem
.back( );
563 // First we remove unnecessary points on straight segments
564 if( poly
.size( ) > 3 )
566 for( PolyIndices::iterator i0
= poly
.begin( ); i0
!= poly
.end( ); ++i0
)
568 Concrete::Coords2D p0
= cornerMem
[ *i0
];
569 PolyIndices::iterator i1
= i0
;
571 if( i1
== poly
.end( ) )
575 Concrete::Coords2D p1
= cornerMem
[ *i1
];
576 PolyIndices::iterator i2
= i1
;
578 if( i2
== poly
.end( ) )
582 Concrete::Coords2D p2
= cornerMem
[ *i2
];
584 // We do the usual inscribed circle test to test alignment
585 while( Computation::triangleArea( p0
, p1
, p2
) < Computation::theTrixelizeOverlapTol
* Computation::triangleSemiPerimeter( p0
, p1
, p2
) )
587 PolyIndices::iterator iRemove
= i1
;
590 poly
.erase( iRemove
);
591 if( poly
.size( ) < 3 )
596 if( i2
== poly
.end( ) )
600 p2
= cornerMem
[ *i2
];
604 if( poly
.size( ) < 3 )
612 PolyIndices::const_iterator src
= poly
.begin( );
617 for( ; src
!= poly
.end( ); ++src
)
620 mergedTriangles
->push_back( Computation::ZBufTriangle( painter
,
622 cornerMem
[ i0
], cornerMem
[ i1
], cornerMem
[ i2
] ) );
631 Lang::ZBuf::trianglesToPolys( std::list
< Computation::ZBufTriangle
> * triangles
, Lang::Clipped2D
* dst
)
633 if( triangles
->empty( ) )
638 const bool DEBUGME
= false;
641 while( ! triangles
->empty( ) )
643 const std::vector
< Concrete::Coords2D
> & points
= triangles
->front( ).points_
;
645 Lang::ElementaryPath2D
* newPath
= new Lang::ElementaryPath2D
;
647 for( std::vector
< Concrete::Coords2D
>::const_iterator src
= points
.begin( ); src
!= points
.end( ); ++src
)
649 newPath
->push_back( new Concrete::PathPoint2D( new Concrete::Coords2D( *src
) ) );
652 dst
->addSubPath( RefCountPtr
< const Lang::ElementaryPath2D
>( newPath
) );
654 triangles
->pop_front( );
659 std::list
< Lang::ZBuf::IndexRepresentation
> indexRepMem
;
660 std::vector
< Concrete::Coords2D
> cornerMem
;
663 std::list
< Lang::ZBuf::IndexRepresentation
> indexRepQueue
;
664 while( ! triangles
->empty( ) )
666 const std::vector
< Concrete::Coords2D
> & points
= triangles
->front( ).points_
;
667 indexRepQueue
.push_back( IndexRepresentation( ) );
668 Lang::ZBuf::IndexRepresentation
& current
= indexRepQueue
.back( );
669 for( std::vector
< Concrete::Coords2D
>::const_iterator i
= points
.begin( ); i
!= points
.end( ); ++i
)
671 Concrete::Coords2D tmp
= *i
;
674 typedef typeof cornerMem MemType
;
675 for( MemType::const_iterator j
= cornerMem
.begin( ); j
!= cornerMem
.end( ); ++j
, ++memIdx
)
677 if( ( tmp
- *j
).norm( ) < Computation::theTrixelizeSplicingTol
)
679 if( current
.isMember( memIdx
) )
681 // This is the error situation when we are just about to reuse a point which is already part of this triangle.
682 // The solution is to abort the creation of the current triangle.
683 indexRepMem
.pop_back( );
687 current
.push_back( memIdx
);
693 current
.push_back( cornerMem
.size( ) );
694 cornerMem
.push_back( tmp
);
698 triangles
->pop_front( );
701 while( ! indexRepQueue
.empty( ) )
703 Lang::ZBuf::IndexRepresentation
& current
= indexRepQueue
.front( );
705 bool wasSplit
= false;
706 for( char e
= 0; e
< 3 && ! wasSplit
; ++e
)
708 Computation::UndirectedEdge edge
= current
.getEdge( e
);
709 size_t iLow
= edge
.low( );
710 size_t iHigh
= edge
.high( );
711 size_t iOther
= current
.getDifferent( e
);
712 Concrete::Coords2D pLow
= cornerMem
[ iLow
];
713 Concrete::Coords2D pHigh
= cornerMem
[ iHigh
];
714 for( size_t i
= 0; i
< cornerMem
.size( ) && ! wasSplit
; ++i
)
716 if( i
== iLow
|| i
== iHigh
|| i
== iOther
)
720 if( areAlignedAndOrdered( pLow
, cornerMem
[ i
], pHigh
) )
722 // To avoid infinite loops, we make sure that the triangles get smaller each time
723 // they are splitted. Otherwise, four points in a row can cause an infinite loop.
725 Concrete::Coords2D pOther
= cornerMem
[ iOther
];
726 Concrete::Coords2D pi
= cornerMem
[ i
];
728 Concrete::Area area0
= Computation::triangleArea( pLow
, pHigh
, pOther
);
730 const double AREA_TOL
= 1e-3;
733 const double relArea
= Computation::triangleArea( pOther
, pLow
, pi
) / area0
;
734 if( AREA_TOL
< relArea
&& relArea
< 1 - AREA_TOL
)
736 indexRepQueue
.push_back( IndexRepresentation( ) );
737 Lang::ZBuf::IndexRepresentation
& newTriangle
= indexRepQueue
.back( );
738 newTriangle
.push_back( iOther
);
739 newTriangle
.push_back( iLow
);
740 newTriangle
.push_back( i
);
745 const double relArea
= Computation::triangleArea( pOther
, pi
, pHigh
) / area0
;
746 if( AREA_TOL
< relArea
&& relArea
< 1 - AREA_TOL
)
748 indexRepQueue
.push_back( IndexRepresentation( ) );
749 Lang::ZBuf::IndexRepresentation
& newTriangle
= indexRepQueue
.back( );
750 newTriangle
.push_back( iOther
);
751 newTriangle
.push_back( i
);
752 newTriangle
.push_back( iHigh
);
762 indexRepMem
.push_back( current
);
765 indexRepQueue
.pop_front( );
769 const size_t pointCount
= cornerMem
.size( );
771 std::vector
< PolyIndices
> polyMem
;
772 polyMem
.reserve( indexRepMem
.size( ) ); // this is crucial to avoid reallocation!
774 Computation::UndirectedEdgeMatrix
< std::list
< PolyIndices
* > > edgeMatrix( pointCount
);
776 while( ! indexRepMem
.empty( ) )
778 bool foundExtension
= false;
779 typedef typeof indexRepMem TrianglesType
;
780 for( TrianglesType::iterator i
= indexRepMem
.begin( ); i
!= indexRepMem
.end( ) && ! foundExtension
; )
783 for( char e
= 0; e
< 3; ++e
)
785 Computation::UndirectedEdge edge
= i
->getEdge( e
);
786 std::list
< PolyIndices
* > & polys
= edgeMatrix
[ edge
];
787 if( polys
.size( ) == 1 ) // By the way, it is an error if the size is greater than 1
789 if( ! extendPoly( polys
.front( ), edge
, i
->getDifferent( e
), & edgeMatrix
, cornerMem
, false ) ) // false to not require convex
793 foundExtension
= true;
799 TrianglesType::iterator iErase
= i
;
801 indexRepMem
.erase( iErase
);
806 if( ! foundExtension
)
808 polyMem
.push_back( indexRepMem
.front( ).toPolyIndices( cornerMem
) );
809 indexRepMem
.pop_front( );
810 PolyIndices
* newPoly
= & polyMem
.back( );
811 addEdges( newPoly
, & edgeMatrix
);
815 while( ! polyMem
.empty( ) )
817 PolyIndices
& poly
= polyMem
.back( );
818 if( poly
.size( ) > 3 )
820 // First we remove insections, that is sequences like 4-5-4 et c.
822 PolyIndices::iterator theEnd
= poly
.begin( );
823 PolyIndices::iterator i0
= poly
.begin( );
824 while( poly
.size( ) >= 5 ) // it would be pathological to have insection in polygons with four corners or less
826 PolyIndices::iterator i1
= i0
;
828 if( i1
== poly
.end( ) )
832 PolyIndices::iterator i2
= i1
;
834 if( i2
== poly
.end( ) )
841 // We found an insection
848 if( i0
== poly
.end( ) )
858 // Then we remove unnecessary points on straight segments
859 for( PolyIndices::iterator i0
= poly
.begin( ); i0
!= poly
.end( ); ++i0
)
861 Concrete::Coords2D p0
= cornerMem
[ *i0
];
862 PolyIndices::iterator i1
= i0
;
864 if( i1
== poly
.end( ) )
868 Concrete::Coords2D p1
= cornerMem
[ *i1
];
869 PolyIndices::iterator i2
= i1
;
871 if( i2
== poly
.end( ) )
875 Concrete::Coords2D p2
= cornerMem
[ *i2
];
877 // We do the usual inscribed circle test to test alignment
878 while( Computation::triangleArea( p0
, p1
, p2
) < Computation::theTrixelizeOverlapTol
* Computation::triangleSemiPerimeter( p0
, p1
, p2
) )
880 PolyIndices::iterator iRemove
= i1
;
883 poly
.erase( iRemove
);
884 if( poly
.size( ) < 3 )
889 if( i2
== poly
.end( ) )
893 p2
= cornerMem
[ *i2
];
897 if( poly
.size( ) < 3 )
906 Lang::ElementaryPath2D
* newPath
= new Lang::ElementaryPath2D
;
908 for( PolyIndices::const_iterator src
= poly
.begin( ); src
!= poly
.end( ); ++src
)
910 newPath
->push_back( new Concrete::PathPoint2D( new Concrete::Coords2D( cornerMem
[ *src
] ) ) );
913 dst
->addSubPath( RefCountPtr
< const Lang::ElementaryPath2D
>( newPath
) );
921 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
)
923 typedef typeof (*edgeMatrix
)[ edge
].second ListType
;
924 ListType
& trianglesAtEdge
= (*edgeMatrix
)[ edge
].second
;
925 trianglesAtEdge
.push_back( indRep
);
927 bool alreadyInQueue
= false;
929 if( trianglesAtEdge
.size( ) > 2 )
931 // This is a problematic case. I've written about it elsewhere. The decision I took was to discard
932 // the smaller if the triangles being on the same side of the edge.
933 // Since we only do this when there are already three triangles sharing the edge, there's a risk
934 // that all three are on the same side. Then we may even drop two of them.
936 alreadyInQueue
= true;
938 Concrete::UnitFloatPair edgeNormalNotNormalized
= cornerMem
[ edge
.low( ) ].unNormalizedOrthogonal( cornerMem
[ edge
.high( ) ] );
939 double m
= Concrete::innerScalar( cornerMem
[ edge
.low( ) ], edgeNormalNotNormalized
);
941 Lang::ZBuf::IndexRepresentation
* posMax
= 0;
942 Lang::ZBuf::IndexRepresentation
* negMax
= 0;
943 Concrete::Area posArea
= -1;
944 Concrete::Area negArea
= -1;
946 for( ListType::iterator i
= trianglesAtEdge
.begin( ); i
!= trianglesAtEdge
.end( ); ++i
)
948 Concrete::Area tmpArea
= Computation::triangleArea( cornerMem
[ (*i
)->i0
], cornerMem
[ (*i
)->i1
], cornerMem
[ (*i
)->i2
] );
949 if( Concrete::innerScalar( cornerMem
[ (*i
)->getDifferent( edge
.low( ), edge
.high( ) ) ], edgeNormalNotNormalized
) > m
)
951 if( tmpArea
> posArea
)
959 if( tmpArea
> negArea
)
967 // *** It is required that the new triangle appears at the end of trianglesAtEdge in case we add it. ***
969 // We temporarily remove the newly added triangle...
970 trianglesAtEdge
.pop_back( );
972 // Now we remove those of the old triangles that were knocked out.
973 // Note that removing triangles from edges clears the job flags at their edges, so we don't have to do that here.
975 // We must be careful since trianglesAtEdge might change when triangles are removed!
976 ListType::iterator i
= trianglesAtEdge
.begin( );
977 Lang::ZBuf::IndexRepresentation
* t1
= *i
;
979 Lang::ZBuf::IndexRepresentation
* t2
= *i
;
981 if( t1
!= posMax
&& t1
!= negMax
)
983 t1
->removeEdges( edgeMatrix
);
985 if( t2
!= posMax
&& t2
!= negMax
)
987 t2
->removeEdges( edgeMatrix
);
991 // Next, we consider the new triangle.
992 if( indRep
!= posMax
&& indRep
!= negMax
)
994 // The new triangle couldn't compete with the old ones, so we shall return false.
998 // ... and now we put it back if it passed the test.
999 trianglesAtEdge
.push_back( indRep
);
1004 if( trianglesAtEdge
.size( ) == 2 && ! (*edgeMatrix
)[ edge
].first
)
1006 if( ! alreadyInQueue
)
1008 jobQueue
->push_back( edge
);
1010 (*edgeMatrix
)[ edge
].first
= true; // Flag that this pair is in the queue.
1017 Lang::ZBuf::removeEdge( Computation::UndirectedEdgeMatrix
< std::pair
< bool, std::list
< Lang::ZBuf::IndexRepresentation
* > > > * edgeMatrix
, const Computation::UndirectedEdge
& edge
, Lang::ZBuf::IndexRepresentation
* indRep
)
1019 std::pair
< bool, std::list
< Lang::ZBuf::IndexRepresentation
* > > & p
= (*edgeMatrix
)[ edge
];
1021 // An edge can have at most two triangles, so when one is removed, the edge cannot be queued for work.
1022 // If this was the only triangle at the edge, this will be a no-op.
1025 std::list
< Lang::ZBuf::IndexRepresentation
* > & lst
= p
.second
;
1026 std::list
< Lang::ZBuf::IndexRepresentation
* >::iterator i
= find( lst
.begin( ), lst
.end( ), indRep
);
1027 if( i
== lst
.end( ) )
1029 throw Exceptions::InternalError( "Attempt to remove nonexistent edge." );
1035 Lang::ZBuf::areAligned( const Concrete::Coords2D p0
, const Concrete::Coords2D p1
, const Concrete::Coords2D p2
)
1037 // We test alignment by looking at the radius of the inscribed circle.
1038 return Computation::triangleArea( p0
, p1
, p2
) < Computation::theTrixelizeSplicingTol
* Computation::triangleSemiPerimeter( p0
, p1
, p2
);
1042 Lang::ZBuf::areAlignedAndOrdered( const Concrete::Coords2D p0
, const Concrete::Coords2D p1
, const Concrete::Coords2D p2
)
1044 // We test alignment by looking at the radius of the inscribed circle.
1045 if( Computation::triangleArea( p0
, p1
, p2
) > Computation::theTrixelizeSplicingTol
* Computation::triangleSemiPerimeter( p0
, p1
, p2
) )
1050 // We then test that p1 is between p0 and p2 by computing a projection onto an unnormalized vector...
1051 // With dHat = d.normalized( ) = d * ( 1 / d.norm( ) ), the condition
1052 // dHat.inner( p1 - p0 ) < d.norm( )
1054 // d.inner( p1 - p0 ) < d.norm( ) * d.norm( )
1055 Concrete::UnitFloatPair
d( ( p2
.x_
- p0
.x_
).offtype
< 1, 0 >( ), ( p2
.y_
- p0
.y_
).offtype
< 1, 0 >( ), bool( ) );
1056 Concrete::Length c
= Concrete::inner( d
, p1
- p0
);
1057 if( c
< Concrete::ZERO_LENGTH
)
1061 if( c
> d
.normSquaredThatOughtToBeOne( ) )
1069 Lang::ZBuf::addEdges( PolyIndices
* poly
, Computation::UndirectedEdgeMatrix
< std::list
< PolyIndices
* > > * edgeMatrix
)
1071 PolyIndices::const_iterator src1
= poly
->begin( );
1072 PolyIndices::const_iterator src2
= src1
;
1074 for( ; src2
!= poly
->end( ); ++src1
, ++src2
)
1076 addEdge( edgeMatrix
, *src1
, *src2
, poly
);
1078 src2
= poly
->begin( );
1079 addEdge( edgeMatrix
, *src1
, *src2
, poly
);
1083 Lang::ZBuf::addEdge( Computation::UndirectedEdgeMatrix
< std::list
< PolyIndices
* > > * edgeMatrix
, size_t ia
, size_t ib
, PolyIndices
* indRep
)
1085 (*edgeMatrix
)[ Computation::UndirectedEdge( ia
, ib
) ].push_back( indRep
);
1088 // Return true when extension was really performed
1090 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
)
1092 const PolyIndices::iterator src0
= std::find( poly
->begin( ), poly
->end( ), edge
.low( ) );
1093 if( src0
== poly
->end( ) )
1098 PolyIndices::iterator src1
;
1099 PolyIndices::iterator src2
;
1100 // First we try the previous point
1101 if( src0
== poly
->begin( ) )
1103 if( poly
->back( ) == edge
.high( ) )
1106 src1
= poly
->end( );
1116 if( *src1
== edge
.high( ) )
1122 // Then we try the next point
1127 if( src2
== poly
->end( ) )
1129 src2
= poly
->begin( );
1131 if( *src2
== edge
.high( ) )
1139 // Before we replace the old edge by the new ones we check convexity, if that's what the caller wants
1142 PolyIndices::iterator srcBack
= src1
;
1143 if( srcBack
== poly
->begin( ) )
1145 srcBack
= poly
->end( );
1149 Concrete::UnitFloatPair inHat
= cornerMem
[ *srcBack
].normalizedOrthogonal( cornerMem
[ *src1
] );
1150 if( Concrete::inner( inHat
, cornerMem
[ iNew
] - cornerMem
[ *src1
] ) < - Computation::theTrixelizeSplicingTol
)
1156 PolyIndices::iterator srcForward
= src2
;
1158 if( srcForward
== poly
->end( ) )
1160 srcForward
= poly
->begin( );
1163 Concrete::UnitFloatPair inHat
= cornerMem
[ *src2
].normalizedOrthogonal( cornerMem
[ *srcForward
] );
1164 if( Concrete::inner( inHat
, cornerMem
[ iNew
] - cornerMem
[ *src2
] ) < - Computation::theTrixelizeSplicingTol
)
1171 poly
->insert( src2
, iNew
);
1172 (*edgeMatrix
)[ edge
].remove( poly
);
1173 (*edgeMatrix
)[ Computation::UndirectedEdge( edge
.low( ), iNew
) ].push_back( poly
);
1174 (*edgeMatrix
)[ Computation::UndirectedEdge( edge
.high( ), iNew
) ].push_back( poly
);