virtualmeet wrote:
> Ben Chambers <ben### [at] pacificwebguycom> wrote:
>> The problem is, you will LOSE on the quality front.
>> ...
>> You are essentially saying "If you just ditch your quality concerns, and
>> use polygonal tessellation instead, you could have much faster renders!"
> Hi,
> What I'm saying is that there is probaly a way to render images faster by
> using an "intelligent" parser: this "intelligence" came from given it some
> geometrical propertys of points to render. Also, the quality of images will
> be the same.

I don't think you're using the word "parser" in the same way it is used 
in POV-Ray.  The "parser" in POV reads SDL from a file into memory.  You 
seem to be talking about the actual trace code.

> I think that people get confused with what I'm saying because there is a
> deep thought that it's impossible to "improve" the parser (the part of the
> code that perform math functions).

On the contrary, we know its very possible to improve the speed of 
things (speaking of math functions, and not the SDL parser), we just 
don't agree with sacrificing quality for speed.  If we did, we'd be 
using 3DS, Maya, or some other mesh modeler.

> What I'm saying is that the actual way
> of doing math calculations (and this in every field where a parser is
> needed) IS OVER : People should think about using geometrical propertys
> when performing math calculations...

I agree, using all applicable knowledge of a shape can lead to amazing 
speed improvements.  However, it's not the kind of thing which has been 
traditionally possible to teach a computer to do, as each situation is 
highly unique.  And your voxel array certainly doesn't add anything in 
terms of geometric analysis, other than approximation.

> I don't know how well this will work with PovRay but for me I'm already
> doing some calculations more than 30 times faster than before! and I'm

I'd say you're falling short of your potential, then.  If you really 
want a speed bump, properly utilizing a graphics card can give you a 
speed increase of several thousands of times.  However, such methods 
compromise quality in a way which is not accepted by this community.

> To be honest, I start thinking that some heivy demanding math applications
> should be rewritten in the perspective to take advantage of that kind of
> "technologie": The parser should "impose" the way math calculations will be
> done and applications should be adapted to that fact.

When you're a hammer, the whole world looks like a nail...  I'm against 
the system imposing on the user any method, as its a case of the tail 
wagging the dog.  Rather than adapting ourselves (and our programs) to 
fit the current fad system, we should adapt systems to suit our needs.

...Chambers

Post a reply to this message

Ben Chambers <ben### [at] pacificwebguycom> wrote:
> I agree, using all applicable knowledge of a shape can lead to amazing
> speed improvements.  However, it's not the kind of thing which has been
> traditionally possible to teach a computer to do, as each situation is
> highly unique.  And your voxel array certainly doesn't add anything in
> terms of geometric analysis, other than approximation.
Hi,
I confirm you that I'm not doing any approximation and that teaching
computer to take advantage from the geometrical shape is much more easy
than it looks like...
Take an object in 3D space, we have three axes X,Y and Z.
Imagine that for every axe, we can make another one parallel to it (say X1,
Y1 and Z1), that holds vules from an UNARY fct g :
g : X[] ==> X1[]
     x  ==> x' = g(x)

g : Y[] ==> Y1[]
     y  ==> y' = g(y)

g : Z[] ==> Z1[]
     z  ==> z' = g(z)

suppose now that we have to compute an isosurface f(x,y,z) = cos(x) + cos(y)
+ cos(z).
If we define g(u) = cos(u), then our isosurface f can be changed to this :
F(x, y, z, x', z', z') = x' + y' + z'.

Isosurfaces f and F are exactly the same and have the same final shape and
there is no approximation in the final shape made by F. However, F is much
more faster to compute than f because it's only made by 2 additions of 3
varibles where f is  a dumb calculation of 3 cosinus and 2 additions for
the ENTIRE 3D grid.
As you can see, all unary defined fct can be changed to a new variables and
used as this by the new parser.
In the same way, Binary fcts are changed to variables defined in "a plan"
rather than a simple axe : Binary fcts are more demanding in term of memory
requirements but they still computed as fast as unary fcts by the new
parser.

Example :
  f(x,y,z) = x*exp(-x^2-y^2) -z

  Changed to :

   g : X[]*Y[] ===> XY[]
          (x,y)===> v = x*exp(-x^2-y^2)

 finally, now we have "only" to compute : F(x,y,z,v) = v -z

All this variables changes are made possible for use by the parser because
of it's ability to exploit the geometry of the object it's using: That's
why I'm calling it the "geometrical parser".
If you think that it's use is very limited, then think about it again...
I'm now using an implementation that let you define up to 3 unary fcts and
up to 3 binary fcts: That's more than what I need to accelerate
calculations of 100% of my examples.
I hope that I made myself clear to you and in any ways thanks for your
comments and suggestions.
Cheers,
Taha

Post a reply to this message

virtualmeet wrote:
> Hi,
> I confirm you that I'm not doing any approximation and that teaching
> computer to take advantage from the geometrical shape is much more easy
> than it looks like...

...

  > suppose now that we have to compute an isosurface f(x,y,z) = cos(x) 
+ cos(y)
> + cos(z).
> If we define g(u) = cos(u), then our isosurface f can be changed to this :
> F(x, y, z, x', z', z') = x' + y' + z'.
> 
> Isosurfaces f and F are exactly the same and have the same final shape and
> there is no approximation in the final shape made by F. However, F is much
> more faster to compute than f because it's only made by 2 additions of 3
> varibles where f is  a dumb calculation of 3 cosinus and 2 additions for
> the ENTIRE 3D grid.

You ARE making approximations.  You're not approximating the underlying 
shape, however, but you are approximating the values of the cos() function.

In fact, this technique is extremely old, and was widely used as 
recently as 10 years ago.  Since then, computers have become so much 
faster that most people are willing to live with the speed hit in order 
to get the greater accuracy offered by using native CPU instructions.

Remember, POV-Ray is extremely dependent on accuracy.  It has been shown 
in the past that even the step down from double to single precision 
produces unacceptable artifacts in the result, so I'm sure you can 
imagine what a linear interpolation lookup table would do.

Also, this kind of method can wreak havoc (and actually cause a speed 
penalty) in multicore architectures.  First, this data needs to be held 
in memory (and to be truly effective, it *MUST* fit within the L1 cache, 
otherwise it will be slower than the native function call).  Fine when 
you have a few hundred values, even a few thousand.  But how many values 
do you need for the accuracy to be acceptable?  100,000?  1,000,000,000?

OK, let's assume for the moment that you only need 10,000 values for 
this function.  Each one is a double precision float, meaning it takes 
up 64 bits or 8 bytes, so you're taking up 80,000 bytes with this lookup 
table.  That's 78k right there, and several CPUs still on the market 
have a smaller L1 cache than that.

So, let's be extremely generous, and say that only 1,000 values will be 
needed for accuracy.  That's still 7k *per* *function*, and how many 
functions do you need to store this for?  Then of course, you have the 
2D functions, which still take up *7.6MB* *each*.  You'd need a Xeon to 
have a cache that large, even then it's the L3 cache, which is 
considerably slower than the L1.

Of course, you're forgetting that the cache is used for holding more 
than just your lookup tables, so by using it up you're effectively 
preventing the cache from doing whatever else it would normally be doing.

Now, please understand me.  I'm not saying that you can't get a speed 
increase with this method.  I'm saying that if you want anything even 
close to accurate enough for POV-Ray, your dataset would be too large to 
be usable, and you would be better off with the original functions.

...Chambers

Post a reply to this message

Ben Chambers <ben### [at] pacificwebguycom> wrote:
> You ARE making approximations.  You're not approximating the underlying
> shape, however, but you are approximating the values of the cos() function.
Hi,
I really don't see where is the approximation you talking about...
Just to let you know that the original parser (and that's the case of all
mathematical parsers) are using an internal stack to save the intermediate
values. So, by saving the value of cosinus fct (as DOUBLE precision
variable), I'm not doing something that the original parser wasn't doing.
The actual parsers are doing the same thing by storing intermediate values
in the stack. What you're saying can be true if the CPU holds an internal
fct defined like the original isosurface formulas but that is not the case
because the CPU implement only basic fcts like "+", "-", cos,...
> Also, this kind of method can wreak havoc (and actually cause a speed
> penalty) in multicore architectures.  First, this data needs to be held
> in memory (and to be truly effective, it *MUST* fit within the L1 cache,
> otherwise it will be slower than the native function call).  Fine when
> you have a few hundred values, even a few thousand.  But how many values
> do you need for the accuracy to be acceptable?  100,000?  1,000,000,000?

You're right about the importance of the cache (I explained that in previous
messages) but for this too I have a solution : I'm using a 64 parallel
instructions inside the parser. I know that the CPU is never looking for a
single value to store in the L1 cache(when it needs a value, it's storing a
bunch of consecutives ones in L2 in case it needs another values near the
original one). The 64 values have then a big chance to be stored "in the
same time" in the cache L1 and then to be processed at the speed of light.
Tests shows that a 64 parallel operations inside the parser is almost as
fast as a 512 or even a 1000 operations and this is due to the amount of
memory cache inside the CPU. CPU have more and more L1 cache memory, so
this "technologie" is working good now, but will work even better tommorow:
It's somehow a "scalable" technic

> I'm saying that if you want anything even
> close to accurate enough for POV-Ray, your dataset would be too large to
> be usable, and you would be better off with the original functions.
Sorry to say it again, but I really don't see from where the loss of
precision for PovRay can came from in case it's using this technic: In the
deepest level, PovRay is using "only" the CPU "welded" fcts...
Cheers,
Taha

Post a reply to this message

virtualmeet wrote:
> Sorry to say it again, but I really don't see from where the loss of
> precision for PovRay can came from in case it's using this technic: In the
> deepest level, PovRay is using "only" the CPU "welded" fcts...
> Cheers,
> Taha

OK, let me clarify something.  Are you saying that
a) your procedure will first evaluate a function X number of times and 
store the result, looking and values in this table later and, if it 
can't find them, interpolating values?

