BSP Question

Thread View: comp.graphics.algorithms

2 messages

[T] Back to Threads [V] Tree View [G] Group Articles

2 total messages Started by Tim Wendt Mon, 30 Oct 1995 15:44

#57

Author: Tim Wendt
Date: Mon, 30 Oct 1995 15:44

34 lines
1786 bytes

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.

Given 3 walls

      W0 = (4,9) (3,6)
      W1 = (1,2) (2,4)
      W2 = (1,5) (2,6)

Choose W0 as the partition plane.  If you draw these on graph paper
both W1 and W2 appear to be to the left or behind W0. Yet using the
dot product test this does not seem to be the case.

testA = [4 9]  testB = [3 6]
        [1 2]          [2 4]

testA = 4*2 - 9*1 = -1
testB = 3*4 - 6*2 = 0

testA = [4 9]  testB = [3 6]
        [1 5]          [2 6]

testA = 4*5 - 9*1 = 18
testB = 3*6 - 6*2 = 6

These two walls appear to be on different sides according to the dot product
test.  What am I not understanding here?  Thanks!
--------------------------------------------------------
|       "Hmm...beer!" - Homer Simpson
---tim.wendt@daytonoh.attgis.com---------A1200/030/33---

Re: BSP Question

#56

Author: Acid Software
Date: Mon, 30 Oct 1995 21:57

60 lines
2658 bytes

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

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads