<commit_before>/***************************************************************************
 *   Copyright (C) 1998-2010 by authors (see AUTHORS.txt )                 *
 *                                                                         *
 *   This file is part of LuxRays.                                         *
 *                                                                         *
 *   LuxRays is free software; you can redistribute it and/or modify       *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 3 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   LuxRays is distributed in the hope that it will be useful,            *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>. *
 *                                                                         *
 *   LuxRays website: http://www.luxrender.net                             *
 ***************************************************************************/

// Based on smallppm, Progressive Photon Mapping by <NAME>

#include <cstdio>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <string>
#include <sstream>
#include <stdexcept>

#if defined (WIN32)
#include <windows.h>
#endif

// Jens's patch for MacOS
#if defined(__APPLE__)
#include <GLut/glut.h>
#else
#include <GL/glut.h>
#endif

#include <FreeImage.h>
#include <boost/detail/container_fwd.hpp>

#include "luxrays/luxrays.h"
#include "luxrays/core/device.h"
#include "luxrays/utils/sdl/scene.h"
#include "luxrays/utils/core/randomgen.h"
#include "luxrays/core/intersectiondevice.h"
#include "luxrays/core/pixel/framebuffer.h"
#include "luxrays/utils/film/film.h"

#define MAX_EYE_PATH_DEPTH 16
#define MAX_PHOTON_PATH_DEPTH 16

enum EyePathState {
	TO_TRACE, HIT, CONSTANT_COLOR
};

class EyePath {
public:
	EyePathState state;

	// Screen information
	float scrX, scrY;

	// Eye path information
	luxrays::Ray ray;
	luxrays::RayHit rayHit;
	unsigned int depth;
	luxrays::Spectrum throughput;
	luxrays::Spectrum constantColor;

	// hit point information
	luxrays::Point position;
	luxrays::Normal normal;
	const luxrays::sdl::SurfaceMaterial *material;

	float photonRadius2;
	unsigned int accumPhotonCount;
	luxrays::Spectrum accumReflectedFlux;
};

class PhotonPath {
public:
	// The ray is stored in the RayBuffer and the index is implicitly stored
	// in the array of PhotonPath
	luxrays::Spectrum flux;
	unsigned int depth;
};

class HashGrid {
public:
	HashGrid(const float s, const luxrays::BBox bb, std::vector<std::list<EyePath *> *> *grid) {
		invHashSize = s;
		gridBBox = bb;
		hashGrid = grid;
	}

	~HashGrid() {
		delete hashGrid;
	}

	float invHashSize;
	luxrays::BBox gridBBox;
	std::vector<std::list<EyePath *> *> *hashGrid;
};

//------------------------------------------------------------------------------

static std::string SPPMG_LABEL = "LuxRays SmallPPMGPU v" LUXRAYS_VERSION_MAJOR "." LUXRAYS_VERSION_MINOR " (LuxRays demo: http://www.luxrender.net)";

static luxrays::Context *ctx = NULL;
static luxrays::sdl::Scene *scene = NULL;

static double startTime = 0.0;
static unsigned int scrRefreshInterval = 2000;

static unsigned int imgWidth = 640;
static unsigned int imgHeight = 480;
static unsigned int imgSuperSampling = 2;
static std::string imgFileName = "image.png";
static luxrays::utils::Film *film = NULL;
static luxrays::SampleBuffer *sampleBuffer = NULL;

static boost::thread *renderThread = NULL;
static unsigned int photonTraced = 0;

static std::vector<EyePath> *eyePathsPtr = NULL;

//------------------------------------------------------------------------------

void FreeImageErrorHandler(FREE_IMAGE_FORMAT fif, const char *message) {
	printf("\n*** ");
	if(fif != FIF_UNKNOWN)
		printf("%s Format\n", FreeImage_GetFormatFromFIF(fif));

	printf("%s", message);
	printf(" ***\n");
}

void DebugHandler(const char *msg) {
	std::cerr << msg << std::endl;
}

//------------------------------------------------------------------------------

static void UpdateFrameBuffer() {
	if (!film)
		return;

	film->Reset();

	std::vector<EyePath> &eyePaths = *eyePathsPtr;
	for (unsigned int i = 0; i < eyePaths.size(); ++i) {
		EyePath *eyePath = &eyePaths[i];

		switch (eyePath->state) {
			case CONSTANT_COLOR: {
				sampleBuffer->SplatSample(eyePath->scrX, eyePath->scrY, eyePath->constantColor);
				break;
			}
			case HIT: {
				const luxrays::Spectrum rad = (eyePath->accumPhotonCount == 0) ? luxrays::Spectrum() :
					(eyePath->accumReflectedFlux / (M_PI * eyePath->photonRadius2 * photonTraced));
				sampleBuffer->SplatSample(eyePath->scrX, eyePath->scrY, rad);
				break;
			}
			default:
				assert(false);
				break;
		}

		if (sampleBuffer->IsFull()) {
			// Splat all samples on the film
			film->SplatSampleBuffer(true, sampleBuffer);
			sampleBuffer = film->GetFreeSampleBuffer();
		}
	}

	if (sampleBuffer->GetSampleCount() > 0) {
		// Splat all samples on the film
		film->SplatSampleBuffer(true, sampleBuffer);
		sampleBuffer = film->GetFreeSampleBuffer();
	}
}

