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 219159 : 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 219159 : int ca(0), cb(0);
63 219159 : if( clipCode1 )
64 : {
65 50 : if( clipCode1 & aMinFlag )
66 : {
67 40 : ca = 2*db*(aMin - a1);
68 40 : o_as = aMin;
69 : }
70 10 : else if( clipCode1 & aMaxFlag )
71 : {
72 4 : ca = 2*db*(a1 - aMax);
73 4 : o_as = aMax;
74 : }
75 :
76 50 : if( clipCode1 & bMinFlag )
77 : {
78 8 : cb = 2*da*(bMin - b1);
79 8 : o_bs = bMin;
80 : }
81 42 : else if( clipCode1 & bMaxFlag )
82 : {
83 2 : cb = 2*da*(b1 - bMax);
84 2 : o_bs = bMax;
85 : }
86 :
87 50 : if( clipCount1 == 2 )
88 4 : clipCode1 &= (ca + da < cb + !bRoundTowardsPt2) ? ~(aMinFlag|aMaxFlag) : ~(bMinFlag|bMaxFlag);
89 :
90 50 : if( clipCode1 & (aMinFlag|aMaxFlag) )
91 : {
92 40 : cb = (ca + da - !bRoundTowardsPt2) / (2*da);
93 :
94 40 : if( sb >= 0 )
95 : {
96 32 : o_bs = b1 + cb;
97 32 : if( o_bs > bMax )
98 8 : return false; // fully clipped
99 : }
100 : else
101 : {
102 8 : o_bs = b1 - cb;
103 8 : if( o_bs < bMin )
104 4 : return false; // fully clipped
105 : }
106 :
107 28 : io_rem += ca - 2*da*cb;
108 : }
109 : else
110 : {
111 10 : ca = (cb - da + 2*db - bRoundTowardsPt2) / (2*db);
112 10 : if( sa >= 0 )
113 : {
114 10 : o_as = a1 + ca;
115 10 : if( o_as > aMax )
116 6 : return false; // fully clipped
117 : }
118 : else
119 : {
120 0 : o_as = a1 - ca;
121 0 : if( o_as < aMin )
122 0 : return false; // fully clipped
123 : }
124 :
125 4 : io_rem += 2*db*ca - cb;
126 : }
127 : }
128 : else
129 : {
130 219109 : o_as = a1; o_bs = b1;
131 : }
132 :
133 219141 : if( clipCode2 )
134 : {
135 22658 : if( clipCount2 == 2 )
136 : {
137 14 : ca = 2*db*((clipCode2 & aMinFlag) ? a1 - aMin : aMax - a1);
138 14 : cb = 2*da*((clipCode2 & bMinFlag) ? b1 - bMin : bMax - b1);
139 14 : clipCode2 &= (cb + da < ca + bRoundTowardsPt2) ? ~(aMinFlag|aMaxFlag) : ~(bMinFlag|bMaxFlag);
140 : }
141 :
142 22658 : if( clipCode2 & (aMinFlag|aMaxFlag) )
143 22644 : o_n = (clipCode2 & aMinFlag) ? o_as - aMin : aMax - o_as;
144 : else
145 : {
146 14 : o_n = (clipCode2 & bMinFlag) ? o_bs - bMin : bMax - o_bs;
147 14 : o_bUseAlternateBresenham = true;
148 : }
149 : }
150 : else
151 196483 : o_n = (a2 >= o_as) ? a2 - o_as : o_as - a2;
152 :
153 219141 : 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 260160 : 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 260160 : rClipRect);
204 : sal_uInt32 clipCode2 = basegfx::tools::getCohenSutherlandClipFlags(aPt2,
205 260160 : rClipRect);
206 :
207 260160 : if( clipCode1 & clipCode2 )
208 : return; // line fully clipped away, both endpoints share a half-plane
209 :
210 219159 : sal_uInt32 clipCount1 = basegfx::tools::getNumberOfClipPlanes(clipCode1);
211 219159 : sal_uInt32 clipCount2 = basegfx::tools::getNumberOfClipPlanes(clipCode2);
212 :
213 219159 : if( (clipCode1 != 0 && clipCode2 == 0)
214 : || (clipCount1 == 2 && clipCount2 == 1) )
215 : {
216 2216 : std::swap(clipCount2,clipCount1);
217 2216 : std::swap(clipCode2,clipCode1);
218 2216 : std::swap(aPt1,aPt2);
219 2216 : bRoundTowardsPt2 = !bRoundTowardsPt2;
220 : }
221 :
222 219159 : const sal_Int32 x1 = aPt1.getX();
223 219159 : const sal_Int32 x2 = aPt2.getX();
224 219159 : const sal_Int32 y1 = aPt1.getY();
225 219159 : const sal_Int32 y2 = aPt2.getY();
226 :
227 : // TODO(E1): This might overflow
228 219159 : sal_Int32 adx = x2 - x1;
229 219159 : int sx = 1;
230 219159 : if( adx < 0 )
231 : {
232 1953 : adx *= -1;
233 1953 : sx = -1;
234 : }
235 :
236 : // TODO(E1): This might overflow
237 219159 : sal_Int32 ady = y2 - y1;
238 219159 : int sy = 1;
239 219159 : if( ady < 0 )
240 : {
241 2871 : ady *= -1;
242 2871 : sy = -1;
243 : }
244 :
245 219159 : int n = 0;
246 219159 : sal_Int32 xs = x1;
247 219159 : sal_Int32 ys = y1;
248 219159 : bool bUseAlternateBresenham=false;
249 219159 : if( adx >= ady )
250 : {
251 : // semi-horizontal line
252 169630 : sal_Int32 rem = 2*ady - adx - !bRoundTowardsPt2;
253 :
254 169630 : 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 : rClipRect.getMaxX()-1, basegfx::tools::RectClipFlags::RIGHT,
258 : rClipRect.getMinY(), basegfx::tools::RectClipFlags::TOP,
259 : rClipRect.getMaxY()-1, basegfx::tools::RectClipFlags::BOTTOM,
260 : bRoundTowardsPt2, bUseAlternateBresenham ) )
261 : return; // line fully clipped away, no active pixel inside rect
262 :
263 169612 : Iterator currIter( begin + vigra::Diff2D(0,ys) );
264 : typename vigra::IteratorTraits<Iterator>::row_iterator
265 169612 : rowIter( currIter.rowIterator() + xs );
266 :
267 169612 : adx *= 2;
268 169612 : ady *= 2;
269 :
270 169612 : if( bUseAlternateBresenham )
271 : {
272 0 : while(true)
273 : {
274 10 : acc.set(color, rowIter);
275 :
276 10 : if( rem >= 0 )
277 : {
278 : // this is intended - we clip endpoint against y
279 : // plane, so n here denotes y range to render
280 10 : if( --n < 0 )
281 10 : break;
282 :
283 0 : ys += sy;
284 0 : xs += sx;
285 0 : rem -= adx;
286 :
287 0 : currIter.y += sy;
288 0 : rowIter = currIter.rowIterator() + xs;
289 : }
290 : else
291 : {
292 0 : xs += sx;
293 0 : rowIter += sx;
294 : }
295 :
296 0 : rem += ady;
297 : }
298 : }
299 : else
300 : {
301 4484096 : while(true)
302 : {
303 4653698 : acc.set(color, rowIter);
304 :
305 4653698 : if( --n < 0 )
306 169602 : break;
307 :
308 4484096 : if( rem >= 0 )
309 : {
310 703 : ys += sy;
311 703 : xs += sx;
312 703 : rem -= adx;
313 :
314 703 : currIter.y += sy;
315 703 : rowIter = currIter.rowIterator() + xs;
316 : }
317 : else
318 : {
319 4483393 : xs += sx;
320 4483393 : rowIter += sx;
321 : }
322 :
323 4484096 : rem += ady;
324 : }
325 : }
326 : }
327 : else
328 : {
329 : // semi-vertical line
330 49529 : sal_Int32 rem = 2*adx - ady - !bRoundTowardsPt2;
331 :
332 49529 : 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 : rClipRect.getMaxY()-1, basegfx::tools::RectClipFlags::BOTTOM,
336 : rClipRect.getMinX(), basegfx::tools::RectClipFlags::LEFT,
337 : rClipRect.getMaxX()-1, basegfx::tools::RectClipFlags::RIGHT,
338 : bRoundTowardsPt2, bUseAlternateBresenham ) )
339 : return; // line fully clipped away, no active pixel inside rect
340 :
341 49529 : Iterator currIter( begin + vigra::Diff2D(xs,0) );
342 : typename vigra::IteratorTraits<Iterator>::column_iterator
343 49529 : colIter( currIter.columnIterator() + ys );
344 :
345 49529 : adx *= 2;
346 49529 : ady *= 2;
347 :
348 49529 : if( bUseAlternateBresenham )
349 : {
350 12 : while(true)
351 : {
352 16 : acc.set(color, colIter);
353 :
354 16 : if( rem >= 0 )
355 : {
356 : // this is intended - we clip endpoint against x
357 : // plane, so n here denotes x range to render
358 8 : if( --n < 0 )
359 4 : break;
360 :
361 4 : xs += sx;
362 4 : ys += sy;
363 4 : rem -= ady;
364 :
365 4 : currIter.x += sx;
366 4 : colIter = currIter.columnIterator() + ys;
367 : }
368 : else
369 : {
370 8 : ys += sy;
371 8 : colIter += sy;
372 : }
373 :
374 12 : rem += adx;
375 : }
376 : }
377 : else
378 : {
379 975358 : while(true)
380 : {
381 1024883 : acc.set(color, colIter);
382 :
383 1024883 : if( --n < 0 )
384 49525 : break;
385 :
386 975358 : if( rem >= 0 )
387 : {
388 1352 : xs += sx;
389 1352 : ys += sy;
390 1352 : rem -= ady;
391 :
392 1352 : currIter.x += sx;
393 1352 : colIter = currIter.columnIterator() + ys;
394 : }
395 : else
396 : {
397 974006 : ys += sy;
398 974006 : colIter += sy;
399 : }
400 :
401 975358 : 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: */
|
