00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 #include "pbrt.h"
00026 #include "sampling.h"
00027
00028 #define SQRT_SAMPLE_TABLE_SIZE 64
00029 #define SAMPLE_TABLE_SIZE (SQRT_SAMPLE_TABLE_SIZE * \
00030 SQRT_SAMPLE_TABLE_SIZE)
00031
00032 int line_num = 0;
00033 string current_file;
00034
00035 static float imageSamples[SAMPLE_TABLE_SIZE][2];
00036 static float timeSamples[SAMPLE_TABLE_SIZE];
00037 static float lensSamples[SAMPLE_TABLE_SIZE][2];
00038
00039 static void addSampleToGrid(float sample[][2],
00040 int sampleNum, SampleGrid *grid) {
00041 int u = GRID(sample[sampleNum][0]);
00042 int v = GRID(sample[sampleNum][1]);
00043 (*grid)[u][v].push_back(sampleNum);
00044 }
00045 inline float Wrapped1DDist(float a, float b) {
00046 float d = fabsf(a - b);
00047 if (d < 0.5f) return d;
00048 else return 1.f - max(a, b) + min(a, b);
00049 }
00050
00051 void BestCandidate2D(float table[][2],
00052 int count, SampleGrid *grid = NULL);
00053 static void
00054 Redistribute2D(float samples[][2], SampleGrid &pixelGrid);
00055 int main() {
00056
00057 SampleGrid pixelGrid;
00058 BestCandidate2D(imageSamples,
00059 SAMPLE_TABLE_SIZE, &pixelGrid);
00060
00061 ProgressReporter timeProgress(SAMPLE_TABLE_SIZE, "Time samples");
00062 for (int i = 0; i < SAMPLE_TABLE_SIZE; ++i)
00063 timeSamples[i] = (i + RandomFloat()) /
00064 SAMPLE_TABLE_SIZE;
00065 for (int currentSample = 1;
00066 currentSample < SAMPLE_TABLE_SIZE;
00067 ++currentSample) {
00068
00069 int best = -1;
00070
00071 float maxMinDelta = 0.;
00072 for (int t = currentSample; t < SAMPLE_TABLE_SIZE; ++t) {
00073
00074 int gu = GRID(imageSamples[currentSample][0]);
00075 int gv = GRID(imageSamples[currentSample][1]);
00076 float minDelta = INFINITY;
00077 for (int du = -1; du <= 1; ++du) {
00078 for (int dv = -1; dv <= 1; ++dv) {
00079
00080
00081 int u = gu + du, v = gv + dv;
00082 if (u < 0) u += BC_GRID_SIZE;
00083 if (u >= BC_GRID_SIZE) u -= BC_GRID_SIZE;
00084 if (v < 0) v += BC_GRID_SIZE;
00085 if (v >= BC_GRID_SIZE) v -= BC_GRID_SIZE;
00086 for (u_int g = 0; g < pixelGrid[u][v].size(); ++g) {
00087 int otherSample = pixelGrid[u][v][g];
00088 if (otherSample < currentSample) {
00089 float dt = Wrapped1DDist(timeSamples[otherSample],
00090 timeSamples[t]);
00091 minDelta = min(minDelta, dt);
00092 }
00093 }
00094 }
00095 }
00096
00097 if (minDelta > maxMinDelta) {
00098 maxMinDelta = minDelta;
00099 best = t;
00100 }
00101 }
00102 Assert(best != -1);
00103 swap(timeSamples[best], timeSamples[currentSample]);
00104 timeProgress.Update();
00105 }
00106 timeProgress.Done();;
00107
00108 BestCandidate2D(lensSamples, SAMPLE_TABLE_SIZE);
00109 Redistribute2D(lensSamples, pixelGrid);
00110
00111 FILE *f = fopen("sampledata.cpp", "w");
00112 if (f == NULL) {
00113 Severe("Couldn't open sampledata.cpp for writing.");
00114 }
00115 fprintf(f, "\n/* Automatically generated %dx%d sample "
00116 "table (%s @ %s) */\n\n",
00117 SQRT_SAMPLE_TABLE_SIZE, SQRT_SAMPLE_TABLE_SIZE,
00118 __DATE__, __TIME__);
00119 fprintf(f, "const float "
00120 "BestCandidateSampler::sampleTable[%d][5] = {\n",
00121 SAMPLE_TABLE_SIZE);
00122 for (int i = 0; i < SAMPLE_TABLE_SIZE; ++i) {
00123 fprintf(f, " { ");
00124 fprintf(f, "%10.10ff, %10.10ff, ", imageSamples[i][0],
00125 imageSamples[i][1]);
00126 fprintf(f, "%10.10ff, ", timeSamples[i]);
00127 fprintf(f, "%10.10ff, %10.10ff, ", lensSamples[i][0],
00128 lensSamples[i][1]);
00129 fprintf(f, "},\n");
00130 }
00131 fprintf(f, "};\n");
00132 return 0;
00133 }
00134 void BestCandidate2D(float table[][2], int totalSamples,
00135 SampleGrid *grid) {
00136 SampleGrid localGrid;
00137 if (!grid) grid = &localGrid;
00138 ProgressReporter
00139 progress(totalSamples-1, "Throwing Darts");
00140
00141 table[0][0] = RandomFloat();
00142 table[0][1] = RandomFloat();
00143 addSampleToGrid(table, 0, grid);
00144 for (int currentSample = 1;
00145 currentSample < totalSamples;
00146 ++currentSample) {
00147
00148 float maxDist2 = 0.;
00149 int numCandidates = 500 * currentSample;
00150 for (int currentCandidate = 0;
00151 currentCandidate < numCandidates;
00152 ++currentCandidate) {
00153
00154 float candidate[2];
00155 candidate[0] = RandomFloat();
00156 candidate[1] = RandomFloat();
00157
00158 float sampleDist2 = INFINITY;
00159 int gu = GRID(candidate[0]), gv = GRID(candidate[1]);
00160 for (int du = -1; du <= 1; ++du) {
00161 for (int dv = -1; dv <= 1; ++dv) {
00162
00163 int u = gu + du, v = gv + dv;
00164 if (u < 0) u += BC_GRID_SIZE;
00165 if (u >= BC_GRID_SIZE) u -= BC_GRID_SIZE;
00166 if (v < 0) v += BC_GRID_SIZE;
00167 if (v >= BC_GRID_SIZE) v -= BC_GRID_SIZE;
00168
00169 for (u_int g = 0; g < (*grid)[u][v].size(); ++g) {
00170 int s = (*grid)[u][v][g];
00171 float xdist = Wrapped1DDist(candidate[0], table[s][0]);
00172 float ydist = Wrapped1DDist(candidate[1], table[s][1]);
00173 float d2 = xdist*xdist + ydist*ydist;
00174 sampleDist2 = min(sampleDist2, d2);
00175 }
00176 }
00177 }
00178
00179 if (sampleDist2 > maxDist2) {
00180 maxDist2 = sampleDist2;
00181 table[currentSample][0] = candidate[0];
00182 table[currentSample][1] = candidate[1];
00183 }
00184 }
00185 addSampleToGrid(table, currentSample, grid);
00186 progress.Update();
00187 }
00188 progress.Done();
00189 }
00190 static void Redistribute2D(float samples[][2],
00191 SampleGrid &pixelGrid) {
00192 ProgressReporter progress(SAMPLE_TABLE_SIZE, "Redistribution");
00193 for (int currentSample = 1;
00194 currentSample < SAMPLE_TABLE_SIZE; ++currentSample) {
00195
00196 int best = -1;
00197
00198 float maxMinDist2 = 0.f;
00199 for (int samp = currentSample; samp < SAMPLE_TABLE_SIZE;
00200 ++samp) {
00201
00202 int gu = GRID(imageSamples[currentSample][0]);
00203 int gv = GRID(imageSamples[currentSample][1]);
00204 float minDist2 = INFINITY;
00205 for (int du = -1; du <= 1; ++du) {
00206 for (int dv = -1; dv <= 1; ++dv) {
00207
00208
00209 int u = gu + du, v = gv + dv;
00210 if (u < 0) u += BC_GRID_SIZE;
00211 if (u >= BC_GRID_SIZE) u -= BC_GRID_SIZE;
00212 if (v < 0) v += BC_GRID_SIZE;
00213 if (v >= BC_GRID_SIZE) v -= BC_GRID_SIZE;
00214 for (u_int g = 0; g < pixelGrid[u][v].size(); ++g) {
00215 int s2 = pixelGrid[u][v][g];
00216 if (s2 < currentSample) {
00217 float dx = Wrapped1DDist(samples[s2][0],
00218 samples[samp][0]);
00219 float dy = Wrapped1DDist(samples[s2][1],
00220 samples[samp][1]);
00221 float d2 = dx*dx + dy*dy;
00222 minDist2 = min(d2, minDist2);
00223 }
00224 }
00225 }
00226 }
00227
00228 if (minDist2 > maxMinDist2) {
00229 maxMinDist2 = minDist2;
00230 best = samp;
00231 }
00232 }
00233 Assert(best != -1);
00234 swap(samples[best][0], samples[currentSample][0]);
00235 swap(samples[best][1], samples[currentSample][1]);
00236 progress.Update();
00237 }
00238 fprintf(stderr, "\n");
00239 progress.Done();
00240 }