//------------------------------------------------------------------------------

static float RadicalInverse(u_int n, u_int base) {
	float val = 0.f;
	const float invBase = 1.f / base;
	float invBi = invBase;
	while (n > 0) {
		// Compute next digit of radical inverse
		u_int d_i = (n % base);
		val += d_i * invBi;
		n /= base;
		invBi *= invBase;
	}

	return val;
}

static std::vector<EyePath> *BuildEyePaths(luxrays::sdl::Scene *scene, luxrays::RandomGenerator *rndGen,
	luxrays::IntersectionDevice *device, luxrays::RayBuffer *rayBuffer,
	const unsigned int width, const unsigned int height) {
	std::vector<EyePath> *eyePathsPtr = new std::vector<EyePath>(width * height * imgSuperSampling * imgSuperSampling);
	std::vector<EyePath> &eyePaths = *eyePathsPtr;
	std::list<EyePath *> todoEyePaths;

	// Generate eye rays
	std::cerr << "Building eye paths rays with " << imgSuperSampling << "x" << imgSuperSampling << " super-sampling:" << std::endl;
	std::cerr << "  0/" << height << std::endl;
	double lastPrintTime = luxrays::WallClockTime();
	unsigned int index = 0;
	const float invImgSuperSampling = 1.f / imgSuperSampling;
	for (unsigned int y = 0; y < height; ++y) {
		if (luxrays::WallClockTime() - lastPrintTime > 2.0) {
			std::cerr << "  " << y << "/" << height << std::endl;
			lastPrintTime = luxrays::WallClockTime();
		}

		for (unsigned int x = 0; x < width; ++x) {
			for (unsigned int sy = 0; sy < imgSuperSampling; ++sy) {
				for (unsigned int sx = 0; sx < imgSuperSampling; ++sx) {
					EyePath *eyePath = &eyePaths[index++];

					eyePath->scrX = x + (sx + rndGen->floatValue()) * invImgSuperSampling - 0.5f;
					eyePath->scrY = y + (sy + rndGen->floatValue()) * invImgSuperSampling - 0.5f;
					scene->camera->GenerateRay(eyePath->scrX, eyePath->scrY, width, height, &eyePath->ray,
							rndGen->floatValue(), rndGen->floatValue(), rndGen->floatValue());

					eyePath->depth = 0;
					eyePath->throughput = luxrays::Spectrum(1.f, 1.f, 1.f);
					eyePath->constantColor = luxrays::Spectrum(0.f, 0.f, 0.f);
					eyePath->state = TO_TRACE;

					todoEyePaths.push_back(eyePath);
				}
			}
		}
	}

	// Iterate through all eye paths
	std::cerr << "Building eye paths hit points: " << std::endl;
	bool done;
	lastPrintTime = luxrays::WallClockTime();
	// Note: (todoEyePaths.size() > 0) is extremly slow to execute
	unsigned int todoEyePathCount = width * height * imgSuperSampling * imgSuperSampling;
	std::cerr << "  " << todoEyePathCount / 1000 << "k eye paths left" << std::endl;
	while(todoEyePathCount > 0) {
		if (luxrays::WallClockTime() - lastPrintTime > 2.0) {
			std::cerr << "  " << todoEyePathCount / 1000 << "k eye paths left" << std::endl;
			lastPrintTime = luxrays::WallClockTime();
		}

		std::list<EyePath *>::iterator todoEyePathsIterator = todoEyePaths.begin();
		while (todoEyePathsIterator != todoEyePaths.end()) {
			EyePath *eyePath = *todoEyePathsIterator;

			assert (eyePath->state == TO_TRACE);

			// Check if we reached the max path depth
			if (eyePath->depth > MAX_EYE_PATH_DEPTH) {
				todoEyePathsIterator = todoEyePaths.erase(todoEyePathsIterator);
				--todoEyePathCount;
				eyePath->state = CONSTANT_COLOR;
			} else {
				eyePath->depth++;
				rayBuffer->AddRay(eyePath->ray);
				done = false;
				if (rayBuffer->IsFull())
					break;

				++todoEyePathsIterator;
			}
		}

		if (rayBuffer->GetRayCount() > 0) {
			// Trace the rays
			device->PushRayBuffer(rayBuffer);
			rayBuffer = device->PopRayBuffer();

			// Update the paths
			todoEyePathsIterator = todoEyePaths.begin();
			for (unsigned int i = 0; i < rayBuffer->GetRayCount(); ++i) {
				EyePath *eyePath = *todoEyePathsIterator;

				assert (eyePath->state == TO_TRACE);

				const luxrays::RayHit *rayHit = &rayBuffer->GetHitBuffer()[i];

				if (rayHit->Miss()) {
					todoEyePathsIterator = todoEyePaths.erase(todoEyePathsIterator);
					--todoEyePathCount;
					if (scene->infiniteLight)
						eyePath->constantColor = scene->infiniteLight->Le(eyePath->ray.d) * eyePath->throughput;

					eyePath->state = CONSTANT_COLOR;
				} else {
					// Something was hit
					const luxrays::Point hitPoint = eyePath->ray(rayHit->t);
					const unsigned int currentTriangleIndex = rayHit->index;

					// Get the triangle
					const luxrays::ExtTriangleMesh *mesh = scene->objects[scene->dataSet->GetMeshID(currentTriangleIndex)];
					const luxrays::Triangle &tri = mesh->GetTriangles()[scene->dataSet->GetMeshTriangleID(currentTriangleIndex)];

					// Get the material
					const luxrays::sdl::Material *triMat = scene->triangleMaterials[currentTriangleIndex];

					luxrays::Spectrum surfaceColor;
					const luxrays::Spectrum *colors = mesh->GetColors();
					if (colors)
						surfaceColor = luxrays::InterpolateTriColor(tri, colors, rayHit->b1, rayHit->b2);
					else
						surfaceColor = luxrays::Spectrum(1.f, 1.f, 1.f);

					// Interpolate face normal
					luxrays::Normal N = luxrays::InterpolateTriNormal(tri, mesh->GetNormal(), rayHit->b1, rayHit->b2);

					// Check if I have to apply texture mapping or normal mapping
					luxrays::sdl::TexMapInstance *tm = scene->triangleTexMaps[currentTriangleIndex];
					luxrays::sdl::BumpMapInstance *bm = scene->triangleBumpMaps[currentTriangleIndex];
					luxrays::sdl::NormalMapInstance *nm = scene->triangleNormalMaps[currentTriangleIndex];
					if (tm || bm || nm) {
						// Interpolate UV coordinates if required
						const luxrays::UV triUV = luxrays::InterpolateTriUV(tri, mesh->GetUVs(), rayHit->b1, rayHit->b2);

						// Check if there is an assigned texture map
						if (tm)	{
							const luxrays::sdl::TextureMap *map = tm->GetTexMap();

							// Apply texture mapping
							surfaceColor *= map->GetColor(triUV);

							// Check if the texture map has an alpha channel
							if (map->HasAlpha()) {
								const float alpha = map->GetAlpha(triUV);

								if ((alpha == 0.0f) || ((alpha < 1.f) && (rndGen->floatValue() > alpha))) {
									eyePath->ray = luxrays::Ray(hitPoint, eyePath->ray.d);
									continue;
								}
							}
						}

						// Check if there is an assigned bump/normal map
						if (bm || nm) {
							if (nm) {
								// Apply normal mapping
								const luxrays::Spectrum color = nm->GetTexMap()->GetColor(triUV);

								const float x = 2.0 * (color.r - 0.5);
								const float y = 2.0 * (color.g - 0.5);
								const float z = 2.0 * (color.b - 0.5);

								luxrays::Vector v1, v2;
								luxrays::CoordinateSystem(luxrays::Vector(N), &v1, &v2);
								N = luxrays::Normalize(luxrays::Normal(
										v1.x * x + v2.x * y + N.x * z,
										v1.y * x + v2.y * y + N.y * z,
										v1.z * x + v2.z * y + N.z * z));
							}

							if (bm) {
								// Apply bump mapping
								const luxrays::sdl::TextureMap *map = bm->GetTexMap();
								const luxrays::UV &dudv = map->GetDuDv();

								const float b0 = map->GetColor(triUV).Filter();

								const luxrays::UV uvdu(triUV.u + dudv.u, triUV.v);
								const float bu = map->GetColor(uvdu).Filter();

								const luxrays::UV uvdv(triUV.u, triUV.v + dudv.v);
								const float bv = map->GetColor(uvdv).Filter();

								const float scale = bm->GetScale();
								const luxrays::Vector bump(scale * (bu - b0), scale * (bv - b0), 1.f);

								luxrays::Vector v1, v2;
								luxrays::CoordinateSystem(luxrays::Vector(N), &v1, &v2);
								N = luxrays::Normalize(luxrays::Normal(
										v1.x * bump.x + v2.x * bump.y + N.x * bump.z,
										v1.y * bump.x + v2.y * bump.y + N.y * bump.z,
										v1.z * bump.x + v2.z * bump.y + N.z * bump.z));
							}
						}
					}

					// Flip the normal if required
					luxrays::Normal shadeN;
					if (luxrays::Dot(eyePath->ray.d, N) > 0.f)
						shadeN = -N;
					else
						shadeN = N;

					if (triMat->IsLightSource()) {
						todoEyePathsIterator = todoEyePaths.erase(todoEyePathsIterator);
						--todoEyePathCount;

						const luxrays::sdl::TriangleLight *tLight = (luxrays::sdl::TriangleLight *)triMat;
						eyePath->constantColor = tLight->Le(scene->objects, -eyePath->ray.d) * eyePath->throughput;
						eyePath->state = CONSTANT_COLOR;
					} else if (triMat->IsDiffuse()) {
						todoEyePathsIterator = todoEyePaths.erase(todoEyePathsIterator);
						--todoEyePathCount;

						eyePath->rayHit = *rayHit;
						eyePath->material = (luxrays::sdl::SurfaceMaterial *)triMat;
						eyePath->throughput *= surfaceColor;
						eyePath->position = hitPoint;
						eyePath->normal = shadeN;
						eyePath->state = HIT;
					} else {
						// Build the next vertex path ray
						const luxrays::sdl::SurfaceMaterial *triSurfMat = (luxrays::sdl::SurfaceMaterial *)triMat;

						float fPdf;
						luxrays::Vector wi;
						bool specularBounce;
						const luxrays::Spectrum f = triSurfMat->Sample_f(-eyePath->ray.d, &wi, N, shadeN,
								rndGen->floatValue(), rndGen->floatValue(), rndGen->floatValue(),
								true, &fPdf, specularBounce) * surfaceColor;
						if ((fPdf <= 0.f) || f.Black()) {
							todoEyePathsIterator = todoEyePaths.erase(todoEyePathsIterator);
							--todoEyePathCount;

							eyePath->state = CONSTANT_COLOR;
						} else {
							++todoEyePathsIterator;

							eyePath->throughput *= f / fPdf;
							eyePath->ray = luxrays::Ray(hitPoint, wi);
						}
					}
				}
			}

			rayBuffer->Reset();
		}
	}

	return eyePathsPtr;
}

