1

Тема: Зрозумійте мені сплайн-інтерполяцію

Прів. Є точки в просторі по котрим треба побудувати гладеньку криву (це мені тре для того, аби камера в сцені гарно облітала різні предмети).
Я нагуглив от таку штуку http://matlab.exponenta.ru/spline/book1/12.php, котра, начебто являється тим, шо мені і потрібно, але я ніяк не можу зрозуміти той алгоритм.
Раніше я думав, що є якась проста формула, в котру треба просто підставити значення іксів та змінну t, котра змінюється від 0 до 1, після чого я отримаю значення ігрика, ну ви зрозуміли. Але тут все якось так важко і незрозуміло, що мені навіть тему довелось створювати.
Як та штука працює? Я так зрозумів, що там будується декілька кривих, котрі залежать одна від одної, і сам алгоритм оперує вершинами, через котрі має проходити сплайн, якоюсь функцією і похідної якоїсь функції.
З вершинами все зрозуміло, без них ніяк, але що то за функція? Де її брати? І якою вона має бути?
І чи можна за допомогою цього алгоритма знаходити точку на сплайні відносно змінної 0>=t<=1, ну, типу t=0 поверне початок, а t=1 поверне кінець сплайну, а t=0.5 поверне серединку.

Подякували: leofun011

2

Re: Зрозумійте мені сплайн-інтерполяцію

Ось же формула
http://matlab.exponenta.ru/spline/book1/12_files/f21.jpg
на відрізку від xk до xk+1. Як шукати коефіцієнти там написано.

3

Re: Зрозумійте мені сплайн-інтерполяцію

Ось же формула
http://matlab.exponenta.ru/spline/book1/12_files/f21.jpg
на відрізку від xk до xk+1. Як шукати коефіцієнти там написано.

4

Re: Зрозумійте мені сплайн-інтерполяцію

22 роки, вища технічна освіта, за плечима 10 років школи і 5 років універу, що таке похідна зрозумів лишень зараз, з трьоххвилинного відео на ютубі.

Подякували: quez, 0xDADA11C72

5

Re: Зрозумійте мені сплайн-інтерполяцію

quez, ви дійсно думаєте, що я не побачив цю формулу, і що після вашого повідомлення я відразу все зрозумію і далі вже все легко буде зрозуміти?
http://не-дійсний-домен/loMxY/7b9a5078d6.png
шо то за функція, котра нам задана, і похідна котрої нам задана теж?

6

Re: Зрозумійте мені сплайн-інтерполяцію

От я тут колись відео зробив - https://www.youtube.com/watch?v=7yflagnitHk , там наприкінці MATLAB коди для малювання цих сплайнів.

Заразом раджу спочатку поєднати точки прямими (тобто сплайнами першого ступеня) і запустити в продакшн, а тоді вже заморочуватись далі.

7

Re: Зрозумійте мені сплайн-інтерполяцію

Сплайн - це кілька фрагментів функцій, зліплених таким чином, щоб похідна в точках зчеплення була однакова у різних фрагментів. Залежно від бажання/наполегливості/вимог/можливостей можна робити однакові похідні 2-го, 3-го і т.д. порядків, це додає плавності. Тобто:
- беремо параметрично задану функцію;
- шукаємо такі параметри, щоб в певних точках відповідні похідні дорівнювали одна одній;
- будуємо на кожному фрагменті нашу криву.
Звідки брати функцію? Та звідки хочете. Найпростіше - поліном (скільки членів - стільки параметрів). Але ніхто не забороняє всякі синуси-косинуси та арктангенси брати. В літературі класичні приклади розібрані.
Як перетворити діапазон на 0..1 - найпростіше лінійно. Тобто у вас є діапазон x1..x2 - то знаходьте k і b такі, що x = kt+b буде давати x1 для t=0 і x2 для t=1.

Прихований текст

x = x1+(x2-x1)t

Подякували: leofun011

8

Re: Зрозумійте мені сплайн-інтерполяцію

FakiNyan написав:

quez, ви дійсно думаєте, що я не побачив цю формулу, і що після вашого повідомлення я відразу все зрозумію і далі вже все легко буде зрозуміти?
http://не-дійсний-домен/loMxY/7b9a5078d6.png
шо то за функція, котра нам задана, і похідна котрої нам задана теж?

Ви в очі посторонні предмети не засуваєте? Не задано ніяких функцій і ніяких похідних, а задані точки і значення функції і похідної в тих точках. Якщо ви не знаєте значень похідної в цих точках, пролистайте нижче до кубічного сплайна, там треба тільки точки і значення функцій в цих точках. І вчіться задавати питання: ви запитали, що за функція, я вам відповів.

Подякували: leofun011

9

Re: Зрозумійте мені сплайн-інтерполяцію

quez написав:
FakiNyan написав:

quez, ви дійсно думаєте, що я не побачив цю формулу, і що після вашого повідомлення я відразу все зрозумію і далі вже все легко буде зрозуміти?
http://не-дійсний-домен/loMxY/7b9a5078d6.png
шо то за функція, котра нам задана, і похідна котрої нам задана теж?

Ви в очі посторонні предмети не засуваєте? Не задано ніяких функцій і ніяких похідних, а задані точки і значення функції і похідної в тих точках. Якщо ви не знаєте значень похідної в цих точках, пролистайте нижче до кубічного сплайна, там треба тільки точки і значення функцій в цих точках. І вчіться задавати питання: ви запитали, що за функція, я вам відповів.

так ви просто тикнули мені першу функцію, котру побачили, а я питав, яка функція використовується для знаходження http://не-дійсний-домен/loTMy/a3a81ff423.png

10

Re: Зрозумійте мені сплайн-інтерполяцію

Хьюстон, у нас проблема!
Значить, я подумав, що спочатку нам треба знайти оті коефіцієнти, при чому всюди, де я бачив f(x), я підставляв sin, бо почитавши пана koala подумав, що мона юзати яку-небудь функцію, тому і вибрав синус, аби хоча б побачити, що з того вийде. Відповідно всюди, де я бачив f'(x) я ставив cos.
Після того, як знайшлися коефіцієнти, я знаходжу 10 значень використовуючи оту здорову функцію, де використовуються коефіцієнти, при цьому за X я беру x, ліл. Точки в мене знаходяться в 3D просторі, то для кожних двох точок я роблю 10 проходів, при цьому перше значення X дорівнює іксу першої (з двох оброблюваних точок, між якими будується шлях) точки, а десяте значення, це вже ікс другої з точок.
Але нічого не вийшло!
А ще я зрозумів, що треба змінювати X і Y, а я тілько Y змінюю.
Що не так?

void Go()
    {
        int index = 0;
        for(int i=0; i<dots.Length-1; i++)
        {
            float x = dots[i].position.x;
            float x1 = dots[i+1].position.x;
            float f = (Mathf.Sin(x1) - Mathf.Sin(x)) /
                      (x1 - x); //http://не-дійсний-домен/loUho/823ec2bac7.png
            float a = Mathf.Sin(x); //http://не-дійсний-домен/loUj1/2d735e53cb.png
            float b = Mathf.Cos(x);
            float c = (3 * (f) - Mathf.Cos(x1 - 2 * Mathf.Cos(x))) /
                      (x1 - x); //http://не-дійсний-домен/loUka/8c88e584d6.png
            float d = (Mathf.Cos(x) + Mathf.Cos(x1) - 2 * f) /
                      (Mathf.Pow(x1 - x, 2));

            float t = (x1 - x) / 10f;

            for (float j = x; j<x1; j+=t)
            {
                float xxk = dots[0].position.x - j;
                float xxk2 = xxk * xxk;
                float xxk3 = xxk2 * xxk;
                float y = a + b * xxk + c * xxk2 + d * xxk3;//http://не-дійсний-домен/loUlP/b182ca3a54.png

                line.SetPosition(index, new Vector3(j, y, 0));

                index++;
            }
        }
    }

http://не-дійсний-домен/loUTK/487e892a18.png

11 Востаннє редагувалося FakiNyan (18.11.2015 09:25:17)

Re: Зрозумійте мені сплайн-інтерполяцію

короче кажучи, переписав  я потім той код і отримав ще одну бяку, а потім наткнувся на ось таку сторіночку http://paulbourke.net/miscellaneous/interpolation/ використав косинусну інтерполяцію, але воно не зовсім підходить мені, зате воно підходить для малювання хвиль http://не-дійсний-домен/lpmgU/92bfa97a5e.png
зара буду брати код з інфою з нового сайту отого

12

Re: Зрозумійте мені сплайн-інтерполяцію

Будь ласка, не sin та cos, а щось на кшталт a+bsin(cx)+dcos(ex). Параметрично задані криві.

13

Re: Зрозумійте мені сплайн-інтерполяцію

koala написав:

Будь ласка, не sin та cos, а щось на кшталт a+bsin(cx)+dcos(ex). Параметрично задані криві.

ну мій другий код був інший, отакий

using UnityEngine;
using System.Collections;
using System;
 
public class Interpolation : MonoBehaviour {
    public Transform[] dots;
    public float[] diffX, diffY, divDiff, c, d;
    public LineRenderer line;
    private int maxIndex, index;
 
    void Start()
    {
        line = GetComponent<LineRenderer>();
        maxIndex = (dots.Length - 1) * 10;
        diffX = new float[dots.Length - 1];
        diffY = new float[dots.Length - 1];
        divDiff = new float[dots.Length - 1];
        c= new float[dots.Length - 1];
        d= new float[dots.Length - 1];
        line.SetVertexCount(maxIndex);
    }
 
    void makeDiff()
    {
        for(int i =0; i<diffX.Length;i++)
        {
            diffX[i] = Mathf.Abs(dots[i].position.x - dots[i + 1].position.x);
            diffY[i] = Mathf.Abs(dots[i].position.y - dots[i + 1].position.y);
            divDiff[i] = diffY[i] / diffX[i];
        }
    }
 
    void Update()
    {
        Go();
    }
 
    float f1(float x)
    {
        return Mathf.Sin(x) + Mathf.Sin(2 * x);
    }
 
    float f2(float x)
    {
        return Mathf.Cos(x) + Mathf.Cos(2 * x);
    }
 
    void Go()
    {
        index = 0;
        makeDiff();
 
        for (int k = 0; k < diffX.Length; k++) {
            float xk = dots[k].position.x;
            float xk1 = dots[k + 1].position.x;
            c[k] = (3 * divDiff[k] - 2 * f2(k) - f2(k+1)) / (xk1 - xk);
            d[k] = (f2(k) - 2 * divDiff[k] + f2(k + 1)) / Mathf.Pow((xk1 - xk), 2);
        }
 
        for(int k =0; k<diffX.Length; k++)
        {
            float xk = dots[k].position.x;
            float xk1 = dots[k + 1].position.x;
 
            for (float i = 0; i<1;i+=0.1f)
            {
                float xx = Mathf.Lerp(xk, xk1, i);
                float yy = f1(i) + f2(i) * (xx - xk) + c[k] * Mathf.Pow(xx - xk, 2) + d[k] * Mathf.Pow(xx - xk, 3);
 
                line.SetPosition(index, new Vector3(xx, yy, 0));
 
                index++;
            }
        }
    }
}

і дає він от такі результати
https://www.youtube.com/watch?v=kviLzizSNmw

14

Re: Зрозумійте мені сплайн-інтерполяцію

Давайте зупинимося, ок? Спершу формулюється і розв'язується математична задача, потім - програмується.
Яку криву будете використовувати в сплайні? До якого степеня треба похідні прирівнювати? Чи є додаткові вимоги стосовно похідних (на кшталт "дотична в точці i має з'єднувати точки i та i+1")?

15

Re: Зрозумійте мені сплайн-інтерполяцію

koala написав:

Давайте зупинимося, ок? Спершу формулюється і розв'язується математична задача, потім - програмується.
Яку криву будете використовувати в сплайні? До якого степеня треба похідні прирівнювати? Чи є додаткові вимоги стосовно похідних (на кшталт "дотична в точці i має з'єднувати точки i та i+1")?

так а чо її формулювати і розв'язувати? я ж взяв наче готовий алгоритм, котрий треба лишень запрограмувати, тільки от не програмуються ніяк.
Про степені похідних я не зна, але там має і першої похідної вистачити, для нормального результату. Я так пойняв, що похідні на кінцях кривих мають дорівнювати похідним на кінцях сусідніх кривих, тоді і дотична має поєднувати точки i та i+1
http://не-дійсний-домен/lpKBo/34fc0e95e3.png

16 Востаннє редагувалося quez (18.11.2015 10:26:39)

Re: Зрозумійте мені сплайн-інтерполяцію

FakiNyan написав:
quez написав:
FakiNyan написав:

quez, ви дійсно думаєте, що я не побачив цю формулу, і що після вашого повідомлення я відразу все зрозумію і далі вже все легко буде зрозуміти?
http://не-дійсний-домен/loMxY/7b9a5078d6.png
шо то за функція, котра нам задана, і похідна котрої нам задана теж?

Ви в очі посторонні предмети не засуваєте? Не задано ніяких функцій і ніяких похідних, а задані точки і значення функції і похідної в тих точках. Якщо ви не знаєте значень похідної в цих точках, пролистайте нижче до кубічного сплайна, там треба тільки точки і значення функцій в цих точках. І вчіться задавати питання: ви запитали, що за функція, я вам відповів.

так ви просто тикнули мені першу функцію, котру побачили, а я питав, яка функція використовується для знаходження http://не-дійсний-домен/loTMy/a3a81ff423.png

Знов ви бачите функцію, яку більш ніхто не бачить. У вас є набір точок x1..xk і значення функції в цих точках f(x1)..f(xk). А f(x) - це і є шуканий сплайн.
http://не-дійсний-домен/i9/cbfa315a5f7963a418bc9db8c4007ec6/1447835184/10301/843963/a.png

17

Re: Зрозумійте мені сплайн-інтерполяцію

А яку функцію беремо? Поліном?

18

Re: Зрозумійте мені сплайн-інтерполяцію

koala написав:

А яку функцію беремо? Поліном?

для малювання отих кривих? на тому сайті пропонують от таке

y=sin(x)+sin(2*x);

19 Востаннє редагувалося FakiNyan (18.11.2015 10:38:31)

Re: Зрозумійте мені сплайн-інтерполяцію

quez написав:
FakiNyan написав:
quez написав:

Ви в очі посторонні предмети не засуваєте? Не задано ніяких функцій і ніяких похідних, а задані точки і значення функції і похідної в тих точках. Якщо ви не знаєте значень похідної в цих точках, пролистайте нижче до кубічного сплайна, там треба тільки точки і значення функцій в цих точках. І вчіться задавати питання: ви запитали, що за функція, я вам відповів.

так ви просто тикнули мені першу функцію, котру побачили, а я питав, яка функція використовується для знаходження http://не-дійсний-домен/loTMy/a3a81ff423.png

Знов ви бачите функцію, яку більш ніхто не бачить. У вас є набір точок x1..xk і значення функції в цих точках f(x1)..f(xk). А f(x) - це і є шуканий сплайн.
http://не-дійсний-домен/i9/cbfa315a5f7963a418bc9db8c4007ec6/1447835184/10301/843963/a.png

ммм, як цікаво. тобто сплайн складається не з шматків інших кривих, котрі задані отою параметричною функцією, а сам з шматків самого себе, при чому щоб знайти ті шматки, треба знайти сам сплайн, дуже цікаво, так так, тобто там щоб знайти коефіцієнт оцього здорового рівняння, треба знайти його самого. чи тіпа того
http://не-дійсний-домен/lpKU8/b79c6e717b.png
це якщо ви мали на увазі, що от ця штука і є f(x)

20

Re: Зрозумійте мені сплайн-інтерполяцію

FakiNyan написав:

ммм, як цікаво. тобто сплайн складається не з шматків інших кривих, котрі задані отою параметричною функцією, а сам з шматків самого себе, при чому щоб знайти ті шматки, треба знайти сам сплайн, дуже цікаво, так так
http://не-дійсний-домен/lpKU8/b79c6e717b.png
це якщо ви мали на увазі, що от ця штука і є f(x)

f(x) складається із k Pk(x)

А ще вам варто змінити тон як нічого не розуміючому.