CS计算机代考程序代写 algorithm Engineering Techniques for Computer Graphics

Engineering Techniques for Computer Graphics

1

Radiosity : Selection of
advanced topics

Intended Learning Outcome

 Study an advanced topic on graphics scene modelling:
radiosity

 Learn how radiosity can model higher level diffuse
reflection and account for the ambient term

 Understand how radiosity is implemented by fast
iterative technique called progressive refinement

2

Radiosity models some phenomenon
in nature
 Colour bleeding

 Soft shadow boundaries and shading within shadows

3

Radiosity

 In conventional graphics, only the “first order” (pixel ray
to first intersection) diffuse reflection is modelled.
Second and higher order (object to object) diffuse
reflections cannot be modelled. Instead, they are
approximated by ambient light 𝐼𝐼𝑎𝑎

 Radiosity models all the higher order diffuse reflection
simultaneously. Thus, with the radiosity model, there is
no need for the ambient term in the illumination model

4

Characteristics

 Adapts the spatial heat transfer model
 Based on conservation of energy
 An object space method: it solves for intensity at surface

patches within an environment. Thus, the solution is
independent of the viewer position. It is easy to obtain
views from different directions

 Useful for realistic background in action games, for
example

5

Limitations

 Cannot model higher order specular reflection (higher
order specular reflection is better modelled by ray
tracing)

6

Radiosity model
Assumptions
1. All surfaces are ideal diffuse (Lambertian) reflectors
2. No specular reflection
3. The surfaces are opaque

The scene is modelled as an enclosure, a volume enclosed by surfaces

7

Definitions

Radiosity 𝐵𝐵 : Light energy leaving a surface point per unit
time per unit area (unit : J/s � 𝑚𝑚2) = 𝑊𝑊/𝑚𝑚2)

Intensity (or luminance) 𝐼𝐼 : Light energy per unit time per
unit projected area per unit solid angle (unit : 𝑊𝑊 /𝑚𝑚2 �
𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 = 𝑊𝑊/𝑚𝑚2)

Projected area is used since our eyes see the projected
area of the surface

8

Steradian

 3D form of radian (recall 0𝑜𝑜 to 3600 corresponds to 0 to
2𝜋𝜋 radian)

𝑠𝑠𝑑𝑑 =
𝑠𝑠𝐴𝐴
𝑠𝑠2

 since the surface area of a sphere with
radius 𝑠𝑠 is 4𝜋𝜋𝑠𝑠2, the total steradian is 4𝜋𝜋

9

differential solid angle
(unit: steradian)

differential surface area (unit 𝑚𝑚2)

radius
dA

r

dw

𝐵𝐵 = 𝐼𝐼𝜋𝜋

10

𝑠𝑠𝐵𝐵 light energy leaving a surface point in the direction
𝜃𝜃,𝜙𝜙 within differential solid angle 𝑠𝑠𝑑𝑑 per unit time per unit

surface area

Intensity 𝐼𝐼 of the diffuse reflection in the direction 𝜃𝜃,𝜙𝜙 is

11

𝐼𝐼 =
𝑠𝑠𝐵𝐵

𝑠𝑠𝑑𝑑 𝑐𝑐𝑐𝑐𝑠𝑠𝜙𝜙
(1)

To obtain the total rate of energy radiation from the surface
point, using (1),

𝐵𝐵 = �
ℎ𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒ℎ𝑒𝑒𝑒𝑒𝑒𝑒

𝑠𝑠𝐵𝐵 = �
ℎ𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒ℎ𝑒𝑒𝑒𝑒𝑒𝑒

𝐼𝐼 cos𝜙𝜙 𝑠𝑠𝑑𝑑

For ideal deflector, 𝐼𝐼 is constant in all viewing direction.
Thus,

𝐵𝐵 = 𝐼𝐼 ∫ℎ𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒ℎ𝑒𝑒𝑒𝑒𝑒𝑒 cos𝜙𝜙 𝑠𝑠𝑑𝑑 = 𝐼𝐼𝜋𝜋

If we can calculate 𝐵𝐵, then intensity 𝐼𝐼 can be found by
dividing by 𝜋𝜋

12

Radiosity equations
 A model for the light reflections from the various surfaces is

