1 #ifndef PHOTONHEAP_HXX
2 #define PHOTONHEAP_HXX
3
4 #include "Photon.hxx"
5
6 // A new class, DistantPhoton, to allow additional storing of
7 // distances to a reference point
8 class DistantPhoton
9 {
10 public:
11 Photon *photon;
12 float distance;
13
14 DistantPhoton(Photon *photon, Vec3f reference)
15 : photon(photon)
16 {
17 Vec3f dist = photon->point - reference;
18 distance = Dot(dist, dist);
19 };
20 };
21
22 // Order function according to the distance
23 bool operator<(DistantPhoton photon1, DistantPhoton photon2)
24 {
25 return (photon1.distance < photon2.distance);
26 };
27
28 // Heap to create radiance estimates
29 class PhotonHeap
30 {
31 DistantPhoton **heap;
32 int count,
33 fill_level;
34
35 // Usual heapify function (will not be commented further as it is... well... pure standard...)
36 void heapify (int position = 0)
37 {
38 int lchild = 2 * position + 1,
39 mchild = lchild + 1;
40
41 if (mchild >= count)
42 return;
43
44 if (heap[lchild] && heap[mchild])
45 {
46 if (*heap[position] < *heap[lchild] || *heap[position] < *heap[mchild])
47 {
48 if (*heap[lchild] < *heap[mchild])
49 {
50 DistantPhoton *help = heap[mchild];
51 heap[mchild] = heap[position];
52 heap[position] = help;
53 heapify(mchild);
54 }
55 else
56 {
57 DistantPhoton *help = heap[lchild];
58 heap[lchild] = heap[position];
59 heap[position] = help;
60 heapify(lchild);
61 }
62 }
63 }
64 else if (heap[lchild] && *heap[position] < *heap[lchild])
65 {
66 DistantPhoton *help = heap[lchild];
67 heap[lchild] = heap[position];
68 heap[position] = help;
69 heapify(lchild);
70 }
71 else if (heap[mchild] && *heap[position] < *heap[mchild])
72 {
73 DistantPhoton *help = heap[mchild];
74 heap[mchild] = heap[position];
75 heap[position] = help;
76 heapify(mchild);
77 }
78 };
79
80 // Sorts heap by subsequently heapifying the partial heaps
81 void sort()
82 {
83 for (int i = count - 1; i >= 0; --i)
84 heapify(i);
85 };
86 public:
87 Vec3f reference;
88 float maxdist2,
89 maxdist;
90
91 PhotonHeap(Vec3f reference, const int number, float maxdist2)
92 : count(number), fill_level(0), reference(reference), maxdist2(maxdist2)
93 {
94 heap = new DistantPhoton*[number];
95 maxdist = sqrt(maxdist2);
96
97 for (int i = 0; i < number; ++i)
98 heap[i] = NULL;
99 };
100
101 virtual ~PhotonHeap()
102 {
103 for (int i = 0; i < count; ++i)
104 if (heap[i])
105 delete(heap[i]);
106
107 delete[] heap;
108 };
109
110 // Quick access to the stored content
111 virtual Photon *operator[](int i)
112 {
113 if (heap[i])
114 return heap[i]->photon;
115 else
116 return NULL;
117 };
118
119 // Get the distance
120 virtual float Distance2(int i)
121 {
122 return heap[i]->distance;
123 };
124
125 // Insert a photon into the heap
126 virtual void Insert(Photon *photon)
127 {
128 DistantPhoton *newphoton = new DistantPhoton(photon, reference);
129 Insert(newphoton);
130 };
131
132 // Insert a DistancePhoton
133 virtual void Insert(DistantPhoton *photon)
134 {
135 // In the first place, we use the heap as simple vector
136 if (fill_level < count)
137 {
138 heap[fill_level] = photon;
139 ++fill_level;
140
141 if (fill_level == count)
142 sort();
143 }
144 else
145 {
146 // As soon as we have more than the RE, we use the heap as true heap
147 if (!heap[0] || photon->distance < heap[0]->distance)
148 {
149 if (heap[0])
150 delete heap[0];
151 heap[0] = photon;
152 maxdist2 = heap[0]->distance;
153 maxdist = sqrt(maxdist2);
154 }
155 else
156 delete photon;
157
158 heapify();
159 }
160 };
161 };
162
163 #endif
syntax highlighted by Code2HTML, v. 0.9.1