Casting Rays

Suppose you’re a moderately experienced programmer and you want to learn about graphics.  After wandering the Internet for a while it becomes obvious there are two distinct disciplines when it comes to rendering.  The first is performance oriented and founded upon projecting and rasterizing geometry.  Applications using tech on this side of the fence are generally interactive and the time to render a frame is restricted to less than 30 milliseconds.  The second discipline is quality focused and founded upon tracing rays.  On this half of the field computational expense is a second rate concern and the time to render a frame can range from a few minutes to a few days.

Let’s say you go the real-time route and hit the Internet in search of tutorials and API documentation.  Here’s what a few hours and 1,000 plus lines of Win32 and DirectX code get you:

Casting Rays Image 01

That’s right:  A window with a black client area.  Sure, it’s redrawing at 60Hz, receiving messages from the OS and maybe it even reacts to resize events properly.  The trouble is you can’t show any of that to a non-programmer and have them understand you did something meaningful.  When starting from scratch it takes a solid week of toil to get pixels on screen and prove you aren’t perpetually twiddling your time away.  Such an investment is a huge discouragement to a sprouting graphics programmer.  If you opt for a ray tracing approach the same amount of code will net you something much more impressive:

Casting Rays Image 02

Editing a mere three lines of the same program yields a remarkably different (in terms of synthesized phenomena, not visual features) and equally interesting image:

Casting Rays Image 03

Much to my astonishment I was able to generate the previous images from scratch in a few hours without using any cumbersome APIs (I’m looking at you DirectX and Win32) or consulting the Internet.  An additional day of tinkering led to the following two images:

Casting Rays Image 07

Casting Rays Image 08

In college my Computer Science peers where always fiddling with ray traces while I was off experimenting with shadow volumes:

Casting Rays Image 04

HDR lighting:

Casting Rays Image 05

and extracting assets from a leaked Doom III demo:

Casting Rays Image 06

The reason for the difference in our extra curricular activities never donned on me until now.  Getting a basic ray tracer up and running is easy and early images can be impressive.  Getting an interactive graphics engine off the ground is tedious and early images are ho-hum.  The same contrast extends beyond getting started; for example, shadows are an implicit feature of any ray tracer (they just happen as a consequence of the algorithm) while a real-time system must explicitly compute shadowed regions.  This dichotomy can be generalized to a theme seen over and over in software engineering.  An elegant algorithm that’s concise and hugely flexible is often times exorbitantly slow at solving the problems deployed to it.  Cracking the same class of problems can be done much more efficiently if you are willing to develop a sprawling software system that explicitly deals with highly specific problem cases.


Solar Spectral Irradiance Part 2

The previous post discussed the possible utility of the satellite used in the Solar Radiation & Climate Experiment (aka SOURCE) when fine tuning atmospheric scatting simulations; specifically, using data from the SIM instrument to accurately replicate the spectral output of the Sun.  A tool to accomplish this and explore the full SSI Data Set in a general sense can be downloaded from here:

The code is a bit rough here and there but easy to read and modify where it counts.  The heart of the program is the data processing done in SSIData.cpp.  Processing is accomplished by partitioning the data into buckets of spectral irradiance values corresponding to a small range of wavelengths equal to that seen by a detector on the satellite. A single bucket holds a list of measurements, one for each day in the filtering window. Statistical anomalies (presumably from instrument malfunctions and planned shutdowns) are removed from each bucket by culling entries that deviate greater than some multiple of the standard deviation. Each bucket is then assigned a single spectral irradiance value equal to the average of the remaining entries. A continuous spectral irradiance function is approximated by interpolating between the averages assigned to each bucket. The re-sampled values in the output are computed by averaging the continuous function across the sampling interval.  What follows is a statistical exploration of the SSI Data with an eye towards using it in rendering applications.

The stability of the Sun’s spectral output can be can be examined by processing the entire Combined SSI data set (third entry down in the download table) and computing the standard deviation of the entries held by each bucket.  Using a filtering threshold of 2 sigma and a spectral range of 360 to 830 nanometers the the amount of data culled and the minimum, maximum and average of all the standard deviations turn out to be:

Percent of data set culled = 4%
Minimum Standard Deviation = 0.000352536
Maximum Standard Deviation = 0.003311630
Average Standard Deviation = 0.001264100

Recall that a standard deviation is in the same units as the population it was derived from.  The minimum and maximum reported irradiance are:

Minimum irradiance = 0.818344
Maximum irradiance = 2.100120

Given the range or irradiance values fluctuations of no more than +/- 0.0034 units indicate an exceptionally consistent spectral output.  From this result it’s safe to conclude that crunching through the entire data set is unnecessary.  Assuming the instruments on the satellite were functioning properly examining a narrow temporal window works just fine. When processing all the data from 2003 to 2013 the years 2012 and 2013 contain most of the culled values and appear to be largely anomalous with long sequences of the same irradiance reported for every wavelength and should therefore be avoided.  When restricting analysis to a single year and using the same 2 sigma culling threshold as before a temporal window centered on 2009 produces the highest quality results:

Percent of data set culled = 3%
Minimum Standard Deviation = 0.000091583
Maximum Standard Deviation = 0.001016310
Average Standard Deviation = 0.000371218

The following data tabulates spectral irradiance sampled at 10 nanometer intervals for the year 2009. The first column specifies the wavelength while the second and third columns are the corresponding irradiance from the Sun at a distance of one AU. The second column was derived from the SSI data while the third was simulated by approximating the Sun as a black body at 5877 degrees Kelvin using Planck’s Law.

360  9.516930920e-001  1.490768419e+000
370  1.197826846e+000  1.562546223e+000
380  1.176483670e+000  1.627999281e+000
390  1.179733765e+000  1.687002253e+000
400  1.620991049e+000  1.739532741e+000
410  1.713176721e+000  1.785655334e+000
420  1.739654186e+000  1.825506525e+000
430  1.510140514e+000  1.859280815e+000
440  1.811059353e+000  1.887218171e+000
450  2.054504598e+000  1.909592901e+000
460  2.074744075e+000  1.926703943e+000
470  2.027987887e+000  1.938866529e+000
480  2.098076411e+000  1.946405112e+000
490  1.953476284e+000  1.949647479e+000
500  1.951250979e+000  1.948919904e+000
510  1.947861312e+000  1.944543253e+000
520  1.837963497e+000  1.936829895e+000
530  1.916672834e+000  1.926081333e+000
540  1.892077945e+000  1.912586435e+000
550  1.888699212e+000  1.896620182e+000
560  1.845626691e+000  1.878442847e+000
570  1.843883785e+000  1.858299527e+000
580  1.836040875e+000  1.836419964e+000
590  1.786591082e+000  1.813018611e+000
600  1.764918047e+000  1.788294867e+000
610  1.712688962e+000  1.762433471e+000
620  1.669518668e+000  1.735604999e+000
630  1.640912179e+000  1.707966441e+000
640  1.605636942e+000  1.679661835e+000
650  1.553109072e+000  1.650822939e+000
660  1.523129542e+000  1.621569919e+000
670  1.514671793e+000  1.592012046e+000
680  1.481266163e+000  1.562248387e+000
690  1.444357539e+000  1.532368487e+000
700  1.407205273e+000  1.502453029e+000
710  1.371497526e+000  1.472574473e+000
720  1.335829076e+000  1.442797668e+000
730  1.304067554e+000  1.413180437e+000
740  1.275121302e+000  1.383774125e+000
750  1.250503961e+000  1.354624128e+000
760  1.224258600e+000  1.325770380e+000
770  1.197535640e+000  1.297247813e+000
780  1.172475695e+000  1.269086788e+000
790  1.145479132e+000  1.241313497e+000
800  1.118541784e+000  1.213950334e+000
810  1.092744384e+000  1.187016240e+000
820  1.067436112e+000  1.160527027e+000
830  1.043209662e+000  1.134495668e+000

