Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

creative1

my ROAM 2.0 implementation (how to avoid popping?)

This topic is 5282 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I ported the roam 2.0 implementation of Trent Polack's book 'focus on 3d terrain programming' to c# and directx. (I asked for his permission to post this question here). The problem I am having is that it runs a little slow (his code goes faster because it is c++). You might say that it is c#'s fault since it won't be as fast as C++ but I don't think I agree. I was expecting it to run slower than C++ but not so slow (15/20 fps in a p4 2.5 and 512 megas with a 4096x4096 terrain) I am sure it can be improved. Also there is alot of popping that I don't know how to fix. Anyway, here is my code, I hope you guys can help me and hopefully this code will also help anyone interested in a roam 2.0 implementation. (edited): Found a way to make it a little faster. Now it goes up to 50fps for 4096^2 terrain. I changed the code accordingly. My main question now is how can I scale it and avoid popping? I added a scale variable to the code but it doesn't work well. This terrain is 4096^2 but I want to make it doble the size. How can I do this? I multiply all the x,y,z by the scale value (2) but then the whole system doesn't work properly. Popping is very very noticeable. Any suggestions to modify my code?
using System;
using System.Drawing;
using System.Windows.Forms;
using Microsoft.DirectX;
using Microsoft.DirectX.Direct3D;


	class SROAM_DIAMOND
	{
		public SROAM_DIAMOND [] m_pParent=new SROAM_DIAMOND[4];	//diamond's parents (two corners)

		public SROAM_DIAMOND [] m_pChild=new SROAM_DIAMOND[4];		//diamond's kids

		public SROAM_DIAMOND m_pPrevDmnd, m_pNextDmnd;		//prev and next links on queue or free list


		public float [] m_fVert=new float[3];					//vertex position

		public float m_fBoundRad;							//radius of the diamond's bounding sphere

		public float m_fErrorRad;							//radius of pointwise error squared


		public short m_sQueueIndex;
		public ushort [] m_usTriIndex=new ushort[2];

		public byte [] m_cChildIndex=new byte[2];			//our kid index within each of our parents

		public sbyte m_cLevel;								//level of resolution

		public byte m_ucLockCount;				//number of references (if 0, the diamond is free for use)

		public byte m_ucFrameCount;
		public byte m_ucCull;
		public byte m_ucFlags;
		public byte m_ucSplitFlags;
		public byte [] m_ucPadding=new byte[3];
		public int index=0; // index of the diamon in the pool array

		public static SROAM_DIAMOND empty=new SROAM_DIAMOND();
	};

	public struct StructHeightMap
	{
		public byte [,] m_ucpData;	//the height data

		public int m_iSize;				//the height size (must be a power of 2)

	}

public class Terrain 
{
	public StructHeightMap HeightMap;
	int m_iVertsPerFrame;		//stat variables

	int m_iTrisPerFrame;
	public Texture map;
	int heightmapwidth=4096;
	int scale=1;


	int m_iSize;
	Vector3 m_vecScale;

	/// <summary>

	/// number of buckets in priority queue

	/// </summary>

	static int IQMAX       =  4096;

	/// <summary>

	/// number of triangle-chunk slots

	/// </summary>

	int TRI_IMAX    = 65536;

	/// <summary>

	/// frustum bitmasks

	/// </summary>

	byte CULL_ALLIN =0x3f;
	/// <summary>

	/// frustum bitmasks

	/// </summary>

	byte CULL_OUT   =0x40;

	//misc. diamond flags

	byte ROAM_SPLIT    =0x01;
	byte ROAM_TRI0     =0x04;
	byte ROAM_CLIPPED  =0x10;
	byte ROAM_SPLITQ   =0x40;
	byte ROAM_MERGEQ   =0x80;
	byte ROAM_ALLQ    = 0xc0;
	byte ROAM_UNQ     = 0x00;


	//parent/child split flags

	byte SPLIT_K0     = 0x01;
	byte SPLIT_K      = 0x0f;
	byte SPLIT_P0     = 0x10;
	byte SPLIT_P      = 0x30;

	Camera m_pCamera;

	/// <summary>

	/// diamond storage pool

	/// </summary>

	SROAM_DIAMOND [] m_pDmndPool;

	/// <summary>

	/// pool size (number of diamonds)

	/// </summary>

	int m_iPoolSize;

	/// <summary>

	/// most recently unlocked diamonds

	/// </summary>

	SROAM_DIAMOND [] m_pFreeDmnd=new SROAM_DIAMOND[2];

	/// <summary>

	/// base diamonds level 0

	/// </summary>

	SROAM_DIAMOND [,] m_pLevel0Dmnd=new SROAM_DIAMOND[4,4];

	/// <summary>

	/// base diamonds level -1,-2...

	/// </summary>

	SROAM_DIAMOND [,] m_pLevel1Dmnd=new SROAM_DIAMOND[4,4];

	/// <summary>

	/// split priority queue

	/// </summary>

	SROAM_DIAMOND [] m_pSplitQueue=new SROAM_DIAMOND[IQMAX];

	/// <summary>

	/// merge priority queue

	/// </summary>

	SROAM_DIAMOND [] m_pMergeQueue=new SROAM_DIAMOND[IQMAX];

	/// <summary>

	/// min/max occupied bucket

	/// </summary>

	int m_iPQMin, m_iPQMax;	

	/// <summary>

	/// packed diamond index and side (left or right)

	/// </summary>

	int [] m_ipPDmndIS;	

	/// <summary>

	/// number of elements on free list

	/// </summary>

	int m_iFreeElements;

	int m_iFrameCount;								//current frame count

	int m_iQueueCoarse;								//coarseness limit on priority index

	int m_iMaxTriChunks;							//max number of tri chunks allowed


	/// <summary>

	/// number of triangles on free list

	/// </summary>

	int m_iFreeTriCount;

	/// <summary>

	/// target triangle count

	/// </summary>

	int m_iMaxTris;	

	/// <summary>

	/// first free tri chunk

	/// </summary>

	int m_iFreeTri;

	int [] m_iLog2Table=new int[256];				//correction to float->int conversions

		
	CustomVertex.PositionColoredTextured[] m_fVertTexBuffer; //data attachment specific to a library step


	float [] m_fpLevelMDSize;							//max midpoint displacement per level

	int m_iMaxLevel;

	/// <summary>

	/// Load a grayscale height map

	/// </summary>

	/// <param name="szFilename">the file name of the height map</param>

	/// <returns></returns>

	public bool LoadHeightMap(string szFilename )
	{
		Bitmap im=new Bitmap(@"ps_height_4k.png");
			
	//	int size=65536; // im.Width*im.Width;

		HeightMap.m_iSize=heightmapwidth*heightmapwidth;
		HeightMap.m_ucpData=new byte[heightmapwidth,heightmapwidth];

		for (int y=0; y<heightmapwidth; y++) 
		{
			for (int x=0; x<heightmapwidth; x++) 
			{
				HeightMap.m_ucpData[x,y]=im.GetPixel(x,y).R;
			}
		}

		m_iSize= heightmapwidth;
		im.Dispose();

		return true;
	}


