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 : #ifndef INCLUDED_BASEBMP_CLIPPEDLINERENDERER_HXX
21 : #define INCLUDED_BASEBMP_CLIPPEDLINERENDERER_HXX
22 :
23 : #include <basegfx/tools/rectcliptools.hxx>
24 : #include <basegfx/point/b2ipoint.hxx>
25 : #include <basegfx/range/b2ibox.hxx>
26 :
27 : #include <vigra/diff2d.hxx>
28 : #include <vigra/iteratortraits.hxx>
29 :
30 : namespace basebmp
31 : {
32 :
33 : // factored-out bresenham setup code, which is used from two different
34 : // places in renderClippedLine() below. Admittedly messy for the long
35 : // parameter list...
36 4642123 : inline bool prepareClip( sal_Int32 a1,
37 : sal_Int32 a2,
38 : sal_Int32 b1,
39 : sal_Int32 da,
40 : sal_Int32 db,
41 : sal_Int32& o_as,
42 : sal_Int32& o_bs,
43 : int sa,
44 : int sb,
45 : sal_Int32& io_rem,
46 : int& o_n,
47 : sal_uInt32 clipCode1,
48 : sal_uInt32 clipCount1,
49 : sal_uInt32 clipCode2,
50 : sal_uInt32 clipCount2,
51 : sal_Int32 aMin,
52 : sal_uInt32 aMinFlag,
53 : sal_Int32 aMax,
54 : sal_uInt32 aMaxFlag,
55 : sal_Int32 bMin,
56 : sal_uInt32 bMinFlag,
57 : sal_Int32 bMax,
58 : sal_uInt32 bMaxFlag,
59 : bool bRoundTowardsPt2,
60 : bool& o_bUseAlternateBresenham )
61 : {
62 4642123 : int ca(0), cb(0);
63 4642123 : if( clipCode1 )
64 : {
65 1434 : if( clipCode1 & aMinFlag )
66 : {
67 1247 : ca = 2*db*(aMin - a1);
68 1247 : o_as = aMin;
69 : }
70 187 : else if( clipCode1 & aMaxFlag )
71 : {
72 159 : ca = 2*db*(a1 - aMax);
73 159 : o_as = aMax;
74 : }
75 :
76 1434 : if( clipCode1 & bMinFlag )
77 : {
78 30 : cb = 2*da*(bMin - b1);
79 30 : o_bs = bMin;
80 : }
81 1404 : else if( clipCode1 & bMaxFlag )
82 : {
83 0 : cb = 2*da*(b1 - bMax);
84 0 : o_bs = bMax;
85 : }
86 :
87 1434 : if( clipCount1 == 2 )
88 2 : clipCode1 &= (ca + da < cb + int(!bRoundTowardsPt2)) ? ~(aMinFlag|aMaxFlag) : ~(bMinFlag|bMaxFlag);
89 :
90 1434 : if( clipCode1 & (aMinFlag|aMaxFlag) )
91 : {
92 1404 : sal_Int32 da2 = 2*da;
93 :
94 1404 : if (da2 == 0)
95 0 : return false; // overflow
96 :
97 1404 : cb = (ca + da - int(!bRoundTowardsPt2)) / (da2);
98 :
99 1404 : if( sb >= 0 )
100 : {
101 1355 : o_bs = b1 + cb;
102 1355 : if( o_bs > bMax )
103 107 : return false; // fully clipped
104 : }
105 : else
106 : {
107 49 : o_bs = b1 - cb;
108 49 : if( o_bs < bMin )
109 4 : return false; // fully clipped
110 : }
111 :
112 1293 : io_rem += ca - da2*cb;
113 : }
114 : else
115 : {
116 30 : sal_Int32 db2 = 2*db;
117 :
118 30 : if (db2 == 0)
119 0 : return false; // overflow
120 :
121 30 : ca = (cb - da + db2 - int(bRoundTowardsPt2)) / (db2);
122 30 : if( sa >= 0 )
123 : {
124 4 : o_as = a1 + ca;
125 4 : if( o_as > aMax )
126 2 : return false; // fully clipped
127 : }
128 : else
129 : {
130 26 : o_as = a1 - ca;
131 26 : if( o_as < aMin )
132 20 : return false; // fully clipped
133 : }
134 :
135 8 : io_rem += db2*ca - cb;
136 : }
137 : }
138 : else
139 : {
140 4640689 : o_as = a1; o_bs = b1;
141 : }
142 :
143 4641990 : if( clipCode2 )
144 : {
145 101819 : if( clipCount2 == 2 )
146 : {
147 16 : ca = 2*db*((clipCode2 & aMinFlag) ? a1 - aMin : aMax - a1);
148 16 : cb = 2*da*((clipCode2 & bMinFlag) ? b1 - bMin : bMax - b1);
149 16 : clipCode2 &= (cb + da < ca + int(bRoundTowardsPt2)) ? ~(aMinFlag|aMaxFlag) : ~(bMinFlag|bMaxFlag);
150 : }
151 :
152 101819 : if( clipCode2 & (aMinFlag|aMaxFlag) )
153 99965 : o_n = (clipCode2 & aMinFlag) ? o_as - aMin : aMax - o_as;
154 : else
155 : {
156 1854 : o_n = (clipCode2 & bMinFlag) ? o_bs - bMin : bMax - o_bs;
157 1854 : o_bUseAlternateBresenham = true;
158 : }
159 : }
160 : else
161 4540171 : o_n = (a2 >= o_as) ? a2 - o_as : o_as - a2;
162 :
163 4641990 : return true; // at least one pixel to render
164 : }
165 :
166 :
167 : /** Render line to image iterators, clip against given rectangle
168 :
169 : This method renders a line from aPt1 to aPt2, clipped against
170 : rClipRect (the clipping will take place pixel-perfect, i.e. as if
171 : the original bresenham-rendered line would have been clipped each
172 : pixel individually. No slight shifts compared to unclipped lines).
173 :
174 : @param aPt1
175 : Start point of the line
176 :
177 : @param aPt2
178 : End point of the line
179 :
180 : @param rClipRect
181 : Rectangle to clip against
182 :
183 : @param color
184 : Color value to render the line with
185 :
186 : @param begin
187 : left-top image iterator
188 :
189 : @param end
190 : right-bottom image iterator
191 :
192 : @param acc
193 : Image accessor
194 :
195 : @param bRoundTowardsPt2
196 : Rounding mode to use. Giving false here results in line pixel tend
197 : towards pt1, i.e. when a pixel exactly hits the middle between two
198 : pixel, the pixel closer to pt1 will be chosen. Giving true here
199 : makes renderClippedLine() choose pt2 in those cases.
200 : */
201 : template< class Iterator, class Accessor >
202 4988816 : void renderClippedLine( basegfx::B2IPoint aPt1,
203 : basegfx::B2IPoint aPt2,
204 : const basegfx::B2IBox& rClipRect,
205 : typename Accessor::value_type color,
206 : Iterator begin,
207 : Accessor acc,
208 : bool bRoundTowardsPt2=false )
209 : {
210 : // Algorithm according to Steven Eker's 'Pixel-perfect line clipping',
211 : // Graphics Gems V, pp. 314-322
212 : sal_uInt32 clipCode1 = basegfx::tools::getCohenSutherlandClipFlags(aPt1,
213 4988816 : rClipRect);
214 : sal_uInt32 clipCode2 = basegfx::tools::getCohenSutherlandClipFlags(aPt2,
215 4988816 : rClipRect);
216 :
217 4988816 : if( clipCode1 & clipCode2 )
218 693519 : return; // line fully clipped away, both endpoints share a half-plane
219 :
220 4642123 : sal_uInt32 clipCount1 = basegfx::tools::getNumberOfClipPlanes(clipCode1);
221 4642123 : sal_uInt32 clipCount2 = basegfx::tools::getNumberOfClipPlanes(clipCode2);
222 :
223 4642123 : if( (clipCode1 != 0 && clipCode2 == 0)
224 : || (clipCount1 == 2 && clipCount2 == 1) )
225 : {
226 23262 : std::swap(clipCount2,clipCount1);
227 23262 : std::swap(clipCode2,clipCode1);
228 23262 : std::swap(aPt1,aPt2);
229 23262 : bRoundTowardsPt2 = !bRoundTowardsPt2;
230 : }
231 :
232 4642123 : const sal_Int32 x1 = aPt1.getX();
233 4642123 : const sal_Int32 x2 = aPt2.getX();
234 4642123 : const sal_Int32 y1 = aPt1.getY();
235 4642123 : const sal_Int32 y2 = aPt2.getY();
236 :
237 : // TODO(E1): This might overflow
238 4642123 : sal_Int32 adx = x2 - x1;
239 4642123 : int sx = 1;
240 4642123 : if( adx < 0 )
241 : {
242 160250 : adx *= -1;
243 160250 : sx = -1;
244 : }
245 :
246 : // TODO(E1): This might overflow
247 4642123 : sal_Int32 ady = y2 - y1;
248 4642123 : int sy = 1;
249 4642123 : if( ady < 0 )
250 : {
251 875373 : ady *= -1;
252 875373 : sy = -1;
253 : }
254 :
255 4642123 : int n = 0;
256 4642123 : sal_Int32 xs = x1;
257 4642123 : sal_Int32 ys = y1;
258 4642123 : bool bUseAlternateBresenham=false;
259 :
260 4642123 : sal_Int32 nMinY(rClipRect.getMinY());
261 4642123 : sal_Int32 nMaxY(rClipRect.getMaxY()-1);
262 4642123 : sal_Int32 nMinX(rClipRect.getMinX());
263 4642123 : sal_Int32 nMaxX(rClipRect.getMaxX()-1);
264 :
265 4642123 : if( adx >= ady )
266 : {
267 : // semi-horizontal line
268 2556685 : sal_Int32 rem = 2*ady - adx - int(!bRoundTowardsPt2);
269 :
270 2556685 : if( !prepareClip(x1, x2, y1, adx, ady, xs, ys, sx, sy,
271 : rem, n, clipCode1, clipCount1, clipCode2, clipCount2,
272 : nMinX, basegfx::tools::RectClipFlags::LEFT,
273 : nMaxX, basegfx::tools::RectClipFlags::RIGHT,
274 : nMinY, basegfx::tools::RectClipFlags::TOP,
275 : nMaxY, basegfx::tools::RectClipFlags::BOTTOM,
276 2556685 : bRoundTowardsPt2, bUseAlternateBresenham ) )
277 20 : return; // line fully clipped away, no active pixel inside rect
278 :
279 2556675 : Iterator currIter( begin + vigra::Diff2D(0,ys) );
280 : typename vigra::IteratorTraits<Iterator>::row_iterator
281 2610760 : rowIter( currIter.rowIterator() + xs );
282 :
283 2556675 : adx *= 2;
284 2556675 : ady *= 2;
285 :
286 76366951 : if( bUseAlternateBresenham )
287 : {
288 1808 : if (rem < 0 && ady <= 0)
289 0 : return; //break will never be hit under these circumstances
290 :
291 : while(true)
292 : {
293 2290 : if (xs >= nMinX && xs <= nMaxX && ys >= nMinY && ys <= nMaxY)
294 2290 : acc.set(color, rowIter);
295 :
296 2290 : if( rem >= 0 )
297 : {
298 : // this is intended - we clip endpoint against y
299 : // plane, so n here denotes y range to render
300 2186 : if( --n < 0 )
301 1808 : break;
302 :
303 378 : ys += sy;
304 378 : xs += sx;
305 378 : rem -= adx;
306 :
307 378 : currIter.y += sy;
308 378 : rowIter = currIter.rowIterator() + xs;
309 : }
310 : else
311 : {
312 104 : xs += sx;
313 104 : rowIter += sx;
314 : }
315 :
316 482 : rem += ady;
317 : }
318 : }
319 : else
320 : {
321 : while(true)
322 : {
323 76364661 : if (xs >= nMinX && xs <= nMaxX && ys >= nMinY && ys <= nMaxY)
324 76364661 : acc.set(color, rowIter);
325 :
326 76364661 : if( --n < 0 )
327 2554867 : break;
328 :
329 73809794 : if( rem >= 0 )
330 : {
331 180248 : ys += sy;
332 180248 : xs += sx;
333 180248 : rem -= adx;
334 :
335 180248 : currIter.y += sy;
336 180248 : rowIter = currIter.rowIterator() + xs;
337 : }
338 : else
339 : {
340 73629546 : xs += sx;
341 73629546 : rowIter += sx;
342 : }
343 :
344 73809794 : rem += ady;
345 : }
346 54085 : }
347 : }
348 : else
349 : {
350 : // semi-vertical line
351 2085438 : sal_Int32 rem = 2*adx - ady - int(!bRoundTowardsPt2);
352 :
353 2085438 : if( !prepareClip(y1, y2, x1, ady, adx, ys, xs, sy, sx,
354 : rem, n, clipCode1, clipCount1, clipCode2, clipCount2,
355 : nMinY, basegfx::tools::RectClipFlags::TOP,
356 : nMaxY, basegfx::tools::RectClipFlags::BOTTOM,
357 : nMinX, basegfx::tools::RectClipFlags::LEFT,
358 : nMaxY, basegfx::tools::RectClipFlags::RIGHT,
359 2085438 : bRoundTowardsPt2, bUseAlternateBresenham ) )
360 246 : return; // line fully clipped away, no active pixel inside rect
361 :
362 2085315 : Iterator currIter( begin + vigra::Diff2D(xs,0) );
363 : typename vigra::IteratorTraits<Iterator>::column_iterator
364 2134368 : colIter( currIter.columnIterator() + ys );
365 :
366 2085315 : adx *= 2;
367 2085315 : ady *= 2;
368 :
369 47081919 : if( bUseAlternateBresenham )
370 : {
371 46 : if (rem < 0 && adx <= 0)
372 0 : return; //break will never be hit under these circumstances
373 :
374 : while(true)
375 : {
376 1644 : if (xs >= nMinX && xs <= nMaxX && ys >= nMinY && ys <= nMaxY)
377 500 : acc.set(color, colIter);
378 :
379 1644 : if( rem >= 0 )
380 : {
381 : // this is intended - we clip endpoint against x
382 : // plane, so n here denotes x range to render
383 1050 : if( --n < 0 )
384 46 : break;
385 :
386 1004 : xs += sx;
387 1004 : ys += sy;
388 :
389 1004 : rem -= ady;
390 :
391 1004 : currIter.x += sx;
392 1004 : colIter = currIter.columnIterator() + ys;
393 : }
394 : else
395 : {
396 594 : ys += sy;
397 594 : colIter += sy;
398 : }
399 :
400 1598 : rem += adx;
401 : }
402 : }
403 : else
404 : {
405 : while(true)
406 : {
407 47080275 : if (xs >= nMinX && xs <= nMaxX && ys >= nMinY && ys <= nMaxY)
408 47080273 : acc.set(color, colIter);
409 :
410 47080275 : if( --n < 0 )
411 2085269 : break;
412 :
413 44995006 : if( rem >= 0 )
414 : {
415 224384 : xs += sx;
416 224384 : ys += sy;
417 224384 : rem -= ady;
418 :
419 224384 : currIter.x += sx;
420 224384 : colIter = currIter.columnIterator() + ys;
421 : }
422 : else
423 : {
424 44770622 : ys += sy;
425 44770622 : colIter += sy;
426 : }
427 :
428 44995006 : rem += adx;
429 : }
430 49053 : }
431 : }
432 : }
433 :
434 : } // namespace basebmp
435 :
436 : #endif /* INCLUDED_BASEBMP_CLIPPEDLINERENDERER_HXX */
437 :
438 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
