🚀 go-pugleaf

Tim Wendt (tim.wendt@daytonoh.ncr.com) wrote:
> What is the test to determine if a vector is is front or behind the partition
> vector (2D only ala Doom) when building a BSP tree?  

> Tim
> --------------------------------------------------------
> |       "Hmm...beer!" - Homer Simpson
> ---tim.wendt@daytonoh.attgis.com---------A1200/030/33---

The cross product.  Cross(V,W) is positive if vector V is "to the
right" of vector W. Negative otherwise.  In 2D, the cross prod is the
the determinant of the matrix made up by the two vectors:

Cross(V,W) = |V1 V2| = V1 * W2 - V2 * W1
             |W1 W2|

Hope this helps.

Jim
mazrimas@shell.portal.com

Tim Wendt <tim.wendt@daytonoh.ncr.com> wrote:
>What is the test to determine if a vector is is front or behind the partition
>vector (2D only ala Doom) when building a BSP tree?  
>
>I'm still confused.  The dot product was described as ||u|| ||v|| cos (angle
>between the vectors).  How do I find the angle between the two vectors?  Is
>this the easiest approach?  Thanks much!
>

you can use this to get rid of the angle and the cos:
 u.v = ||u||*||v||*cos(angle)
     = x1x2 + y1y2 + z1z2

where x,y,z are the respective coordinates of u and v.

------------------
Nicolas Pomarede

No it's not the easiest.  The a simpler (and not that inefficient) would 
be to test the slopes of the 2 lines in question and if m1 <= m2 then the 
segment is on the right...the only catch is if the slope is negative; is 
it the numerator positive and the denominator negative or vic versa?  To 
elimate this (and to eliminate a nasty divide) do if (dx1*dy2) <= 
(dy2*dx2) then the line is on the right of the partion line. EX:

int     OnRight( short Index){
 long   x1 = Nodes[Index].x;
 long   y1 = Nodes[Index].y;
 long   x2 = x1 + Nodes[Index].dx;
 long   y2 = y1 + Nodes[Index].dy;
        if ( ((x1-x2)*(py-y2)) <= ((y1-y2)*(px-x2)) )
           return 1;
        else return 0;
}

more intuative that dot or cross product in my opinion but almost 
certainly not the best.  I remember glancing at a recent issue of DD 
sourcebook and Abrash mentioning a *very* simple test but I may be 
mistaken. 

-- 
Those who danced were thought to be quite insane by those who could not 
hear the music.

Yes, Abrash gives source code and text that explains the operation in 2d. The
BSP FAQ contains a pointer to the code online, and the article is a two part
(maybe more?) over the last two ddj sourcebooks.
-- 
Bretton Wade (bwade@graphics.cornell.edu)
http://www.graphics.cornell.edu/~bwade/

BTW, I'm defending my thesis next week, and I'll be expanding the FAQ soon
thereafter. I'd like to thank all the people who have made suggestions and have
offered to help out. I should say that the FAQ will be moving soon, as a result
of my graduation.

Look for better answers and graphics, a windows help file version of the FAQ, a
windows version of the demo application, some history, and an expanded
bibliography in the months to come.
-- 
Bretton Wade (bwade@graphics.cornell.edu)
http://www.graphics.cornell.edu/~bwade/

Tim Wendt (tim.wendt@daytonoh.ncr.com) wrote:
: What is the test to determine if a vector is is front or behind the partition
: vector (2D only ala Doom) when building a BSP tree?  

: I've read a few FAQs and articles but the only test I've seen in detail is the
: test for 3D polygons (which is the dot product between the normal of the plane
: a the polygon edge.)  One of the texts did say it was a simple dot product
: between the two 2D vectors.  I pulled out the old linear algebra textbook but
: I'm still confused.  The dot product was described as ||u|| ||v|| cos (angle
: between the vectors).  How do I find the angle between the two vectors?  Is
: this the easiest approach?  Thanks much!

: Tim

Well, the point usually is to calculate the cosine of the angle between the
vectors and not the other way round.
By definition: a = (a1, a2, a3) ; b = (b1, b2, b3)
Then a dot b = (a1*b1 + a2*b2 + a3*b3) = |a|*|b|*cos(angle)
You can get a and b using 3 3d points, ie
a = x3-x2; b = x1-x2; (where xn's are 3d-vectors)

That's about it.

--
ttfn
Frans van den Bergh (s9506131@cosine.cs.up.ac.za)
-------------------------------------------------------------------
The only instruction still missing from the Pentium is db 66h, 90h  !