	/// <summary>

	/// Initialize the ROAM engine

	/// </summary>

	/// <param name="iMaxLevel"></param>

	/// <param name="iPoolSize"></param>

	/// <param name="vb"></param>

	/// <param name="pCamera"></param>

	public void Init( int iMaxLevel, int iPoolSize, VertexBuffer vb, Camera pCamera )
	{
		SROAM_DIAMOND pDmnd, pTempDmnd0, pTempDmnd1;

		int iLevel, i, j, k, di, dj, ix, jx;

		//initialize the ROAM engine

		m_iQueueCoarse= 1990;			//"magic number" for the queue "fineness"

		m_iFrameCount = 0;

		m_iMaxLevel    = iMaxLevel;
		m_fpLevelMDSize= new float [m_iMaxLevel+1];

		//generate table of displacement sizes versus levels

		for( iLevel=0; iLevel <= m_iMaxLevel; iLevel++ )
			m_fpLevelMDSize[iLevel]= 255.0f/( ( float )Math.Sqrt( ( float )( ( long )1<<iLevel ) ) );

		//create diamond store, free list

		//allocate diamond and hash table arrays

		m_iPoolSize = iPoolSize;
		m_pDmndPool= new SROAM_DIAMOND[m_iPoolSize];

		m_fVertTexBuffer = new CustomVertex.PositionColoredTextured[m_iPoolSize*3];

		for (i=0; i<m_iPoolSize; i++) 
		{
			m_pDmndPool[i]=new SROAM_DIAMOND();
			m_pDmndPool[i].index=i;
		}

		m_iMaxTriChunks= TRI_IMAX;
		m_ipPDmndIS= new int [m_iMaxTriChunks];

		//allocate memory for the vertex/texture coordinates


		// create a double linked list (prev and next)

		for( i=0; i + 1 < m_iPoolSize; i++ )
		{
			pTempDmnd0= m_pDmndPool[i];
			pTempDmnd1= m_pDmndPool[ i + 1];

			pTempDmnd0.m_pNextDmnd= pTempDmnd1;
			pTempDmnd1.m_pPrevDmnd= pTempDmnd0;
		}

		// set the most recently unlocked diamons from the beginning of the list

		m_pFreeDmnd[0]= m_pDmndPool[0];
		// and the end of the list

		m_pFreeDmnd[1]= m_pDmndPool[ m_iPoolSize - 1 ];
		m_pFreeDmnd[0].m_pPrevDmnd= null;
		m_pFreeDmnd[1].m_pNextDmnd= null;

		// all elements are free at this point of initialization

		m_iFreeElements= m_iPoolSize;

		//initialize diamonds to be NEW and FREE

		for( i=0; i < m_iPoolSize; i++ )
		{
			pTempDmnd0= m_pDmndPool[i];

			pTempDmnd0.m_fBoundRad= -1;		//indicated a NEW diamond

			pTempDmnd0.m_ucLockCount= 0;
			pTempDmnd0.m_ucFlags= 0;
			pTempDmnd0.m_ucFrameCount= 255;

			pTempDmnd0.m_pParent[2]= pTempDmnd0.m_pParent[3]= null;
		
			pTempDmnd0.m_ucCull= 0;
			pTempDmnd0.m_cChildIndex[0]= pTempDmnd0.m_cChildIndex[1]= 0;
			pTempDmnd0.m_sQueueIndex= (short)(IQMAX/2);
			
			// no children

			pTempDmnd0.m_pChild[0]= pTempDmnd0.m_pChild[1]= pTempDmnd0.m_pChild[2]= pTempDmnd0.m_pChild[3]= null;
			
			pTempDmnd0.m_cLevel= -100;
			
			pTempDmnd0.m_pParent[0]= pTempDmnd0.m_pParent[1]= null;
			
			pTempDmnd0.m_fErrorRad= 10.0f;
		}

		//clear the split/merge priority queues

		for( i= 0; i < IQMAX; i++ )
		{
			m_pSplitQueue[i]= m_pMergeQueue[i]= null;
		}
		m_iPQMax= -1;
		m_iPQMin= IQMAX;

		//clear the triangle render-list

		for( i=0; i<m_iMaxTriChunks; i++ )
			m_ipPDmndIS[i]= -1;

		m_iFreeTri= 1;
		m_iTrisPerFrame= 0;
		m_iFreeTriCount= m_iMaxTriChunks - 1;
		m_iMaxTris= 30000;			//set the default maximum triangle count (max triangles visible per frame)


		//generate a LUT for float->int conversations (huge speed-saver later on)

		for( i=0; i<256; i++ )
			m_iLog2Table[i]= calculatethis(i);

		//allocate base diamonds, and set their information (minus link info)

		for( k=0; k<32; k++ )
		{
			//initialization code for dimaonds 0-15

			if( k<16 )
			{
				j= k/4;
				i= k%4;
				
				m_pLevel0Dmnd[j,i]= pDmnd= Create( );
				pDmnd.m_fVert[0]= ( 2.0f*( float )( i - 1 ) );
				pDmnd.m_fVert[2]= ( 2.0f*( float )( j - 1 ) );
			}
				//initialization for diamonds 15-31

			else
			{
				j= ( k - 16 )/4;
				i= ( k - 16 )%4;
				
				m_pLevel1Dmnd[j,i]= pDmnd= Create( );
				pDmnd.m_fVert[0]= ( 2.0f*( float )i - 3.0f );
				pDmnd.m_fVert[2]= ( 2.0f*( float )j - 3.0f );
			}

			//shift the previous coords from [-3, 3] to [0, m_iSize-1]

			ShiftCoords( ref pDmnd.m_fVert[0], ref pDmnd.m_fVert[2] );

			//clamp the coordinates to the map size (prevent a buffer overflow)

			CLAMP( ref pDmnd.m_fVert[0], 0, ( (m_iSize*scale)-1 ) );
			CLAMP( ref pDmnd.m_fVert[2], 0, ( (m_iSize*scale)-1 ) );

			pDmnd.m_fVert[1]= ( float )GetTrueHeightAtPoint( ( int )( Math.Abs( pDmnd.m_fVert[0] ) ),
				( int )( Math.Abs( pDmnd.m_fVert[2] ) ) );
			pDmnd.m_usTriIndex[0]= pDmnd.m_usTriIndex[1]= 0;

			pDmnd.m_fBoundRad= ( float )m_iSize * m_iSize * scale * scale;
			pDmnd.m_fErrorRad= ( float )m_iSize * scale;

			//reset all links

			pDmnd.m_pParent[0]= pDmnd.m_pParent[1]= pDmnd.m_pParent[2]= pDmnd.m_pParent[3]= null;
			pDmnd.m_pChild[0] = pDmnd.m_pChild[1] = pDmnd.m_pChild[2] = pDmnd.m_pChild[3] = null;

			pDmnd.m_cLevel= (sbyte)( k < 16 ? 0 : ( ( ( i^j ) & 1 ) != 0 ? -1 : -2 ) );
			pDmnd.m_ucCull = 0;
			pDmnd.m_ucFlags= 0;
			pDmnd.m_ucSplitFlags= 0;
			pDmnd.m_sQueueIndex= (short)(IQMAX - 1);

			if( k<16 && k!=5 )
				pDmnd.m_ucFlags|= ROAM_CLIPPED;
			if( pDmnd.m_cLevel<0 )
				pDmnd.m_ucFlags|= ROAM_SPLIT;
		}

		//now that all of the diamonds exist, we need to set their links

		for( k=0; k<16; k++ )
		{
			j= k/4;
			i= k%4;
		
			//links for the iLevel 0 diamonds

			pDmnd=m_pLevel0Dmnd[j,i];
			di= ( ( ( i^j ) & 1 ) != 0 ? 1 : -1 );
			dj= 1;
			ix= ( ( 2*i + 1 - di )>>1 )%4;
			jx= ( ( 2*j + 1 - dj )>>1 )%4;
			pDmnd.m_pParent[0]= m_pLevel1Dmnd[jx,ix];
			
			ix= ( ( 2*i + 1 + di )>>1 )%4;
			jx= ( ( 2*j + 1 + dj )>>1 )%4;
			pDmnd.m_pParent[1]= m_pLevel1Dmnd[jx,ix];
			
			ix= ( ( 2*i + 1 - dj )>>1 )%4;
			jx= ( ( 2*j + 1 + di )>>1 )%4;
			pDmnd.m_pParent[2]= m_pLevel1Dmnd[jx,ix];
			
			ix= ( ( 2*i + 1 + dj )>>1 )%4;
			jx= ( ( 2*j + 1 - di )>>1 )%4;
			pDmnd.m_pParent[3]= m_pLevel1Dmnd[jx,ix];
			
			ix= ( di < 0 ? 0 : 3 );
			pDmnd.m_pParent[0].m_pChild[ix]= pDmnd;
			pDmnd.m_cChildIndex[0]= (byte)ix;
			
			ix= ( di < 0 ? 2 : 1 );
			pDmnd.m_pParent[1].m_pChild[ix]= pDmnd;
			pDmnd.m_cChildIndex[1]= (byte)ix;
		}

		for( k=0; k<16; k++ )
		{
			j= k/4;
			i= k%4;
		
			//links for the iLevel -1 diamonds

			pDmnd=m_pLevel1Dmnd[j,i];
			pDmnd.m_pParent[3]= m_pLevel1Dmnd[( j+3 )%4,i];
			pDmnd.m_pParent[2]= m_pLevel1Dmnd[( j+1 )%4,i];
			pDmnd.m_pParent[0]= m_pLevel1Dmnd[j,( i+3 )%4];
			pDmnd.m_pParent[1]= m_pLevel1Dmnd[j,( i+1 )%4];
		}

		//put the top-iLevel diamond on the split queue (and we can work from there

		pDmnd= m_pLevel0Dmnd[1,1];
		Enqueue( pDmnd, ROAM_SPLITQ, IQMAX-1 );

		//get the base tris

		AllocateTri( pDmnd, 0 );
		AllocateTri( pDmnd, 1 );

	//	vb.Unlock();

		//set the class's camera pointer

		m_pCamera= pCamera;
	}

