Lab 3 Metaball Ray-Caster (Part 2)

The stdsun server was used to compile and run this project.
All root finding algorithms that need root finding are run with an fErr of 0.0001 and a dz=0.1.

results:

Experiment #1

The SmilingMetaballs.mball file was used for experiment 1. The pupose of experiment 1 is to show the effect of a light vector on a metaballs file. For this experiment, the light vector is taken to be <-1,-1,1>.

Timings for the analytical derivative rendering method:

• Total Run Time: 13.904898643 seconds
• Total Run Time Spent Bracketing: 12.693751335 seconds
• Total Run Time Spent Root Finding: 1.143481 seconds
• Total Run Time Spent Computating the Normal: 0.012286 seconds
• Total Run Total Spent Shading: 0.043760 seconds

Timings for the central differances derivative approximation rendering method:

• Total Run Time: 14.485647 seconds
• Total Run Time Spent Bracketing: 12.655354 seconds
• Total Run Time Spent Root Finding: 1.098821 seconds
• Total Run Time Spent Computating the Normal: 0.011780 seconds
• Total Run Total Spent Shading: 0.042979 seconds

Timings for the Richardson's Extrapolation derivative approximation rendering method with 3 iterations:

• Total Run Time: 17.171867 seconds
• Bracketing Total Run Time: 12.701098 seconds
• Root Finding Total Run Time: 1.078583 seconds
• Normal Computation Total Run Time: 0.012520 seconds
• Shading Computation Total Run Total: 0.043165 seconds

Timings for the Richardson's Extrapolation derivative approximation rendering method with 2 iterations:

• Total Run Time: 15.792127 seconds
• Bracketing Total Run Time: 12.663376 seconds
• Root Finding Total Run Time: 1.078583 seconds
• Normal Computation Total Run Time: 0.011991 seconds
• Shading Computation Total Run Total: 0.043165 seconds

Timings for the Richardson's Extrapolation derivative approximation rendering method with 1 iterations:

• Total Run Time: 14.504867 seconds
• Bracketing Total Run Time: 12.652152 seconds
• Root Finding Total Run Time: 1.078583 seconds
• Normal Computation Total Run Time: 0.011947 seconds
• Shading Computation Total Run Total: 0.043165 seconds

Analytical Smiling face	Central Differences Smiling face
3 Iterations Richardson's Extrapolation Smiling face	2 Iterations Richardson's Extrapolation Smiling face	1 Iteration Richardson's Extrapolation Smiling face

From the timings of the different methods the time spent on bracketing, finding the root, normalizing the vectors, and shading were all about the same. This is really to be expected. Also as expected, this implies that the major time differences come from the method used to find the derivative. In the end, the quickest method of finding the derivative is the analytical method. This is because either way a sum needs to be computed. The analytical derivative computes three sums, one for each of the deminsions, then it's done. The other two algorithms use the less costly feval operation. However, two algorithms as a whole use more mathmatical operations than the analytical approach. Also, one of the operations used within the the non-analytical algorithms is the more costly division operation. It turns out that two algorithms tie for second place. Those two algorithms are the central differences and 1 iteration of Richardson's extrapolation. This is because the with 1 iteration of Richardson's extrapolation, the two algorithms are identical. As more iterations are added onto Richardson's extrapolation, it quickly loses out to the other two methods. This is to be expected as with more iterations a loop is performed in which several operations take place.

While the Richardson's Extrapolation takes more time with more iterations, it is easily seen that it converges to a value that is reasonably close to the actual value of the derivative fairly quickly. In the pictures this can be seen. With just one iteration, the central differences and Richardson's extrapolation techniques render the same picture, as expected. It is easy to see that the number is not close enough to the actual derivative to render the same nice looking picture. Once a second iteration is applied, it is hard to tell the difference between the Richardson's extrapolation picture, and the analytical derivative picture. Of course it's still hard to tell the difference between the two with the third iteration of Richardson's extrapolation.

