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':
 102                 step = ibuf->x; nextline = 1;
 103                 pixels = ibuf->y; lines = ibuf->x;
 104         }
 105
 106         listarray = (ListBase*)MEM_callocN((lines)* sizeof(ListBase), "listarray");
 107         for (y = 0; y < lines; y++){
 108                 rect = ibuf->rect;
 109                 rect += y * nextline;
 110                 curlist = listarray + y;
 111
 112                 col1 = rect[0];
 113                 count = 0;
 114
 115                 for (x = 0; x < pixels; x++) {
 116                         col2 = rect[0];
 117                         if (compare(col1, col2)) {
 118                                 edge = NEW(Edge);
 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':
 237                 step = ibuf->x; nextline = 1;
 238                 pixels = ibuf->y; lines = ibuf->x;
 239         }
 240
 241         for (y = 1; y < lines - 1; y++){
 242                 irect = ibuf->rect;
 243                 irect += y * nextline;
 244                 crect = cbuf->rect;
 245                 crect += y * nextline;
 246
 247                 middle = listarray[y].first;
 248                 while (middle) {
 249                         left = findmatch(listarray[y - 1].first, middle);
 250                         right = findmatch(listarray[y + 1].first, middle);
 251                         drawboth = FALSE;
 252
 253                         if (left == 0 || right == 0) {
 254                                 /* edge */
 255                                 any = left;
 256                                 if (right) any = right;
 257                                 if (any) {
 258                                         /* mirroring */
 259                                         pos = 2 * middle->position - any->position;
 260
 261                                         if (any->position < middle->position) {
 262                                                 if (pos > pixels - 1) pos = pixels - 1;
 263                                                 if (middle->next) {
 264                                                         if (pos > middle->next->position) pos = middle->next->position;
 265                                                 }
 266 /*                                              if (any->next) {
 267                                                         if (pos > any->next->position) pos = any->next->position;
 268                                                 }
 269 */                                      } else {
 270                                                 if (pos < 0) pos = 0;
 271                                                 if (middle->prev) {
 272                                                         if (pos < middle->prev->position) pos = middle->prev->position;
 273                                                 }
 274 /*                                              if (any->prev) {
 275                                                         if (pos < any->prev->position) pos = any->prev->position;
 276                                                 }
 277 */                                      }
 278                                         temp.position = pos;
 279                                         if (left) right = &temp;
 280                                         else left = &temp;
 281                                         drawboth = TRUE;
 282                                 }
 283                         } else if (left->position == middle->position || right->position == middle->position) {
 284                                 /* straight piece */
 285                                 /* small corner, with one of the two at distance 2 (the other is at dist 0) ? */
 286
 287                                 if (abs(left->position - right->position) == 2) drawboth = TRUE;
 288                         } else if (left->position < middle->position && right->position > middle->position){
 289                                 /* stair 1 */
 290                                 drawboth = TRUE;
 291                         } else if (left->position > middle->position && right->position < middle->position){
 292                                 /* stair 2 */
 293                                 drawboth = TRUE;
 294                         } else {
 295                                 /* a peek */
 296                                 drawboth = TRUE;
 297                         }
 298
 299                         if (drawboth) {
 300                                 filterdraw(irect, crect - nextline, left->position, middle->position, step);
 301                                 filterdraw(irect, crect + nextline, right->position, middle->position, step);
 302                         }
 303
 304                         middle = middle->next;
 305                 }
 306         }
 307 }
 308
 309
 310 void IMB_antialias(struct ImBuf * ibuf)
 311 {
 312         struct ImBuf * cbuf;
 313         ListBase * listarray;
 314
 315         if (ibuf == 0) return;
 316         cbuf = IMB_dupImBuf(ibuf);
 317
 318         anti_a = (anti_mask >> 24) & 0xff;
 319         anti_b = (anti_mask >> 16) & 0xff;
 320         anti_g = (anti_mask >>  8) & 0xff;
 321         anti_r = (anti_mask >>  0) & 0xff;
 322
 323         listarray = scanimage(cbuf, 'h');
 324         if (listarray) {
 325                 filterimage(ibuf, cbuf, listarray, 'h');
 326                 anti_free_listarray(ibuf->y, listarray);
 327
 328                 listarray = scanimage(cbuf, 'v');
 329                 if (listarray) {
 330                         filterimage(ibuf, cbuf, listarray, 'v');
 331                         anti_free_listarray(ibuf->x, listarray);
 332                 }
 333         }
 334
 335         IMB_freeImBuf(cbuf);
 336 }
 337
 338
 339 /* intelligent scaling */
 340
 341 static void _intel_scale(struct ImBuf * ibuf, ListBase * listarray, int dir)
 342 {
 343         int step, lines, nextline, x, y, col;
 344         unsigned int * irect, * trect;
 345         int start, end;
 346         Edge * left, * right;
 347         struct ImBuf * tbuf;
 348
 349         switch (dir) {
 350         case 'h':
 351                 step = 1; nextline = ibuf->x;
 352                 lines = ibuf->y;
 353                 tbuf = IMB_double_fast_y(ibuf);
 354                 break;
 355         case 'v':
 356                 step = 2 * ibuf->x; nextline = 1;
 357                 lines = ibuf->x;
 358                 tbuf = IMB_double_fast_x(ibuf);
 359                 break;
 360         default:
 361                 return;
 362         }
 363
 364         imb_freerectImBuf(ibuf);
 365         ibuf->rect = tbuf->rect;
 366         ibuf->mall |= IB_rect;
 367
 368
 369         ibuf->x = tbuf->x;
 370         ibuf->y = tbuf->y;
 371         tbuf->rect = 0;
 372         IMB_freeImBuf(tbuf);
 373
 374         for (y = 0; y < lines - 2; y++){
 375                 irect = ibuf->rect;
 376                 irect += ((2 * y) + 1) * nextline;
 377
 378                 left = listarray[y].first;
 379                 while (left) {
 380                         right = findmatch(listarray[y + 1].first, left);
 381                         if (right) {
 382                                 if (left->col2 == right->col2) {
 383                                         if (left->next && right->next) {
 384                                                 if (left->next->position >= right->position) {
 385                                                         start = ((left->position + right->position) >> 1);
 386                                                         end = ((left->next->position + right->next->position) >> 1);
 387                                                         col = left->col2;
 388                                                         trect = irect + (start * step);
 389                                                         for (x = start; x < end; x++) {
 390                                                                 *trect = col;
 391                                                                 trect += step;
 392                                                         }
 393                                                 }
 394                                         }
 395                                 }
 396
 397                                 if (left->col1 == right->col1) {
 398                                         if (left->prev && right->prev) {
 399                                                 if (left->prev->position <= right->position) {
 400                                                         end = ((left->position + right->position) >> 1);
 401                                                         start = ((left->prev->position + right->prev->position) >> 1);
 402                                                         col = left->col1;
 403                                                         trect = irect + (start * step);
 404                                                         for (x = start; x < end; x++) {
 405                                                                 *trect = col;
 406                                                                 trect += step;
 407                                                         }
 408                                                 }
 409                                         }
 410                                 }
 411
 412                         }
 413                         left = left->next;
 414                 }
 415         }
 416 }
 417
 418
 419 void IMB_clever_double(struct ImBuf * ibuf)
 420 {
 421         ListBase * listarray, * curlist;
 422         Edge * new;
 423         int size;
 424         int i;
 425
 426         if (ibuf == 0) return;
 427
 428         size = ibuf->x;
 429         listarray = scanimage(ibuf, 'v');
 430         if (listarray) {
 431                 for (i = 0; i < size; i++) {
 432                         curlist = listarray + i;
 433                         new = (Edge*)MEM_callocN(sizeof(Edge),"Edge");
 434                         new->col2 = ibuf->rect[i]; /* upper pixel */
 435                         new->col1 = new->col2 - 1;
 436                         BLI_addhead(curlist, new);
 437                         new = (Edge*)MEM_callocN(sizeof(Edge),"Edge");
 438                         new->position = ibuf->y - 1;
 439                         new->col1 = ibuf->rect[i + ((ibuf->y -1) * ibuf->x)]; /* bottom pixel */
 440                         new->col2 = new->col1 - 1;
 441                         BLI_addtail(curlist, new);
 442                 }
 443                 _intel_scale(ibuf, listarray, 'v');
 444                 anti_free_listarray(size, listarray);
 445
 446                 size = ibuf->y;
 447                 listarray = scanimage(ibuf, 'h');
 448                 if (listarray) {
 449                         for (i = 0; i < size; i++) {
 450                                 curlist = listarray + i;
 451                                 new =  (Edge*)MEM_callocN(sizeof(Edge),"Edge");
 452                                 new->col2 = ibuf->rect[i * ibuf->x]; /* left pixel */
 453                                 new->col1 = new->col2 - 1;
 454                                 BLI_addhead(curlist, new);
 455                                 new =  (Edge*)MEM_callocN(sizeof(Edge),"Edge");
 456                                 new->position = ibuf->x - 1;
 457                                 new->col1 = ibuf->rect[((i + 1) * ibuf->x) - 1]; /* right pixel */
 458                                 new->col2 = new->col1 - 1;
 459                                 BLI_addtail(curlist, new);
 460                         }
 461                         _intel_scale(ibuf, listarray, 'h');
 462                         anti_free_listarray(size, listarray);
 463                 }
 464         }
 465 }