Jump to content
  • Advertisement
Sign in to follow this  
starvinmarvin

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.

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

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 vertices
unsigned 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 this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
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 this post


Link to post
Share on other sites
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 );
}

Share this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!