optimizing square root out of trigonometry

  • 2 Replies
  • 1261 Views
*

MagnusWootton

  • Replicant
  • ********
  • 634
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
  • *
  • 1723
    • mind-child
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.

*

MagnusWootton

  • Replicant
  • ********
  • 634
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.

 


OpenAI Speech-to-Speech Reasoning Demo
by ivan.moony (AI News )
March 28, 2024, 01:31:53 pm
Say good-bye to GPUs...
by MikeB (AI News )
March 23, 2024, 09:23:52 am
Google Bard report
by ivan.moony (AI News )
February 14, 2024, 04:42:23 pm
Elon Musk's xAI Grok Chatbot
by MikeB (AI News )
December 11, 2023, 06:26:33 am
Nvidia Hype
by 8pla.net (AI News )
December 06, 2023, 10:04:52 pm
How will the OpenAI CEO being Fired affect ChatGPT?
by 8pla.net (AI News )
December 06, 2023, 09:54:25 pm
Independent AI sovereignties
by WriterOfMinds (AI News )
November 08, 2023, 04:51:21 am
LLaMA2 Meta's chatbot released
by 8pla.net (AI News )
October 18, 2023, 11:41:21 pm

Users Online

320 Guests, 0 Users

Most Online Today: 396. Most Online Ever: 2369 (November 21, 2020, 04:08:13 pm)

Articles