Jump to content

  • Log In with Google      Sign In   
  • Create Account

jcabeleira

Member Since 24 Sep 2003
Offline Last Active Dec 18 2014 06:35 AM

Topics I've Started

Dijsktra and STL Priority Queues

18 October 2013 - 08:56 AM

Hello guys,

 

I'm implementing Dijkstra and I have a question regarding the priority queues. Most people use one of the STL queues to store their list of nodes to be visited. However it seems that these queues (std::set, std::make_queue, etc) don't allow to store two or more nodes that have the same exact distance to the start node.

Take this example:

 

         Start Node-----3-----Node1

                |

                3

                |  

           Node2

 

As you can seen both Node1 and Node2 have the same distance of 3 to the start node so when exploring the start node you would insert both Node1 and Node2 into the queue. However the insertion of the second node will fail because the priority queue already has a node with shortest distance = 3. Can someone confirm this observation is true?

 

I've seen my implementation fail to find the shortest path because of this fact. It is a rare phenomenon because it is not probable that two nodes have the exact same distance but it does happen and when it does the algorithm fails completely.

 

Thanks in advance


Results on Voxel Cone Tracing - Part 2

14 May 2013 - 03:39 PM

Hello, guys. Please forgive me for the shameless self promotion, I'd just like to share and discuss the results I got with my Voxel Cone Tracing implementation. So, in my last post I presented an early version of my own implementation of global illumination using voxel cone tracing, since then I've done a lot of improvements and ended up creating a demo that you can find here to show it. Very soon I'll be writing a set of articles explaining the implementation in more detail but for now I'll outline the most important aspects:

 

My implementation uses two 128x128x128 3D textures to store the voxelized scene, a small texture and a larger one, where the small one covers a 30x30x30m volume of the scene while the larger one covers a 120x120x120m volume. Together they provide a voxelized representation of the scene with enough quality and range for the GI processing. The volumes are fixed at the world origin, they do not follow the camera because that makes the lighting unstable, I know this  is impractical for a video game but it's enough to cover the smalll scene of my demo.

No Sparse Voxel Octree is used, this is because I concluded from my early experiments that traversing the tree takes a huge toll on performance probably because the divergent code paths and incoherent memory accesses are not very GPU friendly. So, In general volume textures seem to provide much better performance that octrees at the expense of huge memory waste (because of empty voxels). I haven't profiled one method against the other, my choice was based simply on experiments so please feel free to argue against these arguments and provide your own insight on the subject.

 

The scene is voxelized in real-time using a similar version of the technique described by Cyrril Crassin in the free OpenGL Insights chapter that is available here. The voxelization is quite fast and can be performed in real-time without a great impact on performance which allows to make the lighting dynamic, if any object or light source moves you'll see the lighting change accordingly.

Once the voxel volume is ready it is possible to simulate a second bounce of GI by revoxelizing the scene to a second volume while using the first volume to perform cone tracing for each fragment that is inserted into the volume. Note however that this is very expensive and doesn't compensate the reduced improvement in visual quality so it's disabled by default in the demo.

 

The diffuse lighting is calculated in groups of 3x3 pixels to improve the performance and a edge refinement is done later to fix the difficult cases. For each group of 3x3 pixels 16 cones are traced in all directions with 32 samples per cone. The tracing of each cone is done pretty much like Crassin describes in his paper, for each sample inside the cone we read the corresponding mipmap level of the volume texture and accumulate both the color and the opacity of the voxel information that was read.

 

The specular lighting is calculated by tracing a cone along the reflection vector. Voxel cone tracing gives the flexibility to generate sharp and glossy reflections which is really neat. In general both look good but the lack of resolution of the voxel volume prevents the accurate rendering of glass and mirror materials. Sharp reflections are problematic also because they require an insane amount of samples per cone (200 in the demo) to avoid missing scene features like thin walls. The tracing is optimized to skip large portions of empty space by sampling a lower resolution mipmap level of the voxel volume and checking its opacity (similar to sphere tracing), if the opacity is zero then there are no objects nearby and we can skip that space altogether. This is essentially an GPU friendly approximation of what is done with a Sparse Voxel Octree.

 

So this concludes the overview of the implementation. Please feel free to leave your comments.

 

Don't forget to try the demo (I recommend running it on a Nvidia GTX 680 or similar, it's untested for AMD hardware so I have now idea how it runs on it).

 

Here is some eye candy :

 

 

SerenityRevisited1.jpgSerenityRevisited3.jpgSerenityRevisited2.jpg


Results on Voxel Cone Tracing

19 September 2012 - 10:25 AM

