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

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

Курсова3

with 4 comments

Вчора в мене знову з’явився настрій писати мою курсову. Ті проблеми з дірками в поверхні що були минулого разу вирішились, і я вже забув чому. Я пробував з’єднати сусідні точки по три штуки в трикутники. Ага. Сказати просто. Найпростіший алгоритм – брати всі трійки точок, і дивитись чи лежать вони на поверхні, і чи сусідні. Але тоді алгоритм стає складності o(n^9) що хоч і поліноміально, але страшно.

Що ж придумав я? Поверхню я вже обрахував. Точок на ній має бути приблизно n^2. (Це правда залежить від множини, але якщо вважати що n=\frac{1}{\delta}, то найбільше залежить від цього). Всі точки зберігаються в STL-івській структурі map, тому доступ до кожної гарантовано за o(n \log n). Знайти всі трикутники я вирішив пошуком в ширину:

  1. Беремо будь-яку точку, додаємо в чергу.
  2. Якщо черга порожня, завершуємо роботу.
  3. Витягуємо з черги точку, позначаємо її використаною, і дивимось всеможливі трикутники, які мають вершиною нашу точку.
  4. Якщо дві інші точки трикутника лежать на поверхні, і ще не використані, то додаємо новий трикутник в список, а точки в чергу.
  5. Переходимо до пункту 2.

Звичайно, таке працює тільки для замкненої поверхні. Але я сподівався потім трохи розширити алгоритм. Проблеми почались одразу з перебору можливих трикутників. Якщо наприклад навколо точки (0,0,0) є 26 сусідніх точок, то скільки різних трикутників можна до них побудувати? Повний перебір показав, що 132. Хоча кілька разів, я помилково отримував результати від 650 до 24. А так, як бачити трикутники всередині оболонки я не мав можливості, вирішив вивести тільки ребра. І отримав цікавий глюк:

Глюки glPolygonMode

Глюки glPolygonMode

(23:06:27) bunyk: що цікаво, після команди
glPolygonMode(GL_FRONT,GL_LINE);
екран перестає очищатись, а після
glPolygonMode(GL_BACK,GL_LINE);
– ні

Тоді я забив на glPolygonMode і вирішив просто вивести ребра класичним glBegin(GL_LINE_LOOP);. І зміг побачити, що 24 трикутники, це таки замало, бо куб воно з’єднує тільки по швах:

Шви

Шви

Але в кінці кінців, я таки написав програму, яка вивела мені всі можливі трикутники:

	#include <iostream>

using namespace std;
const int POSSIBLE_TRIANGLES_COUNT=650;
int possible_triangles[POSSIBLE_TRIANGLES_COUNT][6];

int d(int a,int b)
{
    int res=a-b;
    if(res<0) return -res;
    return res;
}

