Navigation überspringen
A common optimization to real-time fluid simulations in computer graphics is to use a "Multigrid"…
0:00 / 0:22

A common optimization to real-time fluid simulations in computer graphics is to use a "Multigrid"…

Morten Vassvik

@vassvik3109 Follower

Auf X besuchen

42.305 Aufrufe

A common optimization to real-time fluid simulations in computer graphics is to use a "Multigrid" algorithm to acceleration the solver. This process is often fraught with pitfalls, and there are few references on the expected result. This aims to serve as one such reference.

15 Kommentare

Kommentare aus dem Originalbeitrag auf X (Twitter)

  • Profilbild von Morten Vassvik

    @vassvik

    First disclaimer: This thread: - is not a tutorial on how to implement a Multigrid solver - does not contain advice on how to tune such an algorithm - does not explain what the common pitfalls are or how to solve them A base level of familiarity and understanding is expected

    5 Likes

  • Profilbild von Morten Vassvik

    @vassvik

    Instead, this thread serves as a reference of what things should look like if implemented correctly free of bugs, based on a sensible set of default parameters. In particular, we will look at convergence rates in a coarse manner for a few different setups.

    4 Likes

  • Profilbild von Morten Vassvik

    @vassvik

    The TLDR: The residual/divergence should reduce approximately by an order of magnitude (10x) per V-cycle for a MAC-grid type simulation with open boundaries. This result is mostly input-independent. This is not the optimal result, but is a baseline for more complex variants.

    9 Likes

  • Profilbild von Morten Vassvik

    @vassvik

    Incorrect and buggy implementations will still converge faster than plain Jacobi iterations, but it will be far less efficient and less consistent than what's presented here.

    2 Likes

  • Profilbild von Morten Vassvik

    @vassvik

    As shown in the first tweet of this thread the case study here is a 256x256 grid with a small square source that injects velocity towards the right and also injects density for visualization purposes. The video pauses on the snapshots we'll study in the later posts.

    5 Likes

  • Profilbild von Morten Vassvik

    @vassvik

    There are three grid levels: 256x256, 128x128 and 64x64, respectively. We use 1 pre-smooth and 4 post-smooth iterations (omega 0.8), and 64 SOR half-iterations on the coarse grid solve (omega 1.86). There are between 0 and 8 V-cycles. We use 32-bit floats for the precision.

    4 Likes

  • Profilbild von Morten Vassvik

    @vassvik

    First we'll look at the initial time step. The velocity inside the square point to the right and the of the velocity is zero. The resulting velocity field is reminiscent of the magnetic field from a bar magnet, which ultimately is what makes the fluid curl as it moves.

    5 Likes

  • Profilbild von Morten Vassvik

    @vassvik

    First to explain the color scheme: On the upper left is the velocity field, it uses 0.5 + 0.5*v as colors like a typical flowmap The upper right has the density field The lower left shows the Pressure field The lower right shows the Divergence/Residual field

    2 Likes

  • Profilbild von Morten Vassvik

    @vassvik

    The color scheme on the pressure and divergence/residuals is logarithmic (base 10) and relative. Each color level represent one order of magnitude (10x). White represents values 10 times larger than the orange values, which are 10 times larger than the cyan values, and so on

    3 Likes

  • Profilbild von Morten Vassvik

    @vassvik

    In other words, if a color changes from orange to cyan, or from cyan to purple, or from purple to yellow, and so on, it means the values there decreased by approximately one order of magnitude The maximum and average divergence/residual are also presented as text

    3 Likes

  • Profilbild von Morten Vassvik

    @vassvik

    In the first few V-cycles the residual/divergence mostly reduces by an order of magnitude, matching the earlier descriptions. Eventually parts of the solution converges with some hot spots left that requires more work until eventually floating point precision is reached.

    4 Likes

  • Profilbild von Morten Vassvik

    @vassvik

    Next we'll look at a later snapshot, after 80 or so time steps, where the characteristic initial vortex have appeared. The convergence trend is overall the same as in the previous case.

    4 Likes

  • Profilbild von Morten Vassvik

    @vassvik

    Lastly, after 640 steps, where we have a characteristic vortex street emerging.

    4 Likes

  • Profilbild von Morten Vassvik

    @vassvik

    To emphasize the input-independent nature(i.e. relative to the initial divergence), here's all the gifs side by side (rip compression?) Direct link to full sized gif: And also a link to all the raw image files and videos:

    8 Likes

  • Profilbild von Matt Figdore

    @mattfigdore

    This is the biggest productivity cheat code right now. Kiss reading documents goodbye. You can get an instant summary of any document with this tool.

    15.835 Likes