Here’s the same data again using a more detailed 1 nanometer sampling interval.

360  9.516930920e-001  1.490768419e+000
361  9.620898979e-001  1.498224849e+000
362  9.621930255e-001  1.505620066e+000
363  9.969925766e-001  1.512953779e+000
364  1.039105769e+000  1.520225715e+000
365  1.100759708e+000  1.527435612e+000
366  1.177558592e+000  1.534583219e+000
367  1.198040061e+000  1.541668301e+000
368  1.188647357e+000  1.548690635e+000
369  1.187093383e+000  1.555650009e+000
370  1.197826846e+000  1.562546223e+000
371  1.172990484e+000  1.569379092e+000
372  1.107392908e+000  1.576148440e+000
373  1.024781781e+000  1.582854103e+000
374  9.757398257e-001  1.589495931e+000
375  9.958442919e-001  1.596073783e+000
376  1.083955799e+000  1.602587531e+000
377  1.183748955e+000  1.609037056e+000
378  1.237517790e+000  1.615422251e+000
379  1.228275878e+000  1.621743022e+000
380  1.176483670e+000  1.627999281e+000
381  1.089352450e+000  1.634190955e+000
382  9.627550404e-001  1.640317979e+000
383  8.739780658e-001  1.646380297e+000
384  8.717593775e-001  1.652377866e+000
385  9.389554907e-001  1.658310650e+000
386  9.860652788e-001  1.664178625e+000
387  1.006943823e+000  1.669981774e+000
388  1.034378848e+000  1.675720092e+000
389  1.101896489e+000  1.681393581e+000
390  1.179733765e+000  1.687002253e+000
391  1.178544673e+000  1.692546128e+000
392  1.084807076e+000  1.698025236e+000
393  9.812581883e-001  1.703439615e+000
394  9.602971400e-001  1.708789310e+000
395  9.925452391e-001  1.714074377e+000
396  1.043667949e+000  1.719294878e+000
397  1.116122355e+000  1.724450883e+000
398  1.267841764e+000  1.729542470e+000
399  1.456440859e+000  1.734569725e+000
400  1.620991049e+000  1.739532741e+000
401  1.704911278e+000  1.744431619e+000
402  1.733438738e+000  1.749266467e+000
403  1.730737247e+000  1.754037399e+000
404  1.708879535e+000  1.758744538e+000
405  1.680538087e+000  1.763388010e+000
406  1.667044997e+000  1.767967952e+000
407  1.672077303e+000  1.772484504e+000
408  1.681616789e+000  1.776937815e+000
409  1.700260415e+000  1.781328039e+000
410  1.713176721e+000  1.785655334e+000
411  1.734827771e+000  1.789919868e+000
412  1.759609840e+000  1.794121812e+000
413  1.774400732e+000  1.798261343e+000
414  1.786839945e+000  1.802338645e+000
415  1.780886065e+000  1.806353904e+000
416  1.772249766e+000  1.810307315e+000
417  1.758644076e+000  1.814199077e+000
418  1.744977879e+000  1.818029393e+000
419  1.742436951e+000  1.821798471e+000
420  1.739654186e+000  1.825506525e+000
421  1.742491852e+000  1.829153772e+000
422  1.737108895e+000  1.832740436e+000
423  1.724123489e+000  1.836266742e+000
424  1.713488389e+000  1.839732923e+000
425  1.697502364e+000  1.843139213e+000
426  1.678250802e+000  1.846485851e+000
427  1.640182961e+000  1.849773082e+000
428  1.581333635e+000  1.853001151e+000
429  1.534953247e+000  1.856170311e+000
430  1.510140514e+000  1.859280815e+000
431  1.522884431e+000  1.862332921e+000
432  1.578271130e+000  1.865326892e+000
433  1.643522666e+000  1.868262991e+000
434  1.706013146e+000  1.871141487e+000
435  1.750126424e+000  1.873962650e+000
436  1.771163243e+000  1.876726755e+000
437  1.777002512e+000  1.879434078e+000
438  1.777296234e+000  1.882084900e+000
439  1.788011877e+000  1.884679503e+000
440  1.811059353e+000  1.887218171e+000
441  1.845244226e+000  1.889701193e+000
442  1.884007033e+000  1.892128859e+000
443  1.911747689e+000  1.894501461e+000
444  1.930190574e+000  1.896819293e+000
445  1.943511377e+000  1.899082654e+000
446  1.955620258e+000  1.901291840e+000
447  1.980779005e+000  1.903447155e+000
448  2.012011020e+000  1.905548899e+000
449  2.036353261e+000  1.907597379e+000
450  2.054504598e+000  1.909592901e+000
451  2.060390953e+000  1.911535772e+000
452  2.052189276e+000  1.913426303e+000
453  2.042238458e+000  1.915264805e+000
454  2.039350519e+000  1.917051590e+000
455  2.040097573e+000  1.918786974e+000
456  2.045187744e+000  1.920471271e+000
457  2.054494624e+000  1.922104798e+000
458  2.062828943e+000  1.923687873e+000
459  2.068914352e+000  1.925220814e+000
460  2.074744075e+000  1.926703943e+000
461  2.078234276e+000  1.928137580e+000
462  2.079062936e+000  1.929522047e+000
463  2.073740872e+000  1.930857666e+000
464  2.064124068e+000  1.932144761e+000
465  2.052380139e+000  1.933383657e+000
466  2.039143808e+000  1.934574677e+000
467  2.027807284e+000  1.935718149e+000
468  2.023997096e+000  1.936814397e+000
469  2.024213245e+000  1.937863748e+000
470  2.027987887e+000  1.938866529e+000
471  2.035819221e+000  1.939823068e+000
472  2.046494231e+000  1.940733691e+000
473  2.056181910e+000  1.941598727e+000
474  2.065630580e+000  1.942418505e+000
475  2.075104157e+000  1.943193351e+000
476  2.083112491e+000  1.943923595e+000
477  2.090029002e+000  1.944609564e+000
478  2.096567983e+000  1.945251588e+000
479  2.099867303e+000  1.945849995e+000
480  2.098076411e+000  1.946405112e+000
481  2.084547959e+000  1.946917269e+000
482  2.059662445e+000  1.947386793e+000
483  2.027942220e+000  1.947814012e+000
484  1.993699106e+000  1.948199254e+000
485  1.961995504e+000  1.948542845e+000
486  1.938091679e+000  1.948845113e+000
487  1.927162346e+000  1.949106385e+000
488  1.929324659e+000  1.949326986e+000
489  1.939558275e+000  1.949507242e+000
490  1.953476284e+000  1.949647479e+000
491  1.967817985e+000  1.949748021e+000
492  1.980512703e+000  1.949809192e+000
493  1.989346534e+000  1.949831316e+000
494  1.993613170e+000  1.949814715e+000
495  1.993744748e+000  1.949759713e+000
496  1.988927968e+000  1.949666631e+000
497  1.980768804e+000  1.949535789e+000
498  1.971607931e+000  1.949367508e+000
499  1.960539677e+000  1.949162107e+000
500  1.951250979e+000  1.948919904e+000
501  1.944651818e+000  1.948641218e+000
502  1.942355205e+000  1.948326365e+000
503  1.944046964e+000  1.947975661e+000
504  1.948101641e+000  1.947589421e+000
505  1.953369551e+000  1.947167960e+000
506  1.958359282e+000  1.946711590e+000
507  1.960717273e+000  1.946220623e+000
508  1.959292380e+000  1.945695372e+000
509  1.955074919e+000  1.945136145e+000
510  1.947861312e+000  1.944543253e+000
511  1.933597667e+000  1.943917002e+000
512  1.913908816e+000  1.943257700e+000
513  1.891983763e+000  1.942565653e+000
514  1.871018881e+000  1.941841165e+000
515  1.852234224e+000  1.941084540e+000
516  1.835566486e+000  1.940296080e+000
517  1.824294098e+000  1.939476086e+000
518  1.821744036e+000  1.938624859e+000
519  1.827662149e+000  1.937742696e+000
520  1.837963497e+000  1.936829895e+000
521  1.847468317e+000  1.935886753e+000
522  1.857671780e+000  1.934913564e+000
523  1.868936023e+000  1.933910622e+000
524  1.880266922e+000  1.932878220e+000
525  1.889386797e+000  1.931816647e+000
526  1.893514926e+000  1.930726195e+000
527  1.897242821e+000  1.929607151e+000
528  1.903019758e+000  1.928459803e+000
529  1.910566927e+000  1.927284435e+000
530  1.916672834e+000  1.926081333e+000
531  1.919936514e+000  1.924850779e+000
532  1.921403387e+000  1.923593055e+000
533  1.921680440e+000  1.922308440e+000
534  1.920757694e+000  1.920997214e+000
535  1.917707146e+000  1.919659653e+000
536  1.912650194e+000  1.918296033e+000
537  1.906480768e+000  1.916906630e+000
538  1.900519014e+000  1.915491715e+000
539  1.895800983e+000  1.914051560e+000
540  1.892077945e+000  1.912586435e+000
541  1.889420595e+000  1.911096609e+000
542  1.888246558e+000  1.909582348e+000
543  1.887958561e+000  1.908043919e+000
544  1.888245488e+000  1.906481585e+000
545  1.889099140e+000  1.904895609e+000
546  1.889498886e+000  1.903286252e+000
547  1.890040400e+000  1.901653774e+000
548  1.890681139e+000  1.899998432e+000
549  1.890372601e+000  1.898320483e+000
550  1.888699212e+000  1.896620182e+000
551  1.885795326e+000  1.894897784e+000
552  1.881451113e+000  1.893153538e+000
553  1.877031736e+000  1.891387698e+000
554  1.872527535e+000  1.889600510e+000
555  1.867690612e+000  1.887792223e+000
556  1.862477251e+000  1.885963082e+000
557  1.857155283e+000  1.884113332e+000
558  1.851965718e+000  1.882243216e+000
559  1.848294489e+000  1.880352974e+000
560  1.845626691e+000  1.878442847e+000
561  1.844194724e+000  1.876513073e+000
562  1.842654195e+000  1.874563889e+000
563  1.841211485e+000  1.872595529e+000
564  1.840588785e+000  1.870608227e+000
565  1.840773690e+000  1.868602216e+000
566  1.841590261e+000  1.866577725e+000
567  1.842498988e+000  1.864534984e+000
568  1.843219851e+000  1.862474221e+000
569  1.843616536e+000  1.860395660e+000
570  1.843883785e+000  1.858299527e+000
571  1.844216363e+000  1.856186043e+000
572  1.844906972e+000  1.854055432e+000
573  1.845474087e+000  1.851907911e+000
574  1.845844518e+000  1.849743701e+000
575  1.845482933e+000  1.847563016e+000
576  1.844711556e+000  1.845366073e+000
577  1.843307210e+000  1.843153085e+000
578  1.841703594e+000  1.840924264e+000
579  1.839739961e+000  1.838679820e+000
580  1.836040875e+000  1.836419964e+000
581  1.831655695e+000  1.834144902e+000
582  1.826369107e+000  1.831854841e+000
583  1.820978930e+000  1.829549985e+000
584  1.815497728e+000  1.827230538e+000
585  1.809816296e+000  1.824896700e+000
586  1.804165773e+000  1.822548672e+000
587  1.798829213e+000  1.820186653e+000
588  1.793933153e+000  1.817810840e+000
589  1.789637920e+000  1.815421427e+000
590  1.786591082e+000  1.813018611e+000
591  1.784241740e+000  1.810602582e+000
592  1.782164042e+000  1.808173533e+000
593  1.780202355e+000  1.805731653e+000
594  1.778458479e+000  1.803277131e+000
595  1.776732464e+000  1.800810153e+000
596  1.774997719e+000  1.798330905e+000
597  1.773084522e+000  1.795839570e+000
598  1.770992874e+000  1.793336332e+000
599  1.768155842e+000  1.790821371e+000
600  1.764918047e+000  1.788294867e+000
601  1.761050240e+000  1.785756998e+000
602  1.756973316e+000  1.783207941e+000
603  1.752673257e+000  1.780647871e+000
604  1.748167949e+000  1.778076963e+000
605  1.742961485e+000  1.775495389e+000
606  1.737428146e+000  1.772903320e+000
607  1.731075351e+000  1.770300926e+000
608  1.724778008e+000  1.767688375e+000
609  1.718640602e+000  1.765065835e+000
610  1.712688962e+000  1.762433471e+000
611  1.707015939e+000  1.759791447e+000
612  1.701367548e+000  1.757139927e+000
613  1.695748068e+000  1.754479072e+000
614  1.690331659e+000  1.751809042e+000
615  1.685110348e+000  1.749129996e+000
616  1.680812346e+000  1.746442092e+000
617  1.677300937e+000  1.743745486e+000
618  1.674441658e+000  1.741040333e+000
619  1.672094774e+000  1.738326787e+000
620  1.669518668e+000  1.735604999e+000
621  1.666762457e+000  1.732875121e+000
622  1.663875064e+000  1.730137303e+000
623  1.660875913e+000  1.727391692e+000
624  1.658057302e+000  1.724638437e+000
625  1.655412143e+000  1.721877682e+000
626  1.652873946e+000  1.719109574e+000
627  1.650461303e+000  1.716334253e+000
628  1.647687370e+000  1.713551864e+000
629  1.644348380e+000  1.710762547e+000
630  1.640912179e+000  1.707966441e+000
631  1.637249136e+000  1.705163684e+000
632  1.633681713e+000  1.702354415e+000
633  1.630440262e+000  1.699538768e+000
634  1.627223103e+000  1.696716878e+000
635  1.624058700e+000  1.693888879e+000
636  1.620843059e+000  1.691054903e+000
637  1.617147668e+000  1.688215082e+000
638  1.613349263e+000  1.685369544e+000
639  1.609501069e+000  1.682518419e+000
640  1.605636942e+000  1.679661835e+000
641  1.601868285e+000  1.676799917e+000
642  1.598165964e+000  1.673932791e+000
643  1.593670124e+000  1.671060581e+000
644  1.587933216e+000  1.668183410e+000
645  1.582115876e+000  1.665301399e+000
646  1.576017958e+000  1.662414670e+000
647  1.569947220e+000  1.659523342e+000
648  1.564194447e+000  1.656627532e+000
649  1.558507387e+000  1.653727359e+000
650  1.553109072e+000  1.650822939e+000
651  1.547840481e+000  1.647914387e+000
652  1.542729595e+000  1.645001816e+000
653  1.537845675e+000  1.642085340e+000
654  1.533219754e+000  1.639165070e+000
655  1.529639795e+000  1.636241118e+000
656  1.526213621e+000  1.633313593e+000
657  1.524681847e+000  1.630382603e+000
658  1.523718409e+000  1.627448257e+000
659  1.523182752e+000  1.624510660e+000
660  1.523129542e+000  1.621569919e+000
661  1.523020583e+000  1.618626138e+000
662  1.522679329e+000  1.615679420e+000
663  1.522316391e+000  1.612729868e+000
664  1.521738205e+000  1.609777584e+000
665  1.521080399e+000  1.606822667e+000
666  1.520345438e+000  1.603865217e+000
667  1.519460724e+000  1.600905333e+000
668  1.518481509e+000  1.597943113e+000
669  1.516668386e+000  1.594978652e+000
670  1.514671793e+000  1.592012046e+000
671  1.512042316e+000  1.589043391e+000
672  1.508727161e+000  1.586072779e+000
673  1.505404517e+000  1.583100304e+000
674  1.502038670e+000  1.580126056e+000
675  1.498665912e+000  1.577150128e+000
676  1.495255615e+000  1.574172609e+000
677  1.491812034e+000  1.571193588e+000
678  1.488354074e+000  1.568213152e+000
679  1.484816242e+000  1.565231390e+000
680  1.481266163e+000  1.562248387e+000
681  1.477699568e+000  1.559264230e+000
682  1.474116457e+000  1.556279001e+000
683  1.470527553e+000  1.553292786e+000
684  1.466892919e+000  1.550305667e+000
685  1.463248835e+000  1.547317725e+000
686  1.459559879e+000  1.544329042e+000
687  1.455794521e+000  1.541339698e+000
688  1.452028367e+000  1.538349772e+000
689  1.448202506e+000  1.535359342e+000
690  1.444357539e+000  1.532368487e+000
691  1.440519576e+000  1.529377284e+000
692  1.436707875e+000  1.526385807e+000
693  1.432897924e+000  1.523394133e+000
694  1.429128590e+000  1.520402336e+000
695  1.425398278e+000  1.517410489e+000
696  1.421671968e+000  1.514418665e+000
697  1.418012333e+000  1.511426936e+000
698  1.414370922e+000  1.508435374e+000
699  1.410749889e+000  1.505444049e+000
700  1.407205273e+000  1.502453029e+000
701  1.403665750e+000  1.499462385e+000
702  1.400139502e+000  1.496472185e+000
703  1.396630150e+000  1.493482495e+000
704  1.393120798e+000  1.490493383e+000
705  1.389558269e+000  1.487504914e+000
706  1.385972952e+000  1.484517153e+000
707  1.382383501e+000  1.481530166e+000
708  1.378759598e+000  1.478544015e+000
709  1.375128344e+000  1.475558763e+000
710  1.371497526e+000  1.472574473e+000
711  1.367868342e+000  1.469591207e+000
712  1.364239267e+000  1.466609024e+000
713  1.360592590e+000  1.463627986e+000
714  1.356910177e+000  1.460648152e+000
715  1.353227765e+000  1.457669580e+000
716  1.349606532e+000  1.454692329e+000
717  1.346048978e+000  1.451716456e+000
718  1.342491424e+000  1.448742017e+000
719  1.339108864e+000  1.445769070e+000
720  1.335829076e+000  1.442797668e+000
721  1.332549288e+000  1.439827868e+000
722  1.329340490e+000  1.436859723e+000
723  1.326156634e+000  1.433893287e+000
724  1.322970716e+000  1.430928612e+000
725  1.319740587e+000  1.427965751e+000
726  1.316497784e+000  1.425004755e+000
727  1.313266871e+000  1.422045676e+000
728  1.310173139e+000  1.419088563e+000
729  1.307113244e+000  1.416133467e+000
730  1.304067554e+000  1.413180437e+000
731  1.301155058e+000  1.410229520e+000
732  1.298272755e+000  1.407280765e+000
733  1.295383544e+000  1.404334220e+000
734  1.292433370e+000  1.401389931e+000
735  1.289469785e+000  1.398447945e+000
736  1.286510340e+000  1.395508306e+000
737  1.283592302e+000  1.392571061e+000
738  1.280683926e+000  1.389636253e+000
739  1.277790495e+000  1.386703927e+000
740  1.275121302e+000  1.383774125e+000
741  1.272511911e+000  1.380846891e+000
742  1.269906504e+000  1.377922267e+000
743  1.267500156e+000  1.375000295e+000
744  1.265156176e+000  1.372081015e+000
745  1.262812197e+000  1.369164469e+000
746  1.260408210e+000  1.366250697e+000
747  1.257974666e+000  1.363339738e+000
748  1.255541121e+000  1.360431631e+000
749  1.253047943e+000  1.357526415e+000
750  1.250503961e+000  1.354624128e+000
751  1.247959979e+000  1.351724808e+000
752  1.245422027e+000  1.348828492e+000
753  1.242893505e+000  1.345935216e+000
754  1.240364983e+000  1.343045016e+000
755  1.237808665e+000  1.340157928e+000
756  1.235159695e+000  1.337273987e+000
757  1.232507637e+000  1.334393228e+000
758  1.229837919e+000  1.331515685e+000
759  1.227057826e+000  1.328641391e+000
760  1.224258600e+000  1.325770380e+000
761  1.221459374e+000  1.322902685e+000
762  1.218668525e+000  1.320038337e+000
763  1.215880620e+000  1.317177370e+000
764  1.213092716e+000  1.314319813e+000
765  1.210365798e+000  1.311465699e+000
766  1.207707662e+000  1.308615057e+000
767  1.205049526e+000  1.305767919e+000
768  1.202435955e+000  1.302924312e+000
769  1.199981552e+000  1.300084267e+000
770  1.197535640e+000  1.297247813e+000
771  1.195088163e+000  1.294414977e+000
772  1.192617215e+000  1.291585789e+000
773  1.190140007e+000  1.288760275e+000
774  1.187662800e+000  1.285938462e+000
775  1.185154483e+000  1.283120378e+000
776  1.182613788e+000  1.280306048e+000
777  1.180073093e+000  1.277495499e+000
778  1.177534455e+000  1.274688756e+000
779  1.175004634e+000  1.271885844e+000
780  1.172475695e+000  1.269086788e+000
781  1.169946756e+000  1.266291613e+000
782  1.167379682e+000  1.263500342e+000
783  1.164795475e+000  1.260713000e+000
784  1.162211269e+000  1.257929608e+000
785  1.159576193e+000  1.255150191e+000
786  1.156785392e+000  1.252374771e+000
787  1.153993552e+000  1.249603370e+000
788  1.151200927e+000  1.246836010e+000
789  1.148349446e+000  1.244072712e+000
790  1.145479132e+000  1.241313497e+000
791  1.142608818e+000  1.238558386e+000
792  1.139788068e+000  1.235807400e+000
793  1.137101310e+000  1.233060559e+000
794  1.134414553e+000  1.230317882e+000
795  1.131727796e+000  1.227579389e+000
796  1.129105278e+000  1.224845098e+000
797  1.126506522e+000  1.222115029e+000
798  1.123907767e+000  1.219389200e+000
799  1.121278773e+000  1.216667629e+000
800  1.118541784e+000  1.213950334e+000
801  1.115799033e+000  1.211237332e+000
802  1.113056282e+000  1.208528640e+000
803  1.110389297e+000  1.205824276e+000
804  1.107777174e+000  1.203124256e+000
805  1.105165050e+000  1.200428595e+000
806  1.102569662e+000  1.197737311e+000
807  1.100099778e+000  1.195050418e+000
808  1.097654994e+000  1.192367932e+000
809  1.095210209e+000  1.189689868e+000
810  1.092744384e+000  1.187016240e+000
811  1.090229458e+000  1.184347064e+000
812  1.087714533e+000  1.181682353e+000
813  1.085199608e+000  1.179022121e+000
814  1.082621707e+000  1.176366382e+000
815  1.080003540e+000  1.173715150e+000
816  1.077385374e+000  1.171068436e+000
817  1.074780746e+000  1.168426255e+000
818  1.072311480e+000  1.165788618e+000
819  1.069873796e+000  1.163155538e+000
820  1.067436112e+000  1.160527027e+000
821  1.065033169e+000  1.157903097e+000
822  1.062760499e+000  1.155283759e+000
823  1.060496512e+000  1.152669024e+000
824  1.058232524e+000  1.150058904e+000
825  1.055914650e+000  1.147453408e+000
826  1.053508857e+000  1.144852549e+000
827  1.051103064e+000  1.142256335e+000
828  1.048697271e+000  1.139664777e+000
829  1.046046041e+000  1.137077885e+000
830  1.043209662e+000  1.134495668e+000

The following image was constructed from the higher resolution data in the second table.

SSI Part 2 Figure 01

The colored region correspond to the second column in the table (the processed SSI data) and the white curve corresponds to the third column (the theoretical results from the black body approximation). Aside from a slight overestimation in the red wavelengths and a slight underestimation in the blue wavelengths modeling the Sun as a black body is a decent approximation; to get a vague idea of how decent a trip through the color pipeline is in order. Convoluting both data sets with the CIE 1931 2-Degree Standard Observer XYZ Color Matching Functions yields the following CIE XYZ tristimulus values:

1.898827209e+002 1.964763489e+002 2.040202179e+002  SSI Data
1.933248138e+002 1.989763794e+002 2.031809692e+002  Black Body

Converting to unconstrained, linear sRGB values:

2.115861511e+002 1.930211487e+002 1.861898041e+002  SSI Data
2.193156738e+002 1.943400574e+002 1.849838867e+002  Black Body

Clamping to the sRGB gamut and normalizing such that the largest component is one:

1.000000000e+000 9.122579694e-001 8.799716234e-001  SSI Data
1.000000000e+000 8.861202598e-001 8.434594870e-001  Black Body

Gamma correcting and converting to 8 bit integers:

255 245 241  SSI Data
255 242 237  Black Body

Finally, displaying the values:

