#### Archived

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

# bsp tree falls at the first hurdle

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

## 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 on other sites

Hi!

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, lets do one dotproduct less, to save performance,
and assumed that
__ _ _ _ __ _ _
x0 * n - x * n = ( x0 - x ) * n

This is *NOT* the same!! Its not math with somple numbers,
its 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.

Ciao,
Steve

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

##### 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 on other sites
normalize the ray direction before DotProduct.

##### Share on other sites
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

Enjoy

Matt

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

  int vertex::Classify(polygon& plane){ D3DXVECTOR3 work; 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 return COINCIDENT;}

-----------------
-----------------
"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 on other sites
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 on other sites
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

Matt

##### Share on other sites
A couple of things:

The statement...

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

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

normalize(v1);
normalize(v2);
cosAngle = v1 dot v2

IS EQUIVALENT TO

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 on other sites
shouldn''t it be:

result = dotProduct(direction, *(plane->normal)) - plane->distance;

and the 0.001 in if(result ) be 0.0

and you pass the actual postion as the first param to dotproduct, not the direction...

well, that''s what works for me, anyways...

##### Share on other sites
First of all thanks to everyone who answered my dumb post.

Turns out Mr Anonymous Poster was right - despite checking again and again I didn''t realise that I''d mixed up the + and * in my dot product function!
That''s nothing compared to the fun I had my my ray-plane intersect function but *touch wood* it''s all working now and my splitPoly function actually splits a triangle into 3 (after some major fudging - wonder what happens when I chuck a 20k game level at it =] )

##### Share on other sites

VolkerG:

Ooops, yes, you''re right, I was wrong.

DotProdutct IS distributive, even crossproduct is,
if you keep the order of the variables.

I remembered wrong. I thought I heard the voice of my
ex- math teacher shouting: "don''t do that!", and connected
it to the vector dot-prod.

10 Minutes after posting, and reading some emails, I`ve
tried it out on paper, and realized I erred.
But 1st, I had to go(no internet at home, at the moment),
and 2nd, I''was sure that there were
enough people on the net, who soon will correct my mistake
... ;-)
(and so it was)

And maybe it wasn''t the plane equation, what the questioner
thought about. The new vector produced from the subtraction
is 90 degrees against the normal, if point is within the
plane, and the dotproduct, of course, changes its sign, depending on smaller/greater angle than 90 degs,
BUT I just didn''t see that, when I looked at the code,
and gave a quick response.

(
Well, as my friends know, somtimes I answer while running the last two thinking steps... maybe I should finish thinking first... ;-) It''s a bad habit..
)