# Geomipmapping implementation using direct3d

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

## Recommended Posts

Hello everyone, Iam working on a terrain engine using direct 3d and it is capable of doing the usual stuff of loading heightmaps, height-based texture mapping and renders using triangle strips. I implemented the terrain using brute-force technique and divided the terrain into 17 x 17 patches. I want to extend the capability of my engine by rendering using geomipmapping, quadtrees, ROAM.. etc.. Iam not able to figure out a way to render the terrain using geomipmapping. I implemented level of detail patches by skipping vertices in the index buffer, but Iam not able to implement the vertex skipping needed to juxtapose a terrain patch with higher level of detail besides a terrain patch with lower level of detail... Can this be done easier using triangle fans ? can we constantly modify the index buffer during rendering or is it better to store all the possible cases in seperate index buffers ? Can anyone show me how to render a 17 x 17 patch using triangle fans ? Please help guys... I have been stuck for a week...

##### Share on other sites
Hi,

Here is a quick example of stitching with triangle-strips on a 3x3 grid of vertices

The grid without any stitching and using an anti-clockwise winding order.

0----1----2|   /|   /||  / |  / || /  | /  ||/   |/   |3----4----5|   /|   /||  / |  / || /  | /  ||/   |/   |6----7----8

Index array would be ( 0,3,1,4,2,5,5,3,3,6,4,7,5,8 ) where the repeated indices 5 and 3 give you a degenerate triangle

0----1----2|   /|   /||  / |  / || /  | /  ||/   |/   |3----4----5|   / \   ||  /   \  || /     \ ||/       \|6----7----8

Here we can see what you want your grid to look like when you have stitched down to another patch with a lod level that is 1 less than your current patch's lod level. The size of the index array will be exactly the same and basically all we want to do is shift index 7 so it points to the vertex at index 8. This would mean an index array of ( 0,3,1,4,2,5,5,3,3,6,4,8,5,8 ).

0----1----2|   /|   /||  / |  / || /  | /  ||/   |/   |3----4    5|   / \   ||  /   \  || /     \ ||/       \|6----7----8

Lastly we have a stich down and a stitch right. This time we also need to shift index 5 down to index 8 and the index array would look as follows ...
( 0,3,1,4,2,8,8,3,3,6,4,8,8,8 ).

Notice how the size of the index array never changes. Bare in mind this is just how I implemented it myself and it is probably not the best way to go about it.
I only ever stitch from a higher detail to a low detail. This avoids adding and removing indices as you simply need to shift them along.

Also I build the index array every frame for the lod level needed and I do this on the cpu, although a vertex shader should be quite possible.

The algorithm to do the stitching is very much implementation specific, very hard (in my opinion :D ) and I would suggest you do it on your own (there is definately no better feeling than getting it working) and use a lot of pen and paper :D

2 places I found of great use to me were ...

this gamedev forum topic

and This opengl implementation ...I know you said you were using directx, but building an index array is pretty api independent :)

All the best,
ViLiO

##### Share on other sites
Quote:
 Original post by RB26DETTCan anyone show me how to render a 17 x 17 patch using triangle fans ?

Don't use triangle fans. Use indexed triangle lists (or strips if you are up for the challenge).

Also, unless you are targeting older video cards, make your patches bigger -- at least 33 x 33.

There are three ways to handle stitching two patches of different resolution together.

1. Modify the patches every frame to match the adjacent patches. This probably looks the best, but it can be expensive.

2. Restrict your LOD selection so that the LODs of adjacent patches are differ by one level only. Precompute meshes that match all the possible combinations (16 for each LOD, because each side can be the same LOD or 1 lower). This is probably a better choice than #1, but it is more complicated.

3. Use skirts. It adds extra geometry, but it is the simplest solution.

##### Share on other sites
forgive me for my ignorance...

wat are skirts ?

##### Share on other sites
Hi,

I assume adding a strip of triangles where the patches meet to fill the holes between them. This would be extra geometry though and would surely lead to triangles that are completely vertical (to fill the error space with geometry)

I may try implementing skirts and method 2 myself just to see if there is any noticable speed increase or degradation of quality although I am hoping that building the index buffer each frame would still work out better than forcing patches to be rendered at a higher detail just because their neighbours are.

Regards,
ViLiO

##### Share on other sites
Quote:
 Original post by RB26DETTforgive me for my ignorance... wat are skirts ?

A skirt is extra geometry that hangs down from the edges of every patch. It basically covers any cracks between adjacent patches. The techinique is kind of a hack, but it works pretty well.

##### Share on other sites
I have been tryin to assign the value of each index seperately without using loops .(rendering with triangle lists).This is proving to be very tideous...
Can anyone show me a working code snippet for assigning values to indexes for either triangle lists or triangle strips ? (for geomipmapping)
How do assign values for the 15 other index buffers we need to precalculate ?

##### Share on other sites
#define PATCH_SIZE				32#define PATCH_VERTS				((PATCH_SIZE+1)*(PATCH_SIZE+1))//I'm taking advantage here by using the same constant for 2//different things. These can be used simply as unique IDs, or they//can be used to determine the size of a block.#define		SCAPE_LOD_HIGH		1		//use every vertex#define		SCAPE_LOD_MED		2		//every 2#define		SCAPE_LOD_LOW		4		//every 4#define		SCAPE_LOD_XTRALOW	8		//every 8#define		SCAPE_LOD_MIN		16		//every 16#define		INDICES_LOD_HIGH	(PATCH_SIZE*PATCH_SIZE*2*3)#define		INDICES_LOD_MED		(INDICES_LOD_HIGH / 4)#define		INDICES_LOD_LOW		(INDICES_LOD_MED / 4)#define		INDICES_LOD_XTRALOW	(INDICES_LOD_LOW / 4)#define		INDICES_LOD_MIN		(INDICES_LOD_XTRALOW / 4)

