Hi,
I'm looking for the part of the code that evaluate math functions
(isosurfaces) already stored in the functions table. I can't locate this
ultimate function in the code... Perhaps it's merged with some code and has
a different name than the usual "Eval()" fct?
Thanks in advance,
Taha

Post a reply to this message

virtualmeet wrote:
> I'm looking for the part of the code that evaluate math functions
> (isosurfaces) already stored in the functions table. I can't locate this
> ultimate function in the code... Perhaps it's merged with some code and has
> a different name than the usual "Eval()" fct?

You mean a multifile search/grep for the function names in the internal
function table won't show you? Of course it would, but either way, you are
looking for fnintern.cpp.

	Thorsten

Post a reply to this message

Thorsten Froehlich <tho### [at] trfde> wrote:
> virtualmeet wrote:
> > I'm looking for the part of the code that evaluate math functions
> > (isosurfaces) already stored in the functions table. I can't locate this
> > ultimate function in the code... Perhaps it's merged with some code and has
> > a different name than the usual "Eval()" fct?
>
> You mean a multifile search/grep for the function names in the internal
> function table won't show you? Of course it would, but either way, you are
> looking for fnintern.cpp.
>
>  Thorsten

Hello,
Thanks for the help. I was in fact looking for the fct evaluator of the low
level defined fct ("+", "-"...) and I found it in fnpovfpu.cpp --> DBL
POVFPU_RunDefault(FUNCTION fn) . I also found that you're the author of
this part of code so all I can say is: My hat is off to you and to all Pov
team programers, you're our inspiration.
My Christmas Greetings to you and to the PovRay team.
Taha

Post a reply to this message

Hello again,
My message is to say that there is likely a way to calculate isosurfaces
much more faster than what povray is doing now.
I was looking for a way to accelerate isosurfaces calculations for K3DSurf
but the parser I'm using (fparser from warp, I think it's one of your
developer but I'm not sure) was already optimised (except for the pow fct)
and it's the fastest one I've found on the net. Doing better requires then
a new "methodology" and that's the subject of my message.
The idea is quite simple and the consequences can be very interesting:
Isosurfaces  (the same for simple functions ) should be considered as a
"single math object". By "single math object " I mean that to be
calculated, the parser should do it in one pass and not point by point. To
do this, we should change the stack the parser is using to store the
intermediate value.
To explain better, suppose we have a grid of 4x4x4 points. The modified
parser will use an internal stack with the size of 4x4x4xStackSize
(StackSize is the normal size used by the original fparser).
I'm getting already some interesting results by using this methodology:
** This modified parser run from 1.5 to 5 times faster than the original
parser, however the fastests results came from isosurfaces with pow fcts,
witch was optimised for fparser. For isosurfaces with only trigonometric
fcts (cos, sin...), the midified parser run between 1.5 to 2.5 times
faster.
There is a windows binary available at :
http://sourceforge.net/project/showfiles.php?group_id=142839&package_id=156961
that implement this new parser and you can test some isosurfaces by
activating/deactivating it and comparing the time processing (This binary
was made for some testers and the code is note available yet because it's a
big mess :) ). This parser works only for grid =4, 8, 12... (grid mod 4 =0)
** This parser run faster with new CPU : this is due to the height amount of
memory in the CPU cache (L1 and L2).
** More isosurfaces fct is "big", more it run faster.
** This parser is heighly parallelisable and can take advantage from
multiCPU machines.
I think that PovRay can also use this methodology and if you want more infos
or some code from my implementation, just let me know. Also, you'll not have
to write the hole parser, only the part that evaluate the opcode should be
modified.
Cheers,
Taha
PS: sorry for my english.

Post a reply to this message

Also, the name of the windows binary is  "k3dsurf-0613-Unstable.exe".
and you can find here
http://k3dsurf.sourceforge.net/images/k3dsurf_061/1.jpg an image of the
K3DSurf controls to activate the new parser.
Cheers,
Taha

Post a reply to this message

virtualmeet wrote:
> To explain better, suppose we have a grid of 4x4x4 points.

If you pre-calculate samples in a gird, you create a voxel array, aka
density map in POV-Ray. This is not the same as an isosurface, and even
though sampling a voxel array is fast, it is also extremely inaccurate
unless you assume you have infinite memory. Even worse, once your voxel
array approaches a certain size, you need to calculate a lot more samples
than samples hat are visible. Hence, your voxel array calculations *and*
memory requirements grow O(n1^3) regardless of image resolution (where n1 is
the grid size in one dimension), while isosurface memory requirements are
somewhere around O(log n2) and computation requirements are O(n3*log n2)
where n3 is the number of pixels occupied and n2 is a measure of function
complexity (aka recursive steps of the approximation algorithm).

	Thorsten

Post a reply to this message

> Thorsten Froehlich <tho### [at] trfde> wrote:
> This is not the same as an isosurface, and even
> though sampling a voxel array is fast, it is also extremely inaccurate
> unless you assume you have infinite memory.
Hi,
You're right about the memory requirements, it grows fast with the grid.
However, I resolved this problem by using a small grid of 4x4x4 points and
make the parser able to perform 64=4x4x4 operations in one pass. The
results I talked about were obtained by using this small grid. I made some
tests with grid up to 20x20x20 but I had some stranges results and I think
this is due to the memory cache in the CPU : Performances should grow with
the grid but this is not always the case!
So even with a small grid the results are worthy because as I mentioned
before, it was impossible to made a better parser than the original one by
following the same way of handling the calculations.
I'm not an expert in PovRay but I know that it can split the calculations of
isosurfaces to be done in many CPU (SMP archi). if I'm right, then it's
possible to use the same sheme as what I'm doing with isosurfaces in
K3DSurf, and using a custum parser that can handle as low as 64 operations
in one pass can have significant results.
Just to give you a simple example of the the code I'm using :

