Modelling Multiple Light Sources
–
Realistically Rendering Multiple
Lights
with Variable Intensities.
Submitted in partial
fulfillment of the requirements for the Bachelor of Science (Honours) degree of
Rhodes University.
Melissa
Ridderhof
November
2002
To
my supervisor, Shaun Bangay, for showing me very simple solutions to very
complex problems.
To
my boyfriend Ivan, for providing support, for solving my Linux problems and for
pointing out bugs in my code.
To
Grant Miller, for listening to me complain, and for extensive advice and proof
reading of my writeup.
Lighting
is a significant factor in rendering a realistic 3D scene to a 2D screen.
Standard techniques for lighting, however, restrict the number of lights
available to eight, which is sufficient for most situations. In some cases,
however, a scene will require more lights to be rendered correctly.
In
this paper, we explore the techniques used for lighting a scene, and the
solutions proposed for handling multiple light sources. We restrict our
solutions to providing the correct intensity of light, shading and shadowing.
We implement a standard solution, virtualised light sources (VLS), and an
applicationcomputing solution based on a Binary Space Partition Trees (BSP).
The
VLS system is relatively simple to implement and provides the expected results
– correct intensity and shading but low quality shadows, with short startup
times and reasonable frame rates. The BSP system is more complicated and cannot
cope with very complex scenes. It provides excellent shadowing as well as the
correct intensity and shading. The start up times are far longer, but the frame
rate is comparable.
Multiple
lighting can be handled in a variety of ways, with different tradeoffs. The
optimal solution would be application specific.
2 Chapter 2: Rendering a
Threedimensional Scene
2.1 The Mathematics of 3D
Objects
2.1.2.1 Intersection of Two Lines
2.1.3.1 Position of Point to Plane
2.1.3.3 Intersection of Line and Plane
2.1.4.2 Angle between Ray and Cone Edge
2.2 Hidden Surface Removal
Techniques
2.2.5 Area Subdivision Algorithms
2.5 Shadow Generation
Techniques
2.5.2 Modified Hidden Surface Removal
3 Chapter 3: Designing
for Multiple Light Sources
3.2 Possible Multiple
Light Solutions
3.2.1 ApplicationComputing Lighting
3.2.3 Virtualised Light Sources
3.4 Design Elements Common
to both Systems
4 Chapter 4: Virtualised
Light System
4.3 Adapting to Handle
Variable Intensities
5.3 Adapting to Handle
Variable Intensities
5.5.1 Converting Light BSP Trees into PolygonLists
5.5.3 Not Calculating below an Intensity
7.2 Multiple Light Source
Solutions
7.3 Comparison of Systems
Implemented
Figure 2‑1
Intersection of Two Lines
Figure 2‑2
Intersection of Line and Plane
Figure 3‑1
OneVertex Class Diagram
Figure 3‑2
Triangle Class Diagram
Figure 3‑3
Colour Class Diagram
Figure 3‑4
LightDescription Class Diagram
Figure 3‑5
Subdividing Polygons
Figure 3‑6
Generic Class Structure
Figure 4‑1
Jordan Curve Theorem
Figure 4‑2
VLS Class Structure
Figure 5‑1
BSP Class Structure
Figure 6‑3
VLS Without Shadows
Figure 6‑5
BSP Without Shadows
Figure 6‑8
BSP Intersecting Polygons
Figure 6‑9
BSP MultiColoured Polygons
Computer
graphics has come a long way from pingpong and logo. Now we have immersive
threedimensional games, hyperreal teapots, and fulllength computer animated
movies. The drive in computer graphics has always been for better quality
graphics at greater speeds. Pacman was perfectly adequate a few frames a
second, but connoisseurs of 3D games such as quake or unreal tournament are
now unsatisfied with refresh rates of 60 frames. We are fast approaching a
requirement for accuracy and speeds beyond the threshold of human perception.
Hardware has taken great leaps forward to support this demand, moving much of
the processing to the graphics card. Hardware acceleration is a prerequisite
for many recent games. In fact, 3D chips frequently use these 3D games as
benchmarks. Alongside the improvement of hardware, extensive research has been
performed in developing and improving algorithms to render graphics.
One
of the prevalent tendencies has been to remove the responsibility of
calculation from the programmer to the package, and then from the package to
the hardware. This simplifies application development, and more importantly,
speeds up run times. But hardware cannot support infinite operations and some
ruleofthumb restrictions have developed. One of these is that cards are only
required to support eight lights. Graphic APIs such as OpenGL echo this
restriction in the interest of maintaining high speeds. There is nothing
stopping a manufacturer from supporting more than eight lights, but this may
well be a wasted resource – in the vast majority of cases, far fewer lights
than that are needed. Clusters of lights – multiple bulbs in one fitting – can
generally be approximated as a single light source with no loss of quality. In
addition, brighter lights tend to drown out the effects of others nearby, and
these secondary lights can often be safely ignored.
However
there are cases where more than eight lights are genuinely needed. For
instance, in a theatre we have as many as a hundred lights in a limited space
and with comparable intensities, all of them with a significant effect on an
object. Using this scenario as motivation, this project investigates methods of
rendering scenes with multiple light sources. OpenGL, a popular graphics API,
had been used throughout. We compare the results from the standard virtualised
light source technique (explained in detail below) with those from a system
that takes the effect of all lights into account. The scenario is limited to a
static scene, but is required to cope with user manipulated changing
intensities of lights. Both systems are investigated with regard to the
accuracy of the shading and shadowing, the start up time and the frame rate.
Chapter 2
introduces the basic theory of rendering threedimensional scenes. We investigate some of the mathematics used
in threedimensional scenes. We then explore the options available for
manipulating and lighting objects in three dimensions and rendering them to a
twodimensional screen, with specific focus on the techniques used in the two
systems.
Chapter 3
discusses various solutions for multiple light source scenarios. We determine
various design considerations, and explore the design of aspects that are
common to both systems.
Chapter 4
explores the specific design and implementation of a standard technique –
virtualised light sources.
Chapter 5 explores
the specific design and implementation of the new system developed using BSP
Trees.
Chapter 6 presents
the output of the two systems. We examine the intensity of light and shading
produced and the quality of the shadowing. We compare the time taken in each
case, and have a look at a few scenes produced by the BSP scene.
Chapter 7 draws
some conclusions about systems with multiple light sources, and indicates areas
for further study.
Any
threedimensional scene must be rendered to the screen in such a way that the
user will find it satisfyingly true to life.
This involves various conceptual steps. Firstly, we consider what exists
in a scene. Objects have to be placed in their correct positions with the
correct dimensions. Secondly, we consider what we see of a scene. The further
surfaces that are obscured by the closer surfaces need to be removed from the
view plane – a process known as hidden surface removal. Lastly we consider how
we see it. This is the process this project focuses on – the scene needs to be
lit.
Lighting
plays a very large part in making a two dimensional representation appear truly
threedimensional. There are many different factors that contribute to creating
a correctly lit scene. They can be broadly divided into local lighting concerns
– the effect of a light on an object – and global lighting concerns – the
effect of objects on other objects in the presence of a light.

Local lighting
concerns include the intensity of the light when it reaches the surface of the
object, the correct shading of the object to represent its geometrical
structure, and specular highlights – the reflection of the light off smooth
surfaces.