SSI Part 2 Figure 02

Not exactly the same but fairly close. When it comes to rendering there is likely little to gain by using data from the SOURCE satellite. Planck’s Law does a decent enough job of approximating sunlight and an implementation turns out to be rather straight forward.  A function written in C++ that computes the spectral radiance emitted by a black body should look something like this:

// SpectralRadianceBB(...)
// Compute the spectral radiance at a particular wavelength emitted by
// a black body radiating at a particular temperature using Planck's
// Law.
// a_fLambda  The wavelength of interest in nanometers
// a_fTemp    The temperature of the black body in kelvin
// The return value has the following units:
//       Watts                   1
// ---------------------  *  ----------
// Steradians * Meters^2     Nanometers
// To convert from spectral radiance to radiance integrate spectral
// radiance over a range of wavelengths:
//             _
//            / L1
//            |
// Radiance = | SpectralRadianceBB(L, t)dL
//            |
//           _/ L0
// L  = wavelength "lambda"
// dL = differential operator with respect to L
// L0 = minimum wavelength
// L1 = maximum wavelength
// t  = temperature (constant w.r.t L)

double SpectralRadianceBB(double a_fLambda, double a_fTemp)
    // k1 and k2 are calculated from the following physical constants:
    // h  = Planck constant
    // c  = Speed of light
    // kb = Boltzmann constant
    static const double s_fK1 = 1.1910428661813628e-016; // 2*h*c*c
    static const double s_fK2 = 1.4387769576158687e-002; // (h*c)/kb

    // Convert wavelength from nanometers to meters
    a_fLambda *= 1e-9; 

    // Compute spectral radiance with units:
    //         Watts
    // ---------------------
    // Steradians * Meters^3
    double fNum    = (s_fK1 * pow(a_fLambda, -5.0));
    double fDen    = (exp(s_fK2 / (a_fLambda * a_fTemp)) - 1.0);
    double fResult = fNum / fDen;

    // Convert spectral radiance into the more common form:
    //        Watts                  1
    // ---------------------  *  ----------
    // Steradians * Meters^2     Nanometers
    fResult *= 1e-9; 

    return fResult;

