package edu.uprm.walsaip.vte.core.model.lod;
/*
*   GeoMMLandscape -- An implementation of the GeoMipMap landscape rendering algorithm.
*   
*   Copyright (C) 2001-2004 by Joseph A. Huwaldt
*   All rights reserved.
*   
*   This library is free software; you can redistribute it and/or
*   modify it under the terms of the GNU Lesser General Public
*   License as published by the Free Software Foundation; either
*   version 2.1 of the License, or (at your option) any later version.
*   
*   This library 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
*   Lesser General Public License for more details.
*
*   You should have received a copy of the GNU Lesser 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.
*   Or visit:  http://www.gnu.org/licenses/lgpl.html
**/

import java.util.ArrayList;
import java.util.List;


import javax.media.opengl.GL;

import edu.uprm.walsaip.vte.core.datatypes.terrain.ElevationData;
import edu.uprm.walsaip.vte.core.renderer.Renderer;
import edu.uprm.walsaip.vte.core.util.GLUtils;



/**
*  This class is used to render a landscape (rectangular array of
*  altitude points) using a version of the GeoMipMap level-of-detail
*  algorithm.
*
*  <p>  This code is based on the paper "Fast Terrain Rendering Using Geometrical MipMapping",
*       Willem H. de Boer, whdeboer@iname.com, E-mersion Project, October 2000,
*       http://www.flipcode.com/tutorials/tut_geomipmaps.shtml.
*  </p>
*
*  <p>  Modified by:  Joseph A. Huwaldt   </p>
*
*  @author  Joseph A. Huwaldt   Date:  April 19, 2001
*  @version November 26, 2004
**/
public class GeoMMLandscape implements LODLandscape {
	
	// Size of the height map in grid coordinates.
//	private int gMapXSize;
//	private int gMapYSize;
	
	// Amount of space between map grid points in model coordinates.
	private float gGridSpacingX = 1;
	private float gGridSpacingY = 1;
	
	// HeightMap of the Landscape
	private	 ElevationData elevationMap;
	
	

	
	// The current drawing mode.
	private int gDrawMode = 0;
	
	// An array of top level quad-trees used to organize the terrain data.
	private QuadTreeNode[] gPatches;
	
	// Number of quad-tree patches in this Landscape.
	private int gNumPatches;
	
	// An array of terrain blocks that cover's the landscape being modeled.
	private TerrainBlock[][] gBlocks;
	
	// The size of the terrain blocks that we will eventually be rendering.
	private int gBlockSize;
	private 	Renderer renderer;
	//  The number of mip map levels in each terrain block.
	private int gMipMapLevels;

	
	//	The maximum pixel error allowed before switching to a higher resolution mip-map.
	private int gThreshold;
	
//	 The minimum altitudes in the map (used for altitude shading).
	//private int minAlt;
	//private int maxAlt;
	
	
	/**
	*  Create a new GeoMipMap landscape renderer using the specified height map.
	*
	*  @param  altMap   The map of altitude points (height map) that make up the terrain.
	*                   The map width & height must be 2^n + 1.
	*                   A reference is kept.
	*  @param  blockSize    The size of an individual block of terrain (square and must be 2^m).
	*  @param  gridSpacing  The model (world) coordinate distance between grid points.
	*  @param  vfNear       The distance to the view frustum near clipping plane.
	*  @param  vfTop        The top coordinate of the view frustum near clipping plane.
	*  @param  vRes         The height of the rendering window in pixels.
	*  @param  tau          The threshold for switching mip-map levels.
	**/
	public GeoMMLandscape(Renderer renderer,ElevationData elevationMap, int blockSize, float gridSpacingX,float gridSpacingY,
									float vfNear, float vfTop,
									int vRes, int tau) throws IllegalArgumentException {
		
		int height = elevationMap.getHeight();
		int width = elevationMap.getWidth() ;
		this.gBlockSize = blockSize;
		this.renderer = renderer;
//		int rightPad =0;
//		int leftPad = 0;
//		int topPad =0;
//		int bottomPad;
		if (width%blockSize != 0) {
			throw new IllegalArgumentException("Height map width must be (blockSize*n + 1), value recieved: "+width);
			
		}
		if (height%blockSize != 0) {
			
			throw new IllegalArgumentException("Height map height must be (blockSize*n + 1), value recieved: "+height);
		}
		//int new_height =  height + (blockSize - (height % blockSize));
		//int new_width =  width + (blockSize - (width % blockSize));
		
		
		//gMapXSize = width;
		//gMapYSize = height;
	
		// Store the Height Field array
		this.elevationMap = elevationMap;
		this.gGridSpacingX = gridSpacingX;
		this.gGridSpacingY = gridSpacingY;
		//this.minAlt = (int)altMap.getBoundingBox().getMinElevation();
		//this.maxAlt = (int)altMap.getBoundingBox().getMaxElevation();
		//this.minAlt = (int)altMap.minAlt();
		//this.maxAlt = (int)altMap.maxAlt();
		
		//	Calculate the number of mip-map levels per terrain block.
		this.gMipMapLevels = log2(blockSize) + 1;
	
		
		this.renderer.setupBuffers((blockSize+1)*2);
		
		//	Initialize sine and cosine tables since we use them.
		GLUtils.initSinDCosD();
		
		//	Calculate constant used in calculating mip-map distances.
		this.gThreshold = tau;
		float A = vfNear/(float)Math.abs(vfTop);
		float T = 2*tau/(float)vRes;
		float kC = A/T;
		
		//	Initialize all the quad-tree patches in the landscape.
		initPatches(width, height, blockSize, kC);
		
		//	Link neighboring terrain blocks together.
		linkTerrainBlocks();
		
	}
	