formed by setting up an “enclosure” of surfaces. Each surface
in the enclosure is either a reflector, an emittor (light source),
or a combination reflector-emitter.

13

Let 𝐵𝐵𝑘𝑘 be the total rate of energy leaving surface 𝑘𝑘 per unit area, i.e., the
radiosity of surface 𝑘𝑘

Definition (form factor) 𝐹𝐹𝑗𝑗𝑘𝑘 is defined as the percentage of radiant energy from
surface 𝑗𝑗 that reaches surface 𝑘𝑘 [unit %]

The sum of the energy contributions from all surfaces in the enclosure arriving
at surface 𝑘𝑘 per unit time per unit area is

𝐻𝐻𝑘𝑘 = �
𝑗𝑗

𝐵𝐵𝑗𝑗𝐹𝐹𝑗𝑗𝑘𝑘

For a scene with 𝑠𝑠 surfaces in the enclosure,

𝐵𝐵𝑘𝑘 = 𝐸𝐸𝑘𝑘 + 𝜌𝜌𝑘𝑘𝐻𝐻𝑘𝑘 = 𝐸𝐸𝑘𝑘 + 𝜌𝜌𝑘𝑘�
𝑗𝑗

𝐵𝐵𝑗𝑗𝐹𝐹𝑗𝑗𝑘𝑘

