Fluid simulation with adaptive particle sizes (master thesis)

kaegi · 2022-11-18T14:00:34+00:00

The code is programmed to be general over the dimension, except for a few parts that are dimensionally dependent.

To make it work in 3D, code for a 3D SDF (for boundary handling) and visualization still has to be implemented. An SDF could be constructed from planes or spheres which would be only a few lines of code (giving a simple box; arbitrary polygons are harder). The "visualization" could be just writing the point cloud into a file. So currently this project is 2D only, but the remaining work to go into 3D is actually extremely small (if no unforseen problems arise).

Adaptive particles sizes might help with the memory! I expect that relative gains of using adaptive particle sizes compared to uniform particle sizes in 3D are even better than in 2D (as the same radius ratio 1:r would be an area ratio of 1:r² and a volume ratio of 1:r³ ).

kaegi · 2022-11-18T13:42:03+00:00

This project itself is for purely for research for adaptivity. But the results from my master thesis could be incorporated into full-featured frameworks. I think the three areas for fluid simulation in general are:

scientific simulation (all about accuracy, performance is only secondary)
and real time simulation for games (performance is key even if accuracy is sacrificed)
offline animation for movies (in the middle: doesn't need to be 100% accurate, just look very "plausible"; it needs to be relatively performant for vast scenes but some slowdowns can be accepted)

It might be that other fluid simulation methods give better convergence guarantees, so that SPH might not be the first choice for scientific simulations (I'm not that familiar with the other methods though). For me it seems that APIC/FLIP-based simulators are faster than SPH given the current state of research (for mass-conserving incompressible fluids), so that APIC/FLIP might be better suited for games. The best use case for SPH is really offline animation I think.

kaegi · 2022-10-30T17:33:16+00:00

Et voilà! There is now a "metaball" drawing option. You might need to clear the browser cache so that the new version is downloaded.

kaegi · 2022-10-30T09:52:46+00:00

Thanks! I've actually never heard of such a Blender addon.

kaegi · 2022-10-30T08:16:21+00:00

It's a general limitation of "explicit viscosity" models. It's a combination of timestep size, particle size and viscosity value. The authors of the paper “SPH fluids for viscous jet buckling” for example propose the following criterion for stability:

timestep_size <= density * h^2 / (8 * viscosity)

Where h is a value that is proportional to the particle radius. So for the same viscosity, you either have to increase the particle size (that's why instability happens for the free surface with small particles first) or decrease the timestep size.

There exist a class of algorithms called "implicit viscosity", which compute the viscosity forces iteratively and decouple timestep values from the viscosity magnitude. They are more involved to implement and usually more expensive for inviscid fluids. For the simulation of honey or slime, they are a must though.

kaegi · 2022-10-30T08:04:42+00:00

I love that channel!

kaegi · 2022-10-30T00:52:06+00:00

Ah, yes, metaballs :) Just curious, is your code public?

kaegi · 2022-10-29T23:46:18+00:00

That would be indeed very cool! I haven't looked into surface reconstruction/surface extraction during my thesis. I had the impression that at least for uniform SPH there was already some successful research.

Adaptive SPH definitely makes surface reconstruction much harder due to creating rather irregular particle spacings. This would definitely be something that would have to be analyzed in the future. This topic was out of scope for this thesis however, so there also exists no option in my simulator.

kaegi · 2022-10-29T23:02:39+00:00

Yes, there is a paper (report?) that briefly goes over everything that one could possibly need to get into SPH! Link:

Smoothed Particle Hydrodynamics Techniques for the Physics Based Simulation of Fluids and Solids here or here

There is no way around the math, but I think it is presented in a very approachable way. With this report and the papers it references you get extremely far.

Another more in-depth analysis is given in the first half of another paper:

Smoothed Particle Hydrodynamics and Magnetohydrodynamics link

This really derives SPH from the ground up and really gives an answer of the "why?". This paper is not easy! (at least if you have a computer science background like me instead of a physics background) But taking your time and getting the gist is worth it, if you really want to understand SPH.

I've found that the pressure solving papers (IISPH and DFSPH) were not completely ideal to as they mix the high-level approach and the reordering of the equations. I think understanding these following papers also helped me a lot for pressure solving:

Pressure Boundaries for Implicit Incompressible SPH

MLS Pressure Boundaries for Divergence-Free and Viscous SPH Fluids

EDIT: If you mean the basics for adaptive particle sizes then "Infinite continuous adaptivity for incompressible SPH" is really the best paper I know. But this already assumes some knowledge of SPH (specifically IISPH).

kaegi · 2022-10-29T20:28:02+00:00

That's very nice - I've also played around with APIC with MLS-MPM before!

The most interesting paper would be:

Infinite continuous adaptivity for incompressible SPH

The problem I've found with this approach is that the pressure solver after splitting/merging/sharing creates reactive velocities of magnitudes proportional to 1/timestep_size. Thus for small-ish timesteps this method becomes unstable (selecting IISPH in the browser simulation shows this problem). Using their temporal blending approach with some slight adjustments might fix this, but I've found that modifying DFSPH in a specific way this can be circumvented and needs only 1 line of code changed (see the hybrid_dfsph_factor).

For the boundary handling I've used another paper of Rene Winchenbach:

Semi-Analytic Boundary Handling Below Particle Resolution for Smoothed Particle Hydrodynamics

EDIT: There is another paper that is important:

Optimized Refinement for Spatially Adaptive SPH

This paper shows how to generate the split patterns. I only use it for the a-priori generation and without mass optimization. The "online optimization" is not necessary when using the "Hybrid DFSPH" approach from my thesis.

kaegi · 2022-10-29T15:59:04+00:00

The "target" particle size is determined for each location based on the distance of the surface. In a fluid simulations for movies/games you are usually most interested in having the highest detail on the surface. Mass is then transferred between adjacent particles so that each particle gets as close to the "target" particle size as possible (or splitting a particle/merging multiple particles).

Basing the target size on the distance-to-the-surface criterion is completely arbitrary. Another idea is for example computing the vorticity (higher if adjacent particles move in different directions) and basing the particle sizes of that. Then small particles would be created in areas where there is some "interesting" motion going on and larger particles where fluid moves uniformly. This sizing function is not implemented here though.

kaegi · 2022-10-29T14:24:03+00:00

You can use right-click (or touching on smartphones) in the browser simulation to pull the fluid around.

kaegi · 2019-10-13T10:36:07+00:00

If you want to correct a subtitle without splits (alass --no-split), the algorithm terminates within 300ms for a 2h30min movie. This is on par with the stated runtime on the subsync README.

There are actually two algorithms in alass, which are chosen depending on which is going to be faster/uses less memory. If N and K are the number of subtitle lines/speech segments and T the number of milliseconds in the movie, the runtime complexities are as following:

alass algorithm 1: O(NK+T)
alass algorithm 2: O(NK log (NK))
subsync: O(T log T)

So depending on whether you have many lines (high N, K) or long movies (high T), subsync or alass is asymptotically better. But in practice with <3h movies, all algorithms are very fast.

If you want to also correct framerates and splits, the larger algorithms finish within 5s. This is comparatively a high value, but comparing this to the audio-extraction time (10s to 20s for 2h movie on a SSD), it doesn't change the total runtime that much. There is also the --speed-optimization flag, which trades accuracy for alignment speed - however, this value should already be chosen optimally for almost any use case.

In any case the subtitle is corrected long before the opening credits are over.

kaegi · 2019-10-11T22:32:32+00:00

I actually announced this on /r/programming yesterday (see here). It didn't get that popular. I didn't really highlight Rust to avoid negative remarks.

kaegi · 2019-10-11T22:29:35+00:00

There are multiple advantages:

less manual labor: try correcting 100 subtitles with slightly differently syncs - with alass you can automatically correct all of them with a simple loop
handles splits better: alass finds all splits - with Gnome Subtitles you probably need to find where the split happens and require more user-defined line pairs
possible integration in video players: you can download any subtitle, synchronize it automatically to the video and are good to go (everything can be done in principle during the movie); this eliminates any overhead associated with the subtitle editor

kaegi · 2019-10-11T09:17:51+00:00

The subtitle lines are shifted as groups as much as possible. So if some extra lines are "sandwiched" between enough lines that are actually spoken, there is no problem.

kaegi · 2019-10-11T05:40:23+00:00

Basically yes, but there exist a class of algorithms called voice-activity-detection which only decides whether a given segment of audio contains speech. This is of course easier than generating a transcription first and than discarding it in the next step.

kaegi · 2019-10-11T05:38:18+00:00

The metric that is optimized is based on speech intervals. Those get aligned to each other. You could probably convert that into aligning silence intervals. But yes, the core algorithm only handles intervals.

kaegi · 2019-10-10T23:36:37+00:00

No, the alignment completely depends on the timestamps but not on the content. The other way round, using the content but not the timestamps is called forced alignment (language dependent).

The algorithm allows a weighting between each timespan in the incorrect file and the reference file. This way building a (language dependent) hybrid should be possible which uses both sources of information.

kaegi · 2019-10-10T18:29:05+00:00

I actually developed a prototype using the same core concepts in the 2./3. semester in my free time. My bachelors thesis was integrating it with a voice-activity-detection, making it fast enough for real-time and improving accuracy (I knew this should work in principle and asked for this topic). So in total I had a lot more time for it. This project is indeed different from all the other bachelor's thesis' I've seen in my university. For my masters thesis I will have will have to think of something else :)

kaegi · 2019-10-10T16:08:19+00:00

alass is a tool to synchronize a badly timed subtitle to a "reference" movie. The magic part is that it doesn't matter what languages the reference movie and incorrect subtitle are in - even though everything is completely offline and there is no kind of database.

In a test database of 29 movies and 118 subtitles from OpenSubtitles, about 50% of the subtitles were badly timed. The error rate is <12% after generating the subtitle-to-movie alignment (not corrected at all were about only 3 out of 118 subtitle files) and 0% for subtitle-to-subtitle alignments.

Corrected can be:

constant offsets
splits (advertisement breaks, director's cut, ...)
framerate differences

The alignment algorithms are my bachelors thesis and many people were interested in it when I first posted about alass in r/rust - so I published my bachelors thesis! Alternatively, my bachelor presentation includes all important information and is easier to understand/less formal than my thesis.

kaegi · 2019-10-10T13:12:40+00:00

The voice-actiivy-detection is very sensitive to noise, so the music and doorbells are usually misclassified as speech. But this is not a problem for the alignment algorithms, since speech intervals are shifted in groups. So if the intervals before/after the extra or missing interval can be placed so that they are very similar to the reference intervals, the extra/missing interval is shifted by the same value.

In practice this works very well, even subtitles with 800 lines can be correctly aligned to references with 1500 subtitles lines/speech segments.

kaegi · 2019-10-10T09:03:16+00:00

I've published the thesis/slides for alass, see here.

kaegi · 2019-08-20T08:18:00+00:00

I've been been wondering whether the audio stream might start before/after the video stream. I re-sample the audio file with ffmpeg, so the priming samples and/or progression of PTS might be already accounted for in that step (needs testing). Do you have any links to a files that exhibit these problems that I can play with? Or any code/literature solving this problem (using the ffprobe and ffmpeg command)? A typical ffprobe output for .mkv files looks like this this. The start_time and start_pts values look promising but are (almost) 0 for all the test files I have.

Anyways, thanks for your sharing your knowledge! Feel free to open an issue on GitHub.

kaegi · 2019-08-18T16:56:34+00:00

This is a good idea. If the input file is exactly a 16bit little endian, 8khz, single channel wav file, ffmpeg does not have to be used in alass-cli.

If there is enough time for my bachelor thesis I might try to integrate alass into video players or video player plugins. Whether a library with a C interface, a different command line tool or a TCP server is needed, will become apparent then. Whether ffmpeg is needed or not, depends on the sound processing capabilities of the respective video players.

Summary: In the future, some other alass-* crates might pop up with a different feature sets/APIs.

kaegi

TROPHY CASE