Overview
Semi-Lagrangian Advection samples where each grid cell's contents came from in the previous timestep, making advection stable for larger timesteps.
ExtendedSource checked
Semi-Lagrangian Advection
Moves quantities through a velocity field by tracing backward from grid cells.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Simulation
- Difficulty
- Intermediate
- Family
- Grid Advection
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
backtracevelocity fieldinterpolationstable advection
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(cells)
Average
O(cells)
Worst
O(cells)
Space
O(cells)
When to Use
- Use when stable visual advection is needed more than perfectly sharp transport.
- Use when smoke transport is a central requirement.
When Not to Use
- Avoid when preserving fine detail without diffusion is the primary requirement.
- Avoid when the timestep, constraints, or stability requirements exceed what the method can handle.
What It Does
- Traces backward through velocity
- Samples the previous field
- Writes advected values to the current grid
Use Cases
- Smoke transport
- Fluid dye movement
- Stable grid simulation
Inputs
- Quantity grid
- Velocity field
- Timestep
Outputs
- Advected quantity grid
Key Formulas (1)
Backtrace position
previousposition = position − dt · velocity(position)
previous_position = position - dt * velocity(position)Finds where the current cell's quantity came from.
Pseudocode
- 1.For each grid cell, read its position
- 2.Trace backward by velocity times timestep
- 3.Interpolate the old quantity at that previous position
- 4.Store the sampled value in the new grid
Canonical Example
- Input
- cell position = x, velocity = right, dt = 1
- Output
- sample previous field at x - velocity * dt
- Explanation
- The cell receives the value from upstream.
Implementation Notes
- Use interpolation and boundary clamping consistently for scalar and vector fields.
- Keep units, timestep size, and state variables explicit in tests.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- Sampling outside the domain without clear boundary rules creates edge artifacts.
- Large timesteps can add energy, damp motion, or make constraints explode.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow grid cells pulling color from where the flow came from in the previous frame.
Step 1 of 4: For each grid cell, read its position
simulation-stateNotes
The method is stable but can introduce numerical diffusion.
Sources (2)
What each reference supports for this entry.
Stable Fluids
PaperReference for semi-Lagrangian advection in stable grid-based fluid simulation.
Open sourceFluid Simulation for Computer Graphics
BookFluid-simulation reference covering Semi-Lagrangian Advection grid advection, stability tradeoff, and numerical update model.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toFinite Volume Fluid Simulation
Semi-Lagrangian methods trade sharp conservation for stability.
Often paired withNavier-Stokes Projection
Semi-Lagrangian advection is commonly used in stable incompressible fluid solvers.
Related Algorithms
Tags
SimulationAdvectionMesh MethodNumerical Methods