or b) your procedure will, as functions are evaluated, store the result 
of those evaluations in a lookup table which is then referenced later in 
case the same function with the same input needs to be called again?

If it's a), then the interpolation is the approximation.  This is the 
method I believed you were espousing, and if I was mistaken then I 
apologize.

If it's b), then I would wonder how often a function will be called with 
input identical to a previous one.  I suppose tests would have to be 
done to determine whether or not this would actually benefit, and those 
would have to be done on an application - by application basis.

...Chambers

Post a reply to this message

Ben Chambers <ben### [at] pacificwebguycom> wrote:
> a) your procedure will first evaluate a function X number of times and
> store the result, looking and values in this table later
Hi ,
That's it : I'm evaluating some defined fcts and store them in some tables
for a further use....as a variables. That's very important to think about
thoses tables as tables for NEW VARIABLES. I'll explain after why.

> and, if it can't find them, interpolating values?

That's not true: I'm not doing any interpolation. I'm still using the parser
to evaluate the part of the formulas that was not replaced by a predefined
fct.

Example : f(x,y,z) = cos(x) + y + z
I can define "only" one unary fct and use it to simplify the calculations,
for example : x' = g(x) = cos(x)
then the new formulas will be : F(x,y,z,x') = x' + y + z
As you can see, not all isosurface formula f was changed because I'm still
using a part of it ("y + z") and I made a replacement only for "cos(x)".
This new isosurface F is not the best one but it still advantageous to use
it. Why?
Two facts to know :
(1)You can give as much variables to the parser as you want without any
overhead in it's use.
(2) When analysing the opcode (the replacement of the humain math formulas
for the parser) the parser is faster when it comes to look for a value of
variables.

The fct F was made in this perspective :
I create a new variables x' so F is now a fct of 4 variables (no overhead
see (1)) and the formula of F has now only additions of variables (which is
what the parser like the most, see (2)).
What I'm doing is only trying to replace some part of the formulas by new
variables because variables don't have to be computed whereas a fct must be
evalueted by the parser.
To create this new formulas F, I had to create a new table X'[N] that holds
the N values of cosinus:
X[N] ===> X'[N]
   x ===> x' = cos(x).