	/// <summary>

	/// Put the value x between the range min/max

	/// </summary>

	/// <param name="x"></param>

	/// <param name="min"></param>

	/// <param name="max"></param>

	private void CLAMP(ref float x, int min, int max) 
	{
		x= ( x<min  ? min : x<max ? x : max );
	}

	/// <summary>

	/// A function to get the true height value (0-255) at a point X, Z

	/// </summary>

	/// <param name="x"></param>

	/// <param name="z"></param>

	/// <returns></returns>

	private int GetTrueHeightAtPoint( int x, int z ) 
	{
		return HeightMap.m_ucpData[x/scale,z/scale]*scale; // [( z*m_iSize )+x];

	}


	/// <summary>

	/// "Re-queue" a diamond in the appropriate queue

	/// </summary>

	/// <param name="pDmnd"></param>

	/// <param name="iQueueFlags"></param>

	/// <param name="iNewPQIndex"></param>

	private void Enqueue( SROAM_DIAMOND pDmnd, int iQueueFlags, int iNewPQIndex )
	{
		SROAM_DIAMOND [] pQueue;
		SROAM_DIAMOND pDmndX;
		// SROAM_DIAMOND** pQueue, *pDmndX;

		int i, iDmndLock;

		//return early if the diamond is already in the queue

		if( ( pDmnd.m_ucFlags & ROAM_ALLQ )==iQueueFlags && pDmnd.m_sQueueIndex==iNewPQIndex )
			return;

		//determine the overall change in the diamond lock count

		iDmndLock= 0;
		if(( pDmnd.m_ucFlags & ROAM_ALLQ ) != 0)
			iDmndLock--;
		if(( iQueueFlags & ROAM_ALLQ ) != 0)
			iDmndLock++;

		//remove the diamond from the old queue (if needed)

		if(( pDmnd.m_ucFlags & ROAM_ALLQ )!= 0)
		{
			pQueue= ( (( pDmnd.m_ucFlags & ROAM_SPLITQ ) != 0) ? m_pSplitQueue : m_pMergeQueue );
			if( pDmnd.m_pPrevDmnd != null )
				pDmnd.m_pPrevDmnd.m_pNextDmnd= pDmnd.m_pNextDmnd;
			else
			{
				pQueue[pDmnd.m_sQueueIndex]= pDmnd.m_pNextDmnd;
				if( pDmnd.m_pNextDmnd == null )
				{
					if(( pDmnd.m_ucFlags & ROAM_SPLITQ ) != 0)
					{
						if( pDmnd.m_sQueueIndex==m_iPQMax )
						{
							pDmndX= pQueue[0];
							pQueue[0]= SROAM_DIAMOND.empty;

							//loop until we get 'i' where we want it

							for( i=pDmnd.m_sQueueIndex; pQueue[i] == null; i-- )
								;
							if( (( pQueue[0]= pDmndX ) == null) && i==0 )
								i--;
							m_iPQMax= i;
						}
					}
					else
					{
						if( pDmnd.m_sQueueIndex==m_iPQMin )
						{
							pDmndX= pQueue[IQMAX-1];
							pQueue[IQMAX-1]= SROAM_DIAMOND.empty;

							//loop until we get 'i' where we want it

							for( i= pDmnd.m_sQueueIndex; pQueue[i] == null; i++ )
								;
							if( (( pQueue[IQMAX-1]= pDmndX )==null) && i==IQMAX-1 )
								i++;
							m_iPQMin= i;
						}
					}
				}
			}
			if( pDmnd.m_pNextDmnd != null )
				pDmnd.m_pNextDmnd.m_pPrevDmnd= pDmnd.m_pPrevDmnd;
			pDmnd.m_ucFlags = (byte)(pDmnd.m_ucFlags & (~ROAM_ALLQ));
		}

		//update the diamond's priority

		pDmnd.m_sQueueIndex= (short)iNewPQIndex;

		//insert the diamond into the new queue if needed

		if(( iQueueFlags & ROAM_ALLQ ) != 0)
		{
			//insert into the necessary queue bucket (split or merge)

			pQueue= ( (( iQueueFlags & ROAM_SPLITQ ) != 0) ? m_pSplitQueue : m_pMergeQueue );
			pDmnd.m_pPrevDmnd= null;
			pDmnd.m_pNextDmnd= pQueue[pDmnd.m_sQueueIndex];

			pQueue[pDmnd.m_sQueueIndex]= pDmnd;
			if( pDmnd.m_pNextDmnd != null)
				pDmnd.m_pNextDmnd.m_pPrevDmnd= pDmnd;
			else
			{
				if(( iQueueFlags & ROAM_SPLITQ ) != 0)
				{
					if( pDmnd.m_sQueueIndex>m_iPQMax )
						m_iPQMax= pDmnd.m_sQueueIndex;
				}
				else
				{
					if( pDmnd.m_sQueueIndex<m_iPQMin )
						m_iPQMin= pDmnd.m_sQueueIndex;
				}
			}

			//specify which queue the current diamond is in

			pDmnd.m_ucFlags = (byte)(pDmnd.m_ucFlags | iQueueFlags);
		}

		//perform any required locking/unlocking

		if( iDmndLock!=0 )
		{
			if( iDmndLock<0 )
				Unlock( pDmnd );
			else
				Lock( pDmnd );
		}
	}