Global lighting
concerns include shadowing of one object by another, reflections of other
objects, and refraction of light through semitransparent objects.
We
first look at various geometrical structures present in a threedimensional
scene. We then consider some techniques used to realise realistic real time
systems, including hidden surface removal, shading techniques and shadow
generation techniques. We conclude this chapter with a discussion of nonreal
time systems.
Polygonal
representation is the most popular method for representing objects in computer
graphics. It is the method supported by OpenGL, and as such will be the only
representation considered here. Polygonal representation consists of a
structure of vertices, each indicating a point in threedimensional space.
These vertices define polygons. OpenGL requires polygons to be concave and
planar in order to render them correctly, and therefore triangles are commonly
used – they meet these restrictions automatically. This form obviously matches
angular objects better than curved objects, but the ease of manipulation
outweighs any drawbacks. In addition, by using interpolative shading and
increasing the number of polygons, a polygon mesh can become indistinguishable
from a curved surface. The basic manipulations of polygons, such as
translation, scaling, rotation, etc. are well understood, and can be found in
any book on threedimensional graphics, such as Alan Watt’s Fundamentals of
ThreeDimensional Computer Graphics [Watt]. Some of the calculations used
in the systems implemented in this project are less common, and have been included
here for clarity.
This
is the basic unit of an object. A point is usually a vertex of a more complex
polygon. It comprises of x, y and z components, specifying its relative
distance from each of these three axes. Many graphic systems define x and y as
the screen coordinates, and z as the depth, but the axes can be completely
arbitrary without affecting manipulations. Manipulations of a polygon can be
done on each vertex independently.
A
line (or more accurately, a line segment) is a polygon of two vertices, but the
term is often used in the sense of an edge – the line joining two adjacent
vertices of a larger polygon. A line can be fully described by two end points;
a ray (a line with a starting point that continues into infinity) is defined as
a starting point and the direction of the line.
Figure 2‑1 Intersection of
Two Lines
The
point of intersection between two line segments is frequently needed.
Determining this in three dimensions is only slightly more complex than the two
dimensional equivalent. We outline this algorithm with reference to the above
diagram (Figure 21):

Let P_{1},
P_{2}, Q_{1}, and Q_{2} denote the end points of the
two line segments.

Then vectors u = P_{1}P_{0},
v = Q_{1}Q_{0}, and w = P_{0}Q_{0}.

If the lines
parallel (u and v in same or opposite directions), no intersection occurs.

Let p, q, and r
indicate arbitrary x, y or zaxes such that the two lines are not coplanar
parallel to the pr or qr planes.

Calculate the
intersection parameters:
o
Let d = u.p*v.q – u.q*v.p
o
s = (v.p*w.q – v.q*w.p)/d
o
t = (u.p*w.q – u.q*w.p)/d

Calculate the
intersection point, inter:
o
Inter = P_{0}
+ s*u, or Q_{0} +t*v.

If (P_{0}.r
+ s*u.r) – (Q_{0}.r + t*v.r) is not equal to zero – no intersection occurs in the third
dimension.

If the
intersection is not within the line segments, no intersection occurs.
We
will also often need to find the angle between two lines. We discuss a
simplified algorithm used to accomplish this:

let a be the
normalised vector of one line, and b be the normalised vector of the second
line.
 then
anglebetween = arccos(dot product of a and b);
Infinite
planes are flat surfaces that extend in all directions. While rarely present in
a scene, they are invaluable for various calculations. A plane can be fully
described by a point on a plane, and a vector perpendicular to the plane. This
can be compactly expressed in the form a, b, c, d, where a, b, and c are the
components of the normalised normal vector, and a*x + b*y + c*z + d = 0. This form allows for other values to
be easily calculated.
We
now outline some of the more pertinent calculations that are performed on
planes. We use these algorithms extensively in this project, primarily in
constructing a Binary Space Partition (BSP) tree and in determining whether an
object is exposed to a light source or whether it is obscured.
This
important fact is needed frequently. To determine where a point P is in relation
to the plane, find:

u = a*P.x + b*P.y +c*P.z + d

If u > 0
o
The point lies in
front of the plane.

If u = 0
o
The point is in
the plane

If u < 0
o
The point is
behind the plane
Another
vital piece of information in splitting polygons is the distance to the plane.
This is therefore another significant algorithm. The shortest distance between
a point P and the plane is simply:

Abs (a*P.x + b*P.y + c*P.z + d)
The
intersection of a line and a plane is important not only in creating a BSP
Tree, but also in determining whether segments are shadowed.
Figure 2‑2 Intersection of Line and Plane
With
reference to the above diagram (Figure
2‑2) we discuss the algorithm necessary to find the point
of intersection between a line segment and a plane:

If the line is
parallel to the plane, no intersection occurs.

If the end points
q and r do not lie on either side of the plane (or ray points away from plane),
no intersection occurs.

Calculate the
intersection point, inter:
o
Let direction = q
– r.
o
Let nDotD = dot
product of normal and direction.
o
Let nDotQ = dot
product of normal and point q.
o
Intersection = q +
direction*((d + nDotL)/nDotD)
(note that intersection, q and direction are vectors, d, nDotL, and
nDotD are scalars).
Cones are the next geometrical primitives we
discuss. These are pertinent to our project because they are used to model the
effect of the light source.
A 3D cone, starting from a point, tapers
outwards regularly, into infinity. It is defined by a starting point, a
direction, and the angle of spread (see figure 23).
We now discuss the operations that we perform on
cones and make use of in our project. Our discussion is centred on the fact
that we consider the cone to be well suited to representing a light source.
From the perspective of our project, we need to
determine whether an object is within the cone of a light source. To determine
whether a point is within a cone:

Determine the
vector between the point and the starting point of the cone.

Determine the
angle between this vector and the direction of the cone.

If this angle is
less than the spread angle, the point is within the cone. If it is greater,
then it is not.
This algorithm is relevant when we need to
consider how close a ray is to the edge of the cone, in order to determine how
much falloff has occurred.
To find the angle between
the edge of the cone and a ray from the starting point through a given point:

Check that the
point is in front of the cone, else return an error.

Determine
direction  the vector between the
point and the starting point of the cone.

Determine the
angle between the direction and the direction of the cone.

