This looks like a lot but its a few small changes.
[blender.git] / source / blender / imbuf / intern / antialias.c
1 /**
2  * antialias.c
3  *
4  * $Id$
5  *
6  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version. The Blender
12  * Foundation also sells licenses for use in proprietary software under
13  * the Blender License.  See http://www.blender.org/BL/ for information
14  * about this.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, write to the Free Software Foundation,
23  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
24  *
25  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
26  * All rights reserved.
27  *
28  * The Original Code is: all of this file.
29  *
30  * Contributor(s): none yet.
31  *
32  * ***** END GPL/BL DUAL LICENSE BLOCK *****
33  */
34
35 #include "imbuf.h"
36
37 #include "BLI_blenlib.h"
38 #include "DNA_listBase.h"
39
40 #include "imbuf_patch.h"
41 #include "IMB_imbuf_types.h"
42 #include "IMB_imbuf.h"
43 #include "IMB_allocimbuf.h"
44
45 #ifdef HAVE_CONFIG_H
46 #include <config.h>
47 #endif
48
49 /* how it works:
50
51 1 - seek for a transistion in a collumn
52 2 - check the relationship with left and right, 
53
54 Is pixel above transition to the left or right equal to the top color, seek down
55
56 Is pixel below transition to the left or right equal to the bottom color, seek up 
57                 
58 */
59
60 /* there should be a funcion * to indicate if two colors are
61  * equal or not.
62  * For now we use a define
63  */
64
65
66 static unsigned int anti_mask = 0xffffffff;
67 static int anti_a, anti_b, anti_g, anti_r;
68
69 #define compare(x, y) ((x ^ y) & anti_mask)
70
71 typedef struct Edge
72 {
73         struct Edge * next, * prev;
74         short position;
75         int col1, col2;
76 }Edge;
77
78 static void anti_free_listarray(int count, ListBase * listarray)
79 {
80         int i;
81         
82         if (listarray == 0) return;
83         
84         for (i = 0; i < count; i++) BLI_freelistN(listarray + i);
85         MEM_freeN(listarray);   
86 }
87
88 static ListBase * scanimage(struct ImBuf * ibuf, int dir)
89 {
90         int step, pixels, lines, nextline, x, y, col1, col2;
91         unsigned int * rect;
92         ListBase * listarray, * curlist;
93         Edge * edge;
94         int count;
95         
96         switch (dir) {
97         case 'h':
98                 step = 1; nextline = ibuf->x;
99                 pixels = ibuf->x; lines = ibuf->y;
100                 break;
101 /*      case 'v':  changed so assured values for step etc.. */
102         default:
103                 step = ibuf->x; nextline = 1;
104                 pixels = ibuf->y; lines = ibuf->x;
105         }
106         
107         listarray = (ListBase*)MEM_callocN((lines)* sizeof(ListBase), "listarray");
108         for (y = 0; y < lines; y++){
109                 rect = ibuf->rect;
110                 rect += y * nextline;
111                 curlist = listarray + y;
112                 
113                 col1 = rect[0];
114                 count = 0;
115                 
116                 for (x = 0; x < pixels; x++) {
117                         col2 = rect[0];
118                         if (compare(col1, col2)) {
119                                 edge = NEW(Edge);
120                                 edge->position = x;
121                                 edge->col1 = col1;
122                                 edge->col2 = col2;
123                                 BLI_addtail(curlist, edge);
124                                 col1 = col2;
125                                 count++;
126                                 if (count > 100) {
127                                         printf("\n\n%s: Aborting antialias !\n", ibuf->name);
128                                         printf("To many transitions.\nIs this a natural image ?\n\n"), 
129                                         anti_free_listarray(lines, listarray);
130                                         return(0);
131                                 }
132                         }
133                         rect += step;
134                 }
135         }
136         
137         return(listarray);
138 }
139
140
141 static Edge * findmatch(Edge * first, Edge * edge)
142 {
143         Edge * match = 0;
144         int in = 0, out = 65535;
145         
146         if (edge->prev) in = edge->prev->position;
147         if (edge->next) out = edge->next->position;
148         
149         while (first) {
150                 if (first->position < edge->position) {
151                         if (first->col1 == edge->col1) {
152                                 if (first->position >= in) match = first;
153                         } else if (first->col2 == edge->col2) {
154                                 if (first->next == 0) match = first;
155                                 else if (first->next->position >= edge->position) match = first;
156                         } else if (first->col2 == edge->col1) {
157                                 match = 0; /* at 'sig saw' situations this one can be wrongly set */
158                         }
159                 } else if (first->position == edge->position) {
160                         if (first->col1 == edge->col1 || first->col2 == edge->col2) match = first;
161                 } else {
162                         if (match) break;       /* there is one */
163                         
164                         if (first->col1 == edge->col1) {
165                                 if (first->prev == 0) match = first;
166                                 else if (first->prev->position <= edge->position) match = first;
167                         } else if (first->col2 == edge->col2) {
168                                 if (first->position <= out) match = first;
169                         }
170                 }
171                 
172                 first = first->next;
173         }
174         
175         return(match);
176 }
177
178
179 static void filterdraw(unsigned int * ldest, unsigned int * lsrce, int zero, int half, int step)
180 {
181         uchar * src, * dst;
182         int count;
183         double weight, add;
184         
185         /* we filter the pixels at ldest between in and out with pixels from lsrce
186          * weight values go from 0 to 1
187          */
188         
189
190         count = half - zero;
191         if (count < 0) count = -count;
192         if (count <= 1) return;
193         
194         if (zero < half) {
195                 src = (uchar *) (lsrce + (step * zero));
196                 dst = (uchar *) (ldest + (step * zero));
197         } else {
198                 zero--;
199                 src = (uchar *) (lsrce + (step * zero));
200                 dst = (uchar *) (ldest + (step * zero));
201                 step = -step;
202         }
203         
204         step = 4 * step;
205         
206         dst += step * (count >> 1);
207         src += step * (count >> 1);
208         
209         count = (count + 1) >> 1;
210         add = 0.5 / count;
211         weight = 0.5 * add;
212         
213         /* this of course gamma corrected */
214         
215         for(; count > 0; count --) {
216                 if (anti_a) dst[0] += weight * (src[0] - dst[0]);
217                 if (anti_b) dst[1] += weight * (src[1] - dst[1]);
218                 if (anti_g) dst[2] += weight * (src[2] - dst[2]);
219                 if (anti_r) dst[3] += weight * (src[3] - dst[3]);
220                 dst += step;
221                 src += step;
222                 weight += add;
223         }
224 }
225
226 static void filterimage(struct ImBuf * ibuf, struct ImBuf * cbuf, ListBase * listarray, int dir)
227 {
228         int step, pixels, lines, nextline, y, pos, drawboth;
229         unsigned int * irect, * crect;
230         Edge * left, * middle, * right, temp, * any;
231         
232         switch (dir) {
233         case 'h':
234                 step = 1; nextline = ibuf->x;
235                 pixels = ibuf->x; lines = ibuf->y;
236                 break;
237 /*      case 'v': changed so have values */
238         default:
239                 step = ibuf->x; nextline = 1;
240                 pixels = ibuf->y; lines = ibuf->x;
241         }
242         
243         for (y = 1; y < lines - 1; y++){
244                 irect = ibuf->rect;
245                 irect += y * nextline;
246                 crect = cbuf->rect;
247                 crect += y * nextline;
248                 
249                 middle = listarray[y].first;
250                 while (middle) {
251                         left = findmatch(listarray[y - 1].first, middle);
252                         right = findmatch(listarray[y + 1].first, middle);
253                         drawboth = FALSE;
254                         
255                         if (left == 0 || right == 0) {
256                                 /* edge */
257                                 any = left;
258                                 if (right) any = right;
259                                 if (any) {
260                                         /* mirroring */
261                                         pos = 2 * middle->position - any->position;
262
263                                         if (any->position < middle->position) {
264                                                 if (pos > pixels - 1) pos = pixels - 1;
265                                                 if (middle->next) {
266                                                         if (pos > middle->next->position) pos = middle->next->position;
267                                                 }
268 /*                                              if (any->next) {
269                                                         if (pos > any->next->position) pos = any->next->position;
270                                                 }
271 */                                      } else {
272                                                 if (pos < 0) pos = 0;
273                                                 if (middle->prev) {
274                                                         if (pos < middle->prev->position) pos = middle->prev->position;
275                                                 }
276 /*                                              if (any->prev) {
277                                                         if (pos < any->prev->position) pos = any->prev->position;
278                                                 }
279 */                                      }
280                                         temp.position = pos;
281                                         if (left) right = &temp;
282                                         else left = &temp;
283                                         drawboth = TRUE;
284                                 }
285                         } else if (left->position == middle->position || right->position == middle->position) {
286                                 /* straight piece */
287                                 /* small corner, with one of the two at distance 2 (the other is at dist 0) ? */
288                                 
289                                 if (abs(left->position - right->position) == 2) drawboth = TRUE;
290                         } else if (left->position < middle->position && right->position > middle->position){
291                                 /* stair 1 */
292                                 drawboth = TRUE;
293                         } else if (left->position > middle->position && right->position < middle->position){
294                                 /* stair 2 */
295                                 drawboth = TRUE;
296                         } else {
297                                 /* a peek */
298                                 drawboth = TRUE;
299                         }
300                         
301                         if (drawboth) {
302                                 filterdraw(irect, crect - nextline, left->position, middle->position, step);
303                                 filterdraw(irect, crect + nextline, right->position, middle->position, step);
304                         }
305
306                         middle = middle->next;
307                 }
308         }
309 }
310
311
312 void IMB_antialias(struct ImBuf * ibuf)
313 {
314         struct ImBuf * cbuf;
315         ListBase * listarray;
316         
317         if (ibuf == 0) return;
318         cbuf = IMB_dupImBuf(ibuf);
319         
320         anti_a = (anti_mask >> 24) & 0xff;
321         anti_b = (anti_mask >> 16) & 0xff;
322         anti_g = (anti_mask >>  8) & 0xff;
323         anti_r = (anti_mask >>  0) & 0xff;
324         
325         listarray = scanimage(cbuf, 'h');
326         if (listarray) {
327                 filterimage(ibuf, cbuf, listarray, 'h');
328                 anti_free_listarray(ibuf->y, listarray);
329                 
330                 listarray = scanimage(cbuf, 'v');
331                 if (listarray) {
332                         filterimage(ibuf, cbuf, listarray, 'v');
333                         anti_free_listarray(ibuf->x, listarray);
334                 }
335         }
336                         
337         IMB_freeImBuf(cbuf);
338 }
339
340
341 /* intelligent scaling */
342
343 static void _intel_scale(struct ImBuf * ibuf, ListBase * listarray, int dir)
344 {
345         int step, lines, nextline, x, y, col;
346         unsigned int * irect, * trect;
347         int start, end;
348         Edge * left, * right;
349         struct ImBuf * tbuf;
350         
351         switch (dir) {
352         case 'h':
353                 step = 1; nextline = ibuf->x;
354                 lines = ibuf->y;
355                 tbuf = IMB_double_fast_y(ibuf);
356                 break;
357         case 'v':
358                 step = 2 * ibuf->x; nextline = 1;
359                 lines = ibuf->x;
360                 tbuf = IMB_double_fast_x(ibuf);
361                 break;
362         default:
363                 return;
364         }
365         
366         imb_freerectImBuf(ibuf);
367         ibuf->rect = tbuf->rect;
368         ibuf->mall |= IB_rect;
369         
370         
371         ibuf->x = tbuf->x;
372         ibuf->y = tbuf->y;
373         tbuf->rect = 0;
374         IMB_freeImBuf(tbuf);
375         
376         for (y = 0; y < lines - 2; y++){
377                 irect = ibuf->rect;
378                 irect += ((2 * y) + 1) * nextline;
379                 
380                 left = listarray[y].first;
381                 while (left) {
382                         right = findmatch(listarray[y + 1].first, left);
383                         if (right) {
384                                 if (left->col2 == right->col2) {
385                                         if (left->next && right->next) {
386                                                 if (left->next->position >= right->position) {
387                                                         start = ((left->position + right->position) >> 1);
388                                                         end = ((left->next->position + right->next->position) >> 1);
389                                                         col = left->col2;
390                                                         trect = irect + (start * step);
391                                                         for (x = start; x < end; x++) {
392                                                                 *trect = col;
393                                                                 trect += step;
394                                                         }
395                                                 }
396                                         }
397                                 }
398
399                                 if (left->col1 == right->col1) {
400                                         if (left->prev && right->prev) {
401                                                 if (left->prev->position <= right->position) {
402                                                         end = ((left->position + right->position) >> 1);
403                                                         start = ((left->prev->position + right->prev->position) >> 1);
404                                                         col = left->col1;
405                                                         trect = irect + (start * step);
406                                                         for (x = start; x < end; x++) {
407                                                                 *trect = col;
408                                                                 trect += step;
409                                                         }
410                                                 }
411                                         }
412                                 }
413
414                         }
415                         left = left->next;
416                 }
417         }
418 }
419
420
421 void IMB_clever_double(struct ImBuf * ibuf)
422 {
423         ListBase * listarray, * curlist;
424         Edge * new;
425         int size;
426         int i;
427         
428         if (ibuf == 0) return;
429         
430         size = ibuf->x;
431         listarray = scanimage(ibuf, 'v');
432         if (listarray) {
433                 for (i = 0; i < size; i++) {
434                         curlist = listarray + i;
435                         new = (Edge*)MEM_callocN(sizeof(Edge),"Edge");
436                         new->col2 = ibuf->rect[i]; /* upper pixel */
437                         new->col1 = new->col2 - 1;
438                         BLI_addhead(curlist, new);
439                         new = (Edge*)MEM_callocN(sizeof(Edge),"Edge");
440                         new->position = ibuf->y - 1;
441                         new->col1 = ibuf->rect[i + ((ibuf->y -1) * ibuf->x)]; /* bottom pixel */
442                         new->col2 = new->col1 - 1;
443                         BLI_addtail(curlist, new);
444                 }
445                 _intel_scale(ibuf, listarray, 'v');
446                 anti_free_listarray(size, listarray);
447
448                 size = ibuf->y;
449                 listarray = scanimage(ibuf, 'h');
450                 if (listarray) {
451                         for (i = 0; i < size; i++) {
452                                 curlist = listarray + i;
453                                 new =  (Edge*)MEM_callocN(sizeof(Edge),"Edge");
454                                 new->col2 = ibuf->rect[i * ibuf->x]; /* left pixel */
455                                 new->col1 = new->col2 - 1;
456                                 BLI_addhead(curlist, new);
457                                 new =  (Edge*)MEM_callocN(sizeof(Edge),"Edge");
458                                 new->position = ibuf->x - 1;
459                                 new->col1 = ibuf->rect[((i + 1) * ibuf->x) - 1]; /* right pixel */
460                                 new->col2 = new->col1 - 1;
461                                 BLI_addtail(curlist, new);
462                         }
463                         _intel_scale(ibuf, listarray, 'h');
464                         anti_free_listarray(size, listarray);
465                 }
466         }
467 }