🚀 go-pugleaf

Tim Wendt (tim.wendt@daytonoh.ncr.com) wrote:
: I'm having trouble with my 2D BSP tree creation.  When my function to
: determine if a wall lies to the right or left of the partition wall returned
: unexpected results I began to question my understanding of the dot product
: test.  It is my understanding that observing the signs using simple dot
: products on the endpoints will indicate to which side of the partition the
: test wall lies.  Here is the problem.
: 
: These two walls appear to be on different sides according to the dot product
: test.  What am I not understanding here?  Thanks!


I'm just getting into BSP stuff myself and am using the plane's normal 
to test which side of a plane points are on. For a 2d line, the normal is:

nx=-vy
ny=vx

Where vx and vy represent the planes vector, eg:vx=x2-x1 (by plane, I 
mean a line in 2d).

You might want to normalize this normal:

vl=sqrt(vx*vx+vy*vy)
nx=-vy/vl
ny=vx/vl

This makes the length of the normal =1.

To check which side of the plane a point is on use:

d=(px-x1) * nx + (py-y1) * ny	;Dot product of vector & normal

Where x1,y1 is one (doesn't matter which) end of the plane and px,py is the 
point you're testing. nx,ny is the planes normal.

If you've normalized the normal, then d = the distance of the point from 
the plane - if it's negative, the point is behind the plane. If you 
haven't normalized the normal, then the sign of d still shows you which 
side the point's on.

The nice thing about finding the correct distance though is that it helps 
when splitting polygons. So if you've got d1=a point behind the plane and 
d2=a point in front, you can find the time of intercept with:

t=-d1/(d2-d1)	;d1,d2=distances of points from plane. t=0...1

Then just use t to work out x and y at the intercept point:

ix=(x2-x1) * t + x1
iy=(y2-y1) * t + y1

I think the problem you were having was that Dot products use vectors - 
ie: differences between points where-as you were just using the points 
absolute positions. Maybe. I didn't look too closely!

Good Luck!

Mark Sibly,
Black Magic