 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> float xDiff = x1 - x2;
> if (xDiff > rSum) return false;
>
> float yDiff = y1 - y2;
> if (yDiff > rSum) return false;
>
> if (xDiff + yDiff) < rSum return true;
>
> return (xDiff * xDiff + yDiff * yDiff < rSum * rsum)
I would want to make sure the additional branches don't make this slower.
You also have to take the absolute value of xDiff and yDiff for the first
two checks, which may add slowness. However, it may be worth it if you know
it's extremely uncommon for the circles to overlap in the X or Y direction
(which I suppose is a reasonable assumption).
- Slime
[ http://www.slimeland.com/ ]
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> If you're willing to tolerate an intersection function which has the
> possibility of error, it seems like just using bounding squares instead of
> bounding circles would give better error bounds if you expect your circles
> to often be of very different sizes.
I generally prefer bounding circle/sphere checks to bounding box checks
because box intersection tests (at least naive ones) require multiple
branches. Also, in my particular application I'm dealing with a lot of line
segments, for which I have to create the bounding boxes, which I think
requires at least two more branches (to check if x1 < x2 and if y1 < y2). Of
course I'd have to try it to be sure.
- Slime
[ http://www.slimeland.com/ ]
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Thanks for doing all that work! =) Definitely looks like Bart's method is
the best. I would be scared of using an approximation in case it failed to
determine an important intersection. What is your implementation of
fastSqrt?
- Slime
[ http://www.slimeland.com/ ]
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Approximations_that_depend_on_IEEE_representation
Craziness. I remember finding that invSqrt function a few years ago and
looking it up. I'm always a little worried about portability of this sort of
thing, though.
- Slime
[ http://www.slimeland.com/ ]
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Nicolas Alvarez wrote:
> The compiler may be optimizing knowing you're runing it on the same input
> values each time. For example, only calling sqrt() 3 times and not
> 300000000.
Ahh, good point. After fixing this it looks like isect4 is faster than
isect3, but by a pretty slim margin, so bart's method would definitely
be the way to go.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Slime wrote:
> Thanks for doing all that work! =) Definitely looks like Bart's method is
> the best. I would be scared of using an approximation in case it failed to
> determine an important intersection. What is your implementation of
> fastSqrt?
I just used the one given on Wikipedia.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Although I posed this as a stand-alone question, the actual work I am
> doing is checking if a line segment intersects a triangle.
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?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> 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
|
|
| |
| |
|
|
|
|
| |
