UIUC85

7th January 2004 08:25 UTC

Mathy question...
Ok so I see all this mentioning of Whittaker iteration and Newton-Raphson something (well I guess it was just in UnConeD's presets). Care to explain what it can do other than simple approximations? Or providing a decent site works just as well.

Actually let me specify. Can you give me some decent examples as to where these methods could be used.

UnConeD

7th January 2004 15:14 UTC

Whittaker iteration and Newton-Raphson are 2 methods of finding roots of a function. This means:

Given a function f(x), find x so that f(x) = 0.

For simple equations (linear, quadratic) you can just calculate x directly. For more complicated equations, this is either very hard to do or even impossible, and so-called numerical/iterative methods are used instead.

Iterative methods start with a guess or approximation of x (let's call it x[0]) and based on that, calculate a better approximation (x[1]). By repeatedly applying the formula, x[k] will get closer to the real value of x where f(x) = 0.

The formula for newton-raphson is:

x[k+1] = x[k] - f(x[k])/f'(x[k])

where x[k] is the k'th iteration result, f(x) is the function and f'(x) is its derivative.
When the derivative is complicated and/or erratic, you can use Whittaker iteration instead:

x[k+1] = x[k] - f(x[k])/a

where a is a parameter.

In AVS, this is used to solve complicated equations for raytracing, e.g. quartics (VJ Chmutov for example).
When you have no idea of calculating a good initial guess x[0], it's best to use Whittaker iteration. If you have a good initial guess, Newton-Raphson will converge much more quickly.

For raytracing, Newton-Rapson will get unstable where the surface is tangent to the viewing direction and cause weird artifacts. Also in raytracing, you don't need all roots, just the root with smallest, positive x. If you pick the right sign and magnitude for the Whittaker parameter, this method will always converge on the right root.

I've had some success using a hybrid Newton-Raphson/Whittaker:

x[k+1] = x[k] - f(x[k])/(f'(x[k])*a + b)

where a and b are parameters. I used this in my flag DM. I first calculate the flag as if it was flat (a plane), and then use NR/H to approximate the flag.

Something that I've thought of but haven't tried yet is:

x[k+1] = x[k] + f(x[k])/max(abs(f'(x[k])),b)*sign(f'(x[k]))

This would have the advantage of NR's fast convergence for good approximations, and reverting back to Whittaker when it's not yet close.

In AVS, Whittaker is almost always the fastest method, because if you invert the parameter (1/a instead of a), you don't need any divisions. Also, the derivative of a function you can't solve analytically is almost always complicated.
The extra iterations needed for a good approximation with Whittaker are compensated by the simplicity of each iteration.

For more information, check Mathworld or pick up a Numerical Maths book. The problem with applying most methods to AVS is that most numerical methods are designed to get you accurate results in a reasonable amount of time, while in AVS you just need approximate results really fast.

UIUC85

7th January 2004 20:51 UTC

Thanks UnConeD :)

Quick questions though. In the Whittaker approach, isn't the initial x[k] still a guess? You said if you have no idea what the initial guess might be then use whittaker...
And do you just set 'a' arbitrarily? Is there some rule for setting it or what?

UnConeD

8th January 2004 02:14 UTC

For Whittaker I usually start at x[0] = 0, so yes that's an initial 'guess', but not in any way accurate. For my flag DM, using a flat flag as an initial guess is much better, because it already has an approximate depth that matches the camera rotation/orientation.

For raytracing you want the smallest positive root (larger than 0), so with Whittaker you'll want to assign 'a' the opposite sign of f(0), so that x[1] > 0. The choice for a is normally a guess at f'(x) in the desired root. You have to pick it high enough so that it won't skip over the first root and converge on the next one.

It's best to normalize your ray-direction for whittaker, because otherwise your steps are larger at the side of the window than in the middle.

UIUC85

8th January 2004 07:37 UTC

Alright so I see how they work and I see how I can use them to approximate roots of numbers but I dont see how I can use this to find intersections of rays...

UnConeD

8th January 2004 10:54 UTC

Not intersections of rays, intersections of rays with shapes.
If you have a general implicit equation for a shape f(x,y,z) = 0, you replace (x,y,z) by (k*dx+ox, k*dy+oy, k*dz+oz), where (dx,dy,dz) is your ray direction and (ox,oy,oz) is the ray origin. You then solve the resulting equation in k: f(k)=0 (usually only the smallest positive root is needed).
The point where the ray intersects your object is (k*dx+ox, k*dy+oy, k*dz+oz).

UIUC85

8th January 2004 19:35 UTC

No, I've written raytracers before but I just did something stupid. Nevermind. Thanks for the good explanation on those methods.

UIUC85

9th January 2004 00:05 UTC

Cant edit. sorry

Actually can you use it to solve the intersection points directly with out simplifying the equations? Just plug in the rays into the equation for your shape and make sure it's set equal to zero and then use Whittaker iteration to get the closest zero? It looks like you simplified the Chmutov Surface down to an easier quartic but could you just leave it? I tried it on a sphere and it seems to work, I just didn't work out the texture mapping.

S-uper_T-oast

9th January 2004 02:15 UTC

That is an excelent explanation UnConeD! I know understand how those work! Thank you very much!

UIUC85

9th January 2004 09:50 UTC

mmmm I'm assuming simplifying was just for optimiztion purposes?

UnConeD

9th January 2004 17:11 UTC

It makes sense to only calculate the values that actually change: for polynomials the coefficients are constant and it would be crazy to recalculate them per iteration.

Optimizing is always a good idea. Another thing you should consider is modifying your equation so it's easier to calculate and has (almost) the same result.
For example, the falloff function for my 3D metaballs was chosen to be a polynomial of distance which only contains even powers of distance: no square root is required for calculating it, and speeds it up some more.