I've calculated 8000 radiosity samples (see p.b.i and p.b.s-f). As you can
see in the image the 255x255x255 resolution isn't fine enough for lots of
radiosity samples: the image already shows that the distribution has
rectangular artifacts due to rounding errors. Anyhow I'm posting an image
and a zipped set of files in p.b.s-f that you can use to insert the samples
into the POV-Ray source-code. I can't do that myself now, because I'll have
to install another compiler for that :-(

Post a reply to this message

Apache wrote:
> 
> I've calculated 8000 radiosity samples (see p.b.i and p.b.s-f). As you can
> see in the image the 255x255x255 resolution isn't fine enough for lots of
> radiosity samples: the image already shows that the distribution has
> rectangular artifacts due to rounding errors.

It is fairly obvious that using bytes to store the directions is just a
hack to save memory.  Apart from the accuracy problem it also costs some
computation time to unpack the directions for every radiosity sample
taken.  

> Anyhow I'm posting an image
> and a zipped set of files in p.b.s-f that you can use to insert the samples
> into the POV-Ray source-code. I can't do that myself now, because I'll have
> to install another compiler for that :-(

Without any information on how the samples were generated this suffers
from the same problem as the original set of sample directions.  

Christoph

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

Post a reply to this message

> It is fairly obvious that using bytes to store the directions is just a
> hack to save memory.  Apart from the accuracy problem it also costs some
> computation time to unpack the directions for every radiosity sample
> taken.
No need to save memory with this, because we're having more and more RAM
every year :-) And IIRC computers nowadays work as fast with integers
(16bits) as with bytes (8bits).

> Without any information on how the samples were generated this suffers
> from the same problem as the original set of sample directions.

It's a bit like this:

save first sample, offset = 0 (this one is on the exact center of the disk)
samplescalculated = 1
minimumtrials = 1000
repeat until (samplescalculated equals 8000) {
    trialcounter = 0
    besttrialdistance = 10   (doesn't really matter, must be > 2)
    repeat until (trialcounter equals samplecount \
      and trialcounter is greater or equals minimumtrials) {
        create random sample on disk
        if (distance from random sample to nearest sample saved <
besttrialdistance) {
            besttrialdistance = distance random sample to nearest sample
saved
            save random sample, offset = samplescalculated
            trialcounter = 0
        }
    }
    samplescalculated ++
}

save all samples saved to disk

done


Anyhow. The first test with this test set really sucks :-(    Extreme
artifacts!



Here's the source code of the monster:

#include <stdlib.h>
#include <stdio.h>
#include <math.h>


#define SAMPLESAMOUNT       (12000)
#define MINRETRIES          (1000)
#define DISTRIBUTEROUNDS    (200)
#define DISTRIBUTESTEPSIZE  (0.01)
#define PI                  (3.141592653589793238)
#define XMEAN               (127.5)
#define YMEAN               (127.5)
#define XSCALE              (127.5)
#define YSCALE              (127.5)
#define ZSCALE              (127.5)
#define RANDOMVALUE         ((double)rand() / (double)(RAND_MAX))

int main(void) {
  FILE*     filehandle1;
  double*   x              = (double*) malloc(SAMPLESAMOUNT *
sizeof(double));
  double*   y              = (double*) malloc(SAMPLESAMOUNT *
sizeof(double));
  int       i              = 0;


  /******* CREATE DISTRIBUTION *******/

  x[0] = 0.0;
  y[0] = 0.0;

  for (i = 1; i < SAMPLESAMOUNT; i++) {
    int    i2;
    double xnew;
    double ynew;
    double olddist = 0.0;
    int    retry   = 0;

    printf("\rSETUP DISTRIBUTION   : %d of %d", i, SAMPLESAMOUNT);

    for (retry = 0; (retry < i) || (retry < MINRETRIES); retry++) {
      int    j       = 0;
      double mindist = 1001.0;
      double phi     = 2*PI*RANDOMVALUE;
      double sqrtr   = sqrt(RANDOMVALUE);
      xnew           = cos(phi)*sqrtr;
      ynew           = sin(phi)*sqrtr;

      /** determine distance of new sample to nearest existing sample **/
      for (j = 0; j < i; j++) {
        double dx = xnew - x[j];
        double dy = ynew - y[j];
        double d2 = dx*dx + dy*dy;
        if (d2 < mindist) {
          mindist = d2;
        }
      }

      /** if new sample is farther away than the previous one, save it **/
      if (mindist > olddist) {
        x[i]    = xnew;
        y[i]    = ynew;
        olddist = mindist;
        retry   = 0;
      }
    }

  }
  printf("\rsetup distribution   : done                 \r\n");

  /******* WRITE SAMPLES TO DISK *******/

  printf("SAVE SAMPLES TO DISK...");
  filehandle1 = fopen("newraddata.inc", "w");

  fprintf(filehandle1, "#declare Thing1 = union {\r\n");
  for (i = 0; i < SAMPLESAMOUNT; i++) {
    double z = sqrt(1-x[i]*x[i]-y[i]*y[i]);
    fprintf(filehandle1, "  sphere {<%d, %d, %d>, 1.0} //count %d\r\n",
(int)(.5+XMEAN+XSCALE*x[i]), (int)(.5+YMEAN+YSCALE*y[i]),
(int)(.5+ZSCALE*z), i+1);
  }
  fprintf(filehandle1, "}\r\n");

  fclose(filehandle1);
  printf("\rsave samples to disk : done                \r\n\007");

  free(x);
  free(y);

  return (0);
}

Post a reply to this message

> Anyhow. The first test with this test set really sucks :-(    Extreme
> artifacts!
Oh, lucky me. The artifacts are even worse with the original set. I'm
rendering a bunch of tests now which I'll post later on when they're
finished.

Post a reply to this message

And I'm calculating a 12000 samples set. This time I'll get rid of the
255x255x255 problem. Maybe I'll try integers: 65535x65535x65535.

Post a reply to this message

Apache wrote:
> And I'm calculating a 12000 samples set. This time I'll get rid of the
> 255x255x255 problem. Maybe I'll try integers: 65535x65535x65535.

You could use two shorts instead of three, and compute the third with z =
sqrt(1 - x^2 - y^2). Then the memory use would only go up by 33% per sample.
(Besides, it would probably be faster than vnormalizing the whole vector
every time.)

If you get this working, by the way, you could reuse the same table for
focal blur samples, since it is after all a uniform distribution on the
disc.

Anders

--
#macro E(D)(#if(D<2)D#else#declare I=I+1;mod(pow(.5mod(I 6))*asc(substr(
"X0(1X([\\&Q@TV'YDGU`3F(-V[6Y4aL4XFUTD#N#F8\\A+F1BFO4`#bJN61EM8PFSbFA?C"
I/6 1))2)<1#end)#end#macro R(D,I,T,X,Y)#if(E(D))R(D-1I,T,Y/2X)R(D-1I,T+Y
/2Y/2X)#else box{T T+X+Y pigment{rgb E(2)*9}}#end#end R(10,5z*3-1v*2u*2)

