Initial revision
[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
44 #include "IMB_allocimbuf.h"
45
46 /* werking:
47
48 1 - zoek een overgang in een kolom
49 2 - kijk wat de relatie met links en rechts is, 
50         
51         Is pixel boven overgang links of rechts ervan gelijk aan bovenste kleur, 
52         zoek dan naar beneden.
53         
54         Is pixel onder overgang links of rechts ervan gelijk aan onderste kleur, 
55         zoek dan naar boven.
56         
57         
58 */
59
60 /* er moet een functie * komen die aan kan geven of twee kleuren nu
61  * wel of niet gelijk zijn.
62  * Voor nu maar een define
63  */
64
65
66 /*
67         zipfork "cc -g anti.c util.o -lgl_s -limbuf -limage -lm -o anti > /dev/console"                                                                  
68         zipfork "anti /data/rt > /dev/console"                                                                  
69         zipfork "anti /pics/martin/03.01.ChambFinal/0001 > /dev/console"                                                                  
70 */
71
72 static unsigned int anti_mask = 0xffffffff;
73 static int anti_a, anti_b, anti_g, anti_r;
74
75 #define compare(x, y) ((x ^ y) & anti_mask)
76
77 typedef struct Edge
78 {
79         struct Edge * next, * prev;
80         short position;
81         int col1, col2;
82 }Edge;
83
84 static void anti_free_listarray(int count, ListBase * listarray)
85 {
86         int i;
87         
88         if (listarray == 0) return;
89         
90         for (i = 0; i < count; i++) BLI_freelistN(listarray + i);
91         MEM_freeN(listarray);   
92 }
93
94 static ListBase * scanimage(struct ImBuf * ibuf, int dir)
95 {
96         int step, pixels, lines, nextline, x, y, col1, col2;
97         unsigned int * rect;
98         ListBase * listarray, * curlist;
99         Edge * edge;
100         int count;
101         
102         switch (dir) {
103         case 'h':
104                 step = 1; nextline = ibuf->x;
105                 pixels = ibuf->x; lines = ibuf->y;
106                 break;
107         case 'v':
108                 step = ibuf->x; nextline = 1;
109                 pixels = ibuf->y; lines = ibuf->x;
110         }
111         
112         listarray = (ListBase*)MEM_callocN((lines)* sizeof(ListBase), "listarray");
113         for (y = 0; y < lines; y++){
114                 rect = ibuf->rect;
115                 rect += y * nextline;
116                 curlist = listarray + y;
117                 
118                 col1 = rect[0];
119                 count = 0;
120                 
121                 for (x = 0; x < pixels; x++) {
122                         col2 = rect[0];
123                         if (compare(col1, col2)) {
124                                 edge = NEW(Edge);
125                                 edge->position = x;
126                                 edge->col1 = col1;
127                                 edge->col2 = col2;
128                                 BLI_addtail(curlist, edge);
129                                 col1 = col2;
130                                 count++;
131                                 if (count > 100) {
132                                         printf("\n\n%s: Aborting antialias !\n", ibuf->name);
133                                         printf("To many transitions.\nIs this a natural image ?\n\n"), 
134                                         anti_free_listarray(lines, listarray);
135                                         return(0);
136                                 }
137                         }
138                         rect += step;
139                 }
140         }
141         
142         return(listarray);
143 }
144
145
146 static Edge * findmatch(Edge * first, Edge * edge)
147 {
148         Edge * match = 0;
149         int in = 0, out = 65535;
150         
151         if (edge->prev) in = edge->prev->position;
152         if (edge->next) out = edge->next->position;
153         
154         while (first) {
155                 if (first->position < edge->position) {
156                         if (first->col1 == edge->col1) {
157                                 if (first->position >= in) match = first;
158                         } else if (first->col2 == edge->col2) {
159                                 if (first->next == 0) match = first;
160                                 else if (first->next->position >= edge->position) match = first;
161                         } else if (first->col2 == edge->col1) {
162                                 match = 0; /* bij zigzagjes kan deze al 'ns foutief gezet zijn */
163                         }
164                 } else if (first->position == edge->position) {
165                         if (first->col1 == edge->col1 || first->col2 == edge->col2) match = first;
166                 } else {
167                         if (match) break;       /* er is er al een */
168                         
169                         if (first->col1 == edge->col1) {
170                                 if (first->prev == 0) match = first;
171                                 else if (first->prev->position <= edge->position) match = first;
172                         } else if (first->col2 == edge->col2) {
173                                 if (first->position <= out) match = first;
174                         }
175                 }
176                 
177                 first = first->next;
178         }
179         
180         return(match);
181 }
182
183
184 static void filterdraw(unsigned int * ldest, unsigned int * lsrce, int zero, int half, int step)
185 {
186         uchar * src, * dst;
187         int count;
188         double weight, add;
189         
190         /* we filteren de pixels op ldest tussen in en out met pixels van lsrce
191          * Het gewicht loopt ondertussen van 0 naar 1
192          */
193         
194
195         count = half - zero;
196         if (count < 0) count = -count;
197         if (count <= 1) return;
198         
199         if (zero < half) {
200                 src = (uchar *) (lsrce + (step * zero));
201                 dst = (uchar *) (ldest + (step * zero));
202         } else {
203                 zero--;
204                 src = (uchar *) (lsrce + (step * zero));
205                 dst = (uchar *) (ldest + (step * zero));
206                 step = -step;
207         }
208         
209         step = 4 * step;
210         
211         dst += step * (count >> 1);
212         src += step * (count >> 1);
213         
214         count = (count + 1) >> 1;
215         add = 0.5 / count;
216         weight = 0.5 * add;
217         
218         /* dit moet natuurlijk gamma gecorrigeerd */
219         
220         for(; count > 0; count --) {
221                 if (anti_a) dst[0] += weight * (src[0] - dst[0]);
222                 if (anti_b) dst[1] += weight * (src[1] - dst[1]);
223                 if (anti_g) dst[2] += weight * (src[2] - dst[2]);
224                 if (anti_r) dst[3] += weight * (src[3] - dst[3]);
225                 dst += step;
226                 src += step;
227                 weight += add;
228         }
229 }
230
231 static void filterimage(struct ImBuf * ibuf, struct ImBuf * cbuf, ListBase * listarray, int dir)
232 {
233         int step, pixels, lines, nextline, y, pos, drawboth;
234         unsigned int * irect, * crect;
235         Edge * left, * middle, * right, temp, * any;
236         
237         switch (dir) {
238         case 'h':
239                 step = 1; nextline = ibuf->x;
240                 pixels = ibuf->x; lines = ibuf->y;
241                 break;
242         case 'v':
243                 step = ibuf->x; nextline = 1;
244                 pixels = ibuf->y; lines = ibuf->x;
245         }
246         
247         for (y = 1; y < lines - 1; y++){
248                 irect = ibuf->rect;
249                 irect += y * nextline;
250                 crect = cbuf->rect;
251                 crect += y * nextline;
252                 
253                 middle = listarray[y].first;
254                 while (middle) {
255                         left = findmatch(listarray[y - 1].first, middle);
256                         right = findmatch(listarray[y + 1].first, middle);
257                         drawboth = FALSE;
258                         
259                         if (left == 0 || right == 0) {
260                                 /* rand */
261                                 any = left;
262                                 if (right) any = right;
263                                 if (any) {
264                                         /* spiegelen */
265                                         pos = 2 * middle->position - any->position;
266
267                                         if (any->position < middle->position) {
268                                                 if (pos > pixels - 1) pos = pixels - 1;
269                                                 if (middle->next) {
270                                                         if (pos > middle->next->position) pos = middle->next->position;
271                                                 }
272 /*                                              if (any->next) {
273                                                         if (pos > any->next->position) pos = any->next->position;
274                                                 }
275 */                                      } else {
276                                                 if (pos < 0) pos = 0;
277                                                 if (middle->prev) {
278                                                         if (pos < middle->prev->position) pos = middle->prev->position;
279                                                 }
280 /*                                              if (any->prev) {
281                                                         if (pos < any->prev->position) pos = any->prev->position;
282                                                 }
283 */                                      }
284                                         temp.position = pos;
285                                         if (left) right = &temp;
286                                         else left = &temp;
287                                         drawboth = TRUE;
288                                 }
289                         } else if (left->position == middle->position || right->position == middle->position) {
290                                 /* recht stuk */
291                                 /* klein hoekje, met een van de twee op afstand 2 (ander is toch op afstand 0) ? */
292                                 
293                                 if (abs(left->position - right->position) == 2) drawboth = TRUE;
294                         } else if (left->position < middle->position && right->position > middle->position){
295                                 /* trap 1 */
296                                 drawboth = TRUE;
297                         } else if (left->position > middle->position && right->position < middle->position){
298                                 /* trap 2 */
299                                 drawboth = TRUE;
300                         } else {
301                                 /* piek */
302                                 drawboth = TRUE;
303                         }
304                         
305                         if (drawboth) {
306                                 filterdraw(irect, crect - nextline, left->position, middle->position, step);
307                                 filterdraw(irect, crect + nextline, right->position, middle->position, step);
308                         }
309
310                         middle = middle->next;
311                 }
312         }
313 }
314
315
316 void IMB_antialias(struct ImBuf * ibuf)
317 {
318         struct ImBuf * cbuf;
319         ListBase * listarray;
320         
321         if (ibuf == 0) return;
322         cbuf = IMB_dupImBuf(ibuf);
323         
324         anti_a = (anti_mask >> 24) & 0xff;
325         anti_b = (anti_mask >> 16) & 0xff;
326         anti_g = (anti_mask >>  8) & 0xff;
327         anti_r = (anti_mask >>  0) & 0xff;
328         
329         listarray = scanimage(cbuf, 'h');
330         if (listarray) {
331                 filterimage(ibuf, cbuf, listarray, 'h');
332                 anti_free_listarray(ibuf->y, listarray);
333                 
334                 listarray = scanimage(cbuf, 'v');
335                 if (listarray) {
336                         filterimage(ibuf, cbuf, listarray, 'v');
337                         anti_free_listarray(ibuf->x, listarray);
338                 }
339         }
340                         
341         IMB_freeImBuf(cbuf);
342 }
343
344
345 /* intelligente scaling */
346
347 static void _intel_scale(struct ImBuf * ibuf, ListBase * listarray, int dir)
348 {
349         int step, lines, nextline, x, y, col;
350         unsigned int * irect, * trect;
351         int start, end;
352         Edge * left, * right;
353         struct ImBuf * tbuf;
354         
355         switch (dir) {
356         case 'h':
357                 step = 1; nextline = ibuf->x;
358                 lines = ibuf->y;
359                 tbuf = IMB_double_fast_y(ibuf);
360                 break;
361         case 'v':
362                 step = 2 * ibuf->x; nextline = 1;
363                 lines = ibuf->x;
364                 tbuf = IMB_double_fast_x(ibuf);
365                 break;
366         default:
367                 return;
368         }
369         
370         imb_freerectImBuf(ibuf);
371         ibuf->rect = tbuf->rect;
372         ibuf->mall |= IB_rect;
373         
374         
375         ibuf->x = tbuf->x;
376         ibuf->y = tbuf->y;
377         tbuf->rect = 0;
378         IMB_freeImBuf(tbuf);
379         
380         for (y = 0; y < lines - 2; y++){
381                 irect = ibuf->rect;
382                 irect += ((2 * y) + 1) * nextline;
383                 
384                 left = listarray[y].first;
385                 while (left) {
386                         right = findmatch(listarray[y + 1].first, left);
387                         if (right) {
388                                 if (left->col2 == right->col2) {
389                                         if (left->next && right->next) {
390                                                 if (left->next->position >= right->position) {
391                                                         start = ((left->position + right->position) >> 1);
392                                                         end = ((left->next->position + right->next->position) >> 1);
393                                                         col = left->col2;
394                                                         trect = irect + (start * step);
395                                                         for (x = start; x < end; x++) {
396                                                                 *trect = col;
397                                                                 trect += step;
398                                                         }
399                                                 }
400                                         }
401                                 }
402
403                                 if (left->col1 == right->col1) {
404                                         if (left->prev && right->prev) {
405                                                 if (left->prev->position <= right->position) {
406                                                         end = ((left->position + right->position) >> 1);
407                                                         start = ((left->prev->position + right->prev->position) >> 1);
408                                                         col = left->col1;
409                                                         trect = irect + (start * step);
410                                                         for (x = start; x < end; x++) {
411                                                                 *trect = col;
412                                                                 trect += step;
413                                                         }
414                                                 }
415                                         }
416                                 }
417
418                         }
419                         left = left->next;
420                 }
421         }
422 }
423
424
425 void IMB_clever_double(struct ImBuf * ibuf)
426 {
427         ListBase * listarray, * curlist;
428         Edge * new;
429         int size;
430         int i;
431         
432         if (ibuf == 0) return;
433         
434         size = ibuf->x;
435         listarray = scanimage(ibuf, 'v');
436         if (listarray) {
437                 for (i = 0; i < size; i++) {
438                         curlist = listarray + i;
439                         new = (Edge*)MEM_callocN(sizeof(Edge),"Edge");
440                         new->col2 = ibuf->rect[i]; /* bovenste pixel */
441                         new->col1 = new->col2 - 1;
442                         BLI_addhead(curlist, new);
443                         new = (Edge*)MEM_callocN(sizeof(Edge),"Edge");
444                         new->position = ibuf->y - 1;
445                         new->col1 = ibuf->rect[i + ((ibuf->y -1) * ibuf->x)]; /* onderste pixel */
446                         new->col2 = new->col1 - 1;
447                         BLI_addtail(curlist, new);
448                 }
449                 _intel_scale(ibuf, listarray, 'v');
450                 anti_free_listarray(size, listarray);
451
452                 size = ibuf->y;
453                 listarray = scanimage(ibuf, 'h');
454                 if (listarray) {
455                         for (i = 0; i < size; i++) {
456                                 curlist = listarray + i;
457                                 new =  (Edge*)MEM_callocN(sizeof(Edge),"Edge");
458                                 new->col2 = ibuf->rect[i * ibuf->x]; /* linkse pixel */
459                                 new->col1 = new->col2 - 1;
460                                 BLI_addhead(curlist, new);
461                                 new =  (Edge*)MEM_callocN(sizeof(Edge),"Edge");
462                                 new->position = ibuf->x - 1;
463                                 new->col1 = ibuf->rect[((i + 1) * ibuf->x) - 1]; /* rechtse pixel */
464                                 new->col2 = new->col1 - 1;
465                                 BLI_addtail(curlist, new);
466                         }
467                         _intel_scale(ibuf, listarray, 'h');
468                         anti_free_listarray(size, listarray);
469                 }
470         }
471 }