Converting the spectral radiance returned by SpectralRadianceBB(…) to spectral irradiance can be accomplished by this little gem:

// CalcDeltaOmega(...)
// Delta omega refers to the 'dw' term (typically) written at the end
// of an integral that integrates radiance over a solid angle
// producing irradiance.
//               _
//              /
//              |
// Irradiance = | Radiance(w) dw 
//              |
//             _/
// The return value of this function can be used to approximate the
// irradiance arriving at a point given the radiance emitted
// from a sufficiently distant disk shaped light source.
// fIrradiance = fRadiance * CalcDeltaOmega(fRadius, fDistance)
// Here 'fRadius' is the radius of the light source and 'fDistance' is
// the distance form the light to the point of interest. Similar to
// the above computation the radiance emitted by the light source can 
// be approximated if the irradiance arriving at the point (strictly
// from the light) is known.
// fRadiance = fIrradiance / CalcDeltaOmega(fRadius, fDistance)
// Calculating the unknown irradiance arriving at distance B given the
// known irradiance arriving at distance A can be also be calculated
// by noting that radiance is constant along rays through space.
// fRadiance = fIrradianceA / CalcDeltaOmega(fRadius, fDistanceA)
// fIrradianceB = fRadiance * CalcDeltaOmega(fRadius, fDistanceB)

double CalcDeltaOmega(double a_fRadius, double a_fDistance)
    double fNum = 3.14159265359 * a_fRadius * a_fRadius;
    double fDen = a_fDistance * a_fDistance;

    return fNum / fDen;

Haven taken a thorough look at the spectral output of the Sun, its temporal variability and how is compares to a black body approximation we can now turn our attention to Earth’s orbit and it’s effects on the total incident irradiance.  Earth’s orbit is elliptical with an average distance at periapsis (closest to the Sun) of 147,098,074 km and an average distance at apoapsis (furthest from the Sun) of 152,097,701 km.  Periapsis and apoapsis occur in early January (1st through the 5th) and early July (3rd through the 6th) respectively.  The following animation was constructed by plotting the spectral irradiance from 1 to 2047 nanometers from as seen by the Earth on the 15th of every month for the year 2009.

SSI Part 2 Figure 03

Here’s the same animation again zoomed in on the visible wavelengths.

SSI Part 2 Figure 04

Once again the colored region is the processed SSI data and the two white curves are the the theoretical black body approximation.  The curves have been fixed with respect to time such that the top is a plot of the spectral irradiance received at periapsis and the bottom is the spectral irradiance received at apoapsis.  Earth’s position was computed with Kepler’s Laws using data gathered from here:

AstroPixels:  Earth at Perihelion and Aphelion

Scaling the spectral irradiance values with respect to distance was accomplished with CalcDeltaOmega(…).  The variation at periapsis and apoapsis relative to 1 AU turn out to be:

+3.2445%  At periapsis on 2009/01/04 (147,094,889 km)
-3.4322%  At apoapsis  on 2009/07/04 (152,085,419 km)

If the average distances at periapsis and apoapsis are used rather than the exact values in 2009 the percent gain and loss shift every so slightly:

+3.2601%  At average distance of periapsis (147,098,074 km)
-3.4277%  At average distance of apoapsis  (152,097,701 km)

This insignificant shift begs the question: is an analytical computation derived from Kepler’s Laws a reasonable approximation of Earth’s heliocentric position when computing incident irradiance? Thanks to the table presented at AstroPixels: Earth at Perihelion and Aphelion this is a simple question to answer. The standard deviations of the distance at periapsis and apoapsis in astronomical units for the years 2001 through 2050 are:

Standard deviation of minimum distance:  0.0000265898 AU
Standard deviation of maximum distance:  0.0000321472 AU

Clearly, a more accurate orbital model is hardly worth considering. Just as Planck’s Law is a reasonable approximation of the Sun’s spectral output Kepler’s Laws are a reasonable approximation of Earth’s position relative to the Sun.

In summary there isn’t a lot rendering applications can gain by parsing and rigorously analyzing data from the SOURCE satellite; by the same token there isn’t much to be gained by creating a detailed numerical model of Earth’s orbit.  An accurate representation of the Sun’s spectral output is achievable with just a few lines of code using Planck’s Law and accounting for the distance between the Earth and the Sun is accomplished just as easily using Kepler’s Laws.  While this simple theoretical model is marginally inferior to real world data it is vastly superior to inventing values and ending up in the tuning nightmare outlined in the previous post that atmospheric scattering simulations are so prone to.


Solar Spectral Irradiance Part 1

