2
\$\begingroup\$

This is perhaps a better question for mathematics SE, however, this deals more with the performance side of gaming, and software in general. When I say recursive function, I mean recurrence relation.

I figure, in theory, a recursive function for sine, cosine, and tangent, would provide a function that takes less time to execute, rather than calculating the individual sine, cosine, and tangent every single time, considering that most functions in a game are continuous that require sine and cosine or tangent, e.g. the camera in a 2D or 3D scene. Whenever the mouse is moved, we could use a previous metric of sine, cosine, or tangent to calculate the next value.

Do such recursive functions exist? I have done a quick Google search, but I couldn't really find anything, and I would not know how to formulate a recursive function with my current knowledge of mathematics. (There must be a recursive formula for every function of x that is, at least, continuous.)

Were there older approaches taken in older or even recent video games to achieve good-enough results, like quaternion rotation, to achieve a real-time result?

Some examples where this might potentially be an optimization:

  • Any terrain generation algorithm. For example, Minecraft currently generates xyz 16-256-16 chunks. Instead of generating 16x16 or 16x256x16 chunks, you could generate individual blocks at a time as time passes or per tick. This would reduce the time per tick spent on generating terrain, and is relatively cheap as you could make it camera direction-dependent, e.g. generate blocks in the direction of the camera, and visible blocks can be generated first allowing lazy terrain generation. This would work with chunks of any size. The same could apply to vector terrain generation. However, relating to recurrence relation, said function would require (for Minecraft) one of 6 cardinal directions to calculate what the next block should be.
  • Camera matrices. Despite the fact that you can move your mouse around to make the camera jump on-screen, the Camera function is effectively contiguous per frame. When there is entropy, the transitions are very smooth with about the same interval for each camera rotation, and even then, all movement is a paraboloid shape. This could allow for some optimization like iterative approximation as mentioned in the comments.
  • Any algorithm that is inherently contiguous in software; interpolations; etc.
\$\endgroup\$
  • 4
    \$\begingroup\$ It sounds like you're talking about iterative approximation: taking an output for a previous calculation with an input similar to the one we're providing, and using it to get into the right ballpark so we only need to make small refinements from there. This isn't the sense in which "recursive" is typically used in game programming. In general, you should be very cautious about reasoning from pure math to real-world performance. Real computer chips have built-in instructions for computing trig ratios, and tend to hit bottlenecks in caching, not arithmetic, differing from the theoretical model. \$\endgroup\$ – DMGregory May 17 '18 at 13:28
  • \$\begingroup\$ So, can we make this more concrete? Have you found a particular real application of trig in your current game project that's not exhibiting the performance you'd hope for? With a real example, we'll be in much better position to offer real performance improvements, and avoid falling into the trap of giving you a clever-looking formula that's actually slower when running on actual hardware in your real application. \$\endgroup\$ – DMGregory May 17 '18 at 13:31
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ – AMDG May 17 '18 at 14:07
  • \$\begingroup\$ No, don't tell me in the comments: edit your question. It's best if questions are self-contained, and can be understood by reading them in isolation, without following a back-and-forth chat thread. \$\endgroup\$ – DMGregory May 17 '18 at 14:07
2
\$\begingroup\$

Even if you could make something that's better on paper, than the already available sine and cosine functions, you'd have to essentially go down to the metal to make it useful.

Some systems use the fsin assembly instruction, some create their own approximation. What you need to understand is that these have been in use for almost half a century and were optimized to a point where they're incredibly fast. They don't use traditional algorithms, they use bit trickery.

Using a lookup table today doesn't cut it. It may have been fine in the era of the DS, where small differences in the camera rotation didn't matter, since you had relatively few pixels to work with, but in today's world, where people obsess over low mouse sensitivity values to make sure they have as little pixel skipping as possible, making the camera or something else imprecise isn't worth it. Also, lookup tables will probably be slower.

If you still want to try it, then here are some suggestions:

The taylor series is a good way to approximate the sine of a number. It's an infinite series and can be cut anywhere depending on the precision you need. It's not very fast, but it's a good start.

The other algorithm is called CORDIC. This is what's in your calculator probably. It was designed to be easily implementable in hardware and can give you a pretty decent result very fast. It relies on complec number arithmetics. However, there's a reason it was made for hardware and not software. Adding a layer of abstraction to it can make it suffer pretty badly. And that's only if you're working with a compiled language. Python has 2 layers of abstraction, Java 3, and let's not even talk about JavaScript.

