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