Independent Study: Week 7

Quick update to start the week off, I think it's as good a time as any to show that I have in fact brought this back to interactive frame rates with the help of a spatial hashing system:

It's a shame that, aesthetically, the video isn't very pleasing. It comes down to limitations of raw photon mapping really, as well as the hardware I have to work with. This scene has just short of 400,000 photons bouncing around it, but even that is not enough to uniformly light the objects within it. I would need to incorporate a final gathering phase of some sort if I wanted to correct the issue, and that would have a performance impact as well. I've got one or two ideas I'd like to explore but short of optimizing heavily and then using the new cycles to perform final gathering I don't see the quality improving much sadly.

More to come throughout the week.

Independent Study: Week 6

This week's going to be all about optimization.

I've been trying to find the best balance between effort put in and performance increase as far as acceleration structures go. I thought about a kd-tree for a while, but the problem with those is the difficulty I've had finding a simple-to-implement sorting algorithm. I'm using a parallel selection sort based on Eric Bainville's work since it was extremely basic. It's not fast, but I don't really care about speed of sort for photon mapping itself because it's all done before-hand. The problem is that kd-trees require continuous refinement and re-sorting as you construct them. Every time you go down a level you swap the axis you're splitting on and that requires a partial re-sort. For the time being, I've passed on kd-trees because of these issues. Instead, I've implemented a spatial  grid that just works by partitioning 3D-space uniformly. It appears to be working so far, I've got a pretty decent speed-up, but it's also slightly broken at the moment:

It's not actually broken though, it's behaving exactly as I wanted it to...it just isn't complete.Right now I'm only looking for photons within the grid cell where the ray tracing step intersected the object. This is partially correct, but I really need to be gathering photons from neighboring cells in all 3 dimensions. The distance away from which I should be checking other cells is equivalent to the radius of the photons that I'm emitting. That's next!

Update: 4/15/2012

Tried implementing neighbor search with my uniform grid...now I see why people don't roll their own algorithms! Performance was actually worse than without any "acceleration" structure at all, and I didn't have control over the span that I was searching over easily. One of the biggest problems I'm looking at right now is varying the size of the cells based on the radius of the photons within the scene. This isn't difficult itself, but then adjusting at run-time the resolution of the grid itself IS difficult to wrap my head around right now. I'll need to think on this for a while. If I can enforce that grid cells are the same dimensions as the radius of the photons, the nearest neighbor search becomes a problem with at most 26 grid cells involved. Ultimately, the kd-tree is looking like a better solution still, even if I have no idea how to do it yet.

Also, I've come to realize that my approach thus far is strikingly similar to that of Martin Fleisz.

Update 4/16/2012

Well I followed my hunch and looked into how Martin Fleisz approached acceleration structures. I'm not quite done with my own spin on his algorithm, but I'm getting close and thought I should update to say that hopefully this should be the one I settle on. Initial performance seems promising....if it's true. Hard to tell if I'm getting all the photons I should be with my queries. In the meantime, here's an awesome (broken) screenshot of the current state of the app:

Update: 4/16/2012

Well I fixed that bug, and after a night of hacking away at one problem after another I've come to this point:

I really don't know how I feel about this. It's hard to see but the final gather is still broken and cuts apart some photons, the map doesn't quite look accurate anymore as far as the inter-reflections on the larger sphere from the wall, and the grid structure itself is producing SERIOUS aliasing obviously. 

I'm really worried about the aliasing with this approach. I think the only way I can get rid of it is to cast multiple rays per pixel and then average the results. This would effectively cut my performance to a quarter of what it is now if I want it done right, effectively negating the entire advantage of this approach...

I guess I'll see what I think of it tomorrow...

Update: 4/17/2012

Here's an example of what I think is causing the aliasing. It's a closeup of the photons being cut off at grid boundaries like they shouldn't be:

Update: 4/18/2012

Fixed the error on the left and right walls, introduced a new one I can't figure out on literally every other flat surface and portions of the spheres. You can see it in this shot that also shows some really AWESOME errors I caused on purpose playing with the floating-point error:

Update: 4/19/2012

Still broken =/

Update: 4/21/2012

I FINALLY fixed that bug. It turned out to be a typo in my manual magnitude calculation for a certain vector. I hate myself for it...

I'm experimenting at the moment with larger batches of photons, and more uniform distributions. I'd expect that to be the highlight of next week's content and progress. Looking forward even more, I hope to play with texture memory a bit for Week 8!

Update: 4/21/2012

It's amazing what a better random function can do :)

Independent Study: Week 4