int CScape::RenderPatch( int i ){	int FacesRendered = 0;	static unsigned short Indices[INDICES_LOD_HIGH];	ScapePatch* Patch = &m_Patches;	unsigned short* IndexPtr;	glVertexPointer( 3, GL_FLOAT, sizeof(ScapeVertex), m_Buffer->GetPointer() + (PATCH_VERTS * i * sizeof(ScapeVertex)) );	int CurIndices;	if( Patch->LoD == SCAPE_LOD_HIGH )	{		CurIndices = INDICES_LOD_HIGH;		IndexPtr = m_Indices[0];	}	else if( Patch->LoD == SCAPE_LOD_MED )	{		CurIndices = INDICES_LOD_MED;		IndexPtr = m_Indices[1];	}	else if( Patch->LoD == SCAPE_LOD_LOW )	{		CurIndices = INDICES_LOD_LOW;		IndexPtr = m_Indices[2];	}	else if( Patch->LoD == SCAPE_LOD_XTRALOW )	{		CurIndices = INDICES_LOD_XTRALOW;		IndexPtr = m_Indices[3];	}	else if( Patch->LoD == SCAPE_LOD_MIN )	{		CurIndices = INDICES_LOD_MIN;		IndexPtr = m_Indices[4];	}	memcpy( Indices, IndexPtr, CurIndices * sizeof(unsigned short) );	//GenIndices( Patch->LoD, Indices );	ScapePatch* Other;	//ok, now to work out some adjacency LoD issues	//If an adjacent patch is at a lower LoD, shift indices around	//to avoid cracks in the landscape.	if( i >= m_HeightPatches )	{		Other = &m_Patches[i-m_HeightPatches];		if( Other->LoD > Patch->LoD )		{			//the patch to the left is at a lower LoD			//we need to reduce our left detail level			for( int n = 0; n < CurIndices; ++n )			{				if( (Indices[n] < (PATCH_SIZE+1)) && (Indices[n] % Other->LoD) != 0 )				{					Indices[n] -= Indices[n] % Other->LoD;				}			}		}	}	if( i <= m_NumPatches - m_HeightPatches )	{		Other = &m_Patches[i+m_HeightPatches];		if( Other->LoD > Patch->LoD )		{			//Patch to the right is at a lower LoD			//reduce right edge detail			for( int n = 0; n < CurIndices; ++n )			{				if( (Indices[n] > ((PATCH_SIZE+1)*PATCH_SIZE) ) && (Indices[n] % Other->LoD) != 0 )				{					Indices[n] -= Indices[n] % Other->LoD;				}			}		}	}	if( i % m_HeightPatches )	{		Other = &m_Patches[i-1];		if( Other->LoD > Patch->LoD )		{			//the patch to the top is at a lower LoD			//we need to reduce our top detail level			for( int n = 0; n < CurIndices; ++n )			{				if( (Indices[n] % (PATCH_SIZE+1) == 0) && (Indices[n] % (Other->LoD * (PATCH_SIZE+1))) != 0)				{					Indices[n] -= (PATCH_SIZE+1) * Indices[n] % (Other->LoD * (PATCH_SIZE+1));				}			}		}	}	if( (i + 1) % m_HeightPatches )	{		Other = &m_Patches[i+1];		if( Other->LoD > Patch->LoD )		{			//the patch to the bottom is at a lower LoD			//we need to reduce our bottom detail level			for( int n = 0; n < CurIndices; ++n )			{				if( ((Indices[n] + 1) % (PATCH_SIZE+1) == 0) && (Indices[n] % (Other->LoD * (PATCH_SIZE+1))) != 0)				{					Indices[n] -= (PATCH_SIZE+1) * Indices[n] % (Other->LoD * (PATCH_SIZE+1));				}			}		}	}	glDrawElements( GL_TRIANGLES, CurIndices, GL_UNSIGNED_SHORT, Indices );	FacesRendered = CurIndices / 3;	return FacesRendered;}

The second source box shows my complete algorithm for patching the indices against ANY two bordering LoDs. The shown code does it at the same time at rendering the patch, which is decently fast. In reality though, what I do is to regenerate the LoDs only when some patch's LoD changes, and cache those buffers. This tends to be far more efficient, particularly if you limit LoD changes over time, because the cost is amortized significantly and the index fixing costs become almost zero.

##### Share on other sites
This is not very good solution but I wrote it, because i needed it.
It is very simple and works for 33x33 patch. My LODing halves the patch geometry, that means that my patch has in LEVEL_0 33x33, but in LEVEL_1 17x17. I think the best way is doing geomorphing between LEVELs. There was articel on this subject on GameDev (Terrain geomorphing in Vertex Shader). And here on GameDev is very good articel about lighting too.

Have a nice day. Rubik

WORD pIndices[2176];
int k, l = 0;
for (int j = 0; j <

##### Share on other sites
WORD pIndices[2176];
int k, l = 0;
for (int j = 0; j <

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 13
• 9
• 9
• 15
• 14
• ### Forum Statistics

• Total Topics
634070
• Total Posts
3015330
×