2 24c02865 2005-01-04 devnull * Rotate an image 180° in O(log Dx + log Dy)
3 24c02865 2005-01-04 devnull * draw calls, using an extra buffer the same size
4 24c02865 2005-01-04 devnull * as the image.
6 24c02865 2005-01-04 devnull * The basic concept is that you can invert an array by
7 24c02865 2005-01-04 devnull * inverting the top half, inverting the bottom half, and
8 24c02865 2005-01-04 devnull * then swapping them.
10 24c02865 2005-01-04 devnull * This is usually overkill, but it speeds up slow remote
11 24c02865 2005-01-04 devnull * connections quite a bit.
14 24c02865 2005-01-04 devnull #include <u.h>
15 24c02865 2005-01-04 devnull #include <libc.h>
16 24c02865 2005-01-04 devnull #include <bio.h>
17 24c02865 2005-01-04 devnull #include <draw.h>
18 05a4d855 2007-03-26 devnull #include <thread.h>
19 17157e4a 2006-03-20 devnull #include <cursor.h>
20 24c02865 2005-01-04 devnull #include "page.h"
22 24c02865 2005-01-04 devnull int ndraw = 0;
29 24c02865 2005-01-04 devnull static void reverse(Image*, Image*, int);
30 24c02865 2005-01-04 devnull static void shuffle(Image*, Image*, int, int, Image*, int, int);
31 24c02865 2005-01-04 devnull static void writefile(char *name, Image *im, int gran);
32 24c02865 2005-01-04 devnull static void halvemaskdim(Image*);
33 24c02865 2005-01-04 devnull static void swapranges(Image*, Image*, int, int, int, int);
36 24c02865 2005-01-04 devnull * Rotate the image 180° by reflecting first
37 24c02865 2005-01-04 devnull * along the X axis, and then along the Y axis.
40 24c02865 2005-01-04 devnull rot180(Image *img)
42 24c02865 2005-01-04 devnull Image *tmp;
44 24c02865 2005-01-04 devnull tmp = xallocimage(display, img->r, img->chan, 0, DNofill);
45 24c02865 2005-01-04 devnull if(tmp == nil)
48 24c02865 2005-01-04 devnull reverse(img, tmp, Xaxis);
49 24c02865 2005-01-04 devnull reverse(img, tmp, Yaxis);
51 24c02865 2005-01-04 devnull freeimage(tmp);
54 24c02865 2005-01-04 devnull Image *mtmp;
56 24c02865 2005-01-04 devnull static void
57 24c02865 2005-01-04 devnull reverse(Image *img, Image *tmp, int axis)
59 24c02865 2005-01-04 devnull Image *mask;
60 24c02865 2005-01-04 devnull Rectangle r;
61 24c02865 2005-01-04 devnull int i, d;
64 24c02865 2005-01-04 devnull * We start by swapping large chunks at a time.
65 24c02865 2005-01-04 devnull * The chunk size should be the largest power of
66 24c02865 2005-01-04 devnull * two that fits in the dimension.
68 24c02865 2005-01-04 devnull d = axis==Xaxis ? Dx(img) : Dy(img);
69 24c02865 2005-01-04 devnull for(i = 1; i*2 <= d; i *= 2)
72 24c02865 2005-01-04 devnull r = axis==Xaxis ? Rect(0,0, i,100) : Rect(0,0, 100,i);
73 24c02865 2005-01-04 devnull mask = xallocimage(display, r, GREY1, 1, DTransparent);
74 24c02865 2005-01-04 devnull mtmp = xallocimage(display, r, GREY1, 1, DTransparent);
77 24c02865 2005-01-04 devnull * Now color the bottom (or left) half of the mask opaque.
79 24c02865 2005-01-04 devnull if(axis==Xaxis)
80 24c02865 2005-01-04 devnull r.max.x /= 2;
82 24c02865 2005-01-04 devnull r.max.y /= 2;
84 24c02865 2005-01-04 devnull draw(mask, r, display->opaque, nil, ZP);
85 24c02865 2005-01-04 devnull writefile("mask", mask, i);
88 24c02865 2005-01-04 devnull * Shuffle will recur, shuffling the pieces as necessary
89 24c02865 2005-01-04 devnull * and making the mask a finer and finer grating.
91 24c02865 2005-01-04 devnull shuffle(img, tmp, axis, d, mask, i, 0);
93 24c02865 2005-01-04 devnull freeimage(mask);
97 24c02865 2005-01-04 devnull * Shuffle the image by swapping pieces of size maskdim.
99 24c02865 2005-01-04 devnull static void
100 24c02865 2005-01-04 devnull shuffle(Image *img, Image *tmp, int axis, int imgdim, Image *mask, int maskdim)
102 24c02865 2005-01-04 devnull int slop;
104 24c02865 2005-01-04 devnull if(maskdim == 0)
108 24c02865 2005-01-04 devnull * Figure out how much will be left over that needs to be
109 24c02865 2005-01-04 devnull * shifted specially to the bottom.
111 24c02865 2005-01-04 devnull slop = imgdim % maskdim;
114 24c02865 2005-01-04 devnull * Swap adjacent grating lines as per mask.
116 24c02865 2005-01-04 devnull swapadjacent(img, tmp, axis, imgdim - slop, mask, maskdim);
119 24c02865 2005-01-04 devnull * Calculate the mask with gratings half as wide and recur.
121 24c02865 2005-01-04 devnull halvemaskdim(mask, maskdim, axis);
122 24c02865 2005-01-04 devnull writefile("mask", mask, maskdim/2);
124 24c02865 2005-01-04 devnull shuffle(img, tmp, axis, imgdim, mask, maskdim/2);
127 24c02865 2005-01-04 devnull * Move the slop down to the bottom of the image.
129 24c02865 2005-01-04 devnull swapranges(img, tmp, 0, imgdim-slop, imgdim, axis);
130 24c02865 2005-01-04 devnull moveup(im, tmp, lastnn, nn, n, axis);
134 24c02865 2005-01-04 devnull * Halve the grating period in the mask.
135 fa325e9b 2020-01-10 cross * The grating currently looks like
136 24c02865 2005-01-04 devnull * ####____####____####____####____
137 24c02865 2005-01-04 devnull * where #### is opacity.
139 24c02865 2005-01-04 devnull * We want
140 24c02865 2005-01-04 devnull * ##__##__##__##__##__##__##__##__
141 24c02865 2005-01-04 devnull * which is achieved by shifting the mask
142 24c02865 2005-01-04 devnull * and drawing on itself through itself.
143 fa325e9b 2020-01-10 cross * Draw doesn't actually allow this, so
144 24c02865 2005-01-04 devnull * we have to copy it first.
146 24c02865 2005-01-04 devnull * ####____####____####____####____ (dst)
147 24c02865 2005-01-04 devnull * + ____####____####____####____#### (src)
148 24c02865 2005-01-04 devnull * in __####____####____####____####__ (mask)
149 24c02865 2005-01-04 devnull * ===========================================
150 24c02865 2005-01-04 devnull * ##__##__##__##__##__##__##__##__
152 24c02865 2005-01-04 devnull static void
153 24c02865 2005-01-04 devnull halvemaskdim(Image *m, int maskdim, int axis)
155 24c02865 2005-01-04 devnull Point δ;
157 24c02865 2005-01-04 devnull δ = axis==Xaxis ? Pt(maskdim,0) : Pt(0,maskdim);
158 24c02865 2005-01-04 devnull draw(mtmp, mtmp->r, mask, nil, mask->r.min);
159 24c02865 2005-01-04 devnull gendraw(mask, mask->r, mtmp, δ, mtmp, divpt(δ,2));
160 24c02865 2005-01-04 devnull writefile("mask", mask, maskdim/2);
164 24c02865 2005-01-04 devnull * Swap the regions [a,b] and [b,c]
166 24c02865 2005-01-04 devnull static void
167 24c02865 2005-01-04 devnull swapranges(Image *img, Image *tmp, int a, int b, int c, int axis)
169 24c02865 2005-01-04 devnull Rectangle r;
170 24c02865 2005-01-04 devnull Point δ;
172 24c02865 2005-01-04 devnull if(a == b || b == c)
175 24c02865 2005-01-04 devnull writefile("swap", img, 0);
176 24c02865 2005-01-04 devnull draw(tmp, tmp->r, im, nil, im->r.min);
178 24c02865 2005-01-04 devnull /* [a,a+(c-b)] gets [b,c] */
179 24c02865 2005-01-04 devnull r = img->r;
180 24c02865 2005-01-04 devnull if(axis==Xaxis){
181 24c02865 2005-01-04 devnull δ = Pt(1,0);
182 24c02865 2005-01-04 devnull r.min.x = img->r.min.x + a;
183 24c02865 2005-01-04 devnull r.max.x = img->r.min.x + a + (c-b);
185 24c02865 2005-01-04 devnull δ = Pt(0,1);
186 24c02865 2005-01-04 devnull r.min.y = img->r.min.y + a;
187 24c02865 2005-01-04 devnull r.max.y = img->r.min.y + a + (c-b);
189 24c02865 2005-01-04 devnull draw(img, r, tmp, nil, addpt(tmp->r.min, mulpt(δ, b)));
191 24c02865 2005-01-04 devnull /* [a+(c-b), c] gets [a,b] */
192 24c02865 2005-01-04 devnull r = img->r;
193 24c02865 2005-01-04 devnull if(axis==Xaxis){
194 24c02865 2005-01-04 devnull r.min.x = img->r.min.x + a + (c-b);
195 24c02865 2005-01-04 devnull r.max.x = img->r.min.x + c;
197 24c02865 2005-01-04 devnull r.min.y = img->r.min.y + a + (c-b);
198 24c02865 2005-01-04 devnull r.max.y = img->r.min.y + c;
200 24c02865 2005-01-04 devnull draw(img, r, tmp, nil, addpt(tmp->r.min, mulpt(δ, a)));
201 24c02865 2005-01-04 devnull writefile("swap", img, 1);
205 24c02865 2005-01-04 devnull * Swap adjacent regions as specified by the grating.
206 24c02865 2005-01-04 devnull * We do this by copying the image through the mask twice,
207 24c02865 2005-01-04 devnull * once aligned with the grading and once 180° out of phase.
209 24c02865 2005-01-04 devnull static void
210 24c02865 2005-01-04 devnull swapadjacent(Image *img, Image *tmp, int axis, int imgdim, Image *mask, int maskdim)
212 24c02865 2005-01-04 devnull Point δ;
213 24c02865 2005-01-04 devnull Rectangle r0, r1;
215 24c02865 2005-01-04 devnull δ = axis==Xaxis ? Pt(1,0) : Pt(0,1);
217 24c02865 2005-01-04 devnull r0 = img->r;
218 24c02865 2005-01-04 devnull r1 = img->r;
219 24c02865 2005-01-04 devnull switch(axis){
220 24c02865 2005-01-04 devnull case Xaxis:
221 24c02865 2005-01-04 devnull r0.max.x = imgdim;
222 24c02865 2005-01-04 devnull r1.min.x = imgdim;
224 24c02865 2005-01-04 devnull case Yaxis:
225 24c02865 2005-01-04 devnull r0.max.y = imgdim;
226 24c02865 2005-01-04 devnull r1.min.y = imgdim;
230 24c02865 2005-01-04 devnull * r0 is the lower rectangle, while r1 is the upper one.
232 fa325e9b 2020-01-10 cross draw(tmp, tmp->r, img, nil,
236 24c02865 2005-01-04 devnull interlace(Image *im, Image *tmp, int axis, int n, Image *mask, int gran)
238 24c02865 2005-01-04 devnull Point p0, p1;
239 24c02865 2005-01-04 devnull Rectangle r0, r1;
241 24c02865 2005-01-04 devnull r0 = im->r;
242 24c02865 2005-01-04 devnull r1 = im->r;
243 24c02865 2005-01-04 devnull switch(axis) {
244 24c02865 2005-01-04 devnull case Xaxis:
245 24c02865 2005-01-04 devnull r0.max.x = n;
246 24c02865 2005-01-04 devnull r1.min.x = n;
247 24c02865 2005-01-04 devnull p0 = (Point){gran, 0};
248 24c02865 2005-01-04 devnull p1 = (Point){-gran, 0};
250 24c02865 2005-01-04 devnull case Yaxis:
251 24c02865 2005-01-04 devnull r0.max.y = n;
252 24c02865 2005-01-04 devnull r1.min.y = n;
253 24c02865 2005-01-04 devnull p0 = (Point){0, gran};
254 24c02865 2005-01-04 devnull p1 = (Point){0, -gran};
258 24c02865 2005-01-04 devnull draw(tmp, im->r, im, display->black, im->r.min);
259 24c02865 2005-01-04 devnull gendraw(im, r0, tmp, p0, mask, mask->r.min);
260 24c02865 2005-01-04 devnull gendraw(im, r0, tmp, p1, mask, p1);
264 24c02865 2005-01-04 devnull static void
265 24c02865 2005-01-04 devnull writefile(char *name, Image *im, int gran)
267 24c02865 2005-01-04 devnull static int c = 100;
269 24c02865 2005-01-04 devnull char buf[200];
271 24c02865 2005-01-04 devnull snprint(buf, sizeof buf, "%d%s%d", c++, name, gran);
272 24c02865 2005-01-04 devnull fd = create(buf, OWRITE, 0666);
273 24c02865 2005-01-04 devnull if(fd < 0)
275 24c02865 2005-01-04 devnull writeimage(fd, im, 0);
276 24c02865 2005-01-04 devnull close(fd);
