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