\$\endgroup\$
  • \$\begingroup\$ In favor of Java, it does get compiled to have only 2* layers (AOT compiler WIP). Also JavaScript has OpenGL access (I believe still experimental). Python is a terrible language made for scripting, not performance or games. JavaScript is quite fast, especially on V8. *If it weren't for the JVM executing JIT code, the JIT code would make it 1 layer by itself. \$\endgroup\$ – AMDG Jun 2 '18 at 2:35
  • \$\begingroup\$ Minecraft uses a lookup table which is slow in itself, and has many optimizations it does not take advantage of. I understand that there are already optimizations, but supposing there is a way to linearize an exponential time function or use the previous value to calculate the next, that's an improvement to me. Imagine fibonacci execution if we used an arbitrary function instead of recurrence relation to calculate the next number in the fibonacci sequence? \$\endgroup\$ – AMDG Jun 2 '18 at 2:38
  • \$\begingroup\$ @LinkTheProgrammer Abstraction here means the program has to go through certain stages to run. Java has to first converted to a different format, then has to be run by a different program. I told you about cordic and the taylor series, both of which utilize some kind of recursion. Also, looking at minecraft for optimization ideas isn't a great idea. \$\endgroup\$ – Bálint Jun 2 '18 at 2:43
  • \$\begingroup\$ voxel rendering via implicit rendering and perhaps using triple integrals as constructive geometry (to render volume rather than surfaces, when necessary) are an area of optimization that I will be looking into as I have plans to make an implicit renderer using voxel points that can be just as viable an option as vertices and triangles and getting photo realism in real-time with late cues at or below 16 and 2/3 milliseconds. \$\endgroup\$ – AMDG Jun 2 '18 at 2:50
1
\$\begingroup\$

The closest things I'm aware of that might relate to your definition of 'recursive' are:

  • Lazy evaluation aka call-by-need - an evaluation strategy which delays the evaluation of an expression until its value is needed and which also avoids repeated evaluations through sharing. This is tied to your choice of programming language & is often used used by functional programming launagues.
  • Recurrence relation - an equation that recursively defines a sequence of values (function) as a function of the preceding terms.
  • Differencing - a specific form of recurrence relationships. Starting with a mathematical expression of the form f(x + b) − f(x + a), one can divide by b - a to get a difference quotient. In some situations, you can recycle much of the work used to find the previous value by noting the change in value & calculating that instead of the entire value. For instance, linear interpolation can be rewritten as forward differencing so that at each step, you only need to calculate the change that occured from the previous step.

With respect to performance, the problem is that not all functions can be differenced in a way that reduces computation. Differencing is best to linear functions. But typically, it's non-linear functions that are expensive. While you could redefine a transcendental function to be 'recursive', unless you're dealing with an approximation, the resulting variant function will also be transcendental & that the property that makes them expensive to compute.

\$\endgroup\$
0
\$\begingroup\$

You could use a look-up table. This uses a bit more memory, but memory is quite cheap. This is a common technique used in many Fractal renderers for computing the log-function. The log function is used to compute a kind of brightness, and since there are only 256 color values (well, levels of brightness), a lookup table with say 1000 entries is more than enough.

\$\endgroup\$
  • \$\begingroup\$ memory performance is so bad compared to compute performance on many platforms look-up tables will tank performance. Note the gamma function only works because you only need 256 bytes (and even then, will only work on some CPUs). With this lookup table, you would need 4x at least on IEEE fp 32's already lackluster precision for just 256 elements. Now you need to worry about cache misses due to other stuff going on in the background and loads and stores taking more time than actually computing sine and cos. LUTs almost never work on modern GPUs because of how memory bound they are. \$\endgroup\$ – whn May 21 '18 at 20:40
  • \$\begingroup\$ Nvidia GPUs actually have special function units for sin and cos, and can compute both at once. The performance of this far outpaces even reading from cache, I've found that recomputing values that need both sin and cos was faster than creating a look up table in shared memory by an order of magnitude at times because of how slow memory performance is compared to compute performance on GPUs. CPUs may or may not have actual dedicated hardware to compute sin or cos. \$\endgroup\$ – whn May 21 '18 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.