nl0s+@andrew.cmu.edu (Nathan James Loofbourrow) (11/09/89)
If you are willing to settle for approximate answers (and in most graphic applications, I would hope that you would :-) ), I would recommend using some variation on Newton's Method for determining roots of functions. If you separate your at-most-four roots by subdivision (of the interval in which the roots can occur; you should be able to produce a maximum interval without too much trouble, much as you might produce a bounding volume), you should be able to approximate the roots to any desired precision. Now no one is saying this is fast. Nathan Loofbourrow nl0s+@andrew.cmu.edu nl0s@andrew.bitnet
CMH117%PSUVM.BITNET@VMA.CC.CMU.EDU (Charles Hannum) (11/09/89)
I didn't ask the question, but thanks for your input. However, Ferrari's theorem yields a fast and very accurate answer.
larry@csccat.UUCP (Larry Spence) (11/10/89)
In article <Added.wZKFF0K00Ui30n4E4T@andrew.cmu.edu> CMH117%PSUVM.BITNET@VMA.CC.CMU.EDU (Charles Hannum) writes: >I didn't ask the question, but thanks for your input. However, Ferrari's >theorem yields a fast and very accurate answer. ^^^^ Are you sure about this? If it's the same closed-form solution that you find in the CRC books, etc., doesn't it use trig functions and cube roots? Seems to me there was a paper by Kajiya in the early '80s on numerical ray tracing, and there have been several in the last few years. My advice would be to go look at SIGGRAPH proceedings from 1981 on. Certainly, a closed form solution like the one suggested wouldn't take advantage of any coherence in the problem, unless you wrote all the trig stuff yourself. -- Larry Spence larry@csccat ...{texbell,texsun,attctc}!csccat!larry
wrf@mab.ecse.rpi.edu (Wm Randolph Franklin) (11/10/89)
In <19606@vax5.CIT.CORNELL.EDU> cfwy@vax5.cit.cornell.edu (Larry Gritz) writes: >I need an algorithm to find the roots of a quartic (polynomial of degree 4) >equation to find the solution to a ray-torus intersection test. Quadratic >is easy, and I found a solution to cubic, but I can't get a reference for >quartic. The equation looks like this: > a4*x^4 + a3*x^3 + a2*x^2 + a1*x + a0 = 0 >I'd appreciate a pointer to a solution, or better, a short algorithm >(efficient is good, too). The standard explicit solution may be found in handbooks such as Abramowitz. One disadvantage is that it requires using complex numbers even if all coefficients and all roots are real. This includes taking cube roots of complex numbers. In practice, finding any one root by Newton and then deflating to a cubic might be fastest. One problem with Newton is that it converges very slowly to multiple roots. However the multiple roots of f are roots of gcd(f,f'), so you can identify them. -- Wm. Randolph Franklin Internet: wrf@ecse.rpi.edu (or @cs.rpi.edu) Bitnet: Wrfrankl@Rpitsmts Telephone: (518) 276-6077; Telex: 6716050 RPI TROU; Fax: (518) 276-6261 Paper: ECSE Dept., 6026 JEC, Rensselaer Polytechnic Inst, Troy NY, 12180