Christoph Hormann wrote:

> Jim McElhiney wrote:
> >
> > [...]
> > Not even sure how the POV team works these days,
> > i.e., who keeps the ball for making new official patches, or
> > (for that matter) whether or not anyone is interested in my bug fixes.
>
> In case of bug fixes i'm pretty sure the Team is interested in including
> them in the next official release (3.51).  If you have more elaborate
> changes this will be greatly appreciated for MegaPOV (3.51 is a bugfix
> release so there will be no new features).
>

I'll see whether I can work up changes that are small enough that
everyone will agree they're bug fixes.  (it becomes a judgment
call at some point!)

>
> While you are here - something that has wondered some of us lately is how
> the 1600 sample ray directions which are hardcoded in the program are
> originally generated.  There have been some affords to generate a better
> distribution (and the possibility to use more than 1600 rays).
>

The 1600 samples were created by a fairly sophisticated program
(given the apparent simplicity of the problem), which I might, or might
not, be able to find kicking around.  I spend MANY days on it.  (really!)
Basically, it tries to meet the following criteria:
- Lambert's cosine law.  i.e., for perfectly diffuse surfaces, contribution
for an angle rolls off as you go away from normal in a cosine fashion.
- Equal distribution axially.  (same around the circle).
- Evenly distributed spots, without a regular grid which could produce
aliasing.  Same idea as jittering, but hopefully better.
- Better than random or jittered distribution:  you want samples which are
(after taking into account Lambert) nearly equidistant, no matter how many
samples you have chosen.  Poisson disc is a good example.
- Good coverage at low angles.  I found a fairly naive implementation
did not manage this, and it caused nasty artifacts.  The reason is that
things close to the horizon do not contribute very much to the diffuse
interreflection coverage, but the points are also used for other things,
such as calculating the distance to the nearest object.  If you miss
a low-lying object...think of a pencil on a table, by itself in a very large
room...you get into big problems.  A point on the table surface a short
distance from the pencil will miss the pencil entirely, and end up with a very
large effective radius.  Therefore, its value will get used under the pencil,
which is bad--you should be using local values almost exclusively.  This is
also the reason I put in the distance_max feature--not a very elegant
solution.


So, the final method was:
1 - put the first few points into hand picked locations to handle
the horizon problem.  (first and second rows).  Fix them in place.
2 - spray N points onto the sphere  (e.g., N=50)
3 - use simulated annealing to move them around, so that they
repel each other (using the cosine weighting for the repulsive force).
Start with a very high temperature:  points can jump over each other.
4 - Fix those N points into place.
5  - repeat from step 2 till you hit the max you're going to support.

This means that, for any count which is an increment of N, the
points are pretty optimally distributed according to the chosen criteria.
If you build a POV file from the locations (using them as the centres
of small spheres, for example), you will see this effect.
Needless to say, the order in the file is significant.

1600 was chosen since it fits into a series 50,100,200,400,800,1600
very well.  Also, I figured that at some point someone would complain
about a big include file.

Note, if you have artifacts in a picture for which you want very high
quality output, it is 99% certainty that the problem is a bug in the
software (sorry) or the choice of other parameters, and <1% chance
you really need more samples.
Generally you want to aim for the goal of having each final sample
use an average of 20-ish old samples, but not from too far away.
Typically the existing released code achieves an average of about 2.
The number of rays in each old sample point is usually less significant
to the overall smoothness achieved.

Hope this helps!
Jim

Post a reply to this message

[..]
> 1600 was chosen since it fits into a series 50,100,200,400,800,1600
> very well.  Also, I figured that at some point someone would complain
> about a big include file.

interesting, thank you for the explanation. Does it mean that it's better to
choose a value for count which has a factor of 50 ?

> Note, if you have artifacts in a picture for which you want very high
> quality output, it is 99% certainty that the problem is a bug in the
> software (sorry) or the choice of other parameters, and <1% chance
> you really need more samples.

Some people were wondering why there were still some artifacts even for high
counts, if you've managed to fix it this is really great news ! Thank you !

> Generally you want to aim for the goal of having each final sample
> use an average of 20-ish old samples, but not from too far away.
> Typically the existing released code achieves an average of about 2.
> The number of rays in each old sample point is usually less significant
> to the overall smoothness achieved.

You mean the nearest_count should be 20 ? This seems quite a lot (the doc
says the default value is 5), isn't there a risk to smooth too much the
result ?