	/**
	*  Set the drawing mode to one of the constants defined
	*  in this class.
	**/
	public void setDrawMode(int mode) {
		if (mode < 0)
			mode = 0;
		else if (mode > 3)
			mode = 3;
		gDrawMode = mode;
	}
	
	/**
	*  Return the drawing mode used by this landscape.
	**/
	public int getDrawMode() {
		return gDrawMode;
	}
	
	/**
	*  Return the level-of-detail threshold used to set the
	*  mip-map levels used in this landscape rendering algorithm.
	*  The threshold is an integer number representing the maximum
	*  error allowed in screen pixels.  A value of 1 gives the highest
	*  level of detail.  Larger numbers result in lower detail.
	**/
	public int getLevelOfDetail() {
		return gThreshold;
	}
	
	/**
	*  Set the level-of-detail threshold used to set the
	*  mip-map levels used in this landscape rendering algorithm.
	*  The threshold is an integer number representing the maximum
	*  error allowed in screen pixels.  A value of 1 gives the highest
	*  level of detail.  Larger numbers result in lower detail.
	**/
	public void setLevelOfDetail(int number) {
		if (number < 1)	number = 1;
		
		int sizeY = gBlocks.length;
		int sizeX = gBlocks[0].length;
		for (int i=0; i < sizeY; ++i) {
			for (int j=0; j < sizeX; ++j) {
				gBlocks[i][j].changeThreshold(number);
			}
		}
		
		gThreshold = number;
	}
	
	/**
	*  Returns the actual number of triangles rendered during
	*  the last pass through the render() method.
	**/
	public int numTrianglesRendered() {
		return renderer.numTrianglesRendered();
	}
	
	/**
	*  Initialize all the quad-tree patches in the landscape down to
	*  terrain block size.
	**/
	private void initPatches(int mapWidth, int mapHeight, int blockSize, float kC) {

		//	First create an array of terrain blocks that cover the entire terrain.
		int sizeX = mapWidth/blockSize;
		int sizeY = mapHeight/blockSize;
		gBlocks = new TerrainBlock[sizeY][sizeX];
		//System.out.println("Here" +sizeX+"-"+sizeY);
		for (int i=0; i < sizeY; ++i) {
			for (int j=0; j < sizeX; ++j) {
				gBlocks[i][j] = new TerrainBlock(j*blockSize, i*blockSize, blockSize, kC);
			}
		}
		
		//	Go off and find all the patches required.
		List<QuadTreeNode> patchList = new ArrayList<QuadTreeNode>();
		findPatches(patchList, 0, 0, mapWidth, mapHeight, blockSize, kC);
				
		// Create an array to contain the patches.
		gNumPatches = patchList.size();
		gPatches = new QuadTreeNode[gNumPatches];
		
		// Copy all the terrain patches from the array list to the array
		gPatches = patchList.toArray(gPatches);

		
	}
	
	/**
	*  Link up neighboring terrain blocks.
	**/
	private void linkTerrainBlocks() {
	
		int nx = gBlocks[0].length;
		int ny = gBlocks.length;
		for (int yPos=0; yPos < ny; ++yPos) {
			for (int xPos=0; xPos < nx; ++xPos) {
			
				//	Grab the current block.
				TerrainBlock block = gBlocks[yPos][xPos];
				
				//	Identify the neighbors of this terrain block.
				if (yPos > 0)
					block.north = gBlocks[yPos - 1][xPos];
				if (yPos < gBlocks.length - 1)
					block.south = gBlocks[yPos + 1][xPos];
				if (xPos > 0)
					block.west = gBlocks[yPos][xPos - 1];
				if (xPos < gBlocks[0].length - 1)
					block.east = gBlocks[yPos][xPos + 1];
			
			}
		}
		
	}
	