Over the years I’ve read a lot about the scattering of light by participating media in the context of rendering, particularly atmospheric scattering as it occurs on Earth.  There are a lot of good sources on the subject but very few of them talk about how to quantify sunlight as it exists in space just before entering the atmosphere.  If values are given at all they are generally arbitrary constants that produce good enough results.  This raises a number of issues:

1) Tuning the parameters to your scattering model can be problematic when you are guessing at how much sunlight to dump into the system.  In the face of less than realistic results you can be left asking yourself:  Is the sunlight too dim / bright or are the scattering coefficients too small / large?  Are the phase functions and scale heights properly calibrated?  Why does it look good at sea level but wrong at 5,000 feet?  A tedious cycle of tuning parameters can ensue.

2) Point sampling (or otherwise quantizing) the Sun’s spectral power distribution at the RGB primaries, running computations on the approximation and then converting to display dependent values is not necessarily the same as crunching the number on the actual spectral distribution, convoluting with CIE color matching curves and then converting to display dependent values.  I’m not sure how much this matters when it comes to the visual quality of the final image but it’s worth investigating and I intend to so.

3) Physically based lighting is all the range these days and outdoor scenes are conveniently lit by a radiance map of incoming skylight generated from an atmospheric scatting simulation.  If your sky looks good then your scattering code is probably outputting values with the proper relative intensity but that doesn’t mean they are the right magnitude.  This can be a problem when you add artificial light sources to the mix as you can’t tell if your sky is too dim / bright or if your lights are too bright / dim.  Another tuning nightmare based mostly on conjecture is likely to ensue.  Compounding issues further is your tone mapper which is completely capable of taking absurdly bright or dim values and correcting them.

With this in mind I recently set out to track down a spectral power distribution of the Sun’s irradiance at a distance of one AU as measured by physical instruments.  A few papers turned up but they all required subscriptions to scientific journals.  The results produced by NASA experiments are public domain and it just so happens that a mission to collect solar irradiance measurements across an impressive range of wavelengths was launched in 2003:

Solar Radiation and Climate Experiment

Since April of 2004 the various instruments on the SORCE satellite have been measuring irradiance from the Sun at wavelengths between 0.1 and 2,400 nanometers.  The visible spectrum is comfortably inside of that at 360 to 830 nanometers and primarily measured by the SIM instrument; you can get that data in text form here:

Solar Radiation and Climate Experiment:  Data

Even though the data is labeled “Level 3” (aka processed) it can’t be used directly for rendering.  The biggest inconvenience is the irregular sampling interval which makes reconstructing the continuous irradiance distribution awkward.  The second hiccup comes in the form of measurement anomalies that must be removed via statistical methods.  Initially I assumed “Level 3” meant anomaly free but a visual scan of the text data suggest otherwise.  Finally, the satellite does not orbit the Sun at a constant one AU, instead it orbits Earth at a distance of 645 kilometer.  This is both good and bad.  The Earth’s orbit is elliptical so the amount of incident irradiance changes with the distance to the Sun.  While the satellite’s spatial configuration necessitates more work to derive usable numbers it creates an easy way to extract seasonal irradiance values; you can simply window the data processing by date.  Earth’s distance to the Sun ranges from 152,098,232 km at apoapsis to 147,098,291 km at periapsis (a difference of 1.76%).  That’s a small change and not likely to matter much but it’s still worth considering.

[EDIT:  It turns out processing the data prior to publication involves deriving measurements as they would have been collected from a distance of 1 AU based on the orbital ephemerides of the spacecraft as reported by onboard telemetry and corroborated by NORAD.  This means windowing the data by date isn’t useful if you want irradiance values as received by Earth on a particular date unless you undo this correction manually.  The tool I’ll post later will have an option to do this.]

In a few days I’ll post a command line tool that will process the SIM data into a convenient form based on a given day of the year and a range of wavelengths.  Plugging the output into your scattering computations should be straight forward.  From there tuning rendering parameters can then be done with the small confidence that your sunlight is properly configured.

Tangent Space Derivation

Every now and then a situation arises when geometry must be generated or at least manipulated with custom code in such a way that the tangent-space coordinate system defined at each vertex must be calculated from scratch.  If you assign such a task to a junior or mid-level programmer it’s likely they won’t have a clue how to do this and will end up doing a copy-paste-refactor job on a piece of code found on the internet.  Down the road someone will notice that the bumps on your cloth or ripples on your water are inverted, rotated or just “wrong” according to some hand-wavy explanation of “weirdness” by the troubled author of a once beautiful normal-map.  Chances are the original piece of code from the internet had some sort of transform implicit in the calculations that corrected an incompatibility between the tangent-space coordinate system and the object-space coordinate system.  Perhaps the handedness changed from left to right or the z-axis became the y-axis and vice-versa or any other subtle yet crucial detail.  If no one knows how tangent-spaces are derived fixing this is a pain and will inevitably lead to some poor soul trying a seemingly endless permutation of transposed matrices, swapped vector components, inverted axis directions and any other easily made mathematical perturbation until the results finally look correct.

To solve this problem like proper professionals we need an intuitive understanding of what tangent-space is.  In words it’s the coordinate system that the normals in your normal map are defined in.  To visualize this imagine a texture with a red arrow extending from the center that points to the left and a similarly located green arrow that points down; now mentally paste this texture onto a triangle in object-space.

Tangent Space Figure 00

If you were to measure the delta between the beginning and end of the red arrow you would get a vector that is parallel to the x-axis of the tangent-space expressed in object-space coordinates (this is called the tangent).  Apply the same method to the green arrow and you end up with a vector that is parallel to the y-axis (this is called the binormal).  The z-axis of the tangent-space is simply the triangle’s outward facing surface normal.  As a short hand we will call the un-normalized version of these vectors i, j, and k respectively.  To build a rotation matrix that transforms directions from tangent-space to object-space simply normalize i, j, and k and drop them into the first, second and third column of a 3×3 matrix.

Now that we have a mental model of what needs to be calculated we can get down to hammering out the mathematics.  Suppose we had the following function:

Tangent Space Figure 01

That takes a point (u, v) in texture-space as input and produces a point (x, y, z) in object-space in such a way that is consistent with the texture mapping of our imaginary triangle; in other words, for any point (u, v) on our texture p(u, v) tells us where in object-space that point is.  Going back to the visual analogy used before we can use this function to measure the delta between the object-space start and end points of the red arrow (corresponding to the tangent vector or i) and the green arrow (corresponding to the binormal vectors or j) on the texture.

Tangent Space Figure 02

Note that our choice for a starting (u, v) is irrelevant since left is always left and down is always down regardless of where we are on the texture.  If you are Calculus savvy Equations 2.1 and 2.2 should look suspiciously similar to the numerical approximations to the partial derivatives of p in the u and v direction; indeed, they are equivalent.

Tangent Space Figure 03

The trick is coming up with the function p(u, v) so that we can compute it’s derivatives, this is actually fairly simple.  Suppose our triangle has the following object-space vertices:

Tangent Space Figure 04

and texture-space vertices (a.k.a. uv’s):

Tangent Space Figure 05

We can parameterize object-space and texture-space points on the triangle with the following vector equations:

Tangent Space Figure 06

Where (s, t) pairs that sum to a value on [0, 1] produce points on the triangle in texture-space or object-space.  We want to find the partial derivatives of x, y and z with respect to u and v.  To do this we need to be able to write x, y and z as a function of u and v, not s and t as we did in Equation 4.2.  Equation 4.1 maps pairs of s and t to pairs of u and v so we start by inverting it such that we can do the mapping in reverse.

Tangent Space Figure 07

Now we can rewrite Equation 4.2 in terms of u and v.

Tangent Space Figure 08

Alas our arbitrary (s, t) parameters go away and we are left with a function that maps texture coordinates to object-space.  Finding the tangent-space basis vectors i and j is a simple matter of expanding Equation 6.0 and evaluating the partial derivatives.  Obviously this gets quite cumbersome given the mess of subscripts and subtractions.  To clean things up we’ll adopt the following equalities:

