Folks, I need your help.

I'm planning on a feature, but can't think of a good syntax to go with
it. Here's the deal:

Some of you may be aware that isosurfaces can be used as a replacement
for blobs, to get some added flexibility, such as adding toroids or
boxes to the set of elements, or tweaking the way the elements fuse with
each other. Unfortunately this comes at a huge performance penalty.

Part of this difference in performance is because POV-Ray's blob
implementation makes use of the fact that the individual components have
a limited range of influence, employing a bounding hierarchy to bypass
computation of components that are too far away to make any difference.
Isosurfaces do not provide such a mechanism.

I want to change this.

My idea is to provide a special flavour of function, which would not be
based on an arbitrary mathematical expression, but effectively have the
fixed form

    f(x,y,z) = f1(x,y,z) + f2(x,y,z) + ... fN(x,y,z)

and where each individual component function would have an associated
bounding box or bounding sphere, outside of which that particular
component would be presumed to be zero.

(As an extension, a similar mechanism could be introduced for the
product of multiple functions, with each function presumed to evaluate
to 1 outside the bounding shape.)

Obviuously, there would need to be /some/ syntax to associate the
bounding information to the component functions.

There are a few constraints on that syntax:

- Using the existing function mechanism to define the compound function,
and associating the bounding boxes to the individual component
functions, would certainly make for an elegant syntax, but may not be a
viable option for technical reasons. Instead, the "boosted compound
functions" may need to be of a different flavour than regular functions,
and thus would need to be easily recognizable for the parser without
having to analyze the function expression.

- Merely extending the isosurface syntax is something I would want to
avoid, as I would prefer to make these "boosted compound functions"
generally available, not just in isosurfaces.


Any suggestions?

Post a reply to this message

clipka <ano### [at] anonymousorg> wrote:

>     f(x,y,z) = f1(x,y,z) + f2(x,y,z) + ... fN(x,y,z)
>
> and where each individual component function would have an associated
> bounding box or bounding sphere, outside of which that particular
> component would be presumed to be zero.
> Any suggestions?

Um,  The only thing I can think of right now would be to define something along
the lines of a color map or an interpolated spline, and apply that to f(0) ....
f(n)

I never studied them, but it sounds like you're decomposing everything into
parts like a Fourier transform, or synthesizing the final function from
something like one of those series...   Taylor series, etc.

Not that the POV Team doesn't have impressive experts, but:
Have you asked Jos Leys or Paul Nylander, or floated the question out to the
Stackoverflow or Wolfram fora?

Post a reply to this message

Am 23.04.2016 um 03:17 schrieb Bald Eagle:
> clipka <ano### [at] anonymousorg> wrote:
> 
>>     f(x,y,z) = f1(x,y,z) + f2(x,y,z) + ... fN(x,y,z)
>>
>> and where each individual component function would have an associated
>> bounding box or bounding sphere, outside of which that particular
>> component would be presumed to be zero.
>> Any suggestions?
> 
> Um,  The only thing I can think of right now would be to define something along
> the lines of a color map or an interpolated spline, and apply that to f(0) ....
> f(n)
> 
> I never studied them, but it sounds like you're decomposing everything into
> parts like a Fourier transform, or synthesizing the final function from
> something like one of those series...   Taylor series, etc.

I think you misunderstood.

My goal is _not_ to speed up generic user-defined functions by
approximating them with functions satisfying the above form.

Instead, I want to provide users with a dedicated syntax for cases where
they know that the supplied function _already_ satisfies that form, so
that the parser and render engine can exploit this property. You know,
something like:

    #declare MyFn1 = function(x,y,z) { ... }
    #declare MyFn2 = function(x,y,z) { ... }
    ...
    #declare MyFnN = function(x,y,z) { ... }

    #declare MyFn = function {
        MyFn1(x,y,z bounded_by{box{ ... }}) +
        MyFn2(x,y,z bounded_by{box{ ... }}) +
        ...
        MyFnN(x,y,z bounded_by{box{ ... }})
    }

except that this particular syntax would neither be reasonably easy to
parse, nor do I consider it reasonably pretty.

Post a reply to this message