Slow progress this week because of early midterms and projects in other courses ramping up. I'm still well on track with the tentative schedule I put into the original proposal however, which is a good thing. I plan to make a lot of progress on the material / object systems in the next few days in preparation for the photon mapping which I hope to start implementing this weekend. For now, here's a video that shows that I can successfully integrate my quaternion camera that I developed for a previous project into this project with moderate ease:

I think what I would like to do for photon mapping is get a very basic implementation done initially that uses something like a 1-dimensional (or perhaps 2-dimensional) sorted array for storing the photon map. That way I can get an idea of what kind of performance I have base-line, and then work on optimization. Here's the original projected schedule that I included in my proposal:

Week 1: Final decisions on architectures and hardware to be used are made.
Weeks 2-3: Basic OpenCL / CUDA Ray-Caster implemented (trivial, no bouncing)
Weeks 4-6: OpenCL / CUDA photon-map computation is implemented
Weeks 7-8: Benchmarking and Profiling, bottlenecks are identified and addressed
Weeks 9-10: Finishing touches. Final project completed.
Week 11: Formal Writeup / Final Paper completed.



It's currently week 4, so as I said I'm still well on track. I've also left myself an additional 2 weeks to get this part done, but more importantly is the 2 weeks I've allocated for optimization following that. At the latest, that is when I hope to implement an acceleration structure such as a kd-tree so that I can get some high frame rates. One of the cool things about this approach is that while performance will be decreased by the photon mapping itself, it's overall limited by the ray-tracer's resolution during final gathering. That means that  my "real-time" photon mapper may not be real-time at 1280x720, but dropping it down to 640x480 or lower could still yield decent frame rates. That's sort of cheating however, and I'd rather just get an awesome implementation that runs well :).

Also, caustics are (temporarily) off the table on this project until I get a better idea of the performance boundaries I'm dealing with. I'd love to implement the technique if I have time and I can keep the speed up.




Update: 4/7/2012


...for loops...


Tried adding multiple lights to my scene, a single light that I illuminate with phong shading gets me around 200 FPS at 1280x720 resolution. I up that to two hard-coded lights: 160 FPS...not bad at all. I keep the same two lights, but write the code with a for-loop so that I can handle an arbitrary number of lights: 100 FPS! Just the loop iteration is significantly reducing my frame-rates. I'm not really shocked, but it still sucks. I tried manually unwinding the loop in code and the speed actually went down, so I'm guessing OpenCL already takes care of that to some extent during compilation. Oh well, seeing as everything about this project is supposed to be about indirect lighting, I shouldn't technically need more than one light in the scene anyway. I've resorted to a preprocessor flag, USE_MULTIPLE_LIGHTS that when defined makes the code use a for loop, otherwise it just uses the first light in the scene. I might come back to this later on and see if I can find a faster way to get these going but I just don't see how at the moment...

Independent Study: Week 3

Tried Cuda, hated it. Way too much work to do the same thing as OpenCL.

I'm sticking to the mentality that I don't know OpenCL well enough to be concerned about the framerates I'm getting. But I've learned a LOT in the last few days about how it works.

I've now got dynamic scene support, so I can add planes and spheres at will (excuse the overlap, I haven't implemented depth yet):

Update: (3/26/2012 @ 8:05 PM)

I got accurate depth and intersections done, the following is rendering surface normals at the points of intersection:

Update: (3/26/2012 @ 11:37 PM)

Phong shading integrated successfully:

Independent Study: Week 2

Red Dot:

Still a little quirky, lots of hard-coded stuff (namely the geometry in the world), but it's working!

Annnnnnd I'm probably going to have to start over with CUDA because of that performance thing I was complaining about. But it's not a sure thing yet.

Independent Study: Week 1

Quick update. I've got OpenCL interfacing with OpenGL and drawing a real nice gradient:

I'd be happier if the framerate was higher however. 800 FPS might sound great, but I know that's going to plummet when I actually start doing stuff in the OpenCL kernel code. Right now it's doing some floating point arithmetic and that's it. Also a similar procedural gradient as a shader in OpenGL would probably be hitting 3000 FPS on my test system so I'm not sure what's up there either. Definitely going to have to work on it.

Independent Study

So I'm running out of courses that I'm required to take at RIT for my software engineering degree, and faster than I'm running out of required course blocks that I have to fill in order to actually graduate. So I'm doing an independent study. I've decided that writing a ton isn't for me, so I'm keeping these brief from now on until some miraculous day comes around where people want to actually read what I'm typing. This was after all just for my own records...

So yeah, independent study. I'm doing Photon Mapping on the GPU with a focus on real-time results. My laptop's a beast for it's age (Quadcore i7, GeForce 285M GTX video card) so I should be able to get some power out of it. I'm going to use OpenCL I think, but I might change my mind in the next few days and move to CUDA instead. Other than that there's not much to say right now. I'll throw up another post with content next hopefully.