Return the
difference between this angle and the spread angle.
When
a three dimensional surface is projected onto a two dimensional screen, care
must be taken to ensure that closer objects obscure objects that are further
away, and not the other way round. This process is known as hidden surface
removal. It is a wellexplored field, and some of the major solutions are
described here.
The
algorithms that we discuss here are significant in creating real time systems,
and present the alternatives available for a modified hidden surface removal
algorithm to generate shadows, discussed in section 2.5.2.
This
is the practice of removing all faces on an object with normals pointing away
from the viewer – the ‘back’ faces of the object. It is not a complete solution
in itself, but is an easy test to perform and can speed up another algorithm
significantly.
This
is conceptually the simplest of the algorithms, and paradoxically one of the
hardest to implement. The idea is to
draw the objects furthest from view first, and then the objects closer by –
like an oil painter on a canvas. One simply overwrites the obscured sections of
the old polygon with the new polygon; no calculations are necessary. In order
to do this, the polygons must first be sorted in a backtofront depth order.
However, if polygons are naively sorted by an average or farthest depth, there
will be cases when the representation will be incorrect – an example where this
becomes strikingly apparent is the case where two objects that are both
partially in front of and behind each other. [Hill, pg 592]
These
problems can be solved by using octrees or BSP Trees to sort the polygons.
Octrees are hierarchical data structures, specifying occupancy of cubic volumes
of space (also known as voxels). When projected to 2D screen space, a quad tree
is generated. Binary Space Partition (BSP) trees divide the space adaptively
and are thus potentially more efficient than octrees. In these systems, the
‘problem polygons’ will automatically be subdivided in the creation of the
trees, and painter’s algorithm will yield the correct results in all cases.
[Watt, pg 190]
Also
known as the depth buffer algorithm, this technique is very popular. The
technique can be inefficient and is very memory intensive, but makes up for
these concerns in its lack of complexity – it is simple and fast, and requires
no sorting of polygons.
If
the scene is regarded as being a threedimensional space, with the x and y
coordinates making up the screen face, the equivalent z value indicates the
depth of the object from the screen. For every pixel to be rendered, the
zvalue is interpreted and compared to the value in the zbuffer. If the value
is less than the stored value, the new object in closer to the viewer than the
old object. The pixel is overwritten with the new value appropriate to the
polygon, and the new zvalue is entered into the buffer. [Watt, pg 22]
The
amount of memory dedicated to each pixel in the buffer limits the accuracy with
which depth can be determined – if 8 bits are used, surfaces closer than 1/256
of the total range to each other may not be distinguished, and the wrong face
may be drawn to screen. One solution for reducing memory requirements involves
limiting the size of the buffer to a fraction of the screen, and rendering each
fraction separately. [Hill, pg 594596]
The
Zbuffer is often supported in hardware, making this a very attractive option
for rendering packages, and is the technique used by OpenGL.
This
algorithm is adapted from a rendering technique that takes advantage of linear
spatial coherence to reduce memory traffic. The next pixel to be rendered is
very often the same colour as the pixel that has just been rendered. A colour
is loaded, and each subsequent pixel is flooded with that colour until the run
of the polygon ends. In the standard form, when a pixel that is contained by
more than one polygon is encountered, a userdefined priority level is used to
determine which polygon is rendered. When being used as a hidden surface
removal technique, this priority reflects the relative depth of the two
polygons at that pixel. [Hill, pg 597]
Also
known as Warnock algorithms, these methods take advantage of area coherence
rather than simply linear coherence. The visible area is subdivided until each
unit of area is ‘simple’ to render [Hearn & Baker, pg 268]. Each region is
tested in turn to see if it meets the requirements for simplicity. If it is
simple, it is drawn immediately. If not it is subdivided, and the process is
repeated.
The
various algorithms are variations on how ‘simple’ is defined and how the
regions are subdivided. Quadrant subdivision, for example, defines ‘simple’ as
an region with one face or no faces involved, or an region less than one pixel
in area, and subdivides a problem region into four equal quadrants. Other
definitions of ‘simple’ include:

A region that is
empty or less than one pixel in area – this simplifies the testing, but leads
to very high levels of subdivision.

