#include "TerrainGrid.h"
#include "tweak/main.txt"
#include "globals.h"
#include <d3dx9.h>
#include <cassert>

#include "intrin.h"

void RenderLoading( int iPercent );

static const unsigned short edgeTable[256] =
{
	0x000, 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c,
	0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00,
	0x190, 0x99 , 0x393, 0x29a, 0x596, 0x49f, 0x795, 0x69c,
	0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90,
	0x230, 0x339, 0x33 , 0x13a, 0x636, 0x73f, 0x435, 0x53c,
	0xa3c, 0xb35, 0x83f, 0x936, 0xe3a, 0xf33, 0xc39, 0xd30,
	0x3a0, 0x2a9, 0x1a3, 0xaa , 0x7a6, 0x6af, 0x5a5, 0x4ac,
	0xbac, 0xaa5, 0x9af, 0x8a6, 0xfaa, 0xea3, 0xda9, 0xca0,
	0x460, 0x569, 0x663, 0x76a, 0x66 , 0x16f, 0x265, 0x36c,
	0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60,
	0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0xff , 0x3f5, 0x2fc,
	0xdfc, 0xcf5, 0xfff, 0xef6, 0x9fa, 0x8f3, 0xbf9, 0xaf0,
	0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x55 , 0x15c,
	0xe5c, 0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53, 0x859, 0x950,
	0x7c0, 0x6c9, 0x5c3, 0x4ca, 0x3c6, 0x2cf, 0x1c5, 0xcc ,
	0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0,
	0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc,
	0xcc , 0x1c5, 0x2cf, 0x3c6, 0x4ca, 0x5c3, 0x6c9, 0x7c0,
	0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f, 0xf55, 0xe5c,
	0x15c, 0x55 , 0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650,
	0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6, 0xfff, 0xcf5, 0xdfc,
	0x2fc, 0x3f5, 0xff , 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0,
	0xb60, 0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65, 0xc6c,
	0x36c, 0x265, 0x16f, 0x66 , 0x76a, 0x663, 0x569, 0x460,
	0xca0, 0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac,
	0x4ac, 0x5a5, 0x6af, 0x7a6, 0xaa , 0x1a3, 0x2a9, 0x3a0,
	0xd30, 0xc39, 0xf33, 0xe3a, 0x936, 0x83f, 0xb35, 0xa3c,
	0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x33 , 0x339, 0x230,
	0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f, 0x895, 0x99c,
	0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x99 , 0x190,
	0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c,
	0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x000
};

