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 4325285 : 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 4325285 : int ca(0), cb(0);
63 4325285 : if( clipCode1 )
64 : {
65 2257 : if( clipCode1 & aMinFlag )
66 : {
67 2066 : ca = 2*db*(aMin - a1);
68 2066 : o_as = aMin;
69 : }
70 191 : else if( clipCode1 & aMaxFlag )
71 : {
72 161 : ca = 2*db*(a1 - aMax);
73 161 : o_as = aMax;
74 : }
75 :
76 2257 : if( clipCode1 & bMinFlag )
77 : {
78 34 : cb = 2*da*(bMin - b1);
79 34 : o_bs = bMin;
80 : }
81 2223 : else if( clipCode1 & bMaxFlag )
82 : {
83 0 : cb = 2*da*(b1 - bMax);
84 0 : o_bs = bMax;
85 : }
86 :
87 2257 : if( clipCount1 == 2 )
88 4 : clipCode1 &= (ca + da < cb + int(!bRoundTowardsPt2)) ? ~(aMinFlag|aMaxFlag) : ~(bMinFlag|bMaxFlag);
89 :
90 2257 : if( clipCode1 & (aMinFlag|aMaxFlag) )
91 : {
92 2223 : sal_Int32 da2 = 2*da;
93 :
94 2223 : if (da2 == 0)
95 0 : return false; // overflow
96 :
97 2223 : cb = (ca + da - int(!bRoundTowardsPt2)) / (da2);
98 :
99 2223 : if( sb >= 0 )
100 : {
101 2206 : o_bs = b1 + cb;
102 2206 : if( o_bs > bMax )
103 199 : return false; // fully clipped
104 : }
105 : else
106 : {
107 17 : o_bs = b1 - cb;
108 17 : if( o_bs < bMin )
109 4 : return false; // fully clipped
110 : }
111 :
112 2020 : io_rem += ca - da2*cb;
113 : }
114 : else
115 : {
116 34 : sal_Int32 db2 = 2*db;
117 :
118 34 : if (db2 == 0)
119 0 : return false; // overflow
120 :
121 34 : ca = (cb - da + db2 - int(bRoundTowardsPt2)) / (db2);
122 34 : if( sa >= 0 )
123 : {
124 8 : o_as = a1 + ca;
125 8 : if( o_as > aMax )
126 4 : 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 10 : io_rem += db2*ca - cb;
136 : }
137 : }
138 : else
139 : {
140 4323028 : o_as = a1; o_bs = b1;
141 : }
142 :
143 4325058 : if( clipCode2 )
144 : {
145 100542 : if( clipCount2 == 2 )
146 : {
147 22 : ca = 2*db*((clipCode2 & aMinFlag) ? a1 - aMin : aMax - a1);
148 22 : cb = 2*da*((clipCode2 & bMinFlag) ? b1 - bMin : bMax - b1);
149 22 : clipCode2 &= (cb + da < ca + int(bRoundTowardsPt2)) ? ~(aMinFlag|aMaxFlag) : ~(bMinFlag|bMaxFlag);
150 : }
151 :
152 100542 : if( clipCode2 & (aMinFlag|aMaxFlag) )
153 98474 : o_n = (clipCode2 & aMinFlag) ? o_as - aMin : aMax - o_as;
154 : else
155 : {
156 2068 : o_n = (clipCode2 & bMinFlag) ? o_bs - bMin : bMax - o_bs;
157 2068 : o_bUseAlternateBresenham = true;
158 : }
159 : }
160 : else
161 4224516 : o_n = (a2 >= o_as) ? a2 - o_as : o_as - a2;
162 :
163 4325058 : 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 4596510 : 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 4596510 : rClipRect);
214 : sal_uInt32 clipCode2 = basegfx::tools::getCohenSutherlandClipFlags(aPt2,
215 4596510 : rClipRect);
216 :
217 4596510 : if( clipCode1 & clipCode2 )
218 542677 : return; // line fully clipped away, both endpoints share a half-plane
219 :
220 4325285 : sal_uInt32 clipCount1 = basegfx::tools::getNumberOfClipPlanes(clipCode1);
221 4325285 : sal_uInt32 clipCount2 = basegfx::tools::getNumberOfClipPlanes(clipCode2);
222 :
223 4325285 : if( (clipCode1 != 0 && clipCode2 == 0)
224 : || (clipCount1 == 2 && clipCount2 == 1) )
225 : {
226 38229 : std::swap(clipCount2,clipCount1);
227 38229 : std::swap(clipCode2,clipCode1);
228 38229 : std::swap(aPt1,aPt2);
229 38229 : bRoundTowardsPt2 = !bRoundTowardsPt2;
230 : }
231 :
232 4325285 : const sal_Int32 x1 = aPt1.getX();
233 4325285 : const sal_Int32 x2 = aPt2.getX();
234 4325285 : const sal_Int32 y1 = aPt1.getY();
235 4325285 : const sal_Int32 y2 = aPt2.getY();
236 :
237 : // TODO(E1): This might overflow
238 4325285 : sal_Int32 adx = x2 - x1;
239 4325285 : int sx = 1;
240 4325285 : if( adx < 0 )
241 : {
242 249681 : adx *= -1;
243 249681 : sx = -1;
244 : }
245 :
246 : // TODO(E1): This might overflow
247 4325285 : sal_Int32 ady = y2 - y1;
248 4325285 : int sy = 1;
249 4325285 : if( ady < 0 )
250 : {
251 268580 : ady *= -1;
252 268580 : sy = -1;
253 : }
254 :
255 4325285 : int n = 0;
256 4325285 : sal_Int32 xs = x1;
257 4325285 : sal_Int32 ys = y1;
258 4325285 : bool bUseAlternateBresenham=false;
259 :
260 4325285 : sal_Int32 nMinY(rClipRect.getMinY());
261 4325285 : sal_Int32 nMaxY(rClipRect.getMaxY()-1);
262 4325285 : sal_Int32 nMinX(rClipRect.getMinX());
263 4325285 : sal_Int32 nMaxX(rClipRect.getMaxX()-1);
264 :
265 4325285 : if( adx >= ady )
266 : {
267 : // semi-horizontal line
268 2512213 : sal_Int32 rem = 2*ady - adx - int(!bRoundTowardsPt2);
269 :
270 2512213 : 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 2512213 : bRoundTowardsPt2, bUseAlternateBresenham ) )
277 32 : return; // line fully clipped away, no active pixel inside rect
278 :
279 2512197 : Iterator currIter( begin + vigra::Diff2D(0,ys) );
280 : typename vigra::IteratorTraits<Iterator>::row_iterator
281 2512197 : rowIter( currIter.rowIterator() + xs );
282 :
283 2512197 : adx *= 2;
284 2512197 : ady *= 2;
285 :
286 115252583 : if( bUseAlternateBresenham )
287 : {
288 2024 : if (rem < 0 && ady <= 0)
289 0 : return; //break will never be hit under these circumstances
290 :
291 : while(true)
292 : {
293 2712 : if (xs >= nMinX && xs <= nMaxX && ys >= nMinY && ys <= nMaxY)
294 2712 : acc.set(color, rowIter);
295 :
296 2712 : if( rem >= 0 )
297 : {
298 : // this is intended - we clip endpoint against y
299 : // plane, so n here denotes y range to render
300 2568 : if( --n < 0 )
301 2024 : break;
302 :
303 544 : ys += sy;
304 544 : xs += sx;
305 544 : rem -= adx;
306 :
307 544 : currIter.y += sy;
308 544 : rowIter = currIter.rowIterator() + xs;
309 : }
310 : else
311 : {
312 144 : xs += sx;
313 144 : rowIter += sx;
314 : }
315 :
316 688 : rem += ady;
317 : }
318 : }
319 : else
320 : {
321 : while(true)
322 : {
323 115249871 : if (xs >= nMinX && xs <= nMaxX && ys >= nMinY && ys <= nMaxY)
324 115249871 : acc.set(color, rowIter);
325 :
326 115249871 : if( --n < 0 )
327 2510173 : break;
328 :
329 112739698 : if( rem >= 0 )
330 : {
331 196918 : ys += sy;
332 196918 : xs += sx;
333 196918 : rem -= adx;
334 :
335 196918 : currIter.y += sy;
336 196918 : rowIter = currIter.rowIterator() + xs;
337 : }
338 : else
339 : {
340 112542780 : xs += sx;
341 112542780 : rowIter += sx;
342 : }
343 :
344 112739698 : rem += ady;
345 : }
346 : }
347 : }
348 : else
349 : {
350 : // semi-vertical line
351 1813072 : sal_Int32 rem = 2*adx - ady - int(!bRoundTowardsPt2);
352 :
353 1813072 : 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 1813072 : bRoundTowardsPt2, bUseAlternateBresenham ) )
360 422 : return; // line fully clipped away, no active pixel inside rect
361 :
362 1812861 : Iterator currIter( begin + vigra::Diff2D(xs,0) );
363 : typename vigra::IteratorTraits<Iterator>::column_iterator
364 1812861 : colIter( currIter.columnIterator() + ys );
365 :
366 1812861 : adx *= 2;
367 1812861 : ady *= 2;
368 :
369 88008972 : if( bUseAlternateBresenham )
370 : {
371 44 : if (rem < 0 && adx <= 0)
372 0 : return; //break will never be hit under these circumstances
373 :
374 : while(true)
375 : {
376 790 : if (xs >= nMinX && xs <= nMaxX && ys >= nMinY && ys <= nMaxY)
377 302 : acc.set(color, colIter);
378 :
379 790 : if( rem >= 0 )
380 : {
381 : // this is intended - we clip endpoint against x
382 : // plane, so n here denotes x range to render
383 486 : if( --n < 0 )
384 44 : break;
385 :
386 442 : xs += sx;
387 442 : ys += sy;
388 :
389 442 : rem -= ady;
390 :
391 442 : currIter.x += sx;
392 442 : colIter = currIter.columnIterator() + ys;
393 : }
394 : else
395 : {
396 304 : ys += sy;
397 304 : colIter += sy;
398 : }
399 :
400 746 : rem += adx;
401 : }
402 : }
403 : else
404 : {
405 : while(true)
406 : {
407 88008182 : if (xs >= nMinX && xs <= nMaxX && ys >= nMinY && ys <= nMaxY)
408 88008178 : acc.set(color, colIter);
409 :
410 88008182 : if( --n < 0 )
411 1812817 : break;
412 :
413 86195365 : if( rem >= 0 )
414 : {
415 222451 : xs += sx;
416 222451 : ys += sy;
417 222451 : rem -= ady;
418 :
419 222451 : currIter.x += sx;
420 222451 : colIter = currIter.columnIterator() + ys;
421 : }
422 : else
423 : {
424 85972914 : ys += sy;
425 85972914 : colIter += sy;
426 : }
427 :
428 86195365 : rem += adx;
429 : }
430 : }
431 : }
432 : }
433 :
434 : } // namespace basebmp
435 :
436 : #endif /* INCLUDED_BASEBMP_CLIPPEDLINERENDERER_HXX */
437 :
438 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