A region with one
dominant face (a face that is everywhere closer than other faces), or an empty
region, or a region less than one pixel in area – testing for simplicity is
much more complex, but subdivisions are limited.
In this section we discuss the various
categories of light that combine to determine how an object is lit in a scene.
We consider the appearance of an object in a rendered scene to be produced by
the light that it emits, ambient light in the scene, diffuse light (diffuse
reflection of light from a light source) and specular light (specular
reflection of light from a light source).
Here, we provide a short introduction to this common
taxonomy.
This
is the light that is actually being emitted by the object. The object appears as
a light source (although most systems allow the user to define emitters that
will not be considered as light sources for other objects in the scene, and do
not count towards the eight light maximum). An emitter is not affected by any
other lights in the scene.
Ambient
light is a catchall term for the amount of light that is present in the scene
that comes from no particular direction. Every lit surface reflects and
scatters the light in all directions, in turn illuminating other surfaces. Each
light that is added to a scene will therefore increase the ambient light of the
scene. This chaotic light affects all surfaces roughly equally, and thus is
simply added to each object. [Bangay,
pg 130]
Diffuse
light is the light that comes from a particular source and is then reflected in
all directions. The intensity of diffuse light is a function of the relative
angles of the surface and the direction of the light to the surface – a surface
that is face on to the light will be very well illuminated, while a surface
that is edge on may not be illuminated at all. It is independent of the
viewpoint.
This
is light that is reflected off a surface in a particular direction. The shinier
the surface, the more apparent this effect is. It is a function of the angle of
the viewer to the surface, as well as the surface to the light, and is thus
viewpoint dependent.
Shading
indicates the difference in the effect of a light over the surface of an
object. The use of shading in our project is vitally important in rendering
objects in the presence of light sources realistically.
Constant shading calculates a single intensity for each
polygon in the polygon mesh, and applies this to the whole polygon, creating a
very artificial effect [Bangay, pg 141]. More popular techniques, such as
Gouraud and Phong shading use interpolative methods. We consider these methods
in greater detail below.
The
intensity of light at a vertex is a function of the orientation of the vertex
normal with respect to the light source and the eye. These values are
interpolated linearly across the polygon interior. Specular highlights cannot
be handled properly, and Mach bands can result because of discontinuities in
derivatives across polygon boundaries. The quality of the image can be improved
by increasing the number of polygons used to represent an object. [Watt &
Watt, pg 2324]
This
interpolates the normal vectors across the interior of the polygon, and calculates
the lighting equation at each pixel. This gives accurate highlights, and
reduces the Mach banding effect, but is much slower than Gouraud shading.
[Watt, pg 24]
Tesselation is the process of adaptive
subdivision in order to refine the image. Instead of requiring the user to
divide the object sufficient for lighting to be accurate, the algorithm
tessellates problem areas itself. [Andrews]
The
next consideration in creating realistic lighting is that of shadows. Every
object in a scene that is lit will cast a shadow. With this in mind we need to
critically evaluate the various techniques involved in their generation.
Rather
than attempting a true global light solution, we consider performanceenhancing
techniques in which shadows are added to a scene algorithmically. Some major
techniques that attempt this include:
This
technique treats shadows as if they are themselves polygons. The silhouette
edge of the object is projected from the light source onto another object. This
is relatively easy to do if the second object is a flat surface, and becomes
rapidly more complex with increasing complexity of the second object. The
colour of this shadow polygon is also difficult to determine. [Bangay, pg 188]
The
light point is treated as if it were the viewpoint. Standard hidden surface
removal algorithms are then applied. All surfaces that are not visible to that
light are marked as being shadowed by that light.
A
popular version of this is the shadow zbuffer  the depth information is
calculated as with normal zbuffer techniques, taking the light as viewpoint.
During rendering, if the equivalent z value in the lighting space is not
visible, the object is rendered with diminished intensity. [Watt & Watt,
pg166172]
In
a scan line algorithm, all polygons in the scene are projected onto a sphere
surrounding the point light. If a polygon does not overlap with any other
polygon, it is rendered as normal. If another polygon completely covers it, the
polygon is rendered with appropriately reduced intensity. If it is partly
covered, the polygon is subdivided, and tested each subdivision is tested.
Lights
in these algorithms are treated as ideal points, and thus the shadows produced
have hard edges. [Watt & Watt, pg 158160].
This
considers the volume of space that is shadowed, and tests objects to see
whether they fall within this volume. A shadow volume is projected from the
silhouette edge of an object and forms a semiinfinite cone pointing away from
the light. Finding the silhouette edge of the object can only be easily done
with polygonal objects that have not been generated parametrically, and
therefore this technique is usually only applied in these cases. By generating
a separate shadow volume from each vertex of an area light source, soft shadows
can be reasonably well approximated. [Watt & Watt, pg 160166].
Our
discussion up until now has centred on techniques that are designed to render a
scene in real time. Here, we change the focus of our attention to models that
are more realistic. They are consequently more resource intensive than their
real time counterparts.
These
are systems that try to approximate full global lighting solutions. They
attempt to render scenes using physical models of how light works. They are
distinguished by their very long rendering times – usually hours, and
sometimes days, for complex scenes. The results are generally of far superior quality
to the realtime approaches discussed in this paper.
We now examine two of the most significant
algorithms used to generate realistic and accurately lit scenes.
A
ray is projected from every pixel on the display screen into the picture to see
where it collides with objects. At a collision, two light rays are generated 
one reflected off the object and one transmitted through the object. Further
rays are generated from the point to every light source to see whether that
point is visible to the light, with only the visible lights used to calculate
colour of the object effectively creating shadows. This process is iterated to
a certain depth, and the pixel colour is generated as a combination of the
colours of the objects encountered by the rays. This method is used by POVray
and Radience.
This
method treats surfaces as perfectly smooth, and thus generates unnaturally
sharp reflections. [Watt & Watt, pg 219222]
The
term radiosity refers to energy leaving a surface per unit area per unit time.
The radiosity technique iterates through each patch (surface element),
calculating energy received and emitted, effectively tracing the path of a
light ray as it bounces around the world [Hall, pg 7071] until the system
reaches equilibrium. Light sources are simply surfaces with an initial nonzero
radiosity. This method replaces the ambient factor with an accurate calculation
of diffuse lighting. It handles colour bleeding – when a surface is lit
indirectly, it tends to take on some of the colour of the objects the light is
reflecting off. It renders shadows in a true and accurate manner, and is view
independent. However, because it treats light intensity as being constant over
the area of the patch, it handles specular highlights badly. It is also
massively time intensive, often an order of magnitude greater than ray tracing.
It works best in generating manmade environments where the viewindependence
is a significant advantage – a walk through of a proposed building for example.
[Watt & Watt, pg 266268]
A large
quantity of vector mathematics is used in manipulating 3D objects. Structures
such as points, lines, planes and cones are used to represent the data.
Information such as intersections and the position of a point to another
structure can be determined. Hidden surface removal techniques are used to
ensure that polygons are rendered on the correct order with respect to the
viewpoint. Many algorithms exist, of which the zbuffer is the most popular and
is supported in hardware.
Lighting
concerns include local effects – intensity, shading, and highlights – and
global effects – shadowing, reflection and refraction. The intensity of light
can be divided into emitted light, ambient light, diffuse light and specular
light, each of which is handled separately by a lighting engine. Shading can be
either flat, Gouraud or Phong. Gouraud is most commonly used because it is more
realistic than flat, but not as time intensive as Phong. Phong handles
highlights better than Gouraud. Shadows can be generated by creating new
polygons that indicate the shadow, by using a hidden surface removal algorithm
with the light source as origin to indicate the shadowed areas, or by testing
each polygon to se whether it falls within the shadow of another polygon.
Reflection and refraction, in addition to the other effects mentioned above,
are handled by non real time systems. Raytracing tends to produce unnaturally
sharp reflections. Radiosity is the only technique to handle colourbleeding,
but does not handle highlights well. Both are extremely timeintensive.
Having
introduced the fundamental principles involved in rendering a threedimensional
scene, we now continue on to formulate the design for multiple light source
solutions.
In this
chapter we discuss our approach to the problem of modelling multiple light
sources. By necessity, we introduce this chapter with a discussion of the
minimum requirements for such a system. Once we have defined our problem
domain, we consider possible solutions. This allows us to fully explain the
systems we chose to implement in this project. We chose to implement two
solutions, our custom BSP Tree solution and the VLS solution as our control. We
continue our discussion by considering common design elements in these systems.
We then conclude this chapter by discussing the generic multiple light source
class structure used.
We start
this section with a discussion of the requirements for a lighting system,
taking into consideration local and global lighting aspects.
A
complete lighting system would handle all the local and global concerns
discussed in the previous chapter, namely:
1.
Intensity of light
at a point
2.
Shading
3.
Highlights
4.
Shadowing
5.
Reflections
6.
Refractions
However,
even nonreal time systems can rarely cope with all these requirements –
radiosity cannot handle highlights, raytracing cannot handle diffuse
reflections. In the interest of keeping the lighting solution close to
realtime, only the most relevant features are implemented. The intensity of
the light as it reaches the surface is obviously a prerequisite for any
lighting solution. Shading demonstrates the 3D nature of the objects, and is
therefore also required. Shadowing provides valuable verisimilitude. If we
restrict the system to only containing matt, opaque objects, features 3, 5, and
6 can be safely ignored without much loss of image quality. Further, by not
considering these issues, the system becomes viewindependent.
Now that
we have defined our problem domain, we can consider possible solutions.
True multiple lighting situations are rare. In
the cases where more than eight lights exist are usually solved by using
lightmaps or virtualised light sources. Recently, there have been attempts to
modify global lighting solutions to produce realtime results.
Our investigation into this problem revealed
five possible solutions. We discuss each of these in some detail before
explaining our decisions about which to implement.
The effect of the light is computed by the
application and applied to the vertices as colours. An advantage of this scheme
is that unlimited lights can be introduced. The main disadvantage is that
hardware acceleration cannot be used.
This
approach offers quality at the cost of speed.
Lightmaps are texture maps that contain
information about the light pattern cast by a particular light. This creates an
intensity scale, which is then transformed to match the object/scene and
blended with the existing textures. Lightmaps can provide smoother light
solutions than Gouraud shading and there is no limit as to how many can be
added, although each one does introduce an extra time penalty. They are most
effective in fairly static scenes. [Johansson]
This is a perobject calculation of the eight
brightest or closest lights. The lights that most affect each object are
enabled dynamically as the scene is rendered. There is extra overhead time
introduced by this, but the technique takes advantage of any hardware
acceleration. The technique is only successful if eight or less lights truly do
make a significant contribution to the object being rendered. In actual practice,
the number of effective lights in a scene is usually significantly lower than
eight. [Kilgard]
Radiosity has no restrictions as to number of
lights, and thus a realtime version would provide a complete solution for a
multiple light source scene. Radiosity is well known for being timeconsuming.
By reducing the accuracy of the radiosity calculations, the process can be
dramatically sped up. The complexity used would become a tradeoff between a
solution that is fast and a solution that is satisfyingly ‘real enough’ to the
viewer. A modification of environmental mapping techniques has been proposed,
but not implemented:

Place a cube around the object origin, and render the scene onto
each surface (ignoring the presence of the object itself).

