Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/rotateshear.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 /*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 -
4 - Redistribution and use in source and binary forms, with or without
5 - modification, are permitted provided that the following conditions
6 - are met:
7 - 1. Redistributions of source code must retain the above copyright
8 - notice, this list of conditions and the following disclaimer.
9 - 2. Redistributions in binary form must reproduce the above
10 - copyright notice, this list of conditions and the following
11 - disclaimer in the documentation and/or other materials
12 - provided with the distribution.
13 -
14 - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15 - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16 - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17 - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18 - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19 - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20 - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21 - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22 - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23 - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24 - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 *====================================================================*/
26
27 /*!
28 * \file rotateshear.c
29 * <pre>
30 *
31 * Shear rotation about arbitrary point using 2 and 3 shears
32 *
33 * PIX *pixRotateShear()
34 * PIX *pixRotate2Shear()
35 * PIX *pixRotate3Shear()
36 *
37 * Shear rotation in-place about arbitrary point using 3 shears
38 * l_int32 pixRotateShearIP()
39 *
40 * Shear rotation around the image center
41 * PIX *pixRotateShearCenter() (2 or 3 shears)
42 * l_int32 pixRotateShearCenterIP() (3 shears)
43 *
44 * Rotation is measured in radians; clockwise rotations are positive.
45 *
46 * Rotation by shear works on images of any depth,
47 * including 8 bpp color paletted images and 32 bpp
48 * rgb images. It works by translating each src pixel
49 * value to the appropriate pixel in the rotated dest.
50 * For 8 bpp grayscale images, it is about 10-15x faster
51 * than rotation by area-mapping.
52 *
53 * This speed and flexibility comes at the following cost,
54 * relative to area-mapped rotation:
55 *
56 * ~ Jaggies are created on edges of straight lines
57 *
58 * ~ For large angles, where you must use 3 shears,
59 * there is some extra clipping from the shears.
60 *
61 * For small angles, typically less than 0.05 radians,
62 * rotation can be done with 2 orthogonal shears.
63 * Two such continuous shears (as opposed to the discrete
64 * shears on a pixel lattice that we have here) give
65 * a rotated image that has a distortion in the lengths
66 * of the two rotated and still-perpendicular axes. The
67 * length/width ratio changes by a fraction
68 *
69 * 0.5 * (angle)**2
70 *
71 * For an angle of 0.05 radians, this is about 1 part in
72 * a thousand. This distortion is absent when you use
73 * 3 continuous shears with the correct angles (see below).
74 *
75 * Of course, the image is on a discrete pixel lattice.
76 * Rotation by shear gives an approximation to a continuous
77 * rotation, leaving pixel jaggies at sharp boundaries.
78 * For very small rotations, rotating from a corner gives
79 * better sensitivity than rotating from the image center.
80 * Here's why. Define the shear "center" to be the line such
81 * that the image is sheared in opposite directions on
82 * each side of and parallel to the line. For small
83 * rotations there is a "dead space" on each side of the
84 * shear center of width equal to half the shear angle,
85 * in radians. Thus, when the image is sheared about the center,
86 * the dead space width equals the shear angle, but when
87 * the image is sheared from a corner, the dead space
88 * width is only half the shear angle.
89 *
90 * All horizontal and vertical shears are implemented by
91 * rasterop. The in-place rotation uses special in-place
92 * shears that copy rows sideways or columns vertically
93 * without buffering, and then rewrite old pixels that are
94 * no longer covered by sheared pixels. For that rewriting,
95 * you have the choice of using white or black pixels.
96 * When not in-place, the new pix is initialized with white or black
97 * pixels by pixSetBlackOrWhite(), which also works for cmapped pix.
98 * But for in-place, this initialization is not possible, so
99 * in-place shear operations on cmapped pix are not allowed.
100 *
101 * Rotation by shear is fast and depth-independent. However, it
102 * does not work well for large rotation angles. In fact, for
103 * rotation angles greater than about 7 degrees, more pixels are
104 * lost at the edges than when using pixRotationBySampling(), which
105 * only loses pixels because they are rotated out of the image.
106 * For larger rotations, use pixRotationBySampling() or, for
107 * more accuracy when d > 1 bpp, pixRotateAM().
108 *
109 * For small angles, when comparing the quality of rotation by
110 * sampling and by shear, you can see that rotation by sampling
111 * is slightly more accurate. However, the difference in
112 * accuracy of rotation by sampling when compared to 3-shear and
113 * (for angles less than 2 degrees, when compared to 2-shear) is
114 * less than 1 pixel at any point. For very small angles, rotation by
115 * sampling is much slower than rotation by shear. The speed difference
116 * depends on the pixel depth and the rotation angle. Rotation
117 * by shear is very fast for small angles and for small depth (esp. 1 bpp).
118 * Rotation by sampling speed is independent of angle and relatively
119 * more efficient for 8 and 32 bpp images. Here are some timings
120 * for the ratio of rotation times: (time for sampling)/ (time for shear)
121 *
122 * depth (bpp) ratio (2 deg) ratio (10 deg)
123 * -----------------------------------------------------
124 * 1 25 6
125 * 8 5 2.6
126 * 32 1.6 1.0
127 *
128 * In summary:
129 * * For d == 1 and small angles, use rotation by shear. By default
130 * this will use 2-shear rotations, because 3-shears cause more
131 * visible artifacts in straight lines and, for small angles, the
132 * distortion in asperity ratio is small.
133 * * For d > 1, shear is faster than sampling, which is faster than
134 * area mapping. However, area mapping gives the best results.
135 * These results are used in selecting the rotation methods in
136 * pixRotateShear().
137 *
138 * There has been some work on what is called a "quasishear
139 * rotation" ("The Quasi-Shear Rotation, Eric Andres,
140 * DGCI 1996, pp. 307-314). I believe they use a 3-shear
141 * approximation to the continuous rotation, exactly as
142 * we do here. The approximation is due to being on
143 * a square pixel lattice. They also use integers to specify
144 * the rotation angle and center offset, but that makes
145 * little sense on a machine where you have a few GFLOPS
146 * and only a few hundred floating point operations to do (!)
147 * They also allow subpixel specification of the center of
148 * rotation, which I haven't bothered with, and claim that
149 * better results are possible if each of the 4 quadrants is
150 * handled separately.
151 *
152 * But the bottom line is that you are going to see shear lines when
153 * you rotate 1 bpp images. Although the 3-shear rotation is
154 * mathematically exact in the limit of infinitesimal pixels, artifacts
155 * will be evident in real images. One might imagine using dithering
156 * to break up the horizontal and vertical shear lines, but this
157 * is hard with block shears, where you need to dither on the block
158 * boundaries. Dithering (by accumulation of 'error') with sampling
159 * makes more sense, but I haven't tried to do this. There is only
160 * so much you can do with 1 bpp images!
161 * </pre>
162 */
163
164 #ifdef HAVE_CONFIG_H
165 #include <config_auto.h>
166 #endif /* HAVE_CONFIG_H */
167
168 #include <math.h>
169 #include <string.h>
170 #include "allheaders.h"
171
172 /* Angle limits:
173 * angle < MinAngleToRotate ==> clone
174 * angle > MaxTwoShearAngle ==> warning for 2-angle shears
175 * angle > MaxThreeShearAngle ==> warning for 3-angle shears
176 * angle > MaxShearAngle ==> error
177 */
178 static const l_float32 MinAngleToRotate = 0.001f; /* radians; ~0.06 deg */
179 static const l_float32 MaxTwoShearAngle = 0.06f; /* radians; ~3 deg */
180 static const l_float32 MaxThreeShearAngle = 0.35f; /* radians; ~20 deg */
181 static const l_float32 MaxShearAngle = 0.50f; /* radians; ~29 deg */
182
183 /*------------------------------------------------------------------*
184 * Rotations about an arbitrary point *
185 *------------------------------------------------------------------*/
186 /*!
187 * \brief pixRotateShear()
188 *
189 * \param[in] pixs any depth; cmap ok
190 * \param[in] xcen x value for which there is no horizontal shear
191 * \param[in] ycen y value for which there is no vertical shear
192 * \param[in] angle radians
193 * \param[in] incolor L_BRING_IN_WHITE, L_BRING_IN_BLACK;
194 * \return pixd, or NULL on error.
195 *
196 * <pre>
197 * Notes:
198 * (1) This rotates an image about the given point, using
199 * either 2 or 3 shears.
200 * (2) A positive angle gives a clockwise rotation.
201 * (3) This brings in 'incolor' pixels from outside the image.
202 * (4) For rotation angles larger than about 0.35 radians, we issue
203 * a warning because you should probably be using another method
204 * (either sampling or area mapping)
205 * </pre>
206 */
207 PIX *
208 pixRotateShear(PIX *pixs,
209 l_int32 xcen,
210 l_int32 ycen,
211 l_float32 angle,
212 l_int32 incolor)
213 {
214 if (!pixs)
215 return (PIX *)(PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
216 if (incolor != L_BRING_IN_WHITE && incolor != L_BRING_IN_BLACK)
217 return (PIX *)(PIX *)ERROR_PTR("invalid incolor value", __func__, NULL);
218
219 if (L_ABS(angle) > MaxShearAngle) {
220 L_ERROR("%6.2f radians; too large for shear rotation\n", __func__,
221 L_ABS(angle));
222 return NULL;
223 }
224 if (L_ABS(angle) < MinAngleToRotate)
225 return pixClone(pixs);
226
227 if (L_ABS(angle) <= MaxTwoShearAngle)
228 return pixRotate2Shear(pixs, xcen, ycen, angle, incolor);
229 else
230 return pixRotate3Shear(pixs, xcen, ycen, angle, incolor);
231 }
232
233
234 /*!
235 * \brief pixRotate2Shear()
236 *
237 * \param[in] pixs any depth; cmap ok
238 * \param[in] xcen, ycen center of rotation
239 * \param[in] angle radians
240 * \param[in] incolor L_BRING_IN_WHITE, L_BRING_IN_BLACK;
241 * \return pixd, or NULL on error.
242 *
243 * <pre>
244 * Notes:
245 * (1) This rotates the image about the given point, using the 2-shear
246 * method. It should only be used for angles no larger than
247 * MaxTwoShearAngle. For larger angles, a warning is issued.
248 * (2) A positive angle gives a clockwise rotation.
249 * (3) 2-shear rotation by a specified angle is equivalent
250 * to the sequential transformations
251 * x' = x + tan(angle) * (y - ycen) for x-shear
252 * y' = y + tan(angle) * (x - xcen) for y-shear
253 * (4) Computation of tan(angle) is performed within the shear operation.
254 * (5) This brings in 'incolor' pixels from outside the image.
255 * (6) If the image has an alpha layer, it is rotated separately by
256 * two shears.
257 * </pre>
258 */
259 PIX *
260 pixRotate2Shear(PIX *pixs,
261 l_int32 xcen,
262 l_int32 ycen,
263 l_float32 angle,
264 l_int32 incolor)
265 {
266 PIX *pix1, *pix2, *pixd;
267
268 if (!pixs)
269 return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
270 if (incolor != L_BRING_IN_WHITE && incolor != L_BRING_IN_BLACK)
271 return (PIX *)(PIX *)ERROR_PTR("invalid incolor value", __func__, NULL);
272
273 if (L_ABS(angle) > MaxShearAngle) {
274 L_ERROR("%6.2f radians; too large for shear rotation\n", __func__,
275 L_ABS(angle));
276 return NULL;
277 }
278 if (L_ABS(angle) < MinAngleToRotate)
279 return pixClone(pixs);
280 if (L_ABS(angle) > MaxTwoShearAngle)
281 L_WARNING("%6.2f radians; large angle for 2-shear rotation\n",
282 __func__, L_ABS(angle));
283
284 if ((pix1 = pixHShear(NULL, pixs, ycen, angle, incolor)) == NULL)
285 return (PIX *)ERROR_PTR("pix1 not made", __func__, NULL);
286 pixd = pixVShear(NULL, pix1, xcen, angle, incolor);
287 pixDestroy(&pix1);
288 if (!pixd)
289 return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
290
291 if (pixGetDepth(pixs) == 32 && pixGetSpp(pixs) == 4) {
292 pix1 = pixGetRGBComponent(pixs, L_ALPHA_CHANNEL);
293 /* L_BRING_IN_WHITE brings in opaque for the alpha component */
294 pix2 = pixRotate2Shear(pix1, xcen, ycen, angle, L_BRING_IN_WHITE);
295 pixSetRGBComponent(pixd, pix2, L_ALPHA_CHANNEL);
296 pixDestroy(&pix1);
297 pixDestroy(&pix2);
298 }
299 return pixd;
300 }
301
302
303 /*!
304 * \brief pixRotate3Shear()
305 *
306 * \param[in] pixs any depth; cmap ok
307 * \param[in] xcen, ycen center of rotation
308 * \param[in] angle radians
309 * \param[in] incolor L_BRING_IN_WHITE, L_BRING_IN_BLACK;
310 * \return pixd, or NULL on error.
311 *
312 * <pre>
313 * Notes:
314 * (1) This rotates the image about the given point, using the 3-shear
315 * method. It should only be used for angles smaller than
316 * MaxThreeShearAngle. For larger angles, a warning is issued.
317 * (2) A positive angle gives a clockwise rotation.
318 * (3) 3-shear rotation by a specified angle is equivalent
319 * to the sequential transformations
320 * y' = y + tan(angle/2) * (x - xcen) for first y-shear
321 * x' = x + sin(angle) * (y - ycen) for x-shear
322 * y' = y + tan(angle/2) * (x - xcen) for second y-shear
323 * (4) Computation of tan(angle) is performed in the shear operations.
324 * (5) This brings in 'incolor' pixels from outside the image.
325 * (6) If the image has an alpha layer, it is rotated separately by
326 * two shears.
327 * (7) The algorithm was published by Alan Paeth: "A Fast Algorithm
328 * for General Raster Rotation," Graphics Interface '86,
329 * pp. 77-81, May 1986. A description of the method, along with
330 * an implementation, can be found in Graphics Gems, p. 179,
331 * edited by Andrew Glassner, published by Academic Press, 1990.
332 * </pre>
333 */
334 PIX *
335 pixRotate3Shear(PIX *pixs,
336 l_int32 xcen,
337 l_int32 ycen,
338 l_float32 angle,
339 l_int32 incolor)
340 {
341 l_float32 hangle;
342 PIX *pix1, *pix2, *pixd;
343
344 if (!pixs)
345 return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
346 if (incolor != L_BRING_IN_WHITE && incolor != L_BRING_IN_BLACK)
347 return (PIX *)(PIX *)ERROR_PTR("invalid incolor value", __func__, NULL);
348
349 if (L_ABS(angle) > MaxShearAngle) {
350 L_ERROR("%6.2f radians; too large for shear rotation\n", __func__,
351 L_ABS(angle));
352 return NULL;
353 }
354 if (L_ABS(angle) < MinAngleToRotate)
355 return pixClone(pixs);
356 if (L_ABS(angle) > MaxThreeShearAngle) {
357 L_WARNING("%6.2f radians; large angle for 3-shear rotation\n",
358 __func__, L_ABS(angle));
359 }
360
361 hangle = atan(sin(angle));
362 if ((pixd = pixVShear(NULL, pixs, xcen, angle / 2.f, incolor)) == NULL)
363 return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
364 if ((pix1 = pixHShear(NULL, pixd, ycen, hangle, incolor)) == NULL) {
365 pixDestroy(&pixd);
366 return (PIX *)ERROR_PTR("pix1 not made", __func__, NULL);
367 }
368 pixVShear(pixd, pix1, xcen, angle / 2.f, incolor);
369 pixDestroy(&pix1);
370
371 if (pixGetDepth(pixs) == 32 && pixGetSpp(pixs) == 4) {
372 pix1 = pixGetRGBComponent(pixs, L_ALPHA_CHANNEL);
373 /* L_BRING_IN_WHITE brings in opaque for the alpha component */
374 pix2 = pixRotate3Shear(pix1, xcen, ycen, angle, L_BRING_IN_WHITE);
375 pixSetRGBComponent(pixd, pix2, L_ALPHA_CHANNEL);
376 pixDestroy(&pix1);
377 pixDestroy(&pix2);
378 }
379 return pixd;
380 }
381
382
383 /*------------------------------------------------------------------*
384 * Rotations in-place about an arbitrary point *
385 *------------------------------------------------------------------*/
386 /*!
387 * \brief pixRotateShearIP()
388 *
389 * \param[in] pixs any depth; no cmap
390 * \param[in] xcen, ycen center of rotation
391 * \param[in] angle radians
392 * \param[in] incolor L_BRING_IN_WHITE, L_BRING_IN_BLACK
393 * \return 0 if OK; 1 on error
394 *
395 * <pre>
396 * Notes:
397 * (1) This does an in-place rotation of the image about the
398 * specified point, using the 3-shear method. It should only
399 * be used for angles smaller than MaxThreeShearAngle.
400 * For larger angles, a warning is issued.
401 * (2) A positive angle gives a clockwise rotation.
402 * (3) 3-shear rotation by a specified angle is equivalent
403 * to the sequential transformations
404 * y' = y + tan(angle/2) * (x - xcen) for first y-shear
405 * x' = x + sin(angle) * (y - ycen) for x-shear
406 * y' = y + tan(angle/2) * (x - xcen) for second y-shear
407 * (4) Computation of tan(angle) is performed in the shear operations.
408 * (5) This brings in 'incolor' pixels from outside the image.
409 * (6) The pix cannot be colormapped, because the in-place operation
410 * only blits in 0 or 1 bits, not an arbitrary colormap index.
411 * </pre>
412 */
413 l_ok
414 pixRotateShearIP(PIX *pixs,
415 l_int32 xcen,
416 l_int32 ycen,
417 l_float32 angle,
418 l_int32 incolor)
419 {
420 l_float32 hangle;
421
422 if (!pixs)
423 return ERROR_INT("pixs not defined", __func__, 1);
424 if (incolor != L_BRING_IN_WHITE && incolor != L_BRING_IN_BLACK)
425 return ERROR_INT("invalid value for incolor", __func__, 1);
426 if (pixGetColormap(pixs) != NULL)
427 return ERROR_INT("pixs is colormapped", __func__, 1);
428
429 if (angle == 0.0)
430 return 0;
431 if (L_ABS(angle) > MaxThreeShearAngle) {
432 L_WARNING("%6.2f radians; large angle for in-place 3-shear rotation\n",
433 __func__, L_ABS(angle));
434 }
435
436 hangle = atan(sin(angle));
437 pixHShearIP(pixs, ycen, angle / 2.f, incolor);
438 pixVShearIP(pixs, xcen, hangle, incolor);
439 pixHShearIP(pixs, ycen, angle / 2.f, incolor);
440 return 0;
441 }
442
443
444 /*------------------------------------------------------------------*
445 * Rotations about the image center *
446 *------------------------------------------------------------------*/
447 /*!
448 * \brief pixRotateShearCenter()
449 *
450 * \param[in] pixs any depth; cmap ok
451 * \param[in] angle radians
452 * \param[in] incolor L_BRING_IN_WHITE, L_BRING_IN_BLACK
453 * \return pixd, or NULL on error
454 */
455 PIX *
456 pixRotateShearCenter(PIX *pixs,
457 l_float32 angle,
458 l_int32 incolor)
459 {
460 if (!pixs)
461 return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
462
463 return pixRotateShear(pixs, pixGetWidth(pixs) / 2,
464 pixGetHeight(pixs) / 2, angle, incolor);
465 }
466
467
468 /*!
469 * \brief pixRotateShearCenterIP()
470 *
471 * \param[in] pixs any depth; no cmap
472 * \param[in] angle radians
473 * \param[in] incolor L_BRING_IN_WHITE, L_BRING_IN_BLACK
474 * \return 0 if OK, 1 on error
475 */
476 l_ok
477 pixRotateShearCenterIP(PIX *pixs,
478 l_float32 angle,
479 l_int32 incolor)
480 {
481 if (!pixs)
482 return ERROR_INT("pixs not defined", __func__, 1);
483
484 return pixRotateShearIP(pixs, pixGetWidth(pixs) / 2,
485 pixGetHeight(pixs) / 2, angle, incolor);
486 }