1 /**************************************************************
2 *
3 * Licensed to the Apache Software Foundation (ASF) under one
4 * or more contributor license agreements. See the NOTICE file
5 * distributed with this work for additional information
6 * regarding copyright ownership. The ASF licenses this file
7 * to you under the Apache License, Version 2.0 (the
8 * "License"); you may not use this file except in compliance
9 * with the License. You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing,
14 * software distributed under the License is distributed on an
15 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16 * KIND, either express or implied. See the License for the
17 * specific language governing permissions and limitations
18 * under the License.
19 *
20 *************************************************************/
21
22
23
24 #ifndef INCLUDED_BASEBMP_CLIPPEDLINERENDERER_HXX
25 #define INCLUDED_BASEBMP_CLIPPEDLINERENDERER_HXX
26
27 #include <basegfx/tools/rectcliptools.hxx>
28 #include <basegfx/point/b2ipoint.hxx>
29 #include <basegfx/range/b2irange.hxx>
30
31 #include <vigra/diff2d.hxx>
32 #include <vigra/iteratortraits.hxx>
33
34 namespace basebmp
35 {
36
37 // factored-out bresenham setup code, which is used from two different
38 // places in renderClippedLine() below. Admittedly messy for the long
39 // parameter list...
prepareClip(sal_Int32 a1,sal_Int32 a2,sal_Int32 b1,sal_Int32 da,sal_Int32 db,sal_Int32 & o_as,sal_Int32 & o_bs,int sa,int sb,sal_Int32 & io_rem,int & o_n,sal_uInt32 clipCode1,sal_uInt32 clipCount1,sal_uInt32 clipCode2,sal_uInt32 clipCount2,sal_Int32 aMin,sal_uInt32 aMinFlag,sal_Int32 aMax,sal_uInt32 aMaxFlag,sal_Int32 bMin,sal_uInt32 bMinFlag,sal_Int32 bMax,sal_uInt32 bMaxFlag,bool bRoundTowardsPt2)40 inline bool prepareClip( sal_Int32 a1,
41 sal_Int32 a2,
42 sal_Int32 b1,
43 sal_Int32 da,
44 sal_Int32 db,
45 sal_Int32& o_as,
46 sal_Int32& o_bs,
47 int sa,
48 int sb,
49 sal_Int32& io_rem,
50 int& o_n,
51 sal_uInt32 clipCode1,
52 sal_uInt32 clipCount1,
53 sal_uInt32 clipCode2,
54 sal_uInt32 clipCount2,
55 sal_Int32 aMin,
56 sal_uInt32 aMinFlag,
57 sal_Int32 aMax,
58 sal_uInt32 aMaxFlag,
59 sal_Int32 bMin,
60 sal_uInt32 bMinFlag,
61 sal_Int32 bMax,
62 sal_uInt32 bMaxFlag,
63 bool bRoundTowardsPt2 )
64 {
65 int ca(0), cb(0);
66 if( clipCode1 )
67 {
68 if( clipCode1 & aMinFlag )
69 {
70 ca = 2*db*(aMin - a1);
71 o_as = aMin;
72 }
73 else if( clipCode1 & aMaxFlag )
74 {
75 ca = 2*db*(a1 - aMax);
76 o_as = aMax;
77 }
78
79 if( clipCode1 & bMinFlag )
80 {
81 cb = 2*da*(bMin - b1);
82 o_bs = bMin;
83 }
84 else if( clipCode1 & bMaxFlag )
85 {
86 cb = 2*da*(b1 - bMax);
87 o_bs = bMax;
88 }
89
90 if( clipCount1 == 2 )
91 clipCode1 &= (ca + da < cb + !bRoundTowardsPt2) ? ~(aMinFlag|aMaxFlag) : ~(bMinFlag|bMaxFlag);
92
93 if( clipCode1 & (aMinFlag|aMaxFlag) )
94 {
95 cb = (ca + da - !bRoundTowardsPt2) / (2*da);
96
97 if( sb >= 0 )
98 {
99 o_bs = b1 + cb;
100 if( o_bs > bMax )
101 return false;
102 }
103 else
104 {
105 o_bs = b1 - cb;
106 if( o_bs < bMin )
107 return false;
108 }
109
110 io_rem += ca - 2*da*cb;
111 }
112 else
113 {
114 ca = (cb - da + 2*db - bRoundTowardsPt2) / (2*db);
115 if( sa >= 0 )
116 {
117 o_as = a1 + ca;
118 if( o_as > aMax )
119 return false;
120 }
121 else
122 {
123 o_as = a1 - ca;
124 if( o_as < aMin )
125 return false;
126 }
127
128 io_rem += 2*db*ca - cb;
129 }
130 }
131 else
132 {
133 o_as = a1; o_bs = b1;
134 }
135
136 bool bRetVal = false;
137 if( clipCode2 )
138 {
139 if( clipCount2 == 2 )
140 {
141 ca = 2*db*((clipCode2 & aMinFlag) ? a1 - aMin : aMax - a1);
142 cb = 2*da*((clipCode2 & bMinFlag) ? b1 - bMin : bMax - b1);
143 clipCode2 &= (cb + da < ca + bRoundTowardsPt2) ? ~(aMinFlag|aMaxFlag) : ~(bMinFlag|bMaxFlag);
144 }
145
146 if( clipCode2 & (aMinFlag|aMaxFlag) )
147 o_n = (clipCode2 & aMinFlag) ? o_as - aMin : aMax - o_as;
148 else
149 {
150 o_n = (clipCode2 & bMinFlag) ? o_bs - bMin : bMax - o_bs;
151 bRetVal = true;
152 }
153 }
154 else
155 o_n = (a2 >= o_as) ? a2 - o_as : o_as - a2;
156
157 return bRetVal;
158 }
159
160
161 /** Render line to image iterators, clip against given rectangle
162
163 This method renders a line from aPt1 to aPt2, clipped against
164 rClipRect (the clipping will take place pixel-perfect, i.e. as if
165 the original bresenham-rendered line would have been clipped each
166 pixel individually. No slight shifts compared to unclipped lines).
167
168 @param aPt1
169 Start point of the line
170
171 @param aPt2
172 End point of the line
173
174 @param rClipRect
175 Rectangle to clip against
176
177 @param color
178 Color value to render the line with
179
180 @param begin
181 left-top image iterator
182
183 @param end
184 right-bottom image iterator
185
186 @param acc
187 Image accessor
188
189 @param bRoundTowardsPt2
190 Rounding mode to use. Giving false here results in line pixel tend
191 towards pt1, i.e. when a pixel exactly hits the middle between two
192 pixel, the pixel closer to pt1 will be chosen. Giving true here
193 makes renderClippedLine() choose pt2 in those cases.
194 */
195 template< class Iterator, class Accessor >
renderClippedLine(basegfx::B2IPoint aPt1,basegfx::B2IPoint aPt2,const basegfx::B2IRange & rClipRect,typename Accessor::value_type color,Iterator begin,Accessor acc,bool bRoundTowardsPt2=false)196 void renderClippedLine( basegfx::B2IPoint aPt1,
197 basegfx::B2IPoint aPt2,
198 const basegfx::B2IRange& rClipRect,
199 typename Accessor::value_type color,
200 Iterator begin,
201 Accessor acc,
202 bool bRoundTowardsPt2=false )
203 {
204 // Algorithm according to Steven Eker's 'Pixel-perfect line clipping',
205 // Graphics Gems V, pp. 314-322
206 sal_uInt32 clipCode1 = basegfx::tools::getCohenSutherlandClipFlags(aPt1,
207 rClipRect);
208 sal_uInt32 clipCode2 = basegfx::tools::getCohenSutherlandClipFlags(aPt2,
209 rClipRect);
210
211 if( clipCode1 & clipCode2 )
212 return; // line fully clipped away
213
214 sal_uInt32 clipCount1 = basegfx::tools::getNumberOfClipPlanes(clipCode1);
215 sal_uInt32 clipCount2 = basegfx::tools::getNumberOfClipPlanes(clipCode2);
216
217 if( (clipCode1 != 0 && clipCode2 == 0)
218 || (clipCount1 == 2 && clipCount2 == 1) )
219 {
220 std::swap(clipCount2,clipCount1);
221 std::swap(clipCode2,clipCode1);
222 std::swap(aPt1,aPt2);
223 bRoundTowardsPt2 = !bRoundTowardsPt2;
224 }
225
226 const sal_Int32 x1 = aPt1.getX();
227 const sal_Int32 x2 = aPt2.getX();
228 const sal_Int32 y1 = aPt1.getY();
229 const sal_Int32 y2 = aPt2.getY();
230
231 // TODO(E1): This might overflow
232 sal_Int32 adx = x2 - x1;
233 int sx = 1;
234 if( adx < 0 )
235 {
236 adx *= -1;
237 sx = -1;
238 }
239
240 // TODO(E1): This might overflow
241 sal_Int32 ady = y2 - y1;
242 int sy = 1;
243 if( ady < 0 )
244 {
245 ady *= -1;
246 sy = -1;
247 }
248
249 int n = 0;
250 sal_Int32 xs = x1;
251 sal_Int32 ys = y1;
252 if( adx >= ady )
253 {
254 // semi-horizontal line
255 sal_Int32 rem = 2*ady - adx - !bRoundTowardsPt2;
256
257 const bool bUseAlternateBresenham(
258 prepareClip(x1, x2, y1, adx, ady, xs, ys, sx, sy,
259 rem, n, clipCode1, clipCount1, clipCode2, clipCount2,
260 rClipRect.getMinX(), basegfx::tools::RectClipFlags::LEFT,
261 rClipRect.getMaxX(), basegfx::tools::RectClipFlags::RIGHT,
262 rClipRect.getMinY(), basegfx::tools::RectClipFlags::TOP,
263 rClipRect.getMaxY(), basegfx::tools::RectClipFlags::BOTTOM,
264 bRoundTowardsPt2 ));
265
266 Iterator currIter( begin + vigra::Diff2D(0,ys) );
267 typename vigra::IteratorTraits<Iterator>::row_iterator
268 rowIter( currIter.rowIterator() + xs );
269
270 adx *= 2;
271 ady *= 2;
272
273 if( bUseAlternateBresenham )
274 {
275 while(true)
276 {
277 acc.set(color, rowIter);
278
279 if( rem >= 0 )
280 {
281 if( --n < 0 )
282 break;
283
284 ys += sy;
285 xs += sx;
286 rem -= adx;
287
288 currIter.y += sy;
289 rowIter = currIter.rowIterator() + xs;
290 }
291 else
292 {
293 xs += sx;
294 rowIter += sx;
295 }
296
297 rem += ady;
298 }
299 }
300 else
301 {
302 while(true)
303 {
304 acc.set(color, rowIter);
305
306 if( --n < 0 )
307 break;
308
309 if( rem >= 0 )
310 {
311 ys += sy;
312 xs += sx;
313 rem -= adx;
314
315 currIter.y += sy;
316 rowIter = currIter.rowIterator() + xs;
317 }
318 else
319 {
320 xs += sx;
321 rowIter += sx;
322 }
323
324 rem += ady;
325 }
326 }
327 }
328 else
329 {
330 // semi-vertical line
331 sal_Int32 rem = 2*adx - ady - !bRoundTowardsPt2;
332
333 const bool bUseAlternateBresenham(
334 prepareClip(y1, y2, x1, ady, adx, ys, xs, sy, sx,
335 rem, n, clipCode1, clipCount1, clipCode2, clipCount2,
336 rClipRect.getMinY(), basegfx::tools::RectClipFlags::TOP,
337 rClipRect.getMaxY(), basegfx::tools::RectClipFlags::BOTTOM,
338 rClipRect.getMinX(), basegfx::tools::RectClipFlags::LEFT,
339 rClipRect.getMaxX(), basegfx::tools::RectClipFlags::RIGHT,
340 bRoundTowardsPt2 ));
341
342 Iterator currIter( begin + vigra::Diff2D(xs,0) );
343 typename vigra::IteratorTraits<Iterator>::column_iterator
344 colIter( currIter.columnIterator() + ys );
345
346 adx *= 2;
347 ady *= 2;
348
349 if( bUseAlternateBresenham )
350 {
351 while(true)
352 {
353 acc.set(color, colIter);
354
355 if( rem >= 0 )
356 {
357 if( --n < 0 )
358 break;
359
360 xs += sx;
361 ys += sy;
362 rem -= ady;
363
364 currIter.x += sx;
365 colIter = currIter.columnIterator() + ys;
366 }
367 else
368 {
369 ys += sy;
370 colIter += sy;
371 }
372
373 rem += adx;
374 }
375 }
376 else
377 {
378 while(true)
379 {
380 acc.set(color, colIter);
381
382 if( --n < 0 )
383 break;
384
385 if( rem >= 0 )
386 {
387 xs += sx;
388 ys += sy;
389 rem -= ady;
390
391 currIter.x += sx;
392 colIter = currIter.columnIterator() + ys;
393 }
394 else
395 {
396 ys += sy;
397 colIter += sy;
398 }
399
400 rem += adx;
401 }
402 }
403 }
404 }
405
406 } // namespace basebmp
407
408 #endif /* INCLUDED_BASEBMP_CLIPPEDLINERENDERER_HXX */
409