Environment mapping & faster surface reconstruction

So I have finished putting in environment mapping - I might tweak the shader a bit more as right now I am doing 100% reflectivity whereas elemental mercury should be around 70%. However, I think the texture already goes a long way in help to sell the mercury effect.

Here's a quick vid of the classic glut teapot rendered with environment cube mapping


I have also gotten the improved algorithm to a more stable point. Unfortunately, it's still not real time for 100 particles, but I was at least able to visualize it at a sluggish .1 fps for 100 and realtime for 10 particles. Optimizing on my spatial hashing code should further speed up the algorithm. Also, I am going to try a quick change to the data structure storing the grid point to sample which should also result in a speedup (using a list instead of a set, creating it in linear time, then sorting in O(nlogn) and then iterating through and copying into a new list to get rid of duplicates.

Here's two videos demonstrating the real time 10-particle mercury and the 100-particle mercury sped up to real time.





Anyway, as you can see from the video, the more refined implicit surface reconstruction combo'd with the environment mapping goes a long in selling the material as mercury. Also, the volume introduced by the surface helps add to the surface tension-like blobbiness of the mercury by giving additional depth to the material.

Some sources that were a huge help in understanding environment mapping and actually getting glsl shaders to work:

http://elf-stone.com/glee.php
    -GLee for getting openGL extensions to work
http://www.lonesock.net/soil.html
    -SOIL for loading in cube maps
http://tfc.duke.free.fr/
    -a great environment mapping demo which was a huge help as a base for my code
http://www.lighthouse3d.com/tutorials/glsl-tutorial/?intro
    - a good intro to understanding glsl
http://nehe.gamedev.net/data/articles/article.asp?article=21
    - another thorough article on understanding glsl in general
http://www.ozone3d.net/tutorials/glsl_texturing_p04.php
    - a good environment cube mapping tutorial for glsl
a href="http://3dshaders.com/home/index.php?option=com_weblinks&catid=14&Itemid=34"
    - lots of glsl resources and shader code useful as a reference
http://www.cse.ohio-state.edu/~hwshen/781/Site/Lab4.html
    - another helpful tutorial on setting up environment cube mapping in openGL/glsl
http://www.codemonsters.de/home/content.php?show=cubemaps
    - awesome resource for images to use in creating cube maps; currently I am using one of the ones from NVIDIA.

This will likely be my last post before the presentation and poster session on Thursday, as with Passover just ending, things have been really crazy and I'm still working on finishing up the poster and video and making some final tweaks before the presentation. As always, any comments or feedback is much appreciated!

Texturing and Environment Mapping

As progress has been somewhat limited due to Passover and my current internet connection currently being rather slow, and also due to the fact that I will undoubtedly be posting again later this week, this will be one of the shorter blog posts - at least till I can update with pretty pictures of my progress.  I have currently made a lot of headway on implementing my plan for massively culling the search space for the marching cubes algorithm, but am still bottlenecking on the spatial hashing code and on using stl::sets and corresponding memory management effectively.  I am currently looking again at the grid implementation on this open source SPH implementation for ideas on optimizing the spatial hashing.

Anyway, for now I have shouldered that part and started on the texturing and environment mapping.  Unlike the above, the implementation for this is relatively straightforward; I think texturing is somewhat working now, but I still need to tweak the OpenGL lighting/materials to get more shininess on the liquid. I've been familiarizing myself with GLSL for the cube mapping and it's also proving pretty manageable to use, so I'm also hoping to get that completed in the very near future. That's all for now; hopefully more to come very soon.

Efficiency Idea/Algorithm

Since my current efficiency bottleneck right now is in the cube marching step, I've been thinking about a way to get my algorithm to only sample grid cells likely to be at the border of the implicit surface. So after some serious brainstorming, I thought of a simple idea that should make the cube marching algorithm run significantly faster for me.

The idea basically exploits the fact that the implicit blobby surface should look topologically very similar to the list of spheres that currently approximates the surface in my fluid dynamics algorithm.  Specifically, only very local spheres should have an impact on the implicit surface at any point.  Basically I would like the implicit surface to look like the spheres except with the blobby metaball effect between very nearby ones.  With that in mind, I came up with this algorithm that should allow for a much finer subdivision of my grid without sampling every point.  Rather than a cube marching algorithm, it now ends up being more of a cube finding method in that it only samples voxel cubes that are nearby the implicit surface.

for-each particle
    1.Get a loose boundary B of the sphere (e.g. a bounding box extended such that its width is 2*(the desired radius)
    2.Divide B into x segments and "project" (e.g. round down) to nearest grid cell**
       -Each cell can be defined by a unique integer id based on position
    3.Add each of these cells to a set of integers s- prevents duplicates
---------------------------------------
in cube-marching: for each cell in s
    1. sample that cell as in cube-marching

**Get the nearest grid cell as follows: e.g. In 1-D case, if grid cell size is .01 a segment at .016 might round down to .01. Likewise .026 would round down to .02. Note also that grid cell size should be set equal to the bounding_width/x

I can also reduce the time it takes to sample a point by using spatial hashing on the heuristic that far away spheres should not have an influence on the surface. To do this, I simply need to modify my spatial hashing grid such that it can take an arbitrary position and return all nearby spheres. Sampling can then be re-written as:

sample(point a) {
    get list l of all spheres in a from the spatial hashing grid
    compute the implicit surface at this point using only nearby spheres
}

Analysis:
Since we are looping through each of n particles, and for each particle dividing into x segments along each dimension, we get a total of n*x³ cells to try to add to the set.  In the worst case, adding to the set takes O(lg n*x³) time, so for the first setup part of the algorithm we have an upper bound of O(n*x³lg nx³) = O(n*x³(3lg x+lg n)).

For the sampling part, assuming spatial hashing reduces the evaluation of the surface to O(n_h), since we are sampling up to O(8n*x³) grid points, the running time upper bounds at O(8n*n_h*x³). Since x is used to define amount of subdivisions per sphere exactly and will be some constant, such as 10, and n_h should dominate the lg n term, the entire algorithm is thus upper-bounded by O(n*n_h), same as the dynamics part of the algorithm.  In practice, the constant of order 1000-10000 will be significant in slowing down the running time, this can be somewhat reduced by lowering the value of x, and the overall running time will still be significantly faster since the algorithm would no longer be evaluating the surface at each of the X³ grid cells, where X is the number of subdivisions per dimension in the entire grid space.
______

So for now, I am working on putting this idea into practice and seeing if it will significantly speed up my algorithm to allow for much finer grid resolution. I am also working on texturing so that I can put environment mapping in. On Joe's recommendation I am using glsl to do the environment mapping, which looks like it should be a really nice simple implementation.  In the mean time, any thoughts/comments on the feasibility of the above algorithm would be much appreciated

Slow Progress and Smooth Shading

With the beta review coming up, I finally have some results to show on the implicit surface reconstruction side. The problem is, it runs no where close to real time except at extremely low grid resolution/ poly count. However, you can sort of start to get the idea. Also, with surface normals computed, I have smooth shading working as well. I am currently using an adapted version of the open source marching cube code by Cory Gene Bloyd from this site. I am now thinking in terms of future approach that it is possible that using hierarchical bounding volumes and having an adaptively sized grid might make this algorithm work fast enough at least for low spatial separation.

Anyhow, here's what I currently have: