#include <stdio.h>
#include <stdlib.h>
#ifdef _PSP
#include<pspgu.h>
#include<pspgum.h>
#endif
#include "vert.h"

unsigned nextId;
Octtree *createOcttree(Vertex3DCNP *vert,int vertCount,int *octant,int id,float width,float center[3])
{
	int i;
	int octVertCount=0;
	int octPos=0;
	int bigPoly=0;
	Vertex3DCNP *octVert=0;

	printf("Creating octtree (vert count=%d)\n",vertCount);	
	fflush(stdout);
	for(i=0;i<vertCount;i+=3) {
		// Completely inside the octant
		if(octant[i]==id && octant[i+1]==id && octant[i+2]==id) octVertCount+=3;
	}
	//printf("Creating octtree (octVertCount=%d)\n",octVertCount);
	//printf("id=%d; octant={%d,%d,%d,%d, ... }\n",id,octant[0],octant[1],octant[2],octant[3]);
	if(octVertCount==0) return 0;
	Octtree *tree=calloc(sizeof(Octtree),1);
	if(!tree) return 0;
	tree->center[0]=center[0];
	tree->center[1]=center[1];
	tree->center[2]=center[2];
	tree->width=width;
	tree->descendantVerts=octVertCount;	
	// we're under max poly or over max depth.
	if(octVertCount<MAXVERTPEROCTANT || id>=(1<<27)) {
		printf("Leaf node with %d verts\n",octVertCount);
		fflush(stdout);
		tree->descendantVerts=0;
		octVert=calloc(sizeof( Vertex3DCNP ), octVertCount);
		for(i=0;i<vertCount;i+=3) {	// Copy ours over.
			if(octant[i]==id && octant[i+1]==id && octant[i+2]==id) {
				octVert[octPos++]=vert[i];
				octVert[octPos++]=vert[i+1];
				octVert[octPos++]=vert[i+2];
			}
		}
		tree->vert=octVert;
		tree->vertCount=octVertCount;
		
		return tree;
	}
	// classify each child as a octant:
	int childId=nextId;
	nextId+=8;
	for(i=0;i<vertCount;i+=3) {
		if(octant[i]==id && octant[i+1]==id && octant[i+2]==id) {
			// reclassify as a child id.
			octant[i]=childId+(vert[i].x<center[0]?0:4)+(vert[i].y<center[1]?0:2)+(vert[i].z<center[2]?0:1);
			octant[i+1]=childId+(vert[i+1].x<center[0]?0:4)+(vert[i+1].y<center[1]?0:2)+(vert[i+1].z<center[2]?0:1);
			octant[i+2]=childId+(vert[i+2].x<center[0]?0:4)+(vert[i+2].y<center[1]?0:2)+(vert[i+2].z<center[2]?0:1);
			if(octant[i]!=octant[i+1] || octant[i]!=octant[i+2]) {
				bigPoly++;
			}
		}
	}
	// Keep left over polys.
	if(bigPoly>0) {
		octVert=calloc(sizeof(Vertex3DCNP),bigPoly*3);
		octVertCount=bigPoly*3;
		tree->vert=octVert;
		tree->vertCount=octVertCount;
		octPos=0;
		//printf("Grab big poly %d (%.2f wide)\n",bigPoly,width);
		for(i=0;i<vertCount;i+=3) {
			if(octant[i]>=childId && octant[i]<childId+8) {
				if(octant[i]!=octant[i+1] || octant[i]!=octant[i+2]) {
					if(octPos==octVertCount) {
						printf("big poly overflow\n");
						break;
					}
					octVert[octPos++]=vert[i];
					octVert[octPos++]=vert[i+1];
					octVert[octPos++]=vert[i+2];
				}
			}
		}
		//printf("octPos=%d (%d poly) [%d goal]\n",octPos,octPos/3,octVertCount);
	}
	tree->descendantVerts-=bigPoly*3;
	printf("Tree node with %d verts and %d descendent verts\n",tree->vertCount,tree->descendantVerts);
	fflush(stdout);
	// we should be subdividing the big polys, and classifying them.
#if 0	
	octVert=0;	// eliminate aliasing.
	tree->vert=subdivVerts(tree->vert,&tree->vertCount,250);
#endif
	// Finally form an octtree with child nodes.
	for(i=0;i<8;i++) {
		float newcenter[3];
		newcenter[0]=center[0]+(i&4?width/4:-width/4);
		newcenter[1]=center[1]+(i&2?width/4:-width/4);
		newcenter[2]=center[2]+(i&1?width/4:-width/4);
		tree->child[i]=createOcttree(vert,vertCount,octant,childId+i,width/2,newcenter);
		if(tree->child[i]) tree->descendants+=1+tree->child[i]->descendants;
	}
	return tree;
}

