3D Rendering History

[dynafx]

I'm presenting an amazing article about rendering history from cgnetworks



CGNetworks Feature :: 3D Rendering History

Part 1: Humble Beginnings


By: Dmitry Shklyar



Introduction

3D
rendering technology has managed to find its way into the lives of
millions of people worldwide. Be it a gaming console connected to a
television, animation software on a workstation or the latest special
effects blockbuster at the movies, we use and experience 3D rendering
and harness its power without giving any thought about the marvelous
technology behind it. In part one of this feature series, CGNetworks
takes a look at the history of 3D rendering, from the first line
algorithm to current technologies, we pay tribute to the scientists who
made rendering possible. So next time you hit the render button for
your latest blockbuster creation, think about what happens behind the
scenes with the histories and developments that push the boundaries of
current rendering technology.






From Aircraft to Lines


In 1960, designer William Fetter was attempting to devise a new process
in order to maximize the efficiency of the layout inside Boeing's
airplane cockpits. His final product was a computer generated
orthographic view of the human form. Fetter devised the term 'computer
graphics' to describe his creation, starting a chain of events that
would eventually revolutionize the world of entertainment, advertising
and media. One of Fetter's contemporaries, Ivan Sutherland set things
in motion in 1963 when he submitted his PhD. thesis, entitled Sketchpad: A Man-machine Graphical Communications System.
The software enabled a person, for the very first time, to
interactively create an image on a computer display. According to Sun
Microsystems, where Sutherland currently resides as vice president,
?sketchpad pioneered the concepts of graphical computing, including
memory structures to store objects, rubber-banding of lines, the
ability to zoom in and out on the display and the ability to make
perfect lines, corners,
and joints. This was the first GUI (Graphical User Interface) long
before the term was coined? [1].

Computer Graphics in the 1960's - William Fetter.

Ivan Sutherland with Sketchpad.



Upon receiving his PhD, Sutherland
was inducted into the US army who at the time were the largest
innovators in computer technology. More relevant to the field of
computer graphics though, was Sutherland's stay at the University of
Utah where he helped transform its budding computer science department
into a research institution, which bears significant influence on
today's graphics industry.




The very first
three-dimensional images were extremely rudimentary by today's
standards and consisted of wire frame representations of various
geometric shapes. This was acceptable though one could see what was in
front and behind the shape. It took Sutherland?s colleagues Evans,
Wylie, Romney, and Erdahl to develop the Scan line HSR (Hidden Surface
Removal) algorithm to create renders of solid objects. Many hidden
surface removal algorithms were presented over the years which include
back-face detection, depth sorting, ray casting, Z-Buffer and area
subdivision algorithms. Ivan Sutherland and his colleagues later
published a paper entitled The Characterization of Ten Hidden-Surface Algorithms,
which covered the algorithms known at the time. Incidentally, this
would be Sutherland?s last direct contribution to computer graphics
research. Today, various scan line algorithms are still used throughout
many production facilities.





Shading: Gouraud and Phong


On the road to realism, the next issue for developers was how to
increase the apparent complexity of a scene without increasing the
amounts of geometry, therefore conserving precious system memory. In
the earliest rendering systems, the only way to increase the apparent
complexity of a mesh was to add more polygons. This smooth effect would
be lost if the camera zoomed in on the model due to the fact that the
only shading model available to early renderers was the flat shading
model, also known as faceted. This shading model would find the vector,
which was normal in relation to a face and use that information to
shade all of the pixels.





This all changed when Henry Gouraud developed his now famous, widely
utilized, and aptly named, Gouraud shading model. Gouraud works by
finding the normal vector pertaining to each vertex of a face,
calculating the pixel color at the vertex and then linearly
interpolating that color across the face. The result is a fairly smooth
surface that takes only a modestly larger amount of processing power
than the flat shading model. The only aesthetically displeasing aspects
of Gouraud are the edges that still appear faceted, as well as the fact
that the surface displays a star shaped highlight due to the linear
nature of the interpolation.





