source: trunk/BUTE/src/PreComputingRuns/VoronoiGenerator.cpp @ 126

#include "dxstdafx.h"
#include ".\voronoigenerator.h"
#include <map>
//#include <gl/gl.h>
//#include <gl/glut.h>


VoronoiGenerator::VoronoiGenerator(void)
{
}

VoronoiGenerator::~VoronoiGenerator(void)
{
}

void VoronoiGenerator::addDir(const Vector& d)
{
        if(dirs.size()<3)
        {
                dirs.push_back(d);
                return;
        }
        if(dirs.size() == 3)
        {
                dirs.push_back(d);
                if(
                        ((dirs[0] - dirs[1]) && 
                        (dirs[0] - dirs[2]))
                        *
                        dirs[3]
                        >  0.0
                        )
                {
                        tris.push_back(Tri(this, 0, 1, 2));
                        tris.push_back(Tri(this, 0, 3, 1));
                        tris.push_back(Tri(this, 2, 1, 3));
                        tris.push_back(Tri(this, 0, 2, 3));
                }
                else
                {
                        tris.push_back(Tri(this, 0, 2, 1));
                        tris.push_back(Tri(this, 0, 1, 3));
                        tris.push_back(Tri(this, 0, 3, 2));
                        tris.push_back(Tri(this, 1, 2, 3));
                }
                return;
        }
        dirs.push_back(d);
        std::multimap<int, int> edges;
        int stest;

        std::vector<Tri>::iterator a = tris.begin();
        std::vector<Tri>::iterator end = tris.end();
        while(a != end)
        {
                if(a->violates(d))
                {
                        bool needsab = true, needsbc = true, needsca = true;
                        std::multimap<int, int>::iterator fnd = edges.find(a->bi);
                        while(fnd != edges.end() && fnd->first == a->bi)
                        {
                                if(fnd->second == a->ai)
                                {
                                        edges.erase(fnd);
                                        needsab = false;
                                        break;
                                }
                                fnd++;
                        }
                        fnd = edges.find(a->ci);
                        while(fnd != edges.end() && fnd->first == a->ci)
                        {
                                if(fnd->second == a->bi)
                                {
                                        edges.erase(fnd);
                                        needsbc = false;
                                        break;
                                }
                                fnd++;
                        }
                        fnd = edges.find(a->ai);
                        while(fnd != edges.end() && fnd->first == a->ai)
                        {
                                if(fnd->second == a->ci)
                                {
                                        edges.erase(fnd);
                                        needsca = false;
                                        break;
                                }
                                fnd++;
                        }

                        if(needsab)
                                edges.insert(std::pair<int, int>(a->ai, a->bi));
                        if(needsbc)
                                edges.insert(std::pair<int, int>(a->bi, a->ci));
                        if(needsca)
                                edges.insert(std::pair<int, int>(a->ci, a->ai));
                        a = tris.erase(a);
                        end = tris.end();
                }
                else
                        a++;
        }
        std::multimap<int, int>::iterator l = edges.begin();
        std::multimap<int, int>::iterator lend = edges.end();
        int lastindex = dirs.size() - 1;
        stest = edges.size();
        while(l != lend)
        {
                tris.push_back(Tri(this, lastindex, l->first, l->second));
                l++;
        }
}

VoronoiGenerator::Tri::Tri(VoronoiGenerator* omesh, int ai, int bi, int ci)
{
        mesh = omesh;
        this->ai = ai;
        this->bi = bi;
        this->ci = ci;
        n = (mesh->dirs[ai] - mesh->dirs[bi]) &&
                (mesh->dirs[ai] - mesh->dirs[ci]);
        n.normalize();
        r = n * mesh->dirs[ai];
}

void VoronoiGenerator::Tri::refresh()
{
        n = (mesh->dirs[ai] - mesh->dirs[bi]) &&
                (mesh->dirs[ai] - mesh->dirs[ci]);
        n.normalize();
        r = n * mesh->dirs[ai];
}

bool VoronoiGenerator::Tri::violates(const Vector& p)
{
        return (p * n) > r;
}

bool VoronoiGenerator::Tri::contains(const Vector& p)
{
        if((p * n) < r)
                return false;
        Vector da = mesh->dirs[ai];
        Vector db = mesh->dirs[bi];
        Vector dc = mesh->dirs[ci];
        Vector cross = da && db;
        if(p * cross < 0.0)
                return false;
        cross = db && dc;
        if(p * cross < 0.0)
                return false;
        cross = dc && da;
        if(p * cross < 0.0)
                return false;
        return true;
}


void VoronoiGenerator::glDrawDelaunay(std::vector<Vector>& powers)
{
        /*
        glBegin(GL_TRIANGLES);
                std::vector<Tri>::iterator a = tris.begin();
                std::vector<Tri>::iterator end = tris.end();
                while(a != end)
                {
                        glColor3d(powers[a->ai].r / 1000.0, powers[a->ai].g / 1000.0, powers[a->ai].b / 1000.0);
                        glVertex3d(dirs[a->ai].x, dirs[a->ai].y, dirs[a->ai].z);
                        glColor3d(powers[a->bi].r / 1000.0, powers[a->bi].g / 1000.0, powers[a->bi].b / 1000.0);
                        glVertex3d(dirs[a->bi].x, dirs[a->bi].y, dirs[a->bi].z);
                        glColor3d(powers[a->ci].r / 1000.0, powers[a->ci].g / 1000.0, powers[a->ci].b / 1000.0);
                        glVertex3d(dirs[a->ci].x, dirs[a->ci].y, dirs[a->ci].z);
                        a++;
                }
        glEnd();
        */
}