void init_possible_triangles()
{
    int count=0;
    for(int i=-1;i<2;i++)
        for(int j=-1;j<2;j++)
            for(int k=-1;k<2;k++)
                for(int l=-1;l<2;l++)
                    for(int m=-1;m<2;m++)
                        for(int n=-1;n<2;n++)
                        {
                            if(((i==0)&&(j==0)&&(k==0))||((l==0)&&(m==0)&&(n==0))||((i==l)&&(j==m)&&(k==n))||(d(i,l)>1)||(d(j,m)>1)||(d(k,n)>1)) continue;

                            possible_triangles[count][0]=i;
                            possible_triangles[count][1]=j;
                            possible_triangles[count][2]=k;
                            possible_triangles[count][3]=l;
                            possible_triangles[count][4]=m;
                            possible_triangles[count][5]=n;
                            count++;
                            //cout << "(" << i << "," << j << "," << k << ")";
                            //cout << "(" << l << "," << m << "," << n << ")\n";
                        }
    cout << count;
    int ncount=0;
    for(int i=0;i<count;i++)
    {
        bool unik=true;
        for(int j=i+1;j<count;j++)
        {
            if(
                (possible_triangles[i][0]==possible_triangles[j][3])&&
                (possible_triangles[i][1]==possible_triangles[j][4])&&
                (possible_triangles[i][2]==possible_triangles[j][5])&&
                (possible_triangles[j][0]==possible_triangles[i][3])&&
                (possible_triangles[j][1]==possible_triangles[i][4])&&
                (possible_triangles[j][2]==possible_triangles[i][5])
                )
            {
                unik=false;
                break;
            }
        }
        if(unik)
        {
            ncount++;
            cout << "{" << possible_triangles[i][0];
            cout << "," << possible_triangles[i][1];
            cout << "," << possible_triangles[i][2];
            cout << "," << possible_triangles[i][3];
            cout << "," << possible_triangles[i][4];
            cout << "," << possible_triangles[i][5];

            // normal

            cout << "," << possible_triangles[i][1]*possible_triangles[i][5]
                         - possible_triangles[i][4]*possible_triangles[i][2];
            cout << "," << possible_triangles[i][0]*possible_triangles[i][5]
                         - possible_triangles[i][3]*possible_triangles[i][2];
            cout << "," << possible_triangles[i][0]*possible_triangles[i][4]
                         - possible_triangles[i][1]*possible_triangles[i][3];

            cout << "},\n";
        }
    }
    cout << ncount;
}
int main()
{
    cout << "Hello world!" << endl;
    init_possible_triangles();
    return 0;
}

Вона навіть обчислила нормалі, але про це трохи пізніше. Ну, і я таки отримав набір трикутників поверхні:

9383 трикутники

9383 трикутники

Тоді я знову переключився на GL_TRIANGLES, але для цього треба було нормалі. На щастя їх можна було обчислити при обрахуванні всеможливоих трикутників. Ця функція дуже просто додалась в програму описану вище. Програма згенерувала мені такий красивий модуль:

	const int POSSIBLE_TRIANGLES_COUNT=132;
const int possible_triangles[POSSIBLE_TRIANGLES_COUNT][9]={
{-1,-1,0,-1,-1,-1,1,1,0},
{-1,-1,1,-1,-1,0,1,1,0},
{-1,0,-1,-1,-1,-1,-1,0,1},
// ще 128 рядків з нуликів, одиничок і мінус одиничок, від яких заснути можна.
//Перші три цифри - зміщення другої вершини трикутника відносно першої,
// другі три - відповідно третьої, а останні три - нормаль.
{1,1,1,1,1,0,-1,-1,0}
};

Мене трохи розчарував результат:

Рандомно направлені нормалі

Рандомно направлені нормалі

Але хто в ньому був винен? Напевне векторний добуток, але звідки йому знати в який бік має стирчати нормаль?

Прийшлось додавати вектор нормалі до першої вершини кожного трикутника, і дивитись, чи знаходиться вона в множині. Якщо так, то розвертали її назовні. Це дало деякі результати:

Нормалі в порядку (175224 трикутники)

Нормалі в порядку (175224 трикутники)

Тоді я згадав, що треба підправити алгоритм, для несуцільних поверхонь. Для цього навколо нашого циклу пошуку в ширину, я додав ще один, який шукав ще не використану точку, і додавав її в чергу. Якщо вже всі вершини взяли участь у створенні трикутників робота закінчувалась.

void genhull()
    {
        vertexes.clear();
        for(int i=0;i<Nsize;i++)
            for(int j=0;j<Nsize;j++)
                for(int k=0;k<body[i][j].size();k++)
                {
                        vertexes[Vertex(i,j,body[i][j][k].a)]=1;
                        vertexes[Vertex(i,j,body[i][j][k].b)]=1;
                        for(int h=body[i][j][k].a+1;h<body[i][j][k].b;h++)
                        {
                            if(!(xi(i,j+1,h)&&xi(i,j-1,h)&&xi(i+1,j,h)&&xi(i-1,j,h)))
                                vertexes[Vertex(i,j,h)]=1;
                        }
                }

        queue <Vertex> processing;
        set<Vertex> used;
        Vertex cur;
        Triangle curt;
        int i;
        map<Vertex,int>::iterator it;

        while(true)
        {
        it=vertexes.begin();
        while(it->second!=1)
        {
            it++;
            if(it==vertexes.end()) return;
        }
        processing.push(it->first);

        while(!processing.empty())
        {
            cur=processing.front(); // get next element from queue
            processing.pop();
            if(vertexes[cur]!=1) // but it must be not used before
                continue;

            vertexes[cur]=2;
            for(i=0;i<POSSIBLE_TRIANGLES_COUNT;i++)
            {
                curt.c=cur;
                curt.a.x=cur.x+possible_triangles[i][0];
                curt.a.y=cur.y+possible_triangles[i][1];
                curt.a.z=cur.z+possible_triangles[i][2];

                curt.b.x=cur.x+possible_triangles[i][3];
                curt.b.y=cur.y+possible_triangles[i][4];
                curt.b.z=cur.z+possible_triangles[i][5];

                curt.n.x=possible_triangles[i][6];
                curt.n.y=possible_triangles[i][7];
                curt.n.z=possible_triangles[i][8];

                if((vertexes.count(curt.a)>0)&&(vertexes.count(curt.b)>0))
                if((vertexes[curt.a]==1)&&(vertexes[curt.b]==1))
                {
                    if(xi(curt.c.x+curt.n.x,curt.c.y+curt.n.y,curt.c.z+curt.n.z))
                    {
                        curt.n.x=-curt.n.x;
                        curt.n.y=-curt.n.y;
                        curt.n.z=-curt.n.z;
                    }
                    triangles.push_back(curt);

                    processing.push(curt.a);
                    processing.push(curt.b);
                }
            }
        } //*/
        } // end while true
        cout << triangles.size() << "\n";
    }

Таке запрацювало:

Кілька поверхонь

Кілька поверхонь

І працює для достатньо маленьких дельта:

z>x^2+y^2

Еліптичний параболоїд

Еліптичний параболоїд

Не знаю чи я вже казав, що червоні лінії ідуть паралельно осі x, і при збільшенні координати яскравість збільшується. Зелені – y, сині – z.

0<x^3+y^3+z^3<1:
3D-8 (x*x*x+y*y*y+z*z*z>0)&&(x*x*x+y*y*y+z*z*z<1)
Теж 0<x^3+y^3+z^3<1, але більше точок, і інший ракурс.
3D-9(x*x*x+y*y*y+z*z*z>0)&&(x*x*x+y*y*y+z*z*z<1)

Тепер можна працювати над багатьма напрямками, але основне – відсортувати їх в порядку пріорітетів:

  1. Розбити увесь той бидлокод на модулі.
  2. Створити згладжнені нормалі. (І подумати чи всюди потрібно згладжування, і як визначити де не потрібно?)
  3. Зробити структуру мешу стандарту 3ds.
  4. Приробити якийсь інтерфейс. (Вивчити GTK?)
  5. Приробити парсер функцій.
  6. Оптимізація.
Advertisements

Written by bunyk

Жовтень 22, 2009 at 10:40

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

Tagged with

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

Subscribe to comments with RSS.

  1. 7. Згладити кубелі =)) хоч і так стильно

    три тори дуже реалістичні доречі, ефект металу ти зробив супер

    danbst

    Жовтень 23, 2009 at 12:53

    • Ефект металу? glColor3f(1,1,1); 🙂 🙂 🙂 😉

      Це вже не кубелі, придивись до торів ближче. Це 132 різні трикутники. (В кубелях було умовно кажучи 6 квадратів).

      bunyk

      Жовтень 23, 2009 at 14:33

  2. >складності o(n^9) що хоч і полігонально, але страшно.

    поліноміально?
    ))

    ulidtko

    Жовтень 23, 2009 at 15:39


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

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

Лого WordPress.com

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

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

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