**0**

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

###
#1
Members - Reputation: **125**

Posted 09 June 2012 - 05:20 AM

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.

###
#2
Members - Reputation: **318**

Posted 09 June 2012 - 11:41 AM

###
#3
Members - Reputation: **125**

Posted 09 June 2012 - 09:24 PM

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?

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:

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

And below is how I construct the node in octree:

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

Thanks a lot!

###
#4
Members - Reputation: **318**

Posted 10 June 2012 - 04:32 AM

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

###
#5
Members - Reputation: **125**

Posted 10 June 2012 - 05:05 AM

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.

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 "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?

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

Thanks!

###
#6
Members - Reputation: **318**

Posted 10 June 2012 - 09:48 AM

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.

###
#7
Members - Reputation: **125**

Posted 12 June 2012 - 06:35 AM

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.

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