/* Bob */
#include <string.h>
#include <math.h>
#include <aldumb.h>
#include "main.h"
#include "options.h"
#include "zcontrol.h"
#include "draw.h"
#include "tilemap.h"
#include "texture.h"
#include "level.h"
#include "log.h"

/* NOTES FOR LATER:

   This file must be usable by the menu as well as the game.
   See preview.h.

   The polygons should be drawn using texturing_type[texturing_id] from
   options.h, which is a POLYTYPE_* constant.

   Exceptions:

   When ripples are turned off, ripple tiles should be drawn with
   POLYTYPE_FLAT. Walls surrounding ripple tiles are also drawn with
   POLYTYPE_FLAT.

   Sprites, however, should always be
   drawn with POLYTYPE_ATEX_MASK.


   update_joystick() is then responsible for reading the joystick. It need
   not be locked. It must be called as often as possible within reason. To
   that end, it will be called at several points during the draw_level()
   function. It will also be called once at the beginning of
   update_game() in game.h, to make sure the joysticks are up to date before
   we try to read their FIFOs.
*/


#define MIN_Z 0.1


#define BLOOD_FACTOR  0.5
#define DAMAGE_FACTOR 0.5


static BITMAP *ripple_texture;


static void sort_polygons();
void clean_up_draw();


typedef struct VTX {
	float x, y, z;
} VTX;


typedef struct POLYGON {

    SPRITE *sprite;

    unsigned char i, j, k, clip;

	float val;
} POLYGON;

POLYGON *plist = NULL; /* Pool of all polygons */
POLYGON **draw_list = NULL; /* Pointers to polygons */
int num_polys = 0;

VTX *vlist = NULL; /* Pool of vertices */


/* vlist layout:

   The vlist array may be considered like a linearly mapped 2D array, sized
   map->w+2 x map->h+2. Each element consists of four vertices. Its
   components may be accessed as follows:

   vlist[((i + 1) + (j + 1) * (map->w + 2)) * 4 + n]

   where n ranges from 0 to 3. The values of n represent the corners of the
   tile, arranged as follows:

   03
   12

   The above equation accommodates values of i,j from -1 to map->w,h
   inclusive. This means we can store some of the vertices belonging to the
   tops of the walls, as if of tiles at the top, outside the level; but we
   only store the vertices belonging to the wall, not those on the other
   side.
*/


#define MAX_MAP_W 64
#define MAX_MAP_H 64

#define VLIST_SIZE (17424)
#define PLIST_SIZE (15000)

#define MAX_DIST  12000

int max_used_polys = 0, max_used_verts = 0;

const int wall_y_offset[] = {0, -1, 0, 1, 0};
const int wall_x_offset[] = {0,  0,-1, 0, 1};


/* Get a pointer to the vertex. (i, j) is the tile coord on the map
 * (as in poly->i,j), k is the wall number (0->4), l is the vertex
 * number (0->3) 
 */
#define draw_get_vert(map, v, i, j, k, l) { \
	if (!k) \
		*v = &vlist[(i + 1 + (j + 1) * (map->w + 2)) * 4 + l]; \
	else { \
		unsigned char f = (l & 1) ^ ((l & 2) >> 1); \
		int i2 = i + 1 - ((f & (k == 2))) + ((f & (k == 4))); \
		int j2 = j + 1 - ((f & (k == 1))) + ((f & (k == 3))); \
		*v = &vlist[(i2 + j2 * (map->w + 2)) * 4 + ((2 - l + k) & 3)]; \
	} \
}

