Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

shadow12345

finding planes crossed using a BSP tree

This topic is 5576 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've been working on an iterative approach to my BSP collision detection. Right now I am trying to find what planes the start and endpoints span (if they are not in the same leaf). If worse comes to worse I will implement this recursively (which in all honestly does make more sense in this case). However I've put many attempts into this approach and I would like to have some assistance. I'm not trying to 'reinvent the wheel', I've just been implementing it the way I saw the problem. The first step I take is I find the closest ancestor node shared between the starting and end leafs. The ancestor node is the first leaf that is spanned by the start and endpoints(assuming the start and end leafs are not the same). I go from the startleaf up the BSP tree (traversing nodes using precalculated parent node indices) to the ancestor node tagging all of the planes crossed(they are stored in an std::vector). I then go from the endleaf up the bsp tree to the ancestor again tagging the planes that are crossed. I then calculate the fraction from the starting point to the plane (minus EPSILON units) and store these fractions in another std::vector, then sort them in ascending order, then check each move for a collision detection. I know it sounds like I've done a lot of extra traversing and such, but I've trimmed things down so its not as bad as it seems, and Im solely focusing on getting the algorithm working. if anyone can point out any flaws to me, well, you'll be saving me. I'm going to put the relevant code in another post EDIT: EDIT: I've also made a post about it here at gametutorials.com, if you think you see something I've been doing wrong read this post to make sure no one else has already told me about it: http://www.gametutorials.com/forum/topic.asp?TOPIC_ID=6581 [edited by - Shadow12345 on June 18, 2003 12:12:31 PM]

Share this post


Link to post
Share on other sites
Advertisement
Here is the code that actually finds the planes crossed:


Vector3 BSP::Trace(Vector3 *start, Vector3 *end)
{
int i = 0;
int w = 0;
int startleaf = 0;
int endleaf = 0;
float startdist = 0;
float enddist = 0;
bool ancestorfound = false;
int ancestor = -1;
float Fraction;

//finds subtree (ancestor) node as well as start leaf

while(i >= 0)
{
startdist = DotProduct(start, &mpPlanes[mpNodes[i].plane].vNormal) - mpPlanes[mpNodes[i].plane].d;
enddist = DotProduct(end, &mpPlanes[mpNodes[i].plane].vNormal) - mpPlanes[mpNodes[i].plane].d; //wasteful


if((startdist >= 0 && enddist < 0) || (startdist < 0 && enddist >= 0))
{
if(!ancestorfound)
{
ancestor = i;
ancestorfound = true;
}
}
if(startdist >= 0 )
{
i = mpNodes[i].front;
}
if(startdist < 0)
{
i = mpNodes[i].back;
}
}

startleaf = -(i+1);

if(!ancestorfound) //start and end are in the same leaf

{
endleaf = startleaf;
Fraction = CheckLeafForCollision(startleaf, start, end);
if(Fraction < 1)
return *start + ((*end - *start) * Fraction);
else
return *end;
}
else //start and end are not in the same leaf so they must span some planes (****!)

{
int i, x; //counters

float startdist, enddist;
std::vector<float> Segments;
std::vector<int> PossiblePlanes;

w = mpLeafs[startleaf].parent;
PossiblePlanes.push_back(w);

//this should be ridiculously fast

while(w != ancestor)
{
w = mpNodes[w].parent;
PossiblePlanes.push_back(w);
}

//since we never found it before, we must now find the endleaf

i = ancestor;
while(i >= 0)
{
enddist = DotProduct(end, &mpPlanes[mpNodes[i].plane].vNormal) - mpPlanes[mpNodes[i].plane].d;
if(enddist >= 0)
{
i = mpNodes[i].front;
}
if(enddist < 0)
{
i = mpNodes[i].back;
}
}

endleaf = -(i + 1);
w = mpLeafs[endleaf].parent;
PossiblePlanes.push_back(w);


while(w != ancestor)
{
w = mpNodes[w].parent;
PossiblePlanes.push_back(w);
}

//loop through each possible plane

//if we span the plane, create a segment from start to plane

for( i = 0; i < PossiblePlanes.size(); i++)
{
tBSPNode *tempNode = &mpNodes[PossiblePlanes[i]];
tBSPPlane *tempPlane = &mpPlanes[tempNode->plane];
startdist = DotProduct(start, &tempPlane->vNormal) - tempPlane->d;
enddist = DotProduct(end, &tempPlane->vNormal) - tempPlane->d;

//we span this plane

if((startdist >= 0 && enddist < 0) || (startdist < 0 && enddist >= 0))
{

if(startdist < enddist) //startdist is negative

{
float percent = startdist - EPSILON / (startdist - enddist);
if(percent < 0)
percent = 0;
if(percent > 1)
percent = 1.0f;
Segments.push_back(percent);
}
else if(startdist > enddist) //startdist is positive

{
float percent = startdist + EPSILON / (startdist - enddist);
if(percent < 0)
percent = 0;
if(percent > 1)
percent = 1.0f;
Segments.push_back(percent);
}
else //this can only happen if they are exactly equal to each other

{
float percent = 1.0f;
Segments.push_back(percent);
}
}
}

//sort all of the percents in ascending order

int sm; //smallest element


for(i = 0; i < Segments.size(); i++)
{
sm = i;
for(x = i; x < Segments.size(); x++)
{
if(Segments[x] < Segments[i])
{
if(Segments[x] < Segments[sm])
sm = x;
}
}
//Swap element i with element small (w) because element i is the smallest in the list

float temp = Segments[i];
Segments[i] = Segments[sm];
Segments[sm] = temp;
}
for(i = 0; i < Segments.size(); i++)
{
trace << Segments[i] << "\n";
}
trace << "*" << "\n";
}
return *end;
}




thanks again to anyone who gives me any insight

[edited by - Shadow12345 on June 18, 2003 12:08:50 PM]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!