	/**
	*  Recursively identify all the patches required to cover the terrain.
	*  We'll have one big patch in the upper left with smaller
	*  ones surrounding it as needed depending on map shape.
	**/
	private void findPatches(List<QuadTreeNode> patchList, int xOffset, int yOffset,
									int width, int height, int blockSize, float kC) {
				
		//	Create the big patch.
		int maxPWidth = (int)Math.pow(2, log2(Math.min(width, height)));
		QuadTreeNode patch;
		if (maxPWidth > blockSize)
			patch = new Patch(xOffset, yOffset, maxPWidth, blockSize, kC);
		else {
			//	We are down to a single terrain block, pull it from the global array.
			int xPos = xOffset/blockSize;
			int yPos = yOffset/blockSize;
			patch = gBlocks[yPos][xPos];
		}
		patchList.add(patch);
		
		//	Go off to the right and fill in with smaller patches.
		int usedWidth = maxPWidth;
		int pWidth = maxPWidth;
		int diff = width - usedWidth;
		while (diff > 0) {
			while (pWidth > diff)
				pWidth /= 2;
			
			int vCount = maxPWidth/pWidth;
			for (int i=0; i < vCount; ++i) {
				if (pWidth > blockSize)
					patch = new Patch(xOffset + usedWidth, yOffset + i*pWidth, pWidth, blockSize, kC);
				else {
					//	We are down to a single terrain block, pull it from the global array.
					int xPos = (xOffset + usedWidth)/blockSize;
					int yPos = (yOffset + i*pWidth)/blockSize;
					patch = gBlocks[yPos][xPos];
				}
				patchList.add(patch);
			}
			
			usedWidth += pWidth;
			diff = width - usedWidth;
		}
		
		//	Now do the small patches on the bottom.
		usedWidth = maxPWidth;
		pWidth = maxPWidth;
		diff = height - usedWidth;
		while (diff > 0) {
			while (pWidth > diff)
				pWidth /= 2;
			
			int vCount = maxPWidth/pWidth;
			for (int i=0; i < vCount; ++i) {
				if (pWidth > blockSize)
					patch = new Patch(xOffset + i*pWidth, yOffset + usedWidth, pWidth, blockSize, kC);
				else {
					//	We are down to a single terrain block, pull it from the global array.
					int xPos = (xOffset + i*pWidth)/blockSize;
					int yPos = (yOffset + usedWidth)/blockSize;
					patch = gBlocks[yPos][xPos];
				}
				patchList.add(patch);
			}
			
			usedWidth += pWidth;
			diff = height - usedWidth;
		}
		
		
		// Now do the lower right corner if needed.
		width -= maxPWidth;
		height -= maxPWidth;
		if (width > 0 && height > 0)
			findPatches(patchList, xOffset + maxPWidth, yOffset + maxPWidth,
								width, height, blockSize, kC);
		
	}
	
	/**
	*  Determine visibility of all terrain blocks and determine the geo mip-map level
	*  that will be used by each.
	*
	*  @param  fovX         The field of view in degrees.
	*  @param  viewPosition The location of the camera in model coordinates.
	*  @param  clipAngle    The direction the camera is pointing.
	**/
	public void update(float fovX, float[] viewPosition, float clipAngle) {
		
		/* Perform simple visibility culling on entire patches.
			- Define a triangle set back from the camera by 1/2 terrain block size, following
				the angle of the frustum.
			- A patch is visible if at least one corner is visible in the triangle: Left,Eye,Right
			- This visibility test is only accurate if the camera cannot
				look up or down significantly.
		*/
		int FOV_DIV_2 = Math.round(fovX/2);
		int iClip = GLUtils.range360(Math.round(clipAngle));
		
		//	Calculate grid corrdinates closest to the eye location - 1/2 patch size.
		int eyeX = (int)(viewPosition[0]/gGridSpacingX) - (int)(gBlockSize/2*GLUtils.sinD(iClip));
		int eyeY = (int)(viewPosition[2]/gGridSpacingY) + (int)(gBlockSize/2*GLUtils.cosD(iClip));

		int patch2 = gBlockSize*2;
		int angle = GLUtils.range360(iClip - FOV_DIV_2);
		int leftX = eyeX + (int)( patch2*GLUtils.sinD(angle) );
		int leftY = eyeY - (int)( patch2*GLUtils.cosD(angle) );

		angle = GLUtils.range360(iClip + FOV_DIV_2);
		int rightX = eyeX + (int)( patch2*GLUtils.sinD(angle) );
		int rightY = eyeY - (int)( patch2*GLUtils.cosD(angle) );
		
		//	Loop over the patches updating the visibility of each.
		//	Then pick the mip-map level for each terrain block in each visible patch.
		for (int i=0; i < gNumPatches; ++i) {
			QuadTreeNode patch = gPatches[i];
			patch.makeVisible();
			//patch.setVisibility(eyeX, eyeY, leftX, leftY, rightX, rightY);
			patch.chooseMMLevel(viewPosition);
		}

	}
	
	/**
	*  Render the landscape to the specified OpenGL rendering context.
	*
	*  @param  gl   The OpenGL rendering context that we are rendering into.
	**/
	public void render(GL gl) {
	
		// Reset rendered triangle count.
		


		// Store old matrix
		
	
		// Scale the grid coordinates to model coordinates.
		gl.glScalef(gGridSpacingX, 1, gGridSpacingY);
		
		//	Set the default color.
		//gl.glColor3f(1,1,1);
		
		// All rendering is done with a triangle-strip vertex array (the verticies are filled
		// in and the rendering call made by each TerrainBlock object).
		renderer.render_frame_begin(gl);

		//	Enable a color array for the vertex colors.
//		gl.glEnableClientState(GL.GL_COLOR_ARRAY);
//		gl.glColorPointer(3, GL.GL_FLOAT, 0, colorArray);
		
		//	Render each quad-tree patch in this landscape.
		for (int i=0; i < gNumPatches; ++i) {
			QuadTreeNode patch = gPatches[i];
			patch.render(gl);
		}
		
		renderer.render_frame_end(gl);
		

		// Restore the matrix
		

	}
	
