>> Wouldn't it be faster to just directly check the line against the 
>> triangle?
> 
> Honestly, I don't know. I'm not sure my code for the triangle-line check is 
> very good. =)
> 
> As far as I can tell, to check for an intersection between a triangle and a 
> line segment, you need to check that one of the triangle's vertices is on an 
> opposite side of the line from the other two, and then check that both of 
> the line segment's endpoints are on opposite sides of at least one of the 
> triangle's edges, or that both of them are inside the triangle.
> 
> I did most of these checks with cross products, and then found I had some 
> precision problems in some cases, and the code got more complicated when I 
> tried to avoid them. Since intersections are rare, I figured a bounding 
> check would be the easiest way to improve performance.

Er... yeah, that's not terribly good. ;-)

Do a quick google for "ray triangle intersection". There are several 
methods for doing this kind of thing, some of them highly optimised.

Post a reply to this message

> Er... yeah, that's not terribly good. ;-)
>
> Do a quick google for "ray triangle intersection". There are several 
> methods for doing this kind of thing, some of them highly optimised.

That tends to give results for a 3D problem, whereas my problem is 2D.

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

Slime wrote:
>> Er... yeah, that's not terribly good. ;-)
>>
>> Do a quick google for "ray triangle intersection". There are several 
>> methods for doing this kind of thing, some of them highly optimised.
> 
> That tends to give results for a 3D problem, whereas my problem is 2D.

Many of the methods work for 2D as well though.

But now I'm curious... the cross product is only defined for 3D vectors, 
but you said you used a lot of cross products?

Post a reply to this message

> But now I'm curious... the cross product is only defined for 3D vectors, 
> but you said you used a lot of cross products?

Treat your 2D working area as a plane in 3D space (with Z coordinate zero if 
you like), then you can do cross products, and checking whether the result 
points "in to" the plane or "out of" the plane can be pretty useful (eg to 
find out which side of a line a point is on).

Post a reply to this message

scott wrote:
>> But now I'm curious... the cross product is only defined for 3D 
>> vectors, but you said you used a lot of cross products?
> 
> Treat your 2D working area as a plane in 3D space (with Z coordinate 
> zero if you like), then you can do cross products, and checking whether 
> the result points "in to" the plane or "out of" the plane can be pretty 
> useful (eg to find out which side of a line a point is on).

Oh, right.

...or you could just take the dot product instead, which requires only 2 
multiplies and one addition as opposed to four multiplies and two 
subtractions...

Post a reply to this message

> ...or you could just take the dot product instead, which requires only 2 
> multiplies and one addition as opposed to four multiplies and two 
> subtractions...

How is that useful?

Post a reply to this message

scott wrote:
>> ...or you could just take the dot product instead, which requires only 
>> 2 multiplies and one addition as opposed to four multiplies and two 
>> subtractions...
> 
> How is that useful?

Because you can use it to determine which side of the line a point is on?

Post a reply to this message

> Because you can use it to determine which side of the line a point is on?

How?

Example: Line through (0,0) and (0,1), and points either side of the line at 
(1,0) and (-1,0)

Post a reply to this message

scott wrote:
>> Because you can use it to determine which side of the line a point is on?
> 
> How?
> 
> Example: Line through (0,0) and (0,1), and points either side of the 
> line at (1,0) and (-1,0)

Suppose you have a line from point A to point B. Compute the vector AB, 

the dot product V . A and call it k.

Which side of the line is point X on? Well, take the dot product V . X, 
and subtract k. The result is negative on one side, positive on the 
other, and zero if X is on the line itself (or at least, parallel to it).

...so basically, it's a ray/plane intersection test, except the "plane" 
is a 2D slide - a line.

A = (0,0)
B = (0,1)
AB = (0,1) - (0,0) = (0,1) [already unital]
V = (0,1) * {(0,-1), (1,0)} = (-1,0)
k = (0,0) . (-1,0) = 0

X = (1,0)
X . V - k = (1,0) . (-1,0) - 0 = -1

Y = (-1,0)
Y . V - k = (-1,0) . (-1,0) - 0 = +1

QED.

Post a reply to this message

> Suppose you have a line from point A to point B. Compute the vector AB, 

> dot product V . A and call it k.
>
> Which side of the line is point X on? Well, take the dot product V . X, 
> and subtract k. The result is negative on one side, positive on the other, 
> and zero if X is on the line itself (or at least, parallel to it).
>
> ...so basically, it's a ray/plane intersection test, except the "plane" is 
> a 2D slide - a line.

Sorry, but that seems much more complicated and using up more instructions 
compared to the cross product:

> A = (0,0)
> B = (0,1)
> AB = (0,1) - (0,0) = (0,1) [already unital]

No need to make AB unital for the cross product method (saves a square root 
and divide).

> V = (0,1) * {(0,-1), (1,0)} = (-1,0)
> k = (0,0) . (-1,0) = 0

No need to calculate V or k for the cross product method (saves some 
multiplies and adds).

> X = (1,0)
> X . V - k = (1,0) . (-1,0) - 0 = -1

X cross AB = (1,0) x (0,1) = (1)(1) - (0)(0) = 1
(saves one subtraction compared to your method)

> Y = (-1,0)
> Y . V - k = (-1,0) . (-1,0) - 0 = +1

Y cross AB = (-1,0) x (0,1) = (-1)(1) - (0)(0) = -1
(saves one subtraction compared to your method)

Post a reply to this message