## SolidLeafBSP and Collision detection with Shifting plane

### SolidLeafBSP and Collision detection with Shifting plane

In my engine I used the SolidLeafBSp, with them I calculate the PVS. Now I
wanna implement the Collision detection and response.
I am currently trying to implement the shifting plane technique described in
the paper of Stan Melax. I am sorry if some of this question will seems
really simple but I couldn't manage to have the algorithm works fine .
Well firstly I say that I refer to the pseudocode that you can find in the
Melax page. The pseudo code that I use is the one that return the normal and
the point of impact.You can find the pseudo code that I used to implement
http://www.cs.ualberta.ca/~melax/bsp/feedback.html

Problems:
1) Somethime I get stoped in empty space but this is ok because I didn't do
the beveling of my Tree and so this behaviour it is the same that Melax
described in his paper when it didn't do the bevel step.
2)Sometimes I get inside the wall and I think this doesn't depend on the
beveling step.
Well now the questions :
1)I don't uderstand why there is this line of code:

vector new_normal = (dot(n->normal,v1-v0)>0)? -n : n

Well this menas that when the angle A between the direction point of my
object on which I test the Collision detection and the normal of plane
is -90<A<90 I should invert the normal of the plane. I suppose that with n
the pseudo code means the normal of plane of the node n. Or it means that I
have to negate also the D of the plane equation???? I ask this because I
would like to know if I should pass the new negate normal (or the the
newnegated plane) to the funciton SegmentBack and SegmentFront when the
dot(n->normal,v1-v0)>0. Actually I try both the method and still I got
problem. This is the last implementation of my  HitCheckBSP function:

bool BSPRenderer::HitCheckBSP(int node,D3DXVECTOR3 v0,D3DXVECTOR3 v1,
D3DXVECTOR3
current_normal,D3DXVECTOR3& impact_normal,
D3DXVECTOR3&
impact_point,float offset)
{
bool hit = false;
D3DXVECTOR3 w0,w1;
D3DXVECTOR3 n;

n.x = PlaneArray[NodeArray[node].Plane].Normal.x;
n.y = PlaneArray[NodeArray[node].Plane].Normal.y;
n.z = PlaneArray[NodeArray[node].Plane].Normal.z;

if(NodeArray[node].IsLeaf == 1)
return false;

float dot_result;

dot_result = D3DXVec3Dot(&n,&(v1-v0));
D3DXVECTOR3 new_normal = (dot_result >0.0f)? -n : n;

if(dot_result>0.0f)
{
PLANE Inv_plane;
Inv_plane.Normal = new_normal;
Inv_plane.Distance = PlaneArray[NodeArray[node].Plane].Distance;
if(SegmentBack(Inv_plane,v0,v1,&w0,&w1,offset))
{
if (NodeArray[node].Back == -1)
{
impact_point.x = w0.x;
impact_point.y = w0.y;
impact_point.z = w0.z;

impact_normal.x = (w0==v0)?current_normal.x:new_normal.x;
impact_normal.y = (w0==v0)?current_normal.y:new_normal.y;
impact_normal.z = (w0==v0)?current_normal.z:new_normal.z;

hit = true;
v1.x = impact_point.x;
v1.y = impact_point.y;
v1.z = impact_point.z;

}
else
{
hit = HitCheckBSP(NodeArray[node].Back,w0,w1,
(w0==v0)?current_normal:new_normal,
impact_normal,
impact_point,
offset);
if(hit)
{
v1.x = impact_point.x;
v1.y = impact_point.y;
v1.z = impact_point.z;
}
}

}

if(SegmentFront(Inv_plane,v0,v1,&w0,&w1,-offset))
hit |= HitCheckBSP(NodeArray[node].Front,w0,w1,
(w0==v0)?current_normal :
new_normal,
impact_normal,
impact_point,
offset);

return hit;

}

/* I GET INSIDE THE ELSE IF dot_result <=0.0f*/
else
{
PLANE Inv_plane;
Inv_plane.Normal = new_normal;
Inv_plane.Distance = PlaneArray[NodeArray[node].Plane].Distance;

if(SegmentFront(Inv_plane,v0,v1,&w0,&w1,-offset))
{
hit = HitCheckBSP(NodeArray[node].Front,w0,w1,
(w0==v0)?current_normal :
new_normal,
impact_normal,
impact_point,
offset);

if(hit)

v1.x = impact_point.x;
v1.y = impact_point.y;
v1.z = impact_point.z;
}

}

if(SegmentBack(Inv_plane,v0,v1,&w0,&w1,offset))
{
if (NodeArray[node].Back == -1)
{
hit |= true;
// point of impact
impact_point.x = w0.x;
impact_point.y = w0.y;
impact_point.z = w0.z;

impact_normal.x = (w0==v0)?current_normal.x:new_normal.x;
impact_normal.y = (w0==v0)?current_normal.y:new_normal.y;
impact_normal.z = (w0==v0)?current_normal.z:new_normal.z;

}
else
{
hit |= HitCheckBSP(NodeArray[node].Back,w0,w1,

(w0==v0)?current_normal:new_normal,
impact_normal,
impact_point,
offset);

}
}

return hit;
}

}

I also try to pass the plane equation of the node (whithout any change) to
the function SegmentBack &SegmentFront but still Igot  inside solid space in
some cases. Actually I don't really understand why I should negate the plane
normal when the dot >0.0f.  Maybe I didn't understand what Melax means with
that line of code. If I negate the normal of the plane I will have a new
plane specular by the origin(I don't think that this is the correct geometry
word but I hope you understand)   with  the old one.I don't think that we
want to test if our mevement line is in pisitive or negative half-space of
this new plane.
SO do I need to use beveling to solve the problem or is it a bug in my code?
I hope that some of you can see where I am doing wrong.

2)This how I implement the n shifted upward and n shifted downward:
Suppose that offset is the radius of the sphere that I am using for the
collision detection and Ax+By+Cz+D = 0 is the plane equation then "n shifted
upward" is just:
Ax+By+Cz+(D-offset) = 0
And n shifted downward is
Ax+By+Cz+(D+offset) = 0  :
In the my code SegmentBack is the SegmentUnder of the pseudocode and
SegmentFront is the segmentAbove.
Just to be precise the normal of my plane are unit vector.
Is this correct?Or is this the error?
Thanks

Hello,

it is a common method to represent two objects as convex polyhedra for
collision detection and to try to find a separating plane.
I always read that the plane's normal either has to be the face direction of
one of the polyhedra's faces, or the cross-product of one edge of the one
polyhedron and one of the other.
I understand the first part. But why also the cross-product? I just can't
find any case where using a face as a separation plane wouldn't be enough;
i.e. that I checked all the faces, couldn't find a separation plane but the
objects still don't collide.

I would be very grateful if anyone could point me to such a case.
Thanks

Gerhard