depth sorting

void CRender::DrawTree( OBSERVER *camera,Bsp *node )
{

if ( node==NULL ) return ;

// draw your triangles here
// perform node culling here

float result;

// dot product beetween direction view and
// dividing plane, which you have stored
// in your node as a normal , i hope you did :-))
result=node->Normal[0]*camera->ViewDir[0]+
node->Normal[1]*camera->ViewDir[1]+
node->Normal[2]*camera->ViewDir[2];

if (result > 0)
{


// traversing front

DrawTree ( camera,node->Child[1] );

// perform whatever you like beetween these
// two calls note that you may also draw your triangle list


DrawTree ( camera,node->Child[0] );
}

else

{
// traversing back

DrawTree ( camera,node->Child[0] );

// perform whatever you like beetween these
// two calls note that you may also draw your triangle list

DrawTree ( camera,node->Child[1] );

}

}

note that i''ve called child[0]and child[1] respectlvely the fron and back child , but this really depends on your halfspace dividing function , that''s to say i pick as ''positive'' side
the result of dot( v w ) >0

thanks a lot for your answer

Hmmm... I implemented your the algorithm, but there are still bugs if I turn of the depth-buffer... (but less than before


this is my function.


unsigned long CBspTree:_RenderElement(unsigned long _id, float _frustum[6][4])
{
if (p_BoxInFrustum(&vElements[_id]->vBoundingBox, _frustum))
if (vElements[_id]->vType == EL_NODE)
{
if (p_DotProduct(&vElements[_id]->vSplitter.n, &TVector(_frustum[5][0], _frustum[5][1], _frustum[5][2])) > 0)
return p_RenderElement(vElements[_id]->vFrontElement, _frustum) +
p_RenderElement(vElements[_id]->vBackElement, _frustum);
else
return p_RenderElement(vElements[_id]->vBackElement, _frustum) +
p_RenderElement(vElements[_id]->vFrontElement, _frustum);
} else
if (vElements[_id]->vType == EL_LEAF)
{
vElements[_id]->vPolygonBuffer->p_Render();
return 1;
}
}

the frustum-array contains the 6 planes of the current viewing-frustum. Plane 6 is the near-plane, this normal points into the view-direction, right?
vSplitter.n contains the normal vector of the splitting-plane of the current node.
I think these values are correct, but there are still a few errors if I try to render my map without depth-testing. Does anyone see my fault?

I have tried to reconstruct this concept on paper... it seems not to work in every case...

[edited by - Kaesebrot on May 24, 2002 9:25:49 AM]

It should work if you split your polygones with the BSP Node Planes...
Quake for example doesn''t do that. If your data is from a quake bsp file you cannot render everything perfectly depth sorted.

quote:

---

Original post by noVum
It should work if you split your polygones with the BSP Node Planes...

---

this is exactly what I have done, but it doesn''t work...

Strange , this is the recursive walking i use in my engine, and i''ve disbled the z-depth , and it works, are you sure you are using the positive side for the correct child node ?
and furthermore, i don''t split the triangles if it crosses the splitplane, maybe this is causing you strange results, but the code works, try to move the rendering stuff inside the two calls
but it gives always the same result

quote:

---

Original post by v71
Strange , this is the recursive walking i use in my engine, and i've disbled the z-depth , and it works, are you sure you are using the positive side for the correct child node ?

---

Yeas, I'm shure because I defined the negative side for the "correct" child node. It looked much worse...

may you send me your bsp-creation and bsp-rendering function?



[edited by - Kaesebrot on May 26, 2002 4:43:16 PM]

Hi,
I figured out, that this method isn't correct.. it don't draws in the nodes in the right order in every case. I try to explain it.
Let's say you are standing in a room. The room is surrounded by a wall which is rectangular shaped. In the middle of this room is a cube. You stand beside right side of this cube and you look a bit to the right side of the map.
The room is splitted by a plane which lies on the right side of the cube.
Now, If you use the discriped method of depth-sorting the right side of the cube which belongs to the front-node of the splitting-plane is overdrawn by the wall which belongs to the back-node of the splitting-plane, because the dot product between the direction and the normal of the splitting plane is positive, so the front-node is drawn first. Am I right?

My solution is to build the dot product between the normal of the splitting-plane with each of the four vectors which are lying on the edges of the view-frustum. I hope you can see which edges I mean.. If any of this products is negative, you have to draw the back-node first..

please give me some feetback about this..


[edited by - Kaesebrot on May 27, 2002 4:08:24 PM]