A researcher by the name of Phong Bui-Tuong expanded on Henry Gouraud's
shading model by taking the next logical step. Instead of finding the
normal vectors at just the vertices, the Phong shader calculates a
normal at each pixel. By interpolating across the surface based on the
normals, Phong results in an extremely smooth surface with accurate
highlights the main drawback that Phong is notoriously slow. If one
compares the Phong model against Gouraud model on two identical pieces
of geometry, one will see that it takes up to eight times as long to
render the model shaded using Phong [2].

Kraftwerk

CG Gets Bumpy


As research into various methods of shading continued, Jim Blinn
discovered that by disturbing surface normals, one could simulate the
appearance of an increased amount of surface geometry. This technique
became known as bump mapping and is still generously used in
applications ranging from real time games to feature length movies.
Bump mapping is generally implemented by using a black and white bitmap
or procedural texture in order to define which pixel will have a
perturbed normal. This can achieve the illusion of some very complex
geometry, though a drawback of utilizing this technique is there is no
increase of geometry along the edge of the surface. Bump mapping was
later extended and a technique by the name of displacement mapping was
born. This technique is similar to bump mapping except the actual
pixel, as well as the normal are transformed. This remedied the problem
of the disappearance of surface detail along edges, but also led to a
severe increase in processor and memory load.





Recently, the idea of modifying surface normals at the pixel level has
been extended even further. The technique of normal mapping was
introduced in order to deal with the relatively low amount of bandwidth
present in current consumer level graphics hardware, where they were
not fast enough to deal with the large-scale models associated with
?movie quality? graphics. A solution was found in creating a data
structure, which can capture the normal information of a highly
detailed model and then apply it to a scaled down version. The effect
is similar to that of bump mapping, in that the surface geometry is not
altered, yet the illusion of a complex model is achieved. Upcoming
games such as Id Software's Doom 3, Valve Software's Half-Life 2 and
Bungie's Halo 2 make extensive use of this technique in order to
produce their breath taking imagery in real time.





Conclusion


All of the mentioned breakthroughs of the 1960's, 70's, and 80's in
rendering and shading technology, as well as some of the more recent
advances, have lead to some interesting trends. The problem of how to
shade a surface took precedent over the early problem of finding and
removing hidden surfaces. More recently, graphics cards vendors have
stopped emphasizing the amount of geometry their display cards can
handle but rather place their shading abilities into the spotlight,
offering more creative control into the hands of developers of real
time content. As these trends continue, the lines between cinematic
graphics and real time applications will be blurred. This is quite the
contrast from the early days of computer graphics when pioneers such as
Ivan Sutherland performed their research on machines that cost upwards
of one million dollars. Due to the contributions of these pioneers,
today computer graphics saturate many aspects of our lives. From art,
science, technology and design to the entertaining CG movies
which make us laugh, cringe and cry, we owe it all to the pioneers of
rendering technology.

Works cited [1] Sketchpad: The First Interactive Computer Graphics PhD. Thesis, 1963 -- Mass. Institute of Technology. Sun Microsystems. Date Accessed:9/06/03.http://www.sun.com/960710/feature3/sk etchpad.html [2] Hill Jr., F.S. Computer Graphics Using OpenGL Second Edition. Prentice Hall Publishing. 2001.

Bump and Displace.

Jim Blinn gets juicy.

Current Rendering Technologies in Bungie's Halo 2.

[dynafx]

Part 2: To Photorealism and Beyond.

Introduction


With our first installment of 3D Rendering History,
CGNetworks delivered a glimpse into the industries rendering past to
gain some insight to where the actual technologies derived from. The
second installment, To Photorealism and Beyond, delves even
deeper to where rendering technologies currently sit, what they offer
and where it may lead to in the coming years.




Since
the 1960's, obtaining renders which were indistinguishable from
photographs has been a much sought after goal, the Holy Grail of 3D if
you will. Over the years, many difficulties have arisen to achieve
photorealism, which leads us to one of the larger issues in current CG
technology, global illumination. Global illumination (GI) refers to any
physical based simulation of light being scattered in an artificial
environment.