static unsigned int Hash(const int ix, const int iy, const int iz, const unsigned int hashGridSize) {
	return (unsigned int)((ix * 73856093) ^ (iy * 19349663) ^ (iz * 83492791)) % hashGridSize;
}

static HashGrid *BuildHashGrid(
	std::vector<EyePath *> &hitPoints,
	const unsigned int width, const unsigned int height) {
	// Calculate hit points bounding box
	std::cerr << "Building hit points bounding box: ";
	luxrays::BBox hpBBox;
	for (unsigned int i = 0; i < hitPoints.size(); ++i)
		hpBBox = luxrays::Union(hpBBox, hitPoints[i]->position);
	std::cerr << hpBBox << std::endl;

	// Calculate initial radius
	luxrays::Vector ssize = hpBBox.pMax - hpBBox.pMin;
	const float photonRadius = ((ssize.x + ssize.y + ssize.z) / 3.f) / ((width * imgSuperSampling + height * imgSuperSampling) / 2.f) * 2.f;

	// Expand the bounding box by used radius
	hpBBox.Expand(photonRadius);

	// Initialize hit points field
	const float photonRadius2 = photonRadius * photonRadius;
	for (unsigned int i = 0; i < hitPoints.size(); ++i) {
		EyePath *eyePath = hitPoints[i];

		eyePath->photonRadius2 = photonRadius2;
		eyePath->accumPhotonCount = 0;
		eyePath->accumReflectedFlux = luxrays::Spectrum();
	}

	const float hashs = 1.f / (photonRadius * 2.f);
	// TODO: add a tunable parameter for hashgrid size
	const unsigned int hashGridSize = hitPoints.size();
	// TODO: optimize std::vector<std::vector<EyePath *> > type to save memory
	std::vector<std::list<EyePath *> *> *hashGridPtr = new std::vector<std::list<EyePath *> *>(hashGridSize);
	std::vector<std::list<EyePath *> *> &hashGrid = *hashGridPtr;

	std::cerr << "Building hit points hash grid...";
	const luxrays::Vector vphotonRadius(photonRadius, photonRadius, photonRadius);
	unsigned int maxPathCount = 0;
	for (unsigned int i = 0; i < hitPoints.size(); ++i) {
		EyePath *eyePath = hitPoints[i];

		const luxrays::Vector bMin = ((eyePath->position - vphotonRadius) - hpBBox.pMin) * hashs;
		const luxrays::Vector bMax = ((eyePath->position + vphotonRadius) - hpBBox.pMin) * hashs;

		for (int iz = abs(int(bMin.z)); iz <= abs(int(bMax.z)); iz++) {
			for (int iy = abs(int(bMin.y)); iy <= abs(int(bMax.y)); iy++) {
				for (int ix = abs(int(bMin.x)); ix <= abs(int(bMax.x)); ix++) {
					int hv = Hash(ix, iy, iz, hashGridSize);

					if (hashGrid[hv] == NULL)
						hashGrid[hv] = new std::list<EyePath *>();

					hashGrid[hv]->push_back(eyePath);

					if (hashGrid[hv]->size() > maxPathCount)
						maxPathCount = hashGrid[hv]->size();
				}
			}
		}
	}
	std::cerr << "Done" << std::endl;
	std::cerr << "Max path count in a single hash grid entry: " << maxPathCount << std::endl;

	return new HashGrid(hashs, hpBBox, hashGridPtr);
}

