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 "basicsimplex.h"
34 #include "zbufinternals.h"
35 #include "constructorrepresentation.h"
42 using namespace Shapes
;
45 #define SPLICEDEBUG( code ) // code
48 assertNotOverlapping( const std::list
< Computation::ZBufTriangle
> & disjointTriangles
)
51 typedef typeof disjointTriangles ListType
;
52 ListType::const_iterator last
= disjointTriangles
.end( );
54 for( ListType::const_iterator i
= disjointTriangles
.begin( ); i
!= last
; ++i
)
56 if( last
->overlaps( *i
) )
58 throw Exceptions::InternalError( "assertNotOverlapping triggered" );
64 assertCounterClockwiseConvex( const Lang::ZBuf::PolyIndices
& poly
, const std::vector
< Concrete::Coords2D
> & cornerMem
)
66 for( Lang::ZBuf::PolyIndices::const_iterator i0
= poly
.begin( ); i0
!= poly
.end( ); ++i0
)
68 Lang::ZBuf::PolyIndices::const_iterator i1
= i0
;
70 if( i1
== poly
.end( ) )
74 Lang::ZBuf::PolyIndices::const_iterator i2
= i1
;
76 if( i2
== poly
.end( ) )
80 Concrete::UnitFloatPair inHat
= cornerMem
[ *i0
].normalizedOrthogonal( cornerMem
[ *i1
] );
81 if( Concrete::inner( inHat
, cornerMem
[ *i2
] - cornerMem
[ *i1
] ) < - Computation::theTrixelizeSplicingTol
)
83 throw Exceptions::InternalError( "assertCounterClockwiseConvex triggered" );
89 Computation::ZBufTriangle::ZMap::ZMap( const Concrete::UnitFloatTriple
& normal
,
91 Concrete::Length tiebreaker
,
92 Concrete::Length eyez
)
93 : normal_( normal
), k_x_( normal_
.x_
), k_y_( normal_
.y_
), k_z_( normal_
.z_
), m_( m
),
94 eyezInv_( 1. / eyez
), tiebreaker_( tiebreaker
), eyez_( eyez
)
98 Computation::ZBufTriangle::ZMap::operator () ( const Concrete::Coords2D
& p
) const
100 Concrete::Length tmp
= k_x_
* p
.x_
+ k_y_
* p
.y_
;
101 return ( m_
- tmp
) / ( k_z_
- eyezInv_
* tmp
);
105 Computation::ZBufTriangle::ZMap::writeToMatrices( double a
[3], Concrete::Length
* b
) const
113 Computation::SplicingLine::SplicingLine( const Concrete::Coords2D
& p0
, const Concrete::Coords2D
& p1_sub_p0
, bool isTriangleSide
)
114 : isTriangleSide_( isTriangleSide
),
116 d_( p1_sub_p0
.direction( ) ),
117 length_( p1_sub_p0
.norm( ) ),
118 n_( Concrete::UnitFloatPair( -p1_sub_p0
.y_
.offtype
< 1, 0 >( ), p1_sub_p0
.x_
.offtype
< 1, 0 >( ) ) ), // Note that this will normalize n_. What if this fails?
119 r_( Concrete::inner( n_
, p0
) )
122 Computation::SplicingLine::SplicingLine( const Computation::SplicingLine
& orig
)
123 : isTriangleSide_( orig
.isTriangleSide_
),
126 length_( orig
.length_
),
131 Computation::SplicingLine::SplicingLine( )
132 : isTriangleSide_( false ),
134 d_( 1., 0., bool( ) ),
136 n_( 0., -1., bool( ) ),
141 Computation::SplicingLine::intersection( const Computation::SplicingLine
& other
) const
146 const Concrete::UnitFloatPair
& n2
= other
.n_
;
147 const Concrete::Length
& r2
= other
.r_
;
150 double n_n1
= Concrete::inner( n_
, n2
);
151 double n_n_
= Concrete::inner( n_
, n_
);
152 double n2n2
= Concrete::inner( n2
, n2
);
154 if( n_n1
* n_n1
> ( 1 - 1e-8 ) * ( n_n_
* n2n2
) ) // This corresponds to an angle of approximately 0.01 degree.
156 throw "no intersection";
160 double invDet
= static_cast< double >( 1 ) / ( n_
.x_
* n2
.y_
- n_
.y_
* n2
.x_
);
161 x
= invDet
* ( n2
.y_
* r_
- n_
.y_
* r2
);
162 y
= invDet
* ( - n2
.x_
* r_
+ n_
.x_
* r2
);
164 Concrete::Coords2D
res( x
, y
);
166 Concrete::Length c1
= Concrete::inner( d_
, res
- p0_
);
167 Concrete::Length c2
= Concrete::inner( other
.d_
, res
- other
.p0_
);
168 if( ( isTriangleSide_
&& ( c1
< -Computation::theTrixelizeSplicingTol
|| c1
> length_
+ Computation::theTrixelizeSplicingTol
) ) &&
169 ( other
.isTriangleSide_
&& ( c2
< -Computation::theTrixelizeSplicingTol
|| c2
> other
.length_
+ Computation::theTrixelizeSplicingTol
) ) )
171 throw "no intersection";
179 Computation::SplicingLine::nextLine( const Concrete::Coords2D
* p
, const Concrete::UnitFloatPair
& n
, const std::vector
< Computation::SplicingLine
> & lines
) const
181 // This algorithm is formulated without its own tolerances. It relies on the pointers to the intersection points;
182 // "nearby points" should be represented by the same pointer. If two points are represented by different memory
183 // locations, they are treated as positively separated in geometry as well.
185 SPLICEDEBUG( std::cerr
<< "nextLine at " << Lang::Coords2D( *p
) << " -> " << "( " << n
.x_
<< ", " << n
.y_
<< " )" << " : " );
186 // Note that n will be unit, so it can be used to compute lengths.
187 const Concrete::Coords2D
& my_p
= *p
;
189 // back is parallel to this line, but not in the same halfspace as n.
190 // nOut is parallel to n_ but is turned so that it points out from the enclosed area.
191 // They will both be used to select among lines that intersect at the same point.
192 Concrete::UnitFloatPair back
= d_
;
193 if( Concrete::inner( back
, n
) > 0 )
195 back
= back
.reverse( );
197 Concrete::UnitFloatPair
nIn( back
.y_
, -back
.x_
);
200 Concrete::Length
bestRes( HUGE_VAL
);
201 const Concrete::Coords2D
* bestPoint
= 0;
203 typedef typeof intersections_ ListType
;
204 for( ListType::const_iterator i
= intersections_
.begin( ); i
!= intersections_
.end( ); ++i
, ++idx
)
206 if( *i
== 0 || *i
== p
)
210 Concrete::Length tmp
= Concrete::inner( n
, **i
- my_p
);
211 if( *i
== bestPoint
)
213 // The lines are compared by direction.
214 Concrete::UnitFloatPair dOld
= lines
[res
].d_
;
215 if( Concrete::inner( nIn
, dOld
) < 0 )
217 dOld
= dOld
.reverse( );
219 Concrete::UnitFloatPair dNew
= lines
[idx
].d_
;
220 if( Concrete::inner( nIn
, dNew
) < 0 )
222 dNew
= dNew
.reverse( );
224 if( Concrete::inner( back
, dNew
) > Concrete::inner( back
, dOld
) )
227 // bestPoint is already equal to *i
228 SPLICEDEBUG( std::cerr
<< "{" << res
<< "->" << idx
<< "}" );
232 else if( tmp
> Concrete::ZERO_LENGTH
&& tmp
< bestRes
)
236 SPLICEDEBUG( std::cerr
<< "{" << idx
<< "}" );
240 if( bestRes
== Concrete::HUGE_LENGTH
)
242 SPLICEDEBUG( std::cerr
<< "none" << std::endl
);
243 throw "no intersection";
245 SPLICEDEBUG( std::cerr
<< *intersections_
[res
] << std::endl
);
250 Computation::SplicingLine::distanceTo( const Concrete::Coords2D p
) const
252 return ( Concrete::inner( n_
, p
) - r_
).abs( );
257 Computation::ZBufTriangle::ZBufTriangle( const Computation::PaintedPolygon3D
* painter
, const RefCountPtr
< const Computation::ZBufTriangle::ZMap
> & zMap
, const Concrete::Coords2D
& p1
, const Concrete::Coords2D
& p2
, const Concrete::Coords2D
& p3
)
258 : painter_( painter
), zMap_( zMap
)
260 points_
.reserve( 3 );
261 points_
.push_back( p1
);
262 points_
.push_back( p2
);
263 points_
.push_back( p3
);
267 Computation::ZBufTriangle::zAt( const Concrete::Coords2D
& p
) const
269 return (*zMap_
)( p
);
273 Computation::ZBufTriangle::isOnTopOfAt( const Computation::ZBufTriangle
& other
, const Concrete::Coords2D
& p
) const
275 Concrete::Length zThis
= zAt( p
);
276 Concrete::Length zOther
= other
.zAt( p
);
278 Concrete::Length tThis
= zMap_
->getTiebreaker( );
279 Concrete::Length tOther
= other
.zMap_
->getTiebreaker( );
280 if( ( zThis
- zOther
).abs( ) < std::max( tThis
, tOther
) )
282 return zThis
+ tThis
> zOther
+ tOther
;
285 return zThis
> zOther
;
289 // This function does the test with the tolerance interpretation such that a true return value
290 // means that the triangles really overlaps by some positive amount.
292 Computation::ZBufTriangle::overlaps( const Computation::ZBufTriangle
& other
) const
294 const std::vector
< Concrete::Coords2D
> & pointSet_a( points_
);
295 const std::vector
< Concrete::Coords2D
> & pointSet_b( other
.points_
);
297 /* Do the circle-circle check
300 Concrete::Coords2D
ca( 0, 0 );
301 for( std::vector
< Concrete::Coords2D
>::const_iterator i
= pointSet_a
.begin( );
302 i
!= pointSet_a
.end( );
309 Concrete::Coords2D
cb( 0, 0 );
310 for( std::vector
< Concrete::Coords2D
>::const_iterator i
= pointSet_b
.begin( );
311 i
!= pointSet_b
.end( );
318 Concrete::Length
ra( 0 );
319 for( std::vector
< Concrete::Coords2D
>::const_iterator i
= pointSet_a
.begin( );
320 i
!= pointSet_a
.end( );
323 ra
= std::max( ra
, hypotPhysical( ca
.x_
- i
->x_
, ca
.y_
- i
->y_
) );
326 Concrete::Length
rb( 0 );
327 for( std::vector
< Concrete::Coords2D
>::const_iterator i
= pointSet_b
.begin( );
328 i
!= pointSet_b
.end( );
331 rb
= std::max( rb
, hypotPhysical( cb
.x_
- i
->x_
, cb
.y_
- i
->y_
) );
334 Concrete::Length rSum
= ra
+ rb
;
335 if( rSum
<= Computation::theTrixelizeOverlapTol
)
339 if( ( rSum
- Computation::theTrixelizeOverlapTol
) * ( rSum
- Computation::theTrixelizeOverlapTol
) < ( ca
.x_
- cb
.x_
) * ( ca
.x_
- cb
.x_
) + ( ca
.y_
- cb
.y_
) * ( ca
.y_
- cb
.y_
) )
345 /* Now to the search for a separating line.
347 if( ! oneWayOverlap( pointSet_a
, pointSet_b
) )
351 if( ! oneWayOverlap( pointSet_b
, pointSet_a
) )
358 // To be consistent with the tolerance interpretation in ZBufTriangle::overlaps, which returns true only if the triangles
359 // overlaps by some positive amount, this function shall rather return false than true.
360 // This means that we should prefer not to unflag allOutside.
362 Computation::ZBufTriangle::oneWayOverlap( const std::vector
< Concrete::Coords2D
> & poly1
, const std::vector
< Concrete::Coords2D
> & poly2
)
364 // If a bug is fixed here, remember to fix ZBufLine::overlaps too!
366 for( std::vector
< Concrete::Coords2D
>::const_iterator i0
= poly1
.begin( ); i0
!= poly1
.end( ); ++i0
)
368 std::vector
< Concrete::Coords2D
>::const_iterator i1
= i0
;
370 if( i1
== poly1
.end( ) )
374 std::vector
< Concrete::Coords2D
>::const_iterator i2
= i1
;
376 if( i2
== poly1
.end( ) )
381 const Concrete::Coords2D
& p0( *i0
);
382 const Concrete::Coords2D
& p1( *i1
);
384 const Concrete::Length txUnnormed
= p1
.x_
- p0
.x_
;
385 const Concrete::Length tyUnnormed
= p1
.y_
- p0
.y_
;
386 const Physical
< -1, 0 > invNorm
= 1. / hypotPhysical( txUnnormed
, tyUnnormed
);
387 // First we guess what's the inward direction
388 double inx( - invNorm
* tyUnnormed
);
389 double iny( invNorm
* txUnnormed
);
390 // Then we check if it needs to be reversed
392 const Concrete::Length dx
= i2
->x_
- p0
.x_
;
393 const Concrete::Length dy
= i2
->y_
- p0
.y_
;
394 if( dx
* inx
+ dy
* iny
< Concrete::ZERO_LENGTH
)
401 bool allOutside
= true;
402 for( std::vector
< Concrete::Coords2D
>::const_iterator p
= poly2
.begin( ); p
!= poly2
.end( ); ++p
)
404 const Concrete::Length dx
= p
->x_
- p0
.x_
;
405 const Concrete::Length dy
= p
->y_
- p0
.y_
;
406 if( inx
* dx
+ iny
* dy
> Computation::theTrixelizeOverlapTol
)
418 /* Note that this is only one part of the test, only if both symmetric tests return true do the
424 // tol shall be positive, and gives the smallest acceptable distance from commonPoint to the intersection boundary.
426 Computation::ZBufTriangle::overlaps( const ZBufTriangle
& other
, Concrete::Coords2D
* commonPoint
, Concrete::Length tol
) const
428 // We set up a linear program, and use simplex to solve it.
430 // The linear program is to maximize the distance from the common point to the intersection boundary,
431 // and if the distance becomes greater than tol during the search, we're happy without locating the optimum.
433 const size_t N_CONSTRAINTS
= 7;
434 const size_t N_VARIABLES
= 3;
436 static double c
[ N_VARIABLES
] = { 0, 0, 1 };
437 static double a
[ N_CONSTRAINTS
* N_VARIABLES
] =
444 static double b
[ N_CONSTRAINTS
];
445 static double x
[ N_VARIABLES
];
447 Concrete::Length xmin
= HUGE_VAL
;
448 Concrete::Length ymin
= HUGE_VAL
;
450 typedef typeof points_ ListType
;
451 for( ListType::const_iterator i
= points_
.begin( ); i
!= points_
.end( ); ++i
)
453 xmin
= std::min( xmin
, i
->x_
);
454 ymin
= std::min( ymin
, i
->y_
);
456 for( ListType::const_iterator i
= other
.points_
.begin( ); i
!= other
.points_
.end( ); ++i
)
458 xmin
= std::min( xmin
, i
->x_
);
459 ymin
= std::min( ymin
, i
->y_
);
461 Concrete::Coords2D
llCorner( xmin
, ymin
);
463 addTriangleConstraints( llCorner
, & a
[ 0 ], & b
[ 0 ] );
464 other
.addTriangleConstraints( llCorner
, & a
[ 9 ], & b
[ 3 ] );
466 // bShift is the amount _added_ to the right hand side in order to make the initial point feasible.
467 // It is computed via its additive inverse, and then the sign is changed.
468 // (The initial point will be feasible if the right hand side has no negative elements.)
469 double bShift
= b
[ 0 ];
470 for( const double * src
= & b
[ 1 ]; src
!= b
+ N_CONSTRAINTS
; ++src
)
472 bShift
= std::min( bShift
, *src
);
476 for( double * dst
= & b
[ 0 ]; dst
!= b
+ N_CONSTRAINTS
; ++dst
)
486 res
= Computation::theTwoTriangleSimplex
.maximize( & x
[0],
487 & optRes
, static_cast< double >( Concrete::Length::offtype( tol
) ) + bShift
,
488 & c
[0], & a
[0], & b
[0] );
490 catch( const char * ball
)
492 throw Exceptions::InternalError( ball
);
495 if( optRes
< bShift
)
497 std::cerr
<< "Simplex couldn't find a truly feasible point: " << optRes
<< " < " << bShift
<< std::endl
;
500 commonPoint
->x_
= xmin
+ Concrete::Length( x
[ 0 ] );
501 commonPoint
->y_
= ymin
+ Concrete::Length( x
[ 1 ] );
506 // tol shall be positive, and gives the smallest acceptable distance from a common point on line to the intersection boundary.
508 Computation::ZBufTriangle::overlapsAlong( const ZBufTriangle
& other
, const Computation::SplicingLine
& line
, Concrete::Length tol
) const
510 // This is much simpler than the simplex solution to the general overlap problem. Unfortunately, it doesn't seem like
511 // just keeping track of an upper and lower bound of the time along the line, since this will very often involve division
512 // by tiny numbers when line is parallel to any of the triangle sides.
514 // Instead, I keep track of two points points on the line, initialized far away in both directions. When comparing against
515 // a triangle side, four situations can occur, given by which of the points that satisfy the constraint. If none of the points
516 // satisfy the constraint, there is no intersection along the line. If both satisfy the constraint, the constraint does not
517 // further restrict the points. In the remaining case, the point which does not satisfy the constraint is moved to the border.
519 // The tolerance is implemented by changing all constraints by tol.
521 Concrete::Coords2D upper
= line
.p0_
+ ( 0.1 * std::numeric_limits
< double >::max( ) ) * line
.d_
;
522 Concrete::Coords2D lower
= line
.p0_
- ( 0.1 * std::numeric_limits
< double >::max( ) ) * line
.d_
;
524 // It is convenient to use the halfspace intersection representation of the triangles, so some
525 // code is borrowed from ZBufTriangle::overlaps.
526 // However, this time only two out of the three variables are used.
527 const size_t N_CONSTRAINTS
= 3;
528 const size_t N_VARIABLES
= 3;
530 static double a
[ N_CONSTRAINTS
* N_VARIABLES
];
531 static double b
[ N_CONSTRAINTS
];
532 double * bend
= & b
[ 0 ] + N_CONSTRAINTS
;
534 Concrete::Coords2D
llCorner( 0, 0 ); // This does not matter, so we may take the origin for instance
536 addTriangleConstraints( llCorner
, & a
[ 0 ], & b
[ 0 ] );
537 // Here's how the tolerance is implemented. Since the coefficients in are normalized outward normals,
538 // The triangles are shrunk by tol in all directions by subtracting tol from b.
539 const double * srca
= & a
[0];
540 for( const double * srcb
= & b
[ 0 ]; srcb
!= bend
; ++srcb
, srca
+= N_VARIABLES
)
542 Concrete::UnitFloatPair
n( *( srca
), *( srca
+ 1 ), bool( ) );
543 Concrete::Length m
= Concrete::Length( *srcb
) - tol
;
544 bool upperInside
= Concrete::inner( n
, upper
) < m
;
545 bool lowerInside
= Concrete::inner( n
, lower
) < m
;
547 if( upperInside
&& lowerInside
)
554 // That is, with lower = line.p0_ + t * line.d_, for some t, it shall also satisfy
555 // Concrete::inner( n, lower ) == m
556 lower
= line
.p0_
+ ( ( m
- Concrete::inner( n
, line
.p0_
) ) / Concrete::inner( n
, line
.d_
) ) * line
.d_
;
561 // Move upper, see above.
562 upper
= line
.p0_
+ ( ( m
- Concrete::inner( n
, line
.p0_
) ) / Concrete::inner( n
, line
.d_
) ) * line
.d_
;
565 // None of the points did satisfy the constraint. Infeasible. No overlap.
570 other
.addTriangleConstraints( llCorner
, & a
[ 0 ], & b
[ 0 ] );
571 const double * srca
= & a
[0];
572 for( const double * srcb
= & b
[ 0 ]; srcb
!= bend
; ++srcb
, srca
+= N_VARIABLES
)
574 Concrete::UnitFloatPair
n( *( srca
), *( srca
+ 1 ), bool( ) );
575 Concrete::Length m
= Concrete::Length( *srcb
) - tol
;
576 bool upperInside
= Concrete::inner( n
, upper
) < m
;
577 bool lowerInside
= Concrete::inner( n
, lower
) < m
;
579 if( upperInside
&& lowerInside
)
586 // That is, with lower = line.p0_ + t * line.d_, for some t, it shall also satisfy
587 // Concrete::inner( n, lower ) == m
588 lower
= line
.p0_
+ ( ( m
- Concrete::inner( n
, line
.p0_
) ) / Concrete::inner( n
, line
.d_
) ) * line
.d_
;
593 // Move upper, see above.
594 upper
= line
.p0_
+ ( ( m
- Concrete::inner( n
, line
.p0_
) ) / Concrete::inner( n
, line
.d_
) ) * line
.d_
;
597 // None of the points did satisfy the constraint. Infeasible. No overlap.
606 Computation::ZBufTriangle::addTriangleConstraints( Concrete::Coords2D llCorner
, double * a
, double * b
) const
608 typedef typeof points_ ListType
;
609 ListType::const_iterator i0
= points_
.begin( );
610 ListType::const_iterator i1
= i0
;
612 ListType::const_iterator i2
= i1
;
615 // Note that a is increased by 3 since one position holds a constant 1.
616 for( ; i0
!= points_
.end( ); i1
= i2
, i2
= i0
, ++i0
, a
+= 3, ++b
)
618 // It's important that the normal be normalized, for otherwise the interpretation of the common slack (the third variable) will be wrong.
619 Concrete::UnitFloatPair n
= i0
->normalizedOrthogonal( *i1
);
621 if( Concrete::inner( n
, *i2
- *i0
) < 0 )
623 // The normal points out.
626 *b
= Concrete::Length::offtype( Concrete::inner( n
, *i0
- llCorner
) );
630 // The normal points in -- reverse everything.
633 *b
= - Concrete::Length::offtype( Concrete::inner( n
, *i0
- llCorner
) );
640 Computation::operator << ( std::ostream
& os
, const Computation::ZBufTriangle
& self
)
642 std::vector
< Concrete::Coords2D
>::const_iterator i
= self
.points_
.begin( );
652 Computation::ZBufTriangle::area( ) const
654 return Computation::triangleArea( points_
[ 0 ], points_
[ 1 ], points_
[ 2 ] );
658 Computation::ZBufTriangle::contains( const Concrete::Coords2D
& p
) const
660 for( std::vector
< Concrete::Coords2D
>::const_iterator i0
= points_
.begin( ); i0
!= points_
.end( ); ++i0
)
662 std::vector
< Concrete::Coords2D
>::const_iterator i1
= i0
;
664 if( i1
== points_
.end( ) )
666 i1
= points_
.begin( );
668 std::vector
< Concrete::Coords2D
>::const_iterator i2
= i1
;
670 if( i2
== points_
.end( ) )
672 i2
= points_
.begin( );
675 const Concrete::Coords2D
& p0( *i0
);
676 const Concrete::Coords2D
& p1( *i1
);
678 const double tx
= ( p1
.x_
- p0
.x_
).offtype
< 1, 0 >( );
679 const double ty
= ( p1
.y_
- p0
.y_
).offtype
< 1, 0 >( );
680 bool counterClockwise
; // true when ( p0, p1 ) are ordered counter-clockwise around the interior.
682 const Concrete::Length dx
= i2
->x_
- p0
.x_
;
683 const Concrete::Length dy
= i2
->y_
- p0
.y_
;
684 counterClockwise
= ( ty
* dx
- tx
* dy
< Concrete::ZERO_LENGTH
);
688 const Concrete::Length dx
= p
.x_
- p0
.x_
;
689 const Concrete::Length dy
= p
.y_
- p0
.y_
;
690 if( ( ty
* dx
- tx
* dy
> Concrete::ZERO_LENGTH
) == counterClockwise
)
701 // The larger <tol>, the more often will this function return true.
703 Computation::ZBufTriangle::contains( const Concrete::Coords2D
& p
, Concrete::Length tol
) const
705 for( std::vector
< Concrete::Coords2D
>::const_iterator i0
= points_
.begin( ); i0
!= points_
.end( ); ++i0
)
707 std::vector
< Concrete::Coords2D
>::const_iterator i1
= i0
;
709 if( i1
== points_
.end( ) )
711 i1
= points_
.begin( );
713 std::vector
< Concrete::Coords2D
>::const_iterator i2
= i1
;
715 if( i2
== points_
.end( ) )
717 i2
= points_
.begin( );
720 const Concrete::Coords2D
& p0( *i0
);
721 const Concrete::Coords2D
& p1( *i1
);
723 const Concrete::UnitFloatPair d
= p0
.normalizedOrthogonal( p1
);
724 if( Concrete::inner( d
, *i2
- p0
) < Concrete::ZERO_LENGTH
)
727 if( Concrete::inner( d
, p
- p0
) > tol
)
735 if( Concrete::inner( d
, p
- p0
) < - tol
)
746 Computation::ZBufTriangle::pushLines( std::vector
< Computation::SplicingLine
> * dst
) const
748 for( std::vector
< Concrete::Coords2D
>::const_iterator i0
= points_
.begin( ); i0
!= points_
.end( ); ++i0
)
750 std::vector
< Concrete::Coords2D
>::const_iterator i1
= i0
;
752 if( i1
== points_
.end( ) )
754 i1
= points_
.begin( );
756 pushIfUnique( dst
, *i0
, *i1
);
761 Computation::ZBufTriangle::pushIntersection( std::vector
< Computation::SplicingLine
> * dst
, const Computation::ZBufTriangle
& other
) const
763 Concrete::Coords3D
p0( 0, 0, 0 );
764 Concrete::Coords3D
p1( 0, 0, 0 );
765 if( intersectionLinePoints( other
, & p0
, & p1
) )
767 pushIfUnique( dst
, p0
, p1
, false );
772 Computation::ZBufTriangle::intersection( const Computation::ZBufTriangle
& other
, Computation::SplicingLine
* line
) const
774 Concrete::Coords3D
p03D( 0, 0, 0 );
775 Concrete::Coords3D
p13D( 0, 0, 0 );
776 if( intersectionLinePoints( other
, & p03D
, & p13D
) )
778 const Concrete::Coords2D p0
= p03D
.make2DAutomatic( zMap_
->eyez( ) );
779 const Concrete::Coords2D p1
= p13D
.make2DAutomatic( zMap_
->eyez( ) );
780 *line
= Computation::SplicingLine( p0
, p1
- p0
, false );
788 Computation::ZBufTriangle::intersectionLinePoints( const Computation::ZBufTriangle
& other
, Concrete::Coords3D
* p0
, Concrete::Coords3D
* p1
) const
792 zMap_
->writeToMatrices( a0
, & b0
);
796 other
.zMap_
->writeToMatrices( a1
, & b1
);
798 Concrete::Coords3D
ray( a0
[1]*a1
[2] - a0
[2]*a1
[1],
799 a0
[2]*a1
[0] - a0
[0]*a1
[2],
800 a0
[0]*a1
[1] - a0
[1]*a1
[0] );
802 // If the ray is zero, the planes are paralell, so there's no splicing line to add.
803 if( ray
.normScalar( ) < 1e-5 )
812 for( size_t col_i
= 0; col_i
< 3; ++col_i
, ++src
)
814 double tmp
= fabs( *src
);
822 // Here, one could check that bestCol has really been assigned.
823 // To test if it is unassigned, test for bestCol == 4.
826 const double f
= a1
[bestCol
] / a0
[bestCol
];
829 for( ; src
!= a0
+ 3; ++src
, ++dst
)
836 // The remaining two columns of the second row can now be used to determine the other two components.
837 // Let secondCol point out the biggest remaining element in a1, and zeroCol point out the column containing the smallest
838 // (non-zero) element.
839 // First, we guess...
857 throw Exceptions::InternalError( "pushIntersection: Column switch out of range." );
859 // ... then correct the guess if it's wrong
860 if( fabs( a1
[secondCol
] ) < fabs( a1
[zeroCol
] ) )
862 size_t tmp
= zeroCol
;
867 Concrete::Length res
[3];
868 // Now it's time to determine the first two components of the solution.
869 res
[zeroCol
] = Concrete::ZERO_LENGTH
;
870 res
[secondCol
] = b1
/ a1
[secondCol
];
872 // and then the final component follows by back-substitution:
873 b0
-= a0
[secondCol
] * res
[secondCol
];
874 res
[bestCol
] = b0
/ a0
[bestCol
];
876 *p0
= Concrete::Coords3D( res
[0], res
[1], res
[2] );
877 *p1
= *p0
+ Concrete::SOME_LENGTH
* ray
.direction( );
883 Computation::ZBufTriangle::pushIfUnique( std::vector
< Computation::SplicingLine
> * dst
, const Concrete::Coords3D p03D
, const Concrete::Coords3D p13D
, bool isTriangleSide
) const
885 const Concrete::Coords2D p0
= p03D
.make2DAutomatic( zMap_
->eyez( ) );
886 const Concrete::Coords2D p1
= p13D
.make2DAutomatic( zMap_
->eyez( ) );
887 typedef typeof *dst ListType
;
888 for( ListType::const_iterator i
= dst
->begin( ); i
!= dst
->end( ); ++i
)
890 if( i
->distanceTo( p0
) < Computation::theTrixelizeSplicingTol
&& i
->distanceTo( p1
) < Computation::theTrixelizeSplicingTol
)
895 dst
->push_back( Computation::SplicingLine( p0
, p1
- p0
, isTriangleSide
) );
900 typedef std::pair
< const Concrete::Coords2D
*, const Concrete::Coords2D
* > VisitType
;
905 class less
< Shapes::VisitType
>
908 bool operator () ( const Shapes::VisitType
& p1
,
909 const Shapes::VisitType
& p2
)
911 if( p1
.first
< p2
.first
)
915 if( p2
.first
< p1
.first
)
919 return p1
.second
< p2
.second
;
925 Computation::ZBufTriangle::splice( const ZBufTriangle
& tOld
, const ZBufTriangle
& tNew
, std::list
< Computation::ZBufTriangle
> * oldDisjointTriangles
, std::list
< Computation::ZBufTriangle
> * oldOccludedTriangles
, std::list
< Computation::ZBufTriangle
> * newDisjointTriangles
, std::list
< Computation::ZBufTriangle
> * newOccludedTriangles
, std::list
< Computation::ZBufTriangle
> * triangleQueue
)
927 SPLICEDEBUG( std::cerr
<< "==== Overlapping triangles ====" << std::endl
928 << " old: " << tOld
<< std::endl
929 << " new: " << tNew
<< std::endl
);
931 // This function is only called if the triangles overlap
933 std::vector
< Computation::SplicingLine
> lines
;
935 tOld
.pushLines( & lines
);
936 tNew
.pushLines( & lines
);
938 tOld
.pushIntersection( & lines
, tNew
);
940 const size_t numberOfLines
= lines
.size( );
942 SPLICEDEBUG( std::cerr
<< "#needs circle" << std::endl
943 << "#needs centering" << std::endl
945 << "@width:0bp" << std::endl
948 << "res: Hot2D <<" << std::endl
);
951 typedef typeof lines ListType
;
952 for( ListType::iterator i
= lines
.begin( ); i
!= lines
.end( ); ++i
)
954 SPLICEDEBUG( std::cerr
<< "|** Line " << ( i
- lines
.begin( ) ) << ": " );
955 // SPLICEDEBUG( std::cerr << i->p0_ << " -- " << i->p0_ + i->d_ * i->length_ << std::endl );
956 SPLICEDEBUG( std::cerr
<< std::endl
957 << "res << stroke [] "
958 << " (" << Helpers::shapesFormat( i
->p0_
.x_
) << "," << Helpers::shapesFormat( i
->p0_
.y_
)
959 << ")--(" << Helpers::shapesFormat( (i
->p0_
+ i
->d_
* i
->length_
).x_
) << "," << Helpers::shapesFormat( (i
->p0_
+ i
->d_
* i
->length_
).y_
) << ")"
961 i
->intersections_
.resize( numberOfLines
, 0 );
966 std::vector
< Concrete::Coords2D
> intersectionsMem
;
967 intersectionsMem
.reserve( numberOfLines
* ( numberOfLines
- 1 ) / 2 );
970 typedef typeof lines ListType
;
972 for( ListType::iterator i
= lines
.begin( ); i
!= lines
.end( ); ++i
, ++idx_i
)
974 SPLICEDEBUG( std::cerr
<< "|** Line " << idx_i
<< " intersections: " );
975 SPLICEDEBUG( std::cerr
<< std::endl
);
976 ListType::const_iterator j
= i
;
977 size_t idx_j
= idx_i
;
980 for( ; j
!= lines
.end( ); ++j
, ++idx_j
)
984 Concrete::Coords2D tmp
= i
->intersection( *j
);
985 typedef typeof intersectionsMem VectorType
;
987 // We try to reuse an old point. Not to save space, but to make the algorithm more robust by
988 // perhaps avoiding some corner cases this way...
989 for( VectorType::const_iterator k
= intersectionsMem
.begin( ); k
!= intersectionsMem
.end( ); ++k
)
991 if( ( tmp
- *k
).norm( ) < Computation::theTrixelizeSplicingTol
)
993 // SPLICEDEBUG( std::cerr << "<" << tmp << "> " );
994 SPLICEDEBUG( std::cerr
<< "|** reusing <" << tmp
<< "> " << std::endl
);
996 lines
[ idx_i
].intersections_
[ idx_j
] = & *k
;
997 lines
[ idx_j
].intersections_
[ idx_i
] = & *k
;
1003 // SPLICEDEBUG( std::cerr << tmp << " " );
1004 SPLICEDEBUG( std::cerr
<< "res << [shift (" << Helpers::shapesFormat( tmp
.x_
) << "," << Helpers::shapesFormat( tmp
.y_
) << ")] [] stroke [] [circle 0.1mm]" << std::endl
);
1005 intersectionsMem
.push_back( tmp
);
1006 lines
[ idx_i
].intersections_
[ idx_j
] = & intersectionsMem
.back( );
1007 lines
[ idx_j
].intersections_
[ idx_i
] = & intersectionsMem
.back( );
1010 catch( const char * )
1012 // SPLICEDEBUG( std::cerr << "(no-int)" << " " );
1013 SPLICEDEBUG( std::cerr
<< "|** (no-int)" << std::endl
);
1016 SPLICEDEBUG( std::cerr
<< std::endl
);
1020 SPLICEDEBUG( std::cerr
<< "res;" << std::endl
1021 << "bb: [bbox res]" << std::endl
1022 << "@<< [scale 19cm/[max [xmax bb]-[xmin bb] [ymax bb]-[ymin bb]]] [] res" << std::endl
1023 << "}" << std::endl
);
1025 std::set
< VisitType
> visited
;
1027 for( size_t start_a
= 0; start_a
< numberOfLines
; ++start_a
)
1029 if( ! lines
[ start_a
].isTriangleSide_
)
1033 for( size_t start_b
= 0; start_b
< numberOfLines
; ++start_b
)
1035 if( start_b
== start_a
)
1039 SPLICEDEBUG( std::cerr
<< "From line " << start_a
<< " to line " << start_b
<< std::endl
);
1040 const Concrete::Coords2D
* p0
= lines
[ start_a
].intersections_
[ start_b
];
1043 SPLICEDEBUG( std::cerr
<< " No intersection" << std::endl
);
1046 Concrete::UnitFloatPair start_n
= lines
[ start_a
].n_
;
1047 for( char start_n_i
= 0; start_n_i
< 2; ++start_n_i
, start_n
= start_n
.reverse( ) )
1049 SPLICEDEBUG( std::cerr
<< " Starting direction " << static_cast< int >( start_n_i
) << std::endl
);
1050 Concrete::UnitFloatPair n
= start_n
;
1051 size_t currentLine
= start_b
;
1055 nextLine
= lines
[ currentLine
].nextLine( p0
, n
, lines
);
1056 SPLICEDEBUG( std::cerr
<< "Line " << currentLine
<< " --> " << nextLine
<< std::endl
);
1058 catch( const char * ball
)
1062 const Concrete::Coords2D
* p1
= lines
[ currentLine
].intersections_
[ nextLine
];
1063 if( visited
.find( VisitType( p0
, p1
) ) != visited
.end( ) )
1065 SPLICEDEBUG( std::cerr
<< *p0
<< " --> " << *p1
<< " already visited" << std::endl
);
1068 visited
.insert( VisitType( p0
, p1
) );
1070 // visitedLines is used to tell when we have completed a polygon; when a line is visited a second time,
1071 // the polygon is complete. The first point is on start_b. start_a is only used to give a direction along
1073 std::vector
< bool > visitedLines
;
1074 visitedLines
.resize( numberOfLines
, false );
1075 visitedLines
[ currentLine
] = true;
1078 Concrete::UnitFloatPair oldn
= n
;
1079 n
= lines
[ currentLine
].n_
;
1080 if( - oldn
.y_
* n
.x_
+ oldn
.x_
* n
.y_
< 0 )
1086 const Concrete::Coords2D
* p2
= 0;
1088 currentLine
= nextLine
;
1091 nextLine
= lines
[ currentLine
].nextLine( p1
, n
, lines
);
1092 SPLICEDEBUG( std::cerr
<< "Line " << currentLine
<< " --> " << nextLine
<< std::endl
);
1094 catch( const char * ball
)
1096 SPLICEDEBUG( std::cerr
<< "Line " << currentLine
<< " --> " << "infinity! (no enclosed region)" << std::endl
);
1099 p2
= lines
[ currentLine
].intersections_
[ nextLine
];
1100 visited
.insert( VisitType( p1
, p2
) );
1101 visitedLines
[ currentLine
] = true;
1103 // Here, we choose a way to compute a point well inside the *p0--*p1--*p2 triangle.
1104 // Using the mean is quick, but the incenter should be more robust.
1105 Concrete::Coords2D mean
= (1./3) * ( *p0
+ *p1
+ *p2
);
1106 // Concrete::Coords2D mean = Computation::triangleIncenter( *p0, *p1, *p2 );
1108 // The following test never triggers, which is good.
1109 // if( tOld.contains( mean ) &&
1110 // ( ( ! tOld.contains( *p0, Computation::theTrixelizeSplicingTol ) ) ||
1111 // ( ! tOld.contains( *p1, Computation::theTrixelizeSplicingTol ) ) ||
1112 // ( ! tOld.contains( *p2, Computation::theTrixelizeSplicingTol ) ) ) )
1114 // std::cerr << "tOld contains mean but not all corners!" << std::endl ;
1116 // if( tNew.contains( mean ) &&
1117 // ( ( ! tNew.contains( *p0, Computation::theTrixelizeSplicingTol ) ) ||
1118 // ( ! tNew.contains( *p1, Computation::theTrixelizeSplicingTol ) ) ||
1119 // ( ! tNew.contains( *p2, Computation::theTrixelizeSplicingTol ) ) ) )
1121 // std::cerr << "tNew contains mean but not all corners!" << std::endl ;
1126 const Computation::ZBufTriangle
* topTriangle
= 0;
1127 bool reQueue
= true;
1128 std::list
< Computation::ZBufTriangle
> * disjointDestination
= 0; // this must be assigned when ( ! reQueue )
1129 if( tOld
.contains( mean
) )
1132 if( tNew
.contains( mean
) )
1134 if( tOld
.isOnTopOfAt( tNew
, mean
) )
1136 topTriangle
= & tOld
;
1137 disjointDestination
= oldDisjointTriangles
;
1138 SPLICEDEBUG( std::cerr
<< "Part of tOld" << std::endl
);
1142 topTriangle
= & tNew
;
1143 disjointDestination
= newDisjointTriangles
;
1144 SPLICEDEBUG( std::cerr
<< "Part of tNew" << std::endl
);
1149 topTriangle
= & tOld
;
1150 disjointDestination
= oldDisjointTriangles
;
1151 SPLICEDEBUG( std::cerr
<< "Part of tOld" << std::endl
);
1156 if( tNew
.contains( mean
) )
1158 topTriangle
= & tNew
;
1159 SPLICEDEBUG( std::cerr
<< "Part of tNew" << std::endl
);
1163 SPLICEDEBUG( std::cerr
<< "Outside painted area" << std::endl
);
1171 undoSize
= triangleQueue
->size( );
1175 undoSize
= disjointDestination
->size( );
1178 // This tolerance test assures that we don't produce tiny-tiny triangles.
1179 if( Computation::triangleArea( *p0
, *p1
, *p2
) > Computation::theTrixelizeOverlapTol
* Computation::triangleSemiPerimeter( *p0
, *p1
, *p2
) )
1183 triangleQueue
->push_back( Computation::ZBufTriangle( topTriangle
->painter_
,
1189 disjointDestination
->push_back( Computation::ZBufTriangle( topTriangle
->painter_
,
1197 Concrete::UnitFloatPair oldn
= n
;
1198 n
= lines
[ currentLine
].n_
;
1199 if( - oldn
.y_
* n
.x_
+ oldn
.x_
* n
.y_
< 0 )
1205 bool insertTriangles
= true;
1207 while( ! visitedLines
[ nextLine
] )
1209 currentLine
= nextLine
;
1212 nextLine
= lines
[ currentLine
].nextLine( p1
, n
, lines
);
1213 SPLICEDEBUG( std::cerr
<< "Line " << currentLine
<< " --> " << nextLine
<< std::endl
);
1215 catch( const char * ball
)
1217 SPLICEDEBUG( std::cerr
<< "Line " << currentLine
<< " --> " << "infinity! (no enclosed region)" << std::endl
);
1218 insertTriangles
= false;
1221 p2
= lines
[ currentLine
].intersections_
[ nextLine
];
1222 visited
.insert( VisitType( p1
, p2
) );
1223 visitedLines
[ currentLine
] = true;
1225 if( Computation::triangleArea( *p0
, *p1
, *p2
) > Computation::theTrixelizeOverlapTol
* Computation::triangleSemiPerimeter( *p0
, *p1
, *p2
) )
1229 triangleQueue
->push_back( Computation::ZBufTriangle( topTriangle
->painter_
,
1235 disjointDestination
->push_back( Computation::ZBufTriangle( topTriangle
->painter_
,
1243 Concrete::UnitFloatPair oldn
= n
;
1244 n
= lines
[ currentLine
].n_
;
1245 if( - oldn
.y_
* n
.x_
+ oldn
.x_
* n
.y_
< 0 )
1251 if( insertTriangles
)
1253 visited
.insert( VisitType( p2
, p0
) );
1254 SPLICEDEBUG( std::cerr
<< "Found new region." << std::endl
);
1260 while( triangleQueue
->size( ) > undoSize
)
1262 triangleQueue
->pop_back( );
1267 while( disjointDestination
->size( ) > undoSize
)
1269 disjointDestination
->pop_back( );
1278 std::list
< Computation::ZBufTriangle
>::iterator
1279 Computation::ZBufTriangle::spliceAlong( const Computation::SplicingLine
& line
, std::list
< Computation::ZBufTriangle
> * dst
) const
1282 // Two of the triangle sides will be intersected by the line. A second line will have to be added to split the bottom
1283 // part of the splitted triangle in two triangles.
1284 // First two two intersections are identified along with the sides they belong to. Then the triangle corners can be identified
1285 // and the three triangles be created.
1287 // Let p0 be the point on the intersection of the intereced triangle sides.
1288 // Let pa be the intersection on the line p0--p1,
1289 // and pb be the intersection on the line p0--p2.
1291 // This variable holds each corner points (signed) distance to the line.
1292 Concrete::Length lineDists
[ 3 ];
1294 Concrete::Length
* distDst
= & lineDists
[ 0 ];
1295 for( std::vector
< Concrete::Coords2D
>::const_iterator i
= points_
.begin( ); i
!= points_
.end( ); ++i
, ++distDst
)
1297 *distDst
= Concrete::inner( line
.n_
, *i
) - line
.r_
;
1301 // However, the special case when the line intersects one of the corners will generate just two triangles. This case is
1302 // considered first.
1304 const Concrete::Length
* distSrc
= & lineDists
[ 0 ];
1305 for( std::vector
< Concrete::Coords2D
>::const_iterator i
= points_
.begin( ); i
!= points_
.end( ); ++i
, ++distSrc
)
1307 if( distSrc
->abs( ) < Computation::theTrixelizeSplicingTol
)
1309 // Here p0 coincides either of pa or pb, and here it is *i.
1310 // Let pa denote the intersection with the opposide triangle side.
1313 std::vector
< Concrete::Coords2D
>::const_iterator i1
= i
;
1315 if( i1
== points_
.end( ) )
1317 i1
= points_
.begin( );
1321 std::vector
< Concrete::Coords2D
>::const_iterator i2
= i1
;
1323 if( i2
== points_
.end( ) )
1325 i2
= points_
.begin( );
1328 // Parameterize the line segment from p1 to p2 as ( p1 + t * d )
1329 Concrete::Coords2D d
= *i2
- *i1
;
1330 // Then t can be computed easily using the equation of the line.
1331 Concrete::Coords2D pa
= *i1
+ ( ( line
.r_
- Concrete::inner( line
.n_
, *i1
) ) / Concrete::inner( line
.n_
, d
) ) * d
;
1333 dst
->push_back( Computation::ZBufTriangle( painter_
,
1336 std::list
< Computation::ZBufTriangle
>::iterator res
= dst
->end( );
1339 dst
->push_back( Computation::ZBufTriangle( painter_
,
1347 // Turning the question of intersecting sides around, I search for the side which is not intersected by the line.
1348 // This side is identified by its both endpoints being on the same side of the line.
1349 // By now we assume that we don't run into corner cases when there's no clear cut.
1351 // Since only one line can avoid being intersected by the line, two distances will have the same sign, and the last
1352 // corner will have a distance to the line of the other sign. Hence, the product of all signs will be the sign of the corner
1353 // not belonging to the avoiding line.
1354 bool p0sign
= ( lineDists
[ 0 ] > 0 ) ^ ( lineDists
[ 1 ] > 0 ) ^ ( lineDists
[ 2 ] > 0 );
1357 const Concrete::Length
* distSrc
= & lineDists
[ 0 ];
1358 for( std::vector
< Concrete::Coords2D
>::const_iterator i
= points_
.begin( ); i
!= points_
.end( ); ++i
, ++distSrc
)
1360 if( ( *distSrc
> 0 ) == p0sign
)
1362 // We have p0 being *i
1365 std::vector
< Concrete::Coords2D
>::const_iterator i1
= i
;
1367 if( i1
== points_
.end( ) )
1369 i1
= points_
.begin( );
1373 std::vector
< Concrete::Coords2D
>::const_iterator i2
= i1
;
1375 if( i2
== points_
.end( ) )
1377 i2
= points_
.begin( );
1380 // Parameterize the line segment from p0 to p1 as ( p0 + ta * da )
1381 Concrete::Coords2D da
= *i1
- *i
;
1382 // Then ta can be computed easily using the equation of the line, and then inserted to obtain pa.
1383 Concrete::Coords2D pa
= *i
+ ( ( line
.r_
- Concrete::inner( line
.n_
, *i
) ) / Concrete::inner( line
.n_
, da
) ) * da
;
1385 // Parameterize the line segment from p0 to p2 as ( p0 + tb * db )
1386 Concrete::Coords2D db
= *i2
- *i
;
1387 // Then tb can be computed easily using the equation of the line, and then inserted to obtain pb.
1388 Concrete::Coords2D pb
= *i
+ ( ( line
.r_
- Concrete::inner( line
.n_
, *i
) ) / Concrete::inner( line
.n_
, db
) ) * db
;
1390 dst
->push_back( Computation::ZBufTriangle( painter_
,
1393 std::list
< Computation::ZBufTriangle
>::iterator res
= dst
->end( );
1396 dst
->push_back( Computation::ZBufTriangle( painter_
,
1399 dst
->push_back( Computation::ZBufTriangle( painter_
,
1408 throw Exceptions::InternalError( "Failed to identify p0 when splicing triangle along a line." );
1412 RefCountPtr
< const Lang::ElementaryPath2D
>
1413 Computation::ZBufTriangle::toPath( ) const
1415 Lang::ElementaryPath2D
* res
= new Lang::ElementaryPath2D
;
1417 for( std::vector
< Concrete::Coords2D
>::const_iterator i
= points_
.begin( ); i
!= points_
.end( ); ++i
)
1419 res
->push_back( new Concrete::PathPoint2D( i
->x_
, i
->y_
) );
1423 return RefCountPtr
< const Lang::ElementaryPath2D
>( res
);
1426 RefCountPtr
< const Lang::Drawable2D
>
1427 Computation::ZBufTriangle::debugFrame( ) const
1429 const Concrete::Coords2D
& p1( points_
[ 0 ] );
1430 const Concrete::Coords2D
& p2( points_
[ 1 ] );
1431 const Concrete::Coords2D
& p3( points_
[ 2 ] );
1433 SPLICEDEBUG( std::cerr
<< "Debug frame: " << p1
<< " -- " << p2
<< " -- " << p3
<< std::endl
; )
1435 Kernel::GraphicsState
* discStatePtr
= new Kernel::GraphicsState( true );
1436 discStatePtr
->cap_
= Lang::CapStyle::CAP_ROUND
;
1437 discStatePtr
->width_
= 2 * Computation::triangleArea( p1
, p2
, p3
) / Computation::triangleSemiPerimeter( p1
, p2
, p3
);
1438 discStatePtr
->strokingColor_
= painter_
->getColor( );
1439 RefCountPtr
< const Kernel::GraphicsState
> discState( discStatePtr
);
1441 Kernel::GraphicsState
* frameStatePtr
= new Kernel::GraphicsState( true );
1442 frameStatePtr
->width_
= Concrete::Length( 0.2 );
1443 RefCountPtr
< const Kernel::GraphicsState
> frameState( frameStatePtr
);
1445 Lang::ElementaryPath2D
* pointPath
= new Lang::ElementaryPath2D
;
1446 const Concrete::Coords2D incenter
= Computation::triangleIncenter( p1
, p2
, p3
);
1447 pointPath
->push_back( new Concrete::PathPoint2D( incenter
.x_
, incenter
.y_
) );
1448 pointPath
->push_back( new Concrete::PathPoint2D( incenter
.x_
, incenter
.y_
) );
1450 SPLICEDEBUG( std::cerr
<< " incenter: " << incenter
<< std::endl
);
1451 SPLICEDEBUG( std::cerr
<< " radius: " << Lang::Length( discState
->width_
) << std::endl
);
1453 return Helpers::newSolidTransparencyGroup( RefCountPtr
< const Lang::Drawable2D
>
1454 ( new Lang::PaintedPath2D( frameState
, toPath( ), "S" ) ),
1455 RefCountPtr
< const Lang::Drawable2D
>
1456 ( new Lang::PaintedPath2D( discState
, RefCountPtr
< const Lang::ElementaryPath2D
>( pointPath
), "S" ) ) );