	/**
	*  Returns the base 2 logarithm of a number as an integer.
	**/
	private static int log2(int number) {
		return (int)(Math.log(number)/Math.log(2));
	}
	

	

	/*************************************************************/
	/**
	*  This is the interface for a quad-tree node that can either
	*  be a branch or leaf of the quad-tree data structure.
	**/
	private abstract class QuadTreeNode {
	
		/**
		*  Render the mesh in this quad-tree node.
		**/
		abstract void render(GL gl);
		
		/**
		*  Set this node's visibility flag based on triangle orientation.
		*  Examines triangles formed by the eye point, the left &
		*  right frustum points and the corners of the node.
		*  This method of frustum culling does not work if the camera can
		*  look up or down significantly.
		*
		*  @param  eyeX, eyeY     The grid coordinates of the eye view point.
		*  @param  leftX, leftY   The grid coordinates of the left frustum point.
		*  @param  rightX, rightY The grid coordinates of the right frustum point.
		**/
		abstract void setVisibility(int eyeX, int eyeY, int leftX, int leftY,
										int rightX, int rightY);

		/**
		*  Force this quad-tree patch and all of it's children to be visible.
		**/
		abstract void makeVisible();
	
		/**
		*  Chooses an appropriate mip-map level for all visible nodes.
		*
		*  @param  eyePosition  The world coordinate location of the eye point or
		*                       camera view point [x, y, z].
		**/
		abstract void chooseMMLevel(float[] eyePosition);
	
		/**
		*  Discover the orientation of a triangle's points:
		*  Taken from "Programming Principles in Computer Graphics",
		*      L. Ammeraal (Wiley)
		**/
		protected final boolean orientation( int pX, int pY, int qX, int qY, int rX, int rY ) {
			int aX = qX - pX;
			int aY = qY - pY;
			int bX = rX - pX;
			int bY = rY - pY;

			int d = aX*bY - aY*bX;
			return ( d <= 0 );
		}

	}


	/**
	*  This class is a quad-tree node (branch) that represents an area or patch
	*  of the terrain which is larger than a single terrain block.
	**/
	private class Patch extends QuadTreeNode {
	
		// Is this quad-tree node visible in the current frame?
		private boolean isVisible = false;
		
		// The bounds of this patch in grid coordinates.
		private int offsetX, offsetY, width;
		
		
		// The children of this node.
		private QuadTreeNode[] child = new QuadTreeNode[4];
		
		
		/**
		*  Construct a Patch quad-tree node for a piece of our landscape.
		*
		*  @param  offsetX   Offset into the height map of the upper left corner
		*                    of this patch (X grid coordinate).
		*  @param  offsetY   Offset into the height map of the upper left corner
		*                    of this patch (Y grid coordinate).
		*  @param  width     The width of this patch in grid coordinates.
		*  @param  blockSize The width of a terrain block in grid coordinates.
		*  @param  kC        A constant used in calculating mip-map distances.
		**/
		Patch(int offsetX, int offsetY, int width, int blockSize, float kC) {
		
			this.offsetX = offsetX;
			this.offsetY = offsetY;
			this.width = width;
			
			//	Halve the width.
			width /= 2;
			
			if ( width > blockSize) {				
				//	We are among the branches of the tree, create sub-patches for children.
				child[0] = new Patch(offsetX,		offsetY,		width, blockSize, kC);
				child[1] = new Patch(offsetX,		offsetY+width,	width, blockSize, kC);
				child[2] = new Patch(offsetX+width,	offsetY+width,	width, blockSize, kC);
				child[3] = new Patch(offsetX+width,	offsetY,		width, blockSize, kC);
				
			} else {
				//	We are at top of the tree, create leaf-nodes that will actually be rendered.
				//	These are terrain blocks pulled off the global array.
				int xPos = offsetX/blockSize;
				int yPos = offsetY/blockSize;
				child[0] = gBlocks[yPos][xPos];
				child[1] = gBlocks[yPos + 1][xPos];
				child[2] = gBlocks[yPos + 1][xPos + 1];
				child[3] = gBlocks[yPos][xPos + 1];
			}
			
		}
		
		/**
		*  Render the mesh in this quad-tree patch.
		**/
		final void render(GL gl) {
		
			if (isVisible) {
				//	This patch is at least partly visible, so render each child node.
				for (int i=0; i < 4; ++i)
					child[i].render(gl);
			}
			
		}
		
		/**
		*  Set patch's visibility flag based on triangle orientation.
		*  Examines triangles formed by the eye point, the left &
		*  right frustum points and the corners of the patch.
		*  This method of frustum culling does not work if the camera can
		*  look up or down significantly.
		*
		*  @param  eyeX, eyeY     The grid coordinates of the eye view point.
		*  @param  leftX, leftY   The grid coordinates of the left frustum point.
		*  @param  rightX, rightY The grid coordinates of the right frustum point.
		**/
		final void setVisibility(int eyeX, int eyeY, int leftX, int leftY,
										int rightX, int rightY) {
			//	Set visibility flag.
			int rightVis = cornerVisible(eyeX, eyeY, rightX, rightY);
			int leftVis = cornerVisible(leftX, leftY, eyeX, eyeY);
			isVisible = rightVis != 0 && leftVis != 0;
			
			if (isVisible) {
				if (rightVis == 4 && leftVis == 4) {
					//	This patch is fully visible.  Tell sub-patches.
					for (int i=0; i < 4; ++i)
						child[i].makeVisible();
					
				} else {
					//	This patch is partly visible, update the visibility of it's children.
					for (int i=0; i < 4; ++i)
						child[i].setVisibility(eyeX, eyeY, leftX, leftY, rightX, rightY);
				}
			}
		}
		
		/**
		*  Force this quad-tree patch and all of it's children to be visible.
		**/
		final void makeVisible() {
			isVisible = true;
			for (int i=0; i < 4; ++i)
				child[i].makeVisible();
		}

		/**
		*  Chooses an appropriate mip-map level for all visible terrain blocks.
		*
		*  @param  eyePosition  The world coordinate location of the eye point or
		*                       camera view point [x, y, z].
		**/
		final void chooseMMLevel(float[] eyePosition) {
			if (isVisible) {
				for (int i=0; i < 4; ++i)
					child[i].chooseMMLevel(eyePosition);
			}
		}

		/**
		*  Returns the number of corners of this patch that are visible in
		*  the current view frustum.  If none are visible, 0 is returned.
		*  If all the corners are visible, 4 is returned.
		*  Pass in left frustum limit as "eye" and eye point for "right"
		*  to evaluate the left view frustum limit.
		**/
		private final int cornerVisible(int eyeX, int eyeY, int rightX, int rightY) {
			int vis = 0;
		
			if (orientation(eyeX, eyeY, rightX, rightY, offsetX, offsetY))
				++vis;
			
			int oYpPS = offsetY + width;
			if (orientation(eyeX, eyeY, rightX, rightY, offsetX, oYpPS))
				++vis;
		
			int oXpPS = offsetX + width;
			if (orientation(eyeX, eyeY, rightX, rightY, oXpPS, oYpPS))
				++vis;
		
			if (orientation(eyeX, eyeY, rightX, rightY, oXpPS, offsetY))
				++vis;
			
			return vis;
		}
		
	}
	
	
	/**
	*  This class is a quad-tree node (leaf) that represents the smallest
	*  piece of the terrain height map that is rendered at a time.
	**/
	private class TerrainBlock extends QuadTreeNode {
	
		// Is this quad-tree node visible in the current frame?
		private boolean isVisible = false;
		
		// The bounds of this block in grid coordinates.
		private int offsetX, offsetY, width;
		
		// Square of minimum distance to where a particular mip map level can be used.
		private float[] dMin2;
		
		//	The location of the center of this terrain block in world coordinates.
		private float cx, cy, cz;
		
		//	The current mip-map level.
		private int cLevel;
		
		//	Step size on base terrain map for current mip-map level.
		private int step;
		
		//	Neighboring terrain blocks.
		TerrainBlock north, east, south, west;
		
		
		/**
		*  Construct a TerrainBlock quad-tree node for a piece of our landscape.
		*
		*  @param  offsetX   Offset into the height map of the upper left corner
		*                    of this block (X grid coordinate).
		*  @param  offsetY   Offset into the height map of the upper left corner
		*                    of this block (Y grid coordinate).
		*  @param  width     The width of this block in grid coordinates.
		*  @param  kC        A constant used in calculating mip-map distances.
		**/
		TerrainBlock(int offsetX, int offsetY, int width, float kC) {
			
			this.offsetX = offsetX;
			this.offsetY = offsetY;
			this.width = width;
			
			//	Set up for mip-map levels.
			dMin2 = new float[gMipMapLevels];
			
			//	Calculate dMin^2 for each mip-map level.
			calcDn2(kC);
			
			//	Calculate the center of this terrain block.
			findBlockCenter();
			
		}
		

		/**
		*  Render the mesh in this terrain block.
		**/
		final void render(GL gl) {
		
			if (isVisible) {
				//	This block is visible, so render it.
				
				//	Render the current mip-map level triangles in this block's mesh.
				renderBlock(gl);
				
			}
			
		}
		
