POV-Ray : Newsgroups : povray.advanced-users : Polynomial Vector / Syntax tool Server Time: 20 Jun 2019 19:07:57 GMT
  Polynomial Vector / Syntax tool (Message 1 to 5 of 5)  
From: Bald Eagle
Subject: Polynomial Vector / Syntax tool
Date: 18 Oct 2017 14:20:01
Message: <web.59e76275a367ac6c437ac910@news.povray.org>
I came across a thing I wanted to visualize, and of course it was some insane
8th-order polynomial --- in unexpanded/simplified form, of course.

After getting the equation, finding an online polynomial calculator, wrestling
with a bug, and getting the simplified expansion, I moved on to starting on
converting it to POV-Ray syntax.

The docs state:

"Writing the polynomial vector
.....

Note: It is also possible to make a little program with your favorite
programming language which will print the poly vector from the polynomial
function, but making a program like this is up to you."

So, not being dissuaded by the 120 terms in the polynomial syntax, I copied and
pasted the table from the docs into OpenOffice Calc and have most of it worked
out.

Does anyone have a link to prior work on this?
Has someone actually written a program to return a polynomial vector or the
simplified syntax?

Does anyone here have the knowledge & skill to parse, expand and simplify
polynomial expressions?
Can you provide a reference to an explanation / code?

It would be great to have a native (SDL or source code) polynomial 'processor' -
you know - in v 4.0  ;D



It may take me a while to get my spreadsheet worked out and polished up a bit,
but if I'm reminded (prodded) I can post it here (probably as a zip).


Post a reply to this message

From: Bald Eagle
Subject: Re: Polynomial Vector / Syntax tool
Date: 19 Oct 2017 12:15:01
Message: <web.59e896656449c4e8c437ac910@news.povray.org>
I've made some progress on the spreadsheet, and have some questions and comments
on the topic of polynomials and parametrics and isosurfaces.

In this thread:
http://news.povray.org/povray.binaries.images/thread/%3Cweb.591ae564741e6af9c437ac910%40news.povray.org%3E/

I was working on the Dupin cuclide shape and stated:

> ... Dupin cyclide in both isosurface (implicit) and
> parametric form,
.....
> It is, however, SLLLLllllllllllooooooooooowwwwwwww.

Le_Forgeron <jgr### [at] freefr> wrote:
> It is not slow with a polynomial.

But now check this out:
http://www.povray.org/documentation/view/3.7.1/74/

"Note:Since version 3.5, POV-Ray includes the new isosurface object which makes
the polynomial object more or less obsolete. The isosurface is more versatile
(you can specify any mathematical function, not just polynomials), easier to
use. You can write the function as is, without needing to put values in a
gigantic vector.
Isosurfaces often render considerably faster than equivalent polys."

Whaaaaat?


This was interesting too, as I never knew this was the case:

"However, the most mathematically oriented still like polys because isosurfaces
are calculated just by approximating the right value, while the poly is
calculated in a mathematically exact way. Usually isosurfaces are more than good
enough for most applications, though."


I spent a good deal of time looking into how to find out how many terms there
would need to be for a polynomial of order greater than 7, since the polynomial
that kicked off this line of inquiry is 8th order, and the table in the docs
only goes up to 7.

The docs seem to be fragmented, and scattered over many different incarnations,
with bits and pieces of data here, there and everywhere.

One of those bits was:
http://www.povray.org/documentation/view/3.6.1/298/
There are n such terms where n = ((Order+1)*(Order+2)*(Order+3))/6.

I'd love to know where this equation comes from.

Also, considering that quintics are apparently of ridiculous complexity to
solve, and higher order polynomials rapidly become more insane,  I'd like to get
a little insight as to how POV-Ray deals with 15th order polys and, if the
version of the docs I'm reading is right - _35th_ order.

http://www.povray.org/documentation/3.7.0/t2_3.html

"Note: A maximum of 35th degree polynomial can be represented with the poly
object. If a higher degree polynomial or other non-polynomial function has to be
represented, then it is necessary to use the isosurface object."

(When did the limit go from 15 to 35?   WHO recoded that in the source??)

Also, I would certainly be interested in seeing the equation and render for the
highest order poly object anyone has rendered....  :D


Post a reply to this message

From: clipka
Subject: Re: Polynomial Vector / Syntax tool
Date: 19 Oct 2017 12:54:50
Message: <59e8a09a$1@news.povray.org>
Am 19.10.2017 um 14:11 schrieb Bald Eagle:

> Le_Forgeron <jgr### [at] freefr> wrote:
>> It is not slow with a polynomial.
> 
> But now check this out:
> http://www.povray.org/documentation/view/3.7.1/74/
> 
> "Note:Since version 3.5, POV-Ray includes the new isosurface object which makes
> the polynomial object more or less obsolete. The isosurface is more versatile
> (you can specify any mathematical function, not just polynomials), easier to
> use. You can write the function as is, without needing to put values in a
> gigantic vector.
> Isosurfaces often render considerably faster than equivalent polys."
> 
> Whaaaaat?

I'd expect this to depend on both the order and "density" of the
coefficient matrix, i.e. how many coefficients are non-zero. If you have
many zero coefficients, it may be faster to execute a corresponding
user-defined function than to compute the full set of polynomial terms
and then multiply most of them by zero.

For example, given the function

    f(x,y,z) = x^2 + y^2 + z^2

and

    f(x,y,z) = x^10 + y^10 + z^10

this should require roughly the same effort when using an isosurface,
but when using a polynomial the second function will require a much
higher effort to solve.


> Also, considering that quintics are apparently of ridiculous complexity to
> solve, and higher order polynomials rapidly become more insane,  I'd like to get
> a little insight as to how POV-Ray deals with 15th order polys and, if the
> version of the docs I'm reading is right - _35th_ order.
> 
> http://www.povray.org/documentation/3.7.0/t2_3.html
> 
> "Note: A maximum of 35th degree polynomial can be represented with the poly
> object. If a higher degree polynomial or other non-polynomial function has to be
> represented, then it is necessary to use the isosurface object."
> 
> (When did the limit go from 15 to 35?   WHO recoded that in the source??)

This is defined by the `MAX_ORDER` constant in the source code, which
was "recently" increased by Jerome Grimbert (aka Le_Forgeron).

The previous limit of 15 was rather arbitrary; the current limit of 35
is imposed by the `binomials` precomputed table in `polynomial.cpp`,
which would require more than 32 bits per entry if the limit was
increased above 35.


Post a reply to this message

From: Bald Eagle
Subject: Re: Polynomial Vector / Syntax tool
Date: 19 Oct 2017 14:20:00
Message: <web.59e8b4256449c4e8c437ac910@news.povray.org>
clipka <ano### [at] anonymousorg> wrote:

> I'd expect this to depend on both the order and "density" of the
> coefficient matrix, i.e. how many coefficients are non-zero.

Yes, that makes sense - rather than a broad generalization that one object type
renders faster than another.

Much more better.

> If you have
> many zero coefficients, it may be faster to execute a corresponding
> user-defined function than to compute the full set of polynomial terms
> and then multiply most of them by zero.

Hmm.  Makes sense from a mathematical perspective, and suggests that there may
be room for improvement in the code - check for zero coefficients and bail out
on any subsequent calculations --- if that's at all possible in the algorithms
used.

> For example, given the function
>
>     f(x,y,z) = x^2 + y^2 + z^2
>
> and
>
>     f(x,y,z) = x^10 + y^10 + z^10
>
> this should require roughly the same effort when using an isosurface,
> but when using a polynomial the second function will require a much
> higher effort to solve.

I will have to think about that for a while to understand why.

At the moment I can only assume it because of the statement in the docs that
asserts that isosurfaces are only approximations, whereas polynomials are
'exact' solutions.


> This is defined by the `MAX_ORDER` constant in the source code, which
> was "recently" increased by Jerome Grimbert (aka Le_Forgeron).

Very nice.  (Thanks Jerome!)  :)
He is one very busy bee.

> The previous limit of 15 was rather arbitrary; the current limit of 35
> is imposed by the `binomials` precomputed table in `polynomial.cpp`,
> which would require more than 32 bits per entry if the limit was
> increased above 35.

I'm guessing that if and when 32 bit becomes completely obsolete, that a
64-bit-per-entry will determine the maximum size of the precomputed table....?

2^32 = 4294967296
2^64 = 18446744073709551616

I don't have any clue how to determine what order polynomial that would allow...

That said,
a 35th order polynomial requires an 8436-term vector.  :O
And 35th order is pretty damned impressive - and some might say ... excessive
:D

I am of course interested in how to represent and expand polynomial orders of 7
through (maybe) 35.
Is the table (and the number of terms calculation) based upon something like (x
+ y + z)^Order ?

Also, if that's the case, then I'm assuming that the (maximum) number of terms
for a binomial expression (only x & y) is ((Order+1)*(Order+2))/someDivisor

I am curious as to how the polynomial object is ... bounded.


Post a reply to this message

From: Le Forgeron
Subject: Re: Polynomial Vector / Syntax tool
Date: 22 Oct 2017 15:45:25
Message: <59ecbd15@news.povray.org>
Le 18/10/2017 à 16:17, Bald Eagle a écrit :
> 
> I came across a thing I wanted to visualize, and of course it was some insane
> 8th-order polynomial --- in unexpanded/simplified form, of course.
> 
> After getting the equation, finding an online polynomial calculator, wrestling
> with a bug, and getting the simplified expansion, I moved on to starting on
> converting it to POV-Ray syntax.
> 
> The docs state:
> 
> "Writing the polynomial vector
> .....
> 
> Note: It is also possible to make a little program with your favorite
> programming language which will print the poly vector from the polynomial
> function, but making a program like this is up to you."
> 
> So, not being dissuaded by the 120 terms in the polynomial syntax, I copied and
> pasted the table from the docs into OpenOffice Calc and have most of it worked
> out.
> 
> Does anyone have a link to prior work on this?
> Has someone actually written a program to return a polynomial vector or the
> simplified syntax?

The simplified syntax has a lot of my preference.

http://wiki.povray.org/content/Documentation:Tutorial_Section_3.2#Polynomial_made_easy

>
http://wiki.povray.org/content/Documentation:Tutorial_Section_3.2#Polynomial_made_easy

A term like a.x² become xyz(2,0,0):a,

No need for spreadsheet, order of xyz() is not important, and you can
omit the terms which have a 0.

> 
> Does anyone here have the knowledge & skill to parse, expand and simplify
> polynomial expressions?
> Can you provide a reference to an explanation / code?
> 
> It would be great to have a native (SDL or source code) polynomial 'processor' -
> you know - in v 4.0  ;D
> 

Wolfram is your friend. Really.

> https://www.wolframalpha.com/input/web-apps/algebra-course-assistant/

to get the polynomial factor, "expand <equation>" is the solution.

Transcription of the result is rather simple, but that's my opinion.
Remember, order is irrelevant in the simplified form.

> 
> 
> It may take me a while to get my spreadsheet worked out and polished up a bit,
> but if I'm reminded (prodded) I can post it here (probably as a zip).
> 
> 
>


Post a reply to this message

Copyright 2003-2008 Persistence of Vision Raytracer Pty. Ltd.