Blur the cube view to take
into account distortion, fading, and angle.

Map to UV coordinates, as in normal environmental mapping.

Use this to texture map the cube view onto the object, treating
pixel colour values as lighting values, adding lighting values from direct
light sources.

Render the scene.
[Vegdahl]
Vertex ray tracing differs from ray tracing in
that instead of tracing rays from every point on an object, the algorithm only
trace rays from the vertices. If the
number of polygons in the scene is reasonably limited, this can speed up the
raytracing process to the point that it becomes real time.
We implement two solutions. The first is chosen
as a control, and the second is chosen as one that offers the greatest capacity
for us to innovatively solve the problem of multiple light sources.
As virtualised light sources is the most common
solution, we implement it as a standard for comparison. This system
automatically handles intensity, shading and highlights, and simply needs to be
modified to include shadowing.
We also chose an applicationcomputing solution
to generate highquality images, as this solution offers the most scope for
innovation. The intensity and shading can be handled with an appropriate
lighting model. A modified hidden surface removal algorithm is chosen as the
most elegant method of shadowing. The zbuffer algorithm and the scanline
algorithm need to be supported in hardware to be effective, and are therefore
inappropriate. Painter’s algorithm is finally decided on as being potentially
faster than area subdivision algorithms. The applicationcomputing system is
therefore based on a BSP Tree structure in order to shadow using this method.
Our decision to ignore lightmaps, realtime
radiosity and vertex ray tracing is largely based on the inflexibility of the
algorithms. These algorithms offer little in the way of creative development,
and we felt it more relevant to the development of computer graphics to focus
our attention on a relatively uncharted solution.
We now discuss the design of the common elements
within the VLS system and the custom applicationcomputing (BSP) solution.
The graphic primitives, and the techniques of
storing them, are common to both of the systems chosen and are briefly detailed
here. We have categorized these common elements into
three parts  primitives, subdividing polygons and storing polygon meshes. We
now discuss these in greater detail.
The
primitives used in the systems compose of:

Geometrical
structures: Point3D, Vector3D, Plane, and Cone, explored in detail in section
21 above.

Storage
structures: OneVertex, Triangle, Colour, and LightDescription, explored below.
Figure 3‑1 OneVertex Class Diagram
This
simply stores the position and the colour of a vertex.
Figure 3‑2 Triangle Class Diagram
This is
an index to the vertices making up a triangle – see section 3.4.3 below.
Figure 3‑3 Colour Class Diagram
This
stores the r,g,b, and a values that specify a colour, and provides some
additional functionality.
Figure 3‑4 LightDescription Class Diagram
This
contains some values that are chosen to reflect the nature of spotlights.
One polygon may have very different light
patterns across its full area, and thus to render a more accurate scene, the
polygons may have to be subdivided into segments.
Figure 3‑5 Subdividing
Polygons
To create segments:
If (polygon is a triangle)
Add to segment list
Else
// Divide polygon into triangles
For i= 0 to number of vertices –2
New triangle has vertices 0, i+1,
i+2
Add triangle to segment list
While (still subdividing triangles)
For all triangles
If area > maximum area
// Subdivide triangle
– see figure 35
Original
vertices = one,two,three
Halfway points
between vertices = four, five, six
Triangle 1 has
vertices one, four, five
Triangle 2 has
vertices two, four, six
Triangle 1 has
vertices three, six, five Triangle 1 has vertices four, five,
six
Add triangles to
segment list
The colour information also has to be carried
across, and scaled to reflect the position of the new vertices. By converting
all polygons into triangles, splitting polygons becomes simpler, and the
definition of points is automatically cyclic, convex and planar.
The
aim of any storage structure is to maximise speed of access and minimise space
taken.
Many
different formats exist for the storage of 3D objects. The simplest, like the
POVray RAW triangle format, store the position of every vertex in every
triangle [Anger]. However, the vast majority of structures store vertices
separately, and then reference them when specifying the triangle. Describing
polygons as an index into a vertex list has a number of advantages:
1.
Less memory is
used.
2.
Vertex
transformations occur only once.
3.
Shared vertices
are easier to find.
This
is the representation used by OFF, VRML and other 3D formats [Bangay, pg 233].
Most
structures include some colour or texture information, support other primitives
(polygons, lines), and may also include layer information, moveable parts, and
so on. Most of this provided functionality that is superfluous for these
lighting systems – the systems are restricted to static scenes. Triangles are
indicated for other reasons mentioned above, as well as simplicity of manipulating
them in this format. The format that is therefore chosen for the segment list
is:
A vector of triangles:

Three integer
values indexing the appropriate vertices
A vector of vertices:

The position and
colour information of that vertex.
This
section shows the abstract structure of our system. We outline the major
classes and their interaction.
The
object model of a multiple lighting solution reflects the physical objects in
the scene – the lights and the polygons. Figure 36 shows a simplified diagram
indicating the various classes used to render a scene –
LightSceneVisualRepresentation renders the LightScene. The LightScene is
composed of lights and polygons. The polygons have been subdivided into
segments that are stored as a vector of vertices and a vector of triangles.
Figure 3‑6 Generic Class
Structure
If all
local and global lighting effects are implemented, the resulting solution would
be far from realtime. However, if we only consider matt opaque objects, then
we only need to consider intensity, shading and shadowing to create a
satisfying scene. Many possible solutions exist to render multiple light source
scenes, of which virtualised light sources is the most commonly used. We chose
this solution to implement as a standard of comparison. We also chose an
applicationcomputing solution to generate high quality images. This system is
based on BSP Trees in order to facilitate shadowing. Some design elements are
common to both systems – the primitives used and the methods for subdividing
polygons. An object model for any multiple light source solution shows a light
scene as an aggregate of lights and polygons, subdivided into triangles.
This
concludes our discussion of the problem of modelling multiple light sources and
our approach to its solution. We have outlined the elements common to the
systems we chose to implement, and discussed the structure of the test program,
also common to both solutions.
In the
following two chapters, we explore in detail each of our selected
implementations. We start with the standard solution (VLS) and continue with
the customapplication solution (BSP).
In this chapter we discuss the implementation of
a Virtualised Light System (VLS). This algorithm is a perobject calculation of
the eight brightest or closest lights. We give a more detailed overview of the
technique, and discuss standard algorithms used to implement this technique. We
explain adaptations we have made to the system to handle variable intensities
and we discuss how to add shadows. Following this we give a synopsis of the
final system, discussing the various problems we encountered, and conclude with
possible extensions to the system.
The
steps involved in creating a scene using virtualised light sources are outlined
below.
During
setup:

Enter all polygons
and lights.

Divide the
polygons into segments.

For each segment,
calculate the eight closest lights that can illuminate that surface.
At
run time:

