CSE 291D Final Report

by Alexandr Kuznetsov

For the final project I implemented a SPH fluid simulation.

For that implemented the following:

  • SPH algorithm
  • Spatial hash table for performance
    • With single directional linked list of particles
    • With the set of dirty cells
  • Marching Cube algorithm
    • With vertex hashing
    • And smooth normals
    • Unlimited boundary
  • Extended ray tracer to support water
    • Reflection and refraction
  • Pressure projection solver
  • OpenMP

Video

Fluid Simulator 6_13_2019 3_22_13 PM.mp4

Example of marching cube

With support of smooth shading. I order to do that, I use hash table to find if there an existent vertex for a given edge. Then, I can add that vertex to triangle instead of creating a new one. There 3 different types of edges (x,y,z) for a given position. As a result, I can calculate the normal at a vertex by taking a weighted average of neighboring faces.

Unlimited boundary. If a cube has a surface, I add all the neighboring cubes to be process if they haven't already. For that I used a hashing table to keep track of to be process and done cubes.

Example of ray traced water surface

Used GPU ray tracing api called Optix.

You can see refractions and reflections of the environment map.

Blue color is only in the back. Therefore, blue indicate reflection.

Hash table

I implemented a hash table for quick lookup. Instead of traditional hash table, with a vector list (which would be slow), my hash table points to a particle single. That particle points to another particle in the same cell. As a result, hash tables points to a sinly linked list of particles in a given cell.

Also I track what location in hash table were use. That way I can clean them very fast if hash table is under utilized.

Pressure projection solver

Divergence free method.

Pressure Poisson Equation is solved using conjugate gradient.

I'm still debugging the explosion.

Multithreading

OpenMP was used to speed up calculation across multiple threads.

References

"SPH Fluids in Computer Graphics", Ihmsen, Orthmann, Solenthaler, Kolb, Teschner

"Marching cubes: A high resolution 3D surface construction algorithm", WE Lorensen, HE Cline

http://paulbourke.net/geometry/polygonise/

https://en.wikipedia.org/wiki/Conjugate_gradient_method