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 1847285 : 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 1847285 : int ca(0), cb(0);
63 1847285 : if( clipCode1 )
64 : {
65 1677 : if( clipCode1 & aMinFlag )
66 : {
67 1377 : ca = 2*db*(aMin - a1);
68 1377 : o_as = aMin;
69 : }
70 300 : else if( clipCode1 & aMaxFlag )
71 : {
72 145 : ca = 2*db*(a1 - aMax);
73 145 : o_as = aMax;
74 : }
75 :
76 1677 : if( clipCode1 & bMinFlag )
77 : {
78 24 : cb = 2*da*(bMin - b1);
79 24 : o_bs = bMin;
80 : }
81 1653 : else if( clipCode1 & bMaxFlag )
82 : {
83 133 : cb = 2*da*(b1 - bMax);
84 133 : o_bs = bMax;
85 : }
86 :
87 1677 : if( clipCount1 == 2 )
88 2 : clipCode1 &= (ca + da < cb + int(!bRoundTowardsPt2)) ? ~(aMinFlag|aMaxFlag) : ~(bMinFlag|bMaxFlag);
89 :
90 1677 : if( clipCode1 & (aMinFlag|aMaxFlag) )
91 : {
92 1520 : cb = (ca + da - int(!bRoundTowardsPt2)) / (2*da);
93 :
94 1520 : if( sb >= 0 )
95 : {
96 1514 : o_bs = b1 + cb;
97 1514 : if( o_bs > bMax )
98 4 : return false; // fully clipped
99 : }
100 : else
101 : {
102 6 : o_bs = b1 - cb;
103 6 : if( o_bs < bMin )
104 4 : return false; // fully clipped
105 : }
106 :
107 1512 : io_rem += ca - 2*da*cb;
108 : }
109 : else
110 : {
111 157 : ca = (cb - da + 2*db - int(bRoundTowardsPt2)) / (2*db);
112 157 : if( sa >= 0 )
113 : {
114 137 : o_as = a1 + ca;
115 137 : if( o_as > aMax )
116 134 : return false; // fully clipped
117 : }
118 : else
119 : {
120 20 : o_as = a1 - ca;
121 20 : if( o_as < aMin )
122 2 : return false; // fully clipped
123 : }
124 :
125 21 : io_rem += 2*db*ca - cb;
126 : }
127 : }
128 : else
129 : {
130 1845608 : o_as = a1; o_bs = b1;
131 : }
132 :
133 1847141 : if( clipCode2 )
134 : {
135 137198 : if( clipCount2 == 2 )
136 : {
137 8 : ca = 2*db*((clipCode2 & aMinFlag) ? a1 - aMin : aMax - a1);
138 8 : cb = 2*da*((clipCode2 & bMinFlag) ? b1 - bMin : bMax - b1);
139 8 : clipCode2 &= (cb + da < ca + int(bRoundTowardsPt2)) ? ~(aMinFlag|aMaxFlag) : ~(bMinFlag|bMaxFlag);
140 : }
141 :
142 137198 : if( clipCode2 & (aMinFlag|aMaxFlag) )
143 134443 : o_n = (clipCode2 & aMinFlag) ? o_as - aMin : aMax - o_as;
144 : else
145 : {
146 2755 : o_n = (clipCode2 & bMinFlag) ? o_bs - bMin : bMax - o_bs;
147 2755 : o_bUseAlternateBresenham = true;
148 : }
149 : }
150 : else
151 1709943 : o_n = (a2 >= o_as) ? a2 - o_as : o_as - a2;
152 :
153 1847141 : return true; // at least one pixel to render
154 : }
155 :
156 :
157 : /** Render line to image iterators, clip against given rectangle
158 :
159 : This method renders a line from aPt1 to aPt2, clipped against
160 : rClipRect (the clipping will take place pixel-perfect, i.e. as if
161 : the original bresenham-rendered line would have been clipped each
162 : pixel individually. No slight shifts compared to unclipped lines).
163 :
164 : @param aPt1
165 : Start point of the line
166 :
167 : @param aPt2
168 : End point of the line
169 :
170 : @param rClipRect
171 : Rectangle to clip against
172 :
173 : @param color
174 : Color value to render the line with
175 :
176 : @param begin
177 : left-top image iterator
178 :
179 : @param end
180 : right-bottom image iterator
181 :
182 : @param acc
183 : Image accessor
184 :
185 : @param bRoundTowardsPt2
186 : Rounding mode to use. Giving false here results in line pixel tend
187 : towards pt1, i.e. when a pixel exactly hits the middle between two
188 : pixel, the pixel closer to pt1 will be chosen. Giving true here
189 : makes renderClippedLine() choose pt2 in those cases.
190 : */
191 : template< class Iterator, class Accessor >
192 2128760 : void renderClippedLine( basegfx::B2IPoint aPt1,
193 : basegfx::B2IPoint aPt2,
194 : const basegfx::B2IBox& rClipRect,
195 : typename Accessor::value_type color,
196 : Iterator begin,
197 : Accessor acc,
198 : bool bRoundTowardsPt2=false )
199 : {
200 : // Algorithm according to Steven Eker's 'Pixel-perfect line clipping',
201 : // Graphics Gems V, pp. 314-322
202 : sal_uInt32 clipCode1 = basegfx::tools::getCohenSutherlandClipFlags(aPt1,
203 2128760 : rClipRect);
204 : sal_uInt32 clipCode2 = basegfx::tools::getCohenSutherlandClipFlags(aPt2,
205 2128760 : rClipRect);
206 :
207 2128760 : if( clipCode1 & clipCode2 )
208 563094 : return; // line fully clipped away, both endpoints share a half-plane
209 :
210 1847285 : sal_uInt32 clipCount1 = basegfx::tools::getNumberOfClipPlanes(clipCode1);
211 1847285 : sal_uInt32 clipCount2 = basegfx::tools::getNumberOfClipPlanes(clipCode2);
212 :
213 1847285 : if( (clipCode1 != 0 && clipCode2 == 0)
214 : || (clipCount1 == 2 && clipCount2 == 1) )
215 : {
216 17445 : std::swap(clipCount2,clipCount1);
217 17445 : std::swap(clipCode2,clipCode1);
218 17445 : std::swap(aPt1,aPt2);
219 17445 : bRoundTowardsPt2 = !bRoundTowardsPt2;
220 : }
221 :
222 1847285 : const sal_Int32 x1 = aPt1.getX();
223 1847285 : const sal_Int32 x2 = aPt2.getX();
224 1847285 : const sal_Int32 y1 = aPt1.getY();
225 1847285 : const sal_Int32 y2 = aPt2.getY();
226 :
227 : // TODO(E1): This might overflow
228 1847285 : sal_Int32 adx = x2 - x1;
229 1847285 : int sx = 1;
230 1847285 : if( adx < 0 )
231 : {
232 202438 : adx *= -1;
233 202438 : sx = -1;
234 : }
235 :
236 : // TODO(E1): This might overflow
237 1847285 : sal_Int32 ady = y2 - y1;
238 1847285 : int sy = 1;
239 1847285 : if( ady < 0 )
240 : {
241 217487 : ady *= -1;
242 217487 : sy = -1;
243 : }
244 :
245 1847285 : int n = 0;
246 1847285 : sal_Int32 xs = x1;
247 1847285 : sal_Int32 ys = y1;
248 1847285 : bool bUseAlternateBresenham=false;
249 1847285 : if( adx >= ady )
250 : {
251 : // semi-horizontal line
252 1138668 : sal_Int32 rem = 2*ady - adx - int(!bRoundTowardsPt2);
253 :
254 1138668 : if( !prepareClip(x1, x2, y1, adx, ady, xs, ys, sx, sy,
255 : rem, n, clipCode1, clipCount1, clipCode2, clipCount2,
256 : rClipRect.getMinX(), basegfx::tools::RectClipFlags::LEFT,
257 1138668 : rClipRect.getMaxX()-1, basegfx::tools::RectClipFlags::RIGHT,
258 : rClipRect.getMinY(), basegfx::tools::RectClipFlags::TOP,
259 1138668 : rClipRect.getMaxY()-1, basegfx::tools::RectClipFlags::BOTTOM,
260 3416004 : bRoundTowardsPt2, bUseAlternateBresenham ) )
261 142 : return; // line fully clipped away, no active pixel inside rect
262 :
263 1138526 : Iterator currIter( begin + vigra::Diff2D(0,ys) );
264 : typename vigra::IteratorTraits<Iterator>::row_iterator
265 1138526 : rowIter( currIter.rowIterator() + xs );
266 :
267 1138526 : adx *= 2;
268 1138526 : ady *= 2;
269 :
270 39910671 : if( bUseAlternateBresenham )
271 : {
272 : while(true)
273 : {
274 2847 : acc.set(color, rowIter);
275 :
276 2847 : if( rem >= 0 )
277 : {
278 : // this is intended - we clip endpoint against y
279 : // plane, so n here denotes y range to render
280 2792 : if( --n < 0 )
281 2621 : break;
282 :
283 171 : ys += sy;
284 171 : xs += sx;
285 171 : rem -= adx;
286 :
287 171 : currIter.y += sy;
288 171 : rowIter = currIter.rowIterator() + xs;
289 : }
290 : else
291 : {
292 55 : xs += sx;
293 55 : rowIter += sx;
294 : }
295 :
296 226 : rem += ady;
297 : }
298 : }
299 : else
300 : {
301 : while(true)
302 : {
303 39907824 : acc.set(color, rowIter);
304 :
305 39907824 : if( --n < 0 )
306 1135905 : break;
307 :
308 38771919 : if( rem >= 0 )
309 : {
310 219069 : ys += sy;
311 219069 : xs += sx;
312 219069 : rem -= adx;
313 :
314 219069 : currIter.y += sy;
315 219069 : rowIter = currIter.rowIterator() + xs;
316 : }
317 : else
318 : {
319 38552850 : xs += sx;
320 38552850 : rowIter += sx;
321 : }
322 :
323 38771919 : rem += ady;
324 : }
325 : }
326 : }
327 : else
328 : {
329 : // semi-vertical line
330 708617 : sal_Int32 rem = 2*adx - ady - int(!bRoundTowardsPt2);
331 :
332 708617 : if( !prepareClip(y1, y2, x1, ady, adx, ys, xs, sy, sx,
333 : rem, n, clipCode1, clipCount1, clipCode2, clipCount2,
334 : rClipRect.getMinY(), basegfx::tools::RectClipFlags::TOP,
335 708617 : rClipRect.getMaxY()-1, basegfx::tools::RectClipFlags::BOTTOM,
336 : rClipRect.getMinX(), basegfx::tools::RectClipFlags::LEFT,
337 708617 : rClipRect.getMaxX()-1, basegfx::tools::RectClipFlags::RIGHT,
338 2125851 : bRoundTowardsPt2, bUseAlternateBresenham ) )
339 2 : return; // line fully clipped away, no active pixel inside rect
340 :
341 708615 : Iterator currIter( begin + vigra::Diff2D(xs,0) );
342 : typename vigra::IteratorTraits<Iterator>::column_iterator
343 708615 : colIter( currIter.columnIterator() + ys );
344 :
345 708615 : adx *= 2;
346 708615 : ady *= 2;
347 :
348 14167472 : if( bUseAlternateBresenham )
349 : {
350 : while(true)
351 : {
352 906 : acc.set(color, colIter);
353 :
354 906 : if( rem >= 0 )
355 : {
356 : // this is intended - we clip endpoint against x
357 : // plane, so n here denotes x range to render
358 556 : if( --n < 0 )
359 134 : break;
360 :
361 422 : xs += sx;
362 422 : ys += sy;
363 422 : rem -= ady;
364 :
365 422 : currIter.x += sx;
366 422 : colIter = currIter.columnIterator() + ys;
367 : }
368 : else
369 : {
370 350 : ys += sy;
371 350 : colIter += sy;
372 : }
373 :
374 772 : rem += adx;
375 : }
376 : }
377 : else
378 : {
379 : while(true)
380 : {
381 14166566 : acc.set(color, colIter);
382 :
383 14166566 : if( --n < 0 )
384 708481 : break;
385 :
386 13458085 : if( rem >= 0 )
387 : {
388 258570 : xs += sx;
389 258570 : ys += sy;
390 258570 : rem -= ady;
391 :
392 258570 : currIter.x += sx;
393 258570 : colIter = currIter.columnIterator() + ys;
394 : }
395 : else
396 : {
397 13199515 : ys += sy;
398 13199515 : colIter += sy;
399 : }
400 :
401 13458085 : rem += adx;
402 : }
403 : }
404 : }
405 : }
406 :
407 : } // namespace basebmp
408 :
409 : #endif /* INCLUDED_BASEBMP_CLIPPEDLINERENDERER_HXX */
410 :
411 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|