For each segment,
enable the relevant lights with the corresponding intensity value.
The
openGL supported zbuffer is used for hidden surface removal, the openGL
lighting model for intensity and shading (described in section 4.3.1), and
shadow feelers (a ray cast from the point to the light) for determining
shadowing.
The eight closest lights are calculated prior to
the actual running of the system.
For all segments
For all lights
Find distance from segment to
light
Until eight lights found
Find closest remaining light
If not shadowed
Set as next closest
light
The triangle class is extended to index the
eight closest lights to the segment, substantially increasing the size of this
structure.
Because intensity values are variable, it is
impossible to determine which are the brightest lights at a point in the
precalculation. Therefore, we simply determined the eight closest lights.
The
method used by OpenGl defines:
Vertex colour = light emitted + global ambient scaled
by ambient property + ambient, diffuse and specular contributions from all
light sources, attenuated as necessary.
The attenuation factor is a
quadratic expression that expresses how rapidly light intensity falls off over
distance away from the light. The contribution is further modified by a
spotlight effect – the fall off over distance from the centre of the light
beam. [Woo et al., pg 211241]
When
calculating the eight closest lights, the light is checked to see if it is
visible from that segment.
To
determine if the segment is shadowed:
For all other polygons in the scene
Generate
the plane of the other polygon
Find the intersection
between the plane and the line joining the point to the light
If the point is
within the polygon
The polygon is shadowed.
By
not considering those lights that are not visible to the polygon, the light will
not be activated when rendering segments that are shadowed. This technique is
inaccurate in that it treats the segment as a point rather than an area, and
therefore a segment that is actually partly shadowed will either be rendered as
fully lit or fully shadowed. However, the quality of the resulting image can be
improved increasing the number of segments in an object.
When
a shadow feeler is cast from the segment to the light, we need to test every
other polygon to see whether it lies between the segment and the light source.
After we have determined the intersection of the feeler and the plane of the
polygon, we need to find out whether this point lies within the polygon.
Figure 4‑1 Jordan Curve Theorem
To
determine if the intersection point lies within the polygon:
Find the largest component of the polygon
Project to the plane of the
other two components
Place point at origin
For each edge
If edge crosses
the positive axis of the second component
// That is, if the
two end points lie on either side of the axis
Increment count of intersections
If
intersections =1
The
point lies within the polygon
Else
The
point lies outside the polygon
In
general, a point is within a polygon if the number of intersections is odd – by
the Jordan curve theorem (see figure 41 above) [Bangay, pg 167]. In this system, however, polygons are
restricted to being concave, so only one intersection is possible if the point
is within the polygon.
Our
final system implements the algorithm to calculate the eight closest lights
with the adaptation for variable intensities and shadowing. We now discuss some
of the more important problems encountered in creating this system, and examine
the resulting class structure of this solution.
The
VLS system is relatively simple to implement, and translated well from
theory. It took some trial and error to
convert the LightDescription to the appropriate OpenGL equivalents. The most
problematic part is to calculate the falloff – this is eventually approximated
as a scaled ratio of the null radius and the full radius.
A
further problem is that at runtime, random segments light up at full intensity
or go black for a frame. This was never tracked down, but as the pattern
altered every frame, it was assumed the problem did not lie within the
application code.
Figure 4‑2 VLS Class Structure
As it
stands, the system will already produce specular highlights.
Transparency,
without refraction, would simply involve making use of the alpha values already
supported in OpenGL. The object would, however, still cast a full shadow. Adding refraction could be done by blending
the appropriate colour values of the polygons that are seen through the object
with the values of the object itself at setup time.
Reflection
could be handled with a simplified raytracing algorithm – a ray is shot out
from every segment and tested to see whether it intersects another polygon. The
colour values could then be blended at the appropriate ratio. For refraction
and reflection, the viewpoint must be known at startup.
The VLS
system extends the segment list to include information about the eight closest
lights. Shadow feelers – a ray that determines whether any polygons lie between
the point and the light source – are used to exclude lights that do not light
that segment. The system is generally easy to implement, although some
unexplained hardware errors occurred. It could possibly be extended to include
refraction and reflection, at the cost of view independence.
This
concludes our discussion of the VLS. We move on to our customapplication or
BSP system.
The Binary Space Partition (BSP) System
algorithm is the custom solution we chose to implement because of the wealth of
possibilities available in its customisation.
We follow much the same approach in this
discussion as we followed with the VLS solution. We start by giving an overview
of our solution, and discuss the standard algorithms involved. Following that,
we discuss adapting our solution to handle variable intensities and consider
how to add shadows. Additionally, we discuss some time optimisations. In our
discussion of the final system we consider the problems we encountered and
outline the class structure. Lastly, we discuss possible extensions.
The
steps involved in creating a scene using Binary Space Partition Trees are
outlined below.
During
setup:

Enter all polygons
and lights.

Sort polygons into
a BSP Tree.

Divide polygons
into segments.

For each light,
clone the BSP Tree:
o
Modify colour
values to reflect effect of that light at full intensity.
o
Use Painter’s
algorithm to indicate shadows, and modify colour values.
At
run time:

Scale light BSP
Trees by light intensities.

Combine all light
trees and render.
The
lighting model used is described in 5.3.1, a BSP Tree is used for hidden
surface removal, and painter’s algorithm used to find shadows.
The
most substantial data structure used in the implementation of this system is
the Binary Space Partition (BSP) tree. The BSP Tree is a hierarchical structure
of recursive subdivisions. A three dimensional space is divided into two by a
plane (a two dimensional space by a line, etc.) and the resulting tree is a
powerful sorting and classification structure.
BSP
Trees provide an elegant method for hidden surface removal. Polygons can be
returned in a back to front order to be used in a Painter’s algorithm (see
section 2.2.2 above). Polygons can also be returned in a fronttoback order
for scanline algorithms (each pixel may only be written to once). BSP Trees
can also be used to compute analytic visibility, accelerate ray tracing,
perform collision detection and compute shadows. [Wade et al.]
Constructing
a BSP Tree consists of

Selecting a
partitioning plane

Partitioning the
polygons with the plane

