Skip to main content
gamedev.net
🔒 Locked 🤖 Godot

Circle intersection area optimisation.

Started by luca-deltodesco Sep 14, 2010 at 6:29 PM 6 replies 1.7k views
Original Post
luca-deltodesco
luca-deltodesco
Here is my code atm:

typedef Circle = {	pos : Vector2;	rad : Float;}function intersection(a:Circle, b:Circle) {	var delta = b.pos - a.pos;	var dl = dot(delta,delta);	var dr = b.rad + a.rad;        	//not intersecting	if(dl > dr*dr) return 0;        	var dls = sqrt(dl);	var ar2 = a.rad*a.rad;	var br2 = b.rad*b.rad;	var x = (dl - br2 + ar2) / (2*dls);	//circle a totally contained in circle b	if(x < -a.rad) return pi*ar2;        	//circle b totally contained in circle a	var x2 = dls - x;	if(x2 < -b.rad) return pi*br2;	var ta = acos(x / a.rad);	var tb = acos(x2 / b.rad);	return ta*ar2 - x*sqrt(ar2 - x*x)	     + tb*br2 - x2*sqrt(br2 - x2*x2);}


the computed value 'x' is such that a.pos + x*unit(delta) would be the point between the circles at which the bisector would intersect the two intersection points of the circles.

the last two lines in the final return computer the area of the two circular segments either side of the bisector which at least thankfully, works even when the bisector does not lie between the two centres.

It is not so much the square roots which bother me, as i have a fast sqrt in place which can be used. What bothers me most is the inverse cosines, which i guess could be optimised with a table lookup as accuracy is not essential here, but it would interest me if there were a way to write this function to be simpler.
luca-deltodesco
luca-deltodesco
The last two square roots could possibly be approximated very simply:

x*sqrt(a^2 - x^2) ~= ax. and as |x| is bounded above by |a|, this might not be too bad, though graphing the two graphs shows that the approximation as ax becomes very bad once x reaches about 1/2's of a.

This also seems to work very badly, even taking an extra term of the expansion which probably makes it slower than the fast square root anways as x or x2 is always close to one of the bounds.
luca-deltodesco
luca-deltodesco
using a look up table also doesn't work so well, with very bad results from using look up table when having arguments to the inverse cosine very close to -1 and 1. (of the order of hundreds times the units of area out in final calculations)
Dave Eberly
Dave Eberly
Here are a couple of inverse-cosine approximations from my library.
template <typename Real>Real Math<Real>::FastInvCos0 (Real value){    Real root = Math<Real>::Sqrt(FAbs((Real)1 - value));    Real result = -(Real)0.0187293;    result *= value;    result += (Real)0.0742610;    result *= value;    result -= (Real)0.2121144;    result *= value;    result += (Real)1.5707288;    result *= root;    return result;}

and
template <typename Real>Real Math<Real>::FastInvCos1 (Real value){    Real root = Math<Real>::Sqrt(FAbs((Real)1 - value));    Real result = -(Real)0.0012624911;    result *= value;    result += (Real)0.0066700901;    result *= value;    result -= (Real)0.0170881256;    result *= value;    result += (Real)0.0308918810;    result *= value;    result -= (Real)0.0501743046;    result *= value;    result += (Real)0.0889789874;    result *= value;    result -= (Real)0.2145988016;    result *= value;    result += (Real)1.5707963050;    result *= root;    return result;}
maya18222
maya18222
Sorry to barge in, but are you using a series for that Dave? as discussed here.

http://www.intmath.com/Series-expansion/3_How-calculator-works.php
Dave Eberly
Dave Eberly
Quote:
Original post by maya18222
Sorry to barge in, but are you using a series for that Dave? as discussed here.

http://www.intmath.com/Series-expansion/3_How-calculator-works.php


No. The fast approximations in my Math class are based on minimax (Chebyshev norm).

The information at the link you provided should be ignored, because the writer has no clue about accurate estimation of functions using computers. The CORDIC algorithm was used many years ago for hand calculators, but CORDIC is *not* based on power series, nor is any other good algorithm for accurate estimation over a wide range of inputs.

Power series give you polynomial approximations *locally* at the point of expansion. As you evaluate the polynomial at points not near the point of expansion, the errors can get very large. What good algorithms use are *global approximations*, to minimize some norm over an entire domain. This what minimax does. For a minimax polynomial approximation, you try to choose the coefficients to minimize the maximum absolute differences between estimated and true value.

The calculus curriculum at universities really needs to be modernized. Although power series are of interest pedagogically, for computing on current-day machines, they are typically of no use (other than for estimates very close to the point of expansion). The curriculum needs to include discussion about accurate estimations for an entire domain.
hick18
hick18
Hmm. So are you saying that to get good accuracy from this method, you would need multiple series for a range of expansion points, say one for every 10 degress ort something, and maybe pick the closest one? or maybe even interpolate between them?
Dave Eberly
Dave Eberly
Quote:
Original post by hick18
Hmm. So are you saying that to get good accuracy from this method, you would need multiple series for a range of expansion points, say one for every 10 degress ort something, and maybe pick the closest one? or maybe even interpolate between them?


I did not say this. And, no, choosing multiple series expansions or using linear interpolation is not what you want for accurate function estimation. If you look at my Math class, you will also see polynomial approximations for sine and cosine. These polynomials are *not* obtained from a power series expansion. The coefficients are constructed using a minimax approach.

Key terms for Google: "minimax Chebyshev norm". The topic is not simple mathematics as that for power series. People seem to suggest power series because they are easy to understand. But they are the wrong tool for accurate function estimation when you want to know a global error bound. (A truncated power series gives you only local error bounds.)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.