I don't know if it's worth investigating but I've come across a paper
(http://wfmh.org.pl/~thorgal/jatrac/papers/iccvg02-mskm-gradients.pdf)
suggesting to take more sample locations according to local lightning
distribution to improve Ward's original irradiance caching

M

Post a reply to this message

Jim McElhiney wrote:
> 
> [...]
> 
> The 1600 samples were created by a fairly sophisticated program
> (given the apparent simplicity of the problem), which I might, or might
> not, be able to find kicking around.  I spend MANY days on it.  (really!)
> Basically, it tries to meet the following criteria:
> [...]

That complies well with the observations that have been made with the
sample set, namely that it is fairly good at certain count values but
quite limited for values in between.  When you use 'normal on' in
radiosity (i think this was added by Nathan) it is not guaranteed that the
first N samples are actually used when you use 'count N'.  Another
observation i made was that the sample distribution has a 'rim' structure
at low counts (a lot of samples at the same elevation/theta values, this
could be caused by the way you solved the 'horizon problem').

The changes that will be in next Megapov concerning this are:

- alternative custom (specified in the script) or generated (halton
sequence) sample sets.  The latter is already available in MLPov:

http://martial.rameaux.free.fr/mael/mlpov083.html

- optional random rotation of the sample set around the normal vector. 
This was suggested by Michael Andrews:

Subject: Re: Radiosity flouroescent lighting troubles
Date: Thu, 28 Nov 2002 13:07:10 +0000
From: Michael Andrews <m.c### [at] readingacuk>
Newsgroups: povray.advanced-users

and works quite well in many cases.  

> 
> Note, if you have artifacts in a picture for which you want very high
> quality output, it is 99% certainty that the problem is a bug in the
> software (sorry) or the choice of other parameters, and <1% chance
> you really need more samples.

You need quite a lot of samples when you have strong local variation of
brightness i.e. small and very bright objects.  Of course it is quite
possible that there is a bug somewhere so it needs more samples to produce
smooth results than really necessary.

I tested your suggestion about ot_index and it seems to make some
difference but not much while the difference in speed can be quite
significant (more than twice the time in one test).  It could of course be
that i just tested with the wrong kind of scene and settings.

Christoph

-- 
POV-Ray tutorials, include files, Sim-POV,
HCR-Edit and more: http://www.tu-bs.de/~y0013390/
Last updated 17 Jun. 2003 _____./\/^>_*_<^\/\.______

Post a reply to this message

Mael wrote:

> [..]
> > 1600 was chosen since it fits into a series 50,100,200,400,800,1600
> > very well.  Also, I figured that at some point someone would complain
> > about a big include file.
>
> interesting, thank you for the explanation. Does it mean that it's better to
> choose a value for count which has a factor of 50 ?
>

Short answer:  Yes, a little, maybe.
Long answer:  I admit I can't remember what number I used for "N"
in the annealing process.  I think it started at 50, but might have gone
up by more than 50 at some point after that (like 100 or 200, but also a
good chance I just doubled each time:  50, 100, 200, 400, 800, 1600).
It would only be a very small difference:  the points are known to be
very evenly distributed at each step up in count, because of the annealing.
Between those step points, you have the evenly distributed ones up to the
previous step, and a randomly selected subset of the ones making
up the next annealed set interspersed between them.
The difference between random and evenly distributed is very small,
especially at such high counts.
Numbers under 50 are bad, since they are not randomly distributed.
(this is working from memory from about 7 years ago...)
It is true that I always use a number from the series 50,100,200,400...


>
> > Note, if you have artifacts in a picture for which you want very high
> > quality output, it is 99% certainty that the problem is a bug in the
> > software (sorry) or the choice of other parameters, and <1% chance
> > you really need more samples.
>
> Some people were wondering why there were still some artifacts even for high
> counts, if you've managed to fix it this is really great news ! Thank you !
>

Well, I've got some of the bugs fixed.  I'm intent on making it at least
work as designed;  whether that's good enough or not, we'll see.
Based on Murphy's law, it will probably necessitate at least one change
to how it works as seen by the user, but I'll try to keep things
consistent for now.

>
> > Generally you want to aim for the goal of having each final sample
> > use an average of 20-ish old samples, but not from too far away.
> > Typically the existing released code achieves an average of about 2.
> > The number of rays in each old sample point is usually less significant
> > to the overall smoothness achieved.
>
> You mean the nearest_count should be 20 ? This seems quite a lot (the doc
> says the default value is 5), isn't there a risk to smooth too much the
> result ?
>

More smoothing is in fact what you want, provided you don't use samples
which are so far away that they didn't take into account objects which are
now close to you.  Generally, you want a very smooth
lighting effect on a simple plain.  There are two ways to get it.  Interpolate
very carefully between VERY accurate samples, or average lots of them, so
any minor errors are not visible.
There are big problems with the first (zillions of special cases that are
handled only approximately by this whole class of algorithm), so the second
is your best bet.  This is something that I never fully appreciated when I
first wrote the system.
The max *allowable* nearest count (MAX_NEAREST_COUNT in
radiotit.h) should be much higher, say 50.  (very few resources, there is only
one
structure which has an array of this size.  The code runs a linear scan through
these for each point reused, but with nearest_count=K, that's only <K/2
floating point compares each, which isn't much.)
The runtime max "nearest_count" default should be much higher than 5.
I've been trying numbers around 19-25 lately, and about 20 works best for
my current test scene.  (if points are on a hex grid, 19 would
equate to one point and all its neighbours within distance 2).

Another big problem is with discontinuities in the final trace.
Because of the desire for lots of old samples to average, and the desire
not to do any more samples (or very few) in the final trace pass, I
recommend a low-to-moderate error bound, a moderate trace count, and
a very low low_error_factor.  Try around 0.22  (roughly 1/sqrt(20)).
But be sure to add the fix (hack) for the ot_ins parameter of at least 5 or so,
since the tree gets traversed with the *final* error_bound on the last pass,
which will be 5 times bigger than during the earlier ones.
If you're using recursion >1, increase it by 1.4 for each additional depth too.

Note, if you like hacking and one an image to look a bit better, there's
another hack which helps a bit:  do the final rendering pass completely
twice.  Not as slow as you might think, since you're guaranteed not
to calculate any new radiosity samples.

But, I shouldn't be blathering about hacks, I should be off fixing the
bugs.

>
> I don't know if it's worth investigating but I've come across a paper
> (http://wfmh.org.pl/~thorgal/jatrac/papers/iccvg02-mskm-gradients.pdf)
> suggesting to take more sample locations according to local lightning
> distribution to improve Ward's original irradiance caching
>

I'll have a look at it.  In effect, the system already has some of this very
indirectly,
since it has many metrics of error which are used to estimate what the
nearby gradient should be, and increases its samples (decreases the
spacing beteween them) accordingly.  But the paper's abstract looks interesting,

I'll have a deeper look.
The existing system already calculates an estimate of rate of change of
illuminance in R, G, and B (dR/dx, dG/dx, dB/dx, dR/dx, dR/dy,...) at each
sample point (though not using Ward's method, the idea is the same).  Certainly
the
effective radius of a point could easily be further adjusted by increasing or
decreasing
the harmonic mean distance based on the local gradient being above or below
average.  Whether this would be an improvement or not, beats me.

Jim

Post a reply to this message

Christoph Hormann wrote:

> Jim McElhiney wrote:
> >
> > [...]
> >
> > The 1600 samples were created by a fairly sophisticated program
> > (given the apparent simplicity of the problem), which I might, or might
> > not, be able to find kicking around.  I spend MANY days on it.  (really!)
> > Basically, it tries to meet the following criteria:
> > [...]
>
> That complies well with the observations that have been made with the
> sample set, namely that it is fairly good at certain count values but
> quite limited for values in between.  When you use 'normal on' in
> radiosity (i think this was added by Nathan) it is not guaranteed that the
> first N samples are actually used when you use 'count N'.

It is certainly designed to work well for any number over 50, but it
is designed around the idea that it should always use indices 1..N.
Using anything else would certainly give problems with the current
rad_data.  It would be better to rotate the whole set of points, then
take 1..N, rather than taking a "slanted" sample from the set.
Or, put in a whole different system, of course.
One school of thought is that any area sampling, such as anti-aliasing
pixel subsampling, should use a simple function which gives you
new points one by one, the first one a bit off centre, and each subsequent
one at the centroid of the largest remaining hole. (an effect which I
think Hammersly and Halton points approximate)  I looked around
for an algorithm to generate this sequence on the fly, but no joy.
I think there is a one-dimensional solution using splits based on
the golden ratio, but never got further on it for 2D.  (I'm confident
a solution for a rectangle could be adapted to the hemisphere).
So, I just generated it once and saved the results.  The big issue
in the choice of algorithm is that it be very fast, if it's done for every
point.  But there isn't really a need to do it for every point.

Interestingly, other implementations simply use an MxN grid of samples
(polar coordinates).  I've sometimes wondered whether some of
the smoothness they get is because of this:  there is sample-to-sample
coherence of the sampling directions, so a given object (say a long
thin object ending somewhere nearby) tends to be
either in, or out, of many adjacent samples, rather than jumping
in and out from sample to sample as a random sampling gives.
I call this "artifical smoothness".  Who's to say it's a bad thing?



> Another
> observation i made was that the sample distribution has a 'rim' structure
> at low counts (a lot of samples at the same elevation/theta values, this
> could be caused by the way you solved the 'horizon problem').
>

Yes, this is on purpose.  It should be harmless as long as the count
is high enough that those samples are not overweighting the horizon.
(at least 50;  I assumed people would be using 100+ if they were
interested in a good looking output).
The artifacts caused by leaving these out could probably be solved
other ways (other implementors just use extremely high sample counts),
but they are a big problem and some effort to avoid them should
be considered.  The "pencil on table" test is a good one.  The higher
the angle of your lowest-angle samples, the lower your max effective
radius has to be to compensate.  The low angle can be low for all
scenes without causing problems, whereas the max effective radius
is always something that has to be tuned, so one could consider the
sample-low-angles fix to be a more robust one.  I spent a long
time trying to find the best tradeoff point for those low angles.
A better solution might be to include some even lower angled points,
but underweight results them appropriately for low sample counts.
I'm sure there are even better solutions out there.

>
> The changes that will be in next Megapov concerning this are:
>
> - alternative custom (specified in the script) or generated (halton
> sequence) sample sets.  The latter is already available in MLPov:
>
> http://martial.rameaux.free.fr/mael/mlpov083.html
>

Sounds like a good idea.
(can't get that link right now (despite being in france!), but I'll try later)

>
> - optional random rotation of the sample set around the normal vector.

Yes, I tried this myself.  Probably a good idea.
It reduced the amount of "artificial smoothness" further:  the scenes
were probably more accurate on average, but at quicker renderings
sometimes looked worse, due to increased blotchiness.

>
>
> >
> > Note, if you have artifacts in a picture for which you want very high
> > quality output, it is 99% certainty that the problem is a bug in the
> > software (sorry) or the choice of other parameters, and <1% chance
> > you really need more samples.
>
> You need quite a lot of samples when you have strong local variation of
> brightness i.e. small and very bright objects.  Of course it is quite
> possible that there is a bug somewhere so it needs more samples to produce
> smooth results than really necessary.

You're right, sometimes you want to crank the
count way up, go away for the weekend, and have a really nice picture
at the end.  Stochastic sampling isn't really the right way to solve this
problem, but, since we're talking about how to improve a system that
is based on it, you might as well allow it to crunch away when you want
it to.
When I set up the 1600 limit, bear in mind that this was new to everyone,
and no one was really prepared for the huge increase in rendering times.
A higher limit (or, better yet, no limit), is definitely in order.

>
>
> I tested your suggestion about ot_index and it seems to make some
> difference but not much while the difference in speed can be quite
> significant (more than twice the time in one test).  It could of course be
> that i just tested with the wrong kind of scene and settings.

The effect of the bug that I would expect is as follows:  many samples
are getting stored in the ot_ tree at too small a node size, so are not
getting found when you need them.  Therefore, they aren't getting
included in the averages, except when your sample point is very
close to them.  Whether or not they are included is
dependent on which side of the caching tree node's boundary you
are on, so the old sample drops out of the contribution suddenly between
two pixels while its weight is significant, causing discontinuities.  You would

expect these discontinuities in lighting to align with the scene axes, and
to be more pronounced at low nearest_count values, and high
values of low_error_factor.

The quick hack just forces everything to be stored in a bigger node,
so more nodes are looked at when looking for things to average in.
This does take a little more time, since the tree is traversed a lot.
But, I'm kind of surprised that the speed got that much slower.
Probably a small part of it is the tree traversal per se, and a larger
part of it is the execution of the function (ra_avearge_near) which calculates
the weight and averages it in.


Rgds
Jim

Post a reply to this message

Jim McElhiney wrote:
> 
> [...]
> 
> The effect of the bug that I would expect is as follows:  many samples
> are getting stored in the ot_ tree at too small a node size, so are not
> getting found when you need them.  Therefore, they aren't getting
> included in the averages, except when your sample point is very
> close to them.  Whether or not they are included is
> dependent on which side of the caching tree node's boundary you
> are on, so the old sample drops out of the contribution suddenly between
> two pixels while its weight is significant, causing discontinuities.  You would
> 
> expect these discontinuities in lighting to align with the scene axes, and
> to be more pronounced at low nearest_count values, and high
> values of low_error_factor.
> 
> The quick hack just forces everything to be stored in a bigger node,
> so more nodes are looked at when looking for things to average in.
> This does take a little more time, since the tree is traversed a lot.
> But, I'm kind of surprised that the speed got that much slower.
> Probably a small part of it is the tree traversal per se, and a larger
> part of it is the execution of the function (ra_avearge_near) which calculates
> the weight and averages it in.

Yes, this sounds logical.  The stats also say the render with your
modification - while taking much longer - took much less radiosity
samples.  The factor of 4 i used as you suggested could have been simply
too much.  

Christoph

-- 
POV-Ray tutorials, include files, Sim-POV,
HCR-Edit and more: http://www.tu-bs.de/~y0013390/
Last updated 17 Jun. 2003 _____./\/^>_*_<^\/\.______

Post a reply to this message

"Jim McElhiney" <mun### [at] excitecom> wrote...
> Christoph Hormann wrote:
> > That complies well with the observations that have been made with the
> > sample set, namely that it is fairly good at certain count values but
> > quite limited for values in between.  When you use 'normal on' in
> > radiosity (i think this was added by Nathan) it is not guaranteed that
the
> > first N samples are actually used when you use 'count N'.
>
> It is certainly designed to work well for any number over 50, but it
> is designed around the idea that it should always use indices 1..N.
> Using anything else would certainly give problems with the current
> rad_data.  It would be better to rotate the whole set of points, then
> take 1..N, rather than taking a "slanted" sample from the set.

The code does rotate the points, so to speak, to match the normal.  The code
already was capable of doing that, I just changed it to use the perturbed
normal instead of the raw normal (when the user enables the feature).

The problem is similar to problems with combining reflection with a
perturbed normal.  Because the normal is inconsistent with the geometry,
this method shoots some of the sample rays _below_ the surface of the
object, which is not at all what we want.  I choose to simply throw out
those samples and re-shoot them if such a case was detected.

-Nathan

Post a reply to this message

"Jim McElhiney" <mun### [at] excitecom> wrote...
>
> The max *allowable* nearest count (MAX_NEAREST_COUNT in
> radiotit.h) should be much higher, say 50.  (very few resources, there is
only
> one
> structure which has an array of this size.  The code runs a linear scan
through
> these for each point reused, but with nearest_count=K, that's only <K/2
> floating point compares each, which isn't much.)
> The runtime max "nearest_count" default should be much higher than 5.
> I've been trying numbers around 19-25 lately, and about 20 works best for
> my current test scene.  (if points are on a hex grid, 19 would
> equate to one point and all its neighbours within distance 2).

Have you had a look at the POV 3.5 source code yet?  With MegaPOV I made a
number of modifications to your code (without knowing how it _really_
worked, unfortunately) which generally decreased the artifacts.

One important change was to change the nearest_count from a maximum to a
minimum.  I figured there was no good reason to limit the number of points
to re-use.  The code in ra_average_near already kept running sums for
Weights_Times_Illuminances and Weights for all points that it came across.
As long as a point is within the error_bound, it will be utilized.

> Another big problem is with discontinuities in the final trace.
> Because of the desire for lots of old samples to average, and the desire
> not to do any more samples (or very few) in the final trace pass, I
> recommend a low-to-moderate error bound, a moderate trace count, and
> a very low low_error_factor.  Try around 0.22  (roughly 1/sqrt(20)).
> But be sure to add the fix (hack) for the ot_ins parameter of at least 5
or so,
> since the tree gets traversed with the *final* error_bound on the last
pass,
> which will be 5 times bigger than during the earlier ones.
> If you're using recursion >1, increase it by 1.4 for each additional depth
too.

POV 3.5 includes a feature to disable new samples in the final pass.  This
definately decreases splotchiness.  I probably should have enabled it by
default.

Also, in MegaPOV and POV 3.5, I changed the call to ot_index_sphere so that
it always uses the "real" (final) error bound instead of the one that has
been multiplied by low_error_factor.

I made a number of other modifications here and there to the code.  If you
look at them and have questions, sned me an email.  I _might_ remember why I
made the change.  :-)

-Nathan

Post a reply to this message