Tangent Space Figure 09

Substituting into Equation 6.0 yields:

Tangent Space Figure 10

And differentiating both sides with respect to u and v leaves us with:

Tangent Space Figure 11

There you have it, i and j as a function of texture-space and object-space edge vectors.

Tangent Space Figure 12

Just for fun here’s some c++ code you can attempt to copy and paste into your own project. Is it bug free? Perhaps.  I can assure you that it is not caveat free.

struct Vertex
    Vector3 vPos;      // object-space position
    Vector2 vTex;      // texture-space position
    Vector3 vTangent;  // Tangent space x-axis (left on the texture)
    Vector3 vBinormal; // Tangent space y-axis (down on the texture)
    Vector3 vNormal;   // Tangent space z-axis (out  of the texture)

    void SumBasis(const Vector3& a_vAxisI,
                  const Vector3& a_vAxisJ,
                  const Vector3& a_vAxisK)
        vTangent  += a_vAxisI;
        vBinormal += a_vAxisJ;
        vNormal   += a_vAxisK;

    void NormalizeBasis(void)

    void ZeroBasis(void)
        vTangent  = Vector3::vZeroVector;
        vBinormal = Vector3::vZeroVector;
        vNormal   = Vector3::vZeroVector;

Matrix2x2 CalcTangentMatrix(Vector2& a_vTexA,
                            Vector2& a_vTexB,
                            Vector2& a_vTexC)
    Matrix2x2 mtx;

    mtx.e11 = a_vTexB.x - a_vTexA.x;
    mtx.e12 = a_vTexC.x - a_vTexA.x;
    mtx.e21 = a_vTexB.y - a_vTexA.y;
    mtx.e22 = a_vTexC.y - a_vTexA.y;


    return mtx;

