Home
Blogs
Forums
News
Portfolios
Projects
Tutorials
26 users logged in
New? Learn about game development.
Before posting, review our community guidelines.
Follow Us
Chat in the GameDev.net Discord!
Mastodon
Back to Graphics and GPU Programming

Photon Mapping : Photon Emission

Started by
15 comments, last by cwhite 18 years, 10 months ago
Quickselect is indeed what I was reffering to. I don't understand why there would be a problem with an even number of elements, however. It just seems to me like if you always pick the n/2th element, the tree will not be super perfectly balanced (there will be one photon more on one side). This doesn't seem like it would be that much of a problem, however.

As for building the whole thing. I will just add photons to my photon map class as I trace them, and they will be stored in an std::vector<SPhoton>; object. Once the tracing is done, a CPhotonMap::BuildMap() function will be called. I will find the median in the main vector of photons along the axis that spans the greatest distance. This will be the root of the kd-tree. I will then have to split all other photons in the array into two subarrays, one on each side of the splitting plane, and recursively find their own root. I am still wondering how to efficiently structure the algorithm.

I am thinking of something of the form:

Balance(std::vector<SPhoton>& PhotonArray, std::vector<SPhoton>& HeapArray, unsigned int HeapIndex){    // Find the axis along which the photons in photonarray span the greatest distance    // And equivalently we find the splitting plane    Axis = FindAxis(PhotonArray); // linear-scanning O(n)    // Find the median photon of PhotonArray along the desired axis    MedianPhoton = FindMedian(PhotonArray, Axis); // recursive, O(n)    // Place the median photon in the heap array    HeapArray[HeapIndex] = MedianPhoton;    // Split the photon array into two subarrays, for each side of the median    // std::vector<SPhoton> LeftArray  = Photons < Median    // std::vector<SPhoton> RightArray = Photons >= Median    // Recursively process each half    Balance(LeftArray, HeapArray, 2 * HeapIndex);    Balance(RightArray, HeapArray, 2 * HeapIndex + 1);}


Of course there are going to be a good bit of memory allocations, but it seems like it won't use more than 3 times the memory of the original photon array in total. I can also make sure to reserve enough space in the arrays before recursively passing them along. As for the FindMedian(), it can be done in-place. My intuition tells me this algorithm should run in O(n log n) time.

I specified the photon array as a non-const reference because the function to find the median will need to partition it recursively, and it would seem wasteful to make a copy every time.

I guess that part of the algorithm should be allright. I'm still not sure how to find the nearest photons in the kd-tree efficiently, however.

Looking for a serious game project?
www.xgameproject.com
Advertisement
Quote:Original post by Max_Payne
Quickselect is indeed what I was reffering to. I don't understand why there would be a problem with an even number of elements, however. It just seems to me like if you always pick the n/2th element, the tree will not be super perfectly balanced (there will be one photon more on one side). This doesn't seem like it would be that much of a problem, however.


The problem is that if your tree is not perfectly left balanced, then you can no longer store your kd-tree as an array. This is bad for cache performance and increases your memory overhead because each photon now needs to store pointers to its left and right child. If you try and store the kd-tree in an array and it is not perfectly left balanced, you will have holes in the tree, and your algorithm will get garbage results if it ever indexes a hole. You can fix this by adding an isValid bool to your photon, but that's a memory wasting cheap hack.

Quote:
As for building the whole thing. I will just add photons to my photon map class as I trace them, and they will be stored in an std::vector<SPhoton>; object. Once the tracing is done, a CPhotonMap::BuildMap() function will be called. I will find the median in the main vector of photons along the axis that spans the greatest distance. This will be the root of the kd-tree. I will then have to split all other photons in the array into two subarrays, one on each side of the splitting plane, and recursively find their own root. I am still wondering how to efficiently structure the algorithm.

I am thinking of something of the form:

*** Source Snippet Removed ***

Of course there are going to be a good bit of memory allocations, but it seems like it won't use more than 3 times the memory of the original photon array in total. I can also make sure to reserve enough space in the arrays before recursively passing them along. As for the FindMedian(), it can be done in-place. My intuition tells me this algorithm should run in O(n log n) time.

I specified the photon array as a non-const reference because the function to find the median will need to partition it recursively, and it would seem wasteful to make a copy every time.

I guess that part of the algorithm should be allright. I'm still not sure how to find the nearest photons in the kd-tree efficiently, however.


I don't see why it would require 3 times the memory of the original photon array. It should only require 2 times. During your tracing phase, you store all your photons in an unbalanced array (or vector, if that's how you roll). When tracing is done, you create a balanced array, and use your balance() function to populate that array. If you're careful with your array indexing, you really don't need to create an additional left and right array. As you know, that will save you a lot of allocation time as well as cut down on memory use. For bonus points, find a way to make balance() iterative instead of recursive, and your savings will be even bigger.
Quote:The problem is that if your tree is not perfectly left balanced, then you can no longer store your kd-tree as an array.


That would be rather problematic. Do you have any idea how to prevent that from happening?

Looking for a serious game project?
www.xgameproject.com
Quote:Original post by Max_Payne
Quote:The problem is that if your tree is not perfectly left balanced, then you can no longer store your kd-tree as an array.


