#### Archived

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.

## 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)

1. 1
Rutin
33
2. 2
3. 3
4. 4
5. 5

• 13
• 77
• 11
• 10
• 14
• ### Forum Statistics

• Total Topics
632968
• Total Posts
3009586
• ### Who's Online (See full list)

There are no registered users currently online

×