	/// <summary>

	/// Create a new diamond

	/// </summary>

	/// <returns></returns>

	private SROAM_DIAMOND Create()
	{
		SROAM_DIAMOND pDmnd;

		//recycle the least recently used diamond

		pDmnd= m_pFreeDmnd[0];
		if( pDmnd == null )
		{
			MessageBox.Show("Out of ROAM diamond storage");
			Application.Exit();
		}

		//if the diamond is not NEW, reset its links

		if( pDmnd.m_fBoundRad >= 0.0f )
		{
			pDmnd.m_pParent[0].m_pChild[pDmnd.m_cChildIndex[0]]= null;
			Unlock( pDmnd.m_pParent[0] );
		
			pDmnd.m_pParent[1].m_pChild[pDmnd.m_cChildIndex[1]]= null;
			Unlock( pDmnd.m_pParent[1] );
			pDmnd.m_sQueueIndex= (byte)(IQMAX>>1);
		}
		else
			pDmnd.m_fBoundRad= 0.0f;	//set diamond to NEW


		//make sure that the frame count is old (so we can perform updates and such)

		pDmnd.m_ucFrameCount= (byte) (( m_iFrameCount-1 ) & 255);

		//lock the gathered diamond and return it for use

		Lock( pDmnd );
		return pDmnd;
	}


	/// <summary>

	/// Lock the child to prevent a "diamond discharge"

	/// </summary>

	/// <param name="pDmnd"></param>

	private void Lock( SROAM_DIAMOND pDmnd )
	{
		SROAM_DIAMOND pPrevDmnd, pNextDmnd;

		//remove from free list if first reference

		if( pDmnd.m_ucLockCount==0 )
		{
			pPrevDmnd= pDmnd.m_pPrevDmnd;
			pNextDmnd= pDmnd.m_pNextDmnd;

			if( pPrevDmnd != null)
				pPrevDmnd.m_pNextDmnd= pNextDmnd;
			else
				m_pFreeDmnd[0]= pNextDmnd;

			if( pNextDmnd != null)
				pNextDmnd.m_pPrevDmnd= pPrevDmnd;
			else
				m_pFreeDmnd[1]= pPrevDmnd;

			m_iFreeElements--;
		}
	
		pDmnd.m_ucLockCount++;
	}

	/// <summary>

	/// Unlock the child so it may be used by others

	/// </summary>

	/// <param name="pDmnd"></param>

	private void Unlock( SROAM_DIAMOND pDmnd )
	{
		SROAM_DIAMOND pPrevDmnd;

		pDmnd.m_ucLockCount--;

		//add to free list if no references left

		if( pDmnd.m_ucLockCount==0 )
		{
			pPrevDmnd= m_pFreeDmnd[1];

			pDmnd.m_pPrevDmnd= pPrevDmnd;
			pDmnd.m_pNextDmnd= null;

			if( pPrevDmnd != null)
				pPrevDmnd.m_pNextDmnd= pDmnd;
			else
				m_pFreeDmnd[0]= pDmnd;

			m_pFreeDmnd[1]= pDmnd;

			m_iFreeElements++;
		}
	}

	/// <summary>

	/// Scale an (x, z) vertex (coordinates to shift)

	/// </summary>

	/// <param name="x"></param>

	/// <param name="z"></param>

	private void ShiftCoords( ref float x, ref float z )
	{
		x= ( x+1.0f )/2.0f;	//shift X into [0, 2] then divide by two shift into [0...1]

		z= ( z+1.0f )/2.0f;	//shift Z into [0, 2] then divide by two shift into [0...1]


		x*= m_iSize*scale;			//translate into map-coords

		z*= m_iSize*scale;			//translate into map-coords

	}

	/// <summary>

	/// Allocate a triangle for the triangle render list

	/// Arguments:	 -pDmnd: pointer to a diamond

	//				 -j: side index

	/// </summary>

	/// <param name="pDmnd"></param>

	/// <param name="j"></param>

	private void AllocateTri( SROAM_DIAMOND pDmnd, int j )
	{
		byte iFlags;

		//CLIPPED diamonds never have triangles

		if( (pDmnd.m_ucFlags & ROAM_CLIPPED) != 0 )
			return;

		iFlags= pDmnd.m_pParent[j].m_ucFlags;

		//CLIPPED parent j means no triangle on iSide j

		if (( iFlags & ROAM_CLIPPED ) != 0)
			return;

		//indicate that the triangle on side j is active

		pDmnd.m_ucFlags |= (byte)(ROAM_TRI0 << j);

		//if not IN, take the triangle off of the OUT list

		if( ( pDmnd.m_ucCull & CULL_OUT ) == 0 )
			AddTri( pDmnd, j );
	}

	/// <summary>

	/// Add a triangle to the render list

	/// </summary>

	/// <param name="pDmnd"></param>

	/// <param name="j"></param>

	private void AddTri( SROAM_DIAMOND pDmnd, int j )
	{
		SROAM_DIAMOND [] pDmndTable= new SROAM_DIAMOND[3];
		int fvVB;
		int i, vi;

		/* grab free tri and fill in */
		//get a free triangle and "fill" it in 

		i= m_iFreeTri++;
		if( i>=m_iMaxTriChunks )
		{
			MessageBox.Show("roam: out of triangle memory\n" );
			/* should deal with this more gracefully... */
			Application.Exit();
		}
		m_iFreeTriCount--;
		pDmnd.m_usTriIndex[j]= (ushort)i;


		// index position of pDmnd in m_pDmndPool shifted one bit to the left and inserted the

		// side J (1 or 0)

		m_ipPDmndIS[i]= (pDmnd.index <<1 ) | j;


		//fill in the information for the triangle

		pDmndTable[1]= pDmnd.m_pParent[j];
		if( j != 0 )
		{
			pDmndTable[0]= pDmnd.m_pParent[3];
			pDmndTable[2]= pDmnd.m_pParent[2];
		}
		else
		{
			pDmndTable[0]= pDmnd.m_pParent[2];
			pDmndTable[2]= pDmnd.m_pParent[3];
		}

		//fill the vertex buffer with the information


		// we draw triangles, that is 3 vertices per each triangle

		fvVB= i*3; 

		for( vi=0; vi<3; vi++, fvVB++)
		{
			// position

			m_fVertTexBuffer[fvVB].X = pDmndTable[vi].m_fVert[0]*scale;
			m_fVertTexBuffer[fvVB].Y = pDmndTable[vi].m_fVert[1]*scale;
			m_fVertTexBuffer[fvVB].Z = pDmndTable[vi].m_fVert[2]*scale;
			m_fVertTexBuffer[fvVB].Tu=m_fVertTexBuffer[fvVB].X/(m_iSize*scale);
			m_fVertTexBuffer[fvVB].Tv=m_fVertTexBuffer[fvVB].Z/(m_iSize*scale);

			if (vi==0)
				m_fVertTexBuffer[fvVB].Color = System.Drawing.Color.Blue.ToArgb();
			else if (vi==1)
				m_fVertTexBuffer[fvVB].Color = System.Drawing.Color.Red.ToArgb();
			else
				m_fVertTexBuffer[fvVB].Color = System.Drawing.Color.Green.ToArgb(); 

		}
		m_iVertsPerFrame+= 3;
		m_iTrisPerFrame++;
	}


	/// <summary>

	/// Free a triangle from the triangle render list

	/// </summary>

	/// <param name="pDmnd"></param>

	/// <param name="j">side index</param>

	private void FreeTri( SROAM_DIAMOND pDmnd, int j )
	{
		int iFlags;

		//CLIPPED diamonds never have triangles

		if(( pDmnd.m_ucFlags & ROAM_CLIPPED ) != 0)
			return;

		iFlags= pDmnd.m_pParent[j].m_ucFlags;

		//CLIPPED parent j means no triangle on iSide j

		if(( iFlags & ROAM_CLIPPED ) != 0)
			return;

		//indicate that the triangle on iSide j is not active

		pDmnd.m_ucFlags = (byte)(pDmnd.m_ucFlags & ~( ROAM_TRI0<<j ));

		//if not OUT, take the triangle off of the IN list

		if( ( pDmnd.m_ucCull & CULL_OUT ) == 0 )
			RemoveTri( pDmnd, j );
	}

	/// <summary>

	/// Remove a triangle from the render list

	/// </summary>

	/// <param name="pDmnd"></param>

	/// <param name="j">side index</param>

	private void RemoveTri( SROAM_DIAMOND pDmnd, int j )
	{
		SROAM_DIAMOND pDmndX;
		int iDmndIS, ix, jx, i;
		i= pDmnd.m_usTriIndex[j];

		//put the triangle back on the "free" list for use

		pDmnd.m_usTriIndex[j]=0;
		m_iFreeTri--;
		m_iFreeTriCount++;

		//copy the last triangle on the list (non-free) to the freed triangle

		ix  = m_iFreeTri;
		iDmndIS= m_ipPDmndIS[ix];
		jx  = iDmndIS & 1; // 1 bit, either 0 or 1

		pDmndX = m_pDmndPool[( iDmndIS>>1 )];
		
		pDmndX.m_usTriIndex[jx]= (ushort)i;
		m_ipPDmndIS[i]= iDmndIS;
		
		// overwrite the 3 unused vertex

		i=(i)*3;
		ix=(ix)*3;
		for (int x = 0; x < 3; x++) 
		{
			m_fVertTexBuffer[i+x]=m_fVertTexBuffer[ix+x];
		}

		m_iVertsPerFrame-= 3;
		m_iTrisPerFrame--;
	}

	static int i0= 0;

	/// <summary>

	/// Update the engine's mesh (process queues)

	/// </summary>

	public void Update() 
	{
		SROAM_DIAMOND pDmnd;
		int iSide, iOverlap, iOverlap0, iOptCount, iMaxOptCount, i1, i;

		//update all active diamonds with a recursive culling update

		pDmnd= m_pLevel0Dmnd[1,1];
		UpdateChildCull( pDmnd );
		for( i= 0; i < 4; i++ )
		{
			if( pDmnd.m_pChild[i] != null )
				UpdateChildCull( pDmnd.m_pChild[i] );
		}

		//update all queued diamonds' priority

		i1= i0+( m_iPoolSize+9 )/10;

		if( i1 >= m_iPoolSize )
			i1 = m_iPoolSize-1;

		for( i=i0; i<= i1; i++ )
		{
			pDmnd= m_pDmndPool[i];
			if(( pDmnd.m_ucFlags & ROAM_ALLQ ) != 0)
				UpdatePriority( pDmnd );
		}

		i0= ( i1+1 )%m_iPoolSize; 

		/*
		 * keep splitting/merging until either
		 *  (a) no split/merge priority iOverlap and:
		 *      target tri count reached or accuracy target reached
		 * or
		 *  (b) time is up (limit optimization-loop iterations)
		 * or
		 *  (c) not enough free (unlocked) diamonds in cache
		 *
		 * Note: this implementation handles non-monotonic priorities,
		 * i.e. where a child can have a higher priority than its parent.
		 * Also, we are careful to be just one force-split away from being
		 * beyond the target triangle/accuracy count.  As a iSide effect, this
		 * eliminates one kind of oscillation that might occur if using
		 * the suggested pseudocode from the original ROAM paper (see Vis 1997).
		 *
		 */
		iMaxOptCount= 2000; /* split/merge limit */
		iOptCount   = 0;
		
		//check to see if the mesh is too coarse

		if( ( m_iTrisPerFrame <= m_iMaxTris && m_iPQMax>=m_iQueueCoarse &&
			m_iFreeElements>128	      && m_iFreeTriCount>128 ) )
			iSide= -1;
		else
			iSide= 1;
		
		iOverlap= iOverlap0= m_iPQMax-m_iPQMin;

		//loop through performing split/merge ops

		while( ( iSide!=0 || iOverlap0>1 ) && iOptCount<iMaxOptCount )
		{
			if( iSide<=0 )
			{
				if( m_iPQMax>0 )
				{
					Split( m_pSplitQueue[m_iPQMax] );

					//check to see if the mesh is too coarse

					if( !( m_iTrisPerFrame<=m_iMaxTris && m_iPQMax>=m_iQueueCoarse &&
						m_iFreeElements>128	       && m_iFreeTriCount>128 ) )
						iSide= 1;
				}
				else
					iSide= 0;
			}
			else
			{
				Merge( m_pMergeQueue[m_iPQMin] );

				//check to see if the mesh is too coarse

				if( ( m_iTrisPerFrame<=m_iMaxTris && m_iPQMax>=m_iQueueCoarse && 
					m_iFreeElements>128	&& m_iFreeTriCount>128 ) )
					iSide= 0;
			}

			iOverlap= m_iPQMax-m_iPQMin;
			if( iOverlap<iOverlap0 )
				iOverlap0= iOverlap;

			iOptCount++;
		}

		m_iFrameCount= ( m_iFrameCount+1 ) & 255;
	}

	/// <summary>

	/// Update a child's culling flag

	/// </summary>

	/// <param name="pDmnd"></param>

	private void UpdateChildCull( SROAM_DIAMOND pDmnd )
	{
		SROAM_DIAMOND pChild;
		int iCull, i;

		//CLIPPED diamonds have no interest here, back out

		if(( pDmnd.m_ucFlags & ROAM_CLIPPED ) != 0)
			return;

		iCull= pDmnd.m_ucCull; //save old culling flag for comparison


		//update the diamond's culling flags

		UpdateCull( pDmnd );

		//skip subtree if nothing has really changed

		if( iCull==pDmnd.m_ucCull && ( iCull==CULL_OUT || iCull==CULL_ALLIN ) )
			return;

		//update diamond priority if culling OUT state has changed

		if( (( iCull^pDmnd.m_ucCull ) & CULL_OUT ) != 0)
			UpdatePriority( pDmnd );

		//if diamond is split, recurse down to it's four children if they exist

		if( (pDmnd.m_ucFlags & ROAM_SPLIT ) != 0)
		{
			for( i=0; i<4; i+=2 )
			{
				if(( pChild= pDmnd.m_pChild[i] ) != null )
				{
					if( pChild.m_pParent[0]==pDmnd )
					{
						//update culling for the first child

						if( pChild.m_pChild[0] != null )
							UpdateChildCull( pChild.m_pChild[0] );

						//update culling for the second child

						if( pChild.m_pChild[1] != null )
							UpdateChildCull( pChild.m_pChild[1] );
					}
					else
					{
						//update culling for the third child

						if( pChild.m_pChild[2] != null )
							UpdateChildCull( pChild.m_pChild[2] );

						//update culling for the fourth child

						if( pChild.m_pChild[3] != null )
							UpdateChildCull( pChild.m_pChild[3] );
					}
				}
			}
		}
	}


	/// <summary>

	/// Split a diamond (finer detail)

	/// </summary>

	/// <param name="pDmnd"></param>

	private void Split( SROAM_DIAMOND pDmnd )
	{
		SROAM_DIAMOND pChild, pParent;
		int i, s;

		//if the diamond has already been split, then skip it! And skip it good!

		if( (pDmnd.m_ucFlags & ROAM_SPLIT ) != 0)
			return;

		//split parents recursively (as needed)

		for( i=0; i<2; i++ )
		{
			pParent= pDmnd.m_pParent[i];
			Split( pParent );

			//if the diamond is pParent's first split child, take pParent off of the merge queue

			if( ( pParent.m_ucSplitFlags & SPLIT_K ) == 0 )
				Enqueue( pParent, ROAM_UNQ, pParent.m_sQueueIndex );
			pParent.m_ucSplitFlags = (byte)(pParent.m_ucSplitFlags | (SPLIT_K0<<pDmnd.m_cChildIndex[i]));
		}

		//get the children, update flags, and put on the split queue

		for( i=0; i<4; i++ )
		{
			pChild= GetChild( pDmnd, i );
			UpdateCull( pChild );
			UpdatePriority( pChild );

			//children of the newly split diamond now go on the split queue

			Enqueue( pChild, ROAM_SPLITQ, pChild.m_sQueueIndex );
			s= ( pChild.m_pParent[1]==pDmnd ? 1 :0 );
			pChild.m_ucSplitFlags = (byte)(pChild.m_ucSplitFlags | (SPLIT_P0<<s));
			Unlock( pChild );

			//put the child triangles on the render list

			AllocateTri( pChild, s );
		}

		//diamond is split, update it's queue, and add to "check list"

		pDmnd.m_ucFlags|= ROAM_SPLIT;
		Enqueue( pDmnd, ROAM_MERGEQ, pDmnd.m_sQueueIndex );	//newly split diamond goes on merge queue


		//put parent tris back on the free list

		FreeTri( pDmnd, 0 );
		FreeTri( pDmnd, 1 );
	}


	/// <summary>

	/// Get a new child and set it's information

	/// </summary>

	/// <param name="pDmnd"></param>

	/// <param name="i">child index of given diamond</param>

	/// <returns></returns>