static const char triTable[256][16] =
{
	{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{0, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{0, 8, 3, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{9, 2, 10, 0, 2, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{2, 8, 3, 2, 10, 8, 10, 9, 8, -1, -1, -1, -1, -1, -1, -1},
	{3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{0, 11, 2, 8, 11, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{1, 9, 0, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{1, 11, 2, 1, 9, 11, 9, 8, 11, -1, -1, -1, -1, -1, -1, -1},
	{3, 10, 1, 11, 10, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{0, 10, 1, 0, 8, 10, 8, 11, 10, -1, -1, -1, -1, -1, -1, -1},
	{3, 9, 0, 3, 11, 9, 11, 10, 9, -1, -1, -1, -1, -1, -1, -1},
	{9, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{4, 3, 0, 7, 3, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{0, 1, 9, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{4, 1, 9, 4, 7, 1, 7, 3, 1, -1, -1, -1, -1, -1, -1, -1},
	{1, 2, 10, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{3, 4, 7, 3, 0, 4, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1},
	{9, 2, 10, 9, 0, 2, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1},
	{2, 10, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4, -1, -1, -1, -1},
	{8, 4, 7, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{11, 4, 7, 11, 2, 4, 2, 0, 4, -1, -1, -1, -1, -1, -1, -1},
	{9, 0, 1, 8, 4, 7, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1},
	{4, 7, 11, 9, 4, 11, 9, 11, 2, 9, 2, 1, -1, -1, -1, -1},
	{3, 10, 1, 3, 11, 10, 7, 8, 4, -1, -1, -1, -1, -1, -1, -1},
	{1, 11, 10, 1, 4, 11, 1, 0, 4, 7, 11, 4, -1, -1, -1, -1},
	{4, 7, 8, 9, 0, 11, 9, 11, 10, 11, 0, 3, -1, -1, -1, -1},
	{4, 7, 11, 4, 11, 9, 9, 11, 10, -1, -1, -1, -1, -1, -1, -1},
	{9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{9, 5, 4, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{0, 5, 4, 1, 5, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{8, 5, 4, 8, 3, 5, 3, 1, 5, -1, -1, -1, -1, -1, -1, -1},
	{1, 2, 10, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{3, 0, 8, 1, 2, 10, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1},
	{5, 2, 10, 5, 4, 2, 4, 0, 2, -1, -1, -1, -1, -1, -1, -1},
	{2, 10, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8, -1, -1, -1, -1},
	{9, 5, 4, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{0, 11, 2, 0, 8, 11, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1},
	{0, 5, 4, 0, 1, 5, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1},
	{2, 1, 5, 2, 5, 8, 2, 8, 11, 4, 8, 5, -1, -1, -1, -1},
	{10, 3, 11, 10, 1, 3, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1},
	{4, 9, 5, 0, 8, 1, 8, 10, 1, 8, 11, 10, -1, -1, -1, -1},
	{5, 4, 0, 5, 0, 11, 5, 11, 10, 11, 0, 3, -1, -1, -1, -1},
	{5, 4, 8, 5, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1},
	{9, 7, 8, 5, 7, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{9, 3, 0, 9, 5, 3, 5, 7, 3, -1, -1, -1, -1, -1, -1, -1},
	{0, 7, 8, 0, 1, 7, 1, 5, 7, -1, -1, -1, -1, -1, -1, -1},
	{1, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{9, 7, 8, 9, 5, 7, 10, 1, 2, -1, -1, -1, -1, -1, -1, -1},
	{10, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3, -1, -1, -1, -1},
	{8, 0, 2, 8, 2, 5, 8, 5, 7, 10, 5, 2, -1, -1, -1, -1},
	{2, 10, 5, 2, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1},
	{7, 9, 5, 7, 8, 9, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1},
	{9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 11, -1, -1, -1, -1},
	{2, 3, 11, 0, 1, 8, 1, 7, 8, 1, 5, 7, -1, -1, -1, -1},
	{11, 2, 1, 11, 1, 7, 7, 1, 5, -1, -1, -1, -1, -1, -1, -1},
	{9, 5, 8, 8, 5, 7, 10, 1, 3, 10, 3, 11, -1, -1, -1, -1},
	{5, 7, 0, 5, 0, 9, 7, 11, 0, 1, 0, 10, 11, 10, 0, -1},
	{11, 10, 0, 11, 0, 3, 10, 5, 0, 8, 0, 7, 5, 7, 0, -1},
	{11, 10, 5, 7, 11, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{0, 8, 3, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{9, 0, 1, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{1, 8, 3, 1, 9, 8, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1},
	{1, 6, 5, 2, 6, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{1, 6, 5, 1, 2, 6, 3, 0, 8, -1, -1, -1, -1, -1, -1, -1},
	{9, 6, 5, 9, 0, 6, 0, 2, 6, -1, -1, -1, -1, -1, -1, -1},
	{5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8, -1, -1, -1, -1},
	{2, 3, 11, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{11, 0, 8, 11, 2, 0, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1},
	{0, 1, 9, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1},
	{5, 10, 6, 1, 9, 2, 9, 11, 2, 9, 8, 11, -1, -1, -1, -1},
	{6, 3, 11, 6, 5, 3, 5, 1, 3, -1, -1, -1, -1, -1, -1, -1},
	{0, 8, 11, 0, 11, 5, 0, 5, 1, 5, 11, 6, -1, -1, -1, -1},
	{3, 11, 6, 0, 3, 6, 0, 6, 5, 0, 5, 9, -1, -1, -1, -1},
	{6, 5, 9, 6, 9, 11, 11, 9, 8, -1, -1, -1, -1, -1, -1, -1},
	{5, 10, 6, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{4, 3, 0, 4, 7, 3, 6, 5, 10, -1, -1, -1, -1, -1, -1, -1},
	{1, 9, 0, 5, 10, 6, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1},
	{10, 6, 5, 1, 9, 7, 1, 7, 3, 7, 9, 4, -1, -1, -1, -1},
	{6, 1, 2, 6, 5, 1, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1},
	{1, 2, 5, 5, 2, 6, 3, 0, 4, 3, 4, 7, -1, -1, -1, -1},
	{8, 4, 7, 9, 0, 5, 0, 6, 5, 0, 2, 6, -1, -1, -1, -1},
	{7, 3, 9, 7, 9, 4, 3, 2, 9, 5, 9, 6, 2, 6, 9, -1},
	{3, 11, 2, 7, 8, 4, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1},
	{5, 10, 6, 4, 7, 2, 4, 2, 0, 2, 7, 11, -1, -1, -1, -1},
	{0, 1, 9, 4, 7, 8, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1},
	{9, 2, 1, 9, 11, 2, 9, 4, 11, 7, 11, 4, 5, 10, 6, -1},
	{8, 4, 7, 3, 11, 5, 3, 5, 1, 5, 11, 6, -1, -1, -1, -1},
	{5, 1, 11, 5, 11, 6, 1, 0, 11, 7, 11, 4, 0, 4, 11, -1},
	{0, 5, 9, 0, 6, 5, 0, 3, 6, 11, 6, 3, 8, 4, 7, -1},
	{6, 5, 9, 6, 9, 11, 4, 7, 9, 7, 11, 9, -1, -1, -1, -1},
	{10, 4, 9, 6, 4, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{4, 10, 6, 4, 9, 10, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1},
	{10, 0, 1, 10, 6, 0, 6, 4, 0, -1, -1, -1, -1, -1, -1, -1},
	{8, 3, 1, 8, 1, 6, 8, 6, 4, 6, 1, 10, -1, -1, -1, -1},
	{1, 4, 9, 1, 2, 4, 2, 6, 4, -1, -1, -1, -1, -1, -1, -1},
	{3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6, 4, -1, -1, -1, -1},
	{0, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{8, 3, 2, 8, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1},
	{10, 4, 9, 10, 6, 4, 11, 2, 3, -1, -1, -1, -1, -1, -1, -1},
	{0, 8, 2, 2, 8, 11, 4, 9, 10, 4, 10, 6, -1, -1, -1, -1},
	{3, 11, 2, 0, 1, 6, 0, 6, 4, 6, 1, 10, -1, -1, -1, -1},
	{6, 4, 1, 6, 1, 10, 4, 8, 1, 2, 1, 11, 8, 11, 1, -1},
	{9, 6, 4, 9, 3, 6, 9, 1, 3, 11, 6, 3, -1, -1, -1, -1},
	{8, 11, 1, 8, 1, 0, 11, 6, 1, 9, 1, 4, 6, 4, 1, -1},
	{3, 11, 6, 3, 6, 0, 0, 6, 4, -1, -1, -1, -1, -1, -1, -1},
	{6, 4, 8, 11, 6, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{7, 10, 6, 7, 8, 10, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1},
	{0, 7, 3, 0, 10, 7, 0, 9, 10, 6, 7, 10, -1, -1, -1, -1},
	{10, 6, 7, 1, 10, 7, 1, 7, 8, 1, 8, 0, -1, -1, -1, -1},
	{10, 6, 7, 10, 7, 1, 1, 7, 3, -1, -1, -1, -1, -1, -1, -1},
	{1, 2, 6, 1, 6, 8, 1, 8, 9, 8, 6, 7, -1, -1, -1, -1},
	{2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3, 9, -1},
	{7, 8, 0, 7, 0, 6, 6, 0, 2, -1, -1, -1, -1, -1, -1, -1},
	{7, 3, 2, 6, 7, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{2, 3, 11, 10, 6, 8, 10, 8, 9, 8, 6, 7, -1, -1, -1, -1},
	{2, 0, 7, 2, 7, 11, 0, 9, 7, 6, 7, 10, 9, 10, 7, -1},
	{1, 8, 0, 1, 7, 8, 1, 10, 7, 6, 7, 10, 2, 3, 11, -1},
	{11, 2, 1, 11, 1, 7, 10, 6, 1, 6, 7, 1, -1, -1, -1, -1},
	{8, 9, 6, 8, 6, 7, 9, 1, 6, 11, 6, 3, 1, 3, 6, -1},
	{0, 9, 1, 11, 6, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{7, 8, 0, 7, 0, 6, 3, 11, 0, 11, 6, 0, -1, -1, -1, -1},
	{7, 11, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{3, 0, 8, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{0, 1, 9, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{8, 1, 9, 8, 3, 1, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1},
	{10, 1, 2, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{1, 2, 10, 3, 0, 8, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1},
	{2, 9, 0, 2, 10, 9, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1},
	{6, 11, 7, 2, 10, 3, 10, 8, 3, 10, 9, 8, -1, -1, -1, -1},
	{7, 2, 3, 6, 2, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{7, 0, 8, 7, 6, 0, 6, 2, 0, -1, -1, -1, -1, -1, -1, -1},
	{2, 7, 6, 2, 3, 7, 0, 1, 9, -1, -1, -1, -1, -1, -1, -1},
	{1, 6, 2, 1, 8, 6, 1, 9, 8, 8, 7, 6, -1, -1, -1, -1},
	{10, 7, 6, 10, 1, 7, 1, 3, 7, -1, -1, -1, -1, -1, -1, -1},
	{10, 7, 6, 1, 7, 10, 1, 8, 7, 1, 0, 8, -1, -1, -1, -1},
	{0, 3, 7, 0, 7, 10, 0, 10, 9, 6, 10, 7, -1, -1, -1, -1},
	{7, 6, 10, 7, 10, 8, 8, 10, 9, -1, -1, -1, -1, -1, -1, -1},
	{6, 8, 4, 11, 8, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{3, 6, 11, 3, 0, 6, 0, 4, 6, -1, -1, -1, -1, -1, -1, -1},
	{8, 6, 11, 8, 4, 6, 9, 0, 1, -1, -1, -1, -1, -1, -1, -1},
	{9, 4, 6, 9, 6, 3, 9, 3, 1, 11, 3, 6, -1, -1, -1, -1},
	{6, 8, 4, 6, 11, 8, 2, 10, 1, -1, -1, -1, -1, -1, -1, -1},
	{1, 2, 10, 3, 0, 11, 0, 6, 11, 0, 4, 6, -1, -1, -1, -1},
	{4, 11, 8, 4, 6, 11, 0, 2, 9, 2, 10, 9, -1, -1, -1, -1},
	{10, 9, 3, 10, 3, 2, 9, 4, 3, 11, 3, 6, 4, 6, 3, -1},
	{8, 2, 3, 8, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1},
	{0, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8, -1, -1, -1, -1},
	{1, 9, 4, 1, 4, 2, 2, 4, 6, -1, -1, -1, -1, -1, -1, -1},
	{8, 1, 3, 8, 6, 1, 8, 4, 6, 6, 10, 1, -1, -1, -1, -1},
	{10, 1, 0, 10, 0, 6, 6, 0, 4, -1, -1, -1, -1, -1, -1, -1},
	{4, 6, 3, 4, 3, 8, 6, 10, 3, 0, 3, 9, 10, 9, 3, -1},
	{10, 9, 4, 6, 10, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{4, 9, 5, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{0, 8, 3, 4, 9, 5, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1},
	{5, 0, 1, 5, 4, 0, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1},
	{11, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5, -1, -1, -1, -1},
	{9, 5, 4, 10, 1, 2, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1},
	{6, 11, 7, 1, 2, 10, 0, 8, 3, 4, 9, 5, -1, -1, -1, -1},
	{7, 6, 11, 5, 4, 10, 4, 2, 10, 4, 0, 2, -1, -1, -1, -1},
	{3, 4, 8, 3, 5, 4, 3, 2, 5, 10, 5, 2, 11, 7, 6, -1},
	{7, 2, 3, 7, 6, 2, 5, 4, 9, -1, -1, -1, -1, -1, -1, -1},
	{9, 5, 4, 0, 8, 6, 0, 6, 2, 6, 8, 7, -1, -1, -1, -1},
	{3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0, -1, -1, -1, -1},
	{6, 2, 8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8, -1},
	{9, 5, 4, 10, 1, 6, 1, 7, 6, 1, 3, 7, -1, -1, -1, -1},
	{1, 6, 10, 1, 7, 6, 1, 0, 7, 8, 7, 0, 9, 5, 4, -1},
	{4, 0, 10, 4, 10, 5, 0, 3, 10, 6, 10, 7, 3, 7, 10, -1},
	{7, 6, 10, 7, 10, 8, 5, 4, 10, 4, 8, 10, -1, -1, -1, -1},
	{6, 9, 5, 6, 11, 9, 11, 8, 9, -1, -1, -1, -1, -1, -1, -1},
	{3, 6, 11, 0, 6, 3, 0, 5, 6, 0, 9, 5, -1, -1, -1, -1},
	{0, 11, 8, 0, 5, 11, 0, 1, 5, 5, 6, 11, -1, -1, -1, -1},
	{6, 11, 3, 6, 3, 5, 5, 3, 1, -1, -1, -1, -1, -1, -1, -1},
	{1, 2, 10, 9, 5, 11, 9, 11, 8, 11, 5, 6, -1, -1, -1, -1},
	{0, 11, 3, 0, 6, 11, 0, 9, 6, 5, 6, 9, 1, 2, 10, -1},
	{11, 8, 5, 11, 5, 6, 8, 0, 5, 10, 5, 2, 0, 2, 5, -1},
	{6, 11, 3, 6, 3, 5, 2, 10, 3, 10, 5, 3, -1, -1, -1, -1},
	{5, 8, 9, 5, 2, 8, 5, 6, 2, 3, 8, 2, -1, -1, -1, -1},
	{9, 5, 6, 9, 6, 0, 0, 6, 2, -1, -1, -1, -1, -1, -1, -1},
	{1, 5, 8, 1, 8, 0, 5, 6, 8, 3, 8, 2, 6, 2, 8, -1},
	{1, 5, 6, 2, 1, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{1, 3, 6, 1, 6, 10, 3, 8, 6, 5, 6, 9, 8, 9, 6, -1},
	{10, 1, 0, 10, 0, 6, 9, 5, 0, 5, 6, 0, -1, -1, -1, -1},
	{0, 3, 8, 5, 6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{10, 5, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{11, 5, 10, 7, 5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{11, 5, 10, 11, 7, 5, 8, 3, 0, -1, -1, -1, -1, -1, -1, -1},
	{5, 11, 7, 5, 10, 11, 1, 9, 0, -1, -1, -1, -1, -1, -1, -1},
	{10, 7, 5, 10, 11, 7, 9, 8, 1, 8, 3, 1, -1, -1, -1, -1},
	{11, 1, 2, 11, 7, 1, 7, 5, 1, -1, -1, -1, -1, -1, -1, -1},
	{0, 8, 3, 1, 2, 7, 1, 7, 5, 7, 2, 11, -1, -1, -1, -1},
	{9, 7, 5, 9, 2, 7, 9, 0, 2, 2, 11, 7, -1, -1, -1, -1},
	{7, 5, 2, 7, 2, 11, 5, 9, 2, 3, 2, 8, 9, 8, 2, -1},
	{2, 5, 10, 2, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1},
	{8, 2, 0, 8, 5, 2, 8, 7, 5, 10, 2, 5, -1, -1, -1, -1},
	{9, 0, 1, 5, 10, 3, 5, 3, 7, 3, 10, 2, -1, -1, -1, -1},
	{9, 8, 2, 9, 2, 1, 8, 7, 2, 10, 2, 5, 7, 5, 2, -1},
	{1, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{0, 8, 7, 0, 7, 1, 1, 7, 5, -1, -1, -1, -1, -1, -1, -1},
	{9, 0, 3, 9, 3, 5, 5, 3, 7, -1, -1, -1, -1, -1, -1, -1},
	{9, 8, 7, 5, 9, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{5, 8, 4, 5, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1},
	{5, 0, 4, 5, 11, 0, 5, 10, 11, 11, 3, 0, -1, -1, -1, -1},
	{0, 1, 9, 8, 4, 10, 8, 10, 11, 10, 4, 5, -1, -1, -1, -1},
	{10, 11, 4, 10, 4, 5, 11, 3, 4, 9, 4, 1, 3, 1, 4, -1},
	{2, 5, 1, 2, 8, 5, 2, 11, 8, 4, 5, 8, -1, -1, -1, -1},
	{0, 4, 11, 0, 11, 3, 4, 5, 11, 2, 11, 1, 5, 1, 11, -1},
	{0, 2, 5, 0, 5, 9, 2, 11, 5, 4, 5, 8, 11, 8, 5, -1},
	{9, 4, 5, 2, 11, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{2, 5, 10, 3, 5, 2, 3, 4, 5, 3, 8, 4, -1, -1, -1, -1},
	{5, 10, 2, 5, 2, 4, 4, 2, 0, -1, -1, -1, -1, -1, -1, -1},
	{3, 10, 2, 3, 5, 10, 3, 8, 5, 4, 5, 8, 0, 1, 9, -1},
	{5, 10, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2, -1, -1, -1, -1},
	{8, 4, 5, 8, 5, 3, 3, 5, 1, -1, -1, -1, -1, -1, -1, -1},
	{0, 4, 5, 1, 0, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{8, 4, 5, 8, 5, 3, 9, 0, 5, 0, 3, 5, -1, -1, -1, -1},
	{9, 4, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{4, 11, 7, 4, 9, 11, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1},
	{0, 8, 3, 4, 9, 7, 9, 11, 7, 9, 10, 11, -1, -1, -1, -1},
	{1, 10, 11, 1, 11, 4, 1, 4, 0, 7, 4, 11, -1, -1, -1, -1},
	{3, 1, 4, 3, 4, 8, 1, 10, 4, 7, 4, 11, 10, 11, 4, -1},
	{4, 11, 7, 9, 11, 4, 9, 2, 11, 9, 1, 2, -1, -1, -1, -1},
	{9, 7, 4, 9, 11, 7, 9, 1, 11, 2, 11, 1, 0, 8, 3, -1},
	{11, 7, 4, 11, 4, 2, 2, 4, 0, -1, -1, -1, -1, -1, -1, -1},
	{11, 7, 4, 11, 4, 2, 8, 3, 4, 3, 2, 4, -1, -1, -1, -1},
	{2, 9, 10, 2, 7, 9, 2, 3, 7, 7, 4, 9, -1, -1, -1, -1},
	{9, 10, 7, 9, 7, 4, 10, 2, 7, 8, 7, 0, 2, 0, 7, -1},
	{3, 7, 10, 3, 10, 2, 7, 4, 10, 1, 10, 0, 4, 0, 10, -1},
	{1, 10, 2, 8, 7, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{4, 9, 1, 4, 1, 7, 7, 1, 3, -1, -1, -1, -1, -1, -1, -1},
	{4, 9, 1, 4, 1, 7, 0, 8, 1, 8, 7, 1, -1, -1, -1, -1},
	{4, 0, 3, 7, 4, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{4, 8, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{9, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{3, 0, 9, 3, 9, 11, 11, 9, 10, -1, -1, -1, -1, -1, -1, -1},
	{0, 1, 10, 0, 10, 8, 8, 10, 11, -1, -1, -1, -1, -1, -1, -1},
	{3, 1, 10, 11, 3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{1, 2, 11, 1, 11, 9, 9, 11, 8, -1, -1, -1, -1, -1, -1, -1},
	{3, 0, 9, 3, 9, 11, 1, 2, 9, 2, 11, 9, -1, -1, -1, -1},
	{0, 2, 11, 8, 0, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{3, 2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{2, 3, 8, 2, 8, 10, 10, 8, 9, -1, -1, -1, -1, -1, -1, -1},
	{9, 10, 2, 0, 9, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{2, 3, 8, 2, 8, 10, 0, 1, 8, 1, 10, 8, -1, -1, -1, -1},
	{1, 10, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{1, 3, 8, 9, 1, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{0, 9, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{0, 3, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
	{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
};

static const unsigned char edgeConnection[12][2] = 
{
    {0,1}, {1,2}, {2,3}, {3,0},
    {4,5}, {5,6}, {6,7}, {7,4},
    {0,4}, {1,5}, {2,6}, {3,7}
};

static const D3DVECTOR gridVertices[8] =
{
	{0,0,1}, {1,0,1}, {1,0,0}, {0,0,0}, 
	{0,1,1}, {1,1,1}, {1,1,0}, {0,1,0}
};

const int c_iMaxTerrainVertices= 1 << 19;
static D3DXVECTOR3 vertices[c_iMaxTerrainVertices];
const int c_iMaxTerrainIndices = 1 << 21;
static int indices[c_iMaxTerrainIndices];

const int c_iMaxTerrainStepsXZ = 512;
const int c_iMaxTerrainStepsY = 256;
static float isoValues[c_iMaxTerrainStepsXZ * c_iMaxTerrainStepsY * 2];
static int indexValues[c_iMaxTerrainStepsXZ * c_iMaxTerrainStepsY * 5];

float IsoSphere(const D3DXVECTOR3& pos, const D3DXVECTOR3& center, const D3DXVECTOR3& scale, float r)
{
	D3DXVECTOR3 v = pos - center;
	v.x *= scale.x;
	v.y *= scale.y;
	v.z *= scale.z;
	return sqrtf(v.x * v.x + v.y * v.y + v.z * v.z) - r;
}

float IsoPlane(const D3DXVECTOR3& pos, const D3DXVECTOR3& center, const D3DXVECTOR3& normal)
{
	D3DXVECTOR3 v = pos - center;
	return D3DXVec3Dot(&v, &normal);
}

/*
__forceinline D3DXVECTOR3 D3DXOOV3(float x, float y, float z)
{
	return D3DXVECTOR3(1.0f / x, 1.0f / y, 1.0f / z);
}
*/
#define D3DXOOV3(x, y, z) D3DXVECTOR3(1.0f / x, 1.0f / y, 1.0f / z)

__forceinline float IsoDifference(float iso1, float iso2)
{
	return max(iso1, -iso2);
}

__forceinline float IsoMerge(float iso1, float iso2)
{
	return min(iso1, iso2);
}

__forceinline int mod(int x, int a)
{
	int r = x % a;
	if (r < 0) r += a;
	return r;
}

__forceinline int int_floor(float x)
{
	int i = (int) x;
	return i > x ? i - 1 : i;
}

__forceinline float lerp(float a, float b, float t)
{
	return (1 - t) * a + t * b;
}

float TerrainGrid::IsoSurfaceCave(const D3DXVECTOR3& pos)
{
	float iso = IsoSphere(pos, D3DXVECTOR3(0.5f, 0.5f, 0.5f), D3DXOOV3(1, 1, 1), 0.4f);

	iso = IsoMerge(
		iso,
		IsoSphere(pos, D3DXVECTOR3(0.125f, 0.65f, 0.75f), D3DXOOV3(1, 1.0f, 1), 0.25f) );

	iso = IsoMerge(
		iso,
		IsoSphere(pos, D3DXVECTOR3(0.0f, 0.625f, 0.625f), D3DXOOV3(1, 1.0f, 1), 0.2f) );

	iso = IsoMerge(
		iso,
		IsoSphere(pos, D3DXVECTOR3(0.0f, 0.875f, 0.625f), D3DXOOV3(1, 1.0f, 1), 0.1875f) );

	iso = IsoMerge(
		iso,
		IsoSphere(pos, D3DXVECTOR3(0.0625f, 0.59f, 0.5f), D3DXOOV3(1, 0.75f, 1), 0.125f) );

	iso = IsoMerge(
		iso,
		IsoSphere(pos, D3DXVECTOR3(0.25f, 0.57f, 0.25f), D3DXOOV3(2, 1.0f, 1), 0.125f) );

	iso = IsoDifference(
		iso,
		IsoSphere(pos, D3DXVECTOR3(0.125f, 0.375f, 0.5f), D3DXOOV3(0.125f, 1.0f, 0.125f), 0.25f) );

	iso = IsoDifference(
		iso,
		IsoSphere(pos, D3DXVECTOR3(0.1875f, 0.275f, 0.56f), D3DXOOV3(0.0625f, 1.0f, 0.0625f), 0.25f) );

	iso-= PerlinNoise_2D(pos.x, pos.z, 128) * 6.0f / 32.0f;
	iso-= PerlinNoise_2D(pos.x, pos.y, 192) / 16.0f;
	iso-= PerlinNoise_2D(pos.y, pos.z, 192) / 16.0f;

	iso = IsoDifference(
			IsoSphere(pos, D3DXVECTOR3(0.9f, 0.5f, 0.5f), D3DXOOV3(1, 1, 1), 0.85f),
			iso );

	iso = IsoDifference(
			iso,
			IsoPlane(pos, D3DXVECTOR3(0.0f, 0.97f, 0.0f), D3DXVECTOR3(0.0f, -1.0f, 0.0f)) );
//	iso = IsoDifference(
//			iso,
//			IsoPlane(pos, D3DXVECTOR3(0.97f, 0.0f, 0.0f), D3DXVECTOR3(-1.0f, 0.0f, 0.0f)) );
	iso = IsoDifference(
			iso,
			IsoPlane(pos, D3DXVECTOR3(0.0f, 0.0f, 0.97f), D3DXVECTOR3(0.0f, 0.0f, -1.0f)) );
//	iso = IsoDifference(
//			iso,
//			IsoPlane(pos, D3DXVECTOR3(0.0f, 0.0f, 0.03f), D3DXVECTOR3(0.0f, 0.0f, 1.0f)) );

	return iso;
}

float TerrainGrid::IsoSurfaceCaveGround(const D3DXVECTOR3& pos)
{
	float iso1 = IsoMerge(
		IsoSphere(pos, D3DXVECTOR3(0.5f, 0.4f, 0.5f), D3DXOOV3(1, 1, 1), 0.25f),
		IsoSphere(pos, D3DXVECTOR3(0.5f, 0.1f, 0.5f), D3DXOOV3(1, 1, 1), 0.37f) );
	float iso2 = IsoMerge(
		IsoSphere(pos, D3DXVECTOR3(0.5f, 0.5f, 0.42f), D3DXOOV3(1, 1, 1), 0.17f),
		IsoSphere(pos, D3DXVECTOR3(0.57f, 0.38f, 0.6f), D3DXOOV3(1, 1, 1), 0.11f) );

	float iso= IsoMerge( iso1, iso2 );
	
	iso-= PerlinNoise_2D(pos.x, pos.z, 128) * 12.0f / 32.0f;
	iso-= PerlinNoise_2D(pos.x, pos.y, 192) / 8.0f;
	iso-= PerlinNoise_2D(pos.y, pos.z, 192) / 8.0f;
	return iso;
}

int index = 0;
static const float random[] = {
	0.016096199,
	-0.041969635,
	-0.054145098,
	0.021143436,
	-0.0094251214,
	0.088897280,
	0.36951837,
	-0.16126564,
	0.010747797,
	0.094805837,
	-0.19188920,
	0.25969765,
	0.022508329,
	0.023705304,
	-0.0098044397,
	0.066074423,
	0.024152935,
	-0.089513578,
	-0.38613912,
	0.075401597,
	0.0086482586,
	-0.090612829,
	-0.032468367,
	-0.031355500,
	-0.010738159,
	0.026182247,
	-0.15096381,
	0.17182341,
	-0.035797309,
	-0.029005880,
	-0.27913427,
	-0.22096422,
	0.031160533,
	0.016560698,
	-0.25966603,
	-0.16343403,
	-0.011228019,
	0.050174236,
	0.012509584,
	-0.28846321,
	0.0097525716,
	-0.030592179,
	0.15790334,
	0.16756034,
	0.048684187,
	-0.069313243,
	0.35656410,
	-0.0073550940,
	0.018086834,
	0.035755921,
	-0.13925140,
	0.20644069,
	-0.016748196,
	-0.033889730,
	0.12365069,
	0.34854794,
	0.0099919019,
	0.023382772,
	-0.11413296,
	0.096547559,
	-0.019580711,
	-0.056822035,
	0.036674835,
	-0.33782470};

float IsoMountain(const D3DXVECTOR3& pos)
{
	return IsoSphere(pos, D3DXVECTOR3(0.5f + random[index++], 0.05f, 0.5f + random[index++]), D3DXOOV3(0.25f, 0.7f + random[index++], 0.15f), 0.25f + random[index++]);
}

float TerrainGrid::IsoSurfaceIsle(const D3DXVECTOR3& pos1)
{
	// Koordinaten entsprechen nicht altem System "halber Unitcube"
	D3DXVECTOR3 pos= pos1;
	pos.y*= 0.5f;

	float island = IsoMerge(
		IsoSphere(pos, D3DXVECTOR3(0.5f, 0.10f, 0.5f), D3DXOOV3(1, 1, 1), 0.25f),
		IsoSphere(pos, D3DXVECTOR3(0.5f, 0.01f, 0.5f), D3DXOOV3(1, 0.5f, 1), 0.4f));

	// Small Mountains
	index = 0;
	float mountains = IsoSphere(pos, D3DXVECTOR3(0.5f, 0.1f, 0.84f), D3DXOOV3(0.15f, 0.8f, 0.2f), 0.3f);
	for (int i = 0; i < 16; ++i)
	{
		mountains = IsoMerge(mountains, IsoMountain(pos));
	}
	mountains += PerlinNoise_2D(pos.x, pos.z, 256) * 0.2f;
	mountains += PerlinNoise_2D(pos.y, pos.z, 256) * 0.1f;

	// Big mountains
	float hill = IsoSphere(pos, D3DXVECTOR3(0.5f, 0.18f, 0.5f), D3DXOOV3(0.3f, 0.8f, 0.3f), 0.4f);
	hill += PerlinNoise_2D(pos.x, pos.y, 480) * 0.05f;
	hill += PerlinNoise_2D(pos.y, pos.z, 480) * 0.05f;
	hill += PerlinNoise_2D(pos.z, pos.x, 480) * 0.05f;

	// Canal for the arc
	float canal = IsoSphere(pos, D3DXVECTOR3(0.5f, 0.1f, 0.74f), D3DXOOV3(1.0f, 0.5f, 0.12f), 0.2f);
	canal += PerlinNoise_2D(pos.x, pos.y, 512) * 0.2f;
	canal += PerlinNoise_2D(pos.y, pos.z, 512) * 0.2f;

	// Bridge for the arc
	float bridge = IsoDifference(
		IsoSphere(pos, D3DXVECTOR3(0.5f, 0.25f, 0.75f), D3DXOOV3(0.1f, 0.4f, 0.68f), 0.2f),
		canal);
	bridge += PerlinNoise_2D(pos.x, pos.y, 384) * 0.1f;
	bridge -= PerlinNoise_2D(pos.y, pos.z, 384) * 0.1f;
	bridge += PerlinNoise_2D(pos.z, pos.x, 384) * 0.1f;
	bridge = IsoDifference(bridge, IsoPlane(pos, D3DXVECTOR3(0.5, 0.35f, 0.75f), D3DXVECTOR3(0, -1, 0)));
	
	// Merge everything together
	float iso = IsoMerge(IsoMerge(IsoMerge(island, mountains), bridge), hill);
	
	// Globale verwirbelungen
	iso -= PerlinNoise_2D(pos.x, pos.z, 192) * 0.2f;
	iso += PerlinNoise_2D(pos.y, pos.x, 192) * 0.1f;

	return iso;
}

const float M_PI = 3.141592768f;
const int textureSize = 1024;

float TerrainGrid::PerlinNoise_2D(float x, float y, float scale)
{
	const D3DCOLOR* color = (const D3DCOLOR*)noiseLock.pBits;
	int ix1, ix2, iy1, iy2;
	float t1, t2;
	float c1, c2, c3, c4;
	x *= scale; y *= scale;
	ix1 = int_floor(x);
	t1 = x - ix1;
	ix2 = ix1 + 1;
	iy1 = int_floor(y);
	t2 = y - iy1;
	iy2 = iy1 + 1;
	ix1 = mod(ix1, textureSize);
	ix2 = mod(ix2, textureSize);
	iy1 = mod(iy1, textureSize);
	iy2 = mod(iy2, textureSize);

	t1 = (1-cos(t1 * M_PI))/2;
	t2 = (1-cos(t2 * M_PI))/2;

	c1 = (float)(color[iy1 * textureSize + ix1] >> 24);
	c2 = (float)(color[iy1 * textureSize + ix2] >> 24);
	c3 = (float)(color[iy2 * textureSize + ix1] >> 24);
	c4 = (float)(color[iy2 * textureSize + ix2] >> 24);
	return lerp(lerp(c1, c2, t1), lerp(c3, c4, t1), t2) / 128.0f - 1.0f;
}

D3DXVECTOR3 TerrainGrid::VertexInterp(float isolevel, D3DXVECTOR3 p1, D3DXVECTOR3 p2, float valp1, float valp2)
{
   D3DXVECTOR3 p;

   float mu = (isolevel - valp1) / (valp2 - valp1);
   p.x = p1.x + mu * (p2.x - p1.x);
   p.y = p1.y + mu * (p2.y - p1.y);
   p.z = p1.z + mu * (p2.z - p1.z);

   return(p);
}

int TerrainGrid::Polygonise(GRIDCELL grid, float isolevel, TRIANGLE* triangles)
{
	unsigned short i, flag;
	D3DXVECTOR3 vertlist[12];

	int cubeindex = 0;
	flag = 1;
	for (i = 0; i < 8; ++i, flag <<= 1)
	   if (grid.val[i] <= isolevel) cubeindex |= flag;

	if (edgeTable[cubeindex] == 0)
	  return 0;

	flag = 1;
	for (i = 0; i < 12; ++i, flag <<= 1)
	   if (edgeTable[cubeindex] & flag)
		  vertlist[i] = VertexInterp(isolevel,
			grid.p[edgeConnection[i][0]],
			grid.p[edgeConnection[i][1]],
			grid.val[edgeConnection[i][0]],
			grid.val[edgeConnection[i][1]]);

	for (i = 0; triTable[cubeindex][i] != -1; ++i)
	  triangles[i / 3].p[i % 3] = vertlist[triTable[cubeindex][i]];

	return i / 3;
}

D3DXVECTOR3 TerrainGrid::GetNormal(D3DXVECTOR3 input, iso_surface_function pIsoSurface)
{
	float fEps= 0.01f;
	return D3DXVECTOR3(
		(this->*pIsoSurface)(input + D3DXVECTOR3(fEps, 0, 0)) - (this->*pIsoSurface)(input - D3DXVECTOR3(fEps, 0, 0)),
		(this->*pIsoSurface)(input + D3DXVECTOR3(0, fEps, 0)) - (this->*pIsoSurface)(input - D3DXVECTOR3(0, fEps, 0)),
		(this->*pIsoSurface)(input + D3DXVECTOR3(0, 0, fEps)) - (this->*pIsoSurface)(input - D3DXVECTOR3(0, 0, fEps)));
}

void TerrainGrid::Init( int StepsXZ, int StepsY, iso_surface_function pIsoSurface )
{	
	assert( StepsXZ < c_iMaxTerrainStepsXZ );
	assert( StepsY < c_iMaxTerrainStepsY );

	const float xres = 1.0f / StepsXZ;
	const float yres = 1.0f / StepsY;
	const float zres = 1.0f / StepsXZ;

	g_pTextures[TI_Wave].Lock();
	noiseLock = g_pTextures[TI_Wave].GetData();
	vertexCount = 0;
	indexCount = 0;

	// Clear
	mymemset(indexValues, -1, sizeof(indexValues));

	int StepsXZPP = StepsXZ + 1;
	int StepsYPP = StepsY + 1;
	int StepsXYZPP = StepsXZPP * StepsYPP;

	int iIndexCacheSmallLayerSize = StepsXYZPP;
	int iIndexCacheBigLayerSize = iIndexCacheSmallLayerSize * 2;
	
	int iNextCacheLayer = 0;
	int iNextIndexCacheLayer = 0;
	int iPrevIndexCacheLayerBaseValue = 0;
	bool bFirstRun = true;

	for (int x = 0; x < StepsXZ; ++x)
	{
		// Old layer, new layer
		int iCacheLayers[2] = { (iNextCacheLayer + 1) % 2, iNextCacheLayer };

		// Overwrite oldest layer next time
		iNextCacheLayer = iCacheLayers[0];

		for (int r = 0; r < 1 + bFirstRun; r++)
		{
			// New layer first, old layer afterwards on first run
			int iCacheBase = iCacheLayers[1 - r] * StepsXYZPP;
			int xpp = x + 1 - r;

			for (int y = 0; y < StepsYPP; ++y)
			{
				int iCacheBaseY = iCacheBase + y * StepsXZPP;

				for (int z = 0; z < StepsXZPP; ++z)
				{
					D3DXVECTOR3 gridP = D3DXVECTOR3((float)xpp, (float)y, (float)z);

					gridP.x *= xres;
					gridP.y *= yres;
					gridP.z *= zres;

					isoValues[ iCacheBaseY + z ] = (this->*pIsoSurface)( gridP );
				}
			}
		}
		bFirstRun = false;

		// Old layer, new layer
		int iIndexOuterCacheLayers[2] = { (iNextIndexCacheLayer + 1) % 2, iNextIndexCacheLayer };
		
		// Overwrite oldest layer next time
		iNextIndexCacheLayer = iIndexOuterCacheLayers[0];

		// Layer bases
		int *pIndexValueLayers[3] = {
			indexValues + iIndexOuterCacheLayers[0] * iIndexCacheBigLayerSize,
			indexValues + 2 * iIndexCacheBigLayerSize,
			indexValues + iIndexOuterCacheLayers[1] * iIndexCacheBigLayerSize };

		// Layer value bases
		int iIndexValueLayerBaseValues[3] = {
			iPrevIndexCacheLayerBaseValue,
			vertexCount,
			vertexCount };

		// Current vertex count is base for next time
		iPrevIndexCacheLayerBaseValue = iIndexValueLayerBaseValues[2];

		for (int y = 0; y < StepsY; ++y)
		{
			for (int z = 0; z < StepsXZ; ++z)
			{
				TRIANGLE triangles[5];
				GRIDCELL grid;
				for (int i = 0; i < 8; ++i)
				{
					D3DXVECTOR3 &gridP = grid.p[i];
					gridP = gridVertices[i];
					gridP += D3DXVECTOR3((float)x, (float)y, (float)z);

					int iCacheBase = iCacheLayers[ (int)gridVertices[i].x ] * StepsXYZPP;
					int iCacheBaseY = iCacheBase + (int)gridP.y * StepsXZPP;
					grid.val[i] = isoValues[ iCacheBaseY + (int)gridP.z ];

					gridP.x *= xres;
					gridP.y *= yres;
					gridP.z *= zres;

//					assert( grid.val[i] == IsoSurface(gridP) );
				}
				
				int nTriangles = Polygonise(grid, 0, triangles);
				
				float fCellXL = x * xres, fCellXU = fCellXL + xres;
				float fCellYL = y * yres, fCellYU = fCellYL + yres;
				float fCellZL = z * zres, fCellZU = fCellZL + zres;

				for (int i = 0; i < nTriangles; ++i)
				{
					const TRIANGLE &tri = triangles[i];

					for (int j = 3; j-- > 0; )
					{
						const D3DXVECTOR3 &pos = tri.p[j];
						
						// Compute edge deviations
						float fEdgeXL = pos.x - fCellXL, fEdgeXU = fCellXU - pos.x;
						float fEdgeYL = pos.y - fCellYL, fEdgeYU = fCellYU - pos.y;
						float fEdgeZL = pos.z - fCellZL, fEdgeZU = fCellZU - pos.z;
						
						int iEdgeX = (fEdgeXL > fEdgeXU);
						int iEdgeY = (fEdgeYL > fEdgeYU);
						int iEdgeZ = (fEdgeZL > fEdgeZU);
						
						float fEdgeXD = (iEdgeX) ? fEdgeXU : fEdgeXL;
						float fEdgeYD = (iEdgeY) ? fEdgeYU : fEdgeYL;
						float fEdgeZD = (iEdgeZ) ? fEdgeZU : fEdgeZL;
						
						// Compute layer
						int iEdgeLayer = (fEdgeXD > fEdgeYD && fEdgeXD > fEdgeZD)
							? 1				// Center layer
							: 2 * iEdgeX;	// Top / bottom layer
						int *pLayerIndexValues = pIndexValueLayers[iEdgeLayer];
						int iLayerIndexBaseValue = iIndexValueLayerBaseValues[iEdgeLayer];

						int *pIndexValue;

						// Center layer
						if (iEdgeLayer == 1)
						{
							// Get index value
							int iCacheBaseY = (y + iEdgeY) * StepsXZPP;
							int iCacheIndex = iCacheBaseY + (z + iEdgeZ);
							pIndexValue = &pLayerIndexValues[iCacheIndex];
						}
						// Top / bottom layer
						else
						{
							int iOnY = (fEdgeYD > fEdgeZD);
							int iEdgeZY = (iOnY) ? iEdgeZ : iEdgeY;

							// Get index value
							int iCacheBaseY = ( (y + (1 - iOnY) * iEdgeZY) * 2 + iOnY ) * StepsXZPP;
							int iCacheIndex = iCacheBaseY + ( z + iOnY * iEdgeZY );
							pIndexValue = &pLayerIndexValues[iCacheIndex];
						}

						int &indexValue = *pIndexValue;
						bool bIndexValid = (indexValue >= iLayerIndexBaseValue);

						// Check index
						if(!bIndexValid)
						{
							// Update index
							indexValue = vertexCount;

							// Allocate new vertex
							vertices[vertexCount++] = tri.p[j];
						}

						// Allocate new index
						indices[indexCount++] = indexValue;
					}
				}
			}
		}

		if( ( x & 31 ) == 31 )
		{
			RenderLoading( 4 );
		}
	}

	assert( vertexCount <= c_iMaxTerrainVertices );
	assert( indexCount <= c_iMaxTerrainIndices );
	
	D3DVERTEXELEMENT9 decl[] =
	{
		{0, 0, D3DDECLTYPE_FLOAT3, D3DDECLMETHOD_DEFAULT, D3DDECLUSAGE_POSITION, 0},
		{0, 12, D3DDECLTYPE_FLOAT3, D3DDECLMETHOD_DEFAULT, D3DDECLUSAGE_NORMAL, 0},
		{0, 24, D3DDECLTYPE_FLOAT2, D3DDECLMETHOD_DEFAULT, D3DDECLUSAGE_TEXCOORD, 0},
		{0, 32, D3DDECLTYPE_D3DCOLOR, D3DDECLMETHOD_DEFAULT, D3DDECLUSAGE_COLOR, 0},
		D3DDECL_END()
	};

	assert(vertexCount != 0);

	g_d3d_device->CreateVertexDeclaration(decl, &vertexDecl);
	g_d3d_device->CreateVertexBuffer(sizeof(TerrainVertex) * vertexCount, D3DUSAGE_WRITEONLY, 0, D3DPOOL_MANAGED, &vertexBuffer, NULL);
	g_d3d_device->CreateIndexBuffer(sizeof(int) * indexCount, D3DUSAGE_WRITEONLY, D3DFMT_INDEX32, D3DPOOL_MANAGED, &indexBuffer, NULL);

	TerrainVertex* vertex;
	int* index;

	vertexBuffer->Lock(0, 0, (void**)&vertex, 0);
	indexBuffer->Lock(0, 0, (void**)&index, 0);

	for (int i = 0; i < vertexCount; ++i)
	{
		vertex[i].pos = vertices[i];
		vertex[i].col = D3DXCOLOR(0xFFFFFFFF);
		vertex[i].tex = D3DXVECTOR2(vertices[i].x, vertices[i].z);
		vertex[i].normal = GetNormal(vertices[i], pIsoSurface); // D3DXVECTOR3(0, 0, 0); // GetNormal(vertices[i]);
	}

	mymemcpy(index, indices, sizeof(int) * indexCount);

/*	for (int i = 0; i < indexCount; i+=3)
	{
		int iVertex1 = index[i];
		int iVertex2 = index[i + 1];
		int iVertex3 = index[i + 2];
		
		D3DXVECTOR3 vNormal;
		D3DXVECTOR3 vDelta1 = vertex[iVertex2].pos - vertex[iVertex1].pos;
		D3DXVECTOR3 vDelta2 = vertex[iVertex3].pos - vertex[iVertex1].pos;
		D3DXVec3Cross(&vNormal, &vDelta1, &vDelta2);
		
		vertex[iVertex1].normal += vNormal;
		vertex[iVertex2].normal += vNormal;
		vertex[iVertex3].normal += vNormal;
	}

	for (int i = 0; i < vertexCount; ++i)
		D3DXVec3Normalize(&vertex[i].normal, &vertex[i].normal);
*/
	indexBuffer->Unlock();
	vertexBuffer->Unlock();
	g_pTextures[TI_Wave].Unlock();
}


void TerrainGrid::Render()
{
	g_d3d_device->SetStreamSource(0, vertexBuffer, 0, sizeof(TerrainVertex));
	g_d3d_device->SetFVF(NULL);
	g_d3d_device->SetVertexDeclaration(vertexDecl);
	g_d3d_device->SetIndices(indexBuffer);

	g_d3d_device->DrawIndexedPrimitive(D3DPT_TRIANGLELIST, 0, 0, vertexCount, 0, indexCount / 3);
}