The search for Global Illumination


To clarify, GI is not an algorithm, instead, it is an effect achieved
by many. The first algorithm, devised to tackle this problem was ray
tracing. Yes, you read it correctly, ray tracing was initially thought
of as a method to calculate GI. The very first computer based
implementation of ray tracing was performed at IBM in 1968 by a
researcher named Appel where he published a paper entitled Some Techniques for Shading Machine Renderings of Solids. Being that it was 1968, computers were nowhere near being capable of practically utilizing this algorithm.





It wasn't until 1980 when Turner Whitted published his groundbreaking paper entitled An Improved Illumination Model for Shaded Display.
Whitted's paper described a ray tracing algorithm which facilitated for
shadows, reflections, and refractions. Whitted's method was so simple
that it could be described in as few as 3 functions, comprising of
about a dozen lines of pseudo code [2]. Because of these reasons, most
of today's commercial rendering packages are based on Turner Whitted's
research [1].




Ray Tracing


Ray tracing works by shooting a ray from the viewer's eye into the
scene, where it either leaves that scene or hits another object. If a
ray meets an object, it then sends a secondary ray in the direction of
the surface normal, until it either hits another surface, in which case
the object is in shadow, or until it hits a light. If a surface is
transparent, a ray is transmitted through that object in a direction
which is determined in part of that object's index of refraction.







ray tracing

Despite all of ray tracing's
benefits, it is still far from flawless. One problem associated with
ray tracing, and computer graphics in general, is aliasing. This is due
to the fact ray tracing samples a scene at regularly spaced intervals
and ignores everything in between.





Stochastic Sampling


Robert L. Cook, who helped author the now widely popular Renderman
standard [5], sought to solve this problem, and published his findings
in a 1986 paper called Stochastic Sampling in Computer Graphics.
Cook's stochastic sampling method works by randomly sampling the areas
in between pixels. By using this method, the extremely jarring effect
of aliasing is reduced to noise, which is easily tolerated by the human
eye.




This noise, besides being a replacement for
unsightly aliasing, can also be used to great effect in simulating
various so called ?fuzzy phenomena? [1]. For example, stochastic
sampling can be used to accurately simulate a blurry reflection by
jittering the secondary rays.





Many scan-line based renderers, such as Pixar's PRMan, have taken full
advantage of Cook's work. Stochastic sampling can be used to address
these phenomena where the renderer calculates what is called the
?circle of confusion? [1], and then jitters the appropriate rays which
pertain to this circle in order to create the blurred effect.
Stochastic sampling also deals with motion blur in a very intuitive way
where not only are rays distributed across a single frame, but also
over time.





Despite adding a whole new repertoire of effects, stochastic sampling
does not fix ray tracing's most glaring drawback as a solution to GI.
Ray tracing only solves part of the problem, in that it only simulates
direct illumination. A method of simulating diffuse reflections was
necessary to complete the GI solution, this being radiosity.





Radiosity


With their 1984 paper, Modeling the Interaction of Light Between Diffuse Surfaces,
Cindy M. Goral , Kenneth E. Torrance , Donald P. Greenberg , and
Bennett Battaile introduced the second algorithm of the decade to
revolutionize the field of computer graphics. Radiosity handles a scene
by splitting up geometry into a series of sub patches. It then uses
linear equations to calculate how illumination travels from a light
source and across these patches. Radiosity though, just like ray
tracing, only solved part of the GI equation and did not account for
effects like specular and mirror reflections and transmission.





Since ray tracing was already successful at these tasks, the next
logical step for researchers was to combine both algorithms, as well as
carry over all of the benefits of stochastic sampling. The end result
was a fairly robust method in creating photo-realistic scenes. Some
commercial rendering packages still utilize this hybrid, such as
Lightwave 3D.





Radiosity
is not without its drawbacks though. The simple fact that radiosity
needs to subdivide the scene into sub patches creates a huge strain on
system resources. Radiosity's close coupling with geometry also creates
other problems, for instance, visible artifacts, calculating sharp
changes in illumination and obtuse looking shadows.





