Блоґ одного кібера

Історія хвороби контуженого інформаційним вибухом

n-вимірний куб

with 15 comments

Щойно подумав, що добре було б мати свій логотип. Щось красиве, що за одно відображало програмерсько-математичне спрямування мого блогу, а заодно оригінальне. І таки одна річ спала на думку. Недавно робив кубик рубика. Всім сподобалося. Але кубик – це занадто просто. І на думку спав тессеракт.

Десь рік тому, випадково я запрограмував повертання каркасу тессеракта в Паскалі. А недавно подумав – та що там той тессеракт. Фігня. Дай я намалюю n-вимірний куб. Це ж аналогічно до тривимірного.

Одна з проекцій каркасу п'ятивимірного куба

Одна з проекцій каркасу п'ятивимірного куба

Теорія

Спочатку теоретичні міркування. Хай ми перебуваємо в n-вимірному просторі. Тому далі все по замовчуванню буде вважатись n-вимірне. Для простоти розуміння уявляйте собі наш простір (тривимірний).

Дамо означення деяким поняттям:

Точка (вершина)
вектор з n компонентами (координатами)
Відрізок
множина точок яка знаходиться між двома точками. Нехай це точки A=(a_1,a_2,\ldots,a_n) і B=(b_1,b_2,\ldots,b_n). Тоді відрізок AB – це множина AB=\{ X = (x_1,x_2,\ldots,x_n) | \forall i=\overline{1..n},\, t \in [0;1],\, x_i = a_i + t(b_i - a_i) \}
Куб
множина точок, модуль максимальної компоненти яких менший 1. (Таке визначення задає лише куб в центрі координат, зі стороною 2, і ребрами паралельними осям координат, але спрощує означення. Інші куби можна утворити афінними перетвореннями).
Вершина куба
точка, в якої модуль кожної координати дорівнює одиниці.
Ребро куба
відрізок між вершинами, які відрізняються лише одною координатою.

Для малювання каркасу, цього має бути достатньо. З означень виходить, що одновимірний куб є відрізком [-1;1], двовимірний – квадратом, ну і нормальний тривимірний куб теж підпадає під означення.

Тепер треба думати, як це все будемо малювати. Малювати можна або на папері, або на дисплеї. Обоє з цих пристроїв двовимірні. Тому прийдеться генерувати проекцію.

Проекція точки
двовимірна точка з координатами рівними двом першим компонентам точки яка проектується. (Також доволі спрощене означення, яке задає строгу ортогональну проекцію.)
Проекція відрізка
Проекція всіх його точок. А також, очевидно, відрізок на площині, який сполучає проекції кінців нашого відрізка.

Згадавши означення куба, можна зробити правильний висновок, що ортогональна проекція будь-якого n-мірного куба на площину є квадрат. Тоді нащо скільки мороки, щоб намалювати квадрат? Круто би було мати перспективну проекцію, але як її здійснити? А, така проста на перший погляд ортогональна проекція легко стає ізометричною після здійснення повороту на 45° навколо кожної з осей. (Це для тривимірного простору, який вчать на кресленні. Для n-вимірного повороту треба давати означення).

Поворот доволі цікава штука. Означення дати не так і просто. Очевидно, що поворот – це рух. Кожен рух характеризується ступенем свободи. В повороту є тільки один ступінь свободи – кут. Крім кута, для повороту задають вісь, навколо якої обертають. Стоп! Це твердження стосується тільки тривимірного простору. На площині повертають навколо прямої, а навколо точки. Тоді навколо чого обертають точки в гіперпросторі. Логічно припустити що навколо площини. Уявили собі? Отож-бо!

А я думаю, що ми обмежуємо себе, говорячи “поворот навколо”. Насправді поворот відбувається в площині. Площина двовимірна, і з цього випливає розмірність об’єктів навколо яких ми робим поворот в різних просторах.

  1. Повороту в одновимірному просторі не існує, бо площина не влізається в одновимірний простір.
  2. В двовимірному просторі для об’єкта який задає поворот залишається 2-2=0 вимірів. 0 вимірним простором є точка. Тому в площині ми робимо поворот навколо точки.
  3. В тривимірному просторі для фіксації повороту використовують 3-2=1 одновимірний об’єкт. Одновимірна в нас пряма. Тому ми кажемо, що поворот відбувається навколо прямої. В площині ортогональній до прямої.
  4. Про чотиривиміриний простір говорити не будем, бо як ви собі уявите поворот навколо площини? Краще думати що поворот відбувається в площині.

Раз ми вже домовились, що поворот відбувається в площині, то пригадаємо, що таке поворот на площині. Для повороту на кут α нам було досить двох шкільних формул:

\begin{cases} x' = x \cos \alpha - y \sin \alpha \\ y' = x \sin \alpha + y \cos \alpha \end{cases}\ (1)

Тепер трошки ближче до означень. Знову ж таки для нашої святої простоти будемо вважати, що поворот виконується в площині паралельній якимось двом осям нашої системи координат. Правда простота не завжди означає обмеженість. Один вчений на ім’я Ейлер, колись довів, що будь-яку орієнтацію тіла в просторі можна задати кутами повороту навколо трьох осей координат. Тобто будь-який поворот навколо довільної осі можна замінити трьома поворотами навколо осей координат. Ці три кути називаються кутами Ейлера. Він звісно говорив про тривимірний простір, але немає ніяких причин думати, що його ідея буде невірною в інших просторах. Просто в n-вимірному просторі для задання орієнтації треба зробити n поворотів.

Тепер означення повороту для нас дати зовсім легко:

Поворот
Зміна двох вибраних координат точки за системою (1). (Вибір координат задає площину повороту)

Проектування

Трошки комбінаторних розрахунків. З означення випливає, що вершин у куба 2n. В тривимірного 8=23. Ребер n2n-1. В тривимірного куба 12=3*22.

Можна просто створити функцію яка за номером вершини визначає її координати. Як я вже казав в означенні, всі координати вершини рівні за модулем одиниці. Тобто кожна з них дорівнює або -1, або 1. А це не що інше, як двійкове представлення номера вершини, де замість 0 взято -1.

Добре було б аналогічно придумати функцію, яка за номером ребра повертає номери вершин, які це ребро з’єднує. Вершини з’єднані ребром відрізняються лише однією координатою. Тому, ребро можна задати як номер координати в якій відрізняються вершини ребра, і бітовий код решти вершин. Цей двійковий код вершин, які не змінюються буде займати n-1 біт на початку числа. Все решта буде номером координати яка міняється.

Схема побітових перетворень

Схема побітових перетворень

Тобто, спочатку зсувом на n вправо визначаємо x. Потім вирізаємо перших x-1 cимволів з нашого числа, вставляємо на х-тій позиції нуль, або одиничку (залежно від того яку точку ми хочемо отримати), і дописуємо до кінця решту бітів.

Код

#include <GL/glut.h>
#include <stdlib.h>
#include <math.h>

const int DIMENSIONS=5;
const int VERTEXES=1<<DIMENSIONS;
const int EDGES=DIMENSIONS*(1<<(DIMENSIONS-1));

typedef float Vertex[DIMENSIONS];

void GenVertexBin(int num, Vertex ver) // generate vertex from binary form of integer num
{
    for(int i=0;i<DIMENSIONS;i++)
    {
        ver[i]=(0.5-(num&1))*2;
        num>>=1;
    }
};

int Avertex(int num) // get number of first vertex of edge
{
    int x=num>>(DIMENSIONS-1);
    num=num%(1<<(DIMENSIONS-1));
    int res=num%(1<<x);
    num>>=x;
    num<<=x+1;
    return res|num;
}
int Bvertex(int num) // second vertex of edge
{
    int x=num>>(DIMENSIONS-1);
    return Avertex(num)|(1<<x);
}

class Ncube // n dimensional cube
{
    Vertex vertexes[VERTEXES];
public:
    void reset(void) // sets cube into orthogonal position
    {
        for(int i=0;i<VERTEXES;i++)
            GenVertexBin(i,vertexes[i]);
    }
    void rotate(int a,int b,float angle) // rotates cube inside plane ab
    {
        float x,y;
        angle*=3.1415926/180;
        for(int i=0;i<VERTEXES;i++)
        {
            x=vertexes[i][a]*cos(angle)-vertexes[i][b]*sin(angle);
            y=vertexes[i][a]*sin(angle)+vertexes[i][b]*cos(angle);
            vertexes[i][a]=x;
            vertexes[i][b]=y;
        }
    }
    void draw() // draws flat projection of cube onto xy plane
    {
        glColor3f(1,1,1);
        glBegin(GL_LINES);
            for(int i=0;i<EDGES;i++)
            {
                glVertex3f(vertexes[Avertex(i)][0],vertexes[Avertex(i)][1],0);
                glVertex3f(vertexes[Bvertex(i)][0],vertexes[Bvertex(i)][1],0);
            }
        glEnd();
    }
};

Ncube cube;

І щоб відрендерити картинку на початку цієї статті я використав таку послідовність поворотів:

    cube.reset();

    cube.rotate(0,1,45);
    cube.rotate(4,3,45);
    cube.rotate(3,2,45);
    cube.rotate(2,1,45);
    cube.rotate(0,4,45);
Advertisements

Written by bunyk

Квітень 27, 2009 at 07:18

Оприлюднено в Графіка, Кодерство

Tagged with , ,

Відповідей: 15

Subscribe to comments with RSS.

  1. це 5-вимірний куб?

    круто, я теж колись задумувався над n-вимірними просторами, також думав над проекціями. Щоправда відмовився ілюструвати на екрані. Чому? По-перше, було впадлу думати над математикою. По-друге, якщо логічно подумати, при проектування 4-вимірного куба на площину ми втратимо 2 виміри! Половина вимірів зникне, і зрозуміти, що було спочатку – не вдасться.

    Але було би цікаво спроектувати 4-вимірний куб на 3-вимірний простір. Це було б набагато краще. Лишилось тільки зрозуміти, як намалювати синьо-червону картинку для стерео окулярів (благо вони у мене є)

    danbst

    Квітень 27, 2009 at 14:16

  2. На російскій вікіпедії в статті тессеракт є стереокартинка.

    bunyk

    Квітень 27, 2009 at 17:02

  3. ого, сказитися можна 🙂

    ELECTRIC

    Квітень 30, 2009 at 11:05

  4. Невже ніхто не зрозумів, що тут все надзвичайно просто, чого не скажеш про вивід суцільних граней? Коли потрібно визначити яка грань видима, а яка ні, і що взагалі таке грань, і видимість? 🙂

    bunyk

    Травень 3, 2009 at 20:32

  5. зроби генератор тих gif-ок, що на ру.вікі я бачив. там де тессеракт крутиться. дуже сподобалось, можна в темку про фрактали додати – типу краса математики

    danbst

    Травень 3, 2009 at 23:40

  6. Я думав. Але це вже тема для окремої здоровенної статті:
    Рендеринг в GIF з OpenGL. А я навіть в текстуру ще не рендерив. Не те щоб її потім зберігати.

    bunyk

    Травень 4, 2009 at 01:44

  7. Ти псих!

    uBusinessMan

    Червень 2, 2009 at 02:51

  8. Стараюсь :))

    bunyk

    Червень 2, 2009 at 02:57

  9. […] багато людей мені мали б і так заздрити через те, що я інколи щось хочу, і бігом це роблю, а вони терпіти не можуть ні математику ні […]

  10. […] доведеться, просто насолоджуйтесь красою. Це схоже на мої дослідження гіперкубів, тільки на порядок вище. До речі, не завважували в мене […]

  11. А про інші геом. об’єкти не думав?
    Я знайшов спосіб швидко знаходити координати вершин
    n-вимірного тетраедру:

    2D: (-x2, y1)
    ( x2, y1)
    ( 0, y2)

    3D: (-x2, y1, z1)
    ( x2, y1, z1)
    ( 0, y2, z1)
    ( 0, 0, z2)

    4D: (-x2, y1, z1, w1)
    ( x2, y1, z1, w1)
    ( 0, y2, z1, w1)
    ( 0, 0, z2, w1)
    ( 0, 0, 0, w2)

    і т. д.
    де
    x2 = a^2/(s*sqrt(a^2-0^2)); // виходить x1 = a/2
    x1 = -sqrt(x2^2-0^2); // x2 = -a/2
    y2 = a^2/(s*sqrt(a^2-x2^2));
    y1 = -sqrt(y2^2-x2^2);
    z2 = a^2/(s*sqrt(a^2-y2^2));
    z1 = -sqrt(z2^2-y2^2);
    a – ребро тетраедру.
    Не знав, що це може знадобитися.

    vlad

    Жовтень 1, 2010 at 14:26

    • Думав, але не додумався. 🙂

      Позначимо \vec x = (x_1,x_2,\ldots , x_n)

      Якось так виходить, що коли ми будуємо (i+1)-вимірний тетраедр, ми беремо i-вимірний як основу, яка розміщена в гіперплощині x_n = w_{n_1}, тобто додаємо до кожного існуючого вектора ще одну координату з якимось значенням, а потім додаємо ще одну вершину в точку (0,0,\ldots,w_{n_2}).

      Як знаходяться значення w_{n_1} і w_{n_2}?

      І чи немає в тебе картинок того що вийшло?

      bunyk

      Жовтень 1, 2010 at 14:54

      • Так, беремо і-вимірний за основу, “опускаємо” його, на w1, о потім додаємо вершину, треба щоб:
        x_2^2+y_1^2=y_2^2;
        x_2^2+(y_2-y_1)^2=a^2;
        перше рівняння для того щоб всі вершини були на однаковій відстані від центру, а друге – щоб були рівні сторони.
        w_{n2} = a^2/(s*\sqrt{a^2-w_{(n-1)2}^2});
        w_{n1} = -\sqrt{w_{n2}^2-w_{(n-1)2}^2};

        (не знаю як написати індекси)

        Індекси пишуться якщо писати формулу так: $latex x_n^2 $, що дасть нам x_n^2
        Коментар змінено адміністратором, який щиро сподівається що зміст не спотворився. Якщо це не так – вкажіть.

        vlad

        Жовтень 1, 2010 at 21:32

      • w2 = a^2/(s*sqrt(a^2-z2^2));
        w1 = -sqrt(w2^2-z2^2);
        і т. д.

        vlad

        Жовтень 1, 2010 at 21:43


Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: