POV-Ray : Newsgroups : povray.binaries.scene-files : Making functions for natural cubic splines Server Time
31 Oct 2024 18:59:33 EDT (-0400)
  Making functions for natural cubic splines (Message 4 to 13 of 23)  
<<< Previous 3 Messages Goto Latest 10 Messages Next 10 Messages >>>
From: Tor Olav Kristensen
Subject: Re: Making functions for natural cubic splines
Date: 11 Oct 2014 13:35:00
Message: <web.543969915b2bbe7b97906c220@news.povray.org>
"Bald Eagle" <cre### [at] netscapenet> wrote:
> Something caught my eye right away as I looked through some of this.
>
>   function(t_) {
>     select(t_ - tt[0], 1, 0, 0)*ff[0](t_) +
>     #local I = 0;
>     #while (I <= N - 1)
>       select(t_ - tt[I], 0, select(t_ - tt[I+1], 1, 0))*ff[I](t_) +
>       #local I = I + 1;
>     #end // while
>     select(t_ - tt[N], 0, 1, 1)*ff[N-1](t_)
>   }
>
> It appear(ed)(s) that those "+" operators are just hanging off the edges ...
>
> Does it work by having the first result of SELECT added to the contents of the
> loop, which itself is a concatenation of SELECT results?
.....

Yes, that's right.

The select-statement in the middle just chooses one cubic polynomial function
for each of the intervals. And the select statements at the beginning and at the
end choose functions to use if t_ goes "off the ends", i.e. outside the interval
from tt[0] to tt[N].

I have made a rendering that illustrates how each set of X, Y and Z functions
contribute to each of the parts of the spline inbetween the points at tt[0],
tt[1], ... tt[N-1], tt[N]. I'll post this rendering later today or tomorrow.


> That's pretty crazy and I might need an adult beverage to even begin how it is
> that you came up with that.

Remember that this script is parsed and that the directives does not end up in
the resulting code for the scene. So the operators and the other non-directive
stuff is not "hanging loose", they are left there so that they become part of
the function that is built by the script.


Note that this is a quite powerful feature in POV-Ray; that you can build user
functions with macros.

> Not that I didn't let out a few whistles looking over some of those other
> methods.
>
> Constants reminders of
> (a) why I should have stuck with and went into writing computer software
> and
> (b) I should have definitely taken more math.
> :D

It's never too late learn new math =)

For me it was very useful to study, again, the math that I had already learned
years ago. (I did not understand how useful it could be when I learned it at
school.)

Maybe I can help with implementing these splines in BASIC, if you like.

--
Tor Olav
http://subcube.com


Post a reply to this message

From: Bald Eagle
Subject: Re: Making functions for natural cubic splines
Date: 11 Oct 2014 22:35:00
Message: <web.5439e8035b2bbe7b5e7df57c0@news.povray.org>
"Tor Olav Kristensen" <tor### [at] TOBEREMOVEDgmailcom> wrote:

> Yes, that's right.

> Maybe I can help with implementing these splines in BASIC, if you like.

I'm sure that if you either commented on your code with explanations, or laid
out the logic in pseudocode or flowchart, then translating that to syntactically
correct BASIC wouldn't be too gruesome.

Nevado is already hard at work on it, and I'm certain that between the 3 of us,
we could work out something nice.  I would certainly feel good about being able
to do something useful for all the people who have helped me as I muddled
through things here.

Thanks so much for all the help so far!


Post a reply to this message

From: Tor Olav Kristensen
Subject: Re: Making functions for natural cubic splines
Date: 12 Oct 2014 19:55:01
Message: <web.543b14405b2bbe7b7b9c043a0@news.povray.org>
"Bald Eagle" <cre### [at] netscapenet> wrote:
> "Tor Olav Kristensen" <tor### [at] TOBEREMOVEDgmailcom> wrote:
>
> > Yes, that's right.
>
> > Maybe I can help with implementing these splines in BASIC, if you like.
>
> I'm sure that if you either commented on your code with explanations, or laid
> out the logic in pseudocode or flowchart, then translating that to syntactically
> correct BASIC wouldn't be too gruesome.
> ...

After looking at the JustBasic language, it seems to be a very "poor" language,
with regards arrays, functions, parameter passing, documentation etc. (But it
seems to work with Wine in Linux =)

Therefore I have attached a file with POV-Ray SDL code where POV-Ray's functions
are not used. It's also implemented mostly with global variables (which was
painful for me to do).

I hope this code is not too difficult to translate to JustBasic.

But note that I have not done much testing of this code, so there may be small
insects lurking within it.

--
Tor Olav
http://subcube.com


Post a reply to this message


Attachments:
Download 'natural_cubic_splines_02_04.pov.txt' (6 KB)

From: Nevado
Subject: Re: Making functions for natural cubic splines
Date: 12 Oct 2014 23:30:00
Message: <web.543b44d05b2bbe7b6dce1a360@news.povray.org>
"Tor Olav Kristensen" <tor### [at] TOBEREMOVEDgmailcom> wrote:

> After looking at the JustBasic language, it seems to be a very "poor" language,
> with regards arrays, functions, parameter passing, documentation etc. (But it
> seems to work with Wine in Linux =)

Hi Tor
Thanks for your contribution :-)
I agree about the language, and I first believed this was an impossible task,
but I did find a way to draw PointWriter shapes with cubic splines in JustBasic.
(Luckily, two dimensions are enough for my purposes.) My method takes four user
points A, B, C and D, solves the cubic curve that connects them, draws the
middle segment from point B to C, then moves on to solve B, C, D and E, draws
the segment from C to D and so on. This produces nicely flowing curves. But I
keep running into problems when the curve doubles back on itself, needing two
y-values for the same x-value. The problem arises because the points are
connected in order of increasing x, not in the order the points are clicked.
So when I want this:

       D
         *
          *
           C
         *
       *
     B
   *
A

I get this:


       D
      *  *
      *   *
     *     C
     *
     *
     B
   *
A


My present workaround is to pre-test x for this doubling back situation, then
simply swap x/y values for the input coordinates before solving the polynomial,
effectively mirroring the curve, and then mirror it back when drawing it by
swapping output coordinates. This takes care of some problem situations.
But there will still be cases where both the x- and the y-value double back on
themselves, so the problem remains after mirroring the curve. For example, if
you try to draw a simple cube by clicking four points at right angles to each
other, it won't work, unless I come up with a new idea.


Post a reply to this message

From: clipka
Subject: Re: Making functions for natural cubic splines
Date: 13 Oct 2014 01:18:23
Message: <543b609f$1@news.povray.org>
Am 13.10.2014 05:24, schrieb Nevado:

> I agree about the language, and I first believed this was an impossible task,
> but I did find a way to draw PointWriter shapes with cubic splines in JustBasic.
> (Luckily, two dimensions are enough for my purposes.) My method takes four user
> points A, B, C and D, solves the cubic curve that connects them, draws the
> middle segment from point B to C, then moves on to solve B, C, D and E, draws
> the segment from C to D and so on. This produces nicely flowing curves. But I
> keep running into problems when the curve doubles back on itself, needing two
> y-values for the same x-value. The problem arises because the points are
> connected in order of increasing x, not in the order the points are clicked.
> So when I want this:
>
>         D
>           *
>            *
>             C
>           *
>         *
>       B
>     *
> A
>
> I get this:
>
>
>         D
>        *  *
>        *   *
>       *     C
>       *
>       *
>       B
>     *
> A

Here's some misconception about splines: Each segment is /not/ defined 
by a simple function mapping x coordinates to y coordinates like this:

     y = f(x) = a x^2 + b x + c

Instead, a spline segment in 2D space is defined by a /pair/ of 
functions, each mapping some /third/ value (often denoted as "t" and 
typically ranging from 0 to 1 within each segment) to one of the 
coordinates, e.g.:

     x = f_x(t) = a_x t^2 + b_x t + c_x
     y = f_y(t) = a_y t^2 + b_y t + c_y

or, using vector notation:

     (x,y) = f(t) = (a_x,a_y) t^2 + (b_x,b_y) t + (c_x,c_y)

To understand what the "t" parameter means, think of a cubic spline as 
the trajectory of an object that undergoes some constant acceleration 
within each segment; then, the coefficient

     (c_x,c_y)

is equal to the position of the object at the beginning of the segment,

     (b_x,b_y)

is equal to the speed of the object at the beginning of the segment,

     (a_x,a_y)

is equal to the acceleration of the object in this spline segment, while

     t

is the time since the beginning of the segment.


Post a reply to this message

From: Nevado
Subject: Re: Making functions for natural cubic splines
Date: 13 Oct 2014 05:25:02
Message: <web.543b991b5b2bbe7b6dce1a360@news.povray.org>
Okay, thanks for clearing that up. I have obviously been oversimplifying the
drawing problem.

I'll try and see if my high-school math is enough to handle Tor's code.


Post a reply to this message

From: Bald Eagle
Subject: Re: Making functions for natural cubic splines
Date: 13 Oct 2014 09:30:01
Message: <web.543bd3205b2bbe7b5e7df57c0@news.povray.org>
> > After looking at the JustBasic language, it seems to be a very "poor" language,
> > with regards arrays, functions, parameter passing, documentation etc.

It has always been that way, but way back when, we managed.  :)


> Hi Tor
> Thanks for your contribution :-)
> I agree about the language, and I first believed this was an impossible task,

I used to think many things were impossible, but there's always some clever
devil out there who manages to find a sneaky way to pull it off.
Not sure if you're familiar with these maniacs:
http://en.wikipedia.org/wiki/Demoscene
I was shocked and amazed that people still use all the old equipment with their
limitations and do things I wouldn't have imagined possible.

> but I did find a way to draw PointWriter shapes with cubic splines in JustBasic.

Fast work!

>... I keep running into problems when the curve doubles back on itself, needing two
> y-values for the same x-value. The problem arises because the points are
> connected in order of increasing x, not in the order the points are clicked.

Post a code snippet, and maybe we can see exactly why that is, and hopefully a
way out.

I'm not the greatest at either programming OR math, but I do have a decent
amount of experience clobbering and scheming to get computer languages and
software to do things that they wouldn't ordinarily let you do...   :D


Post a reply to this message

From: Bald Eagle
Subject: Re: Making functions for natural cubic splines
Date: 13 Oct 2014 09:50:00
Message: <web.543bd7d05b2bbe7b5e7df57c0@news.povray.org>
Thanks for that info, Christoph!

Should we be naughtily sneaking a peek at the POV-Ray source code?

https://github.com/POV-Ray/povray/blob/master/source/backend/math/polysolv.cpp

The solve_cubic function in particular?


Post a reply to this message

From: Bald Eagle
Subject: Re: Making functions for natural cubic splines
Date: 13 Oct 2014 12:35:00
Message: <web.543bfe1a5b2bbe7b5e7df57c0@news.povray.org>
"Nevado" <MYPUBLICNAME(a)sol.dk> wrote:

> I'll try and see if my high-school math is enough to handle Tor's code.

I didn't even try to follow the math - I just did a quick verbatim literal
translation from the c++ based SDL to JustBasic

See if you can plug some of this in where it needs to go.
I popped some comments in there and did the best I could on short notice, but I
figured that you "get" JustBASIC enough to know what to do with functions and
subroutines.  See what I tried to do in the SplineDraw.bas file in that respect.

I haven't tested this or looked for typos, but I figured this would get you
started.

Size = 5;
N = Size - 1;


'This is the weird way I came up to populate an array from a list
dim Times (Size)
Times$ = "-2, -1, 0, 0.5, 1"
for i = 0 to N
 Times (i) = val (WORD$ (Times$, i , "," ))
next i


dim Points (Size, 3)
Points$ = "-2, 0, 40, 0, 0, -2, 1, 0, 2, 0, 6, 2, 8, 2, 2"
for i = 0 to N
 Points (i,1) = val (WORD$ (Points$, 1+i*3 , "," ))
 Points (i,2) = val (WORD$ (Points$, 2+i*3 , "," ))
 Points (i,3) = val (WORD$ (Points$, 3+i*3 , "," ))
next i


Start = Times[0]
End   = Times[N]
Span  = End - Start

'T.O.K.'s way, using global variables

dim X (Size)
dim Y (Size)
dim Z (Size)


for i = 0 to N
X (i) = Points (i, 1)
Y (i) = Points (i, 2)
Z (i) = Points (i, 3)
next i

dim tt (Size)
dim yy (Size)

dim hh (Size)
dim uu (Size)
dim vv (Size)
dim zz (Size)

dim kk (Size, 3)


'#macro CalculateCoefficients()
' Change this to a subroutine or a function and place at end of code
sub CalculateCoefficients hh, tt, kk, yy, uu, vv, zz

for i = 0 to N-1
 hh(i) = tt(i+1) - tt(i)
 kk (i, 1) = 6*(yy(i+1) - yy(i))/hh(i)
next i

for i = 2 to N-1
 uu(1) = 2*(hh(0) + hh(1))
 vv(1) = kk(1, 1) - kk(0, 1) - hh(i-1)*vv(i-1)/uu(i-1)
next i

zz(n) = 0
for i = n-1 to 1 step -1
 zz(i) = (vv(i) - hh(i)*zz(i+1)/uu(i)
next i
zz(0) = 0

for i = 0 to N-1
 kk(i,0) = (zz(i+1) - zz(i)/(6*hh(i))
 kk (i, 1) = zz(i)/2
 kk (i,2) = -hh(i)/6*zz(i+1) + 2*zz(i)) +(yy(i+1) - yy(i))/hh(i)
next i

end sub ' or end function


for i = 0 to N
 tt(i) = Times(i)
 yy(i) = X(i)
next i


// Calculate coefficients for the X polynomials
call CalculateCoefficients hh, tt, kk, yy, uu, vv, zz

dim Coeffs_X (Size, 3)
' // Copy kk to Coeffs_X
for i = 0 to N-1
 Coeffs_X (i, 0) = kk (i, 0)
 Coeffs_X (i, 1) = kk (i, 1)
 Coeffs_X (i, 2) = kk (i, 2)
next i


// Calculate coefficients for the Y polynomials

// Copy Y to yy
for i = 0 to N
 yy(i) = Y(i)
next i

call CalculateCoefficients hh, tt, kk, yy, uu, vv, zz


dim Coeffs_Y (Size, 3)

// Copy kk to Coeffs_Y
for i = 0 to N-1
 Coeffs_Y (i, 0) = kk (i, 0)
 Coeffs_Y (i, 1) = kk (i, 1)
 Coeffs_Y (i, 2) = kk (i, 2)
next i



// Calculate coefficients for the Z polynomials
// Copy Z to yy
for i = 0 to N
 yy(i) = Z(i)
next i

call CalculateCoefficients hh, tt, kk, yy, uu, vv, zz


dim Coeffs_Z (Size, 3)

// Copy kk to Coeffs_Y
for i = 0 to N-1
 Coeffs_Z (i, 0) = kk (i, 0)
 Coeffs_Z (i, 1) = kk (i, 1)
 Coeffs_Z (i, 2) = kk (i, 2)
next i



'#macro
function CubicPolynomial T, A, B, C, D

  (D + T*(C + T*(B + T*A))) // Equals (A*T^3 + B*T^2 + C*T + D)

'#end // macro CubicPolynomial
end function


'#macro
sub CalculateCoordinates T, I

 dT = T - Times(i)
     ComponentX = CubicPolynomial (dT, Coeffs_X (i, 0), Coeffs_X (i, 1),
Coeffs_X (i, 2), X (i))

 ComponentY = CubicPolynomial (dT, Coeffs_Y (i, 0), Coeffs_Y (i, 1), Coeffs_Y
(i, 2), Y (i))

 ComponentZ = CubicPolynomial (dT, Coeffs_Z (i, 0), Coeffs_Z (i, 1), Coeffs_Z
(i, 2), Z (i))

'#end // macro CalculateCoordinates
end sub

Color$ = "Cyan, Green, Orange, Yellow, Blue"
' I haven't yet gotten a firm grasp of BASIC graphics - Nevado appears to be
really familiar
' do a lookup using using the   WORD$( Color$, n , "," )   trick
' or convert this to an rgb value, etc.
'#declare Colors =
'  array[Size] {
'    color Cyan,
'    color Green,
'    color Orange,
'    color Yellow,
'    color Blue // Not used
'  }

Intervals = 400

Radius = 0.08

for J = 0 to Intervals - 1     'replaces T.O.K's while loop
 T = Start + J/Intervals*Span
 ComponentX = 0
 ComponentY = 0
 ComponentZ = 0

 if T < Times(0) then
  sub CalculateCoordinates T, 0
  '#declare Color = (Colors[0]/2 + White);
 end if

 for  i = 0 to N-1
  if Times(i) <= T & T < Times(i+1) then
  ' you may have to check the proper BASIC syntax for this comparison logic
  sub CalculateCoordinates T, i
  '#declare Color = Colors[I];
  end if
 next i

 if Times(n) <= T then
  sub CalculateCoordinates T, N-1
  '#declare Color = (Colors[N-1]/2 + White);
 end if

 #grid, "size 5 ; color "; WORD$( Color$, n , "," ) ;" ; set "; XandY(Points,
1); " "; XandY(Points, 2)
 ' sphere {<ComponentX, ComponentY, ComponentZ>, Radius pigment { color Color }}
next J


Post a reply to this message

From: Bald Eagle
Subject: Re: Making functions for natural cubic splines
Date: 13 Oct 2014 13:55:01
Message: <web.543c115e5b2bbe7b5e7df57c0@news.povray.org>
Error-checked it and fixed a bunch of comments, missing parentheses, and syntax
errors.
Added the basic stuff to get it to run in the compiler, but it doesn't do
anything, and I can't exit it without forcibly killing the process in the task
manager.

But it's a small improvement.  :)


Post a reply to this message

<<< Previous 3 Messages Goto Latest 10 Messages Next 10 Messages >>>

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