svn merge -r 12937:13095 https://svn.blender.org/svnroot/bf-blender/trunk/blender
[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 /* how it works:
46
47 1 - seek for a transistion in a collumn
48 2 - check the relationship with left and right, 
49
50 Is pixel above transition to the left or right equal to the top color, seek down
51
52 Is pixel below transition to the left or right equal to the bottom color, seek up 
53                 
54 */
55
56 /* there should be a funcion * to indicate if two colors are
57  * equal or not.
58  * For now we use a define
59  */
60
61
62 static unsigned int anti_mask = 0xffffffff;
63 static int anti_a, anti_b, anti_g, anti_r;
64
65 #define compare(x, y) ((x ^ y) & anti_mask)
66
67 typedef struct Edge
68 {
69         struct Edge * next, * prev;
70         short position;
71         int col1, col2;
72 }Edge;
73
74 static void anti_free_listarray(int count, ListBase * listarray)
75 {
76         int i;
77         
78         if (listarray == 0) return;
79         
80         for (i = 0; i < count; i++) BLI_freelistN(listarray + i);
81         MEM_freeN(listarray);   
82 }
83
84 static ListBase * scanimage(struct ImBuf * ibuf, int dir)
85 {
86         int step, pixels, lines, nextline, x, y, col1, col2;
87         unsigned int * rect;
88         ListBase * listarray, * curlist;
89         Edge * edge;
90         int count;
91         
92         switch (dir) {
93         case 'h':
94                 step = 1; nextline = ibuf->x;
95                 pixels = ibuf->x; lines = ibuf->y;
96                 break;
97 /*      case 'v':  changed so assured values for step etc.. */
98         default:
99                 step = ibuf->x; nextline = 1;
100                 pixels = ibuf->y; lines = ibuf->x;
101         }
102         
103         listarray = (ListBase*)MEM_callocN((lines)* sizeof(ListBase), "listarray");
104         for (y = 0; y < lines; y++){
105                 rect = ibuf->rect;
106                 rect += y * nextline;
107                 curlist = listarray + y;
108                 
109                 col1 = rect[0];
110                 count = 0;
111                 
112                 for (x = 0; x < pixels; x++) {
113                         col2 = rect[0];
114                         if (compare(col1, col2)) {
115                                 edge = NEW(Edge);
116
117                                 if (edge == NULL) return(0);
118
119                                 edge->position = x;
120                                 edge->col1 = col1;
121                                 edge->col2 = col2;
122                                 BLI_addtail(curlist, edge);
123                                 col1 = col2;
124                                 count++;
125                                 if (count > 100) {
126                                         printf("\n\n%s: Aborting antialias !\n", ibuf->name);
127                                         printf("To many transitions.\nIs this a natural image ?\n\n"), 
128                                         anti_free_listarray(lines, listarray);
129                                         return(0);
130                                 }
131                         }
132                         rect += step;
133                 }
134         }
135         
136         return(listarray);
137 }
138
139
140 static Edge * findmatch(Edge * first, Edge * edge)
141 {
142         Edge * match = 0;
143         int in = 0, out = 65535;
144         
145         if (edge->prev) in = edge->prev->position;
146         if (edge->next) out = edge->next->position;
147         
148         while (first) {
149                 if (first->position < edge->position) {
150                         if (first->col1 == edge->col1) {
151                                 if (first->position >= in) match = first;
152                         } else if (first->col2 == edge->col2) {
153                                 if (first->next == 0) match = first;
154                                 else if (first->next->position >= edge->position) match = first;
155                         } else if (first->col2 == edge->col1) {
156                                 match = 0; /* at 'sig saw' situations this one can be wrongly set */
157                         }
158                 } else if (first->position == edge->position) {
159                         if (first->col1 == edge->col1 || first->col2 == edge->col2) match = first;
160                 } else {
161                         if (match) break;       /* there is one */
162                         
163                         if (first->col1 == edge->col1) {
164                                 if (first->prev == 0) match = first;
165                                 else if (first->prev->position <= edge->position) match = first;
166                         } else if (first->col2 == edge->col2) {
167                                 if (first->position <= out) match = first;
168                         }
169                 }
170                 
171                 first = first->next;
172         }
173         
174         return(match);
175 }
176
177
178 static void filterdraw(unsigned int * ldest, unsigned int * lsrce, int zero, int half, int step)
179 {
180         uchar * src, * dst;
181         int count;
182         double weight, add;
183         
184         /* we filter the pixels at ldest between in and out with pixels from lsrce
185          * weight values go from 0 to 1
186          */
187         
188
189         count = half - zero;
190         if (count < 0) count = -count;
191         if (count <= 1) return;
192         
193         if (zero < half) {
194                 src = (uchar *) (lsrce + (step * zero));
195                 dst = (uchar *) (ldest + (step * zero));
196         } else {
197                 zero--;
198                 src = (uchar *) (lsrce + (step * zero));
199                 dst = (uchar *) (ldest + (step * zero));
200                 step = -step;
201         }
202         
203         step = 4 * step;
204         
205         dst += step * (count >> 1);
206         src += step * (count >> 1);
207         
208         count = (count + 1) >> 1;
209         add = 0.5 / count;
210         weight = 0.5 * add;
211         
212         /* this of course gamma corrected */
213         
214         for(; count > 0; count --) {
215                 if (anti_a) dst[0] += weight * (src[0] - dst[0]);
216                 if (anti_b) dst[1] += weight * (src[1] - dst[1]);
217                 if (anti_g) dst[2] += weight * (src[2] - dst[2]);
218                 if (anti_r) dst[3] += weight * (src[3] - dst[3]);
219                 dst += step;
220                 src += step;
221                 weight += add;
222         }
223 }
224
225 static void filterimage(struct ImBuf * ibuf, struct ImBuf * cbuf, ListBase * listarray, int dir)
226 {
227         int step, pixels, lines, nextline, y, pos, drawboth;
228         unsigned int * irect, * crect;
229         Edge * left, * middle, * right, temp, * any;
230         
231         switch (dir) {
232         case 'h':
233                 step = 1; nextline = ibuf->x;
234                 pixels = ibuf->x; lines = ibuf->y;
235                 break;
236 /*      case 'v': changed so have values */
237         default:
238                 step = ibuf->x; nextline = 1;
239                 pixels = ibuf->y; lines = ibuf->x;
240         }
241         
242         for (y = 1; y < lines - 1; y++){
243                 irect = ibuf->rect;
244                 irect += y * nextline;
245                 crect = cbuf->rect;
246                 crect += y * nextline;
247                 
248                 middle = listarray[y].first;
249                 while (middle) {
250                         left = findmatch(listarray[y - 1].first, middle);
251                         right = findmatch(listarray[y + 1].first, middle);
252                         drawboth = FALSE;
253                         
254                         if (left == 0 || right == 0) {
255                                 /* edge */
256                                 any = left;
257                                 if (right) any = right;
258                                 if (any) {
259                                         /* mirroring */
260                                         pos = 2 * middle->position - any->position;
261
262                                         if (any->position < middle->position) {
263                                                 if (pos > pixels - 1) pos = pixels - 1;
264                                                 if (middle->next) {
265                                                         if (pos > middle->next->position) pos = middle->next->position;
266                                                 }
267 /*                                              if (any->next) {
268                                                         if (pos > any->next->position) pos = any->next->position;
269                                                 }
270 */                                      } else {
271                                                 if (pos < 0) pos = 0;
272                                                 if (middle->prev) {
273                                                         if (pos < middle->prev->position) pos = middle->prev->position;
274                                                 }
275 /*                                              if (any->prev) {
276                                                         if (pos < any->prev->position) pos = any->prev->position;
277                                                 }
278 */                                      }
279                                         temp.position = pos;
280                                         if (left) right = &temp;
281                                         else left = &temp;
282                                         drawboth = TRUE;
283                                 }
284                         } else if (left->position == middle->position || right->position == middle->position) {
285                                 /* straight piece */
286                                 /* small corner, with one of the two at distance 2 (the other is at dist 0) ? */
287                                 
288                                 if (abs(left->position - right->position) == 2) drawboth = TRUE;
289                         } else if (left->position < middle->position && right->position > middle->position){
290                                 /* stair 1 */
291                                 drawboth = TRUE;
292                         } else if (left->position > middle->position && right->position < middle->position){
293                                 /* stair 2 */
294                                 drawboth = TRUE;
295                         } else {
296                                 /* a peek */
297                                 drawboth = TRUE;
298                         }
299                         
300                         if (drawboth) {
301                                 filterdraw(irect, crect - nextline, left->position, middle->position, step);
302                                 filterdraw(irect, crect + nextline, right->position, middle->position, step);
303                         }
304
305                         middle = middle->next;
306                 }
307         }
308 }
309
310
311 void IMB_antialias(struct ImBuf * ibuf)
312 {
313         struct ImBuf * cbuf;
314         ListBase * listarray;
315         
316         if (ibuf == 0) return;
317         cbuf = IMB_dupImBuf(ibuf);
318         if (cbuf == 0) return;
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         if (tbuf == NULL) return;
367
368         imb_freerectImBuf(ibuf);
369
370         ibuf->rect = tbuf->rect;
371         ibuf->mall |= IB_rect;
372         
373         ibuf->x = tbuf->x;
374         ibuf->y = tbuf->y;
375         tbuf->rect = 0;
376         IMB_freeImBuf(tbuf);
377         
378         for (y = 0; y < lines - 2; y++){
379                 irect = ibuf->rect;
380                 irect += ((2 * y) + 1) * nextline;
381                 
382                 left = listarray[y].first;
383                 while (left) {
384                         right = findmatch(listarray[y + 1].first, left);
385                         if (right) {
386                                 if (left->col2 == right->col2) {
387                                         if (left->next && right->next) {
388                                                 if (left->next->position >= right->position) {
389                                                         start = ((left->position + right->position) >> 1);
390                                                         end = ((left->next->position + right->next->position) >> 1);
391                                                         col = left->col2;
392                                                         trect = irect + (start * step);
393                                                         for (x = start; x < end; x++) {
394                                                                 *trect = col;
395                                                                 trect += step;
396                                                         }
397                                                 }
398                                         }
399                                 }
400
401                                 if (left->col1 == right->col1) {
402                                         if (left->prev && right->prev) {
403                                                 if (left->prev->position <= right->position) {
404                                                         end = ((left->position + right->position) >> 1);
405                                                         start = ((left->prev->position + right->prev->position) >> 1);
406                                                         col = left->col1;
407                                                         trect = irect + (start * step);
408                                                         for (x = start; x < end; x++) {
409                                                                 *trect = col;
410                                                                 trect += step;
411                                                         }
412                                                 }
413                                         }
414                                 }
415
416                         }
417                         left = left->next;
418                 }
419         }
420 }
421
422
423 void IMB_clever_double(struct ImBuf * ibuf)
424 {
425         ListBase * listarray, * curlist;
426         Edge * new;
427         int size;
428         int i;
429         
430         if (ibuf == 0) return;
431         
432         size = ibuf->x;
433         listarray = scanimage(ibuf, 'v');
434         if (listarray) {
435                 for (i = 0; i < size; i++) {
436                         curlist = listarray + i;
437                         new = (Edge*)MEM_callocN(sizeof(Edge),"Edge");
438                         new->col2 = ibuf->rect[i]; /* upper pixel */
439                         new->col1 = new->col2 - 1;
440                         BLI_addhead(curlist, new);
441                         new = (Edge*)MEM_callocN(sizeof(Edge),"Edge");
442                         new->position = ibuf->y - 1;
443                         new->col1 = ibuf->rect[i + ((ibuf->y -1) * ibuf->x)]; /* bottom pixel */
444                         new->col2 = new->col1 - 1;
445                         BLI_addtail(curlist, new);
446                 }
447                 _intel_scale(ibuf, listarray, 'v');
448                 anti_free_listarray(size, listarray);
449
450                 size = ibuf->y;
451                 listarray = scanimage(ibuf, 'h');
452                 if (listarray) {
453                         for (i = 0; i < size; i++) {
454                                 curlist = listarray + i;
455                                 new =  (Edge*)MEM_callocN(sizeof(Edge),"Edge");
456                                 new->col2 = ibuf->rect[i * ibuf->x]; /* left pixel */
457                                 new->col1 = new->col2 - 1;
458                                 BLI_addhead(curlist, new);
459                                 new =  (Edge*)MEM_callocN(sizeof(Edge),"Edge");
460                                 new->position = ibuf->x - 1;
461                                 new->col1 = ibuf->rect[((i + 1) * ibuf->x) - 1]; /* right pixel */
462                                 new->col2 = new->col1 - 1;
463                                 BLI_addtail(curlist, new);
464                         }
465                         _intel_scale(ibuf, listarray, 'h');
466                         anti_free_listarray(size, listarray);
467                 }
468         }
469 }