struct D3DVERTEX{
        D3DXVECTOR3 pos;
        D3DXVECTOR3 normal;
        D3DXVECTOR2 tex0;
        D3DXVECTOR2 tex1;
        D3DXVECTOR3 tex2;
};

void VoronoiGenerator::d3dDrawDelaunay(LPDIRECT3DDEVICE9 device)
{
        std::vector<Tri>::iterator a = tris.begin();
        std::vector<Tri>::iterator end = tris.end();
        while(a != end)
        {
                D3DVERTEX tr[3];
            tr[0].pos=D3DXVECTOR3(dirs[a->ai].x, dirs[a->ai].y, dirs[a->ai].z);
                tr[1].pos=D3DXVECTOR3(dirs[a->bi].x, dirs[a->bi].y, dirs[a->bi].z);
                tr[2].pos=D3DXVECTOR3(dirs[a->ci].x, dirs[a->ci].y, dirs[a->ci].z);

                device->DrawPrimitiveUP(D3DPT_TRIANGLELIST, 1, tr, sizeof(D3DVERTEX));
                a++;
        }


}

void VoronoiGenerator::relaxLloyd()
{
        double* voroAreas = new double[dirs.size()];
        std::vector<Vector> relaxedDirs;
        relaxedDirs.insert(relaxedDirs.begin(), dirs.size(), Vector::RGBBLACK);
/*      for(int r=0; r<dirs.size(); r++)
        {
                voroAreas[r] = 0.0;
        }*/

        std::vector<Tri>::iterator a = tris.begin();
        std::vector<Tri>::iterator end = tris.end();
        while(a != end)
        {
                Vector la = (dirs[a->bi] - dirs[a->ai]);
                Vector lb = (dirs[a->ci] - dirs[a->ai]);
                double lcos = la * lb;
                if(lcos >= 1.0)
                        lcos = 1.0;
                double triArea = 
                        sqrt(la.norm2() * la.norm2() * (1.0 - lcos * lcos)) / 4.0;
//              double lsin = sqrt(1.0 - lcos * lcos);
//              relaxedDirs[a->ai] += a->n * lsin;
//              relaxedDirs[a->bi] += a->n * lsin;
//              relaxedDirs[a->ci] += a->n * lsin;
                relaxedDirs[a->ai] += (dirs[a->ai] * 4.0 + dirs[a->bi] + dirs[a->ci]) * 0.166666666666 * triArea;
                relaxedDirs[a->bi] += (dirs[a->ai] + dirs[a->bi] * 4.0 + dirs[a->ci]) * 0.166666666666 * triArea;
                relaxedDirs[a->ci] += (dirs[a->ai] + dirs[a->bi] + dirs[a->ci] * 4.0) * 0.166666666666 * triArea;
//              voroAreas[a->ai] += triArea;
//              voroAreas[a->bi] += triArea;
//              voroAreas[a->ci] += triArea;
                a++;
        }
        std::vector<Vector>::iterator d = relaxedDirs.begin();
        std::vector<Vector>::iterator dend = relaxedDirs.end();
        int idx = 0;
        while(d != dend)
        {
/*              if(voroAreas[idx] == 0.0)
                {
                        char mess[200];
                        sprintf(mess, "HEY: %d", idx);
                        AfxMessageBox(mess);
                        voroAreas[idx] = 1.0;
                }
                (*d) *= 1.0 / voroAreas[idx];*/
                d->normalize();
                d++;
                idx++;
        }
        dirs = relaxedDirs;
        delete voroAreas;
        std::vector<Tri>::iterator rfa = tris.begin();
        std::vector<Tri>::iterator rfend = tris.end();
        while(rfa != rfend)
        {
                rfa->refresh();
                rfa++;
        }
}

int VoronoiGenerator::lastNearestTriIndex = 0;

int VoronoiGenerator::getNearestDirIndex(const Vector& pd)
{
        std::vector<Tri>::iterator a = tris.begin() + lastNearestTriIndex;
        std::vector<Tri>::iterator end = tris.end();
        std::vector<Tri>::iterator finitor = end;
        if(lastNearestTriIndex)
                finitor = tris.begin() + (lastNearestTriIndex - 1);
        while(a != finitor)
        {
                if(a == end)
                {
                        a = tris.begin();
                        if(a == finitor)
                                break;
                }
                if(a->contains(pd))
                {
                        lastNearestTriIndex = a - tris.begin();
                        double adist = dirs[a->ai] * pd;
                        double bdist = dirs[a->bi] * pd;
                        double cdist = dirs[a->ci] * pd;
                        if(adist > bdist && adist > cdist)
                                return a->ai;
                        if(bdist > adist && bdist > cdist)
                                return a->bi;
                        if(cdist > adist && cdist > bdist)
                                return a->ci;
                }
                a++;
        }
        return 0;
}