Photon mapping

In the mid 1990's, a researcher by the name of Henrik Wann Jensen
created a solution to these inconveniences. During his PhD studies in
1994 at the Technical University of Denmark, Jensen invented the
algorithm known as photon mapping. His findings were officially
published in 1996 with his paper Global Illumination Using Photon Maps.

Mirror reflection

Blurry reflection

Incorrect radiosity shadows

Photon mapped spheres

Jensen's algorithm worked in two passes, the first pass would emit a user specified amount of photons into the scene. These photons would bounce for a specified amount of time, or leave the scene completely. Each time a photon bounces it loses intensity, as well as picks up some color from other surfaces. These bounces would then be stored in a data structure called the photon map. The second pass would basically sample each pixel in the scene, like a ray tracer, and calculate how much each photon hit contributed to that pixel's color and illumination. Once again, all of the benefits of ray tracing could be implemented, such as stochastic sampling. On top of eliminating virtually every drawback of using a hybrid radiosity and ray tracing solution, photon mapping brings along a few more welcome surprises. Due to photon mapping's particle nature, it becomes an extremely capable method for simulating new and exciting effects. These include caustics, where photons are focused through a volume and are transmitted through the other side, as well as sub surface scattering which allows for the accurate modeling of translucent surfaces, such as illuminated candle wax, human skin, etc. Doing it in Real Time For the last few years, gaming has been the dominant force in pushing the advancement of computer technology. Multimedia design and scientific simulations occupy a relatively small niche of the market compared to gamers, but this is not to say that they do not benefit from these advances. This relationship is indirectly reciprocated when advanced graphics techniques work their way into the game production pipeline. Techniques such as radiosity and photon mapping have been implemented in recent years to help enhance photorealism in the gaming environment. A few years ago, dedicated graphics hardware solely excelled at drawing triangles with filled textures. The last few releases from Nvidia and ATI brought something completely different to the table, as it is now possible to execute custom shaders on graphics hardware. The next step in bringing GI algorithms into the realm of real time interaction was to implement Jensen's photon map. Although these advances are quite astounding, end users still have a few years to wait before playing a photon mapped version of Quake in real time. Saving Faces One requirement for a scene to have any semblance of photorealism is the appearance of all objects within a scene exhibiting influence over each other. Reflections, refractions, as well as shadows, can all be convincingly and cheaply simulated even in real time, though diffuse reflections present a problem. A new technique, called image based lighting, aims to remedy this. Instead of performing many costly computations, image based lighting attempts to store lighting information in an image file. This high precision image not only stores color information at each pixel, but also a radiance value. This radiance value is then used to test how each pixel contributes to a scene's diffuse lighting distribution. Conclusion Even though photon mapping is currently state of the art in terms of rendering algorithms, there are still certain phenomena which it does not account. These phenomena, such as diffraction, interference, and polarization still can not be accurately simulated. It is because of this, that researchers still devote themselves to finding new, exciting and more efficient ways to represent a 3D scene on a 2D monitor. Recommended Readings Henrik Wann Jensen's website An Introduction to Ray Tracing - Andrew S. Glassner Radiosity and Global Illumination - Francois X. Sillion, Claude Puech Realistic Image Synthesis Using Photon Mapping - Henrik Wann Jensen Works cited [1] Glassner, Andrew S. An Introduction to Ray Tracing. MORGAN KAUFMANN. 1989. [2] Jesen, Henrik Wann. Realistic Image Synthesis Using Photon Mapping. A K Peters. 2001 [3] Buck, Ian; Hanrahan, Pat; Mark, William R. Purcell, Timothy J; Ray Tracing on Programmable Graphics Hardware. 2001 [4] Cammarano, Mike; Donner, Craig; Hanrahan, Pat; Jensen, Henrik Wann; Purcell, Timothy J; Photon Mapping on Programmable Graphics Hardware. 2003 [5] http://www.acm.org/awards/fellows_citations/cook.html

Photon mapped cornell box Volume caustics