Ei, guys!
I'd like to show you guys the results of my attempt on implementing the real-time global illumination used by the Unreal Engine 4 and discuss the results I got.

Here is an overview of the implementation:
  • I do not own a DX11 grade graphics card so my implementation uses simple 3D textures instead of Sparse Voxel Octrees and the voxelization is performed on the CPU with raytracing . For each voxel, the raytracer sends a ray in each axis direction (-X, +X, -Y, +Y, -Z, +Z) with distance clamping to avoid intersecting geometry outside the voxel and stores the color and normal of the intersection point.
  • Six 128x128x128 3D textures are used to represent the anisotropic radiance of the voxel volume, i.e. the radiance that goes in each axis direction (-X, +X, -Y, +Y, -Z, +Z).The points that were calculated before are rendered into these volume textures, their illumination is calculated and they are injected into the 3D textures by weighting their normals against the direction that each of the 3D texture represents thus giving us how much of the lighting goes into each direction.
  • After the 3D textures are created we need to generate their mipmaps so we can perform cone tracing. This step requires a custom mipmapping step that adds the radiance of neighbouring texels instead of averaging becase without it empty voxels wich are black would darken the radiance in the deeper mipmap levels.
  • Once the volumes are ready the GI is rendered with a full screen pass where 16 uniformly distributed cones are cast. For each cone, 20 samples are taken along it with a fixed distance between samples. For each sample, the sample radius is calculated from the cone angle and the distance to the source point and used to calculate the correspondent mipmap level. The anisotropic radiance is sampled from the 6 volumes and weighted by the cone direction.

Regarding performance, these are my thoughts:
  • Using a fullscreen pass for the GI, with 16 cones per pixel, 20 samples per cone gives an average of 2 FPS on my GTX260 Mobile.
  • Using a configuration similar to the UE4, rendering at 1/3 of the screen resolution (which should be fairly equivalent to their 3x3 interlacing method) with 9 cones per pixel, 20 samples per cone (it is unknown how much samples UE4 uses for each cone) I obtain 10 FPS.
  • It would be interesting to see how this runs on a more powerfull GPU like the GTX680 that it was used on the UE4 presentation
  • I'm also curious to see if a Sparse Voxel Octree would increase or reduce the performance (please share your thoughts on this)

Regarding quality:
  • The overall quality fairly independent on the number of cones. Usually, 9 cones provide acceptable quality while 16 cones provide good quality and 32 is similar to 16 cones while providing subtle fine details.
  • Specular reflections are not that good for two reasons: the low resolution of the volume and the fact that the reflection has no GI, only direct illumination, which makes them look displaced from the scene even for glossy reflections.
  • In certain situation some bleeding shows up on the corners, probably due to the discretization of the scene and low resolution of the volume


The following screenshots were taken with the following configuration: fullscreen resolution, 16 cones per pixel, 40 samples per cone.

Posted Image Posted ImagePosted ImagePosted ImagePosted ImagePosted Image

Benefits of Physically Based Rendering

26 March 2012 - 06:29 AM

Hey, guys. I'd like to ask your opinions on the somewhat recent trend of replacing the old lighting models (Blinn-Phong) by more physically accurate ones (Oren-Nayar, Cook-Torrance, Ward, etc.).It seems like nowadays lots of people are switching to these models and other physically based techniques to obtain energy conservation and more intuitive artistic parameters but do these models really provide a significant boost in visual realism?
I'm asking this because I've tried a combination of Oren-Nayar for diffuse and Cook-Torrance for specular and I did not notice any increase in realism, the resulting lighting is slightly different but not necessarily better nor worse, just different. I've even done some comparison renderings in 3dsMax and they also don't show any increase in realism, once again they just look different. What's your take on this subject?

One more thing, how could Oren-Nayar be used with ambient lighting stored in Spherical Harmonics? The SH coefficients to approximate a cosine convolution are well known and widely used, but now we need coefficients that approximate the Oren-Nayar diffuse convolution, does anyone know if these coefficients have already been derived?

Thanks in advance

Screen Space Motion Blur artifacts

31 January 2012 - 07:39 AM

Hello, I guys, I'm implementing screen space motion blur in my deferred renderer using the trick of obtaining the per-pixel velocity vector by transforming the pixel's world space position by the current and previous view/projection matrices and calculating the difference between the two.
The results of this technique are good except when I rotate the camera too fast or move backwards which results in blurring artifacts/discontinuities (I'll upload a screenshot as soon as I can). I believe this is due to the fact that in those cases the pixel was behind the camera in the previous frame and so it won't be correctly projected to the near plane because its W value is bellow the [-1, 1] range. However I see everyone using this technique without any problems so what am I missing here?

Thanks in advance

PARTNERS