Computer Graphics (CSE306), Bachelor of Science, École Polytechnique.
Overview
This project implements a free-surface 2D fluid solver using incompressible Euler’s equations. It implements all of the mandatory sections of the assignment: Voronoï Diagrams, Power Diagram, Optimization with LBFGS, the de Gallouet-Mérigot incompressible Euler scheme, and a spring force from each fluid particle to their Laguerre’s cell centroid. The code is written in C++11 and split into headers and sources for organisational purposes, with a Makefile to simplify compilation. To ensure clarity and correctness, the code is also optimized as much as possible: const statements were added wherever possible to avoid and identify bugs easily, floating-point operations were prioritized for the highest precision, and the most efficient types were used for each variable to optimize memory.
Clipping and Voronoï diagrams
The first part of the project revolves around implementing the Voronoï Parallel Linear Enumeration algorithm. For that, I implement the Sutherland-Hodgman polygon clipping algorithm, a Polygon class, and a VoronoiDiagram class. The implementation renders a diagram of N = 3000 cells in 0.072s.
Power diagram and weights optimization with L-BFGS
In this second part, the Voronoï diagram is converted to a Power diagram that generalizes it by assigning a weight to each point, implementing semi-discrete optimal transport with L-BFGS. Beyond uniform weights, the solver can be tested with arbitrary weight distributions: below, a Gaussian distribution (standard deviation σ = 0.18) and an exponential distribution from the bottom-left corner (λ = 4), each tailored for best visual results.
Fluid dynamics
After implementing these diagrams which we can parametrize with any kind of weights, we can move on to modeling fluid dynamics. Each fluid particle is coupled to its Laguerre cell through a spring force to the cell centroid, and the system is advanced with the de Gallouet-Mérigot incompressible Euler scheme. The simulation below runs 500 fluid particles with ε = 0.004, dt = 0.002 and a mass of 200 per particle, over 250+ frames.
Key results
- Voronoï diagram via parallel linear enumeration: 0.072s for N = 3000 cells.
- Power diagram with semi-discrete optimal transport optimised through L-BFGS, supporting arbitrary weight distributions (uniform, Gaussian, exponential).
- Free-surface fluid simulation coupling each particle to its Laguerre cell centroid via the de Gallouet-Mérigot incompressible Euler scheme.