source: GTP/trunk/App/Demos/Illum/PathMap/MergeTree.cpp @ 896

Revision 896, 4.7 KB checked in by szirmay, 19 years ago (diff)
Line 
1#include "dxstdafx.h"
2#include "mergetree.h"
3
4MergeTree::MergeTree(unsigned short nOccluders, Occluder* occArray)
5        :freeNodes( 4 )//nOccluders  >>1)
6{
7        maxR = 0.0f;
8        this->nOccluders = nOccluders;
9        locations = new unsigned short[nOccluders];
10        pool = new Node[nOccluders << 1];
11        nAllocated = 0;
12        occluders = occArray;
13}
14
15MergeTree::~MergeTree(void)
16{
17        delete pool;
18}
19
20
21void MergeTree::searchOptimalMerger(unsigned short p)
22{
23        if(pool[p].type == MERGETREELEAFNODE)
24        {
25                if(indexOfCandidate == pool[p].occluderIndex)
26                {
27                        foundMyselfAllRight = true;
28                        return;
29                }
30                float R = occluders[indexOfCandidate].solidRadius;
31                float r = occluders[pool[p].occluderIndex].solidRadius;
32        Vector diff = occluders[pool[p].occluderIndex].centre - occluders[indexOfCandidate].centre;
33                float d = diff.norm();
34                float cost;
35                if(R > r)
36                        cost = d;// + r - R;
37                else
38                        cost = d;// + R - r;
39                if(cost < minCost){
40                        minCost = cost;
41                        minMerger = pool[p].occluderIndex;
42                }
43                return;
44        }
45        else
46        {
47                float distToCut = occluders[indexOfCandidate].centre[pool[p].type] - pool[p].cut;
48                if(distToCut > 0.0f)
49                {
50                        searchOptimalMerger( pool[p].right );
51                        if(distToCut < minCost /*+ maxR*/)
52                                searchOptimalMerger( pool[p].left );
53                }
54                else
55                {
56                        searchOptimalMerger( pool[p].left );
57                        if(-distToCut < minCost /*+ maxR*/)
58                                searchOptimalMerger( pool[p].right );
59                }
60        }
61}
62
63void MergeTree::insert(unsigned short index)
64{
65        if(occluders[index].solidRadius > maxR)
66                maxR = occluders[index].solidRadius;
67        if(nAllocated == 0)
68        {
69                locations[index] = 0;
70                pool[0].occluderIndex = index;
71                pool[0].type = MERGETREELEAFNODE;
72                pool[0].parent = 0;
73                nAllocated++;
74        }
75        else
76        {
77                unsigned short p = 0;
78                for(;;)
79                {
80                        if(pool[p].type == MERGETREELEAFNODE)
81                        {
82                                unsigned short other = pool[p].occluderIndex;
83                                if(freeNodes.isEmpty())
84                                {
85                                        pool[p].left = nAllocated++;
86                                        pool[p].right = nAllocated++;
87                                }
88                                else
89                                {
90                                        pool[p].left = freeNodes.removeMin();
91                                        pool[p].right = freeNodes.removeMin();
92                                }
93
94                                Vector diff = occluders[index].centre - occluders[other].centre;
95
96                                char dominantDir;
97                                if(fabsf(diff[0]) > fabsf(diff[1]))
98                                        if(fabsf(diff[0]) > fabsf(diff[2]))
99                                                dominantDir = 0;
100                                        else
101                                                dominantDir = 2;
102                                else
103                                        if(fabsf(diff[1]) > fabsf(diff[2]))
104                                                dominantDir = 1;
105                                        else
106                                                dominantDir = 2;
107
108                                pool[p].type = dominantDir;
109                                pool[p].cut = occluders[other].centre[dominantDir] + (diff[dominantDir] * 0.5f);
110                                pool[pool[p].left].type = MERGETREELEAFNODE;
111                                pool[pool[p].left].occluderIndex = (diff[dominantDir] > 0.0f)?other:index;
112                                pool[pool[p].right].type = MERGETREELEAFNODE;
113                                pool[pool[p].right].occluderIndex = (diff[dominantDir] > 0.0f)?index:other;
114                                locations[other] = (diff[dominantDir] > 0.0f)?pool[p].left:pool[p].right;
115                                locations[index] = (diff[dominantDir] > 0.0f)?pool[p].right:pool[p].left;
116                                pool[locations[other]].parent = p;
117                                pool[locations[index]].parent = p;
118                                return;
119                        }
120                        else
121                        {
122                                if(occluders[index].centre[pool[p].type] > pool[p].cut)
123                                        p = pool[p].right;
124                                else
125                                        p = pool[p].left;
126                        }
127                }
128        }
129}
130
131void MergeTree::remove(unsigned short index)
132{
133        unsigned short p = locations[index];
134        unsigned short parent = pool[p].parent;
135        unsigned short grandpa = pool[parent].parent;
136        freeNodes.insert(pool[parent].left);
137        freeNodes.insert(pool[parent].right);
138        if(pool[parent].left == p)
139                pool[parent] = pool[pool[parent].right];
140        else
141                pool[parent] = pool[pool[parent].left];
142        pool[parent].parent = grandpa;
143        if(pool[parent].type == MERGETREELEAFNODE)
144                locations[pool[parent].occluderIndex] = parent;
145        else
146        {
147                pool[pool[parent].left].parent = parent;
148                pool[pool[parent].right].parent = parent;
149        }
150}
151
152bool MergeTree::verify(unsigned short p, float minx, float maxx, float miny, float maxy, float minz, float maxz)
153{
154        if(pool[p].type == MERGETREELEAFNODE)
155        {
156                Vector& a = occluders[pool[p].occluderIndex].centre;
157                return a.x >= minx && a.x <= maxx &&
158                                a.y >= miny && a.y <= maxy &&
159                                a.z >= minz && a.z <= maxz;
160        }
161        else
162        {
163                if(pool[p].type == 0)
164                        return
165                                verify(pool[p].left, minx, pool[p].cut, miny, maxy, minz, maxz)
166                                &&
167                                verify(pool[p].right, pool[p].cut, maxx, miny, maxy, minz, maxz);
168                if(pool[p].type == 1)
169                        return
170                                verify(pool[p].left, minx, maxx , miny, pool[p].cut, minz, maxz)
171                                &&
172                                verify(pool[p].right, minx, maxx, pool[p].cut, maxy, minz, maxz);
173                if(pool[p].type == 2)
174                        return
175                                verify(pool[p].left, minx, maxx , miny, maxy, minz, pool[p].cut)
176                                &&
177                                verify(pool[p].right, minx, maxx, miny, maxy, pool[p].cut, maxz);
178        }
179}
Note: See TracBrowser for help on using the repository browser.