Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


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


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
6 replies to this topic

#1 icqqq123   Members   -  Reputation: 125

Like
0Likes
Like

Posted 09 June 2012 - 05:20 AM

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.

Attached Thumbnails

  • rpg.JPG


Sponsor:

#2 Narf the Mouse   Members   -  Reputation: 318

Like
0Likes
Like

Posted 09 June 2012 - 11:41 AM

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?

#3 icqqq123   Members   -  Reputation: 125

Like
0Likes
Like

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 Narf the Mouse   Members   -  Reputation: 318

Like
0Likes
Like

Posted 10 June 2012 - 04:32 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.

#5 icqqq123   Members   -  Reputation: 125

Like
0Likes
Like

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 Narf the Mouse   Members   -  Reputation: 318

Like
0Likes
Like

Posted 10 June 2012 - 09:48 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. :)

#7 icqqq123   Members   -  Reputation: 125

Like
0Likes
Like

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. Posted Image


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




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