		/**
		*  Render the triangles in this terrain block's mesh at the current
		*  geo mip-map level.
		**/
		private void renderBlock(GL gl) {
			//HeightMap altMap = new HeightMapWrapper(elevationMap.getAsArray());		
			//	Deal with neighbors at highter mip-map levels by skipping the edge points
			//	and "blending" them later.
			boolean fixNorth = (north != null && north.cLevel > cLevel);
			boolean fixSouth = (south != null && south.cLevel > cLevel);
			boolean fixEast = (east != null && east.cLevel > cLevel);
			boolean fixWest = (west != null && west.cLevel > cLevel);
			
			int xStart = offsetX;
			int xEnd = xStart + width;
			if (fixWest)	xStart += step;
			if (fixEast)	xEnd -= step;
			
			int yStart = offsetY;
			int yEnd = yStart + width;
			if (fixNorth)	yStart += step;
			if (fixSouth)	yEnd -= step;
 			
 			//	Number of verticies in each triangle strip.
			int vCount = ((xEnd - xStart)/step + 1)*2;
			
			//	Create a triangle strip for each row of the block.
			for (int yPos=yStart; yPos < yEnd; yPos += step) {
				
				//	Fill in vertex array with correct coordinates.
				int idx = 0;
				int yPos2 = yPos + step;
				for (int xPos=xStart; xPos <= xEnd; xPos += step) {
					idx = renderer.addVertex(idx, xPos, yPos,elevationMap.get(xPos, yPos));
					idx = renderer.addVertex(idx, xPos, yPos2,elevationMap.get(xPos, yPos2));
				}
				
				renderer.render(gl,GL.GL_TRIANGLE_STRIP ,vCount);
			}
			
			//	Now do the edge mip-map level blending skipped above.
			if (fixWest)	blendWestEdge(gl, fixNorth, fixSouth);
			if (fixEast)	blendEastEdge(gl, fixNorth, fixSouth);
			if (fixNorth)	blendNorthEdge(gl, fixEast, fixWest);
			if (fixSouth)	blendSouthEdge(gl, fixEast, fixWest);

		}
		
		/**
		*  Set both the vertex in the vertex array and the shading in the color
		*  array.
		*
		*  @param  idx  Index to the next element in the vertex and color arrays.
		*  @param  xPos Horizontal position in the height map.
		*  @param  yPos Vertical position in the height map.
		*  @return The index to the next position in the vertex and color arrays.
		**/
		

		

		
		
		/**
		*  Method that blends in triangles skipped between this block and it's
		*  neighbor to the west.  These triangles were skipped because the neighbor
		*  block has a higher mip map level (is more coarse) than this block.
		**/
		private void blendWestEdge(GL gl, boolean fixNorth, boolean fixSouth) {
		
			//	Retrieve the neighbor step size (bigger than "this.step").
			int nStep = west.step;
			
			//	Use triangle fans to blend in the difference in resolution between this block,
			//	and the neighbor block.
			int last = offsetY + width - nStep;
			int iEnd = offsetY + width;
			int yStart = offsetY + nStep, yEnd = offsetY;
			for (int i=offsetY; i < iEnd; i += nStep) {
				int vCount = 0;
				int idx = 0;
				
				//	Locate the center of the fan.
				int xPos = offsetX;
				int yPos = i;
				idx = renderer.addVertex(idx, xPos, yPos,elevationMap.get(xPos, yPos));
				++vCount;
				
				//	Now add the bottom vertex to the triangle fan.
				yPos += nStep;
				idx = renderer.addVertex(idx, xPos, yPos,elevationMap.get(xPos, yPos));
				++vCount;
				
				//	Deal with the south edge also being at a higher mip-map level.
				if (i == last && fixSouth)
					yStart -= step;
				
				//	Now locate the verticies on this block's side of the fan.
				xPos += step;
				for (yPos=yStart; yPos >= yEnd; yPos -= step) {
					idx = renderer.addVertex(idx, xPos, yPos,elevationMap.get(xPos, yPos));
					++vCount;
				}
				
				//	Deal with the north edge also being at a higher mip-map level.
				if (i == offsetY && fixNorth)
					--vCount;
				
				renderer.render(gl, GL.GL_TRIANGLE_FAN,vCount);
				
				//	Prepare for next triangle fan.
				yStart += nStep;
				yEnd += nStep;
			}
		}
		
		/**
		*  Method that blends in triangles skipped between this block and it's
		*  neighbor to the east.  These triangles were skipped because the neighbor
		*  block has a higher mip map level (is more coarse) than this block.
		**/
		private void blendEastEdge(GL gl, boolean fixNorth, boolean fixSouth) {
			
			//	Retrieve the neighbor step size (bigger than "this.step").
			int nStep = east.step;
			
			//	Use triangle fans to blend in the difference in resolution between this block,
			//	and the neighbor block.
			int last = offsetY + width - nStep;
			int iEnd = offsetY + width;
			int yStart = offsetY, yEnd = offsetY + nStep;
			for (int i=offsetY; i < iEnd; i += nStep) {
				int vCount = 0;
				int idx = 0;
				
				//	Locate the center of the fan.
				int xPos = offsetX + width;
				int yPos = i;
				idx = renderer.addVertex(idx, xPos, yPos,elevationMap.get(xPos, yPos));
				++vCount;
				
				//	Deal with the north edge also at a higher mip-map level.
				if (i == offsetY && fixNorth)
					yStart += step;
				
				//	Deal with the south edge also at a higher mip-map level.
				if (i == last && fixSouth)
					yEnd -= step;
				
				//	Now locate the verticies on this block's side of the fan.
				xPos = offsetX + width - step;
				for (yPos=yStart; yPos <= yEnd; yPos += step) {
					idx = renderer.addVertex(idx, xPos, yPos,elevationMap.get(xPos, yPos));
					++vCount;
				}
				
				//	Locate the last point on the fan.
				xPos = offsetX + width;
				yPos = i + nStep;
				renderer.addVertex(idx, xPos, yPos,elevationMap.get(xPos, yPos));
				++vCount;
				
				renderer.render(gl,GL.GL_TRIANGLE_FAN,vCount);
				
				//	Deal with the north edge also at a higher mip-map level.
				if (i == offsetY && fixNorth)
					yStart -= step;
				
				//	Prepare for next triangle fan.
				yStart += nStep;
				yEnd += nStep;
			}
		}
		
