 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Have you tried this condition?
>
> ((distSq < (radius1Sq+radius2Sq))
> or (4*radius1Sq*radius2Sq > (distSq - (radius1Sq+radius2Sq))^2))
Smart. I feel stupid now! =) I see the equivalence, but I'm curious how long
you took to come up with that. Was it obvious?
- Slime
[ http://www.slimeland.com/ ]
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> How about more simply:
>
> distSq < 4 * max( radius1Sq, radius2Sq )
>
> Followed by the expensive square root operation to check if they really
> intersect?
Well, I'd have to weigh the cost of doing the square root against the cost
of just going forward and doing the more expensive test. Although I posed
this as a stand-alone question, the actual work I am doing is checking if a
line segment intersects a triangle.
There's probably a bunch of ways to make my code faster, but I became
curious about this particular problem.
- Slime
[ http://www.slimeland.com/ ]
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?
- Slime
[ http://www.slimeland.com/ ]
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> 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
|
|
| |
| |
|
|
|
|
| |
