Sign in to follow this  
icqqq123

Problem on using quadtree from the book: Programming RPG with DirectX

Recommended Posts

Dear all,

I have read a book called Programming RPG with DirectX recently and I find a problem on using the quadtree provided by the book.

When I loaded my level using the class cNodeTree in the book, I found that my level was displayed very weird, for example, part of the level disappeared. I have checked the code but I cannot find which piece of code wrong. Therefore, is there any people who have read that book can help me?

Thanks!

PS. attached is a screen shot of my program, you can see that there is missing part of the castle and the grass.

Share this post


Link to post
Share on other sites
[quote name='Narf the Mouse' timestamp='1339263707' post='4947704']
Without code, we can just guess. One guess might be - You're probably using a frustum to get meshes from the octree. Are you doing the Frustum check correctly?
[/quote]

Yes, I am using the frustum to get meshes from octree. I think the Frustum check should be correct as I tried to use a character mesh to perform the same check and the character looked fine.

Below is the checking in Frustum:
[CODE]
BOOL cFrustum::CheckRectangle(float XCenter, float YCenter, float ZCenter, float XSize, float YSize, float ZSize, BOOL *CompletelyContained)
{
short i;
DWORD TotalIn = 0;
// Count the number of points inside the frustum
for(i=0;i<6;i++) {
DWORD Count = 8;
BOOL PointIn = TRUE;

// Test all eight points against plane
if(D3DXPlaneDotCoord(&m_Planes[i], &D3DXVECTOR3(XCenter-XSize, YCenter-YSize, ZCenter-ZSize)) < 0.0f) {
PointIn = FALSE;
Count--;
}
if(D3DXPlaneDotCoord(&m_Planes[i], &D3DXVECTOR3(XCenter+XSize, YCenter-YSize, ZCenter-ZSize)) < 0.0f) {
PointIn = FALSE;
Count--;
}
if(D3DXPlaneDotCoord(&m_Planes[i], &D3DXVECTOR3(XCenter-XSize, YCenter+YSize, ZCenter-ZSize)) < 0.0f) {
PointIn = FALSE;
Count--;
}
if(D3DXPlaneDotCoord(&m_Planes[i], &D3DXVECTOR3(XCenter+XSize, YCenter+YSize, ZCenter-ZSize)) < 0.0f) {
PointIn = FALSE;
Count--;
}
if(D3DXPlaneDotCoord(&m_Planes[i], &D3DXVECTOR3(XCenter-XSize, YCenter-YSize, ZCenter+ZSize)) < 0.0f) {
PointIn = FALSE;
Count--;
}
if(D3DXPlaneDotCoord(&m_Planes[i], &D3DXVECTOR3(XCenter+XSize, YCenter-YSize, ZCenter+ZSize)) < 0.0f) {
PointIn = FALSE;
Count--;
}
if(D3DXPlaneDotCoord(&m_Planes[i], &D3DXVECTOR3(XCenter-XSize, YCenter+YSize, ZCenter+ZSize)) < 0.0f) {
PointIn = FALSE;
Count--;
}
if(D3DXPlaneDotCoord(&m_Planes[i], &D3DXVECTOR3(XCenter+XSize, YCenter+YSize, ZCenter+ZSize)) < 0.0f) {
PointIn = FALSE;
Count--;
}
// If none contained, return FALSE
if(Count == 0)
return FALSE;
// Update counter if they were all in front of plane
TotalIn += (PointIn == TRUE) ? 1:0;
}
// Store BOOL flag if completely contained
if(CompletelyContained != NULL)
*CompletelyContained = (TotalIn == 6) ? TRUE:FALSE;
return TRUE;
}
[/CODE]

And below is how I construct the node in octree:
[CODE]
void cNodeTreeMesh::AddNode(sNode *Node)
{
unsigned long i, Group;
sPolygon *Polygon;
short Num;
if(Node == NULL)
return;
// Perform frustum check based on tree type
BOOL CompletelyContained = FALSE;
if(m_TreeType == QUADTREE) {
if(m_Frustum->CheckRectangle(
Node->XPos, 0.0f, Node->ZPos,
Node->Size / 2.0f, m_Size / 2.0f, Node->Size / 2.0f,
&CompletelyContained) == FALSE)
return;
} else {
if(m_Frustum->CheckRectangle(
Node->XPos, Node->YPos, Node->ZPos,
Node->Size / 2.0f, Node->Size / 2.0f, Node->Size / 2.0f,
&CompletelyContained) == FALSE)
return;
}
if(CompletelyContained == FALSE) {
// Scan other nodes
Num = 0;
for(i=0;i<(unsigned long)((m_TreeType==QUADTREE)?4:8);i++) {
if(Node->Nodes[i] != NULL) {
Num++;
AddNode(Node->Nodes[i]);
}
}

// Don't need to go on if there was other nodes
if(Num)
return;
}
// Add contained polygons (if any)
if(Node->NumPolygons != 0) {
for(i=0;i<Node->NumPolygons;i++) {
// Get pointer to polygon
Polygon = &m_Polygons[Node->PolygonList[i]];
// Only draw if not done already this frame
if(Polygon->Timer != m_Timer) {

// Set polygon as processed this frame
Polygon->Timer = m_Timer;
// Get material group of polygon
Group = Polygon->Group;
// Make sure group is okay and material is not transparent
if(Group < m_NumGroups && m_Mesh->m_Materials[Group].Diffuse.a != 0.0f) {
// Copy indices into index buffer
*m_Groups[Group].IndexPtr++ = Polygon->Vertex0;
*m_Groups[Group].IndexPtr++ = Polygon->Vertex1;
*m_Groups[Group].IndexPtr++ = Polygon->Vertex2;

// Increase count of polygons to draw in group
m_Groups[Group].NumPolygonsToDraw++;
}
}
}
}
}
[/CODE]