Le 23/04/2016 05:57, clipka a écrit :
>     #declare MyFn1 = function(x,y,z) { ... }
>     #declare MyFn2 = function(x,y,z) { ... }
>     ...
>     #declare MyFnN = function(x,y,z) { ... }
> 
>     #declare MyFn = function {
>         MyFn1(x,y,z bounded_by{box{ ... }}) +
>         MyFn2(x,y,z bounded_by{box{ ... }}) +
>         ...
>         MyFnN(x,y,z bounded_by{box{ ... }})
>     }
> 
> except that this particular syntax would neither be reasonably easy to
> parse, nor do I consider it reasonably pretty.

Could you move the bounded_by in the initial declare ?
(well, it might be something else than function as we know it)


    #declare MyFn1 = bounded_function(x,y,z) { ... bounded_by{box{ ... }}}
    #declare MyFn2 = bounded_function(x,y,z) { ... bounded_by{box{ ... }}}
    ...
    #declare MyFnN = bounded_function(x,y,z) { ... bounded_by{box{ ... }}}

    #declare MyFn = function {
        MyFn1(x,y,z) +
        MyFn2(x,y,z) +
        ...
        MyFnN(x,y,z)
    }

Now, I suck at naming, so go find a better keyword than "bounded_function".
(better: easy to spell, as short as possible, easy to remember, meaningful.)

Post a reply to this message

On 23.04.2016 8:19, Le_Forgeron wrote:

> Could you move the bounded_by in the initial declare ?

This would seem more logical to me too. I don't even think
a new keyword is needed since the presence of the bounded_by
block is obvious to the parser. So having a bounding object
becomes an attribute that any function object may have (and
which might later be exploited in other context too).

However as far as I understand it the problem technically
would be in the need to analyze the compound function expression
to determine that it is indeed just a sum of functions with
attached bounding object. Such information should be available
from the parse tree of the expression but I don't know how it
is implemented in POV-Ray. If some way is needed to specify
expected limitation ahead of time one option might be to
add a new operator that accepts only bounded values, e.g.

#declare Compound_Function = function
{
   bounded_sum(f1,bounded_sum(f2,f3)).
}

or

#declare Compound_Function = function
{
   f1 [+] f2 [+] f3
}

Post a reply to this message

clipka <ano### [at] anonymousorg> wrote:

> Instead, I want to provide users with a dedicated syntax for cases where
> they know that the supplied function _already_ satisfies that form, so
> that the parser and render engine can exploit this property.

Right, sorry - I probably just confused the issue by speculating on a tenuous
similarity.


> You know,
> something like:
>
>     #declare MyFn1 = function(x,y,z) { ... }
>     #declare MyFn2 = function(x,y,z) { ... }
>     ...
>     #declare MyFnN = function(x,y,z) { ... }
>
>     #declare MyFn = function {
>         MyFn1(x,y,z bounded_by{box{ ... }}) +
>         MyFn2(x,y,z bounded_by{box{ ... }}) +
>         ...
>         MyFnN(x,y,z bounded_by{box{ ... }})
>     }
>
> except that this particular syntax would neither be reasonably easy to
> parse, nor do I consider it reasonably pretty.

Well, I was thinking that the way color maps and splines are defined, you could
just do something like

#declare MyFunctions = boundedf {
(x,y,z), pow(x,2) + pow(y,2) + pow(z,2), sphere { ...},
(x,y,z), -(pow(x,3) + pow(y,1) + pow(z,3)), box { ...},
(u,v,z), MyFn1, box { ...},
(u,v,t), MyFn2, box { ...},
(Theta, Phi), MyParametricFn, sphere { ...}
}

That way you don't need to have separate code blocks, retype "function" and
"bounded_by" and their associated braces every time, etc.

"boundedf" implies it's a function bounded by something already known.