	private SROAM_DIAMOND GetChild( SROAM_DIAMOND pDmnd, int i )
	{
		SROAM_DIAMOND k, pParentX, pChildX;
		float [] pDmndCenter, pParentVert0, pParentVert1;
		float fSqrBound, fSqrBoundTemp;
		float [] fTempVert;
		int ix;

		//if the diamond is already alive, return it

		if( ( k= pDmnd.m_pChild[i] ) != null )
		{
			Lock( k );
			return k;
		}

		//lock the center diamond to prevent early recycling

		Lock( pDmnd );

		//recursively create other parent for the child (i)

		if( i<2 )
		{
			pParentX= pDmnd.m_pParent[0];
			ix= ( pDmnd.m_cChildIndex[0] + ( i==0 ? 1 : -1 ) ) & 3;
		}
		else
		{
			pParentX= pDmnd.m_pParent[1];
			ix= ( pDmnd.m_cChildIndex[1] + ( i==2 ? 1 : -1 ) ) & 3;
		}

		pChildX= GetChild( pParentX, ix ); //lock other child parent


		//create a new child, and lock it

		k= Create( );

		//set all of the child's links

		pDmnd.m_pChild[i]= k;
		ix= ( i & 1 )^1;
		if( pChildX.m_pParent[1]==pParentX )
			ix|= 2;

		pChildX.m_pChild[ix]= k;
		if(( i & 1 ) != 0)
		{
			k.m_pParent[0]    = pChildX;
			k.m_cChildIndex[0]= (byte)ix;
			k.m_pParent[1]    = pDmnd;
			k.m_cChildIndex[1]= (byte)i;
		}
		else
		{
			k.m_pParent[0]    = pDmnd;
			k.m_cChildIndex[0]= (byte)i;
			k.m_pParent[1]    = pChildX;
			k.m_cChildIndex[1]= (byte)ix;
		}
		k.m_pParent[2]= pDmnd.m_pParent[i>>1];
		k.m_pParent[3]= pDmnd.m_pParent[( ( ( i + 1 ) & 2 )>>1 ) + 2];
		k.m_pChild[0] = k.m_pChild[1]= k.m_pChild[2]= k.m_pChild[3]= null;

		//set child information (iLevel, vertex info, flags, etc.)

		k.m_ucCull = 0;
		k.m_ucFlags= 0;
		k.m_ucSplitFlags= 0;
		if( (( k.m_pParent[2].m_ucFlags & ROAM_CLIPPED ) != 0) ||
			( (( pDmnd.m_ucFlags & ROAM_CLIPPED ) != 0) && (( pChildX.m_ucFlags & ROAM_CLIPPED ) != 0) ) )
			k.m_ucFlags|= ROAM_CLIPPED;
		k.m_usTriIndex[0]= k.m_usTriIndex[1]= 0;
		k.m_sQueueIndex= -10;
		k.m_cLevel= (sbyte)(pDmnd.m_cLevel+1);

		pDmndCenter= k.m_fVert;

		pParentVert0= k.m_pParent[2].m_fVert;
		pParentVert1= k.m_pParent[3].m_fVert;
		k.m_fVert[0]= ( float )Math.Abs( ( pParentVert0[0] + pParentVert1[0] )/2.0f );
		k.m_fVert[2]= ( float )Math.Abs( ( pParentVert0[2] + pParentVert1[2] )/2.0f );
		k.m_fVert[1]= GetTrueHeightAtPoint( ( int )k.m_fVert[0],
			( int )k.m_fVert[2] );

		//compute radius of diamond bounding sphere (squared)

		//calculate the bounding sphere for the current triangle

		//calculation 1

		fTempVert= k.m_pParent[0].m_fVert;
		fSqrBound= ( ( fTempVert[0]-pDmndCenter[0] ) * ( fTempVert[0]-pDmndCenter[0] )  ) +
			( ( fTempVert[1]-pDmndCenter[1] ) * ( fTempVert[1]-pDmndCenter[1] ) ) +
			( ( fTempVert[2]-pDmndCenter[2] ) * ( fTempVert[2]-pDmndCenter[2] ) );

		fTempVert= k.m_pParent[1].m_fVert;
		//calculation 2

		fSqrBoundTemp= ( ( fTempVert[0]-pDmndCenter[0] ) * ( fTempVert[0]-pDmndCenter[0] )) +
			( ( fTempVert[1]-pDmndCenter[1] ) * ( fTempVert[1]-pDmndCenter[1] )) +
			( ( fTempVert[2]-pDmndCenter[2] ) * ( fTempVert[2]-pDmndCenter[2] ));
	
		//check to see if this is the largest distance we've calculated so far

		if( fSqrBoundTemp>fSqrBound )
			fSqrBound= fSqrBoundTemp;

		//calculation 3

		fTempVert= k.m_pParent[2].m_fVert;
		fSqrBoundTemp= ( ( fTempVert[0]-pDmndCenter[0] ) * ( fTempVert[0]-pDmndCenter[0] )) +
			( ( fTempVert[1]-pDmndCenter[1] ) * ( fTempVert[1]-pDmndCenter[1] )) +
			( ( fTempVert[2]-pDmndCenter[2] ) * ( fTempVert[2]-pDmndCenter[2] ));
	
		//check to see if this is the largest distance we've calculated so far

		if( fSqrBoundTemp>fSqrBound )
			fSqrBound= fSqrBoundTemp;

		//calculation 4

		fTempVert= k.m_pParent[3].m_fVert;
		fSqrBoundTemp= ( ( fTempVert[0]-pDmndCenter[0] ) * ( fTempVert[0]-pDmndCenter[0] )) +
			( ( fTempVert[1]-pDmndCenter[1] ) * ( fTempVert[1]-pDmndCenter[1] )) +
			( ( fTempVert[2]-pDmndCenter[2] ) * ( fTempVert[2]-pDmndCenter[2] ));
	
		//check to see if this is the largest distance we've calculated so far

		if( fSqrBoundTemp>fSqrBound )
			fSqrBound= fSqrBoundTemp;

		k.m_fBoundRad= fSqrBound;
		k.m_fErrorRad=  m_fpLevelMDSize[k.m_cLevel] *  m_fpLevelMDSize[k.m_cLevel] ;

		return k;
	}

	/// <summary>

	/// Merge a diamond (coarser detail)

	/// </summary>

	/// <param name="pDmnd"></param>

	private void Merge( SROAM_DIAMOND pDmnd )
	{
		SROAM_DIAMOND k, pParent;
		int i, s;

		//if this diamond has already been merged, then skip

		if( ( pDmnd.m_ucFlags & ROAM_SPLIT ) == 0 )
			return;

		//children off split queue if their other parent is not split

		for( i=0; i<4; i++ )
		{
			k= pDmnd.m_pChild[i];
			s= ( k.m_pParent[1]==pDmnd ? 1 : 0 );

			k.m_ucSplitFlags = (byte)(k.m_ucSplitFlags & (~( SPLIT_P0<<s )));
			if( ( k.m_ucSplitFlags & SPLIT_P ) == 0 )
				Enqueue( k, ROAM_UNQ, k.m_sQueueIndex );

			//put the tris back on the free list

			FreeTri( k, s );
		}

		//diamond is not split, update it's queue, and add to "check list"

		pDmnd.m_ucFlags = (byte)(pDmnd.m_ucFlags & (~ROAM_SPLIT));
		Enqueue( pDmnd, ROAM_SPLITQ, pDmnd.m_sQueueIndex );

		//update the diamond's parents, only if it is needed

		for( i=0; i<2; i++ )
		{
			pParent= pDmnd.m_pParent[i];

			pParent.m_ucSplitFlags = (byte)(pParent.m_ucSplitFlags & (~( SPLIT_K0<<pDmnd.m_cChildIndex[i] )));
			if( ( pParent.m_ucSplitFlags & SPLIT_K ) == 0 )
			{
				UpdatePriority( pParent );
				Enqueue( pParent, ROAM_MERGEQ, pParent.m_sQueueIndex );
			}
		}

		//put the parent tris on the triangle render list

		AllocateTri( pDmnd, 0 );
		AllocateTri( pDmnd, 1 );
	}