Recursing with
both sets.
The
stopping point for recursion is application specific, either to a maximum
depth, or a certain maximum number of polygons in each leaf node. [Wade et al.]
For
this system, the first polygon of the set has been used as the partitioning
plane. For the most effective use of the tree, the end point is chosen as when
all polygons are within internal nodes.
To
construct a tree:
Initialise a node with the first polygon
as the partitioning plane
Add first polygon to coincident
polygon list
For all remaining polygons
If polygon
coincident
Add to coincident
polygons list
If polygon
completely in front of plane
Add to front list
If polygon
completely behind
Add to back list
If polygon spans
plane
Split polygon
Add the front piece
to the front list
Add the back piece
to the back list.
Create front node with front
list
Create back node with back
list.
This
algorithm does a large amount of list handling, and ignores the end case. In
practice, it is easier to create a node with only the partitioning polygon, and
default front and back nodes to null. Each subsequent polygon is then added to
the tree in a separate method.
To
split the polygon across the plane:
For all vertices
If point in front
of the plane
Add to front piece
Else
Add to back piece
If next point and
current on opposite sides of the plane
Find intersection of the line
joining current and next with the plane.
Add to front piece
Add to back piece
If the original polygon is specified cyclically,
then so will the two resulting two polygons.
Polygons can be returned in a back to front or
front to back order from a certain viewpoint. The following algorithm is for
returning polygons in a back to front order:
If the viewpoint is in front of the plane
Return polygons
from back node
Return polygons
from this node
Return polygons
from front node
Else
Return polygons
from front node
Return polygons
from this node
Return polygons
from back node
The algorithm for front to back order simply
reverses this if statement.
A
very simple lighting model is set up to light the system. Lights are assumed to
be spotlights, defined by the position, the direction, two angles – the radius
within which the light is at full intensity, and the radius without which the
light is at null intensity – and the colour.
The
lighting equation:
If point outside the null cone
intensity = 0
If point within the null cone,
but outside of the full cone
intensity = angle between
vertex and null edge / angle between full edge and null edge
If point within full cone
intensity =1
L = vector from vertex to
light source
N = normal of the surface
Dist = distance between point
and light source
Modifier = intensity *reflection coefficient* n Dot L / (distance/arbitrary
constant).
The BSP Tree that has been
generated for the scene is cloned for every light in the scene. The effect of
this light at full intensity on each segment in the scene is calculated and
stored in the tree. Shadows are then added (see below). At run time, this tree
is then scaled by the intensity of the light. All light trees are then
combined, and the scene is rendered.
The next step in our
implementation is the inclusion of shadows. Our implementation is outlined as
follows: the polygons are retrieved from the BSP Tree in a back to front order,
with the light treated as the viewpoint. Each polygon is then projected from
the light to the plane of each polygon behind it. The overlap indicates the
shadow cast by the front polygon on the back polygon. The colour values of the
segments within this overlap are set to zero, for that particular light BSP
Tree.
Various algorithms were
attempted for projecting the polygon to the plane of the shadowed polygon. The
first attempt makes extensive use of quaternions. The area shadowed is
approximated as the area covered by dropping the polygon perpendicular to the
target plane:
Move polygon such that target point
becomes the origin
For each point in original polygon
Rotate
point such that target plane becomes parallel to xy plane // using quaternions
Project
point onto xy plane (set z values to zero)
Rotate
back
Move polygon back
The second attempt produced
exactly the same results, but somewhat more elegantly:
For each point on original polygon
Generate ray from the point
along the polygon normal
Find intersection between ray
and target plane
Set corresponding point of
target polygon as intersection
This algorithm, however, can be
easily modified to eliminate the approximation. By generating the ray from the
point to the light source (instead of the ray along the polygon normal) the
projection can be made accurately. This
is the final algorithm used in the system.
The polygon being shadowed is passed the area
that is shadowed. It then iterates through each segment, testing whether that
segment falls within the shadowed area (in fact, each vertex is tested
separately). Originally, an attempt was made to pass only the overlap between
the projected polygon and the shadowed polygon. The major difficulty occurred
in trying to generate an overlap polygon that was cyclic in definition. The
algorithm as it stood before it was finally abandoned was:
For each edge (a, b) of first
polygon
For each edge
(c,d) of second polygon
If the two lines intersect and
at least one point lies within the other polygon
If one point of each line lies
within the other polygon //that is, corners overlap
If a not in
overlap vector
add a
Else if b not in
overlap vector
add b
If intersection
not in overlap vector
add intersection
If c not in
overlap vector
add c
Else if d not in
overlap vector
add d.
Else if both a and
b lie within other polygon
…
And so on for another hundred lines, but it
still did not result in a cyclic definition of points in all cases. However, it
was found that since the algorithm to create shadows tests only points that are
within that polygon, if the entire shadowing polygon is passed, the same effect
is achieved.
Rather than storing and transferring the full
BSP Tree for each light, each light BSP Tree is immediately converted to a
vector of polygons in a predetermined order. This list takes less time to pass
between classes than the full BSP Tree.
When the polygon is scaled by the intensity of
the light, it alters the values of the polygon. The polygon must therefore be
cloned as many times as there are active lights every frame. This is a very
time intensive process, and therefore a modified clone technique is used that
provided the required functionality but does not take as long.
The following modifications are used:
1.
Vertex positions
of polygon were not cloned, but passed as references.
2.
In the segment
list, the elements in the triangle list are passed as references.
3.
In the segment
list, in the elements of the vertex list, positions are passed as references.
In effect, only the colour information of each
polygon is in fact cloned. This speeds up the process significantly.
Lights whose intensities are very low (taken as
less than 5%) will have no significant effect on the scene. By not scaling and
adding the light BSP Tree for these lights, the frame rate of a sparsely lit
scene is dramatically improved. Obviously, if all lights are in use, no speed
up occurs.
When a
polygon is passed to a node, we first have to check whether the node equals
null and has to be initialised, or if it already exists. Because polygons are
passed down frequently in various parts of the construction code, this
functionality is removed to a separate method. In the interests of code
protection, however, Java does not allow direct manipulation of pointers. A
pointer passed as a parameter cannot be changed. A work around involving an
integer key and a switch statement had to be used.
Because
of floating point inaccuracies, polygons that just touch are sometimes
subdivided into the full polygon and a second polygon of zero width. Also,
polygons that are projected to another plane and then back again are slightly
misplaced. A partial solution to this is to limit the accuracy to significantly
below the available accuracy. All double values are rounded off to four decimal
places where appropriate, and if the point is very close to the plane, it is
considered to be in the plane.
Java
passes all values by reference rather than by value. Therefore, in the
instances where values have to be changed temporarily, it is necessary to pass
a clone of the object. To implement the
clone class, a new object has to be created, and then the values of that class
have to be entered into the new object. Of course, these values themselves need
to be cloned – only simple primitives such as integers and doubles are passed
by value. Some care had to be taken for each ‘layer’ to ensure it is cloned
correctly. We need to create an object, clone it, change the values of the
clone, and then compare the two to ensure the original remains unchanged.
The
system is very memory intensive, and cannot handle very complex scenes on an
average user computer. The original goal of one hundred lights cannot be met.
However, we have successfully rendered a simple scene with up to fifty lights.
Figure 5‑1 BSP Class
Structure
To
implement the other lighting effects, the viewindependent nature of the system
must be sacrificed. If the position of the viewer is passed to the segment list
in the method initialiseLitSegments, the lighting model could easily be
adjusted to handle specular highlights.
Transparency,
without any refraction, can be handled by adding alpha values to the Colour
class. The shadowing method could be modified to allow for partial shadows –
instead of reducing those values to zero, shadowed segments could be scaled by
an appropriate factor. To create refraction, the polygons behind the
transparent object (from the point of view of the user) would have to be
shifted by the appropriate amount and then blended with the object colour. This
would have to be done after all the polygons are entered into the scene, but
before lighting is considered.
Reflections
could be handled in a similar way to shadowing. Along the correct angle (see
figure 52), polygons could be projected onto the plane of the reflective
polygon. Those that overlap can be blended with the existing polygon at a
suitable ratio, depending on the reflectiveness of the material.
The BSP
System uses a BSP structure to sort the polygons, and then uses Painter’s
algorithm to set the appropriate segments as shadowed. Some time optimisations
are used to speed up the system, such as a modified clone method and not
considering low intensity lights. Some complications were found due to the
restrictions and limitations of Java, but could generally be worked around. The
system could possibly be extended to include highlights, refraction and
reflection, at the cost of viewindependence.
This
concludes the discussion of the implementation of the two systems we chose to
implement, VLS and BSP Systems. We now take a step back from these low level
discussions and critically consider the results of our project.
This chapter discusses the results of our work
on this project. We contrast our two systems when we investigate the success of
the shading and shadowing techniques employed. We then evaluate the time taken
to generate render a scene, and give of few examples of scenes rendered by the
BSP system.
To test whether different faces of a surface are
rendered correctly, both systems were tested with a box. To avoid floating
point errors, the box floats slightly above the surface of the plane, rather
than sitting directly on top of it.
The box in figure 61 is rendered correctly –
surfaces perpendicular to the direction of the light (the floor and the top of
the box) are brightly lit, while the surface parallel to the direction of the
light (the front face of the box) is dimly lit.
In figure 62, we can see that the box is
rendered correctly, in the same way as the VLS system, as expected.
This
is a scene composing simply of one polygon raised above a plane, with different
coloured light sources from different directions. It is used to test whether
shadowing works correctly.
Figure 6‑3 VLS Without Shadows
First,
what the scene looks like without shadowing. In figure 63 we can see that
areas of low intensity lighting not rendered correctly – it is clear which
segments have not employed which lights, for example, on the top of the
polygon.
In
figure 64 shadowing is in evidence – the full shadow slanting to the left and
the blue shadow slanting to the right. Only a faint pink shadow occurs because
few of the segments in that area that are not shadowed employ the blue light
anyway. The shadow is irregular, but the quality (at the cost of extra time)
could be improved by segmenting the polygons further.
Figure 6‑5 BSP Without Shadows
Again,
we demonstrate what the scene looks like without shadows. In figure 65 we can
see lighting is smooth, with low intensity areas lit correctly.
Shadowing occurs correctly in figure 66 – the full
shadow slanting left, the blue shadow slanting right, and the pink shadow
slanting forwards. Edges are smooth and sharp, as desired.
In this section we discuss the time needed to
render a scene. Our discussion starts with the time taken to initialise the
system, and progresses to discuss the frame rate achieved by our systems
The
VLS System takes ten seconds to startup. The BSP System takes three minutes,
six seconds to start up, which is more than eighteen times longer than the VLS
System. The VLS system may be altered with reasonable time costs, but changing
the scene in the BSP system is prohibitively expensive.
The
VLS Systems advances fairly regularly – lights 5 and 14 are the two centre
lights that affect proportionally more segments than the other lights,
explaining the jumps. It takes approximately 0.12 extra seconds for each extra
light. By extrapolation, 100 lights would take 12.5 seconds per frame.
The
BSP System starts at a higher frame rate than the VLS system, but is more
affected by an increasing number of lights. It takes approximately 0.15 extra
seconds for each extra light. 100 lights would take 15 seconds per frame.
Both
time dependencies are roughly linear, which is what is expected.
Figure 6‑8 BSP Intersecting Polygons
Figure
68 demonstrates intersecting polygons. The polygons are lit by ten sidelights,
blue from the left and purple from the right.
Figure 6‑9 BSP MultiColoured Polygons
Figure
69 demonstrates a multicoloured polygon lying at a slant. It is lit by
twentyfive white lights from directly above.
Both
systems handle the requirements of intensity and shading correctly. Shadowing
is handled with limited success by the VLS system, and with more success by the
BSP system. The startup time of the VLS System is significantly less than that
of the BSP System, but their frame rates were of comparable orders.
Now that
we have completed our discussion on the findings of this project, we draw some
conclusions about the project.
To
represent a 3D scene, the objects must be placed in their correct positions,
rendered in the correct order to a twodimensional screen, and lit correctly.
There are six major categories of lighting effects – the intensity of a light,
shading, highlights, shadowing, refractions and reflections. A full solution
would implement all these effects, but if only matt, opaque objects are
considered, then highlights, refractions and reflections can be ignored.
The range of solutions to these problems is
vast. There is a tradeoff not only in quality versus speed, but also in the
type of quality – realtime radiosity offers colour bleeding but no specular
highlights, light maps potentially offer both, but no reflections or
refractions. Some solutions, such as light maps and the BSP solution described
here, are static. Virtualised light sources is the most commonly used solution
and is implemented as a standard for comparison. A better quality image can be
created with an applicationcomputing, and a system using Binary Space
Partition Trees to create shadows is implemented. The optimum solution will clearly be application specific.
In
comparing the two systems, we are presented with the classic quality versus
speed tradeoff. The BSP system provides better quality and more accurate
shadowing, but the VLS system is marginally faster. Neither system is truly
realtime, but a few seconds to render a scene would not be too much of a delay
for a user whose only other option is raytracing.
Future
projects could implement the multiple light solutions not investigated here 
lightmaps, realtime radiosity and vertex ray tracing.
The
current systems could be expanded to deal with the other lighting concerns –
specular highlights, semitransparent objects and reflections, as described in
sections 4.6 and 5.7.
[Andrews] 
Andrews, Jeff. Light Based Tessellation: Application
Note http://www.gamedev.net/reference/articles/article1504.asp. 
[Anger] 
Anger, Steve. POVray raw triangle format http://astronomy.swin.edu.au/~pbourke/geomformats/pov/povraw.html,
1996. 
[Bangay] 
Bangay, Shaun Computer Graphics Course notes,
2001. 
[Hall] 
Hall, Roy Illumination
and Color in Computer Generated Imagery. New York: SpringerVerlag, 1988. 
[Hearn & Baker] 
Hearn, D. & Baker, M.P. Computer Graphics. New
Jersey: PrenticeHall, 1986. 
[Hill] 
Hill, F.S. Computer Graphics. New York: Macmillan
Publishing Company, 1990. 
[Johansson] 
Johansson, Tobias Lightmaps http://polygone.flipcode.com/tut_lightmap.htm,
2000. 
[Kilgard] 
Kilgard, Mark Virtualized OpenGL Light Sources for
Efficient MultiLight Source Lighting http://www.opengl.org/developers/code/mjktips/VirtualizedLights/VirtualizedLights.html. 
[Vegdahl] 
Vegdahl, Realtime Radiosity http://www.gamedev.net/reference/programming/features/rtradiosity/ 
[Wade et al.] 
Wade et al., Binary Space Partitioning Trees FAQ http://www.faqs.org/faqs/graphics/bsptreefaq. 
[Watt & Watt] 
Watt, Alan & Watt, Mark. Advanced Animation and
Rendering Techniques: Theory and Practice. New York: ACM Press, 1992. 
[Watt] 
Watt, Alan. Fundamentals of ThreeDimensional Computer
Graphics. London:
AddisonWesley Publishing Company,1989. 
[Woo et al.] 
Woo, M., Neider, J., Davis, T. & Shreiner,D. OpenGL Programming Guide: the Official
Guide to Learning OpenGl,Version 1.2 , 3^{rd} Ed. Indianapolis:
Silicon Grahics, Inc., 1999. 
Frame Rate 

Number of Lights 
VLS System / [s] 
BSP System / [s] 

1 
0.7 
0.4 

2 
0.8 
0.5 

3 
0.9 
0.6 

4 
1 
0.9 

5 
1.3 
1.1 

6 
1.4 
1.2 

7 
1.5 
1.4 

8 
1.6 
1.5 

9 
1.7 
1.6 

10 
1.8 
1.8 

11 
1.9 
2 

12 
2 
2.1 

13 
2.1 
2.2 

14 
2.3 
2.4 

15 
2.4 
2.5 

16 
2.6 
2.7 

17 
2.7 
2.9 

18 
2.8 
3 