Jump to content

  • Log In with Google      Sign In   
  • Create Account


Quadtree/terrain frustum culling help


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
4 replies to this topic

#1 newtechnology   Members   -  Reputation: 627

Like
0Likes
Like

Posted 11 January 2014 - 08:09 AM

I tried to implement frustum culling of terrain by my own but unfortunately, I failed.

I also searched the forums but didn't found any good tutorials on frustum culling on terrain, so can anyone help me out with this (by just linking/giving a good tutorial on terrain frustum cull.)



Sponsor:

#2 ericrrichards22   Members   -  Reputation: 746

Like
0Likes
Like

Posted 11 January 2014 - 12:09 PM

There are a few different ways you could do this.

  • If you are using DX11, you can do frustum culling in the hull shader.  I've got a post on how I implemented the terrain example from Luna's DX11 book in SlimDX (the relevant parts are HLSL, so that shouldn't be a problem if you're using C++ rather than C#).
  • If you are using DX10, I would imagine you could do something similar using the geometry shader, although I don't have any examples off the shelf to point you to.
  • You could also do the culling on the CPU, by dividing your terrain mesh up into patches, and culling based on the bounding box of the patch.  O have another article using this technique, although I imagine there are a fair number of other resources, since this is a fairly established way of doing terrain culling.

Eric Richards

SlimDX tutorials - http://www.richardssoftware.net/

Twitter - @EricRichards22


#3 newtechnology   Members   -  Reputation: 627

Like
0Likes
Like

Posted 12 January 2014 - 05:02 AM

I'm using third method, here is my code, I don't know whats going wrong.

I get vector subscript out of range error.

using namespace std;
 
class Terrain
{
private:
struct SubGrid
{
SubGrid()
{
VertexBuffer = 0;
IndexBuffer = 0;
}
 
GeometryGenerator::MeshData mesh;
XNA::AxisAlignedBox box;
 
ID3D11Buffer* VertexBuffer;
ID3D11Buffer* IndexBuffer;
 
bool operator < (const SubGrid& rhs)const;
 
const static int NUM_ROWS  = 33;
const static int NUM_COLS  = 33;
const static int NUM_TRIS  = (NUM_ROWS-1)*(NUM_COLS-1)*2;
const static int NUM_VERTS = NUM_ROWS*NUM_COLS;
};
public:
struct InitInfo
{
wstring HeightmapFileName,
LayerMapFileName0,
LayerMapFileName1,
LayerMapFileName2,
LayerMapFileName3,
LayerMapFileName4,
BlendMapFileName;
 
float HeightScale;
float HeightOffset;
UINT NumRows;
UINT NumCols;
float CellSpacing;
};
 
public:
Terrain();
~Terrain();
 
void Init(const InitInfo& info);
 
float width()const;
float depth()const;
 
float getHeight(float x, float y)const;
void SetDirectionToSun(const XMFLOAT3& v);
void draw(CXMMATRIX world, Camera& cam);
 
UINT GetNumVertices()const { return mNumVertices; }
private:
void BuildFX();
void loadHeightMap();
void Smooth();
bool inBounds(UINT i, UINT j);
float average(UINT i, UINT j);
void BuildGeometry();
void BuildSubGrid(RECT &R, Vertex::Basic32* gridVerts);
private:
InitInfo mInfo;
UINT mNumVertices;
UINT mNumFaces;
 
vector<float> mHeightmap;
vector<SubGrid> mSubGrids;
 
ID3DX11Effect* mFX;
 
 
ID3D11Buffer* mVB;
ID3D11Buffer* mIB;
 
ID3D11ShaderResourceView* mLayer0;
ID3D11ShaderResourceView* mLayer1;
ID3D11ShaderResourceView* mLayer2;
ID3D11ShaderResourceView* mLayer3;
ID3D11ShaderResourceView* mLayer4;
ID3D11ShaderResourceView* mBlendMap;
 
ID3DX11EffectTechnique* mTech;
ID3DX11EffectMatrixVariable* mfxWVPVar;
ID3DX11EffectMatrixVariable* mfxWorldVar;
ID3DX11EffectVectorVariable* mfxDirToSunVar;
ID3DX11EffectShaderResourceVariable* mfxLayer0Var;
ID3DX11EffectShaderResourceVariable* mfxLayer1Var;
ID3DX11EffectShaderResourceVariable* mfxLayer2Var;
ID3DX11EffectShaderResourceVariable* mfxLayer3Var;
ID3DX11EffectShaderResourceVariable* mfxLayer4Var;
ID3DX11EffectShaderResourceVariable* mfxBlendMapVar;
 
};
//====================================================================================================================================
#include "stdafx.h"
#include <list>
 
Terrain::Terrain()
{
 
mVB = nullptr;
mIB = nullptr;
 
 
mLayer0 = nullptr;
mLayer1 = nullptr;
mLayer2 = nullptr;
mLayer3 = nullptr;
mLayer4 = nullptr;
mBlendMap = nullptr;
}
 
Terrain::~Terrain()
{
ReleaseCOM(mVB);
ReleaseCOM(mIB);
ReleaseCOM(mFX);
 
 
ReleaseCOM(mBlendMap);
ReleaseCOM(mLayer0);
ReleaseCOM(mLayer1);
ReleaseCOM(mLayer2);
ReleaseCOM(mLayer3);
ReleaseCOM(mLayer4);
 
for (UINT i = 0; i < mSubGrids.size(); ++i)
{
ReleaseCOM(mSubGrids[i].VertexBuffer);
ReleaseCOM(mSubGrids[i].IndexBuffer);
}
}
 
float Terrain::width()const
{
return (mInfo.NumCols-1)*mInfo.CellSpacing;
}
 
float Terrain::depth()const
{
return (mInfo.NumRows-1)*mInfo.CellSpacing;
}
 
float Terrain::getHeight(float x, float z)const
{
// Transform from terrain local space to "cell" space.
float c = (x + 0.5f*width()) /  mInfo.CellSpacing;
float d = (z - 0.5f*depth()) / -mInfo.CellSpacing;
 
// Get the row and column we are in.
int row = (int)floorf(d);
int col = (int)floorf(c);
 
// Grab the heights of the cell we are in.
// A*--*B
//  | /|
//  |/ |
// C*--*D
float A = mHeightmap[row*mInfo.NumCols + col];
float B = mHeightmap[row*mInfo.NumCols + col + 1];
float C = mHeightmap[(row+1)*mInfo.NumCols + col];
float D = mHeightmap[(row+1)*mInfo.NumCols + col + 1];
 
// Where we are relative to the cell.
float s = c - (float)col;
float t = d - (float)row;
 
// If upper triangle ABC.
if( s + t <= 1.0f)
{
float uy = B - A;
float vy = C - A;
return A + s*uy + t*vy;
}
else // lower triangle DCB.
{
float uy = C - D;
float vy = B - D;
return D + (1.0f-s)*uy + (1.0f-t)*vy;
}
}
 
void Terrain::BuildFX()
{
std::ifstream fin("Resources\\Shaders\\Terrain.fxo", std::ios::binary);
 
fin.seekg(0, std::ios_base::end);
int size = (int)fin.tellg();
fin.seekg(0, std::ios_base::beg);
std::vector<char> compiledShader(size);
 
fin.read(&compiledShader[0], size);
fin.close();
 
HR(D3DX11CreateEffectFromMemory(&compiledShader[0], size, 
0, pDevice, &mFX));
}
 
void Terrain::Init(const InitInfo& initInfo)
{
BuildFX();
 
mTech          = mFX->GetTechniqueByName("TerrainTech");
mfxWVPVar      = mFX->GetVariableByName("gWVP")->AsMatrix();
mfxWorldVar    = mFX->GetVariableByName("gWorld")->AsMatrix();
mfxDirToSunVar = mFX->GetVariableByName("gDirToSunW")->AsVector();
mfxLayer0Var   = mFX->GetVariableByName("gLayer0")->AsShaderResource();
mfxLayer1Var   = mFX->GetVariableByName("gLayer1")->AsShaderResource();
mfxLayer2Var   = mFX->GetVariableByName("gLayer2")->AsShaderResource();
mfxLayer3Var   = mFX->GetVariableByName("gLayer3")->AsShaderResource();
mfxLayer4Var   = mFX->GetVariableByName("gLayer4")->AsShaderResource();
mfxBlendMapVar = mFX->GetVariableByName("gBlendMap")->AsShaderResource();
 
mInfo = initInfo;
 
mNumVertices = mInfo.NumRows*mInfo.NumCols;
mNumFaces    = (mInfo.NumRows-1)*(mInfo.NumCols-1)*2;
 
loadHeightMap();
Smooth();
 
BuildGeometry();
 
HR(D3DX11CreateShaderResourceViewFromFile(pDevice, initInfo.LayerMapFileName0.c_str(), 0, 0, &mLayer0, 0));
HR(D3DX11CreateShaderResourceViewFromFile(pDevice, initInfo.LayerMapFileName1.c_str(), 0, 0, &mLayer1, 0));
HR(D3DX11CreateShaderResourceViewFromFile(pDevice, initInfo.LayerMapFileName2.c_str(), 0, 0, &mLayer2, 0));
HR(D3DX11CreateShaderResourceViewFromFile(pDevice, initInfo.LayerMapFileName3.c_str(), 0, 0, &mLayer3, 0));
HR(D3DX11CreateShaderResourceViewFromFile(pDevice, initInfo.LayerMapFileName4.c_str(), 0, 0, &mLayer4, 0));
HR(D3DX11CreateShaderResourceViewFromFile(pDevice, initInfo.BlendMapFileName.c_str(), 0, 0, &mBlendMap, 0));
}
 
void Terrain::SetDirectionToSun(const XMFLOAT3& v)
{
XMVECTOR temp = XMVectorSet(v.x, v.y, v.z, 0.0f);
mfxDirToSunVar->SetFloatVector((float*)&temp);
}
 
void Terrain::draw(CXMMATRIX world, Camera& cam)
{
pDeviceContext->IASetInputLayout(InputLayouts::Basic32);
 
UINT stride = sizeof(Vertex::Basic32);
    UINT offset = 0;
 
 
std::list<SubGrid> visibleSubGrids;
for(UINT i = 0; i < mSubGrids.size(); ++i)
{
if( XNA::IntersectAxisAlignedBoxFrustum(&mSubGrids[i].box, &d3d->GetFrustum()))
visibleSubGrids.push_back(mSubGrids[i]);
}
 
// Sort front-to-back from camera.
visibleSubGrids.sort();
 
 
 
for(std::list<SubGrid>::iterator iter = visibleSubGrids.begin(); iter != visibleSubGrids.end(); ++iter)
{
pDeviceContext->IASetVertexBuffers(0, 1, &iter->VertexBuffer, &stride, &offset);
pDeviceContext->IASetIndexBuffer(iter->IndexBuffer, DXGI_FORMAT_R32_UINT, 0);
 
}
 
 
XMMATRIX view = cam.View();
XMMATRIX proj = cam.Proj();
 
XMMATRIX WVP = world * view * proj;
 
 
mfxWVPVar->SetMatrix((float*)&WVP);
mfxWorldVar->SetMatrix((float*)&world);
 
mfxLayer0Var->SetResource(mLayer0);
mfxLayer1Var->SetResource(mLayer1);
mfxLayer2Var->SetResource(mLayer2);
mfxLayer3Var->SetResource(mLayer3);
mfxLayer4Var->SetResource(mLayer4);
mfxBlendMapVar->SetResource(mBlendMap);
 
    D3DX11_TECHNIQUE_DESC techDesc;
    mTech->GetDesc(&techDesc);
 
    for(UINT i = 0; i < techDesc.Passes; ++i)
    {
        ID3DX11EffectPass* pass = mTech->GetPassByIndex(i);
pass->Apply(0, pDeviceContext);
 
for(std::list<SubGrid>::iterator iter = visibleSubGrids.begin(); iter != visibleSubGrids.end(); ++iter)
pDeviceContext->DrawIndexed(iter->mesh.Indices.size(), 0, 0);
} 
}
 
void Terrain::loadHeightMap()
{
// A height for each vertex
std::vector<unsigned char> in( mInfo.NumRows * mInfo.NumCols );
 
// Open the file.
std::ifstream inFile;
inFile.open(mInfo.HeightmapFileName.c_str(), std::ios_base::binary);
 
if(inFile)
{
// Read the RAW bytes.
inFile.read((char*)&in[0], (std::streamsize)in.size());
 
// Done with file.
inFile.close();
}
 
// Copy the array data into a float array, and scale and offset the heights.
mHeightmap.resize(mInfo.NumRows * mInfo.NumCols, 0);
for(UINT i = 0; i < mInfo.NumRows * mInfo.NumCols; ++i)
{
mHeightmap[i] = (float)in[i] * mInfo.HeightScale + mInfo.HeightOffset;
}
}
 
 
void Terrain::Smooth()
{
std::vector<float> dest( mHeightmap.size() );
 
for(UINT i = 0; i < mInfo.NumRows; ++i)
{
for(UINT j = 0; j < mInfo.NumCols; ++j)
{
dest[i*mInfo.NumCols+j] = average(i,j);
}
}
 
// Replace the old heightmap with the filtered one.
mHeightmap = dest;
}
 
bool Terrain::SubGrid::operator<(const SubGrid& rhs) const
{
 
XMFLOAT3 camerapos = d3d->GetCameraPosition();
 
XMVECTOR d1 = XMLoadFloat3(&box.Center) - XMLoadFloat3(&camerapos);
XMVECTOR d2 = XMLoadFloat3(&rhs.box.Center) - XMLoadFloat3(&camerapos);
 
XMVECTOR v1, v2;
    v1 = XMVector3LengthSq(d1);
v2 = XMVector3LengthSq(d2);
 
XMFLOAT2 vv1, vv2;
 
    XMStoreFloat2(&vv1, v1);
XMStoreFloat2(&vv2, v2);
 
FLOAT Scalar1, Scalar2;
 
Scalar1 = vv1.x;
Scalar2 = vv2.y;
 
return Scalar1 < Scalar2;
}
 
bool Terrain::inBounds(UINT i, UINT j)
{
// True if ij are valid indices; false otherwise.
return 
i >= 0 && i < mInfo.NumRows && 
j >= 0 && j < mInfo.NumCols;
}
 
float Terrain::average(UINT i, UINT j)
{
// Function computes the average height of the ij element.
// It averages itself with its eight neighbor pixels.  Note
// that if a pixel is missing neighbor, we just don't include it
// in the average--that is, edge pixels don't have a neighbor pixel.
//
// ----------
// | 1| 2| 3|
// ----------
// |4 |ij| 6|
// ----------
// | 7| 8| 9|
// ----------
 
float avg = 0.0f;
float num = 0.0f;
 
for(UINT m = i-1; m <= i+1; ++m)
{
for(UINT n = j-1; n <= j+1; ++n)
{
if( inBounds(m,n) )
{
avg += mHeightmap[m*mInfo.NumCols + n];
num += 1.0f;
}
}
}
 
return avg / num;
}
 
 
 
void Terrain::BuildGeometry()
{
//=========================================
//               Build Vertices
//=========================================
 
std::vector<Vertex::Basic32> vertices(mNumVertices);
 
float halfWidth = (mInfo.NumCols-1)*mInfo.CellSpacing*0.5f;
float halfDepth = (mInfo.NumRows-1)*mInfo.CellSpacing*0.5f;
 
float du = 1.0f / (mInfo.NumCols-1);
float dv = 1.0f / (mInfo.NumRows-1);
for(UINT i = 0; i < mInfo.NumRows; ++i)
{
float z = halfDepth - i*mInfo.CellSpacing;
for(UINT j = 0; j < mInfo.NumCols; ++j)
{
float x = -halfWidth + j*mInfo.CellSpacing;
 
float y = mHeightmap[i*mInfo.NumCols+j];
vertices[i*mInfo.NumCols+j].Pos    = XMFLOAT3(x, y, z);
vertices[i*mInfo.NumCols+j].Normal = XMFLOAT3(0.0f, 1.0f, 0.0f);
 
// Stretch texture over grid.
vertices[i*mInfo.NumCols+j].Tex.x = j*du;
vertices[i*mInfo.NumCols+j].Tex.y = i*dv;
}
}
 
// Estimate normals for interior nodes using central difference.
float invTwoDX = 1.0f / (2.0f*mInfo.CellSpacing);
float invTwoDZ = 1.0f / (2.0f*mInfo.CellSpacing);
for(UINT i = 2; i < mInfo.NumRows-1; ++i)
{
for(UINT j = 2; j < mInfo.NumCols-1; ++j)
{
float t = mHeightmap[(i-1)*mInfo.NumCols + j];
float b = mHeightmap[(i+1)*mInfo.NumCols + j];
float l = mHeightmap[i*mInfo.NumCols + j - 1];
float r = mHeightmap[i*mInfo.NumCols + j + 1];
 
XMFLOAT3 tanZ(0.0f, (t-b)*invTwoDZ, 1.0f);
XMFLOAT3 tanX(1.0f, (r-l)*invTwoDX, 0.0f);
 
XMVECTOR N;
N = XMVector3Cross(XMLoadFloat3(&tanZ), XMLoadFloat3(&tanX));
N = XMVector3Normalize(N);
 
XMStoreFloat3(&vertices[i * mInfo.NumCols + j].Normal, N);
 
}
}
 
//=======================================================
//                     Build Indices
//=======================================================
 
std::vector<DWORD> indices(mNumFaces*3); // 3 indices per face
 
// Iterate over each quad and compute indices.
int k = 0;
for(UINT i = 0; i < mInfo.NumRows-1; ++i)
{
for(UINT j = 0; j < mInfo.NumCols-1; ++j)
{
indices[k]   = i*mInfo.NumCols+j;
indices[k+1] = i*mInfo.NumCols+j+1;
indices[k+2] = (i+1)*mInfo.NumCols+j;
 
indices[k+3] = (i+1)*mInfo.NumCols+j;
indices[k+4] = i*mInfo.NumCols+j+1;
indices[k+5] = (i+1)*mInfo.NumCols+j+1;
 
k += 6; // next quad
}
}
 
 
//===============================================================
// Now break the grid up into subgrid meshes.
 
// Find out the number of subgrids we'll have.  For example, if
// m = 513, n = 257, SUBGRID_VERT_ROWS = SUBGRID_VERT_COLS = 33,
// then subGridRows = 512/32 = 16 and sibGridCols = 256/32 = 8.
int subGridRows = (mInfo.NumRows-1) / (SubGrid::NUM_ROWS-1);
int subGridCols = (mInfo.NumCols-1) / (SubGrid::NUM_COLS-1);
 
for(int r = 0; r < subGridRows; ++r)
{
for(int c = 0; c < subGridCols; ++c)
{
// Rectangle that indicates (via matrix indices ij) the
// portion of grid vertices to use for this subgrid.
RECT R = 
{
c * (SubGrid::NUM_COLS - 1),
r * (SubGrid::NUM_ROWS - 1),
(c+1) * (SubGrid::NUM_COLS - 1),
(r+1) * (SubGrid::NUM_ROWS - 1)
};
 
BuildSubGrid(R, &vertices[0]); 
}
}
 
    D3D11_BUFFER_DESC vbd;
    vbd.Usage = D3D11_USAGE_IMMUTABLE;
vbd.ByteWidth = sizeof(Vertex::Basic32) * mNumVertices;
    vbd.BindFlags = D3D11_BIND_VERTEX_BUFFER;
    vbd.CPUAccessFlags = 0;
    vbd.MiscFlags = 0;
 
    
for (int i = 0; i < mSubGrids.size(); i++)
{
   D3D11_SUBRESOURCE_DATA vinitData;
vinitData.pSysMem = mSubGrids[i].VertexBuffer;  
 
HR(pDevice->CreateBuffer(&vbd, &vinitData, &mSubGrids[i].VertexBuffer));
}
 
D3D11_BUFFER_DESC ibd;
    ibd.Usage = D3D11_USAGE_IMMUTABLE;
    ibd.ByteWidth = sizeof(DWORD) * mNumFaces * 3;
    ibd.BindFlags = D3D11_BIND_INDEX_BUFFER;
    ibd.CPUAccessFlags = 0;
    ibd.MiscFlags = 0;
 
    
for (int i = 0; i < mSubGrids.size(); ++i)
{    
D3D11_SUBRESOURCE_DATA iinitData;
iinitData.pSysMem = mSubGrids[i].IndexBuffer;
 
HR(pDevice->CreateBuffer(&ibd, &iinitData, &mSubGrids[i].IndexBuffer)); 
}
}
 
 
void Terrain::BuildSubGrid(RECT &R, Vertex::Basic32* gridVerts)
{
 
 
GeometryGenerator::MeshData temp;
GeometryGenerator gen;
 
gen.CreateGrid(SubGrid::NUM_ROWS, SubGrid::NUM_COLS,
SubGrid::NUM_ROWS * mInfo.CellSpacing, SubGrid::NUM_COLS * mInfo.CellSpacing, temp);
 
GeometryGenerator::MeshData subMesh;
 
int k = 0;
for(int i = R.top; i <= R.bottom; ++i)
{
for(int j = R.left; j <= R.right; ++j)
{
 
subMesh.Vertices[k++].Position = gridVerts[i*mInfo.NumCols+j].Pos;
}
}
 
XNA::AxisAlignedBox box;
XNA::ComputeBoundingAxisAlignedBoxFromPoints(&box, subMesh.Vertices.size(), &subMesh.Vertices[0].Position, sizeof(Vertex::Basic32));
  
 
for (int i = 0; i < SubGrid::NUM_TRIS; i++)
{
subMesh.Indices[i*3+0] = temp.Indices[i*3+0];
subMesh.Indices[i*3+1] = temp.Indices[i*3+1];
subMesh.Indices[i*3+2] = temp.Indices[i*3+2];
}
 
SubGrid g;
 
g.mesh = subMesh;
g.box = box;
 
mSubGrids.push_back(g);
}


#4 greenpig83   Members   -  Reputation: 325

Like
0Likes
Like

Posted 12 January 2014 - 12:07 PM

This is the tut i used for quadtree : http://rastertek.com/tertut05.html
And this is for frustum culling : http://www.flipcode.com/archives/Frustum_Culling.shtml
Here also : http://www.chadvernon.com/blog/resources/directx9/frustum-culling/
I think combine this 2, can help u !

#5 newtechnology   Members   -  Reputation: 627

Like
0Likes
Like

Posted 13 January 2014 - 08:28 AM

I can't because I use XNAMath.

Anyways, I changed the code but still not getting it to work. (getting vector subscript out of range error.)

http://pastebin.com/kSibZFEf






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS