POV-Ray : Newsgroups : povray.binaries.scene-files : Making functions for natural cubic splines Server Time
28 Mar 2024 11:00:59 EDT (-0400)
  Making functions for natural cubic splines (Message 1 to 10 of 23)  
Goto Latest 10 Messages Next 10 Messages >>>
From: Tor Olav Kristensen
Subject: Making functions for natural cubic splines
Date: 6 Oct 2014 18:35:00
Message: <web.54331726f5851fad7b9c043a0@news.povray.org>
The POV-Ray SDL code in two files in the attached zip-file has macros that
creates functions that can be used to make splines like POV-Ray's built-in
(cubic) natural_spline. (There's also code that shows how to use the macros.)

I made this to illustrate a possible way to make cubic splines, as discussed in
this thread:

Newsgroup: povray.binaries.utilities
From: Bald Eagle
Subject: Re: PointWriter: New app for making spline-based shapes easily
Date: 5th Oct 2014
http://news.povray.org/web.5431a1b09ace5295e7df57c0%40news.povray.org


Also see these threads for similar macros and more:

Newsgroup: povray.text.scene-files
From: Tor Olav Kristensen
Subject: Even spacing of points along natural cubic splines
Date: 12th Dec 2010
http://news.povray.org/povray.text.scene-files/thread/%3Cweb.4d04dadb31d78932c734aecd0@news.povray.org%3E/

Newsgroup: povray.binaries.images
From: Tor Olav Kristensen
Subject: Spacing of points along natural cubic splines
Date: 12th Dec 2010
http://news.povray.org/povray.binaries.images/thread/%3Cweb.4d04e35320256a0cc734aecd0%40news.povray.org%3E/

--
Tor Olav
http://subcube.com


Post a reply to this message


Attachments:
Download 'natural_cubic_splines.zip' (3 KB)

From: Bald Eagle
Subject: Re: Making functions for natural cubic splines
Date: 8 Oct 2014 15:30:00
Message: <web.54358f8d5b2bbe7b5e7df57c0@news.povray.org>
Yay!  I just saw this now - and will look into it in a little while.
I'm assuming if it can be implemented in SDL, it can be converted to BASIC.

Thanks so much for working this out and posting it!


Post a reply to this message

From: Bald Eagle
Subject: Re: Making functions for natural cubic splines
Date: 8 Oct 2014 23:10:00
Message: <web.5435fb975b2bbe7b5e7df57c0@news.povray.org>
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?
That's pretty crazy and I might need an adult beverage to even begin how it is
that you came up with that.
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


Post a reply to this message

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

Goto Latest 10 Messages Next 10 Messages >>>

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