void optimizeItem(struct Item *item)
{
	// Optimize the item, by placing it in an octtree and cutting large polys into small polys.
	int *octant=malloc(sizeof(int)*item->polyCount);
	float width;
	float center[3];
	int i;
	float min[3],max[3];
	
	if(item->polyCount<1) return;	// Nothing to optimize :-)

	min[0]=max[0]=item->vert[0].x;
	min[1]=max[1]=item->vert[0].y;
	min[2]=max[2]=item->vert[0].z;
	// Calculate the width and center
	Vertex3DCNP *vert=item->vert;
	for(i=1;i<item->polyCount;i++) {
		if(vert[i].x<min[0]) min[0]=vert[i].x;
		if(vert[i].x<min[1]) min[1]=vert[i].y;
		if(vert[i].x<min[2]) min[2]=vert[i].z;
		if(vert[i].x>max[0]) max[0]=vert[i].x;
		if(vert[i].x>max[1]) max[1]=vert[i].y;
		if(vert[i].x>max[2]) max[2]=vert[i].z;
	}
	width=max[0]-min[0];
	if(width<max[1]-min[1]) width=max[1]-min[1];
	if(width<max[2]-min[2]) width=max[2]-min[2];
	center[0]=(min[0]+max[0])/2;
	center[1]=(min[1]+max[1])/2;
	center[2]=(min[2]+max[2])/2;
	printf("Optimizing with Verts: %d; Center: %.2f,%.2f,%.2f width %.2f\n",item->polyCount,center[0],center[1],center[2],width);

	for(i=0;i<item->polyCount;i++) {
		octant[i]=1;
	}
	nextId=2;
	Octtree *oct=createOcttree(item->vert,item->polyCount,octant,1,width,center);
	if(oct) {
		printf("Made an octtree\n");
		free(item->vert);
		item->vert=0;
		item->vertCount=0;
		item->poly=0;
		item->polyCount=0;
		item->oct=oct;
	}
}

void freeOcttree(Octtree *octtree)
{
	if(octtree==0) return;
	printf("Freeing oct (width=%.2f) with %d verts and descendants: %d (%d verts)\n",octtree->width,octtree->vertCount,octtree->descendants,octtree->descendantVerts);

	int i;
	for(i=0;i<8;i++) {
		freeOcttree(octtree->child[i]);
		octtree->child[i]=0;
	}
	if(octtree->vert) free(octtree->vert);
	octtree->vert=0;
	free(octtree);
}

void drawOcttree(Octtree *octtree)
{
	if(octtree==0) return;
	
	// Could do frustrum culling right here.	
	if(octtree->vertCount>0) {
#ifdef _PSP
			sceGumUpdateMatrix();	// We only need to do this when we actually change the matrix.
			Vertex3DP *bbox=sceGuGetMemory(sizeof(Vertex3DP)*8);
#if 1
			int i;
			for(i=0;i<8;i++) {
				bbox[i].x=octtree->center[0]+octtree->width*(i&4?-1:1);
				bbox[i].y=octtree->center[1]+octtree->width*(i&2?-1:1);
				bbox[i].z=octtree->center[2]+octtree->width*(i&1?-1:1);
			}
			sceGuBeginObject(GU_VERTEX_32BITF,8,0,bbox);
#endif
			sceGumDrawArray(GU_TRIANGLES,GU_VERTEX_32BITF|GU_NORMAL_32BITF|GU_COLOR_8888|GU_TRANSFORM_3D,octtree->vertCount,0,octtree->vert);
#ifdef _PSP
			sceGuEndObject();
#endif
#else
		printf("#Octtree %d verts (width=%.2f)\n",octtree->vertCount,octtree->width);
		int i;
		for(i=0;i<octtree->vertCount;i++) {
			printf("v %.4f %.4f %.4f\n",octtree->vert[i].x,octtree->vert[i].y,octtree->vert[i].z);
			if((i%3)==2) printf("f %d %d %d\n",i-1,i-0,i+1);
		}
#endif
	}
	if(octtree->descendants>0) {
		//printf(">>Processing %d descendants with %d verts\n",octtree->descendants,octtree->descendantVerts);
	}
	int i;
	for(i=0;i<8;i++) {
		drawOcttree(octtree->child[i]);
	}
}