static void InitPhotonPath(luxrays::sdl::Scene *scene, luxrays::RandomGenerator *rndGen,
	PhotonPath *photonPath, luxrays::Ray *ray) {<commit_msg>SPPG: added some more progress information<commit_after>/***************************************************************************
 *   Copyright (C) 1998-2010 by authors (see AUTHORS.txt )                 *
 *                                                                         *
 *   This file is part of LuxRays.                                         *
 *                                                                         *
 *   LuxRays is free software; you can redistribute it and/or modify       *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 3 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   LuxRays is distributed in the hope that it will be useful,            *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>. *
 *                                                                         *
 *   LuxRays website: http://www.luxrender.net                             *
 ***************************************************************************/

// Based on smallppm, Progressive Photon Mapping by <NAME>

#include <cstdio>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <string>
#include <sstream>
#include <stdexcept>

#if defined (WIN32)
#include <windows.h>
#endif

// Jens's patch for MacOS
#if defined(__APPLE__)
#include <GLut/glut.h>
#else
#include <GL/glut.h>
#endif

#include <FreeImage.h>
#include <boost/detail/container_fwd.hpp>

#include "luxrays/luxrays.h"
#include "luxrays/core/device.h"
#include "luxrays/utils/sdl/scene.h"
#include "luxrays/utils/core/randomgen.h"
#include "luxrays/core/intersectiondevice.h"
#include "luxrays/core/pixel/framebuffer.h"
#include "luxrays/utils/film/film.h"

#define MAX_EYE_PATH_DEPTH 16
#define MAX_PHOTON_PATH_DEPTH 16

enum EyePathState {
	TO_TRACE, HIT, CONSTANT_COLOR
};

class EyePath {
public:
	EyePathState state;

	// Screen information
	float scrX, scrY;

	// Eye path information
	luxrays::Ray ray;
	luxrays::RayHit rayHit;
	unsigned int depth;
	luxrays::Spectrum throughput;
	luxrays::Spectrum constantColor;

	// hit point information
	luxrays::Point position;
	luxrays::Normal normal;
	const luxrays::sdl::SurfaceMaterial *material;

	float photonRadius2;
	unsigned int accumPhotonCount;
	luxrays::Spectrum accumReflectedFlux;
};

class PhotonPath {
public:
	// The ray is stored in the RayBuffer and the index is implicitly stored
	// in the array of PhotonPath
	luxrays::Spectrum flux;
	unsigned int depth;
};

class HashGrid {
public:
	HashGrid(const float s, const luxrays::BBox bb, std::vector<std::list<EyePath *> *> *grid) {
		invHashSize = s;
		gridBBox = bb;
		hashGrid = grid;
	}

	~HashGrid() {
		delete hashGrid;
	}

	float invHashSize;
	luxrays::BBox gridBBox;
	std::vector<std::list<EyePath *> *> *hashGrid;
};

//------------------------------------------------------------------------------

static std::string SPPMG_LABEL = "LuxRays SmallPPMGPU v" LUXRAYS_VERSION_MAJOR "." LUXRAYS_VERSION_MINOR " (LuxRays demo: http://www.luxrender.net)";

static luxrays::Context *ctx = NULL;
static luxrays::sdl::Scene *scene = NULL;

static double startTime = 0.0;
static unsigned int scrRefreshInterval = 2000;

static unsigned int imgWidth = 640;
static unsigned int imgHeight = 480;
static unsigned int imgSuperSampling = 2;
static std::string imgFileName = "image.png";
static luxrays::utils::Film *film = NULL;
static luxrays::SampleBuffer *sampleBuffer = NULL;

static boost::thread *renderThread = NULL;
static unsigned int photonTraced = 0;

static std::vector<EyePath> *eyePathsPtr = NULL;

//------------------------------------------------------------------------------

void FreeImageErrorHandler(FREE_IMAGE_FORMAT fif, const char *message) {
	printf("\n*** ");
	if(fif != FIF_UNKNOWN)
		printf("%s Format\n", FreeImage_GetFormatFromFIF(fif));

	printf("%s", message);
	printf(" ***\n");
}

void DebugHandler(const char *msg) {
	std::cerr << msg << std::endl;
}

//------------------------------------------------------------------------------

static void UpdateFrameBuffer() {
	if (!film)
		return;

	film->Reset();

	std::vector<EyePath> &eyePaths = *eyePathsPtr;
	for (unsigned int i = 0; i < eyePaths.size(); ++i) {
		EyePath *eyePath = &eyePaths[i];

		switch (eyePath->state) {
			case CONSTANT_COLOR: {
				sampleBuffer->SplatSample(eyePath->scrX, eyePath->scrY, eyePath->constantColor);
				break;
			}
			case HIT: {
				const luxrays::Spectrum rad = (eyePath->accumPhotonCount == 0) ? luxrays::Spectrum() :
					(eyePath->accumReflectedFlux / (M_PI * eyePath->photonRadius2 * photonTraced));
				sampleBuffer->SplatSample(eyePath->scrX, eyePath->scrY, rad);
				break;
			}
			default:
				assert(false);
				break;
		}

		if (sampleBuffer->IsFull()) {
			// Splat all samples on the film
			film->SplatSampleBuffer(true, sampleBuffer);
			sampleBuffer = film->GetFreeSampleBuffer();
		}
	}

	if (sampleBuffer->GetSampleCount() > 0) {
		// Splat all samples on the film
		film->SplatSampleBuffer(true, sampleBuffer);
		sampleBuffer = film->GetFreeSampleBuffer();
	}
}

//------------------------------------------------------------------------------

static float RadicalInverse(u_int n, u_int base) {
	float val = 0.f;
	const float invBase = 1.f / base;
	float invBi = invBase;
	while (n > 0) {
		// Compute next digit of radical inverse
		u_int d_i = (n % base);
		val += d_i * invBi;
		n /= base;
		invBi *= invBase;
	}

	return val;
}

static std::vector<EyePath> *BuildEyePaths(luxrays::sdl::Scene *scene, luxrays::RandomGenerator *rndGen,
	luxrays::IntersectionDevice *device, luxrays::RayBuffer *rayBuffer,
	const unsigned int width, const unsigned int height) {
	std::vector<EyePath> *eyePathsPtr = new std::vector<EyePath>(width * height * imgSuperSampling * imgSuperSampling);
	std::vector<EyePath> &eyePaths = *eyePathsPtr;
	std::list<EyePath *> todoEyePaths;

	// Generate eye rays
	std::cerr << "Building eye paths rays with " << imgSuperSampling << "x" << imgSuperSampling << " super-sampling:" << std::endl;
	std::cerr << "  0/" << height << std::endl;
	double lastPrintTime = luxrays::WallClockTime();
	unsigned int index = 0;
	const float invImgSuperSampling = 1.f / imgSuperSampling;
	for (unsigned int y = 0; y < height; ++y) {
		if (luxrays::WallClockTime() - lastPrintTime > 2.0) {
			std::cerr << "  " << y << "/" << height << std::endl;
			lastPrintTime = luxrays::WallClockTime();
		}

		for (unsigned int x = 0; x < width; ++x) {
			for (unsigned int sy = 0; sy < imgSuperSampling; ++sy) {
				for (unsigned int sx = 0; sx < imgSuperSampling; ++sx) {
					EyePath *eyePath = &eyePaths[index++];

					eyePath->scrX = x + (sx + rndGen->floatValue()) * invImgSuperSampling - 0.5f;
					eyePath->scrY = y + (sy + rndGen->floatValue()) * invImgSuperSampling - 0.5f;
					scene->camera->GenerateRay(eyePath->scrX, eyePath->scrY, width, height, &eyePath->ray,
							rndGen->floatValue(), rndGen->floatValue(), rndGen->floatValue());

					eyePath->depth = 0;
					eyePath->throughput = luxrays::Spectrum(1.f, 1.f, 1.f);
					eyePath->constantColor = luxrays::Spectrum(0.f, 0.f, 0.f);
					eyePath->state = TO_TRACE;

					todoEyePaths.push_front(eyePath);
				}
			}
		}
	}

	// Iterate through all eye paths
	std::cerr << "Building eye paths hit points: " << std::endl;
	bool done;
	lastPrintTime = luxrays::WallClockTime();
	// Note: (todoEyePaths.size() > 0) is extremly slow to execute
	unsigned int todoEyePathCount = width * height * imgSuperSampling * imgSuperSampling;
	std::cerr << "  " << todoEyePathCount / 1000 << "k eye paths left" << std::endl;
	while(todoEyePathCount > 0) {
		if (luxrays::WallClockTime() - lastPrintTime > 2.0) {
			std::cerr << "  " << todoEyePathCount / 1000 << "k eye paths left" << std::endl;
			lastPrintTime = luxrays::WallClockTime();
		}

		std::list<EyePath *>::iterator todoEyePathsIterator = todoEyePaths.begin();
		while (todoEyePathsIterator != todoEyePaths.end()) {
			EyePath *eyePath = *todoEyePathsIterator;

			assert (eyePath->state == TO_TRACE);

			// Check if we reached the max path depth
			if (eyePath->depth > MAX_EYE_PATH_DEPTH) {
				todoEyePathsIterator = todoEyePaths.erase(todoEyePathsIterator);
				--todoEyePathCount;
				eyePath->state = CONSTANT_COLOR;
			} else {
				eyePath->depth++;
				rayBuffer->AddRay(eyePath->ray);
				done = false;
				if (rayBuffer->IsFull())
					break;

				++todoEyePathsIterator;
			}
		}

		if (rayBuffer->GetRayCount() > 0) {
			// Trace the rays
			device->PushRayBuffer(rayBuffer);
			rayBuffer = device->PopRayBuffer();

			// Update the paths
			todoEyePathsIterator = todoEyePaths.begin();
			for (unsigned int i = 0; i < rayBuffer->GetRayCount(); ++i) {
				EyePath *eyePath = *todoEyePathsIterator;

				assert (eyePath->state == TO_TRACE);

				const luxrays::RayHit *rayHit = &rayBuffer->GetHitBuffer()[i];

				if (rayHit->Miss()) {
					todoEyePathsIterator = todoEyePaths.erase(todoEyePathsIterator);
					--todoEyePathCount;
					if (scene->infiniteLight)
						eyePath->constantColor = scene->infiniteLight->Le(eyePath->ray.d) * eyePath->throughput;

					eyePath->state = CONSTANT_COLOR;
				} else {
					// Something was hit
					const luxrays::Point hitPoint = eyePath->ray(rayHit->t);
					const unsigned int currentTriangleIndex = rayHit->index;

					// Get the triangle
					const luxrays::ExtTriangleMesh *mesh = scene->objects[scene->dataSet->GetMeshID(currentTriangleIndex)];
					const luxrays::Triangle &tri = mesh->GetTriangles()[scene->dataSet->GetMeshTriangleID(currentTriangleIndex)];

					// Get the material
					const luxrays::sdl::Material *triMat = scene->triangleMaterials[currentTriangleIndex];

					luxrays::Spectrum surfaceColor;
					const luxrays::Spectrum *colors = mesh->GetColors();
					if (colors)
						surfaceColor = luxrays::InterpolateTriColor(tri, colors, rayHit->b1, rayHit->b2);
					else
						surfaceColor = luxrays::Spectrum(1.f, 1.f, 1.f);

					// Interpolate face normal
					luxrays::Normal N = luxrays::InterpolateTriNormal(tri, mesh->GetNormal(), rayHit->b1, rayHit->b2);

					// Check if I have to apply texture mapping or normal mapping
					luxrays::sdl::TexMapInstance *tm = scene->triangleTexMaps[currentTriangleIndex];
					luxrays::sdl::BumpMapInstance *bm = scene->triangleBumpMaps[currentTriangleIndex];
					luxrays::sdl::NormalMapInstance *nm = scene->triangleNormalMaps[currentTriangleIndex];
					if (tm || bm || nm) {
						// Interpolate UV coordinates if required
						const luxrays::UV triUV = luxrays::InterpolateTriUV(tri, mesh->GetUVs(), rayHit->b1, rayHit->b2);

						// Check if there is an assigned texture map
						if (tm)	{
							const luxrays::sdl::TextureMap *map = tm->GetTexMap();

							// Apply texture mapping
							surfaceColor *= map->GetColor(triUV);

							// Check if the texture map has an alpha channel
							if (map->HasAlpha()) {
								const float alpha = map->GetAlpha(triUV);

								if ((alpha == 0.0f) || ((alpha < 1.f) && (rndGen->floatValue() > alpha))) {
									eyePath->ray = luxrays::Ray(hitPoint, eyePath->ray.d);
									continue;
								}
							}
						}

						// Check if there is an assigned bump/normal map
						if (bm || nm) {
							if (nm) {
								// Apply normal mapping
								const luxrays::Spectrum color = nm->GetTexMap()->GetColor(triUV);

								const float x = 2.0 * (color.r - 0.5);
								const float y = 2.0 * (color.g - 0.5);
								const float z = 2.0 * (color.b - 0.5);

								luxrays::Vector v1, v2;
								luxrays::CoordinateSystem(luxrays::Vector(N), &v1, &v2);
								N = luxrays::Normalize(luxrays::Normal(
										v1.x * x + v2.x * y + N.x * z,
										v1.y * x + v2.y * y + N.y * z,
										v1.z * x + v2.z * y + N.z * z));
							}

							if (bm) {
								// Apply bump mapping
								const luxrays::sdl::TextureMap *map = bm->GetTexMap();
								const luxrays::UV &dudv = map->GetDuDv();

								const float b0 = map->GetColor(triUV).Filter();

								const luxrays::UV uvdu(triUV.u + dudv.u, triUV.v);
								const float bu = map->GetColor(uvdu).Filter();

								const luxrays::UV uvdv(triUV.u, triUV.v + dudv.v);
								const float bv = map->GetColor(uvdv).Filter();

								const float scale = bm->GetScale();
								const luxrays::Vector bump(scale * (bu - b0), scale * (bv - b0), 1.f);

								luxrays::Vector v1, v2;
								luxrays::CoordinateSystem(luxrays::Vector(N), &v1, &v2);
								N = luxrays::Normalize(luxrays::Normal(
										v1.x * bump.x + v2.x * bump.y + N.x * bump.z,
										v1.y * bump.x + v2.y * bump.y + N.y * bump.z,
										v1.z * bump.x + v2.z * bump.y + N.z * bump.z));
							}
						}
					}

					// Flip the normal if required
					luxrays::Normal shadeN;
					if (luxrays::Dot(eyePath->ray.d, N) > 0.f)
						shadeN = -N;
					else
						shadeN = N;

					if (triMat->IsLightSource()) {
						todoEyePathsIterator = todoEyePaths.erase(todoEyePathsIterator);
						--todoEyePathCount;

						const luxrays::sdl::TriangleLight *tLight = (luxrays::sdl::TriangleLight *)triMat;
						eyePath->constantColor = tLight->Le(scene->objects, -eyePath->ray.d) * eyePath->throughput;
						eyePath->state = CONSTANT_COLOR;
					} else if (triMat->IsDiffuse()) {
						todoEyePathsIterator = todoEyePaths.erase(todoEyePathsIterator);
						--todoEyePathCount;

						eyePath->rayHit = *rayHit;
						eyePath->material = (luxrays::sdl::SurfaceMaterial *)triMat;
						eyePath->throughput *= surfaceColor;
						eyePath->position = hitPoint;
						eyePath->normal = shadeN;
						eyePath->state = HIT;
					} else {
						// Build the next vertex path ray
						const luxrays::sdl::SurfaceMaterial *triSurfMat = (luxrays::sdl::SurfaceMaterial *)triMat;

						float fPdf;
						luxrays::Vector wi;
						bool specularBounce;
						const luxrays::Spectrum f = triSurfMat->Sample_f(-eyePath->ray.d, &wi, N, shadeN,
								rndGen->floatValue(), rndGen->floatValue(), rndGen->floatValue(),
								true, &fPdf, specularBounce) * surfaceColor;
						if ((fPdf <= 0.f) || f.Black()) {
							todoEyePathsIterator = todoEyePaths.erase(todoEyePathsIterator);
							--todoEyePathCount;

							eyePath->state = CONSTANT_COLOR;
						} else {
							++todoEyePathsIterator;

							eyePath->throughput *= f / fPdf;
							eyePath->ray = luxrays::Ray(hitPoint, wi);
						}
					}
				}
			}

			rayBuffer->Reset();
		}
	}

	return eyePathsPtr;
}

static unsigned int Hash(const int ix, const int iy, const int iz, const unsigned int hashGridSize) {
	return (unsigned int)((ix * 73856093) ^ (iy * 19349663) ^ (iz * 83492791)) % hashGridSize;
}

static HashGrid *BuildHashGrid(
	std::vector<EyePath *> &hitPoints,
	const unsigned int width, const unsigned int height) {
	// Calculate hit points bounding box
	std::cerr << "Building hit points bounding box: ";
	luxrays::BBox hpBBox;
	for (unsigned int i = 0; i < hitPoints.size(); ++i)
		hpBBox = luxrays::Union(hpBBox, hitPoints[i]->position);
	std::cerr << hpBBox << std::endl;

	// Calculate initial radius
	luxrays::Vector ssize = hpBBox.pMax - hpBBox.pMin;
	const float photonRadius = ((ssize.x + ssize.y + ssize.z) / 3.f) / ((width * imgSuperSampling + height * imgSuperSampling) / 2.f) * 2.f;

	// Expand the bounding box by used radius
	hpBBox.Expand(photonRadius);

	// Initialize hit points field
	const float photonRadius2 = photonRadius * photonRadius;
	for (unsigned int i = 0; i < hitPoints.size(); ++i) {
		EyePath *eyePath = hitPoints[i];

		eyePath->photonRadius2 = photonRadius2;
		eyePath->accumPhotonCount = 0;
		eyePath->accumReflectedFlux = luxrays::Spectrum();
	}

	const float hashs = 1.f / (photonRadius * 2.f);
	// TODO: add a tunable parameter for hashgrid size
	const unsigned int hashGridSize = hitPoints.size();
	std::vector<std::list<EyePath *> *> *hashGridPtr = new std::vector<std::list<EyePath *> *>(hashGridSize);
	std::vector<std::list<EyePath *> *> &hashGrid = *hashGridPtr;

	std::cerr << "Building hit points hash grid:" << std::endl;
	std::cerr << "  0k/" << hitPoints.size() / 1000 << "k" <<std::endl;
	const luxrays::Vector vphotonRadius(photonRadius, photonRadius, photonRadius);
	unsigned int maxPathCount = 0;
	double lastPrintTime = luxrays::WallClockTime();
	for (unsigned int i = 0; i < hitPoints.size(); ++i) {
		if (luxrays::WallClockTime() - lastPrintTime > 2.0) {
			std::cerr << "  " << i / 1000 << "k/" << hitPoints.size() / 1000 << "k" <<std::endl;
			lastPrintTime = luxrays::WallClockTime();
		}

		EyePath *eyePath = hitPoints[i];

		const luxrays::Vector bMin = ((eyePath->position - vphotonRadius) - hpBBox.pMin) * hashs;
		const luxrays::Vector bMax = ((eyePath->position + vphotonRadius) - hpBBox.pMin) * hashs;

		for (int iz = abs(int(bMin.z)); iz <= abs(int(bMax.z)); iz++) {
			for (int iy = abs(int(bMin.y)); iy <= abs(int(bMax.y)); iy++) {
				for (int ix = abs(int(bMin.x)); ix <= abs(int(bMax.x)); ix++) {
					int hv = Hash(ix, iy, iz, hashGridSize);

					if (hashGrid[hv] == NULL)
						hashGrid[hv] = new std::list<EyePath *>();

					hashGrid[hv]->push_front(eyePath);

					if (hashGrid[hv]->size() > maxPathCount)
						maxPathCount = hashGrid[hv]->size();
				}
			}
		}
	}
	std::cerr << "Max path count in a single hash grid entry: " << maxPathCount << std::endl;

	return new HashGrid(hashs, hpBBox, hashGridPtr);
}

static void InitPhotonPath(luxrays::sdl::Scene *scene, luxrays::RandomGenerator *rndGen,
	PhotonPath *photonPath, luxrays::Ray *ray) {
{'fraction_non_alphanumeric': 0.16311103645220898, 'fraction_numerical': 0.009267036228232264, 'mean_word_length': 2.8863018169948864, 'pattern_counts': {'":': 0, '<': 259, '<?xml version=': 0, '>': 346, 'https://': 0, 'lorem ipsum': 0, 'www.': 6, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 34, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2746216', 'n_tokens_mistral': 14329, 'n_tokens_neox': 11466, 'n_words': 2811}