>>   Suppose that the most significant non-zero digit of x is in the 2^n 
>> place. Let y = x / 2^(n/2). Now Sqrt(x) is approximately x / y.
> 
> Is there a way to quickly get n for a given number?

If you don't mind depending on a specific floating-point 
representation... sure. Just find out which bits of the number contain 
the exponent. (For example, for a double-precision IEEE float, the 
bitmask is 0x7FFF000000000000, and you then shift out those zeros and 
subtract 0x3FFF to get the real value.)

That's what makes this so efficient. You just need the exponent field 
from the float value, so no need to calculate anything. (Indeed, as an 
even rougher approximation, just halve the exponent...)

Post a reply to this message

scott wrote:

> So let me understand this, you are constructing two circles, one around 
> the line and one around the triangle, then seeing the circles intersect, 
> and if they do proceeding to check if the line actually intersects the 
> triangle?
> 
> Wouldn't it be faster to just directly check the line against the triangle?

It would.

Now, if the circle encloses a few *thousand* triangles, it's probably 
way, way faster to check the circle first...

Post a reply to this message

> So let me understand this, you are constructing two circles, one around 
> the line and one around the triangle, then seeing the circles intersect, 
> and if they do proceeding to check if the line actually intersects the 
> triangle?

Well, the one around the triangle is precomputed. Otherwise, yes.

> 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.

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

Post a reply to this message

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