Post a reply to this message

In article <3e1b35b0@news.povray.org> , "Anders K." <and### [at] kaseorgcom> 
wrote:

> You could use two shorts instead of three, and compute the third with z =
> sqrt(1 - x^2 - y^2). Then the memory use would only go up by 33% per sample.
> (Besides, it would probably be faster than vnormalizing the whole vector
> every time.)

I never looked at the radiosity code, but it does not use VNormalize insde
the radiosity calculations, does it???

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

In article <3e1b35b0@news.povray.org> , "Anders K." <and### [at] kaseorgcom> 
wrote:

> You could use two shorts instead of three, and compute the third with z =
> sqrt(1 - x^2 - y^2). Then the memory use would only go up by 33% per sample.
> (Besides, it would probably be faster than vnormalizing the whole vector
> every time.)

Never mind, I checked and it really does.  This has to be fixed.  A fix will
be in POV-Ray 3.51.

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

Thorsten Froehlich wrote:
> 
> > You could use two shorts instead of three, and compute the third with z =
> > sqrt(1 - x^2 - y^2). Then the memory use would only go up by 33% per sample.
> > (Besides, it would probably be faster than vnormalizing the whole vector
> > every time.)
> 
> Never mind, I checked and it really does.  This has to be fixed.  A fix will
> be in POV-Ray 3.51.

Be careful, this could possibly 'break' old radiosity scenes because the
directions will slightly differ (although the differences will not be
large of course).  Calculating the direction vectors at the beginning and
not during every ra_gather() call would be a good idea IMO.  I already
made this modification for Megapov in case you want it.

Christoph

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

Post a reply to this message

In article <3E1B3FDE.4F8CC9FA@gmx.de> , Christoph Hormann 
<chr### [at] gmxde>  wrote:

> Be careful, this could possibly 'break' old radiosity scenes because the
> directions will slightly differ (although the differences will not be
> large of course).  Calculating the direction vectors at the beginning and
> not during every ra_gather() call would be a good idea IMO.  I already
> made this modification for Megapov in case you want it.

Already in 3.51, too.  The speed gain does not seem to be too much, though
:-(

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

I use this function in radiosit.cpp:

/***************************************************************************
**
*
* FUNCTION  VGet()  -  Gets 2dimensional src_vec, converts it with
*                      z=sqrt(1-x*x-y*y) into 3dimensional dest_vec.
*
* INPUT
*
* OUTPUT
*
* RETURNS   Nothing
*
* AUTHOUR   Eli Jehoel
*
* DESCRIPTION
*
*  The radiosity rays have been precomputed. For each sample, dz is derived
*  from dx and dy. Ranges of dx and dy are (-1. to 1.), range of dz is
*  (0. to 1.)
*
*  There is no VNormalizing involved in this function in order to gain
speed.
*
* CHANGES
*
*   --- Jan 2002 : Creation.
*
****************************************************************************
**/
static void VGet(VECTOR dest_vec, DOUBLE_XY * src_vec)
{
  dest_vec[X] = src_vec->x;
  dest_vec[Y] = src_vec->y;
  dest_vec[Z] = sqrt(1. - pow(src_vec->x, 2.)-pow(src_vec->x, 2.));
}

Post a reply to this message

Or maybe I should precompute the z values too? It will take 50% more space,
but it saves expensive sqrt calls and some multiplications. Anyone?

Post a reply to this message

"Apache" <apa### [at] yahoocom> wrote in message
news:3e1b6a20@news.povray.org...
> I use this function in radiosit.cpp:
>
>   dest_vec[Z] = sqrt(1. - pow(src_vec->x, 2.)-pow(src_vec->x, 2.));
>

I'm assuming that you meant: dest_vec[Z] = sqrt(1. - pow(src_vec->x,
2.)-pow(src_vec->y, 2.));

If you just cut and pasted this code then you may want to re-run your tests,
because this would make a huge difference.

And I would at least expand pow function to square a value into a single
multiplication for efficiency.

--- Troy S. Ristow

Post a reply to this message

Thanks! Stupid typos ....  :-)  Haven't run the code yet, because I'm
waiting for a set of 12000 samples to finish.

Post a reply to this message

"Apache" <apa### [at] yahoocom> wrote in message
news:3e1bca0a$1@news.povray.org...
> Thanks! Stupid typos ....  :-)  Haven't run the code yet, because I'm
> waiting for a set of 12000 samples to finish.
>

Keep in mind that the reason (in my belief) that the sample set is difficult
to create, is because it must not only be valid for 12000 samples, but also
the first 9000 of that set and the first 6000 and... etc.  (sorry for the
run-on.)

I have worked with creating dither patterns that are built up in this way.
When I get some time I will try to articulate the algorithms I used about 8
years ago to generate a cascading set of blue noise at various intensity
levels.  In the mean time, carry on with the tests, I have a few (always
have something) running in the background.

--- Troy

Post a reply to this message

I have come up with a new algorithm that creates exactly the same set with
extremely high speed. First have to implement it. but probably I can get it
to create a set of 65535 samples in an acceptible time :-)

Post a reply to this message

That's exactly what I've kept in my mind all the time :-) I think "my" set
is pretty good at it.

Post a reply to this message

"Apache" <apa### [at] yahoocom> a écrit dans le message de news:
3e1c2fa1$1@news.povray.org...
> I have come up with a new algorithm that creates exactly the same set with
> extremely high speed. First have to implement it. but probably I can get
it
> to create a set of 65535 samples in an acceptible time :-)

Just a general comment about this "search for more radiosity" samples, which
I sincerely hope will be fruitful and lead to better, faster radiosity.
In my experience, "more samples" doesn't mean "better radiosity". In fact,
this is true between, say, 0 and 500, but after that, having more samples
just doesn't address the artefact issues : radiosity-created splotches just
tend to get smoother and more organised (with some luck, they may look like
natural dirt...) but they're still there and I'm not sure that raising the
count will make them disappear, i.e. more samples will lead asymptotically
to "nice", regular artefacts instead of messy ones. There are even some
cases where having less samples results in locally better results, something
puzzling enough to suggest that some sort of adaptive sampling could be used
(I'm clueless about the whole thing, don't ask for details!).
Anyone has investigated this problem or will raising the count to 65000
actually solve it ?

G.

--

**********************
http://www.oyonale.com
**********************
- Graphic experiments
- POV-Ray and Poser computer images
- Posters

Post a reply to this message

"Apache" <apa### [at] yahoocom> wrote:
>   dest_vec[Z] = sqrt(1. - pow(src_vec->x, 2.)-pow(src_vec->x, 2.));

Why on Earth are you using such an expensive thing as pow() here? It is slow
as hell compared to simple multiplication. What's the catch? Am I missing
something?

Post a reply to this message

Maybe you're right. I don't know. But I know that x*x is faster than
src_vec->x*src_vec->x. Haven't thought about it really. I have this blurry
and faint feeling that the power function is incorporated in most cpus. If
not, please tell me.

Post a reply to this message

I haven't investigated it. If 65000 samples doesn't help, we can always try
to go to 2^32 samples  :-)

