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

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

Що ж придумав я? Поверхню я вже обрахував. Точок на ній має бути приблизно . (Це правда залежить від множини, але якщо вважати що , то найбільше залежить від цього). Всі точки зберігаються в STL-івській структурі map, тому доступ до кожної гарантовано за . Знайти всі трикутники я вирішив пошуком в ширину:

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

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

Глюки 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 трикутники

Тоді я знову переключився на 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 трикутники)

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

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";
    }

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

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

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

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

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

:

Теж , але більше точок, і інший ракурс.

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

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