optimizing square root out of trigonometry

  • 2 Replies
  • 366 Views
*

MagnusWootton

  • Starship Trooper
  • *******
  • 294
optimizing square root out of trigonometry
« on: June 27, 2021, 01:54:48 pm »
The worst part of making a physics engine  (Like a 3d game.)  Is the simple operation of getting the hypotenuse of a right angled triangle.
It requires an operation which is LOG*LOG*LOG cost!!  LOG CUBED!  To do Newton iteration square roots!!!  (If you are making your ALU from scratch.)
The first log, is to get the precision of the adder,  the second log is to get the precision of the multiplier, and the third log is to run for iteration over the significance,  u only get 1 bit at a time!

Thats looking at it from a very raw standpoint,  so theres going to be ways to get around doing the full cube,  But I have a way of getting it with only so many multiplies - alot of them constant,  and only 2 variable multiplies!


The main reason to get the hypotenuse, is to give you rotations, in my mind,  you cant really make a 3d game without rotation,  its very difficult to make anything out of it, without being able to check the birds pathway distance (Diagonal) to things.

Code: "c++"
void hypatn2(int posx, int posy, int& hypot, int& angle)
{
 if(posx!=0 || posy!=0)
 {
  int ang2=0;
  bool swip=true;
  if(posx>0){if(posy>0){ang2=0;}else{ang2=270;}}else{if(posy<0){ang2=180;}else{ang2=90;}} //this might take a few cells up to get the quadrants...
  int px=fabs(posx);int py=fabs(posy); //get rid of the polarities difference.
  if(py<px){int swap=px;px=py;py=swap;swip=false;} //get rid of the 45 degree difference.
  if(ang2==270 || ang2==90) swip=!swip;
  int ang22=45;
  if(!swip){ang22=-45;}
  ang2+=ang22;
  //if im in the wrong 2d-octant swap it over.
  int edge1=-(px-py);  //get the distance between it and the mirror coordinate
  int edge2=px;        //get the distance toward the vertical
  //2 mul/divs.  (this way of interpolating is better. its got a beginning and a derivative,  slightly better.)
  int range;
  range=(edge1+edge2);
  int outp1=edge2+edge1/2.2;         //the vertical length     (nudged this one from 2.0(theoretically correct) -> 2.2(slightly fixed a bit))
  int outp2=edge2+edge1/sqrt2;       //the diagonal length     (kept this one sqrt2, its the 45 degree one.)
  hypot=(outp1+(outp2-outp1)*edge1/range)*sqrt2-(0.215*256); //(second nudge.-0.215 on all of them. so its missing something, some integer alignment mixup.)
  if(swip){angle=ang2+(0-45)*(px*sqrt2)/hypot;}
      else{angle=ang2+(45-0)*(px*sqrt2)/hypot;}
 }
 else
 {
  hypot=0;
  angle=0;
 }
}

If you get the hypotenuse,  you can compute PI,  sin and cos seems to be the reverse logic of getting the hypotenuse, and u can rotate,  and u can have quaternions. (They are rotational velocity accumulators.)  And maybe they could be good for computing a wierd roll from a non spherical object, if u keep accumulating the centre of mass rotation as it goes.

*

ivan.moony

  • Trusty Member
  • ************
  • Bishop
  • *
  • 1590
    • contrast-zone
Re: optimizing square root out of trigonometry
« Reply #1 on: June 27, 2021, 02:51:49 pm »
I used to have a pre-cached 2d array of diagonals, calculated only once at startup. Later, i could fastly get `distance[abs(x2-x1), abs(y2-y1)]` at the cost of addition and substraction

Code
// precache
var dist = [[]], width = 200, height = 200;
for(x = 0; x < width; x++) {
    for(y = 0; y < height; y++) {
        dist[x, y] = Math.sqrt(x * x + y * y);
    }
}

//later reach
var x1 = 10, y1 = 25, x2 = 150, y2 = 175;
var diagonal = dist[Math.abs(x2 - x1), Math.abs(y2 - y1)];

The best thing is that this works with any kind of formulas, being composed of log, exp, sin, tan, or whatever else. In a case of floats, we only have to quantify and round them, and then we can get distances, angles, curvatures, or whatever else we want. Basically, it's a cache of `f(x, y, z, ...)`, and amount of memory used for cache is `mn` numbers where `m` is a size of a dimension and `n` is a total number of dimensions.
There exist some rules interwoven within this world. As much as it is a blessing, so much it is a curse.

*

MagnusWootton

  • Starship Trooper
  • *******
  • 294
Re: optimizing square root out of trigonometry
« Reply #2 on: June 27, 2021, 03:22:47 pm »
I used to have a pre-cached 2d array of diagonals, calculated only once at startup. Later, i could fastly get `distance[abs(x2-x1), abs(y2-y1)]` at the cost of addition and substraction

Code
// precache
var dist = [[]], width = 200, height = 200;
for(x = 0; x < width; x++) {
    for(y = 0; y < height; y++) {
        dist[x, y] = Math.sqrt(x * x + y * y);
    }
}

//later reach
var x1 = 10, y1 = 25, x2 = 150, y2 = 175;
var diagonal = dist[Math.abs(x2 - x1), Math.abs(y2 - y1)];

The best thing is that this works with any kind of formulas, being composed of log, exp, sin, tan, or whatever else. In a case of floats, we only have to quantify and round them, and then we can get distances, angles, curvatures, or whatever else we want. Basically, it's a cache of `f(x, y, z, ...)`, and amount of memory used for cache is `mn` numbers where `m` is a size of a dimension and `n` is a total number of dimensions.

That would be good for FPGA design, because they are really good at lookup tables, being a digital/binary thing.

If you do one divide,  you could have a ratio input, to get a normalized result on a 1d table,  and it would be a smaller table.  (Smaller tables eventually fit into the computer cache if they are smaller enough.)  But I guess,  maybe the sum of shifts required to access it might kill the idea if it was on an FPGA.