Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Faster asin() was hiding in plain sight

16bpp.net

Post reply on HN
Print view View original

121–130 of 140 posts

Re: Faster asin() was hiding in plain sight

#121

Post by pixelesque »

scottlamb wrote: post #27
TimorousBestie wrote: post #16

Earlier quoted context omitted.

I don’t know much about raytracing but it’s probably tricky to orchestrate all those asin calls so that the input and output memory is aligned and contiguous. My uneducated intuition is that there’s little regularity as to which pixels will take which branches and will end up requiring which asin calls, but I might be wrong.

I'd expect it to come down to data-oriented design: SoA (structure of arrays) rather than AoS (array of structures). I skimmed the author's source code, and this is where I'd start: https://github.com/define-private-public/PSRayTracing/blob/8... Instead of an `_objects`, I might try for a `_spheres`, `_boxes`, etc. (Or just `_lists` still using the virtual dispatch but for each list, rather than each object.) The `as…

It comes down to how "coherent" the rays are, and how much effort (compute) you want to put into sorting them into batches of rays.

With "primary" ray-tracing (i.e. camera rays, rays from surfaces to area lights), it's quite easy to batch them up and run SIMD operations on them.

But once you start doing global illumination, with rays bouncing off surfaces in all directions (and with complex materials, with multiple BSDF lobes, where lobes can be chosen stochastically), you start having to put a LOT of effort into sorting and batching rays such that they all (within a batch) hit the same objects or are going in roughly the same direction.

Re: Faster asin() was hiding in plain sight

#122

Post by rendaw »

neutronicus wrote: post #84
def-pri-pub wrote: post #57

Earlier quoted context omitted.

These are books that my uni courses never had me read. I'm a little shocked at times at how my degree program skimped on some of the more famous texts.

It is not a textbook, it is an extremely dense reference manual, so that honestly makes sense. In physics grad school, professors would occasionally allude to it, and textbooks would cite it ... pretty often. So it's a thing anyone with postgraduate physics education should know exists, but you wouldn't ever be assigned it .

Presumably someone read it though, at some point, in order to be able to cite it.

Re: Faster asin() was hiding in plain sight

#123

Post by neutronicus »

rendaw wrote: post #122
neutronicus wrote: post #84

Earlier quoted context omitted.

It is not a textbook, it is an extremely dense reference manual, so that honestly makes sense. In physics grad school, professors would occasionally allude to it, and textbooks would cite it ... pretty often. So it's a thing anyone with postgraduate physics education should know exists, but you wouldn't ever be assigned it .

Presumably someone read it though, at some point, in order to be able to cite it.

The relevant sections, at any rate

Re: Faster asin() was hiding in plain sight

#124

Post by djmips »

WithinReason wrote: post #118

> In any graphics application trigonometric functions are frequently used. Counterpoint from the man himself, "avoiding trigonometry": https://iquilezles.org/articles/noacos/

And further to that. https://fgiesen.wordpress.com/2010/10/21/finish-your-derivat...

Re: Faster asin() was hiding in plain sight

#125

Post by djmips »

To the blog poster:

Robin Green is an excellent resource

Faster Math Functions:

https://basesandframes.wordpress.com/wp-content/uploads/2016...

https://basesandframes.wordpress.com/wp-content/uploads/2016...

Even faster math functions GDC 2020:

https://www.gdcvault.com/play/1027337/Math-in-Game-Developme...

Re: Faster asin() was hiding in plain sight

#127

Post by davrosthedalek »

bee_rider wrote: post #62
herf wrote: post #37

Earlier quoted context omitted.

They teach a lot of Taylor/Maclaurin series in Math classes (and trig functions are sometimes called "CORDIC" which is an old method too) but these are not used much in actual FPUs and libraries. Maybe we should update the curricula so people know better ways.

Taylor series makes a lot more sense in a math class, right? It is straightforward and (just for example), when you are thinking about whether or not a series converges in the limit, why care about the quality of the approximation after a set number of steps?

Taylor series have a quite different convergence behavior than a general polynomial approximation. Or polynomial fit for that matter. Many papers were written which confuse this.

For example, 1/(x+2) has a pole at x=-2. The Taylor series around 0 will thus not converge for |x|>2. A polynomial approximation for, say, a range 0<x<L, will for all L.

Re: Faster asin() was hiding in plain sight

#128

Post by xyzzyz »

bee_rider wrote: post #62
herf wrote: post #37

Earlier quoted context omitted.

They teach a lot of Taylor/Maclaurin series in Math classes (and trig functions are sometimes called "CORDIC" which is an old method too) but these are not used much in actual FPUs and libraries. Maybe we should update the curricula so people know better ways.

Taylor series makes a lot more sense in a math class, right? It is straightforward and (just for example), when you are thinking about whether or not a series converges in the limit, why care about the quality of the approximation after a set number of steps?

Not quite. The point of Taylor’s theorem is that the n-th degree Taylor polynomial around a is the best n-th degree polynomial approximation around a. However, it doesn’t say anything about how good of an approximation it is further away from the point a. In fact, in math, when you use Taylor approximation, you don’t usually care about the infinite Taylor series, only the finite component.

Re: Faster asin() was hiding in plain sight

#129

Post by rockmeamedee »

jason_s wrote: post #23

While I'm glad to see the OP got a good minimax solution at the end, it seems like the article missed clarifying one of the key points: error waveforms over a specified interval are critical, and if you don't see the characteristic minimax-like wiggle, you're wasting easy opportunity for improvement. Taylor series in general are a poor choice, and Pade approximants of Taylor series are equally poor. If you're going t…

I had no idea, but this "wiggle" is required for an optimal approximation, it's called the "equioscillation property" [https://en.wikipedia.org/wiki/Equioscillation_theorem].

For a polynomial P (of degree n) to approximate a function F on the real numbers with minimal absolute error, the max error value of |P - F| needs to be hit multiple times, (n+2 times to be precise). You need to have the polynomial "wiggle" back and forth between the top of the error bound and the bottom.

And even more surprisingly, this is a necessary _and sufficient_! condition for optimality. If you find a polynomial whose error alternates and it hits its max error bound n+2 times, you know that no other polynomial of degree n can do better, that is the best error bound you can get for degree n.

Very cool!

Re: Faster asin() was hiding in plain sight

#130

Post by eesmith »

def-pri-pub wrote: post #57
exmadscientist wrote: post #32

This line: > This amazing snippet of code was languishing in the docs of dead software, which in turn the original formula was scrawled away in a math textbook from the 60s. was kind of telling for me. I have some background in this sort of work (and long ago concluded that there was pretty much nothing you can do to improve on existing code, unless either you have some new specific hardware or domain constraint, or…

These are books that my uni courses never had me read. I'm a little shocked at times at how my degree program skimped on some of the more famous texts.

I didn't need Abramowitz and Stegun until grad school. In the 1990s. It was a well-known reference book for people at that level, not a text book.

For my undergrad the CRC math handbook was enough.

Post reply on HN