	/// <summary>

	/// Render the ROAM engine

	/// </summary>

	public void Render(Device device, VertexBuffer vb)
	{

	//	CustomVertex.PositionColoredTextured[] c=(CustomVertex.PositionColoredTextured [])vb.Lock(0,LockFlags.Discard | LockFlags.NoSystemLock);


		GraphicsStream gs=vb.Lock(0,0,0);

	//	for (int i=3; i<(3*(m_iFreeTri));i++) 

	//		c[i-3]=this.m_fVertTexBuffer[i];

		gs.Write(this.m_fVertTexBuffer);
		vb.Unlock();

		device.SetStreamSource(0, vb, 0, VertexInformation.GetFormatSize(CustomVertex.PositionColoredTextured.Format));
		device.VertexFormat = CustomVertex.PositionColoredTextured.Format;

		device.SetTexture(0, map);
		device.SamplerState[0].MinFilter=TextureFilter.Linear;
		device.SamplerState[0].MagFilter=TextureFilter.Linear;
		device.RenderState.FillMode = FillMode.Solid;
		device.DrawPrimitives(PrimitiveType.TriangleList, 0, m_iFreeTri);

	}

	/// <summary>

	/// Update a given diamond's culling flag

	/// </summary>

	/// <param name="pDmnd"></param>

	private void UpdateCull( SROAM_DIAMOND pDmnd )
	{
		float r;
		int iCull, j, m;

		//get the diamond's parent's culling flag

		iCull= pDmnd.m_pParent[2].m_ucCull;

		//if needed, update for all non-IN halfspaces

		if( iCull!=CULL_ALLIN && iCull!=CULL_OUT )
		{
			for( j=0, m=1; j<6; j++, m<<= 1 )
			{
				if( ( iCull & m ) == 0 )
				{
#warning
					r= this.m_pCamera.m_cullinfo.planeFrustum[j].A*pDmnd.m_fVert[0] +
						this.m_pCamera.m_cullinfo.planeFrustum[j].B*pDmnd.m_fVert[1] +
						this.m_pCamera.m_cullinfo.planeFrustum[j].C*pDmnd.m_fVert[2] +
						this.m_pCamera.m_cullinfo.planeFrustum[j].D; 

					//cull the diamond

					if( (r*r ) > pDmnd.m_fBoundRad )
					{
						if( r<0.0f )
							iCull= CULL_OUT;
						else
							iCull|= m; //IN

					} //else still overlaps this frustum plane

				}
			} 
		}

		//if OUT state changes, update in/out listing on any draw tris

		if( ( ( pDmnd.m_ucCull^iCull ) & CULL_OUT ) != 0)
		{
			for( j=0; j<2; j++ )
			{
				if(( pDmnd.m_ucFlags & ( ROAM_TRI0<<j ) ) != 0)
				{
					if(( iCull & CULL_OUT ) != 0)
						RemoveTri( pDmnd, j );
					else
						AddTri( pDmnd, j );
				}
			}
		}

		//store the updated cull flags

		pDmnd.m_ucCull= (byte)iCull;
	}

	/// <summary>

	/// Update a diamond's priority in the split/merge queues

	/// </summary>

	/// <param name="pDmnd"></param>

	private void UpdatePriority( SROAM_DIAMOND pDmnd )
	{
		float d;
		int j, k;

		//skip the update procedure if it has already been done

		if( m_iFrameCount==pDmnd.m_ucFrameCount )
			return;
		pDmnd.m_ucFrameCount= (byte)m_iFrameCount;

		if( (( pDmnd.m_ucFlags & ROAM_CLIPPED ) !=0) || pDmnd.m_cLevel >= m_iMaxLevel )
			k= 0;
		else
		{
			//set the local integer pointer (for the IEEE floating-point tricks)


			unsafe 
			{

				int *pInt= ( int* )( &d );		//set the local integer pointer (for the IEEE floating-point tricks)

				d= pDmnd.m_fErrorRad;

				//compute the fixed-point log_2 value (based on the error metric)

				k = *pInt;
				k+= m_iLog2Table[( k>>15 ) & 0xff];
    
				//distance calculation

#warning
				d= SQR( ( pDmnd.m_fVert[0]-this.m_pCamera.m_cullinfo.position.X ) ) +
					SQR( ( pDmnd.m_fVert[1]-this.m_pCamera.m_cullinfo.position.Y ) ) +
					SQR( ( pDmnd.m_fVert[2]-this.m_pCamera.m_cullinfo.position.Z ) ); 

				//compute the fixed-point log_2 value (based on the distance to the camera)

				j = *pInt;
				j+= m_iLog2Table[( j>>15 ) & 0xff];

			}

			//compute the fixed-point log_2(error/distance)

			k= ( k-j )+0x10000000;

			//scale and clamp the priority index to [1, IQMAX-1]

			if( k<0 )
				k= 0;
			
			k= ( k>>16 )+1;
			if( k>=IQMAX )
				k= IQMAX-1;

			//for OUT diamonds, reduce priority (but leave them ordered)

			if( (pDmnd.m_ucCull & CULL_OUT ) != 0)
			{
				if( k>m_iSize )
					k-= ( m_iSize/2 );
				else
					k= ( k+1 )>>1;
			}
		}

		//update the queue index

		Enqueue( pDmnd, pDmnd.m_ucFlags & ROAM_ALLQ, k );
	}

	private float SQR (float x) 
	{
		return x*x;
	}

	unsafe int calculatethis(int i) 
	{
		float f;
		int *pInt;
		pInt= ( int * )( &f );
		*pInt= 0x3f800000 + ( i<<15 );
		return ( int )Math.Floor( m_iSize*( Math.Log( f )/Math.Log( 2.0 ) - ( float )i/256.0 ) + 0.5f )<<12;
	}
}



Found a way to make it a little faster. Now it goes up to 50fps for a terrain of 4096^2 I changed the code accordingly. My main question now is how can I scale it and avoid popping? I added a scale variable to the code but it doesn't work well. This terrain is 4096^2 but I want to make it doble the size. How can I do this? I multiply all the x,y,z by the scale value (2) but then the whole system doesn't work properly. Popping is very very noticeable. Any suggestions to modify my code? Joaquin Grech [edited by - creative1 on June 4, 2004 12:55:02 PM]

Share this post


Link to post
Share on other sites
Advertisement

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!