void SumTangentSpace(Vertex& a_kVertexA,
                     Vertex& a_kVertexB,
                     Vertex& a_kVertexC)
    // Compute object space edge vectors
    Vector3 vEdgeAB = a_kVertexB.vPos - a_kVertexA.vPos;
    Vector3 vEdgeAC = a_kVertexC.vPos - a_kVertexA.vPos;

    // Compute the triangle's normal vector and area
    Vector3 vNormal = Vector3::CrossProduct(vEdgeAB, vEdgeAC);
    float32 fArea2x = vNormal.Magnitude();

    // Compute the tangent matrix
    Matrix2x2 mtxTex = CalcTangentMatrix(a_kVertexA.vTex,

    // Compute tangent-space basis vectors
    Vector3 vAxisI = vEdgeAB * mtxTex.e11 + vEdgeAC * mtxTex.e12;
    Vector3 vAxisJ = vEdgeAB * mtxTex.e21 + vEdgeAB * mtxTex.e22;

    // Normalize and weigh each vector by the area of the triangle
    vAxisI = Vector3::Normalize(vAxisI) * fArea2x;
    vAxisJ = Vector3::Normalize(vAxisJ) * fArea2x;

    // Accumulate the tangent space basis vector at each vertex
    a_kVertexA.SumBasis(vAxisI, vAxisJ, vNormal);
    a_kVertexB.SumBasis(vAxisI, vAxisJ, vNormal);
    a_kVertexC.SumBasis(vAxisI, vAxisJ, vNormal);

void CalcTangentSpace(const int32* a_pIndexList,  int32 a_nNumIndices,
                      Vertex*      a_pVertexList, int32 a_nNumVertices)
    for(int32 i = 0; i < a_nNumVertices; i++)

    for(int32 i = 0; i < a_nNumIndices; i+=3)
        int32 nIndexA = a_pIndexList[i];
        int32 nIndexB = a_pIndexList[i+1];
        int32 nIndexC = a_pIndexList[i+2];


    for(int32 i = 0; i < a_nNumVertices; i++)


The Trouble with Interviews

Lately I’ve been submitting myself to a lot of interviews.  About half of them have featured questions posed by people seemingly unprepared to evaluate answers that deviated from a very specific, expected response.  This might not sound like a big deal; if you are wrong you are wrong, end of story.  Unfortunately it’s not that simple, some answers are more correct than others.  Here’s a paraphrased exchange to demonstrate:

Them:  How would you manipulate an object-space to world-space matrix such that it transforms from world-space to object-space?

Me:  Rotation and translation only?

Them:  Yes.

Me:  Transpose the upper-left 3×3 sub-matrix and set the translational column of the matrix to a new vector where the x component is the object space x-axis dotted with the negative of the translation, the y component is the object space y-axis dotted with the negative translation and z component is the object space z-axis dotted with the negative translation.

Them:  You are incorrect.

Me:  It’s equivalent to taking the inverse of the matrix but faster as it only requires six swapping operations and 3 dot products.  The optimization is possible by exploiting the properties of the matrix: namely the rotational component contains mutually perpendicular, unit length vectors.

Them:  You should always just take the inverse, it’s easier.

Perhaps I over thought this question.  Of course you can simply take the inverse but every graphics programmer knows that; it’s not even worth asking.  It’s frustrating that a more knowledgeable answer was dismissed as uninformed or some type of ugly hack.

Here’s another, similar exchange with a different studio:

Them:  Given a 3×4 transformation matrix that contains rotations and translations only how do you compute the inverse?

Me:  [same answer as before]

Them:  That is incorrect.  You simply negate the translational component and invert the rotational component by taking the transpose as you described.

Me:  But you must do the reverse in the opposite order which can only be encoded in standard matrix form by projecting the negative translation onto the original local-space basis vectors.  Negating the individual operations in isolation doesn’t work, they are not separable.

Them:  No.  Transformation matrices rotate and then translate points so it follows you can reverse a transformation by doing the opposite translation and rotation.

I suppose they wanted to know if I understood that a transformation matrix can conceptually be thought of as a rotation followed by a translation.  That particular bit of knowledge is not something that can be easily evaluated, it is purely conceptual and may not be the mental model the interviewee defaults to when envisioning the operation especially when dealing with someone who has an academic background in mathematics.  Furthermore, you can’t accurately evaluate such intuition if you are not prepared to recognize how that intuition can be embedded in a correct answer to a reasonable interpretation of the question.

I’ll stop with the transformation matrix questions even though I have two more almost identical examples.  Here’s another exchange with a different studio involving data-structures:

Them:  Are you familiar with Big-O notation?

Me:  Yes

Them:  What type of data structure would you use if you needed to insert and access objects by key in O(1) time.

Me:  That’s not possible, the best you can do is O(log n).  Typically this is accomplished with a self-balancing binary tree such as a red-black tree or something similar.

They then proceeded to ask me a bunch of vague questions about when and how binary trees turn into link-lists with linear access times.  As it turns out the answer they were looking for was “hash table” and they found it alarming that I mentioned a binary tree.  Alas, inserting and removing into a binary search tree is no better than a link-list when it becomes unbalanced but this is irrelevant as I specifically mentioned a self-balancing tree.  Moreover this is an unfair point to make since the question indicated worst case time complexity and a hash-table has the same problem which occurs when every object gets hashed to the same bucket and you end up with a single list (or tree) of all objects.

The confusion started with the previous question about big-o notation.  I justifiably assumed we were talking about what is possible in theory not what is practical in implementation.  It would have been better to drop the big-o phrasing and simply ask what type of container I would use if the insertion and access of objects by key needed to be as fast as possible.  In this case the person who asked the question seemed to have disregarded the fact that big-o notation refers to the worst case when considering the desired answer and then suddenly remembered and incorrectly applied it when judging my technically correct answer.

Another hiccup of the interview process I have found to be frustrating is the haphazard handling of radiometric terms such as using irradiance and radiance interchangeably or swapping the definition of intensity with the definition of irradiance.  This kind of nonsense needs to stop.  The industry has officially entered the age of physically based reflection models and global illumination.  Even if your game is stylized it can reap enormous benefits from a mathematically careful treatment of the rendering pipeline.  These things matter, we can no longer get away with a sloppy and cavalier attitude towards the physics and mathematics involved.  Formulate your question accordingly.  If a candidate claims your question is mathematically nonsensical…they might actually be right.

Projection transformations and clip-spaces are hazardous areas as well.  I’ve been asked numerous questions about these topics only to be told I am confused about the issue because my projection matrix or clipping algorithm isn’t consistent with DirectX, OpenGL, the PS3 etc.  The problem here is it’s difficult to talk about these things in a general way: the handedness of the coordinate system, configuration of the clip-space, memory layout of the projection matrix w.r.t. the hardware instructions available all matter.

If you find yourself giving an interview consider the following:

  1. Select your words carefully and use proper phrasing.  If you are looking for a laser specific answer ask a laser specific question and specify the exact scenario, API, platform etc. you have in mind.
  2. Be prepared to evaluate the candidate’s understanding of the topic; not whether or not they give the exact answer you expect.  Everyone’s brain works differently and no one will interpret your question exactly as you would.
  3. Prior to the interview brush up on the topics you intend to cover.  This will assist in your evaluation should the candidate approach the question from a correct but unexpected angle or demonstrate knowledge you are not aware of and may interpret is incorrect and/or unrelated.
  4. Clearly indicate when theoretical concerns are being discussed vs. practical properties.

In my experience interviews that are “tough but fair” are the most fun and rewarding even when an offer is not extended.  Flying across the country or driving 3 hours to engage in an uneven and seemingly random evaluation of my competency isn’t fun and I’m unlikely to accept an offer from such a place as its ability to consistently fill roles with the required talent is doubtful.

Intro to Cubic Splines

Splines are ubiquitous in computer graphics; they can be found in all but the most limited graphics libraries, masquerading under countless names and taking on an equally vast range of forms.  At the kernel of most implementation is a third order polynomial:

Generally, the name applied to an implementation indicates the way in which the vector coefficients { a, b, c, d } are calculated.  Resources on specific implementations are abundant; rather than dictating the recipes for various types this post is intended provide a fundamental understanding that can be used to derive your own types.

The formulation of v(t) as a third order polynomial necessitates the production of four constraints in order to uniquely define the four coefficients.  There is a great deal of freedom in the way the constraints can be chosen.  A common choice is a set of four control points { v0, v1, v2, v3 } that the spline must pass through at the parametric values of t ∊ { 0,  1/3,  2/3,  1 }.

Plugging t ∊ {0, 1/3, 2/3, 1} into v(t) and expanding produces a set of four linear equations:

The same expansion can be neatly collapsed into a single linear equation:

The 4×4 matrix on the left will be referred to as the parameter matrix as its formulation is a function of the parametric values of t for which the constraints apply.  Note that while the parameter matrix is an array of scalars the elements within the two column vectors are actually vectors themselves; this notation is chosen for the sake of convenience and is meant to imply:

Where i indexes the individual elements of each vector.  Computing the coefficients  { a, b, c, d } is a simple matter of multiplying the inverse of the parameter matrix with the column of control points { v0, v1, v2, v3 } and simplifying the results.  Doing so produces the following:

The result of plotting v(t) with the choice of control points { (1, 4)  (15, 4)  (10, 8)  (6, 1) } is shown in Figure 1.

An equally common scheme is to choose two control points and two tangent vectors, one at each position, that determine the magnitude and direction of the spline’s first order derivative.  The first order derivative of v(t) with respect to t takes the form:

Let the choice of constraints { v0, v1, t0, t1 } be applied to the spline at t ∊ {0, 1} where { v0, v1} are the positional constraints and { t0, t1} are the tangential constraints.

Plugging t ∊ {0, 1} into v(t) and v(t) and expanding produces a set of four linear equations:

Just as before, the same expansion can be neatly collapsed into a single linear equation:

The result of plotting v(t) with the choice of control points { (2, 6)  (14, 5) } and tangent vectors { (25, 25)  (0, 35) } is shown in Figure 2 (the tangent vectors have been scaled down by a factor of 10).

Other spline configurations follow the same pattern of (1) selecting constraints and (2) solving the resulting system of equations such that the spline coefficients can be written as an explicit function of the control data.  Occasionally the interval chosen for the parametric value t is something other than [0, 1] such as: [-1, 1], [-1, 2], [0, 3], etc.  Changing the bounding interval of t alters the parameter matrix and thus invalidates the computation of the coefficients { a, b, c, d } as a static function of the control data.  Flexible implementations cope with variable parameter-intervals by requiring the user to specify where on the spline the control data is applied.  The parameter matrix can then be assembled dynamically and inverted on the fly to compute the spline coefficients.  The overhead incurred by this flexibility can be avoided in most cases by detecting common interval choices and defaulting to a set of previously computed and inverted parameter matrices whenever possible.

Volume Calculations

While building a physics engine the problem of determining the volume enclosed by a collision hull (or some other surface bound topology) is likely to present itself.  A simple volume determination can be carried out by dividing the space around a volume into a regular grid and summing up the volume of all the voxels enclosed by the bounding surface; while straight forward to implement this is extraordinarily slow due to the number of containment tests involved.  Collision hulls are defined by an explicit description of their bounding surface, usually in the form of a mesh tessellated by a set of n sided polygons.  With this in mind we would like to relate the volume of a collision hull to an explicit calculation on the surface of the hull.  This leads us to the Divergence Theorem:

Roughly stated (with apologies to mathematicians for the sloppy wording) the Divergence Theorem tells us that the divergence of the vector field F within the closed volume V is equal to the flux of F through the boundary of V where the boundary of V is given as the closed, oriented, 2d surface S.  The so called orientation of S comes from the unit length vector n which consistently points “outside” of V and is well defined for every point on S.  Note that the left hand side of the theorem looks very similar to the triple integral you would use to directly calculate the volume of V.

If we choose F as the vector field (x, 0, 0) then the divergence of F is trivially computed as 1.

Which of course collapses the internals of the integral on the LHS of the Divergence Theorem into a simple unit integration through the volume of V.

The Divergence Theorem can then be used to relate the volume of V to the divergence of F through S.

We now have the volume-to-surface relationship needed for the efficient calculation of the volume enclosed by a collision hull.  Assuming a straight forward mesh representation the volume of a collision hull can be computed as the piece wise summation of the flux of F = (x, 0, 0) through each polygon in the mesh.

Calculating the flux of F through Si requires integrating a vector field across area Si and therefore a 2 dimension parameterization of Si.  For the sake of simplicity we restrict ourselves to the decomposition of S into n triangular regions described by a set of counter-clock-wise wound vector triplets.

In other words, S is a triangulated mesh.  A straight forward parameterization of triangle Si is given by the parametric equation Ti.

Under this parameterization the outward facing differential area dAi is computed as:

The flux of F through triangle Ti can now be written as an explicit 2d integral.

The symbolic evaluation of the double integral is tedious and mundane and in the interest of space has been omitted; the final result follows.

Finally, the total volume of V can be expressed as:

For the mathematically adverse a basic C++ implementation should look something like this:

 float32 CalculateVolume(const Vector3* a_pVerts,
                         const int32*   a_pIndices,
                         const int32    a_nNumTris)
    float32 fVolume = 0.0f;

    for(int32 i = 0; i < a_nNumTris; i++)
        Vector3 v1 = a_pVerts[a_pIndices[3*i  ]];
        Vector3 v2 = a_pVerts[a_pIndices[3*i+1]];
        Vector3 v3 = a_pVerts[a_pIndices[3*i+2]];

        fVolume += (v1.x+v2.x+v3.x)*((v2.y-v1.y)*(v3.z-v1.z)-

    return fVolume / 6.0f;