Jump to content
  • Advertisement


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


bsp tree falls at the first hurdle

This topic is 6178 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

int classifyPoint(VECTOR *position, TRIANGLE *plane) { float result; VECTOR *v1 = (VECTOR *)&plane->vertexList[0]; VECTOR direction; direction.x = v1->x - position->x; direction.y = v1->y - position->y; direction.z = v1->z - position->z; result = dotProduct(direction, *(plane->normal)); if (result < -0.001) return CP_FRONT; if (result > 0.001) return CP_BACK; return CP_ONPLANE; } This is my function for testing a point against a plane to find whether it''s in front or behind the plane (i''m writing a bsp engine). Can anyone please tell me why it always tells me that my points are in front of the plane? for example my splitter triangle is in the yz plane, plane->vertexList[0] is (0, -1 -1) plane->normal is (-1, 0, 0) ---pointing ''left'' position is (0.5, -0.5, 0) ---on the ''right''? now surely it should tell me that point is behind the plane? but I get a dotProduct return of -0.75, and when I do the maths on paper I get the same result so I''m guessing my logic is to blame. Can anyone please help? OnDeZ

Share this post

Link to post
Share on other sites


After some minutes of thinking, I guess I figured out what you
are doing, and how you came to that equation.

First, you took the plane equation:
__ _ _ _
x0 * n - x * n = 0, in case the point is within the plane,

and the sign of the value different from 0 tells u on which side the point is.

What you did, and you just SHOULD NOT DO:

you thought, hey, let`s do one dotproduct less, to save performance,
and assumed that
__ _ _ _ __ _ _
x0 * n - x * n = ( x0 - x ) * n

This is *NOT* the same!! It`s not math with somple numbers,
it`s vector math, and this is not allowed!!

Just calculate the dot product of your vertex[0] vector of the triangle and its normal vector,
then subtract the dot product of the normal and the point you want to know on which
it is, just like the equ.:
__ _ _ _
x0 * n - x * n = side

To save a lot of processing time, just calculate the dot product of the triangle''s
normal vector and the vertex[0] vector after loading the triangle into RAM,
and STORE it in the triangle data structure, KEEP IT !!!
And this do for every triangle.
So, when your''re going to test on which side a point is, you have only to do one
dot product, with the normal of the triangle and the vector of the point to test,
and then subtract this from your STORED v[0]*normal value.

Hope I could help you :-)


Share this post

Link to post
Share on other sites
oops, sorry for the strange lines above the equations.
I tried to give the vectors a little arrow, like it`s written in math books,
but it seems there are text formatting errors...

Share this post

Link to post
Share on other sites
Well UnshavenBastard, that can't be the reason since the scalar multiplication is distributive.
By the way, the point IS to the right.

Edited by - VolkerG on November 20, 2001 4:11:03 AM

Edited by - VolkerG on November 20, 2001 4:11:26 AM

Share this post

Link to post
Share on other sites
Guest Anonymous Poster
Let''s see... it''s impossible that you get a -0.75 something in your dotProduct

direction = v1 - position = (0, -1, -1) - (.5, -.5, 0) = (-.5, -.5, -1)

a*b = a.x*b.x + a.y*b.y + a.z*b.z

direction*normal = -1*-.5 + 0*-.5 + 0*-1 = .5

So check what you understand by dot product... perhaps you are doing a cross one instead?

By the way, no need to normalize anything... and use std::numeric_limits::epsilon() for the onplane checks, it''ll give you a platform dependent way of comparing with 0...

However I think that is much straighforward to think of it as (position - v1)... just a personal belief



Share this post

Link to post
Share on other sites
This is what my code looks like, and it works just dandily for me.

int vertex::Classify(polygon& plane)

work.x = location.x - plane.vertices[0].location.x;
work.y = location.y - plane.vertices[0].location.y;
work.z = location.z - plane.vertices[0].location.z;

float result = D3DXVec3Dot(&work, &plane.normal);

if ( result > 0 ) return FRONT;
if ( result < 0 ) return BACK;

// result == 0


The Goblin (madgob@aol.com)
"Before critisizing somebody, walk a mile in their shoes. That way, when you do critisize them, not only will you be a mile away, but you''ll also have their shoes!"

Share this post

Link to post
Share on other sites
Guest Anonymous Poster
Thank you, anonymous poster, how right you are! There''s something screwy going on I''ll just have to go back and look again, and thanks to the guy who posted his code I''ll probably end up just trtanslating it and using it =]

Share this post

Link to post
Share on other sites
Guest Anonymous Poster
However your code is equivalent to the one Globlin posted... the only difference is that he is using (position - v1) instead of (v1 - position) to do the dot product with the plane normal, so he also changes the sign criteria... I think that is more easy to understand in Goblin''s way... but both pieces of code should work...

Just check your dot product thing.. sometimes too much optimizing gives funny errors XDDD


Share this post

Link to post
Share on other sites
A couple of things:

The statement...

v1 * n - v2 * n = (v1 - v2) * n

...is true!!! They are equivalent.

In addition, the following:

cosAngle = v1 dot v2


cosAngle = (v1 dot v2)/(|v1| * |v2|)
// The absolute value of a vector is
// its magnitude. Hence:
// |v1| = sqrt(v1.x2+v1.y2+v1.z2)

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!