void draw_polygons(BITMAP *dest, TILEMAP *map, float zc, float cth) {
	int i;
	unsigned char j, l;

	V3D_f v[32];
	V3D_f vout[32];
	V3D_f vtmp[32];

	AL_CONST V3D_f *v2[32];
	V3D_f *v2out[32];
	V3D_f *v2tmp[32];
	int out[32];

    int mode;
    BITMAP *texture;

	/* Make V3D pointers */
	for (i = 0; i < 32; i++) {
		v2[i] = &v[i];
		v2out[i] = &vout[i];
		v2tmp[i] = &vtmp[i];
	}

	for (i = 0; i < num_polys; i++) {
		POLYGON *poly = draw_list[i];

		if (poly->sprite) {
			SPRITE_DRAW_PROC proc = sprite_draw_proc[poly->sprite->type];
			(*proc)(dest, poly->sprite, cth);
		}
		else {
			TILE *tile = &map->tile[poly->j][poly->i];
			int nv;
			VTX *vtx;

            int outer_wall = poly->k & 128;
            int texture_int = outer_wall ? map->border_texture : tile->texture;
            poly->k &= ~128;

			/* Covnert VTX->V3D */
			for (j = 0; j < 4; j++) {
				draw_get_vert(map, &vtx, poly->i, poly->j, poly->k, j);
				v[j].x = vtx->x;
				v[j].y = vtx->y;
				v[j].z = vtx->z;
			}

			/* Fill in texture map values */
            {
                float vlo, vhi;
                /* 'hi' and 'lo' refer to the position on the texture
                   bitmap. This means numerically that vlo > vhi.
                */

                if (outer_wall) {
                    /* br tr tl bl */
			        v[0].u = 0.9999; v[1].u = 0.9999;
			        v[2].u = 0.0001; v[3].u = 0.0001;
                    /* In this case, vhi and vlo are swapped. */
                    vhi = -0.0001 - tile->z;
                    vlo = -zc;
                } else {
			        v[0].u = 0.0001; v[1].u = 0.0001;
			        v[2].u = 0.9999; v[3].u = 0.9999;
                    if (poly->k) {
                        vhi = 0.0001;
                        vlo = tile->z -
                              map->tile[poly->j + wall_y_offset[poly->k]]
                                       [poly->i + wall_x_offset[poly->k]].z
                              - 0.0001;
                    } else {
                        vhi = 0.0001;
                        vlo = 0.9999;
                    }
                }
                v[0].v = vhi; v[1].v = vlo;
                v[2].v = vlo; v[3].v = vhi;
            }


			texture = NULL;

			/* Get texture */
			if (poly->k == 0 && tile->ripples) {
				texture = ripple_texture;
			} else if (tile->type == TILE_TYPE_LIQUID && !outer_wall) {
				texture = NULL;
			} else if (

						// Temporary, just to make levels look nicer!
						texture_int = MIN(texture_int, N_TEXTURES-1),

						texture_int < N_TEXTURES) {
                int blood = (int)tile->blood.s[poly->k] * BLOOD_FACTOR;
                int damage = (int)tile->damage.s[poly->k] * DAMAGE_FACTOR;
				texture = block_info[texture_int][poly->k ? 1 : 0]
				                    [MIN(blood, N_BLOOD_LEVELS - 1)]
				                    [MIN(damage, N_DAMAGE_LEVELS - 1)];
			}

			/* Get polygon mode */
			mode = texture ? texturing_type[texturing_id] : POLYTYPE_FLAT;

			/* Clip */
			if (poly->clip) {
				nv = clip3d_f(mode, MIN_Z, 0, 4, v2, v2out, v2tmp, out);
			}
			else {
				nv = 4;
				memcpy(vout, v, 4 * sizeof(V3D_f));
			}

			/* If nothing to do */
			if (nv < 3)
				continue;
			
			/* Project vertices */
			for (j = 0; j < nv; j++)
				persp_project_f(vout[j].x, vout[j].y, vout[j].z, &vout[j].x, &vout[j].y);


            if (texture) {
				/* Generate ripples */
				if (poly->k == 0 && tile->ripples) {
					int x = poly->i;
					int y = poly->j;

					draw_ripples(&water_colours, texture, ripple_quality - 1,
						map->ripple_info,
						tile->ripples,
						(x > 0)        ? map->tile[y][x-1].ripples : 0,
						(x < map->w-1) ? map->tile[y][x+1].ripples : 0,
						(y > 0)        ? map->tile[y-1][x].ripples : 0,
						(y < map->h-1) ? map->tile[y+1][x].ripples : 0,
						(x > 0        && y > 0)        ? map->tile[y-1][x-1].ripples : 0,
						(x < map->w-1 && y > 0)        ? map->tile[y-1][x+1].ripples : 0,
						(x > 0        && y < map->h-1) ? map->tile[y+1][x-1].ripples : 0,
						(x < map->w-1 && y < map->h-1) ? map->tile[y+1][x+1].ripples : 0);
				}
				for (l = 0; l < nv; l++) {
					vout[l].u *= texture->w;
					vout[l].v *= texture->h;
				}
            } 
			else
                vout[0].c = (*tile_colour_proc[poly->k ? 1 : 0][tile->type])
                            (map, tile, outer_wall ? -1 : poly->i, poly->j);

			polygon3d_f(dest, mode, texture, nv, v2out);
        }
	}
}


float get_sprite_hash(SPRITE *sprite, float xc, float yc) {

	float ret = sprite->zview * 3 / 2 - sprite->r * 2;
	float min;

	min = MIN(SQDIST2(sprite->x-xc, sprite->y-yc), SQDIST2(sprite->x-xc - 0.5, sprite->y-yc - 0.5));
	min = MIN(min, SQDIST2(sprite->x-xc, sprite->y-yc - 0.5));
	min = MIN(min, SQDIST2(sprite->x-xc - 0.5, sprite->y-yc));
	min = MIN(min, SQDIST2(sprite->x-xc, sprite->y-yc + 0.5));
	min = MIN(min, SQDIST2(sprite->x-xc + 0.5, sprite->y-yc));
	min = MIN(min, SQDIST2(sprite->x-xc + 0.5, sprite->y-yc + 0.5));
	ret += min * 2; 
	
	return ret;
}


void transform_polygons(BITMAP *dest, TILEMAP *map, SPRITE *sprite, MATRIX_f *cam, int xc, int yc, float zc, float cth) {

	VTX *v;
	TILE *tile, *tile2;
	float z;
	unsigned int surfaces = 0;
	unsigned char i, j, k, l;

	(void)dest;
	(void)cth;

	if (!map)
		goto Sprites;

	for (j = 0; j < map->h; j++) {
		for (i = 0; i < map->w; i++) {

			z = map->tile[j][i].z;
			v = &vlist[(i + 1 + (j + 1) * (map->w + 2)) * 4];

			/* Calc vertices of tile top */
			apply_matrix_f(cam, i,     j,     z, &v[0].x, &v[0].y, &v[0].z);
			apply_matrix_f(cam, i,     j + 1, z, &v[1].x, &v[1].y, &v[1].z);
			apply_matrix_f(cam, i + 1, j + 1, z, &v[2].x, &v[2].y, &v[2].z);
			apply_matrix_f(cam, i + 1, j,     z, &v[3].x, &v[3].y, &v[3].z);
		}
	}

	/* Fill in vertices for outer walls */
	for (j = 0; j < map->h; j++) {
		/* Left wall: i = -1 */
		v = &vlist[((j + 1) * (map->w + 2)) * 4];
		apply_matrix_f(cam, 0,     j,     zc, &v[3].x, &v[3].y, &v[3].z);
		apply_matrix_f(cam, 0, j + 1,     zc, &v[2].x, &v[2].y, &v[2].z);

		/* Right wall: i = map->w */
		v = &vlist[(map->w + 1 + (j + 1) * (map->w + 2)) * 4];
		apply_matrix_f(cam, map->w, j,     zc, &v[0].x, &v[0].y, &v[0].z);
		apply_matrix_f(cam, map->w, j + 1, zc, &v[1].x, &v[1].y, &v[1].z);
	}
	for (i = 0; i < map->w; i++) {
		/* Top wall: j = -1 */
		v = &vlist[(i + 1) * 4];
		apply_matrix_f(cam, i + 1,     0,     zc, &v[2].x, &v[2].y, &v[2].z);
		apply_matrix_f(cam, i,         0,     zc, &v[1].x, &v[1].y, &v[1].z);

		/* Bottom wall: j = map->h */
		v = &vlist[(i + 1 + (map->h + 1) * (map->w + 2)) * 4];
		apply_matrix_f(cam, i + 1, map->h, zc, &v[3].x, &v[3].y, &v[3].z);
		apply_matrix_f(cam, i,     map->h, zc, &v[0].x, &v[0].y, &v[0].z);
	}

	for (j = 0; j < map->h; j++) {
		for (i = 0; i < map->w; i++) {

			tile = &(map->tile[j][i]);
			surfaces = 0;

			/* Find out which walls we need to draw */
			if (tile->z < zc)
				surfaces |= 1;
			/* Left wall */
            if ((i > 0)  &&  (i > xc)  &&  ((tile2 = &map->tile[j][i-1])->z < tile->z))
				surfaces |= 4;
            else if (i == 0  &&  i <= xc)
				surfaces |= 4 | 64;
			/* Right wall */
			if ((i < (map->w - 1))  &&  (i < xc)  &&  ((tile2 = &map->tile[j][i+1])->z < tile->z))
				surfaces |= 16;
			else if (i == map->w - 1  &&  i >= xc)
				surfaces |= 16 | 256;
			/* Top wall */
            if ((j > 0)  &&  (j > yc)  &&  ((tile2 = &map->tile[j-1][i])->z < tile->z))
				surfaces |= 2;
			else if (j == 0  &&  j <= yc)
				surfaces |= 2 | 32;
			/* Bottom wall */
			if ((j < (map->h - 1))  &&  (j < yc)  &&  ((tile2 = &map->tile[j+1][i])->z < tile->z))
				surfaces |= 8;
			else if (j == map->h - 1  &&  j >= yc)
				surfaces |= 8 | 128;

			/* Create polygons */
			for (k = 0; k < 5; k++) {
				POLYGON *poly = plist + num_polys;
				float total = 0.0, max = 0.0, min = 99999999;
				char flags[4];

				if (!(surfaces & (1 << k)))
					continue;

				/* Build polygon structure */
                poly->i = i;
                poly->j = j;
                poly->k = k;

                /* Label outer walls to be treated differently when texturing. */
				if (k && ((surfaces >> 4) & (1 << k)))
                    poly->k |= 128;

				/* simple clip */
				for (l = 0; l < 4; l++) {
					VTX *vtx;
					flags[l] = 0;

					draw_get_vert(map, &vtx, i, j, k, l);

					/* set flags if this vertex is off the edge of the screen */
					if (vtx->x < -vtx->z)
						flags[l] |= 1;
					if (vtx->x > vtx->z)
						flags[l] |= 2;
					if (vtx->y < -vtx->z)
						flags[l] |= 4;
					if (vtx->y > vtx->z)
						flags[l] |= 8;
					if (vtx->z < MIN_Z)
						flags[l] |= 16;

					max = MAX(max, vtx->z);
					min = MIN(min, vtx->z);
					total += vtx->z;
				}
				/* quit if all vertices are off the same edge of the screen */
				if (flags[0] & flags[1] & flags[2] & flags[3])
					continue;

				poly->clip = flags[0] | flags[1] | flags[2] | flags[3];

				if (num_polys >= PLIST_SIZE - 2) {
					LOG(ERROR "Draw::draw_level: Over max polys have been drawn! aborting draw!\n");
					return;
				}

				poly->val = total / 8 + max + SQDIST2(i-xc + .5, j-yc + .5) * 2;
				poly->sprite = NULL;

				/* HACK: to get the outer walls to be drawn first */
				if (k && ((surfaces >> 4) & (1 << k)))
					poly->val = 10000;

				/* Add the polygon for sorting */
				draw_list[num_polys] = poly;
				num_polys++;
			}
		}
	}

Sprites:

	/* Build sprite polygon list */
	while (sprite) {

		VTX v2;
		SPRITE_DRAW_PROC proc = sprite_draw_proc[sprite->type];
		POLYGON *p = plist + num_polys;

		if (num_polys >= PLIST_SIZE - 2) {
			LOG(ERROR "Draw::draw_level+sprite: Over max polys have been drawn! aborting draw!\n");
			return;
		}

		if (!proc) {
			sprite = sprite->next;
			continue;
		}

		/* Transform the center and edge of the sprite */
		apply_matrix_f(cam, sprite->x, sprite->y, sprite->z, &v2.x, &v2.y, &v2.z);
		apply_matrix_f(cam, sprite->x, sprite->y, sprite->z, &v2.x, &v2.y, &sprite->zview);

        if (sprite->zview >= MIN_Z) {

		    persp_project_f(v2.x, v2.y, sprite->zview, &sprite->xview, &sprite->yview);

		    p->val = get_sprite_hash(sprite, xc, yc);

		    p->sprite = sprite;

		    persp_project_f(v2.x - sprite->r, v2.y - sprite->r*VIEW_ASPECT, sprite->zview, &v2.x, &v2.y);
		    sprite->xrad = sprite->xview - v2.x;
		    sprite->yrad = sprite->yview - v2.y;

		    draw_list[num_polys] = p;
		    num_polys++;
        }

		sprite = sprite->next;
	}
	return;
}