It would be a nice feature to be able to use some mixture of (, [, and { to
define functions, as it always helps me differentiate between different parts of
large equations, and keep track of key terms - but that's "related to but
separate from" the present issue.

Post a reply to this message

Am 23.04.2016 um 15:12 schrieb Christian Froeschlin:
> On 23.04.2016 8:19, Le_Forgeron wrote:
> 
>> Could you move the bounded_by in the initial declare ?
> 
> This would seem more logical to me too. I don't even think
> a new keyword is needed since the presence of the bounded_by
> block is obvious to the parser. So having a bounding object
> becomes an attribute that any function object may have (and
> which might later be exploited in other context too).

It would also be my own preference, if it wasn't for the technical
problems I'd expect with this approach.

> However as far as I understand it the problem technically
> would be in the need to analyze the compound function expression
> to determine that it is indeed just a sum of functions with
> attached bounding object.

That's one of the problems.
The other is that I would need to attach the bounding information to the
function object in the first place.

You see, the whole function thing in POV-Ray is (at least to me) a black
box of equally black magic. The less I need to intrude there, the better.


(Of course that doesn't need to limit your brainstorming. Maybe the
issues happen to be less of an obstacle than I currently expect.)

Post a reply to this message

On 04/22/2016 08:02 PM, clipka wrote:
> Folks, I need your help.
>
> I'm planning on a feature, but can't think of a good syntax to go with
> it. Here's the deal:
>
> Some of you may be aware that isosurfaces can be used as a replacement
> for blobs, to get some added flexibility, such as adding toroids or
> boxes to the set of elements, or tweaking the way the elements fuse with
> each other. Unfortunately this comes at a huge performance penalty.
>
> Part of this difference in performance is because POV-Ray's blob
> implementation makes use of the fact that the individual components have
> a limited range of influence, employing a bounding hierarchy to bypass
> computation of components that are too far away to make any difference.
> Isosurfaces do not provide such a mechanism.
>
> I want to change this.
...
>

I'm still finishing a move to a new city and apartment as I try my hand 
at retirement, but as I play quite a bit with isosurfaces, saw your 
post, and have some initial thoughts more on the internals than syntax I 
guess.

- I have often enough wished for a more flexible contained_by mechanism 
for isosurfaces than the sphere / box container shapes we have today so 
I welcome any effort to improve it.

- We can today use shape functions as in "(F_Stem(x,y,z)>=0)" or 
functions testing whether inside or outside and object with select() 
limit the evaluation of other functions. I sometimes use left side 
multiplication too because it is quicker to code though not sure if the 
VM really bails early. I've played with isosurfaces defined by inside 
tests on objects in the past too.

The point is the performance limiter on implementing container/range 
methods for isosurfaces very quickly becomes the fact there is no 
internal optimization on the evaluation of the container objects. Any 
scheme to enable many bounded_by objects in functions, I believe should 
look to make rapid inside evaluations of all those container shapes. It 
was not clear to me from your proposal if this would be the case? I 
believe all the containers would have to be evaluated for each 
evaluation step the isosurface code takes.

- Suppose obvious, but containers internal to the isosurface can 
themselves introduce discontinuities / gradient issues in the overall 
function. Inside a single isosurface they'd need to be used with care.

Bill P.

Post a reply to this message

Am 23.04.2016 um 17:09 schrieb William F Pokorny:

> I'm still finishing a move to a new city and apartment as I try my hand
> at retirement, but as I play quite a bit with isosurfaces, saw your
> post, and have some initial thoughts more on the internals than syntax I
> guess.

Your brainstorming contribution is much appreciated.

> - I have often enough wished for a more flexible contained_by mechanism
> for isosurfaces than the sphere / box container shapes we have today so
> I welcome any effort to improve it.

I'll put this thought somewhere at the back of my head, and let it
ferment for a while.

> - We can today use shape functions as in "(F_Stem(x,y,z)>=0)" or
> functions testing whether inside or outside and object with select()
> limit the evaluation of other functions.

While the select() statement does give some boost by cutting short the
evaluation of sub-expressions, a dedicated mechanism for "blob-like" use
cases could do even better.

Imagine a blob-ish isosurface comprised of, say, 1000 elements, with any
given point in space influenced by at most, say, 5 of them.

A naive function would require the complete evaulation of 1000
sub-expressions, as well as 999 additions, each time the compound
function is to be evaluated.

A function wrapping each sub-expression in a select() could cut that
down to complete evaluation of only 5 sub-expressions, but would
introduce an additional 6000 comparisons, 5000 logical operators and
1000 branches (in the most straightforward implementation that is; using
nested switch() expressions instead of logical operators might instead
give you some guesstimated 2000 comparisons, no logical ops, and a
guesstimated 2000 branches). You'd also still be left with the 999
additions. Also, all of this would happen in a virtual machine without
JIT-compilation. So the workload would still grow linearly with the
number of component functions.

A dedicated mechanism, on the other hand, could make use of some
space-partitioning structure like a KD-tree, to further trim down the
workload to a mere log2(1000)=10 comparisons and branches in native
machine code, followed by 5 complete evaluations of sub-expressions,
mixed with 4 additions in native machine code. So the workload would
primarily be determined by how much "overlap" you have between component
functions, while their total number would be almost irrelevant).


> I sometimes use left side
> multiplication too because it is quicker to code though not sure if the
> VM really bails early. I've played with isosurfaces defined by inside
> tests on objects in the past too.

To the best of my knowledge, POV-Ray's function VM does not use
short-circuit evaluation anywhere, except in switch() expressions.


> The point is the performance limiter on implementing container/range
> methods for isosurfaces very quickly becomes the fact there is no
> internal optimization on the evaluation of the container objects. Any
> scheme to enable many bounded_by objects in functions, I believe should
> look to make rapid inside evaluations of all those container shapes. It
> was not clear to me from your proposal if this would be the case? I
> believe all the containers would have to be evaluated for each
> evaluation step the isosurface code takes.

The main speedup provided by bounding shapes is actually not from
allowing to make a quick first guess on insideness or intersection tests
for an _individual_ object, but rather from providing coordinate ranges
to compile a (very sophisticated) spatial "lookup table" of objects,
which in turn allows to make a quick first guess across _all_ objects at
once, eliminating most objects without even performing individual
bounded_by tests on them.

When intersection or insideness tests need to be performed for a large
number of N objects, per-object bounded_by tests can only reduce the
workload from a*N to b*N with b<a. Lookup structures based on the
bounded_by coordinate ranges, on the other hand, can reduce the workload
to as little as c*log(N) (often with c<=b, but for sufficiently large N
that's of little relevance anyway).


> - Suppose obvious, but containers internal to the isosurface can
> themselves introduce discontinuities / gradient issues in the overall
> function. Inside a single isosurface they'd need to be used with care.

It should indeed be flagged as a caveat; but it would raise a
max_gradient warning, so I think that's ok.

Post a reply to this message

On 04/23/2016 01:40 PM, clipka wrote:
> Am 23.04.2016 um 17:09 schrieb William F Pokorny:
>
>> I'm still finishing a move to a new city and apartment as I try my hand
>> at retirement, but as I play quite a bit with isosurfaces, saw your
>> post, and have some initial thoughts more on the internals than syntax I
>> guess.
>
> Your brainstorming contribution is much appreciated.
>
>> - I have often enough wished for a more flexible contained_by mechanism
>> for isosurfaces than the sphere / box container shapes we have today so
>> I welcome any effort to improve it.
>
> I'll put this thought somewhere at the back of my head, and let it
> ferment for a while.
>

Yes, suppose this outer most container is peripherally related to what 
you are working toward with bounded functions and perhaps more like the 
bounding Bald Eagle was mentioning.

I've played with isosurface sphere_sweep equivalents(1) and they work - 
slowly. The gradients are somewhat steep - which is very often tolerable 
if the container is tight to the shape so to speak - but today the 
container for such things often ends up by volume very much larger due 
having only spheres and boxes.

I don't believe the function bounding being suggested is going to help 
with such isosurfaces. It is at least not apparent to me how I could 
employ it. Perhaps I could though if this new method could associate 
many containers - as in say a spline of spheres/ranges - with one function?

(1) - One axis must contain no folds.

Of course we often struggle with the more complex bounding methods (ie 
sphere_sweep) so perhaps asking for trouble by introducing more complex 
bounding to isosurfaces! ;-)

Aside: Hmm. Wondering... Did we ever wrap up that sphere_sweep bounding 
bug someone found as a git bug or otherwise fix it? This one:

http://news.povray.org/povray.bugreports/thread/%3Cweb.5692847b8bcbbc2219f71b680%40news.povray.org%3E/

>> - We can today use shape functions as in "(F_Stem(x,y,z)>=0)" or
>> functions testing whether inside or outside and object with select()
>> limit the evaluation of other functions.
>
> While the select() statement does give some boost by cutting short the
> evaluation of sub-expressions, a dedicated mechanism for "blob-like" use
> cases could do even better.
>
> Imagine a blob-ish isosurface comprised of, say, 1000 elements, with any
> given point in space influenced by at most, say, 5 of them.
>
> A naive function would require the complete evaulation of 1000
> sub-expressions, as well as 999 additions, each time the compound
> function is to be evaluated.
>
> A function wrapping each sub-expression in a select() could cut that
> down to complete evaluation of only 5 sub-expressions, but would
> introduce an additional 6000 comparisons, 5000 logical operators and
> 1000 branches (in the most straightforward implementation that is; using
> nested switch() expressions instead of logical operators might instead
> give you some guesstimated 2000 comparisons, no logical ops, and a
> guesstimated 2000 branches). You'd also still be left with the 999
> additions. Also, all of this would happen in a virtual machine without
> JIT-compilation. So the workload would still grow linearly with the
> number of component functions.
>
> A dedicated mechanism, on the other hand, could make use of some
> space-partitioning structure like a KD-tree, to further trim down the
> workload to a mere log2(1000)=10 comparisons and branches in native
> machine code, followed by 5 complete evaluations of sub-expressions,
> mixed with 4 additions in native machine code. So the workload would
> primarily be determined by how much "overlap" you have between component
> functions, while their total number would be almost irrelevant).
>
>
>> I sometimes use left side
>> multiplication too because it is quicker to code though not sure if the
>> VM really bails early. I've played with isosurfaces defined by inside
>> tests on objects in the past too.
>
> To the best of my knowledge, POV-Ray's function VM does not use
> short-circuit evaluation anywhere, except in switch() expressions.
>
>
>> The point is the performance limiter on implementing container/range
>> methods for isosurfaces very quickly becomes the fact there is no
>> internal optimization on the evaluation of the container objects. Any
>> scheme to enable many bounded_by objects in functions, I believe should
>> look to make rapid inside evaluations of all those container shapes. It
>> was not clear to me from your proposal if this would be the case? I
>> believe all the containers would have to be evaluated for each
>> evaluation step the isosurface code takes.
>
> The main speedup provided by bounding shapes is actually not from
> allowing to make a quick first guess on insideness or intersection tests
> for an _individual_ object, but rather from providing coordinate ranges
> to compile a (very sophisticated) spatial "lookup table" of objects,
> which in turn allows to make a quick first guess across _all_ objects at
> once, eliminating most objects without even performing individual
> bounded_by tests on them.
>
> When intersection or insideness tests need to be performed for a large
> number of N objects, per-object bounded_by tests can only reduce the
> workload from a*N to b*N with b<a. Lookup structures based on the
> bounded_by coordinate ranges, on the other hand, can reduce the workload
> to as little as c*log(N) (often with c<=b, but for sufficiently large N
> that's of little relevance anyway).
>

Thanks much for the detail. I think I mostly follow it and the plan 
sounds very promising.

Expect you are already aware of it, but to be certain, Christoph Horman 
did quite a bit of isosurface optimization work/study some years back. 
See the isosurface speed up items on the page at : 
http://www.imagico.de/pov/tools_en.php

I did wake up this morning wondering more about the interaction internal 
function bounding with the isosurface mechanism itself.

I don't see any issue for bounded sub-functions used in patterns. There 
the function will be passed a point in space and return a value.

In isosurfaces though there is that search inside the outer container 
along the ray for threshold value(s) defining shape surface(s). My 
thinking is still cloudy, but wondering if this could lead to additional 
iso-search work due the internal container boundaries interacting at 
distance from any intended shape(s)?

Guess thinking some rays might travel through multiple adjacent search 
ranges causing differing sets of functions to be evaluated along the ray 
in a way that is noisier. Ah, maybe though this is just the same 
gradient concern but away from the shape surfaces. For large numbers of 
functions have to think we'd still come out ahead.

>
>> - Suppose obvious, but containers internal to the isosurface can
>> themselves introduce discontinuities / gradient issues in the overall
>> function. Inside a single isosurface they'd need to be used with care.
>
> It should indeed be flagged as a caveat; but it would raise a
> max_gradient warning, so I think that's ok.
>

Post a reply to this message