Post a reply to this message

Apache wrote:
> Maybe you're right. I don't know. But I know that x*x is faster than
> src_vec->x*src_vec->x.

A reasonably smart compiler will optimize "src_vec->x * src_vec->x" to "x =
src_vec->x; x * x", but I doubt it would change "pow(x, 2)" to "x * x".

> Haven't thought about it really. I have this blurry
> and faint feeling that the power function is incorporated in most cpus. If
> not, please tell me.

Even if pow is included on the CPU, multiplication is much faster (AFAIK).

Anders

--
#macro E(D)(#if(D<2)D#else#declare I=I+1;mod(pow(.5mod(I 6))*asc(substr(
"X0(1X([\\&Q@TV'YDGU`3F(-V[6Y4aL4XFUTD#N#F8\\A+F1BFO4`#bJN61EM8PFSbFA?C"
I/6 1))2)<1#end)#end#macro R(D,I,T,X,Y)#if(E(D))R(D-1I,T,Y/2X)R(D-1I,T+Y
/2Y/2X)#else box{T T+X+Y pigment{rgb E(2)*9}}#end#end R(10,5z*3-1v*2u*2)

Post a reply to this message

In article <3e1c5b48@news.povray.org>,
 "Apache" <apa### [at] yahoocom> wrote:

> I haven't investigated it. If 65000 samples doesn't help, we can always try
> to go to 2^32 samples  :-)

Hmm...4GB per byte of sample. Stored as 3 floats, at 4 bytes each for 12 
bytes a sample, that would be 48GB. If 5 bytes are sufficient, only 20GB.
And I wonder what the render times would be with 4,294,967,296 
samples...the results would be really nice though. Little need for 
photons, with some adjustments most other things could also be done with 
this algorithm.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message

Gilles Tran wrote:
> 
> Just a general comment about this "search for more radiosity" samples, which
> I sincerely hope will be fruitful and lead to better, faster radiosity.
> In my experience, "more samples" doesn't mean "better radiosity". In fact,
> this is true between, say, 0 and 500, but after that, having more samples
> just doesn't address the artefact issues : ...

This is one of the reasons why i have been focussing on finding a better
solution for lower sample counts.  With higher ray counts the differences
between distributions will diminish as long as they maintain the correct
density falloff.

Christoph

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

Post a reply to this message

"Anders K." <and### [at] kaseorgcom> wrote:
> A reasonably smart compiler will optimize "src_vec->x * src_vec->x" to "x
=
> src_vec->x; x * x", but I doubt it would change "pow(x, 2)" to "x * x".
>
> Even if pow is included on the CPU, multiplication is much faster (AFAIK).

Right.

As to the direct support of pow() in the CPU, this is very and very
unlikely... Usually, pow() is implemented as a function that computes its
result using the

x ^ y == 2 ^ (y * log2(x))

formula, with *some* support for the log2(x) in the CPU (power of 2, being a
shift, is quite efficient, of course). log2(x) may easily take a hundred or
so cycles, plus those extra calculations, plus the overhead of the function
call... so, hope you got the idea.

Post a reply to this message

It's just a matter of rewriting the whole POV-Ray package and especially the
octree code so that the calculations and data can be divided over a few
thousand computers with the internet as communication medium. Maybe someone
is willing to hardcode everything into a pure POV-Ray chip? rant rant
rant.............. :-)

Post a reply to this message

What what would be the best (set of) scene(s) to test sets for lower sample
counts.

Post a reply to this message

You folks absolutely convinced me!

Post a reply to this message

I have this set ready for testing. It contains of 3200 samples. I'm
currently running some test scenes while another process is calculating a
set of 32000 samples at low priority (cygwin's nice). I have compiled a
patch of POV-Ray with those 3200 samples. The complete windows source files
(including windows executable) are available for download at
http://24.132.254.158/experiments/elipovray350winvc7src_3200samples.zip (143
kb). For those who only want to download the changed files (for all
platforms):
http://24.132.254.158/experiments/elipovray350_patched_3200samples.zip
(5,721 kb) My upstream here is 15kb/s max, so be patient if it's slow...

Please do some test, I have limited CPU power nowadays...ehhhh... as ever
:-P

Regards,
Apache

Post a reply to this message

I was unable to download the first file, and the second file is source only.

--
Anthony Bennett

Post a reply to this message

I made some mistakes naming the files. Now you *can* download them. And I
mixed up the filesizes too! These are the right links:
http://24.132.254.158/experiments/elipovray350winvc7src_3200samples.zip
(5,721 kb)
http://24.132.254.158/experiments/elipovray350_patched_3200samples.zip (143
kb)

Post a reply to this message

I found a bug. The patch won't improve radiosity quality. I'm recalculating
the set (again)  :-S

Post a reply to this message