𝐸𝐸𝑘𝑘 is the emitter radiosity if surface 𝑘𝑘 is also a light source
𝜌𝜌𝑘𝑘 is the reflectivity factor for surface 𝑘𝑘 (plays the same role as 𝑘𝑘𝑑𝑑 in the
diffuse reflection model

14

The radiosity equation matrix
𝐵𝐵𝑘𝑘 = 𝐸𝐸𝑘𝑘 + 𝜌𝜌𝑘𝑘𝐻𝐻𝑘𝑘 = 𝐸𝐸𝑘𝑘 + 𝜌𝜌𝑘𝑘�

𝑗𝑗

𝐵𝐵𝑗𝑗𝐹𝐹𝑗𝑗𝑘𝑘

Re-arranging

1 − 𝜌𝜌𝑘𝑘𝐹𝐹𝑘𝑘𝑘𝑘 𝐵𝐵𝑘𝑘 − 𝜌𝜌𝑘𝑘�
𝑗𝑗≠𝑘𝑘

𝐵𝐵𝑗𝑗𝐹𝐹𝑗𝑗𝑘𝑘 = 𝐸𝐸𝑘𝑘 𝑘𝑘 = 1, 2, … , 𝑠𝑠

We shall show later that all the form factors can be pre-calculated from the
scene geometry. Thus, the above gives a linear system of 𝑠𝑠 equations in 𝑠𝑠
unknowns. The unknowns are 𝐵𝐵1, … ,𝐵𝐵𝑛𝑛

1 − 𝜌𝜌1𝐹𝐹11 −𝜌𝜌1𝐹𝐹21 ⋯ −𝜌𝜌1𝐹𝐹𝑛𝑛1
−𝜌𝜌2𝐹𝐹12 1 − 𝜌𝜌2𝐹𝐹22 ⋯ −𝜌𝜌2𝐹𝐹𝑛𝑛2

⋮ ⋮ ⋮
−𝜌𝜌𝑛𝑛𝐹𝐹1𝑛𝑛 −𝜌𝜌𝑛𝑛𝐹𝐹2𝑛𝑛 ⋯ 1 − 𝜌𝜌𝑛𝑛𝐹𝐹𝑛𝑛𝑛𝑛

𝐵𝐵1
𝐵𝐵2

𝐵𝐵𝑛𝑛

=

𝐸𝐸1
𝐸𝐸2

𝐸𝐸𝑛𝑛

which can be solved by standard techniques (e.g. Gaussian elimination)
15

Rendering the image

 Divide the enclosure into small image
patches

 After the radiosity 𝐵𝐵 of each patch is

found, use 𝐼𝐼 = 𝐵𝐵
𝜋𝜋

 A smooth scene can be obtained by Gouraud shading
 Note that generation of new scene from any new viewpoint is easy and fast

16

Properties of the form factor matrix
The form factor matrix is

𝐹𝐹11 … 𝐹𝐹1𝑛𝑛

𝐹𝐹𝑛𝑛1 ⋯ 𝐹𝐹𝑛𝑛𝑛𝑛

Property 1 : Conservation of energy


𝑘𝑘=1

𝑛𝑛

𝐹𝐹𝑗𝑗𝑘𝑘 = 1 𝑓𝑓𝑐𝑐𝑠𝑠 𝑠𝑠𝑎𝑎𝑎𝑎 𝑗𝑗

Property 2 : Uniform light reflection
𝐴𝐴𝑗𝑗𝐹𝐹𝑗𝑗𝑘𝑘 = 𝐴𝐴𝑘𝑘𝐹𝐹𝑘𝑘𝑗𝑗

Property 3 : For convex or plane surface patch only
𝐹𝐹𝑗𝑗𝑗𝑗 = 0

17

Derivation of the form factor

 We wish to show

𝐹𝐹𝑗𝑗𝑘𝑘 =
1
𝐴𝐴𝑗𝑗

𝑒𝑒𝑠𝑠𝑒𝑒𝑠𝑠𝑗𝑗


𝑒𝑒𝑠𝑠𝑒𝑒𝑠𝑠𝑘𝑘

cos𝜙𝜙𝑗𝑗 cos𝜙𝜙𝑘𝑘
𝜋𝜋𝑠𝑠2

𝑠𝑠𝐴𝐴𝑘𝑘𝑠𝑠𝐴𝐴𝑗𝑗

 That is, the form factor only depends on scene geometry, as 𝐴𝐴𝑗𝑗 ,𝜙𝜙𝑗𝑗 ,𝜙𝜙𝑘𝑘 , 𝑠𝑠
only depends on the scene and can be pre-calculated.

18

Consider two small surface elements 𝑠𝑠𝐴𝐴𝑗𝑗 and 𝑠𝑠𝐴𝐴𝑘𝑘 on surface 𝑗𝑗 and 𝑘𝑘.

Using (1), 𝑠𝑠𝐵𝐵𝑗𝑗 = 𝐼𝐼𝑗𝑗 cos𝜙𝜙𝑗𝑗 𝑠𝑠𝑑𝑑

Rate of radiant energy falling on 𝑠𝑠𝐴𝐴𝑘𝑘 from surface element 𝑠𝑠𝐴𝐴𝑗𝑗 is

𝑠𝑠𝐵𝐵𝑗𝑗𝑠𝑠𝐴𝐴𝑗𝑗 = (𝐼𝐼𝑗𝑗 cos𝜙𝜙𝑗𝑗𝑠𝑠𝑑𝑑)𝑠𝑠𝐴𝐴𝑗𝑗 (2)

Solid angle 𝑠𝑠𝑑𝑑 can be written in terms of projection of the element 𝑠𝑠𝐴𝐴𝑘𝑘
perpendicular to the direction 𝑠𝑠𝐵𝐵𝑗𝑗

𝑠𝑠𝑑𝑑 = 𝑑𝑑𝑑𝑑
𝑒𝑒2

= 𝑑𝑑𝑑𝑑𝑘𝑘 cos 𝜙𝜙𝑘𝑘
𝑒𝑒2

(3)

Combine (2) and (3)

𝑠𝑠𝐵𝐵𝑗𝑗𝑠𝑠𝐴𝐴𝑗𝑗 =
𝐼𝐼𝑗𝑗 cos𝜙𝜙𝑗𝑗 𝑐𝑐𝑐𝑐𝑠𝑠𝜙𝜙𝑘𝑘𝑠𝑠𝐴𝐴𝑗𝑗𝑠𝑠𝐴𝐴𝑘𝑘

𝑠𝑠2
(4)

19

By definition, form factor between two surfaces is the % of energy emanating
from area 𝑠𝑠𝐴𝐴𝑗𝑗 that are incident on 𝑠𝑠𝐴𝐴𝑘𝑘

𝐹𝐹𝑑𝑑𝑑𝑑𝑗𝑗,𝑑𝑑𝑑𝑑𝑘𝑘 =
𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑒𝑒𝑒𝑒 𝑠𝑠𝑠𝑠𝑐𝑐𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑐𝑐𝑠𝑠 𝑠𝑠𝐴𝐴𝑘𝑘
𝑠𝑠𝑐𝑐𝑠𝑠𝑠𝑠𝑎𝑎 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑒𝑒𝑒𝑒 𝑎𝑎𝑠𝑠𝑠𝑠𝑙𝑙𝑠𝑠𝑠𝑠𝑒𝑒 𝑠𝑠𝐴𝐴𝑗𝑗

=
𝑠𝑠𝐵𝐵𝑗𝑗𝑠𝑠𝐴𝐴𝑗𝑗
𝐵𝐵𝑗𝑗𝑠𝑠𝐴𝐴𝑗𝑗

=
𝐼𝐼𝑗𝑗 cos𝜙𝜙𝑗𝑗 𝑐𝑐𝑐𝑐𝑠𝑠𝜙𝜙𝑘𝑘𝑠𝑠𝐴𝐴𝑗𝑗𝑠𝑠𝐴𝐴𝑘𝑘

𝑠𝑠2

1
𝐵𝐵𝑗𝑗𝑠𝑠𝐴𝐴𝑗𝑗

=
𝐼𝐼𝑗𝑗 cos𝜙𝜙𝑗𝑗 𝑐𝑐𝑐𝑐𝑠𝑠𝜙𝜙𝑘𝑘𝑠𝑠𝐴𝐴𝑘𝑘

𝑠𝑠2𝐵𝐵𝑗𝑗

=
cos𝜙𝜙𝑗𝑗 𝑐𝑐𝑐𝑐𝑠𝑠𝜙𝜙𝑘𝑘

𝜋𝜋𝑠𝑠2
𝑠𝑠𝐴𝐴𝑘𝑘

The fraction of emitted energy from area 𝑠𝑠𝐴𝐴𝑗𝑗 incident on the entire surface 𝑘𝑘 is

𝐹𝐹𝑑𝑑𝑑𝑑𝑗𝑗𝑑𝑑𝑘𝑘 = �
𝑒𝑒𝑠𝑠𝑒𝑒𝑠𝑠𝑘𝑘

cos𝜙𝜙𝑗𝑗 𝑐𝑐𝑐𝑐𝑠𝑠𝜙𝜙𝑘𝑘
𝜋𝜋𝑠𝑠2

𝑠𝑠𝐴𝐴𝑘𝑘

where 𝐴𝐴𝑘𝑘 is the surface area of surface 𝑘𝑘
20

using (4)

using 𝐵𝐵𝑗𝑗 = 𝐼𝐼𝑗𝑗𝜋𝜋

𝐹𝐹𝑗𝑗𝑘𝑘 is the area average of the above expression, which is

𝐹𝐹𝑗𝑗𝑘𝑘 =
1
𝐴𝐴𝑗𝑗

𝑒𝑒𝑠𝑠𝑒𝑒𝑠𝑠𝑗𝑗

𝐹𝐹𝑑𝑑𝑑𝑑𝑗𝑗𝑑𝑑𝑘𝑘 𝑠𝑠𝐴𝐴𝑗𝑗

=
1
𝐴𝐴𝑗𝑗

𝑒𝑒𝑠𝑠𝑒𝑒𝑠𝑠𝑗𝑗


𝑒𝑒𝑠𝑠𝑒𝑒𝑠𝑠𝑘𝑘

cos𝜙𝜙𝑗𝑗 cos𝜙𝜙𝑘𝑘
𝜋𝜋𝑠𝑠2

𝑠𝑠𝐴𝐴𝑘𝑘𝑠𝑠𝐴𝐴𝑗𝑗

The double integrals in the above equation can be calculated using a numerical
integration technique called hemi-cube method

Figure from A. Watt, 3D Computer Graphics 3rd Ed.

Based on the observation that
numerical integration on the
hemi-sphere is equivalent
to numerical integration on
the hemi-cube

Pros and Cons

 Programs with the standard radiosity method
 Form factor computation is computationally intensive
 𝑠𝑠 is large, to solve a system of linear equations with 𝑠𝑠

variables, 𝑂𝑂(𝑠𝑠3) is required
 Storage of form factors require 𝑂𝑂(𝑠𝑠2) (not so

important with today’s storage capability)

 Advantage
 Once calculated, it is easy and fast to generate a new

scene

22

Progressive refinement radiosity
method
 Approximate method
 Compute and store form factors on-the-fly
 Much quicker than solving linear system of equations

𝐵𝐵𝑗𝑗 due to 𝐵𝐵𝑘𝑘 = 𝜌𝜌𝑗𝑗𝐵𝐵𝑘𝑘𝐹𝐹𝑘𝑘𝑗𝑗

By uniform light reflection, 𝐴𝐴𝑘𝑘𝐹𝐹𝑘𝑘𝑗𝑗 = 𝐴𝐴𝑗𝑗𝐹𝐹𝑗𝑗𝑘𝑘. Thus

𝐵𝐵𝑗𝑗 due to 𝐵𝐵𝑘𝑘 = 𝜌𝜌𝑗𝑗𝐵𝐵𝑘𝑘𝐹𝐹𝑗𝑗𝑘𝑘
𝑑𝑑𝑗𝑗
𝑑𝑑𝑘𝑘

This conversion is to facilitate computation of 𝐹𝐹𝑗𝑗𝑘𝑘 by the hemi-cube method

23

Algorithm

 Keep a store of radiosity for each patch
 Selects the brightest patch, i.e., the surface patch with the highest 𝐸𝐸𝑘𝑘𝐴𝐴𝑘𝑘
 Calculate all form factors 𝐹𝐹𝑗𝑗𝑘𝑘 and shoot light from the patch 𝑘𝑘 to all other

patches 𝑗𝑗
 Selects a patch with the highest received radiosity and iterate

24

Initialize: Set 𝐵𝐵𝑘𝑘 and store Δ𝐵𝐵𝑘𝑘 to 𝐸𝐸𝑘𝑘

Repeat
select the patch with the highest Δ𝐵𝐵𝑘𝑘𝐴𝐴𝑘𝑘

for each patch 𝑗𝑗 (𝑗𝑗 ≠ 𝑘𝑘) {

∆𝑠𝑠𝑠𝑠𝑠𝑠 = 𝜌𝜌𝑗𝑗𝐵𝐵𝑘𝑘𝐹𝐹𝑗𝑗𝑘𝑘
𝑑𝑑𝑗𝑗
𝑑𝑑𝑘𝑘

// radiosity received by 𝑗𝑗 due to 𝑘𝑘

∆𝐵𝐵𝑗𝑗 = ∆𝐵𝐵𝑗𝑗 + ∆𝑠𝑠𝑠𝑠𝑠𝑠 // store up radiosity
𝐵𝐵𝑗𝑗 = 𝐵𝐵𝑗𝑗 + ∆𝑠𝑠𝑠𝑠𝑠𝑠 // update total radiosity

}
∆𝐵𝐵𝑘𝑘 = 𝜌𝜌𝑘𝑘𝐵𝐵𝑘𝑘𝐹𝐹𝑘𝑘𝑘𝑘 // patch 𝑘𝑘 receives some radiosity from itself

// if 𝐹𝐹𝑘𝑘𝑘𝑘 ≠ 0. Otherwise set ∆𝐵𝐵𝑘𝑘 to 0

display the intermediate scene { … 𝐼𝐼𝑘𝑘 =
𝐵𝐵𝑘𝑘
𝜋𝜋

…}

until (convergence)

25

 Physical meaning: The solution approximates the propagation of light
through an environment. For example, in reality, for a light source such as
sunlight streaming through a window, most of the ambient light comes from
the first bounce of the light from the surfaces in the room. A scene
rendered this way will progressively goes from dark to bright, since those
not directly illuminated by the first ray of the sun will stay dark in the first
iteration.

26

27https://en.wikipedia.org/wiki/Radiosity_(computer_graphics)

https://en.wikipedia.org/wiki/Radiosity_(computer_graphics)

Radiosity : Selection of advanced topics
Intended Learning Outcome
Radiosity models some phenomenon in nature
Radiosity
Characteristics
Limitations
Radiosity model
Definitions
Steradian
𝐵=𝐼𝜋
Slide Number 11
Slide Number 12
Radiosity equations
Slide Number 14
The radiosity equation matrix
Rendering the image
Properties of the form factor matrix
Derivation of the form factor
Slide Number 19
Slide Number 20
Slide Number 21
Pros and Cons
Progressive refinement radiosity method
Algorithm
Slide Number 25
Slide Number 26
Slide Number 27