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

Revision 126, 7.1 KB checked in by barsi, 19 years ago (diff)

Added a folder remotely
Line 
1#include "dxstdafx.h"
2#include ".\voronoigenerator.h"
3#include <map>
4//#include <gl/gl.h>
5//#include <gl/glut.h>
6
7
8VoronoiGenerator::VoronoiGenerator(void)
9{
10}
11
12VoronoiGenerator::~VoronoiGenerator(void)
13{
14}
15
16void VoronoiGenerator::addDir(const Vector& d)
17{
18        if(dirs.size()<3)
19        {
20                dirs.push_back(d);
21                return;
22        }
23        if(dirs.size() == 3)
24        {
25                dirs.push_back(d);
26                if(
27                        ((dirs[0] - dirs[1]) &&
28                        (dirs[0] - dirs[2]))
29                        *
30                        dirs[3]
31                        >  0.0
32                        )
33                {
34                        tris.push_back(Tri(this, 0, 1, 2));
35                        tris.push_back(Tri(this, 0, 3, 1));
36                        tris.push_back(Tri(this, 2, 1, 3));
37                        tris.push_back(Tri(this, 0, 2, 3));
38                }
39                else
40                {
41                        tris.push_back(Tri(this, 0, 2, 1));
42                        tris.push_back(Tri(this, 0, 1, 3));
43                        tris.push_back(Tri(this, 0, 3, 2));
44                        tris.push_back(Tri(this, 1, 2, 3));
45                }
46                return;
47        }
48        dirs.push_back(d);
49        std::multimap<int, int> edges;
50        int stest;
51
52        std::vector<Tri>::iterator a = tris.begin();
53        std::vector<Tri>::iterator end = tris.end();
54        while(a != end)
55        {
56                if(a->violates(d))
57                {
58                        bool needsab = true, needsbc = true, needsca = true;
59                        std::multimap<int, int>::iterator fnd = edges.find(a->bi);
60                        while(fnd != edges.end() && fnd->first == a->bi)
61                        {
62                                if(fnd->second == a->ai)
63                                {
64                                        edges.erase(fnd);
65                                        needsab = false;
66                                        break;
67                                }
68                                fnd++;
69                        }
70                        fnd = edges.find(a->ci);
71                        while(fnd != edges.end() && fnd->first == a->ci)
72                        {
73                                if(fnd->second == a->bi)
74                                {
75                                        edges.erase(fnd);
76                                        needsbc = false;
77                                        break;
78                                }
79                                fnd++;
80                        }
81                        fnd = edges.find(a->ai);
82                        while(fnd != edges.end() && fnd->first == a->ai)
83                        {
84                                if(fnd->second == a->ci)
85                                {
86                                        edges.erase(fnd);
87                                        needsca = false;
88                                        break;
89                                }
90                                fnd++;
91                        }
92
93                        if(needsab)
94                                edges.insert(std::pair<int, int>(a->ai, a->bi));
95                        if(needsbc)
96                                edges.insert(std::pair<int, int>(a->bi, a->ci));
97                        if(needsca)
98                                edges.insert(std::pair<int, int>(a->ci, a->ai));
99                        a = tris.erase(a);
100                        end = tris.end();
101                }
102                else
103                        a++;
104        }
105        std::multimap<int, int>::iterator l = edges.begin();
106        std::multimap<int, int>::iterator lend = edges.end();
107        int lastindex = dirs.size() - 1;
108        stest = edges.size();
109        while(l != lend)
110        {
111                tris.push_back(Tri(this, lastindex, l->first, l->second));
112                l++;
113        }
114}
115
116VoronoiGenerator::Tri::Tri(VoronoiGenerator* omesh, int ai, int bi, int ci)
117{
118        mesh = omesh;
119        this->ai = ai;
120        this->bi = bi;
121        this->ci = ci;
122        n = (mesh->dirs[ai] - mesh->dirs[bi]) &&
123                (mesh->dirs[ai] - mesh->dirs[ci]);
124        n.normalize();
125        r = n * mesh->dirs[ai];
126}
127
128void VoronoiGenerator::Tri::refresh()
129{
130        n = (mesh->dirs[ai] - mesh->dirs[bi]) &&
131                (mesh->dirs[ai] - mesh->dirs[ci]);
132        n.normalize();
133        r = n * mesh->dirs[ai];
134}
135
136bool VoronoiGenerator::Tri::violates(const Vector& p)
137{
138        return (p * n) > r;
139}
140
141bool VoronoiGenerator::Tri::contains(const Vector& p)
142{
143        if((p * n) < r)
144                return false;
145        Vector da = mesh->dirs[ai];
146        Vector db = mesh->dirs[bi];
147        Vector dc = mesh->dirs[ci];
148        Vector cross = da && db;
149        if(p * cross < 0.0)
150                return false;
151        cross = db && dc;
152        if(p * cross < 0.0)
153                return false;
154        cross = dc && da;
155        if(p * cross < 0.0)
156                return false;
157        return true;
158}
159
160
161void VoronoiGenerator::glDrawDelaunay(std::vector<Vector>& powers)
162{
163        /*
164        glBegin(GL_TRIANGLES);
165                std::vector<Tri>::iterator a = tris.begin();
166                std::vector<Tri>::iterator end = tris.end();
167                while(a != end)
168                {
169                        glColor3d(powers[a->ai].r / 1000.0, powers[a->ai].g / 1000.0, powers[a->ai].b / 1000.0);
170                        glVertex3d(dirs[a->ai].x, dirs[a->ai].y, dirs[a->ai].z);
171                        glColor3d(powers[a->bi].r / 1000.0, powers[a->bi].g / 1000.0, powers[a->bi].b / 1000.0);
172                        glVertex3d(dirs[a->bi].x, dirs[a->bi].y, dirs[a->bi].z);
173                        glColor3d(powers[a->ci].r / 1000.0, powers[a->ci].g / 1000.0, powers[a->ci].b / 1000.0);
174                        glVertex3d(dirs[a->ci].x, dirs[a->ci].y, dirs[a->ci].z);
175                        a++;
176                }
177        glEnd();
178        */
179}
180
181struct D3DVERTEX{
182        D3DXVECTOR3 pos;
183        D3DXVECTOR3 normal;
184        D3DXVECTOR2 tex0;
185        D3DXVECTOR2 tex1;
186        D3DXVECTOR3 tex2;
187};
188
189void VoronoiGenerator::d3dDrawDelaunay(LPDIRECT3DDEVICE9 device)
190{
191        std::vector<Tri>::iterator a = tris.begin();
192        std::vector<Tri>::iterator end = tris.end();
193        while(a != end)
194        {
195                D3DVERTEX tr[3];
196            tr[0].pos=D3DXVECTOR3(dirs[a->ai].x, dirs[a->ai].y, dirs[a->ai].z);
197                tr[1].pos=D3DXVECTOR3(dirs[a->bi].x, dirs[a->bi].y, dirs[a->bi].z);
198                tr[2].pos=D3DXVECTOR3(dirs[a->ci].x, dirs[a->ci].y, dirs[a->ci].z);
199
200                device->DrawPrimitiveUP(D3DPT_TRIANGLELIST, 1, tr, sizeof(D3DVERTEX));
201                a++;
202        }
203
204
205}
206
207void VoronoiGenerator::relaxLloyd()
208{
209        double* voroAreas = new double[dirs.size()];
210        std::vector<Vector> relaxedDirs;
211        relaxedDirs.insert(relaxedDirs.begin(), dirs.size(), Vector::RGBBLACK);
212/*      for(int r=0; r<dirs.size(); r++)
213        {
214                voroAreas[r] = 0.0;
215        }*/
216
217        std::vector<Tri>::iterator a = tris.begin();
218        std::vector<Tri>::iterator end = tris.end();
219        while(a != end)
220        {
221                Vector la = (dirs[a->bi] - dirs[a->ai]);
222                Vector lb = (dirs[a->ci] - dirs[a->ai]);
223                double lcos = la * lb;
224                if(lcos >= 1.0)
225                        lcos = 1.0;
226                double triArea =
227                        sqrt(la.norm2() * la.norm2() * (1.0 - lcos * lcos)) / 4.0;
228//              double lsin = sqrt(1.0 - lcos * lcos);
229//              relaxedDirs[a->ai] += a->n * lsin;
230//              relaxedDirs[a->bi] += a->n * lsin;
231//              relaxedDirs[a->ci] += a->n * lsin;
232                relaxedDirs[a->ai] += (dirs[a->ai] * 4.0 + dirs[a->bi] + dirs[a->ci]) * 0.166666666666 * triArea;
233                relaxedDirs[a->bi] += (dirs[a->ai] + dirs[a->bi] * 4.0 + dirs[a->ci]) * 0.166666666666 * triArea;
234                relaxedDirs[a->ci] += (dirs[a->ai] + dirs[a->bi] + dirs[a->ci] * 4.0) * 0.166666666666 * triArea;
235//              voroAreas[a->ai] += triArea;
236//              voroAreas[a->bi] += triArea;
237//              voroAreas[a->ci] += triArea;
238                a++;
239        }
240        std::vector<Vector>::iterator d = relaxedDirs.begin();
241        std::vector<Vector>::iterator dend = relaxedDirs.end();
242        int idx = 0;
243        while(d != dend)
244        {
245/*              if(voroAreas[idx] == 0.0)
246                {
247                        char mess[200];
248                        sprintf(mess, "HEY: %d", idx);
249                        AfxMessageBox(mess);
250                        voroAreas[idx] = 1.0;
251                }
252                (*d) *= 1.0 / voroAreas[idx];*/
253                d->normalize();
254                d++;
255                idx++;
256        }
257        dirs = relaxedDirs;
258        delete voroAreas;
259        std::vector<Tri>::iterator rfa = tris.begin();
260        std::vector<Tri>::iterator rfend = tris.end();
261        while(rfa != rfend)
262        {
263                rfa->refresh();
264                rfa++;
265        }
266}
267
268int VoronoiGenerator::lastNearestTriIndex = 0;
269
270int VoronoiGenerator::getNearestDirIndex(const Vector& pd)
271{
272        std::vector<Tri>::iterator a = tris.begin() + lastNearestTriIndex;
273        std::vector<Tri>::iterator end = tris.end();
274        std::vector<Tri>::iterator finitor = end;
275        if(lastNearestTriIndex)
276                finitor = tris.begin() + (lastNearestTriIndex - 1);
277        while(a != finitor)
278        {
279                if(a == end)
280                {
281                        a = tris.begin();
282                        if(a == finitor)
283                                break;
284                }
285                if(a->contains(pd))
286                {
287                        lastNearestTriIndex = a - tris.begin();
288                        double adist = dirs[a->ai] * pd;
289                        double bdist = dirs[a->bi] * pd;
290                        double cdist = dirs[a->ci] * pd;
291                        if(adist > bdist && adist > cdist)
292                                return a->ai;
293                        if(bdist > adist && bdist > cdist)
294                                return a->bi;
295                        if(cdist > adist && cdist > bdist)
296                                return a->ci;
297                }
298                a++;
299        }
300        return 0;
301}
Note: See TracBrowser for help on using the repository browser.