Features

• Ray marching of distance fields done on the Gpu inspired by IQ demo “Slisesix” and  Shadertoy. The video shows two scenes rendered with a pixel shader: the simple scene showing basic distance fields and the more elaborated one, showing procedural distance fields and shading.

Report

This test is heavily inspired by the IQ’s work done on ray marching and his several raymarched demos. The test builds the pixel shader, which is the ray marcher, on the fly everytime the shader changes. The algorithm is as straightforward as cast a ray, sample the distance in a position and advance to the next with the distance obtained until you reach a minimun distance or a maximun number of iterations. The distance fields are functions like spheres, cylinders and torus. The fun comes with the csg operators you can use like union or difference. I have had a great amount of fun developing the procedural distance fields but requires a lot of tweaking and time.

Controls

• Left click plus mouse movement to rotate the camera around the center of the scene.

Technology

• C++
• Boost
• Opengl 2.0
• Glew
• CMake
• Microsoft Visual Studio 2010
• Subversion
• Redmine
• Windows 7 x64

Develop/Build/Test Machine Specs

• Intel(R) Core(TM) i7 CPU 920 @ 2.67GHz
• 3072 Mb RAM
• Nvidia GeForce GTX 260
• Nvidia Driver Version: 260.99
• Microsoft Windows 7 Professional x64

Resources

• Raymarching distance fields by IQ
• Sphere tracing:a geometric methodfor the antialiased raytracing of implicitsurfaces by John C. Hart
• Terrain raymarching by IQ
• Rendering worlds with two triangles with raytracing on the GPU in 4096 bytes by IQ
• Behind elevated by IQ
• Making graphics in 4 kilobytes by IQ
• Better fog by IQ
• Shadertoy by IQ
• Fog in GLSL by oZone3D.Net
• Gpu Gems 2. Chapter 19. Generic refraction simulation by Tiago Sousa

Hopefully I will have some time to attend a talk or maybe a course. Anyway, if you want to catch me up during the conference just drop me an email.

Happy Siggraph everyone!

Features

• Flock simulation using tasks in order to keep busy all the cpu cores. It uses the Vista Pool Thread API to make a really simple wrap for send multiple tasks to the pool. The video shows how most of cpu cores (hardware threads) are not working under a heavy load of work with only one task in the pool. If the work is spread across multiple tasks, the video shows how all the cpu cores are busy.

Downloads

• Source code

Report

After seeing the gdc10 intel talk about tasks using the vista thread pool api,  I wanted to give it a try. So, the objective of this test is just try the thread pool api that vista provides. I dont try to get a massive amount of geometry on screen, just have something cpu intensive and appealing like a flock simulation algorithm.

Controls

• Left click plus mouse movement to rotate the camera around the flock.
• Right click plus mouse move up/down to zoom in/out.

Technology

• C++
• Boost
• Opengl 2.0
• Qt
• Freeglut
• Glew
• Microsoft Visual Studio 2008 Professional Edition
• Subversion
• Redmine
• Windows 7 x64

Develop/Build/Test Machine Specs

• Intel(R) Core(TM) i7 CPU 920 @ 2.67GHz
• 3072 Mb RAM
• Nvidia GeForce GTX 260
• Nvidia Driver Version: 196.21 WHQL
• Microsoft Windows 7 Professional x64

Resources

• Vista Thread Pool API from msdn
• “Steering Behaviors For Autonomous Characters” by Craig Reynolds
• “Task-based Multithreading — How to Program for 100 Cores” by Ron Fosner
• “Trefoil knot” from Wikipedia

Features

• CUDA based application showing gpu volume raycasting using single pass Stegmaier et al. technique.

Downloads

• Video
• Source code

Report

The cuda raycasting implementation is the same approach as the Stegmaier one but with some minor changes and simplifications:

• CUDA kernel
• The volume is a cube: width, height and depth are all the same.
• Proxy geometry (the six quads or the cube) is normalized and translated so the center its the same as the center of the scene.

The intersection code is really unoptimized. It’s just a straightforward implementation of the intersection ray-aabox function shown in “Real time collision detection” by Christer Ericson. I would suggest you to see the implementation of this function within the nvidia sdk volume render sample .

Controls

• Left click plus mouse movement to rotate the camera around the volume.
• Right click to show the context menu.
• Middle click plus vertical movement to increase/decrease the density window width.
• Middle click plus horizontal movement to move right/left the density window.

Technology

• C++
• Opengl 2.1
• CUDA
• Glut for Win32
• Glew
• Microsoft Visual Studio 2008 Professional Edition
• Subversion
• Redmine

Develop/Build/Test Machine Specs

• Intel(R) Core(TM) i7 CPU 920 @ 2.67GHz
• 3072 Mb RAM
• Nvidia GeForce GTX 260
• Nvidia Driver Version: 196.21 WHQL
• Microsoft Windows 7 Professional x64

Resources

• [SSKE05] S. Stegmaier, M. Strengert, T. Klein, and T. Ertl.
  A Simple and Flexible Volume Rendering Framework for Graphics-Hardware-based Raycasting,
  Proceedings of Volume Graphics 2005, Stony Brook, New York, USA, pp.187-195, 2005
• A Simple and Flexible Volume Rendering Framework for Graphics-Hardware-based Raycasting website. Includes paper, dataset and source code.
• The Volume Library
• NVIDIA GPU Computing Developer Home Page
• GLEW: The OpenGL Extension Wrangler Library

Features

• Opengl based application showing gpu volume raycasting using single pass Stegmaier et al. technique.

Downloads

• Video
• Source code

Report

The gpu raycasting implementation is the same approach as the Stegmaier one but with some minor changes and simplifications:

• GLSL shaders
• The volume is a cube: width, height and depth are all the same.
• Proxy geometry (the six quads or the cube) is normalized and translated so the center its the same as the center of the scene.

Controls

• Left click plus mouse movement to rotate the camera around the volume.
• Right click to show the context menu.
• Middle click plus vertical movement to increase/decrease the density window width.
• Middle click plus horizontal movement to move right/left the density window.

Technology

• C++
• Opengl 2.1
• GLSL
• Glut for Win32
• Glew
• Microsoft Visual Studio 2008 Professional Edition
• Subversion
• Redmine

Develop/Build/Test Machine Specs

• Intel(R) Core(TM) i7 CPU 920 @ 2.67GHz
• 3072 Mb RAM
• Nvidia GeForce GTX 260
• Nvidia Driver Version: 196.21 WHQL
• Microsoft Windows 7 Professional x64

Resources

• [SSKE05] S. Stegmaier, M. Strengert, T. Klein, and T. Ertl.
  A Simple and Flexible Volume Rendering Framework for Graphics-Hardware-based Raycasting,
  Proceedings of Volume Graphics 2005, Stony Brook, New York, USA, pp.187-195, 2005
• A Simple and Flexible Volume Rendering Framework for Graphics-Hardware-based Raycasting website. Includes paper, dataset and source code.
• The Volume Library
• GLEW: The OpenGL Extension Wrangler Library

As with the previous problem I used Threading Building Blocks as the tool to parallelize the algorithm. I chose to use the parallel_reduce algorithm, after trying to make it with parallel_for. The problem is gathering the results across all the tasks. Parallel_reduce is an easy way of collect results after the tasks completion. The algorithm includes a synchronization method: join. After a task ends the join method is called to merge the results. The parallel approach gave me a time of ~60secs.

I think the speed I got wasn’t that fast to win this round but that’s not my objective. I’m having a lot of fun, I’m learning from other people and I’m learning how to use TBB. Those are my objectives.

The approach I took to solve the problem is really naive due time constraints. The problems I found were:

• Convert a bounded knapsack problem to a 0-1 knapsack problem.
• Convert real number weights and benefits to integers.
• Parallelization of the serial algorithm.
• Memory efficiency.

The serial algorithm is really naive:

1. Convert the weights and values to integer numbers.
2. Convert the problem to a 0-1 knapsack problem repeating bounded limit times the items.
3. Solve 0-1 knapsack problems with a dynamic programming algorithm.
4. Trace back the items.

As you see this approach is the classical example of dynamic programming you can find in textbooks. Although it has big problems when you try to solve big data.  Repeating the items bounded limit times its a really easy way to convert the problem but needs tons of memory. Multiplying by 100 makes the deal, but it can lead to rounding precision problems. The parallel algorithm is the same but using a “parallel_for” to replace the second for loop of the algorithm.

Well, the solution proposed is very naive, so I don’t expect good results in the contest. Anyway, I enjoyed the problem and I’m already thinking about the next one: “Segment intersection”.

I really don’t have much time but I could enjoy participating in this contest and well, it’s a nice excuse to get my hands on Threading Building Blocks. I’m going to give a try for the next couple of weeks to the first problem (bounded knapsack problem) and I will see if I have fun. Don’t expect any graphics related tests/tech demos in the meantime although I want to show something of the entry development. For the moment, I don’t know exactly what I’m going to show but I will.