void draw_level(BITMAP *dest, TILEMAP *map, SPRITE *sprite, MATRIX_f *cam,
                int xc, int yc, float zc, float cth) {

#ifndef ZIG_GL
	// I don't trust Allegro's polygon routines. They overrun the clipping
	// rectangle.
	dest->cl++; dest->cr--;
	dest->ct++; dest->cb--;

	num_polys = 0;

	/* Build structures needed */
	if (!plist) {

		plist = malloc(sizeof(POLYGON) * PLIST_SIZE);
        if (!plist) exit(37);
		LOG("PList size: %i bytes\n", sizeof(POLYGON) * PLIST_SIZE);
		if (!plist) {
			clean_up_draw();
			return;
		}

		draw_list = malloc(sizeof(POLYGON*) * PLIST_SIZE);
        if (!draw_list) exit(37);
		LOG("DList size: %i bytes\n", sizeof(POLYGON*) * PLIST_SIZE);
		if (!draw_list) {
			clean_up_draw();
			return;
		}

		vlist = malloc(sizeof(VTX) * VLIST_SIZE);
        if (!vlist) exit(37);
		LOG("VList size: %i bytes\n", sizeof(VTX) * VLIST_SIZE);
		if (!vlist) {
			clean_up_draw();
			return;
		}
	}

	set_projection_viewport(0, 0, dest->w, dest->h);

	al_poll_duh(adp);
    update_joystick();

	transform_polygons(dest, map, sprite, cam, xc, yc, zc, cth);

	al_poll_duh(adp);
    update_joystick();

	/* Sort polygons */
	sort_polygons();

	draw_polygons(dest, map, zc, cth);

	al_poll_duh(adp);
    update_joystick();

	// I still don't trust Allegro's polygon routines.
	dest->cl--; dest->cr++;
	dest->ct--; dest->cb++;
	rect(dest, dest->cl, dest->ct, dest->cr-1, dest->cb-1, 0);
#else
#endif

	return;
}