From the original Eval() fct in the paser I'm using:
-------------------------------------------
    for(IP=0; IP<ByteCodeSize; ++IP){
        switch(ByteCode[IP])
        {
         case   cCos: Stack[SP] = cos(Stack[SP]);
                      break;
         case   cSin: Stack[SP] = sin(Stack[SP]);
                      break;

......
Where Stack = new double[StackSize];
---------------------------------------------

Changed to :
---------------------------------------------

    for(IP=0; IP<ByteCodeSize; ++IP)
    {
        switch(ByteCode[IP])
        {
         case   cCos:
NewStack = &StackArray[SP*64];
for(i=0; i<64; i++) NewStack[i] = cos(NewStack[i]);
break;

         case   cSin:
NewStack = &StackArray[SP*64];
for(i=0; i<64; i++) NewStack[i] = sin(NewStack[i]);
break;

......
Where StackArray = new double[64*StackSize];
-------------------------------------------------

I'm not sure if you understand exactly what I'm saying (because of my poor
english) but all I can say for now is that it works for me and it should
work for every mathematical parser. I'm doing some tests for more that 3
months now and for me one thing is sure: writing a better math parser is
impossible by using the same sheme, because the fparser is the best of it's
kinde. Using the "topology" of the mathematical object to sample
calculations is one way to go further than what we are used to.
Moreover, we can make "scalables" math parsers to take advantage of
differents CPU by increasing the amount of operations that it can handle.
Who knows, perhaps in one century, we 'll have some CPU with enought memory
to store a "Super Stack" of 1 Gig  :).
Cheers,
Taha

Post a reply to this message

virtualmeet <tah### [at] yahoofr> wrote:
> I'm doing some tests for more that 3
> months now and for me one thing is sure: writing a better math parser is
> impossible by using the same sheme, because the fparser is the best of it's
> kinde.

  Not true, actually. It could use JIT compiling, making it even faster.
(This has been an idea for years, but I have never got to actually do it.)

  OTOH, if you are making every operation to 64 items at a time in a loop,
then maybe JIT compiling won't make *that* significantly faster...

-- 
                                                          - Warp

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
>   OTOH, if you are making every operation to 64 items at a time in a loop,
> then maybe JIT compiling won't make *that* significantly faster...
Warp <war### [at] tagpovrayorg> wrote:
>   OTOH, if you are making every operation to 64 items at a time in a loop,
> then maybe JIT compiling won't make *that* significantly faster...
Hello,
First, Thank you for your work on fparser, it's really a great job.
I just made some tests with multithreading support and it's also promising.
I don't know about the JIT compiling but I think that graphical applications
like Povray and K3DSurf should take advantage of there math objetcs and give
a parser some hints on the math objects they are handling: isosurfaces
(dim=3)should not be treated like a single point (dim=0) by the parser and
the internal stack of the parser should be one dimension more than the
object it performs. This new parser has the advantage that it uses 100% of
the old one, will take advantage of all opcode optimisation and we don't
have to write a new one from scratch: all to do is just write some special
Eval() fcts suitables for every math object the application is able to
handle (Isosurfaces (dim=3), parametriques(dim=2), simple fcts(dim=1),
point (dim=0) ). It's even possible to write a single new fct Eval() and
use it for heigher dimensional object: we can for example use an Eval() fct
made for "simple fcts" (dimension = 1) to perform parametric object ( by
calculating the parametric  map line by line) and Isosurfaces (by
calculating line by line and layer by layer). We can also use an Eval() fct
suitible for calculating objetc with dim =2 (parametric map) to perform
isosurfaces layer by layer (that's what I'm planing to do in the future).
Also, it's a scalable parser since it's easy to change the number of
operations it can perform in the loop and by doing so approching the
"theorical" maximum number of calculations the hardware is able to do
(since most of the CPU time will be used in series of independants
calculations).
As tests shows, examples run up to 5 times faster (the fastest examples are
"Shmutov_2" and "Pseudo_Duplin" in the last k3dsurf-0613-Unstable) but it's
easy to see that it will run faster with "big" functions (since some time is
economised from the  loop).
Cheers,
Taha

Post a reply to this message

Hi again,
Just to say that the monster has just started to show it's real face to
me...calculations can go really mad by exploting Isosurfaces geometry: New
calcul simplifitions can be done , which are impossible to do by another
way.
Example: Cos(x) + cos(y) + cos(z)  (Schwartz). Well, beleave it or not but a
grid of 1000x1000x1000 will require only 3000 cosinus fct calculations (I'm
already able to use this kind of simplifications), rather than the normal
10^9.
Not only it can run fast but it can also run handreds or thousands times
faster than a "hard coded" function...in short, the parser can make the
hardwar run faster than it's original purpose!
Thorsten and Warp: Please consider to take a closer look at this way of
making geometrical math calculations...it looks to me that I'm still seeing
only the top of the iceberg and skilled peoples like you can certainly make
things much more better.
Cheers,
Taha

Post a reply to this message