Line data Source code
1 : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : /*
3 : * This file is part of the LibreOffice project.
4 : *
5 : * This Source Code Form is subject to the terms of the Mozilla Public
6 : * License, v. 2.0. If a copy of the MPL was not distributed with this
7 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 : *
9 : * This file incorporates work covered by the following license notice:
10 : *
11 : * Licensed to the Apache Software Foundation (ASF) under one or more
12 : * contributor license agreements. See the NOTICE file distributed
13 : * with this work for additional information regarding copyright
14 : * ownership. The ASF licenses this file to you under the Apache
15 : * License, Version 2.0 (the "License"); you may not use this file
16 : * except in compliance with the License. You may obtain a copy of
17 : * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 : */
19 :
20 : #include <basegfx/polygon/b2dpolygonclipper.hxx>
21 : #include <osl/diagnose.h>
22 : #include <basegfx/polygon/b2dpolygontools.hxx>
23 : #include <basegfx/numeric/ftools.hxx>
24 : #include <basegfx/matrix/b2dhommatrix.hxx>
25 : #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
26 : #include <basegfx/polygon/b2dpolygoncutandtouch.hxx>
27 : #include <basegfx/polygon/b2dpolypolygontools.hxx>
28 : #include <basegfx/curve/b2dcubicbezier.hxx>
29 : #include <basegfx/tools/rectcliptools.hxx>
30 : #include <basegfx/matrix/b2dhommatrixtools.hxx>
31 :
32 : //////////////////////////////////////////////////////////////////////////////
33 :
34 : namespace basegfx
35 : {
36 : namespace tools
37 : {
38 3 : B2DPolyPolygon clipPolygonOnParallelAxis(const B2DPolygon& rCandidate, bool bParallelToXAxis, bool bAboveAxis, double fValueOnOtherAxis, bool bStroke)
39 : {
40 3 : B2DPolyPolygon aRetval;
41 :
42 3 : if(rCandidate.count())
43 : {
44 3 : const B2DRange aCandidateRange(getRange(rCandidate));
45 :
46 3 : if(bParallelToXAxis && fTools::moreOrEqual(aCandidateRange.getMinY(), fValueOnOtherAxis))
47 : {
48 : // completely above and on the clip line. also true for curves.
49 2 : if(bAboveAxis)
50 : {
51 : // add completely
52 1 : aRetval.append(rCandidate);
53 : }
54 : }
55 1 : else if(bParallelToXAxis && fTools::lessOrEqual(aCandidateRange.getMaxY(), fValueOnOtherAxis))
56 : {
57 : // completely below and on the clip line. also true for curves.
58 0 : if(!bAboveAxis)
59 : {
60 : // add completely
61 0 : aRetval.append(rCandidate);
62 : }
63 : }
64 1 : else if(!bParallelToXAxis && fTools::moreOrEqual(aCandidateRange.getMinX(), fValueOnOtherAxis))
65 : {
66 : // completely right of and on the clip line. also true for curves.
67 1 : if(bAboveAxis)
68 : {
69 : // add completely
70 1 : aRetval.append(rCandidate);
71 : }
72 : }
73 0 : else if(!bParallelToXAxis && fTools::lessOrEqual(aCandidateRange.getMaxX(), fValueOnOtherAxis))
74 : {
75 : // completely left of and on the clip line. also true for curves.
76 0 : if(!bAboveAxis)
77 : {
78 : // add completely
79 0 : aRetval.append(rCandidate);
80 : }
81 : }
82 : else
83 : {
84 : // add cuts with axis to polygon, including bezier segments
85 : // Build edge to cut with. Make it a little big longer than needed for
86 : // numerical stability. We want to cut against the edge seen as endless
87 : // ray here, but addPointsAtCuts() will limit itself to the
88 : // edge's range ]0.0 .. 1.0[.
89 0 : const double fSmallExtension((aCandidateRange.getWidth() + aCandidateRange.getHeight()) * (0.5 * 0.1));
90 : const B2DPoint aStart(
91 0 : bParallelToXAxis ? aCandidateRange.getMinX() - fSmallExtension : fValueOnOtherAxis,
92 0 : bParallelToXAxis ? fValueOnOtherAxis : aCandidateRange.getMinY() - fSmallExtension);
93 : const B2DPoint aEnd(
94 0 : bParallelToXAxis ? aCandidateRange.getMaxX() + fSmallExtension : fValueOnOtherAxis,
95 0 : bParallelToXAxis ? fValueOnOtherAxis : aCandidateRange.getMaxY() + fSmallExtension);
96 0 : const B2DPolygon aCandidate(addPointsAtCuts(rCandidate, aStart, aEnd));
97 0 : const sal_uInt32 nPointCount(aCandidate.count());
98 0 : const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L);
99 0 : B2DCubicBezier aEdge;
100 0 : B2DPolygon aRun;
101 :
102 0 : for(sal_uInt32 a(0L); a < nEdgeCount; a++)
103 : {
104 0 : aCandidate.getBezierSegment(a, aEdge);
105 0 : const B2DPoint aTestPoint(aEdge.interpolatePoint(0.5));
106 : const bool bInside(bParallelToXAxis ?
107 0 : fTools::moreOrEqual(aTestPoint.getY(), fValueOnOtherAxis) == bAboveAxis :
108 0 : fTools::moreOrEqual(aTestPoint.getX(), fValueOnOtherAxis) == bAboveAxis);
109 :
110 0 : if(bInside)
111 : {
112 0 : if(!aRun.count() || !aRun.getB2DPoint(aRun.count() - 1).equal(aEdge.getStartPoint()))
113 : {
114 0 : aRun.append(aEdge.getStartPoint());
115 : }
116 :
117 0 : if(aEdge.isBezier())
118 : {
119 0 : aRun.appendBezierSegment(aEdge.getControlPointA(), aEdge.getControlPointB(), aEdge.getEndPoint());
120 : }
121 : else
122 : {
123 0 : aRun.append(aEdge.getEndPoint());
124 : }
125 : }
126 : else
127 : {
128 0 : if(bStroke && aRun.count())
129 : {
130 0 : aRetval.append(aRun);
131 0 : aRun.clear();
132 : }
133 : }
134 0 : }
135 :
136 0 : if(aRun.count())
137 : {
138 0 : if(bStroke)
139 : {
140 : // try to merge this last and first polygon; they may have been
141 : // the former polygon's start/end point
142 0 : if(aRetval.count())
143 : {
144 0 : const B2DPolygon aStartPolygon(aRetval.getB2DPolygon(0));
145 :
146 0 : if(aStartPolygon.count() && aStartPolygon.getB2DPoint(0).equal(aRun.getB2DPoint(aRun.count() - 1)))
147 : {
148 : // append start polygon to aRun, remove from result set
149 0 : aRun.append(aStartPolygon); aRun.removeDoublePoints();
150 0 : aRetval.remove(0);
151 0 : }
152 : }
153 :
154 0 : aRetval.append(aRun);
155 : }
156 : else
157 : {
158 : // set closed flag and correct last point (which is added double now).
159 0 : closeWithGeometryChange(aRun);
160 0 : aRetval.append(aRun);
161 : }
162 0 : }
163 : }
164 : }
165 :
166 3 : return aRetval;
167 : }
168 :
169 0 : B2DPolyPolygon clipPolyPolygonOnParallelAxis(const B2DPolyPolygon& rCandidate, bool bParallelToXAxis, bool bAboveAxis, double fValueOnOtherAxis, bool bStroke)
170 : {
171 0 : const sal_uInt32 nPolygonCount(rCandidate.count());
172 0 : B2DPolyPolygon aRetval;
173 :
174 0 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
175 : {
176 0 : const B2DPolyPolygon aClippedPolyPolygon(clipPolygonOnParallelAxis(rCandidate.getB2DPolygon(a), bParallelToXAxis, bAboveAxis, fValueOnOtherAxis, bStroke));
177 :
178 0 : if(aClippedPolyPolygon.count())
179 : {
180 0 : aRetval.append(aClippedPolyPolygon);
181 : }
182 0 : }
183 :
184 0 : return aRetval;
185 : }
186 :
187 1 : B2DPolyPolygon clipPolygonOnRange(const B2DPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke)
188 : {
189 1 : const sal_uInt32 nCount(rCandidate.count());
190 1 : B2DPolyPolygon aRetval;
191 :
192 1 : if(!nCount)
193 : {
194 : // source is empty
195 0 : return aRetval;
196 : }
197 :
198 1 : if(rRange.isEmpty())
199 : {
200 0 : if(bInside)
201 : {
202 : // nothing is inside an empty range
203 0 : return aRetval;
204 : }
205 : else
206 : {
207 : // everything is outside an empty range
208 0 : return B2DPolyPolygon(rCandidate);
209 : }
210 : }
211 :
212 1 : const B2DRange aCandidateRange(getRange(rCandidate));
213 :
214 1 : if(rRange.isInside(aCandidateRange))
215 : {
216 : // candidate is completely inside given range
217 0 : if(bInside)
218 : {
219 : // nothing to do
220 0 : return B2DPolyPolygon(rCandidate);
221 : }
222 : else
223 : {
224 : // nothing is outside, then
225 0 : return aRetval;
226 : }
227 : }
228 :
229 1 : if(!bInside)
230 : {
231 : // cutting off the outer parts of filled polygons at parallell
232 : // lines to the axes is only possible for the inner part, not for
233 : // the outer part which means cutting a hole into the original polygon.
234 : // This is because the inner part is a logical AND-operation of
235 : // the four implied half-planes, but the outer part is not.
236 : // It is possible for strokes, but with creating unnecessary extra
237 : // cuts, so using clipPolygonOnPolyPolygon is better there, too.
238 : // This needs to be done with the topology knowlegde and is unfurtunately
239 : // more expensive, too.
240 0 : const B2DPolygon aClip(createPolygonFromRect(rRange));
241 :
242 0 : return clipPolygonOnPolyPolygon(rCandidate, B2DPolyPolygon(aClip), bInside, bStroke);
243 : }
244 :
245 : // clip against the four axes of the range
246 : // against X-Axis, lower value
247 1 : aRetval = clipPolygonOnParallelAxis(rCandidate, true, bInside, rRange.getMinY(), bStroke);
248 :
249 1 : if(aRetval.count())
250 : {
251 : // against Y-Axis, lower value
252 1 : if(1L == aRetval.count())
253 : {
254 1 : aRetval = clipPolygonOnParallelAxis(aRetval.getB2DPolygon(0L), false, bInside, rRange.getMinX(), bStroke);
255 : }
256 : else
257 : {
258 0 : aRetval = clipPolyPolygonOnParallelAxis(aRetval, false, bInside, rRange.getMinX(), bStroke);
259 : }
260 :
261 1 : if(aRetval.count())
262 : {
263 : // against X-Axis, higher value
264 1 : if(1L == aRetval.count())
265 : {
266 1 : aRetval = clipPolygonOnParallelAxis(aRetval.getB2DPolygon(0L), true, !bInside, rRange.getMaxY(), bStroke);
267 : }
268 : else
269 : {
270 0 : aRetval = clipPolyPolygonOnParallelAxis(aRetval, true, !bInside, rRange.getMaxY(), bStroke);
271 : }
272 :
273 1 : if(aRetval.count())
274 : {
275 : // against Y-Axis, higher value
276 0 : if(1L == aRetval.count())
277 : {
278 0 : aRetval = clipPolygonOnParallelAxis(aRetval.getB2DPolygon(0L), false, !bInside, rRange.getMaxX(), bStroke);
279 : }
280 : else
281 : {
282 0 : aRetval = clipPolyPolygonOnParallelAxis(aRetval, false, !bInside, rRange.getMaxX(), bStroke);
283 : }
284 : }
285 : }
286 : }
287 :
288 1 : return aRetval;
289 : }
290 :
291 1 : B2DPolyPolygon clipPolyPolygonOnRange(const B2DPolyPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke)
292 : {
293 1 : const sal_uInt32 nPolygonCount(rCandidate.count());
294 1 : B2DPolyPolygon aRetval;
295 :
296 1 : if(!nPolygonCount)
297 : {
298 : // source is empty
299 0 : return aRetval;
300 : }
301 :
302 1 : if(rRange.isEmpty())
303 : {
304 0 : if(bInside)
305 : {
306 : // nothing is inside an empty range
307 0 : return aRetval;
308 : }
309 : else
310 : {
311 : // everything is outside an empty range
312 0 : return rCandidate;
313 : }
314 : }
315 :
316 1 : if(bInside)
317 : {
318 2 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
319 : {
320 1 : const B2DPolyPolygon aClippedPolyPolygon(clipPolygonOnRange(rCandidate.getB2DPolygon(a), rRange, bInside, bStroke));
321 :
322 1 : if(aClippedPolyPolygon.count())
323 : {
324 0 : aRetval.append(aClippedPolyPolygon);
325 : }
326 1 : }
327 : }
328 : else
329 : {
330 : // for details, see comment in clipPolygonOnRange for the "cutting off
331 : // the outer parts of filled polygons at parallell lines" explanations
332 0 : const B2DPolygon aClip(createPolygonFromRect(rRange));
333 :
334 0 : return clipPolyPolygonOnPolyPolygon(rCandidate, B2DPolyPolygon(aClip), bInside, bStroke);
335 : }
336 :
337 1 : return aRetval;
338 : }
339 :
340 : //////////////////////////////////////////////////////////////////////////////
341 :
342 237 : B2DPolyPolygon clipPolyPolygonOnPolyPolygon(const B2DPolyPolygon& rCandidate, const B2DPolyPolygon& rClip, bool bInside, bool bStroke)
343 : {
344 237 : B2DPolyPolygon aRetval;
345 :
346 237 : if(rCandidate.count() && rClip.count())
347 : {
348 237 : if(bStroke)
349 : {
350 : // line clipping, create line snippets by first adding all cut points and
351 : // then marching along the edges and detecting if they are inside or outside
352 : // the clip polygon
353 140 : for(sal_uInt32 a(0); a < rCandidate.count(); a++)
354 : {
355 : // add cuts with clip to polygon, including bezier segments
356 70 : const B2DPolygon aCandidate(addPointsAtCuts(rCandidate.getB2DPolygon(a), rClip));
357 70 : const sal_uInt32 nPointCount(aCandidate.count());
358 70 : const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L);
359 70 : B2DCubicBezier aEdge;
360 70 : B2DPolygon aRun;
361 :
362 326 : for(sal_uInt32 b(0); b < nEdgeCount; b++)
363 : {
364 256 : aCandidate.getBezierSegment(b, aEdge);
365 256 : const B2DPoint aTestPoint(aEdge.interpolatePoint(0.5));
366 256 : const bool bIsInside(tools::isInside(rClip, aTestPoint) == bInside);
367 :
368 256 : if(bIsInside)
369 : {
370 70 : if(!aRun.count())
371 : {
372 70 : aRun.append(aEdge.getStartPoint());
373 : }
374 :
375 70 : if(aEdge.isBezier())
376 : {
377 0 : aRun.appendBezierSegment(aEdge.getControlPointA(), aEdge.getControlPointB(), aEdge.getEndPoint());
378 : }
379 : else
380 : {
381 70 : aRun.append(aEdge.getEndPoint());
382 : }
383 : }
384 : else
385 : {
386 186 : if(aRun.count())
387 : {
388 62 : aRetval.append(aRun);
389 62 : aRun.clear();
390 : }
391 : }
392 256 : }
393 :
394 70 : if(aRun.count())
395 : {
396 : // try to merge this last and first polygon; they may have been
397 : // the former polygon's start/end point
398 8 : if(aRetval.count())
399 : {
400 0 : const B2DPolygon aStartPolygon(aRetval.getB2DPolygon(0));
401 :
402 0 : if(aStartPolygon.count() && aStartPolygon.getB2DPoint(0).equal(aRun.getB2DPoint(aRun.count() - 1)))
403 : {
404 : // append start polygon to aRun, remove from result set
405 0 : aRun.append(aStartPolygon); aRun.removeDoublePoints();
406 0 : aRetval.remove(0);
407 0 : }
408 : }
409 :
410 8 : aRetval.append(aRun);
411 : }
412 70 : }
413 : }
414 : else
415 : {
416 : // area clipping
417 167 : B2DPolyPolygon aMergePolyPolygonA(rClip);
418 :
419 : // First solve all polygon-self and polygon-polygon intersections.
420 : // Also get rid of some not-needed polygons (neutral, no area -> when
421 : // no intersections, these are tubes).
422 : // Now it is possible to correct the orientations in the cut-free
423 : // polygons to values corresponding to painting the PolyPolygon with
424 : // a XOR-WindingRule.
425 167 : aMergePolyPolygonA = solveCrossovers(aMergePolyPolygonA);
426 167 : aMergePolyPolygonA = stripNeutralPolygons(aMergePolyPolygonA);
427 167 : aMergePolyPolygonA = correctOrientations(aMergePolyPolygonA);
428 :
429 167 : if(!bInside)
430 : {
431 : // if we want to get the outside of the clip polygon, make
432 : // it a 'Hole' in topological sense
433 0 : aMergePolyPolygonA.flip();
434 : }
435 :
436 167 : B2DPolyPolygon aMergePolyPolygonB(rCandidate);
437 :
438 : // prepare 2nd source polygon in same way
439 167 : aMergePolyPolygonB = solveCrossovers(aMergePolyPolygonB);
440 167 : aMergePolyPolygonB = stripNeutralPolygons(aMergePolyPolygonB);
441 167 : aMergePolyPolygonB = correctOrientations(aMergePolyPolygonB);
442 :
443 : // to clip against each other, concatenate and solve all
444 : // polygon-polygon crossovers. polygon-self do not need to
445 : // be solved again, they were solved in the preparation.
446 167 : aRetval.append(aMergePolyPolygonA);
447 167 : aRetval.append(aMergePolyPolygonB);
448 167 : aRetval = solveCrossovers(aRetval);
449 :
450 : // now remove neutral polygons (closed, but no area). In a last
451 : // step throw away all polygons which have a depth of less than 1
452 : // which means there was no logical AND at their position. For the
453 : // not-inside solution, the clip was flipped to define it as 'Hole',
454 : // so the removal rule is different here; remove all with a depth
455 : // of less than 0 (aka holes).
456 167 : aRetval = stripNeutralPolygons(aRetval);
457 167 : aRetval = stripDispensablePolygons(aRetval, bInside);
458 : }
459 : }
460 :
461 237 : return aRetval;
462 : }
463 :
464 : //////////////////////////////////////////////////////////////////////////////
465 :
466 232 : B2DPolyPolygon clipPolygonOnPolyPolygon(const B2DPolygon& rCandidate, const B2DPolyPolygon& rClip, bool bInside, bool bStroke)
467 : {
468 232 : B2DPolyPolygon aRetval;
469 :
470 232 : if(rCandidate.count() && rClip.count())
471 : {
472 232 : aRetval = clipPolyPolygonOnPolyPolygon(B2DPolyPolygon(rCandidate), rClip, bInside, bStroke);
473 : }
474 :
475 232 : return aRetval;
476 : }
477 :
478 : //////////////////////////////////////////////////////////////////////////////
479 :
480 : /*
481 : * let a plane be defined as
482 : *
483 : * v.n+d=0
484 : *
485 : * and a ray be defined as
486 : *
487 : * a+(b-a)*t=0
488 : *
489 : * substitute and rearranging yields
490 : *
491 : * t = -(a.n+d)/(n.(b-a))
492 : *
493 : * if the denominator is zero, the line is either
494 : * contained in the plane or parallel to the plane.
495 : * in either case, there is no intersection.
496 : * if numerator and denominator are both zero, the
497 : * ray is contained in the plane.
498 : *
499 : */
500 : struct scissor_plane {
501 : double nx,ny; // plane normal
502 : double d; // [-] minimum distance from origin
503 : sal_uInt32 clipmask; // clipping mask, e.g. 1000 1000
504 : };
505 :
506 : /*
507 : *
508 : * polygon clipping rules (straight out of Foley and Van Dam)
509 : * ===========================================================
510 : * current |next |emit
511 : * ____________________________________
512 : * inside |inside |next
513 : * inside |outside |intersect with clip plane
514 : * outside |outside |nothing
515 : * outside |inside |intersect with clip plane follwed by next
516 : *
517 : */
518 0 : sal_uInt32 scissorLineSegment( ::basegfx::B2DPoint *in_vertex, // input buffer
519 : sal_uInt32 in_count, // number of verts in input buffer
520 : ::basegfx::B2DPoint *out_vertex, // output buffer
521 : scissor_plane *pPlane, // scissoring plane
522 : const ::basegfx::B2DRectangle &rR ) // clipping rectangle
523 : {
524 : ::basegfx::B2DPoint *curr;
525 : ::basegfx::B2DPoint *next;
526 :
527 0 : sal_uInt32 out_count=0;
528 :
529 : // process all the verts
530 0 : for(sal_uInt32 i=0; i<in_count; i++) {
531 :
532 : // vertices are relative to the coordinate
533 : // system defined by the rectangle.
534 0 : curr = &in_vertex[i];
535 0 : next = &in_vertex[(i+1)%in_count];
536 :
537 : // perform clipping judgement & mask against current plane.
538 0 : sal_uInt32 clip = pPlane->clipmask & ((getCohenSutherlandClipFlags(*curr,rR)<<4)|getCohenSutherlandClipFlags(*next,rR));
539 :
540 0 : if(clip==0) { // both verts are inside
541 0 : out_vertex[out_count++] = *next;
542 : }
543 0 : else if((clip&0x0f) && (clip&0xf0)) { // both verts are outside
544 : }
545 0 : else if((clip&0x0f) && (clip&0xf0)==0) { // curr is inside, next is outside
546 :
547 : // direction vector from 'current' to 'next', *not* normalized
548 : // to bring 't' into the [0<=x<=1] intervall.
549 0 : ::basegfx::B2DPoint dir((*next)-(*curr));
550 :
551 0 : double denominator = ( pPlane->nx*dir.getX() +
552 0 : pPlane->ny*dir.getY() );
553 0 : double numerator = ( pPlane->nx*curr->getX() +
554 0 : pPlane->ny*curr->getY() +
555 0 : pPlane->d );
556 0 : double t = -numerator/denominator;
557 :
558 : // calculate the actual point of intersection
559 0 : ::basegfx::B2DPoint intersection( curr->getX()+t*dir.getX(),
560 0 : curr->getY()+t*dir.getY() );
561 :
562 0 : out_vertex[out_count++] = intersection;
563 : }
564 0 : else if((clip&0x0f)==0 && (clip&0xf0)) { // curr is outside, next is inside
565 :
566 : // direction vector from 'current' to 'next', *not* normalized
567 : // to bring 't' into the [0<=x<=1] intervall.
568 0 : ::basegfx::B2DPoint dir((*next)-(*curr));
569 :
570 0 : double denominator = ( pPlane->nx*dir.getX() +
571 0 : pPlane->ny*dir.getY() );
572 0 : double numerator = ( pPlane->nx*curr->getX() +
573 0 : pPlane->ny*curr->getY() +
574 0 : pPlane->d );
575 0 : double t = -numerator/denominator;
576 :
577 : // calculate the actual point of intersection
578 0 : ::basegfx::B2DPoint intersection( curr->getX()+t*dir.getX(),
579 0 : curr->getY()+t*dir.getY() );
580 :
581 0 : out_vertex[out_count++] = intersection;
582 0 : out_vertex[out_count++] = *next;
583 : }
584 : }
585 :
586 0 : return out_count;
587 : }
588 :
589 0 : B2DPolygon clipTriangleListOnRange( const B2DPolygon& rCandidate,
590 : const B2DRange& rRange )
591 : {
592 0 : B2DPolygon aResult;
593 :
594 0 : if( !(rCandidate.count()%3) )
595 : {
596 0 : const int scissor_plane_count = 4;
597 :
598 : scissor_plane sp[scissor_plane_count];
599 :
600 0 : sp[0].nx = +1.0;
601 0 : sp[0].ny = +0.0;
602 0 : sp[0].d = -(rRange.getMinX());
603 0 : sp[0].clipmask = (RectClipFlags::LEFT << 4) | RectClipFlags::LEFT; // 0001 0001
604 0 : sp[1].nx = -1.0;
605 0 : sp[1].ny = +0.0;
606 0 : sp[1].d = +(rRange.getMaxX());
607 0 : sp[1].clipmask = (RectClipFlags::RIGHT << 4) | RectClipFlags::RIGHT; // 0010 0010
608 0 : sp[2].nx = +0.0;
609 0 : sp[2].ny = +1.0;
610 0 : sp[2].d = -(rRange.getMinY());
611 0 : sp[2].clipmask = (RectClipFlags::TOP << 4) | RectClipFlags::TOP; // 0100 0100
612 0 : sp[3].nx = +0.0;
613 0 : sp[3].ny = -1.0;
614 0 : sp[3].d = +(rRange.getMaxY());
615 0 : sp[3].clipmask = (RectClipFlags::BOTTOM << 4) | RectClipFlags::BOTTOM; // 1000 1000
616 :
617 : // retrieve the number of vertices of the triangulated polygon
618 0 : const sal_uInt32 nVertexCount = rCandidate.count();
619 :
620 0 : if(nVertexCount)
621 : {
622 : ////////////////////////////////////////////////////////////////////////
623 : ////////////////////////////////////////////////////////////////////////
624 : ////////////////////////////////////////////////////////////////////////
625 : //
626 : // Upper bound for the maximal number of vertices when intersecting an
627 : // axis-aligned rectangle with a triangle in E2
628 : //
629 : // The rectangle and the triangle are in general position, and have 4 and 3
630 : // vertices, respectively.
631 : //
632 : // Lemma: Since the rectangle is a convex polygon ( see
633 : // http://mathworld.wolfram.com/ConvexPolygon.html for a definition), and
634 : // has no holes, it follows that any straight line will intersect the
635 : // rectangle's border line at utmost two times (with the usual
636 : // tie-breaking rule, if the intersection exactly hits an already existing
637 : // rectangle vertex, that this intersection is only attributed to one of
638 : // the adjoining edges). Thus, having a rectangle intersected with
639 : // a half-plane (one side of a straight line denotes 'inside', the
640 : // other 'outside') will at utmost add _one_ vertex to the resulting
641 : // intersection polygon (adding two intersection vertices, and removing at
642 : // least one rectangle vertex):
643 : //
644 : // *
645 : // +--+-----------------+
646 : // | * |
647 : // |* |
648 : // + |
649 : // *| |
650 : // * | |
651 : // +--------------------+
652 : //
653 : // Proof: If the straight line intersects the rectangle two
654 : // times, it does so for distinct edges, i.e. the intersection has
655 : // minimally one of the rectangle's vertices on either side of the straight
656 : // line (but maybe more). Thus, the intersection with a half-plane has
657 : // minimally _one_ rectangle vertex removed from the resulting clip
658 : // polygon, and therefore, a clip against a half-plane has the net effect
659 : // of adding at utmost _one_ vertex to the resulting clip polygon.
660 : //
661 : // Theorem: The intersection of a rectangle and a triangle results in a
662 : // polygon with at utmost 7 vertices.
663 : //
664 : // Proof: The inside of the triangle can be described as the consecutive
665 : // intersection with three half-planes. Together with the lemma above, this
666 : // results in at utmost 3 additional vertices added to the already existing 4
667 : // rectangle vertices.
668 : //
669 : // This upper bound is attained with the following example configuration:
670 : //
671 : // *
672 : // ***
673 : // ** *
674 : // ** *
675 : // ** *
676 : // ** *
677 : // ** *
678 : // ** *
679 : // ** *
680 : // ** *
681 : // ** *
682 : // ----*2--------3 *
683 : // | ** |*
684 : // 1* 4
685 : // **| *|
686 : // ** | * |
687 : // **| * |
688 : // 7* * |
689 : // --*6-----5-----
690 : // ** *
691 : // **
692 : //
693 : // As we need to scissor all triangles against the
694 : // output rectangle we employ an output buffer for the
695 : // resulting vertices. the question is how large this
696 : // buffer needs to be compared to the number of
697 : // incoming vertices. this buffer needs to hold at
698 : // most the number of original vertices times '7'. see
699 : // figure above for an example. scissoring triangles
700 : // with the cohen-sutherland line clipping algorithm
701 : // as implemented here will result in a triangle fan
702 : // which will be rendered as separate triangles to
703 : // avoid pipeline stalls for each scissored
704 : // triangle. creating separate triangles from a
705 : // triangle fan produces (n-2)*3 vertices where n is
706 : // the number of vertices of the original triangle
707 : // fan. for the maximum number of 7 vertices of
708 : // resulting triangle fans we therefore need 15 times
709 : // the number of original vertices.
710 : //
711 : ////////////////////////////////////////////////////////////////////////
712 : ////////////////////////////////////////////////////////////////////////
713 : ////////////////////////////////////////////////////////////////////////
714 :
715 : //const size_t nBufferSize = sizeof(vertex)*(nVertexCount*16);
716 : //vertex *pVertices = (vertex*)alloca(nBufferSize);
717 : //sal_uInt32 nNumOutput = 0;
718 :
719 : // we need to clip this triangle against the output rectangle
720 : // to ensure that the resulting texture coordinates are in
721 : // the valid range from [0<=st<=1]. under normal circustances
722 : // we could use the BORDERCOLOR renderstate but some cards
723 : // seem to ignore this feature.
724 0 : ::basegfx::B2DPoint stack[3];
725 0 : unsigned int clipflag = 0;
726 :
727 0 : for(sal_uInt32 nIndex=0; nIndex<nVertexCount; ++nIndex)
728 : {
729 : // rotate stack
730 0 : stack[0] = stack[1];
731 0 : stack[1] = stack[2];
732 0 : stack[2] = rCandidate.getB2DPoint(nIndex);
733 :
734 : // clipping judgement
735 0 : clipflag |= !(rRange.isInside(stack[2]));
736 :
737 0 : if(nIndex > 1)
738 : {
739 : // consume vertices until a single seperate triangle has been visited.
740 0 : if(!((nIndex+1)%3))
741 : {
742 : // if any of the last three vertices was outside
743 : // we need to scissor against the destination rectangle
744 0 : if(clipflag & 7)
745 : {
746 0 : ::basegfx::B2DPoint buf0[16];
747 0 : ::basegfx::B2DPoint buf1[16];
748 :
749 0 : sal_uInt32 vertex_count = 3;
750 :
751 : // clip against all 4 planes passing the result of
752 : // each plane as the input to the next using a double buffer
753 0 : vertex_count = scissorLineSegment(stack,vertex_count,buf1,&sp[0],rRange);
754 0 : vertex_count = scissorLineSegment(buf1,vertex_count,buf0,&sp[1],rRange);
755 0 : vertex_count = scissorLineSegment(buf0,vertex_count,buf1,&sp[2],rRange);
756 0 : vertex_count = scissorLineSegment(buf1,vertex_count,buf0,&sp[3],rRange);
757 :
758 0 : if(vertex_count >= 3)
759 : {
760 : // convert triangle fan back to triangle list.
761 0 : ::basegfx::B2DPoint v0(buf0[0]);
762 0 : ::basegfx::B2DPoint v1(buf0[1]);
763 0 : for(sal_uInt32 i=2; i<vertex_count; ++i)
764 : {
765 0 : ::basegfx::B2DPoint v2(buf0[i]);
766 0 : aResult.append(v0);
767 0 : aResult.append(v1);
768 0 : aResult.append(v2);
769 0 : v1 = v2;
770 0 : }
771 0 : }
772 : }
773 : else
774 : {
775 : // the last triangle has not been altered, simply copy to result
776 0 : for(sal_uInt32 i=0; i<3; ++i)
777 0 : aResult.append(stack[i]);
778 : }
779 : }
780 : }
781 :
782 0 : clipflag <<= 1;
783 0 : }
784 : }
785 : }
786 :
787 0 : return aResult;
788 : }
789 :
790 : //////////////////////////////////////////////////////////////////////////////
791 :
792 : } // end of namespace tools
793 : } // end of namespace basegfx
794 :
795 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