		/**
		*  Method that blends in triangles skipped between this block and it's
		*  neighbor to the north.  These triangles were skipped because the neighbor
		*  block has a higher mip map level (is more coarse) than this block.
		**/
		private void blendNorthEdge(GL gl, boolean fixEast, boolean fixWest) {
			
			//	Retrieve the neighbor step size (bigger than "this.step").
			int nStep = north.step;
			
			//	Use triangle fans to blend in the difference in resolution between this block,
			//	and the neighbor block.
			int last = offsetX + width - nStep;
			int iEnd = offsetX + width;
			int xStart = offsetX, xEnd = offsetX + nStep;			
			for (int i=offsetX; i < iEnd; i += nStep) {
				int vCount = 0;
				int idx = 0;
				
				//	Locate the center of the fan.
				int xPos = i;
				int yPos = offsetY;
				idx = renderer.addVertex(idx, xPos, yPos,elevationMap.get(xPos, yPos));
				++vCount;
				
				//	Deal with west edge also at a higher mip-map level.
				if (i == offsetX && fixWest)
					xStart += step;

				//	Deal with east edge also at a higher mip-map level.
				if (i == last && fixEast)
					xEnd -= step;
				
				//	Now locate the verticies on this block's side of the fan.
				yPos += step;
				for (xPos=xStart; xPos <= xEnd; xPos += step) {
					idx = renderer.addVertex(idx, xPos, yPos,elevationMap.get(xPos, yPos));
					++vCount;
				}
				
				//	Now locate the last point on the fan.
				xPos = i + nStep;
				yPos = offsetY;
				renderer.addVertex(idx, xPos, yPos,elevationMap.get(xPos, yPos));
				++vCount;
				
				renderer.render(gl,GL.GL_TRIANGLE_FAN,vCount);
				
				//	Deal with west edge also at a higher mip-map level.
				if (i == offsetX && fixWest)
					xStart -= step;
					
				//	Prepare for next triangle fan.
				xStart += nStep;
				xEnd += nStep;
			}
			
		}
		
		/**
		*  Method that blends in triangles skipped between this block and it's
		*  neighbor to the south.  These triangles were skipped because the neighbor
		*  block has a higher mip map level (is more coarse) than this block.
		**/
		private void blendSouthEdge(GL gl, boolean fixEast, boolean fixWest) {
		
			//	Retrieve the neighbor step size (bigger than "this.step").
			int nStep = south.step;
			
			//	Use triangle fans to blend in the difference in resolution between this block,
			//	and the neighbor block.
			int last = offsetX + width - nStep;
			int iEnd = offsetX + width;
			int xStart = offsetX + nStep, xEnd = offsetX;
			for (int i=offsetX; i < iEnd; i += nStep) {
				int vCount = 0;
				int idx = 0;
				
				//	Locate the center of the fan.
				int xPos = i;
				int yPos = offsetY + width;
				idx = renderer.addVertex(idx, xPos, yPos,elevationMap.get(xPos, yPos));
				++vCount;
				
				//	Locate the next point in the fan.
				xPos += nStep;
				idx = renderer.addVertex(idx, xPos, yPos,elevationMap.get(xPos, yPos));
				++vCount;
				
				//	Deal with the east edge also at a higher mip-map level.
				if (i == last && fixEast)
					xStart -= step;
				
				//	Now locate the verticies on this block's side of the fan.
				yPos -= step;
				for (xPos=xStart; xPos >= xEnd; xPos -= step) {
					idx = renderer.addVertex(idx, xPos, yPos,elevationMap.get(xPos, yPos));
					++vCount;
				}
				
				//	Deal with the west edge also at a higher mip-map level.
				if (i == offsetX && fixWest)
					--vCount;
					
				renderer.render(gl,GL.GL_TRIANGLE_FAN,vCount);
				
				//	Deal with the west edge also at a higher mip-map level.
				if (i == last && fixEast)
					xStart += step;
					
				//	Prepare for next triangle fan.
				xStart += nStep;
				xEnd += nStep;
			}
		}
		

		
		/**
		*  Set block's visibility flag based on triangle orientation.
		*  Examines triangles formed by the eye point, the left &
		*  right frustum points and the corners of the block.
		*  This method of frustum culling does not work if the camera can
		*  look up or down significantly.
		*
		*  @param  eyeX, eyeY     The grid coordinates of the eye view point.
		*  @param  leftX, leftY   The grid coordinates of the left frustum point.
		*  @param  rightX, rightY The grid coordinates of the right frustum point.
		**/
		final void setVisibility(int eyeX, int eyeY, int leftX, int leftY,
										int rightX, int rightY) {
			//	Set visibility flag.
			isVisible = cornerVisible(eyeX, eyeY, rightX, rightY) && cornerVisible(leftX, leftY, eyeX, eyeY);
			
		}
		
		/**
		*  Returns true if any one corner of this patch is visible
		*  based on the eye point and the right view frustum limit.
		*  Pass in left frustum limit as "eye" and eye point for "right"
		*  to evaluate the left view frustum limit.
		**/
		private boolean cornerVisible(int eyeX, int eyeY, int rightX, int rightY) {
			if (orientation(eyeX, eyeY, rightX, rightY, offsetX, offsetY))
				return true;
			
			int oYpPS = offsetY + width;
			if (orientation(eyeX, eyeY, rightX, rightY, offsetX, oYpPS))
				return true;
			
			int oXpPS = offsetX + width;
			if (orientation(eyeX, eyeY, rightX, rightY, oXpPS, oYpPS))
				return true;
			
			if (orientation(eyeX, eyeY, rightX, rightY, oXpPS, offsetY))
				return true;
				
			return false;
		}
		
		/**
		*  Force this terrain block to be visible.
		**/
		final void makeVisible() {
			isVisible = true;
		}
		
		/**
		*  Chooses an appropriate mip-map level for all visible terrain blocks.
		*
		*  @param  eyePosition  The world coordinate location of the eye point or
		*                       camera view point [x, y, z].
		**/
		final void chooseMMLevel(float[] eyePosition) {
		
			if (isVisible) {
				//	Calculate distance from eye point to center of terrain block.
				float dx = eyePosition[0] - cx;
				float dy = eyePosition[1] - cy;
				float dz = eyePosition[2] - cz;
				
				//	Distance squared.
				float d2 = dx*dx + dy*dy + dz*dz;
				
				//	Pick mip-map level and step size.
				cLevel = 0;
				step = 1;
				int maxLevel = gMipMapLevels-1;
				while (cLevel < maxLevel && d2 > dMin2[cLevel+1]) {
					++cLevel;
					step *=2;
				}
				
			}
		}

		
		/**
		*  Change the threshold value used for choosing the appropriate
		*  mip-map level.
		**/
		final void changeThreshold(int tau) {
			float factor = gThreshold*gThreshold/(float)(tau*tau);
			
			//	Loop over each mip-map level.
			int numLevels = dMin2.length;
			for (int level=1; level < numLevels; ++level) {
				dMin2[level] *= factor;
			}
			
		}
		
		/**
		*  Calculates the minimum distance squared (dMin^2) for each mip map
		*  level in this terrain block.
		**/
		private void calcDn2(float kC) {
		
			//	Square kC factor.
			kC *= kC;
			
			//	dMin for 1st level is always 0.
			dMin2[0] = 0;
			
			float deltaMax = 0;
			
			//	Loop over each mip-map level.
			int step = 2;
			int numLevels = dMin2.length;
			for (int level=1; level < numLevels; ++level) {
				
				//	Loop over all the points in the block calculating deltas.
				int endY = width + offsetY;
				int endX = width + offsetX;
				for (int i=offsetY; i < endY; ++i) {
					int posY = i/step;
					posY *= step;
					for (int j=offsetX; j < endX; ++j) {
						if (i%step != 0 || j%step != 0) {
							int posX = j/step;
							posX *= step;
							float delta = biLinearInterp(posX, posX+step, posY, posY+step, j, i);
							delta -= elevationMap.get(j, i);
							delta = Math.abs(delta);
							deltaMax = Math.max(deltaMax, delta);
						}
					}
					
				}
				
				//	Save off maximum delta^2 * C^2;
				dMin2[level] = deltaMax*deltaMax*kC;
				
				
				//	Prepare for next level.
				step *= 2;
			}
		}
		
		/**
		*  Interpolate a height value out of the height map for the given
		*  indexes.
		**/
		private float biLinearInterp(int lx, int hx, int ly, int hy, int tx, int ty) {
			float s00 = elevationMap.get(lx, ly);
			float s01 = elevationMap.get(hx, ly);
			float s10 = elevationMap.get(lx, hy);
			float s11 = elevationMap.get(hx, hy);
			
			int dx = hx - lx;
			int dtx = tx - lx;
			float v0 = (s01 - s00)/dx*dtx + s00;
			float v1 = (s11 - s10)/dx*dtx + s10;
			float value = (v1 - v0)/(hy - ly)*(ty - ly) + v0;
			
			return value;
		}
		
		/**
		*  Finds the 3D center point of this terrain block in world coordinates.
		**/
		private void findBlockCenter() {
			
			//	First, find min/max altitude in this block.
			float minAlt = Float.MAX_VALUE;
			float maxAlt = -minAlt;
			int endY = width + offsetY;
			int endX = width + offsetX;
			for (int i=offsetY; i < endY; ++i) {
				for (int j=offsetX; j < endX; ++j) {
					int alt = (int)elevationMap.get(j, i);
					minAlt = Math.min(minAlt, alt);
					maxAlt = Math.max(maxAlt, alt);
				}
			}
			
			//	The cy coordinate is the average altitude of this block.
			cy = (minAlt + maxAlt)/2;
			
			//	The cx and cz coordinates are in the center of the square.
			float wo2 = width*gGridSpacingX/2;
			cx = offsetX*gGridSpacingX + wo2;
			cz = offsetY*gGridSpacingY + wo2;
		}
		
	}
	
}
