Hi,

I've just thought of a way of calculating radiosity that in my mind should
be able to speed up Povray's radiosity pass greatly. Now, I'm no programmer
or expert in this field, so Povray may already calculate radiosity in this
way, or there could be something that I'm not seeing that would greatly slow
down the process, so please bear with me. To help explain the stuff below, I
have mocked up some images in a graphics package, and posted them to
povray.binaries.images in the message "Faster radiosity images (don't get
excited)". Below, I will also be talking about frame rates. I am not talking
about generating Povray images with radiosity at faster than 1 a second! I
will be talking about vector graphics, much like many of the arcade machines
in the early 80s produced. Don't worry, this is still relevant to Povray - I
will be transferring the process below in different ways until I reach
Povray.

Before I get flames over this, read the WHOLE post carefully. First I am
going to describe how I think Povray calculates radiosity, and then I will
build on it to describe what I feel would be a faster and more efficient
system.

For a minute just imagine a 2D vector line world. You have a point that
emits light, three vector line surfaces, and a non-physical line along which
you are going to calculate final radiosity values. (step01.jpg)

Now imagine that our light source emits a single vector line ray of light.
(step02.jpg)

Where this ray of light hits the red vector line, a normal to the red
surface is calculated. Because our original light colour was rgb <1.0, 1.0,
1.0>, and the red surface has a Colour_change property of 0.4, a new light
beam is calculated that had a colour of rgb <1.0, 0.6, 0.6> (i.e. 40% of the
change from rgb <1.0, 1.0, 1.0> to rgb <1.0, 0.6, 0.6>). This new beam
travels away from the red surface at the same angle as the original beam
was, relative to the red surface. The new beam strikes the green
surface.(step03.jpg)

A new normal is calculated, and for similar reasons as above, a new beam
leaves the green surface with a colour of rgb <0.8, 0.678, 0.12>. The new
beam hits the blue surface. (step 4.jpg)

Again a normal is calculated, and a new beam is shot, with a colour of rgb
<0.4, 0.624, 0.561>. Where this beam crosses our final calculation field,
the radiosity colour at that point is displayed. (step05.jpg)

(If my colour calculations as above were a little dodgy, it's because I was
using a graphics package that uses numbers between 0 and 255 to represent
colours, which doesn't translate too well to Povray's 0 to 1 system)

Now, because of the speed of modern computers, I can imagine that such
calculations with 2D vector lines can be done very quickly, giving a few
frames a second of such radiosity calculations, should our line surfaces be
rotating or moving. The reason that our colours stayed relatively bright was
because our light source brightness didn't fade over distance. Such a
darkening of the lines shouldn't slow down the calculation process too much.

Now imagine the same vector setup as above, except in 3D. Instead of line
surfaces, we have three coloured vector rectangles, that can be rotated and
moved in any of the three dimensions. Now, while there should be a hit in
the frame rate at this point as calculating normals in three dimensions is
more complicated that calculating them in two (I'm sure, though I don't know
for certain. Any programmers out there back me up on this one?), I would
still think that a few frames a second could be managed.

Now imagine that our 3D light source shoots out two rays, in slightly
different directions. They each bounce in different ways, depending on what
surfaces they hit or miss. Eventually, they hit our final calculation field,
which is now a rectangle. We now have two different points of two (probably)
different colours. A stripe of interpolated colours fading between our two
colour spots could be drawn.

If four rays are shot from the light source, we end up with four points on
our final calculation field. Interpolating the colours between them gives us
a four sided shape of colour, which is the start of our radiosity system.
However, with each new ray shot from the light source, the whole process
slows dramatically, until eventually, for a complex scene, the radiosity
calculations alone for three light bounces like we have above could take
over half an hour or more! This is, as far as I know, more or less how
Povray operates. If it isn't, would this not be a much better way to
calculate radiosity? It certainly seems like it would be faster to me, for
simple scenes anyway. If that is however how Povray calculates radiosity,
keep reading.

What I propose as a change to this system is the following: instead of
having one count variable that sets how many radiosity samples are
calculated per light, why not let each object have a count variable, and not
let lights have one?

The main problem with giving light sources a count variable, is that in many
scenes, a lot of time is spent calculating radiosity samples that are
wasted; either because the light beam shoots off to somewhere where its
effects will never be seen, or because the object is too small or only
partially in the light. All these useless samples all increase the time it
takes for radiosity to calculate and to trace.

Now, trying to Program Povray with some intelligence as to what to bother
calculating radiosity for, and how high a count to give each object would be
very difficult I imagine. Artificial intelligence today is still pretty new
stuff, especially artistic artificial intelligence :) . It would also lead
to problems with Povray making decisions about the radiosity that the person
making the scene wouldn't agree with.

But by letting the Pov user have control themselves over what count each
object should have, greater artistic control is given to the user, while at
the same time decreasing the amount of time the render takes.

Here is how I envision the system would work. There is a light source, a
sphere and a simple closed, square room. The sphere has a count of 100. The
walls of the room have a count of 50. If the light does not hit the sphere,
then only radiosity for the walls is calculated. This is calculated by
determining what portions of the walls are in the light. Then, 50 points
spread out evenly over the surface of the walls are chosen, and using
normals determined from the angle of the original light, new beams are shot
much like the ones in my 3D vector example above. When these beams hit
objects, radiosity points are found, and a radiosity map is interpolated. If
the sphere is also hit by the light, then 100 points on the surface of the
sphere where it is hit by light are selected (probably also evenly
distributed), and normals and new beams shot also.

Each object could also be given a number_of_bounces variable, that would set
the number of light bounces off the object that would be calculated. If for
example the sphere had a number_of_bounces 2, this would mean that two
generations of radiosity would be allowed to be calculated on its surface,
but no more than that. This could give greater control to the Povray user,
as they could give faraway objects a low number_of_bounces, while giving
closer objects a higher number_of_bounces.

Indeed, faraway objects such as distant trees could be given a count of
zero, meaning that they wouldn't cause radiosity to calculated in the scene
because of them. As standard Povray would calculate this, and it would have
very little effect on the final image anyway, this would be a great time
saver.

One point I can see being raised against this new radiosity system is that
it would remove the possibility of using high ambient objects in a lightless
environment as a light source. For this reason, I propose adding another
variable, ambient_count. This would act much like the per-object radiosity
count as above, except the ambient_count would shoot rays from the entire
surface of the object. The brightness and colour of these rays would depend
on the colour and ambient value of the object at the point where each ray
was calculated. Indeed, this system would have a further use, as the
ambient_count would act like a new type of light source, giving a light that
would depend on the shape of the object. This would make true area_lights
from spheres, cylinders, blobs, meshes etc. possible. I have seen a lot of
requests for this feature posted on the various newsgroups at different
times in the last few years.

Another point I can see being raised is that this new radiosity system is
much more complicated than the old system, and would only end up confusing
people. To that, all I can suggest is that the old radiosity system should
be kept, with this new system implemented *as well*, giving people the
chance to decide which system to use.

I don't profess to have thought of all eventualities. I am sure there are
lots of problems with this system that I have not thought of. But maybe if
we discuss this system, we could work out enough of the problems to begin
designing a working version of the system. Possibly somebody out there who
has experience with creating Povray patches could start experimenting to see
if any of this would be possible. I know that Mr. Nathan Kopp was looking at
the radiosity system when he was working on his excellent Photon Patch. I
also know that in the Povray SuperPatch, there is a feature that allows ray
intersection tests, a feature that would be very important in the above
proposed radiosity system.


I look forward to comments and suggestions.


Yours hopefully,

Equiprawn

Post a reply to this message

On Wed, 30 Jun 1999 15:19:00 +0100, Equiprawn wrote:
>Now imagine that our 3D light source shoots out two rays, in slightly
>different directions. They each bounce in different ways, depending on what
>surfaces they hit or miss. Eventually, they hit our final calculation field,
>which is now a rectangle. We now have two different points of two (probably)
>different colours. A stripe of interpolated colours fading between our two
>colour spots could be drawn.

It could be drawn, but I think it'd be meaningless unless both rays hit all 
the same objects on the way there.

>This is, as far as I know, more or less how
>Povray operates. If it isn't, would this not be a much better way to
>calculate radiosity? It certainly seems like it would be faster to me, for
>simple scenes anyway. If that is however how Povray calculates radiosity,
>keep reading.

Okay, so let me get this straight.  You say "Here's this really slow system.
If this isn't how POV does it, shouldn't it be?"  I'm having trouble grasping
that.

The fact is, this isn't how POV operates.  It doesn't trace any rays starting
with the light sources, for the very reasons you mention below: most of the
samples would be useless.  Instead, it fires a pile of random rays at the 
surrounding scenery whenever it needs to compute radiosity effects for a 
given intersection point, then caches the results for use with other nearby 
points. This ends up handling the most obvious cases of diffuse 
interreflection, such as indirect lighting, while ignoring cases of multiple 
bounces.  Note that there are no fixed counts for any objects, including 
lights.  POV fires an easily computed number of sample rays per intersection 
(if it needs to) but those sample rays are not associated with any one light 
source.

In this model, the number of sample rays for a specific object is highly
dependent on screen area taken up by that object.  Thus, large or close objects 
will be illuminated more carefully.  The number of times an object is the 
target of one of those sample rays is dependent on how visible that object is 
to the source of the sample rays.  Small or faraway objects won't contribute 
much, because they won't be hit by many sample rays.

What you're envisioning is roughly how photon mapping operates, though there 
are additional subtleties in both Nathan's and Jensen's implementation of it 
that are too difficult to talk about in detail here.

>if any of this would be possible. I know that Mr. Nathan Kopp was looking at
>the radiosity system when he was working on his excellent Photon Patch. I
>also know that in the Povray SuperPatch, there is a feature that allows ray
>intersection tests, a feature that would be very important in the above
>proposed radiosity system.

The superpatch feature you're thinking about is only to make the existing ray 
intersection tests available to people writing POV-script. The ray intersection 
tests were all already there, obviously, because that's what a raytracer does.

Post a reply to this message

What you are describing here is the photon mapping principle.
  It's not the way povray calculates radiosity.
  Nathan Kopp's photon mapping patch uses this technique to evaluate true
caustics. It might be used to calculate radiosity too, but it seems to be
too expensive (as you noticed in your text). The caustics are not expensive
because they are calculated on a per-object basis (not for the whole scene).

  Once again, the povray documentation is helpful:

"POV's radiosity system, based on a method by Greg Ward, provides a way to
replace the last term - the constant ambient light value - with a light
level which is based on what surfaces are nearby and how bright in turn they
are."
"How does POV-Ray calculate the ambient term for each point? By sending out
more rays, in many different directions, and averaging the results. A
typical point might use 200 or more rays to calculate its ambient light
level correctly."
"Now this sounds like it would make the ray-tracer 200 times slower. This
is true, except that the software takes advantage of the fact that ambient
light levels change quite slowly (remember, shadows are calculated separately,
so sharp shadow edges are not a problem). Therefore, these extra rays are
sent out only once in a while (about 1 time in 50), then these calculated
values are saved and reused for nearby pixels in the image when possible."

  That is, when povray calculates the illumination of a surface it calculates
the direct illumination from the light sources and then sends lots of rays
to every direction to see what else is illuminating it.

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):5;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

Ahh! It all becomes clear now!

Then what I propose is a radiosity implementation that works on a per object
basis. Could the benefits reaped by photons not also be reaped by radiosity?

Equiprawn

Post a reply to this message

Hi,

>
> It could be drawn, but I think it'd be meaningless unless both rays hit
all
> the same objects on the way there.
>

Why would it be meaningless? One ray might hit the red plane at a certain
angle, and bounce direct to the field. Another might hit off the red, bounce
straight to the blue and ano to the field. With more rays shot, a
comprehensive radiosity map could be drawn.

>
> Okay, so let me get this straight.  You say "Here's this really slow
system.
> If this isn't how POV does it, shouldn't it be?"  I'm having trouble
grasping
> that.

Sorry! I realised just after describing the process that that probably was
how Povray operates. I then went back and tried to make the original text
make sense to a new question I wanted to ask. What I meant to say was
"Here's a really slow system. If this isn't how really really slow POV does
it, shouldn't we use this?" After that, my second method was a second
optimisation that I thought of while I was typing, so I wrote about that as
well. Sorry for the confusion.

>
> The fact is, this isn't how POV operates.  It doesn't trace any rays
starting
> with the light sources, for the very reasons you mention below: most of
the
> samples would be useless.  Instead, it fires a pile of random rays at the
> surrounding scenery whenever it needs to compute radiosity effects for a
> given intersection point, then caches the results for use with other
nearby
> points. This ends up handling the most obvious cases of diffuse
> interreflection, such as indirect lighting, while ignoring cases of
multiple
> bounces.  Note that there are no fixed counts for any objects, including
> lights.  POV fires an easily computed number of sample rays per
intersection
> (if it needs to) but those sample rays are not associated with any one
light
> source.

This is what I was talking about optimising. Instead of firing off random
rays, why doesn't it shoot of rays at the objects? Surely a large portion of
the random rays would be wasted on useless samples?

>
> In this model, the number of sample rays for a specific object is highly
> dependent on screen area taken up by that object.  Thus, large or close
objects
> will be illuminated more carefully.  The number of times an object is the
> target of one of those sample rays is dependent on how visible that object
is
> to the source of the sample rays.  Small or faraway objects won't
contribute
> much, because they won't be hit by many sample rays.

Yes, but are any rays at all still calculated for them? To me, any saving of
time, no matter how small, is a benefit.

> The superpatch feature you're thinking about is only to make the existing
ray
> intersection tests available to people writing POV-script. The ray
intersection
> tests were all already there, obviously, because that's what a raytracer
does.

Ahh, I wasn't 100% sure of what the feature did (never used it myself). But
seeing as it gives output to script writers, I would imagine it would be
more useful than Povray's internal intersection tests for tracing.

Equiprawn

Post a reply to this message

On Thu, 1 Jul 1999 20:43:58 +0100, "Equiprawn" <equ### [at] tinetie>
wrote:

>Ahh! It all becomes clear now!
>
>Then what I propose is a radiosity implementation that works on a per object
>basis. Could the benefits reaped by photons not also be reaped by radiosity?
>
>Equiprawn
>

It is possible to use photons for global illumination purposes, the
this is exactly what you propose. AFAIK Nathan mentioned that he
wouldn't tinker with it for the time being, but you should best ask
him.


Peter Popov
ICQ: 15002700

Post a reply to this message

On Thu, 1 Jul 1999 20:56:11 +0100, Equiprawn wrote:
>Hi,
>
>>
>> It could be drawn, but I think it'd be meaningless unless both rays hit
>all
>> the same objects on the way there.
>>
>
>Why would it be meaningless? One ray might hit the red plane at a certain
>angle, and bounce direct to the field. Another might hit off the red, bounce
>straight to the blue and ano to the field. With more rays shot, a
>comprehensive radiosity map could be drawn.

My point was, the transition between those two rays is not linear.  It's 
probably more like a step function.  So blindly interpolating between them
yields suboptimal results.

>This is what I was talking about optimising. Instead of firing off random
>rays, why doesn't it shoot of rays at the objects? Surely a large portion of
>the random rays would be wasted on useless samples?

In a large scene, it may be more work to build a map of which objects are 
visible in which directions than it is to just fire a few dozen misses.

>Small or faraway objects won't contribute much, because they won't be 
>hit by many sample rays.

>Yes, but are any rays at all still calculated for them? To me, any saving of
>time, no matter how small, is a benefit.

Yes, but only in proportion to how large they appear to the object being
illuminated (and to a probability density that favors light coming in along
the normal)  The result is that the importance of small or faraway objects
is scaled automatically: they contribute little to the light striking an
object in the foreground, but they contribute more to the light striking
an object closer to themselves.  That is how it is in nature, after all.

>Ahh, I wasn't 100% sure of what the feature did (never used it myself). But
>seeing as it gives output to script writers, I would imagine it would be
>more useful than Povray's internal intersection tests for tracing.

I'm not sure I understand this.  The global illumination algorithm you're
proposing would have to be implemented in C to be of any practical use.  In
that case, you would use the intersection tests that already existed in the
official version.  All trace() is is a parser hack that's wrapped around
the existing intersection() call in the POV code.

Post a reply to this message

Having seen the results of similar techniques in GI, i'm a tad sceptical. While
such a method can be very accurate, I believe it would necessitate Monte Carlo
sampling - threreby introducing a lot of noise in the image. Think of the
current media that uses a similar technique.
The beauty of the current GI method is that it's relatively easily integrated
into the POV engine. If you want something better, I would prefer true
radiosity. Implementing this, however, is a daunting task - probably more so
than the photon approach. In particular, it would require meshing the scene into
discrete patches. I'm not sure if Radiance's wavelet method, though... Anybody?

Margus

Peter Popov wrote:
> 
> On Thu, 1 Jul 1999 20:43:58 +0100, "Equiprawn" <equ### [at] tinetie>
> wrote:
> 
> >Ahh! It all becomes clear now!
> >
> >Then what I propose is a radiosity implementation that works on a per object
> >basis. Could the benefits reaped by photons not also be reaped by radiosity?
> >
> >Equiprawn
> >
> 
> It is possible to use photons for global illumination purposes, the
> this is exactly what you propose. AFAIK Nathan mentioned that he
> wouldn't tinker with it for the time being, but you should best ask
> him.
> 
> Peter Popov
> ICQ: 15002700

Post a reply to this message

Actually, Jensen (the guy who originated the photon map technique) has used
photon maps quite successfully with full global illumination.  In my
preliminary tests, I did not find such good results, but I've learned more
about photon mapping since then.

His techniques use a global photon map to improve the speed of the 
gradient-cached MC tecnique (which is what POV uses).  POV does use MC, but
it uses many samples rays per sample point and then interpolates between
sample points.  Adding photons to this means that you use the photon data
to direct the sample rays so that you can use fewer rays with equally good
results.  Relatively few photons are needed to achieve this.  Also, this
technique can achieve more than one level of indirectness by directly
visualizing the photon map after the first bounce (and the photon map
already has many levels of indirectness incorporated already).

I haven't done this yet because I don't fully understand how POV's
radiosity works (the code is not well commented, IMHO).  Is the original
author around to help explain it to me?  Does anybody (Ron?) have links
to Ward's papers on this topic?

-Nathan

Margus Ramst wrote:
> 
> Having seen the results of similar techniques in GI, i'm a tad sceptical. While
> such a method can be very accurate, I believe it would necessitate Monte Carlo
> sampling - threreby introducing a lot of noise in the image. Think of the
> current media that uses a similar technique.
> The beauty of the current GI method is that it's relatively easily integrated
> into the POV engine. If you want something better, I would prefer true
> radiosity. Implementing this, however, is a daunting task - probably more so
> than the photon approach. In particular, it would require meshing the scene into
> discrete patches. I'm not sure if Radiance's wavelet method, though... Anybody?
> 
> Margus
>

Post a reply to this message

On Sat, 03 Jul 1999 11:49:58 -0400, Nathan Kopp <Nat### [at] Koppcom>
wrote:

>I haven't done this yet because I don't fully understand how POV's
>radiosity works (the code is not well commented, IMHO).  Is the original
>author around to help explain it to me?  Does anybody (Ron?) have links
>to Ward's papers on this topic?

I don't have any links to his papers, but I have a half-decent
understanding of POV's implementation.  If you'd like to pick my
brain, feel free.

Post a reply to this message