# Terrain chunks and index arrays

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

## Recommended Posts

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]

##### Share on other sites
I don't want to annoy you, but I still haven't solved the problem myself :(

##### Share on other sites
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]

##### Share on other sites
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)?

##### Share on other sites
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]

##### Share on other sites
Quote:
 Original post by starvinmarvinThank 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]

##### Share on other sites
Quote:
 Original post by camenim_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]

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by starvinmarvin@cameni, nverts in those lines doesn't seem right to menew_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?

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 );}

##### Share on other sites
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.

1. 1
2. 2
Rutin
23
3. 3
4. 4
5. 5
khawk
14

• 9
• 11
• 11
• 23
• 11
• ### Forum Statistics

• Total Topics
633653
• Total Posts
3013158
×