Home
Blogs
Forums
News
Portfolios
Projects
Tutorials
33 users logged in
New? Learn about game development.
Before posting, review our community guidelines.
Follow Us
Chat in the GameDev.net Discord!
Mastodon
Back to General and Gameplay Programming

Terrain chunks and index arrays

Started by
26 comments, last by rethan 14 years, 11 months ago
Hey there! I want to split my terrain into several pieces. It's working, actually... but I got some weird problem with the degenerated triangles, I guess. 

//m_patchSize is a power of 2 digit
for(unsigned int patchZ = 0; patchZ < GetWidth(); patchZ += m_patchSize)
	{
		for(unsigned int patchX = 0; patchX < GetWidth(); patchX += m_patchSize)
		{
			TerrainPatch new_patch;

		
			new_patch.m_vertexCount = m_patchSize*m_patchSize + m_patchSize*2;

			flx_Vertex		*patchVertices	= new flx_Vertex[new_patch.m_vertexCount];
			flx_TexCoord	        *patchTexCoords	= new flx_TexCoord[new_patch.m_vertexCount];
			flx_Normal		*patchNormals	= new flx_Normal[new_patch.m_vertexCount];
//Note: m_pVertices is the array of the vertices from the unchunked terrain (which is rendering correct)
			for(unsigned int z = 0; z < m_patchSize; ++z)
			{
				unsigned int x;
				for(x = 0; x < m_patchSize; ++x)
				{
					patchVertices[x + z * m_patchSize].x = m_pVertices[(x + patchX ) + (z + patchZ) * GetWidth()].x;
					patchVertices[x + z * m_patchSize].y = m_pVertices[(x + patchX) + (z + patchZ) * GetWidth()].y;
					patchVertices[x + z * m_patchSize].z = m_pVertices[(x + patchX) + (z + patchZ) * GetWidth()].z;

					patchTexCoords[x + z * m_patchSize].u = (float)((float)((x + patchX) * m_fOffsetX) / GetWidth());
					patchTexCoords[x + z * m_patchSize].v = (float)((float)((z + patchZ) * m_fOffsetZ) / GetLength());

					patchNormals[x + z * m_patchSize].x =  m_pNormals[(x + patchX) + (z + patchZ) * GetWidth()].x;
					patchNormals[x + z * m_patchSize].y =  m_pNormals[(x + patchX) + (z + patchZ) * GetWidth()].y;
					patchNormals[x + z * m_patchSize].z =  m_pNormals[(x + patchX) + (z + patchZ) * GetWidth()].z;
				}
			}
			
//create indices, incl. degenerated triangles
			unsigned int indexPatchSize = m_patchSize;
			for(int z = 0; z < indexPatchSize-1; z++)
			{
				if(z % 2)
				{
					int x;
					for(x = indexPatchSize-1; x >= 0; x--)
					{
						new_patch.m_Indices.push_back((z + 1)*m_patchSize + x );
						new_patch.m_Indices.push_back(x  + (z * m_patchSize) );
							
					}
						new_patch.m_Indices.push_back( (z+1)*m_patchSize );
						new_patch.m_Indices.push_back( (z+1)*m_patchSize );
				}
				else
				{
					int x;
					for(x = 0; x < indexPatchSize; x++)
					{
						new_patch.m_Indices.push_back( z*m_patchSize + x );
						new_patch.m_Indices.push_back( (z+1)*m_patchSize + x );
					}
						new_patch.m_Indices.push_back( (z+2)*m_patchSize-1 );
						new_patch.m_Indices.push_back( (z+2)*m_patchSize-1 );

				}
			}
This screen shows the problem: 1 row and 1 column are missing Thank you! [Edited by - starvinmarvin on May 4, 2009 10:42:39 AM]

http://www.qbnet.de

Advertisement
I don't want to annoy you, but I still haven't solved the problem myself :(

http://www.qbnet.de

You seem to have a stitching issue. Say the patch m_patchSize is 8, which means you keep track of 8x8 verts, where is the indexing for closing the gap between the right set of verts of one patch and the left set of verts of the next patch? If you want to use a vert buffer and indexing, then you will need to duplicate the verticies on the shared edge. So, for example, if you want 8x8 patches, you will actually need to store 9x9 verts the 9'th vert will = the 1'st vert of the patch it is next to.

Here is a simpler example of 9 total patches where you want "4x4". This requires that you store 5x5 verts for each patch. One way to do this is to include the right and bottom verts from the neighbor patches so the indexing can reference them:

. . . . o . . . o . . . .. . . . o . . . o . . . .. . . . o . . . o . . . .. . . . o . . . o . . . .o o o o o o o o o o o o o. . . . o . . . o . . . .. . . . o . . . o . . . .. . . . o . . . o . . . .o o o o o o o o o o o o o. . . . o . . . o . . . .. . . . o . . . o . . . .. . . . o . . . o . . . .. . . . o . . . o . . . .



the o's are shared, and the verts you would store for each patch would be like so:

. . . . o    o . . . o   o . . . .. . . . o    o . . . o   o . . . .. . . . o    o . . . o   o . . . .. . . . o    o . . . o   o . . . .o o o o o    o o o o o   o o o o o   o o o o o    o o o o o   o o o o o. . . . o    o . . . o   o . . . .. . . . o    o . . . o   o . . . .. . . . o    o . . . o   o . . . .o o o o o    o o o o o   o o o o o   o o o o o    o o o o o   o o o o o. . . . o    o . . . o   o . . . .. . . . o    o . . . o   o . . . .. . . . o    o . . . o   o . . . .. . . . o    o . . . o   o . . . .



To be explicit, if your global list of verts are numbered like so:

1  2  3  4  5  6  7  8  9 10 11 12 13.  .  .  .  o  .  .  .  o  .  .  .  .



these verts would show up like so in the top three patches:

1  2  3  4  5    5  6  7  8  9    9 10 11 12 13.  .  .  .  o    o  .  .  .  o    o  .  .  .  .



(And yes, this means you basically duplicate a lot of verts, which is one of the drawbacks, so picking a large enough m_patchSize is important to reduce the "# or verts per patch / duplicate verts per patch" ratio.

Hope that makes sense,
Val

[Edited by - rethan on May 4, 2009 4:30:42 PM]
Thank you! But I already found out that I have to get the neighbour vertices too :). The problem is my piece of code which creates the indices.

Anyway, do you think splitting the terrain into patches is a bad idea (when implementing LOD sometime)?

http://www.qbnet.de

m_patchSize used in the routine should be a (2^n + 1) number, as rethan pointed out, because of the stitching. So you should use something like

//m_patchSize is a power of 2 digit//but patch contains (m_patchSize+1)^2 verticesunsigned int nvert = m_patchSize + 1;for(unsigned int patchZ = 0; patchZ < GetWidth(); patchZ += m_patchSize){	for(unsigned int patchX = 0; patchX < GetWidth(); patchX += m_patchSize)	{		TerrainPatch new_patch;				new_patch.m_vertexCount = nvert*nvert;		flx_Vertex *patchVertices = new flx_Vertex[new_patch.m_vertexCount];		flx_TexCoord *patchTexCoords = new flx_TexCoord[new_patch.m_vertexCount];		flx_Normal *patchNormals = new flx_Normal[new_patch.m_vertexCount];//Note: m_pVertices is the array of the vertices from the unchunked terrain (which is rendering correct)		for(unsigned int z = 0; z < nvert; ++z)		{			unsigned int x;			for(x = 0; x < nvert; ++x)			{				patchVertices[x + z * nvert].x = m_pVertices[(x + patchX ) + (z + patchZ) * GetWidth()].x;				patchVertices[x + z * nvert].y = m_pVertices[(x + patchX) + (z + patchZ) * GetWidth()].y;				patchVertices[x + z * nvert].z = m_pVertices[(x + patchX) + (z + patchZ) * GetWidth()].z;				patchTexCoords[x + z * nvert].u = (float)((float)((x + patchX) * m_fOffsetX) / GetWidth());				patchTexCoords[x + z * nvert].v = (float)((float)((z + patchZ) * m_fOffsetZ) / GetLength());				patchNormals[x + z * nvert].x =  m_pNormals[(x + patchX) + (z + patchZ) * GetWidth()].x;				patchNormals[x + z * nvert].y =  m_pNormals[(x + patchX) + (z + patchZ) * GetWidth()].y;				patchNormals[x + z * nvert].z =  m_pNormals[(x + patchX) + (z + patchZ) * GetWidth()].z;			}		}			//create indices, incl. degenerated triangles		unsigned int indexPatchSize = nvert;		for(int z = 0; z < indexPatchSize-1; z++)		{			if(z % 2)			{				int x;				for(x = nvert-1; x >= 0; x--)				{					new_patch.m_Indices.push_back((z + 1)*nvert + x );					new_patch.m_Indices.push_back(x  + (z * nvert) );											}				new_patch.m_Indices.push_back( (z+1)*nvert );				new_patch.m_Indices.push_back( (z+1)*nvert );			}			else			{				int x;				for(x = 0; x < indexPatchSize; x++)				{					new_patch.m_Indices.push_back( z*nvert + x );					new_patch.m_Indices.push_back( (z+1)*nvert + x );				}				new_patch.m_Indices.push_back( (z+2)*nvert-1 );				new_patch.m_Indices.push_back( (z+2)*nvert-1 );			}		}


Hope I got it right .. [smile]
Outerra
Quote:Original post by starvinmarvin
Thank you! But I already found out that I have to get the neighbour vertices too :). The problem is my piece of code which creates the indices.

Anyway, do you think splitting the terrain into patches is a bad idea (when implementing LOD sometime)?


I think it depends on how you indend to use the patches. If you are using patches to not draw parts of the terrain that are not visible etc, then there will be a sweet spot for patch size based on what your GPU can do. The trade off there is if the patch size is too small, you're binding texture/indecies too often, and if they are too big, you will be including big chunks of terrain even if only a small bit is visible.

Another trick that you use (if not already) is that really you just need 1 index array that all the chunks can use since each chunk really uses the same indexing to draw and it's only the normals and vertex positions that change. You can also look into automatic texture coordinate generation if you are rendering a heightmap that is based on a regular grid (which you are doing). ie the glTexGeni() func and friends.

[Edited by - rethan on May 4, 2009 11:23:25 PM]
Quote:Original post by cameni
m_patchSize used in the routine should be a (2^n + 1) number, as rethan pointed out, because of the stitching. So you should use something like

*** Source Snippet Removed ***

Hope I got it right .. [smile]


Thanks for the trouble! That's almost what I've got so far, but nverts is out of range of m_pVertices since it has the dimension of terrain_size^2. The reason for that is that I first build a vertice array like you would do without splitting the terrain.

@cameni, nverts in those lines doesn't seem right to me
new_patch.m_Indices.push_back( (z + 2) * m_patchSize-1 );


void GeometryTerrain::buildPatches(){	for(unsigned int patchZ = 0; patchZ < GetWidth(); patchZ += m_patchSize)	{		for(unsigned int patchX = 0; patchX < GetWidth(); patchX += m_patchSize)		{			TerrainPatch new_patch;			new_patch.m_vertexCount = (m_patchSize+1)*(m_patchSize+1);			flx_Vertex		*patchVertices	= new flx_Vertex[new_patch.m_vertexCount];			flx_TexCoord		*patchTexCoords	= new flx_TexCoord[new_patch.m_vertexCount];			flx_Normal		*patchNormals	= new flx_Normal[new_patch.m_vertexCount];			Vector3 tmax  = Vector3(-999999,-999999,-999999);			Vector3 tmin  = Vector3(999999,999999,999999);                        //fill the buffers/arrays of the patch with data			for(unsigned int z = 0; z < m_patchSize+1; ++z)			{				unsigned int x;				for(x = 0; x < m_patchSize+1; ++x)				{					//I do that because if x and y equal m_patchSize+1 they would be out of m_pVertices range					if(((tx + patchX) + (tz + patchZ) * GetWidth()) > GetWidth()*GetWidth()) continue;					patchVertices[x + z * m_patchSize].x = m_pVertices[(x + patchX) + (z + patchZ) * GetWidth()].x;					patchVertices[x + z * m_patchSize].y = m_pVertices[(x + patchX) + (z + patchZ) * GetWidth()].y;					patchVertices[x + z * m_patchSize].z = m_pVertices[(x + patchX) + (z + patchZ) * GetWidth()].z;						patchTexCoords[x + z * m_patchSize].u = (float)((float)((x + patchX) * m_fOffsetX) / GetWidth());					patchTexCoords[x + z * m_patchSize].v = (float)((float)((z + patchZ) * m_fOffsetZ) / GetLength());					patchNormals[x + z * m_patchSize].x =  m_pNormals[(x + patchX) + (z + patchZ) * GetWidth()].x;					patchNormals[x + z * m_patchSize].y =  m_pNormals[(x + patchX) + (z + patchZ) * GetWidth()].y;					patchNormals[x + z * m_patchSize].z =  m_pNormals[(x + patchX) + (z + patchZ) * GetWidth()].z;	                                //find corners of AABB					tmin.x = min(patchVertices[x + z * m_patchSize].x, tmin.x);					tmin.y = min(patchVertices[x + z * m_patchSize].y, tmin.y);					tmin.z = min(patchVertices[x + z * m_patchSize].z, tmin.z);					tmax.x = max(patchVertices[x + z * m_patchSize].x, tmax.x);					tmax.y = max(patchVertices[x + z * m_patchSize].y, tmax.y);					tmax.z = max(patchVertices[x + z * m_patchSize].z, tmax.z);				}								}			//set AABB min/max			new_patch.m_aabb.vecMax = tmax;			new_patch.m_aabb.vecMin = tmin;                        //create the indices + degenerate triangles			unsigned int indexPatchSize = m_patchSize;			for(int z = 0; z < indexPatchSize-1; z++)			{				if(z % 2)				{					int x;					for(x = indexPatchSize-1; x >= 0; x--)					{												new_patch.m_Indices.push_back(x + (z + 1) * m_patchSize);						new_patch.m_Indices.push_back(x + (z    ) * m_patchSize);												}						new_patch.m_Indices.push_back( (z + 1) * m_patchSize );						new_patch.m_Indices.push_back( (z + 1) * m_patchSize );				}				else				{					int x;					for(x = 0; x < indexPatchSize; x++)					{						new_patch.m_Indices.push_back(x + (z    ) * m_patchSize );						new_patch.m_Indices.push_back(x + (z + 1) * m_patchSize );					}						new_patch.m_Indices.push_back( (z + 2) * m_patchSize-1 );						new_patch.m_Indices.push_back( (z + 2) * m_patchSize-1 );				}			}			new_patch.VertexBuffer.setElementList(patchVertices, new_patch.m_vertexCount);			new_patch.TexCoordBuffer.setElementList(patchTexCoords, new_patch.m_vertexCount);			new_patch.NormalBuffer.setElementList(patchNormals, new_patch.m_vertexCount);			new_patch.VertexBuffer.build(GL_ARRAY_BUFFER, GL_VERTEX_ARRAY);			new_patch.TexCoordBuffer.build(GL_ARRAY_BUFFER, GL_TEXTURE_COORD_ARRAY);			new_patch.NormalBuffer.build(GL_ARRAY_BUFFER, GL_NORMAL_ARRAY);			m_vTerrainPatches.push_back(new_patch);			delete [] patchVertices; patchVertices = NULL;			delete [] patchTexCoords; patchTexCoords = NULL;			delete [] patchNormals; patchNormals = NULL;		}	}}


And what I got is:



As you can see the missing z row is now rendered, but the indices for the missing x row are messed up.

I'm sure the problem is the part where I create indices, because when I draw the AABBs now, they appear having the correct size (patchsize+1*patchsize+1).

I played for days with the loop which creates the indices, every try failed.

[Edited by - starvinmarvin on May 4, 2009 5:26:42 PM]

http://www.qbnet.de

Hey starvinmarvin,

What my first reply implied is that your patches should include shared verts. From your code, it looks like using power of two and not power of two +1 patch sizes would make a better fit from your big vertex data. To achieve this, your loop to copy the verticies from your big vertex buffer to your patches should be something like:

	for(unsigned int patchZ = 0; patchZ < GetWidth(); patchZ += (m_patchSize-1))	{		for(unsigned int patchX = 0; patchX < GetWidth(); patchX += (m_patchSize-1))		{			TerrainPatch new_patch;			new_patch.m_vertexCount = (m_patchSize)*(m_patchSize);			flx_Vertex		*patchVertices	= new flx_Vertex[new_patch.m_vertexCount];			flx_TexCoord		*patchTexCoords	= new flx_TexCoord[new_patch.m_vertexCount];			flx_Normal		*patchNormals	= new flx_Normal[new_patch.m_vertexCount];...


Note the:
patchZ += (m_patchSize-1)


in the for loop. This causes us to start copying on the shared vertex which should allow you to have power of two patch sizes which hopefully means the total width/height of the terrain is a multiple of the patch size and also means you shouldn't need:

if(((tx + patchX) + (tz + patchZ) * GetWidth()) > GetWidth()*GetWidth()) continue;


You may also have issues with how you do your indexing, I'm not quite sure what method you are using to compose the mesh. Are you using a single triangle strip? The way I would do a mesh is like so:

Verts:
 0  1  2  3 .  .  .  . 4  5  6  7 .  .  .  . 8  9 10 11 .  .  .  .12 13 14 15 .  .  .  .


Then i would index like so:

0 4 1 5 2 6 3 7 7 7 11 6 10 5 9 4 8 8 8 12 9 13 10 14 11 15 15 15 ...

But there are plenty of other ways.



Quote:Original post by starvinmarvin
@cameni, nverts in those lines doesn't seem right to me
new_patch.m_Indices.push_back( (z + 2) * m_patchSize-1 );


There are m_patchSize+1 vertices in each row of the patch, so the z coords should be multiplied by (m_patchSize+1) row multiplier to get the correct index.

Then you should generate indices for the 2^n+1st vertex too, so the for cycles with x should be extended.
And I think there is a problem with the degenerate triangles in (z+2)*m_patchSize-1, why -1?
Please try this:

if(z % 2){	int x;	for(x = indexPatchSize; x >= 0; x--)	{		new_patch.m_Indices.push_back((z + 1)*nvert + x );		new_patch.m_Indices.push_back(x  + (z * nvert) );				}		new_patch.m_Indices.push_back( (z+1)*nvert );		new_patch.m_Indices.push_back( (z+1)*nvert );}else{	int x;	for(x = 0; x <= indexPatchSize; x++)	{		new_patch.m_Indices.push_back( z*nvert + x );		new_patch.m_Indices.push_back( (z+1)*nvert + x );	}		new_patch.m_Indices.push_back( (z+1)*nvert + indexPatchSize );		new_patch.m_Indices.push_back( (z+2)*nvert + indexPatchSize );}
Outerra
Thanks again to both of you. I tried your solutions, but unfortunately the results are getting even more weird :(

The problem is trivial, actually, but in the end it turns out that it's hard to be solved.

I made a little sketch to explain it a bit better, but I guess that's what you've already understood:



And yes, I'm using triangle strips.
I'm sure the problem is all about the indices.

http://www.qbnet.de

This topic is closed to new replies.

Advertisement

Popular Topics

Aybe One
How do you manage yourself and your time as years pass on? GDNet Lounge
Jikoob
Too many managers? General and Gameplay Programming
ReignOnU
Do your part to stop global warming and climate change GDNet Lounge
Konjointed
C++ how do you use dependency injection? For Beginners
aigan
The promise of freedom in story games Game Design and Theory
robertrobert
Facebook Ads for sales on steam, does it work? Games Business and Law
Advertisement

Recommended Tutorials

Myopic Rhino
Using Abstraction to Optimize Runtime Polymorphism General and Gameplay Programming
DELETE_ME
Character Writing Advice From Writers Writing for Games
Myopic Rhino
OpenGL Tutors Graphics and GPU Programming
Myopic Rhino
S-Buffer FAQ Graphics and GPU Programming
Myopic Rhino
Austin Game Conference and Women's Game Conference 2004 Report Event Coverage

Reticulating splines

About GameDev.net
Community Guidelines
Terms of Service
Privacy Policy
Contact Us
Copyright (c) 1999-2024 GameDev.net, LLC
Back to Top