For a grid of NxNxN, the required calculations to evaluate :

f  =  N^3*(cosinus evaluations) + 2* N^3 *(addition evaluations)

F  =  N*(cosinus evaluations) + 2* N^3 *(addition evaluations)

The difference between those evalutions came from the cosinus :
For "F" it's N but for "f" it's N^3.

Knowing that there is 3 axes and that the axe X has only N value, make
it possible to evaluate "cos(x)" with the maximum efficiency (only N
evaluations).
The knowlege of the geometry make it possible to store some fct values in a
table and use them as many times as needed when evaluating the entire
grid : That's where the geometry is important.

A normal parser can only hold informations inside one point evaluation, but
never for the entire process because it doesn't use any knowledge about the
gemetry of the domain where the fct is evalueted.

If something is not clear to you , just let me know.
Cheers,
Taha

Post a reply to this message

OK, so you're basically caching recent lookups of various functions so 
you don't have to compute them later.

I still doubt that this would really benefit POV-Ray, because I doubt 
that the various functions such as sqrt or cos are called very often 
with the same exact input.  And if it isn't called with the same input, 
you'd still have to evaluate the function.

Something like a modeller which does object tesselation would probably 
benefit a great deal from this, especially if it tends to evaluate on 
fixed intervals (for algorithms such as marching cubes); however, 
POV-Ray samples many, many more points, all over the spacial area, so 
you'd likely need a much larger cache, resulting in more overhead and 
less performance.

Of course, the only real way to know for sure would be to implement it 
and test; why don't you branch the 3.6 codebase, try it out, and let us 
know if it works?

...Chambers

Post a reply to this message

Ben Chambers <ben### [at] pacificwebguycom> wrote:
> I still doubt that this would really benefit POV-Ray, because I doubt
> that the various functions such as sqrt or cos are called very often
> with the same exact input.  And if it isn't called with the same input,
> you'd still have to evaluate the function.
Hi,
You're right about the reuse for predefined fcts values : This process is
not garanted like with a voxel grid. Also, we have a few informations about
points to evaluate : there number and exact locations aren't known (we know
"only" that they are in the same line), so it needs more work than with the
grid.
However, I belive that we can improve the raytracing process in many ways by
using a grid of voxels:
I think that surfaces sampling by the marching cube and the raytrce can have
the same first process which consist on locating the isosurface in 3D space.
The divergence came after that process: I'm using the marching cube to
generate triangles of the surface but we can easily imagine using the
raytrace technic to do the job "inside" every voxel...
What I mean is that we can use a grid of voxels to minimise the 3D space and
after that use the raytrace technic to finish the job: mainly the grid will
reduice the cube to a "tick" isosurface.
I don't know if someone else have done this before but the closest idea I
found is here : http://www.imagico.de/fast_iso/patch.html (Christoph's
page).
Where Christoph use an octree, I'll use a predefined grid and push the
resolution to height level to reduice the final use of the raytrace.
I have one question thought: is there a reference to something like that in
the net? if not, then i think that something is preventing such use because
it's more easy to imagine that process than the octree process...

> why don't you branch the 3.6 codebase, try it out, and let us
> know if it works?
I already started to look at the code but I have to say that it will took
time before I start to be familliar with the entire code: hopefully I'll
find an easy way to prevent all that process.
Cheers,
Taha

Post a reply to this message