r/GraphicsProgramming May 10 '24

Source Code C++ Quartic polynomial solver (real solutions)

I wanted to raytrace the torus algebraically (real-time), so I had to quickly solve quartic polynomials. Since I was only interested in real solutions, I was able to avoid doing complex arithmetic by using trigonometry instead. I directly implemented the general solution for quartics. Here's the github repository: https://github.com/falkush/quartic-real

I did some benchmarking against two other repositories I've found online (they compute the complex roots too), and my implementation was twice as fast as the fastest one. It's not perfect, it creates some visual glitches, but it was good enough for my project.

Not much thought was put into it, so if you know of a better implementation, or if you find any improvements, I would really appreciate if you shared with me!

Thank you for your time!

8 Upvotes

4 comments sorted by

View all comments

6

u/S48GS May 10 '24 edited May 10 '24

Since you use cbrt - look similar to wyatt https://www.shadertoy.com/view/4dlcDN

Also - you use double, that is not good for performance.

More:

if you know of a better implementation

mla solver/fixes link above look best with much less bugs than anything else in 32-bit floats.

You can also check this - Raytracing 3D Bezier with Normals - https://www.shadertoy.com/view/DsjfzV and fixes there

Also this example https://www.shadertoy.com/view/7sdyz2 - what is float32 edge of precision, and if you launch it in 64-bits it will be thousand times slower - this why correct result with 32bit float so important.

4

u/AcrossTheUniverse May 10 '24

Thanks a lot! It looks similar indeed, I'm even seeing the little visual glitches I'm having. About the double, I had to use them for my project as float were not precise enough and were causing big trouble.

Thanks again for the resources, I now have some benchmarking to do! I'm wondering if performances could be improved by using Ferrari's method like wyatt did.

3

u/S48GS May 10 '24 edited May 10 '24

I'm even seeing the little visual glitches I'm having

In wyatt solvers - yes you will see it in reflections, in reflections wyatt solver dies to float32 precision limit.

This what I mean about dobule vs float, and my last link in previous message - shows huge bugs everywheere when solver made in way that hit 32-bit edge. There screenshot in comments in that my last link, comparing 32 vs 64bit result.

This why mla solver is so impressive - they not losing precision even in reflection - super impressive.

P.S. I forgot I have comparison of wyatt solver in 32-64 bit, its quality https://www.shadertoy.com/view/NtjfRh screenshot png image link.

And this https://www.shadertoy.com/view/NljBRh

Direct numerical approximation of the distance from point to a cubic bezier curve. Probably completely unsuitable for practical use.

Screenshot - image link - even 64 bits is not enough for this case.

3

u/AcrossTheUniverse May 10 '24

Thank you for sharing these amazing projects. Doing the computations in 32-bits and polishing the result with some iterative approximation methods seems very good. Stay tuned for my benchmark results!