Thanks a lot!

Share this post


Link to post
Share on other sites
Only two things I can see at this point is (3:29 AM and having trouble sleeping), you're checking for complete containment - But if the frustum only intersects part of the object, then the object won't be visible to the camera, resulting in objects disappearing before they fully leave the screen.

Also, if your IDE supports it, try stepping through the bounds check and checking the values.

Share this post


Link to post
Share on other sites
[quote name='Narf the Mouse' timestamp='1339324320' post='4947872']
Only two things I can see at this point is (3:29 AM and having trouble sleeping), you're checking for complete containment - But if the frustum only intersects part of the object, then the object won't be visible to the camera, resulting in objects disappearing before they fully leave the screen.

Also, if your IDE supports it, try stepping through the bounds check and checking the values.
[/quote]

Sorry, could you tell me which part perform complete containment checking so that "if the frustum only intersects part of the object, then the object won't be visible to the camera"? Since in the code of [font=monospace]"[/font]AddNode()", it checks if the node is inside the frustum, and checks if it is totally contained inside the frustum. If not totally contained but partially, it will be further divided to 8 or 4 child nodes so that the child nodes are totally contained in side the frustum. I think the logic is correct, but I cannot find out the reason why I get the result shown in the attachment.

Below is the code of the construction of the frustum, is there any problem of that?
[CODE]
BOOL cFrustum::Construct(cGraphics *Graphics, float ZDistance)
{
D3DXMATRIX Matrix, matView, matProj;
float ZMin, Q;
// Error checking
if(Graphics == NULL)
return FALSE;
// Calculate FOV data
Graphics->GetDeviceCOM()->GetTransform(D3DTS_PROJECTION, &matProj);
if(ZDistance != 0.0f) {
// Calculate new projection matrix based on distance provided
ZMin = -matProj._43 / matProj._33;
Q = ZDistance / (ZDistance - ZMin);
matProj._33 = Q;
matProj._43 = -Q * ZMin;
}
Graphics->GetDeviceCOM()->GetTransform(D3DTS_VIEW, &matView);
D3DXMatrixMultiply(&Matrix, &matView, &matProj);
// Calculate the planes
m_Planes[0].a = Matrix._14 + Matrix._13; // Near
m_Planes[0].b = Matrix._24 + Matrix._23;
m_Planes[0].c = Matrix._34 + Matrix._33;
m_Planes[0].d = Matrix._44 + Matrix._43;
D3DXPlaneNormalize(&m_Planes[0], &m_Planes[0]);
m_Planes[1].a = Matrix._14 - Matrix._13; // Far
m_Planes[1].b = Matrix._24 - Matrix._23;
m_Planes[1].c = Matrix._34 - Matrix._33;
m_Planes[1].d = Matrix._44 - Matrix._43;
D3DXPlaneNormalize(&m_Planes[1], &m_Planes[1]);
m_Planes[2].a = Matrix._14 + Matrix._11; // Left
m_Planes[2].b = Matrix._24 + Matrix._21;
m_Planes[2].c = Matrix._34 + Matrix._31;
m_Planes[2].d = Matrix._44 + Matrix._41;
D3DXPlaneNormalize(&m_Planes[2], &m_Planes[2]);
m_Planes[3].a = Matrix._14 - Matrix._11; // Right
m_Planes[3].b = Matrix._24 - Matrix._21;
m_Planes[3].c = Matrix._34 - Matrix._31;
m_Planes[3].d = Matrix._44 - Matrix._41;
D3DXPlaneNormalize(&m_Planes[3], &m_Planes[3]);
m_Planes[4].a = Matrix._14 - Matrix._12; // Top
m_Planes[4].b = Matrix._24 - Matrix._22;
m_Planes[4].c = Matrix._34 - Matrix._32;
m_Planes[4].d = Matrix._44 - Matrix._42;
D3DXPlaneNormalize(&m_Planes[4], &m_Planes[4]);
m_Planes[5].a = Matrix._14 + Matrix._12; // Bottom
m_Planes[5].b = Matrix._24 + Matrix._22;
m_Planes[5].c = Matrix._34 + Matrix._32;
m_Planes[5].d = Matrix._44 + Matrix._42;
D3DXPlaneNormalize(&m_Planes[5], &m_Planes[5]);
return TRUE;
}
[/CODE]

Thanks!

Share this post


Link to post
Share on other sites
Ok, looking at it awake -

1) Your Frustum check returns false (if I'm reading this correctly) if any part of the box is not contained in the Frustum. You want it to return true if any part of the box is contained in the Frustum, to get partial containment.
2) This means "return" is called when something isn't completely contained.

Run it in the debugger and see if I know what I'm talking about. :)

Share this post


Link to post
Share on other sites
[quote name='Narf the Mouse' timestamp='1339343335' post='4947939']
Ok, looking at it awake -

1) Your Frustum check returns false (if I'm reading this correctly) if any part of the box is not contained in the Frustum. You want it to return true if any part of the box is contained in the Frustum, to get partial containment.
2) This means "return" is called when something isn't completely contained.

Run it in the debugger and see if I know what I'm talking about. [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]
[/quote]

Not really, Frustum set PointIn = FALSE; and Count-- if any part of the box is not contained in the Frustum, but it return TRUE unless Count == 0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this