The numbers tells the story of what is really going on behind the scenes. The root mean square error is the biggest for the central difference and Richardson's extrapolation with 1 iteration with a value of 0.292273. For a graphics type job, at least, this error is rather large. However, for graphics, Richardson's extrapolation with 2 iterations is good enough. It's root mean square error is 0.017682. This might not be all that great for some other applications where more precision is needed. In those case is, Richardson's extrapolation with 3 iterations will probably be enough. It's mean square error is 0.000287. If more precision is needed, perhaps for a scientific related project, then more iterations of Richardson's extrapolation can be used.

It is clear, for this problem at least, that if there is access to the derivative, then it should be used. This is probably true for most equations, and is definetly true when a high amount of precision is needed. For most of the common problems for which the derivative is defined and easily obtainable, the analytical derivative is probably the way to go. Timewise, the analytical derivative will most likely have the time advantage as well. However, when the analytical derivative is hard to get at or not available, Richardson's extrapolation gives a great alternative.

Experiment #2

The TeddyBear.mball file was used for experiment 1. The pupose of experiment 2 is to emulate what an x-ray would like on a metaballs file.

Timings for the Riemann sum rendering method:

• Total Run Time: 89.316948 seconds
• Integration Total Run Total: 89.297882 seconds
• Total Run Total Spent Shading: 0.000000500

Timings for the composite trapezoid approximation rendering method with 64 iterations:

• Total Run Time: 59.067654 seconds
• Integration Total Run Total: 58.921963 seconds
• Total Run Total Spent Shading: 0.000000500

Timings for the Romberg's Extrapolation approximation rendering method with 3 iterations:

• Total Run Time: 4.921757696
• Integration Total Run Total: 4.741296 seconds
• Shading Computation Total Run Total: 0.000000500

Timings for the Romberg's Extrapolation approximation rendering method with 2 iterations:

• Total Run Time: 2.947233 seconds
• Integration Total Run Total: 2.899595 seconds
• Shading Computation Total Run Total: 0.000000500

Timings for the Romberg's Extrapolation approximation rendering method with 1 iterations:

• Total Run Time: 2.030501 seconds
• Integration Total Run Total: 1.912793
• Shading Computation Total Run Total: 0.000000500

Riemann Sum Teddy Bear	64 iterations Trapezoid Rule with Teddy Bear
3 iterations Romberg's Extrapolation Teddy Bear	2 iterations Romberg's Extrapolation Teddy Bear	1 itteration Romberg's Extrapolation Teddy Bear

For this experiment, it is made really obvious that the amount of time spent is really going to depend on the technique that is choosen to integrate a function. The Riemann sum took the longest time. This is to be expected, especially considering it runs for 100 iterations. The next slowest was the composite trapezoid approximation. This was no surprize either considering it had 64 iterations. Romberg's extrapolation took the least amount of time. Considering it was only run for just 1, 2, and 3 iterations, this is also not a surprize.

From the pictures, the next best thing to the "true" solution is the composite trapezoid approximation. This is an expected result since so man iterations of it were used. The Romberg extrapolation with 1 iteration was surprizing at first. The picture is blank. However, this makes sense if you think about the fact that the Gaussian function is symetric about zero. This is significant because Romberg's extrapolation with 1 iteration tries to fit a single trapezoid over the interval. The area under that particular interval is going to evaluate to zero because half of the interval is positive, and the other half with the exact same are is negative. Thus, these two terms cancel out. Romberg's extrapolation with 2 iterations provides a better picture than it did with 1 iteration. An image of a teddy bear can easily be seen in this picture. Although, it still does not have quite the same detail as the true solution. Romberg's extrapolation with 3 itterations gets better still, but is still not quite there. In fact 4 or more itterations are required for Romberg's extrapolation to produce a picture that looks really close to that of the "true" solution's.

These results are backed up by the numbers. A somewhat shocking result is that the composite trapezoid approximation comes very close to that of the "true" solution. It actually comes so close that a value of 0 is printed out for the root mean square error. All of the Romberg's extrapolation root mean square errors were as expected from the pictures. The less itterations used, the greater the root mean square error was, as expected.