/**
 * antialias.c
 *
 * $Id$
 *
 * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version. The Blender
 * Foundation also sells licenses for use in proprietary software under
 * the Blender License.  See http://www.blender.org/BL/ for information
 * about this.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
 * All rights reserved.
 *
 * The Original Code is: all of this file.
 *
 * Contributor(s): none yet.
 *
 * ***** END GPL/BL DUAL LICENSE BLOCK *****
 */

#include "imbuf.h"

#include "BLI_blenlib.h"
#include "DNA_listBase.h"

#include "imbuf_patch.h"
#include "IMB_imbuf_types.h"
#include "IMB_imbuf.h"

#include "IMB_allocimbuf.h"

/* werking:

1 - zoek een overgang in een kolom
2 - kijk wat de relatie met links en rechts is, 
	
	Is pixel boven overgang links of rechts ervan gelijk aan bovenste kleur, 
	zoek dan naar beneden.
	
	Is pixel onder overgang links of rechts ervan gelijk aan onderste kleur, 
	zoek dan naar boven.
	
	
*/

/* er moet een functie * komen die aan kan geven of twee kleuren nu
 * wel of niet gelijk zijn.
 * Voor nu maar een define
 */


/*
	zipfork "cc -g anti.c util.o -lgl_s -limbuf -limage -lm -o anti > /dev/console"                                                                  
	zipfork "anti /data/rt > /dev/console"                                                                  
	zipfork "anti /pics/martin/03.01.ChambFinal/0001 > /dev/console"                                                                  
*/

static unsigned int anti_mask = 0xffffffff;
static int anti_a, anti_b, anti_g, anti_r;

#define compare(x, y) ((x ^ y) & anti_mask)

typedef struct Edge
{
	struct Edge * next, * prev;
	short position;
	int col1, col2;
}Edge;

static void anti_free_listarray(int count, ListBase * listarray)
{
	int i;
	
	if (listarray == 0) return;
	
	for (i = 0; i < count; i++) BLI_freelistN(listarray + i);
	MEM_freeN(listarray);	
}

static ListBase * scanimage(struct ImBuf * ibuf, int dir)
{
	int step, pixels, lines, nextline, x, y, col1, col2;
	unsigned int * rect;
	ListBase * listarray, * curlist;
	Edge * edge;
	int count;
	
	switch (dir) {
	case 'h':
		step = 1; nextline = ibuf->x;
		pixels = ibuf->x; lines = ibuf->y;
		break;
	case 'v':
		step = ibuf->x; nextline = 1;
		pixels = ibuf->y; lines = ibuf->x;
	}
	
	listarray = (ListBase*)MEM_callocN((lines)* sizeof(ListBase), "listarray");
	for (y = 0; y < lines; y++){
		rect = ibuf->rect;
		rect += y * nextline;
		curlist = listarray + y;
		
		col1 = rect[0];
		count = 0;
		
		for (x = 0; x < pixels; x++) {
			col2 = rect[0];
			if (compare(col1, col2)) {
				edge = NEW(Edge);
				edge->position = x;
				edge->col1 = col1;
				edge->col2 = col2;
				BLI_addtail(curlist, edge);
				col1 = col2;
				count++;
				if (count > 100) {
					printf("\n\n%s: Aborting antialias !\n", ibuf->name);
					printf("To many transitions.\nIs this a natural image ?\n\n"), 
					anti_free_listarray(lines, listarray);
					return(0);
				}
			}
			rect += step;
		}
	}
	
	return(listarray);
}


static Edge * findmatch(Edge * first, Edge * edge)
{
	Edge * match = 0;
	int in = 0, out = 65535;
	
	if (edge->prev) in = edge->prev->position;
	if (edge->next) out = edge->next->position;
	
	while (first) {
		if (first->position < edge->position) {
			if (first->col1 == edge->col1) {
				if (first->position >= in) match = first;
			} else if (first->col2 == edge->col2) {
				if (first->next == 0) match = first;
				else if (first->next->position >= edge->position) match = first;
			} else if (first->col2 == edge->col1) {
				match = 0; /* bij zigzagjes kan deze al 'ns foutief gezet zijn */
			}
		} else if (first->position == edge->position) {
			if (first->col1 == edge->col1 || first->col2 == edge->col2) match = first;
		} else {
			if (match) break;	/* er is er al een */
			
			if (first->col1 == edge->col1) {
				if (first->prev == 0) match = first;
				else if (first->prev->position <= edge->position) match = first;
			} else if (first->col2 == edge->col2) {
				if (first->position <= out) match = first;
			}
		}
		
		first = first->next;
	}
	
	return(match);
}


static void filterdraw(unsigned int * ldest, unsigned int * lsrce, int zero, int half, int step)
{
	uchar * src, * dst;
	int count;
	double weight, add;
	
	/* we filteren de pixels op ldest tussen in en out met pixels van lsrce
	 * Het gewicht loopt ondertussen van 0 naar 1
	 */
	

	count = half - zero;
	if (count < 0) count = -count;
	if (count <= 1) return;
	
	if (zero < half) {
		src = (uchar *) (lsrce + (step * zero));
		dst = (uchar *) (ldest + (step * zero));
	} else {
		zero--;
		src = (uchar *) (lsrce + (step * zero));
		dst = (uchar *) (ldest + (step * zero));
		step = -step;
	}
	
	step = 4 * step;
	
	dst += step * (count >> 1);
	src += step * (count >> 1);
	
	count = (count + 1) >> 1;
	add = 0.5 / count;
	weight = 0.5 * add;
	
	/* dit moet natuurlijk gamma gecorrigeerd */
	
	for(; count > 0; count --) {
		if (anti_a) dst[0] += weight * (src[0] - dst[0]);
		if (anti_b) dst[1] += weight * (src[1] - dst[1]);
		if (anti_g) dst[2] += weight * (src[2] - dst[2]);
		if (anti_r) dst[3] += weight * (src[3] - dst[3]);
		dst += step;
		src += step;
		weight += add;
	}
}

static void filterimage(struct ImBuf * ibuf, struct ImBuf * cbuf, ListBase * listarray, int dir)
{
	int step, pixels, lines, nextline, y, pos, drawboth;
	unsigned int * irect, * crect;
	Edge * left, * middle, * right, temp, * any;
	
	switch (dir) {
	case 'h':
		step = 1; nextline = ibuf->x;
		pixels = ibuf->x; lines = ibuf->y;
		break;
	case 'v':
		step = ibuf->x; nextline = 1;
		pixels = ibuf->y; lines = ibuf->x;
	}
	
	for (y = 1; y < lines - 1; y++){
		irect = ibuf->rect;
		irect += y * nextline;
		crect = cbuf->rect;
		crect += y * nextline;
		
		middle = listarray[y].first;
		while (middle) {
			left = findmatch(listarray[y - 1].first, middle);
			right = findmatch(listarray[y + 1].first, middle);
			drawboth = FALSE;
			
			if (left == 0 || right == 0) {
				/* rand */
				any = left;
				if (right) any = right;
				if (any) {
					/* spiegelen */
					pos = 2 * middle->position - any->position;

					if (any->position < middle->position) {
						if (pos > pixels - 1) pos = pixels - 1;
						if (middle->next) {
							if (pos > middle->next->position) pos = middle->next->position;
						}
/*						if (any->next) {
							if (pos > any->next->position) pos = any->next->position;
						}
*/					} else {
						if (pos < 0) pos = 0;
						if (middle->prev) {
							if (pos < middle->prev->position) pos = middle->prev->position;
						}
/*						if (any->prev) {
							if (pos < any->prev->position) pos = any->prev->position;
						}
*/					}
					temp.position = pos;
					if (left) right = &temp;
					else left = &temp;
					drawboth = TRUE;
				}
			} else if (left->position == middle->position || right->position == middle->position) {
				/* recht stuk */
				/* klein hoekje, met een van de twee op afstand 2 (ander is toch op afstand 0) ? */
				
				if (abs(left->position - right->position) == 2) drawboth = TRUE;
			} else if (left->position < middle->position && right->position > middle->position){
				/* trap 1 */
				drawboth = TRUE;
			} else if (left->position > middle->position && right->position < middle->position){
				/* trap 2 */
				drawboth = TRUE;
			} else {
				/* piek */
				drawboth = TRUE;
			}
			
			if (drawboth) {
				filterdraw(irect, crect - nextline, left->position, middle->position, step);
				filterdraw(irect, crect + nextline, right->position, middle->position, step);
			}

			middle = middle->next;
		}
	}
}


void IMB_antialias(struct ImBuf * ibuf)
{
	struct ImBuf * cbuf;
	ListBase * listarray;
	
	if (ibuf == 0) return;
	cbuf = IMB_dupImBuf(ibuf);
	
	anti_a = (anti_mask >> 24) & 0xff;
	anti_b = (anti_mask >> 16) & 0xff;
	anti_g = (anti_mask >>  8) & 0xff;
	anti_r = (anti_mask >>  0) & 0xff;
	
	listarray = scanimage(cbuf, 'h');
	if (listarray) {
		filterimage(ibuf, cbuf, listarray, 'h');
		anti_free_listarray(ibuf->y, listarray);
		
		listarray = scanimage(cbuf, 'v');
		if (listarray) {
			filterimage(ibuf, cbuf, listarray, 'v');
			anti_free_listarray(ibuf->x, listarray);
		}
	}
			
	IMB_freeImBuf(cbuf);
}


/* intelligente scaling */

static void _intel_scale(struct ImBuf * ibuf, ListBase * listarray, int dir)
{
	int step, lines, nextline, x, y, col;
	unsigned int * irect, * trect;
	int start, end;
	Edge * left, * right;
	struct ImBuf * tbuf;
	
	switch (dir) {
	case 'h':
		step = 1; nextline = ibuf->x;
		lines = ibuf->y;
		tbuf = IMB_double_fast_y(ibuf);
		break;
	case 'v':
		step = 2 * ibuf->x; nextline = 1;
		lines = ibuf->x;
		tbuf = IMB_double_fast_x(ibuf);
		break;
	default:
		return;
	}
	
	imb_freerectImBuf(ibuf);
	ibuf->rect = tbuf->rect;
	ibuf->mall |= IB_rect;
	
	
	ibuf->x = tbuf->x;
	ibuf->y = tbuf->y;
	tbuf->rect = 0;
	IMB_freeImBuf(tbuf);
	
	for (y = 0; y < lines - 2; y++){
		irect = ibuf->rect;
		irect += ((2 * y) + 1) * nextline;
		
		left = listarray[y].first;
		while (left) {
			right = findmatch(listarray[y + 1].first, left);
			if (right) {
				if (left->col2 == right->col2) {
					if (left->next && right->next) {
						if (left->next->position >= right->position) {
							start = ((left->position + right->position) >> 1);
							end = ((left->next->position + right->next->position) >> 1);
							col = left->col2;
							trect = irect + (start * step);
							for (x = start; x < end; x++) {
								*trect = col;
								trect += step;
							}
						}
					}
				}

				if (left->col1 == right->col1) {
					if (left->prev && right->prev) {
						if (left->prev->position <= right->position) {
							end = ((left->position + right->position) >> 1);
							start = ((left->prev->position + right->prev->position) >> 1);
							col = left->col1;
							trect = irect + (start * step);
							for (x = start; x < end; x++) {
								*trect = col;
								trect += step;
							}
						}
					}
				}

			}
			left = left->next;
		}
	}
}


void IMB_clever_double(struct ImBuf * ibuf)
{
	ListBase * listarray, * curlist;
	Edge * new;
	int size;
	int i;
	
	if (ibuf == 0) return;
	
	size = ibuf->x;
	listarray = scanimage(ibuf, 'v');
	if (listarray) {
		for (i = 0; i < size; i++) {
			curlist = listarray + i;
			new = (Edge*)MEM_callocN(sizeof(Edge),"Edge");
			new->col2 = ibuf->rect[i]; /* bovenste pixel */
			new->col1 = new->col2 - 1;
			BLI_addhead(curlist, new);
			new = (Edge*)MEM_callocN(sizeof(Edge),"Edge");
			new->position = ibuf->y - 1;
			new->col1 = ibuf->rect[i + ((ibuf->y -1) * ibuf->x)]; /* onderste pixel */
			new->col2 = new->col1 - 1;
			BLI_addtail(curlist, new);
		}
		_intel_scale(ibuf, listarray, 'v');
		anti_free_listarray(size, listarray);

		size = ibuf->y;
		listarray = scanimage(ibuf, 'h');
		if (listarray) {
			for (i = 0; i < size; i++) {
				curlist = listarray + i;
				new =  (Edge*)MEM_callocN(sizeof(Edge),"Edge");
				new->col2 = ibuf->rect[i * ibuf->x]; /* linkse pixel */
				new->col1 = new->col2 - 1;
				BLI_addhead(curlist, new);
				new =  (Edge*)MEM_callocN(sizeof(Edge),"Edge");
				new->position = ibuf->x - 1;
				new->col1 = ibuf->rect[((i + 1) * ibuf->x) - 1]; /* rechtse pixel */
				new->col2 = new->col1 - 1;
				BLI_addtail(curlist, new);
			}
			_intel_scale(ibuf, listarray, 'h');
			anti_free_listarray(size, listarray);
		}
	}
}