#define SORT_DOWN(pos, len) for (k = pos;;) { \
		int right, left, max; \
		left = 2 * k + 1;     \
		right = left + 1;     \
		if (left >= len)      \
			break;            \
		else if ((right >= len) || (draw_list[left]->val < draw_list[right]->val)) \
			max = left;       \
		else                  \
			max = right;      \
		if (draw_list[k]->val < draw_list[max]->val) \
			break;            \
		temp = draw_list[k];  \
		draw_list[k] = draw_list[max]; \
		draw_list[max] = temp; \
		k = max;              \
	}

/* Sorts the polygon list using Heap sort */
static void sort_polygons() {

	POLYGON *temp;
	int i, k;

	/* Builds a heap out of the polygon list */
	for (i = num_polys / 2;  i >= 0; i--)
		SORT_DOWN(i, num_polys);

	for (i = num_polys - 1; i > 0; i--) {
		temp = draw_list[i];
		draw_list[i] = draw_list[0];
		draw_list[0] = temp;

		SORT_DOWN(0, i);
	}

	return;
}



void initialise_draw(void) {
 int size = (RIPPLE_D >> 1) << ripple_quality;
 ripple_texture = create_bitmap(size, size);
 if (!ripple_texture) exit(37);
}



void shut_down_draw(void) {
 destroy_bitmap(ripple_texture);
}



/* Use this to free memory used by the draw functions */
void clean_up_draw(void) {

	if (plist)
		free(plist);
	plist = NULL;

	if (draw_list)
		free(draw_list);
	draw_list = NULL;

	if (vlist)
		free(vlist);
	vlist = NULL;

	return;
}