That would be rather problematic. Do you have any idea how to prevent that from happening?


It all comes down to making sure you choose the correct median when there are an even number of photons in the list.
Quote:Original post by cwhite
Quote:Original post by Max_Payne
Quote:The problem is that if your tree is not perfectly left balanced, then you can no longer store your kd-tree as an array.


That would be rather problematic. Do you have any idea how to prevent that from happening?


It all comes down to making sure you choose the correct median when there are an even number of photons in the list.


Hmm. Well, I will try to find out how...

EDIT: I found a simple document which describes how to do it at http://www2.imm.dtu.dk/pubdb/views/publication_details.php?id=2535

I should be completing my photon map building code tonight.

I have already written the C++ code for the diffuse emission direction, if anyone is interested in this:

CVector3 DiffuseVector(const CVector3& Normal){	// Assert that the vector is not zero	assert(!Normal.IsZero());	// Declare two vectors to create an orthonormal basis	CVector3 U, V;	// Find two vectors orthogonal to the normal	if (Normal.X != 0.0f)	{		U.Set(-Normal.Y/Normal.X, 1.0f, 0.0f);		V.Set(-Normal.Z/Normal.X, 0.0f, 1.0f);	}	else if (Normal.Y != 0.0f)	{		U.Set(1.0f, -Normal.X/Normal.Y, 0.0f);		V.Set(0.0f, -Normal.Z/Normal.Y, 1.0f);	}	else	{		U.Set(1.0f, 0.0f, -Normal.X/Normal.Z);		V.Set(0.0f, 1.0f, -Normal.Y/Normal.Z);	}	// Make V orthogonal to U	V *= (1.0f - DotProduct(U, V)/V.LengthSqr());		// Normalize U and V to obtain an orthonormal basis	U.Normalize();	V.Normalize();	// Compute the polar coordinates of a random point on the unit circle	float Angle  = RandomFloat(0.0f, TWO_PI);	float Radius = RandomFloat(0.0f, 1.0f);	// Obtain 2D cartesian coordinates for the point	float X = Radius * cosf(Angle);	float Y = Radius * sinf(Angle);	// Obtain the Z coordinate projecting this point on the unit sphere	float Z = sqrtf(1.0f - X*X - Y*Y);	// Return the resulting direction vector	return (X * U) + (Y * V) + (Z * Normal);}


[Edited by - Max_Payne on June 7, 2005 5:56:14 PM]

Looking for a serious game project?
www.xgameproject.com
I programmed the photon map building algorithm. I did it so that it doesnt require left and right arrays to be carried on, as cwhite suggested. I also used an array of pointers to do all the shuffling around quicker. I traced 600000 random photons into it, and it took about 6 seconds to build the map in debug mode. I then ran a function I made to verify the correctness, and it returns true, indicating that the kd-tree properties are valid... I am hoping it all works right, because it might be hard to debug if it does not. I guess I will only know when I can take advantage of it.

So hmm... Could anyone explain me how exactly the algorithm works to find the nearest photons and build a heap?

Looking for a serious game project?
www.xgameproject.com
This is pseudocode, not meant to compile.

[source language=c++]//photon is the current photon in the kd-tree, p is the point we are consideringfindPhotons(int ph, point p){     if (ph > numPhotons)     {          return; // termination condition     }     Photon phot = balanced[ph];     int pl = phot.plane;     float d = phot[pl] - p[pl];     if (d < 0) // right of splitting plane     {          findPhotons(ph * 2 + 1, p);          if (fabs(d) < maxDistSquared)          {               findPhotons(ph * 2, p);          }     }     else // left of splitting plane     {          findPhotons(ph * 2, p);          if (fabs(d) < maxDistSquared)          {               findPhotons(ph * 2 + 1, p);          }     }     float dist = squareDistance(phot, p);     if (dist < maxDistSquared)     {          //if heap has more than nLookup photons, remove top photon and update          //maxDistSquared          //insert photon into heap.     }}


That's the general idea.

This topic is closed to new replies.

Advertisement

Popular Topics

aigan
The promise of freedom in story games Game Design and Theory
Nosey
Ideas for a new genre (anonimous) Game Design and Theory
KielanT
DirectX 12 Renderer Graphics and GPU Programming
MrK45
Inheriting from application registered class AngelCode
Advertisement

Recommended Tutorials

Myopic Rhino
WWH - Calculating a Rotation Matrix Based on Location/Target Graphics and GPU Programming
gdarchive
Tracking Player Metrics and Views in Flash Games with Google Analytics Business and Law
Dyonisian
Walk The Streets Of 1941 Lochee, Dundee: A Framework For Large-Scale Outdoors Augmented Reality Game Design and Theory
Secretmapper
Why your Games are Unfinished, and What To Do About It Business and Law
Myopic Rhino
Code on the Cob Part 7 General and Gameplay Programming

Reticulating splines

About GameDev.net
Community Guidelines
Terms of Service
Privacy Policy
Contact Us
Copyright (c) 1999-2024 GameDev.net, LLC
Back to Top