Cogs and Levers A blog full of technical stuff

Writing Your Own Lisp Interpreter in Haskell - Part 2

15 Feb 2025

Introduction

In our previous post we put a very simple Lisp interpreter together that was capable of some very basic arithmetic.

In today’s update, we’ll introduce variable definitions into our Lisp interpreter, allowing users to define and retrieve values persistently. This required a number of structural changes to support mutable environments, error handling, and function lookups.

All the changes here will set us up to do much more sophisticated things in our system.

If you’re following along, you can find the implementation for this article here.

Mutable Environment

In order to store variables in our environment, we need to make it mutable. This way we can store new values in the environment as we define them.

Env was originally a pure Map:

type Env = Map String LispVal

This meant that variable bindings were immutable and couldn’t persist across expressions.

We changed Env to an IORef (Map String LispVal), making it mutable:

type Env = IORef (Map String LispVal)

We added nullEnv to create an empty environment:

nullEnv :: IO Env
nullEnv = newIORef Map.empty

Why?

  • This allows variables to persist across expressions.
  • Future changes (like set! for modifying variables) require mutability.
  • IORef enables safe concurrent updates in a controlled manner.

REPL update

Now we need to update our REPL at the top level to be able to use this mutable state.

Previously, our REPL was just using the primitiveEnv value.

main :: IO ()
main = do
    putStrLn "Welcome to Mini Lisp (Haskell)"
    repl primitiveEnv

We now pass it in as a value. Note that the underlying types have changed.

main :: IO ()
main = do
    env <- primitiveEnv  -- Create a new environment
    putStrLn "Welcome to Mini Lisp (Haskell)"
    repl env

Why?

  • The REPL now uses a mutable environment (primitiveEnv).
  • This ensures variables persist across expressions instead of resetting each time.

Variable Definition

We introduced defineVar to allow defining variables:

defineVar :: Env -> String -> LispVal -> IOThrowsError LispVal
defineVar envRef var val = do
    env <- liftIO $ readIORef envRef  -- Read environment
    liftIO $ writeIORef envRef (Map.insert var val env)  -- Update environment
    return val

This enables us to define variables like this:

(define x 10)

defineVar reads the current environment, updates it, and then writes it back.

Evaluation

Probably the biggest change is that our evaluation no longer returns just a ThrowsError LispVal.

eval :: Env -> LispVal -> ThrowsError LispVal

This has had to be upgraded to support our IO activity as we now have mutable state.

eval :: Env -> LispVal -> IOThrowsError LispVal

This change allows eval to interact with mutable variables stored in Env and perform IO actions when updating environment bindings

We also added parsing support for define:

eval env (List [Atom "define", Atom var, expr]) = do
    val <- eval env expr
    defineVar env var val

Variable Lookup

Our lookupVar now needs an upgrade:

lookupVar :: Env -> String -> ThrowsError LispVal
lookupVar env var = case Map.lookup var env of
    Just val -> Right val
    Nothing  -> Left $ UnboundVar var

It’s not designed to work in a mutable IORef environment. We create getVar to accomodate.

getVar :: Env -> String -> IOThrowsError LispVal
getVar envRef var = do
    env <- liftIO $ readIORef envRef  -- Read environment from IORef
    case Map.lookup var env of
        Just val -> return val
        Nothing  -> throwError $ UnboundVar ("Undefined variable: " ++ var)

This now allows variables to be defined and retrieved across multiple expressions.

Builtins

Previously, built-in functions were not stored as part of the environment.

primitives :: [(String, LispVal)]
primitives =
  [ ("+", BuiltinFunc numericAdd),
    ("-", BuiltinFunc numericSub),
    ("*", BuiltinFunc numericMul),
    ("/", BuiltinFunc numericDiv)
  ]

This has changed now with primitiveEnv which will store a set of these.

primitiveEnv :: IO Env
primitiveEnv = newIORef (Map.fromList primitives)

This change enables us to dynamically add more built-in functions in the future.

Fixing eval

With the introduction of IO into our program, our evaluation logic needed updates to handle variable bindings correctly.

eval env (List (Atom func : args)) = do
    func' <- eval env (Atom func)
    args' <- mapM (eval env) args
    apply func' args'

Now, we’ll look up the function in the environment:

eval env (List (Atom func : args)) = do
    func' <- getVar env func  -- Look up function in the environment
    args' <- mapM (eval env) args  -- Evaluate arguments
    apply func' args'

Now, we’ll find any of our functions in the environment itself.

Fixing apply

Now, we need to look at the apply function.

apply (BuiltinFunc f) args = f args

We add support for functions out of the environment with the liftThrows helper:

apply (BuiltinFunc f) args = liftThrows $ f args

Provision is also added for user-defined functions (lambda):

apply (Lambda params body closure) args = do
    env <- liftIO $ readIORef closure  -- Read function's closure environment
    if length params == length args
        then eval closure body
        else throwError $ NumArgs (length params) args

ThrowsError

Previously, ThrowsError was used for error handling:

type ThrowsError = Either LispError

However, since we now interact with IO, we introduce IOThrowsError:

type IOThrowsError = ExceptT LispError IO

We also add helper functions to manage conversions between them:

runIOThrows :: IOThrowsError String -> IO String
runIOThrows action = runExceptT action >>= return . extract
  where
    extract (Left err)  = "Error: " ++ show err
    extract (Right val) = val

liftThrows :: ThrowsError a -> IOThrowsError a
liftThrows (Left err)  = throwError err
liftThrows (Right val) = return val

Why?

  • Allows IO operations inside error handling (necessary for mutable Env).
  • Prevents mixing IO and pure computations incorrectly.
  • Enables future features like reading files, user-defined functions, etc.

Fixing readExpr

Finally, we need to fix readExpr. It’s current defined like this:

readExpr :: String -> ThrowsError LispVal

It changes to support IOThrowsError:

readExpr :: String -> IOThrowsError LispVal
readExpr input = liftThrows $ case parse parseExpr "lisp" input of
    Left err -> Left $ ParserError (show err)
    Right val -> Right val

This allows readExpr to integrate with our new IOThrowsError-based evaluator.

Running

With all of these pieces in place, we can use define to define variables and start to work with them.

Welcome to Mini Lisp (Haskell)
λ> (define a 50)
50
λ> (define b 120)
120
λ> (define c 4)
4
λ> (+ (- b c) a)
166
λ>

Conclusion

This update introduced:

  • Persistent variables using define
  • A mutable environment with IORef
  • Function lookup inside the environment
  • A fully working REPL that retains state across expressions

We’ll continue to add to this as we go. See you in the next chapter!

Writing Your Own Lisp Interpreter in Haskell - Part 1

15 Feb 2025

Introduction

Lisp has long been a favorite language for those interested in metaprogramming, functional programming, and symbolic computation. Writing your own Lisp interpreter is one of the best ways to deepen your understanding of programming languages. In this series, we’ll build a Lisp interpreter from scratch in Haskell, a language that lends itself well to this task due to its strong type system and functional nature.

In this first post, we’ll cover:

  • Defining Lisp’s syntax and core data structures
  • Writing a simple parser for Lisp expressions
  • Implementing an evaluator for basic operations

By the end of this post, you’ll have a working Lisp interpreter that can evaluate basic expressions like (+ 1 2).

If you’re following along, you can find the implementation for this article here.

Setup

We’re using Haskell to implement our Lisp interpreter, so make sure you’re installed and ready to go.

To get started, create yourself a new project. I use stack so creating my new list (called hlisp):

stack new hlisp

We’ll need a few dependencies to begin with. I’m adding my entire Lisp system to my library, leaving my main exe to simply be a REPL.

Add containers, mtl, and parsec as dependencies:

library:
    source-dirs: src
    dependencies:
        - containers
        - mtl
        - parsec

Code

Now we can get started on some code.

Defining Lisp Expressions

Lisp code is composed of simple data types:

  • Atoms (symbols, numbers, booleans)
  • Lists (sequences of expressions)
  • Functions (built-in or user-defined)

In Haskell, we can represent these using a data type:

module Expr where

import Data.Map (Map)
import qualified Data.Map as Map
import Control.Monad.Except

-- Lisp expression representation
data LispVal
    = Atom String
    | Number Integer
    | Bool Bool
    | List [LispVal]
    | Lambda [String] LispVal Env -- user-defined function
    | BuiltinFunc ([LispVal] -> ThrowsError LispVal) -- built-in functions

instance Show LispVal where
    show (Atom name) = name
    show (Number n) = show n
    show (Bool True) = "#t"
    show (Bool False) = "#f"
    show (List xs) = "(" ++ unwords (map show xs) ++ ")"
    show (Lambda params body _) =
        "(lambda (" ++ unwords params ++ ") " ++ show body ++ ")"
    show (BuiltinFunc _) = "<builtin function>"

instance Eq LispVal where
    (Atom a) == (Atom b) = a == b
    (Number a) == (Number b) = a == b
    (Bool a) == (Bool b) = a == b
    (List a) == (List b) = a == b
    _ == _ = False  -- Functions and different types are not comparable

-- Environment for variable storage
type Env = Map String LispVal

-- Error handling
data LispError
    = UnboundVar String
    | TypeMismatch String LispVal
    | BadSpecialForm String LispVal
    | NotAFunction String
    | NumArgs Int [LispVal]
    | ParserError String
    deriving (Show)

type ThrowsError = Either LispError

This defines the core structure of Lisp expressions and introduces a simple error-handling mechanism.

We define Show and Eq explicitly on LispVal because of the Lambda and BuiltinFunc not really having naturally expressed analogs for these type classes. The compiler complains!

LispVal allows us to define:

  • Atom
  • Number
  • Bool
  • List
  • Lambda
  • BuiltinFunc

The Env type gives us an environment to operate in keeping track of our variables.

LispError defines some high level problems that can occur, and ThrowsError is partially applied type where you’re either going to receive the value (to complete the application), or as the type suggests - you’ll get a LispError.

Parsing Lisp Code

To evaluate Lisp code, we first need to parse input strings into our LispVal data structures. We’ll use the Parsec library to handle parsing.

module Parser where

import Text.Parsec
import Text.Parsec.String (Parser)
import Expr
import Control.Monad
import Numeric

-- Parse an atom (symbol)
parseAtom :: Parser LispVal
parseAtom = do
    first <- letter <|> oneOf "!$%&|*+-/:<=>?@^_~"
    rest <- many (letter <|> digit <|> oneOf "!$%&|*+-/:<=>?@^_~")
    return $ Atom (first : rest)

-- Parse a number
parseNumber :: Parser LispVal
parseNumber = Number . read <$> many1 digit

-- Parse booleans
parseBool :: Parser LispVal
parseBool =
    (string "#t" >> return (Bool True)) <|> (string "#f" >> return (Bool False))

-- Parse lists
parseList :: Parser LispVal
parseList = List <$> between (char '(') (char ')') (sepBy parseExpr spaces)

-- General parser for any expression
parseExpr :: Parser LispVal
parseExpr = parseAtom <|> parseNumber <|> parseBool <|> parseList

-- Top-level function to run parser
readExpr :: String -> ThrowsError LispVal
readExpr input = case parse parseExpr "lisp" input of
    Left err -> Left $ ParserError (show err)
    Right val -> Right val

With these parsers defined, we can now evaluate expressions.

Simple Evaluation

Now, we can use these types to perform some evaluations. We do need to give our interpreter some functions that it can execute.

module Eval where

import Expr
import Control.Monad.Except
import qualified Data.Map as Map

-- Look up variable in environment
lookupVar :: Env -> String -> ThrowsError LispVal
lookupVar env var = case Map.lookup var env of
  Just val -> Right val
  Nothing -> Left $ UnboundVar var

-- Apply a function (either built-in or user-defined)
apply :: LispVal -> [LispVal] -> ThrowsError LispVal
apply (BuiltinFunc f) args = f args
apply (Lambda params body closure) args =
  if length params == length args
    then eval (Map.union (Map.fromList (zip params args)) closure) body
    else Left $ NumArgs (length params) args
apply notFunc _ = Left $ NotAFunction (show notFunc)

-- Evaluator function
eval :: Env -> LispVal -> ThrowsError LispVal
eval env (Atom var) = lookupVar env var
eval _ val@(Number _) = Right val
eval _ val@(Bool _) = Right val
eval env (List [Atom "quote", val]) = Right val
eval env (List (Atom func : args)) = do
  func' <- eval env (Atom func)
  args' <- mapM (eval env) args
  apply func' args'
eval _ badForm = Left $ BadSpecialForm "Unrecognized form" badForm

-- Sample built-in functions
primitives :: [(String, LispVal)]
primitives =
  [ ("+", BuiltinFunc numericAdd),
    ("-", BuiltinFunc numericSub),
    ("*", BuiltinFunc numericMul),
    ("/", BuiltinFunc numericDiv)
  ]

numericAdd, numericSub, numericMul, numericDiv :: [LispVal] -> ThrowsError LispVal
numericAdd [Number a, Number b] = Right $ Number (a + b)
numericAdd args = Left $ TypeMismatch "Expected numbers" (List args)

numericSub [Number a, Number b] = Right $ Number (a - b)
numericSub args = Left $ TypeMismatch "Expected numbers" (List args)

numericMul [Number a, Number b] = Right $ Number (a * b)
numericMul args = Left $ TypeMismatch "Expected numbers" (List args)

numericDiv [Number a, Number b] =
  if b == 0 then Left $ TypeMismatch "Division by zero" (Number b)
  else Right $ Number (a `div` b)
numericDiv args = Left $ TypeMismatch "Expected numbers" (List args)

-- Initialize environment
primitiveEnv :: Env
primitiveEnv = Map.fromList primitives

Creating a REPL

We can now tie all of this together with a REPL.

module Main where

import Eval
import Parser
import Expr
import Control.Monad
import System.IO

-- REPL loop
repl :: Env -> IO ()
repl env = do
  putStr "λ> "
  hFlush stdout
  input <- getLine
  unless (input == "exit") $ do
    case readExpr input >>= eval env of
      Left err -> print err
      Right val -> print val
    repl env

main :: IO ()
main = do
  putStrLn "Welcome to Mini Lisp (Haskell)"
  repl primitiveEnv

Run

Now we can give this a run!

hlisp stack exec hlisp-exe
Welcome to Mini Lisp (Haskell)
λ> (+ 6 5)
11
λ> (- 10 (+ 50 4))
-44
λ>

These simple expressions now evaluate!

Conclusion

This gives us a pretty solid base!

We now have a working Lisp interpreter that can:

  • Parse expressions (atoms, numbers, booleans, lists)
  • Evaluate basic arithmetic expressions
  • Provide an interactive REPL

In the next post, we’ll add variables, conditionals, and user-defined functions to make our Lisp more powerful!

Formatting to FAT32 on FreeBSD

06 Feb 2025

Formatting drives on any operating system can be a handful of instructions specific to that operating environment. In today’s post we’ll walk through the process of formatting a USB drive to FAT32, explaining each command along the way.

Identifying the Device

Before making any changes, you need to determine which device corresponds to your USB drive. The best way to do this is:

dmesg | grep da

or, for a more detailed view:

geom disk list

On FreeBSD, USB mass storage devices are typically named /dev/daX (where X is a number). If you only have one USB drive plugged in, it is likely /dev/da0.

Device naming in FreeBSD is quite uniform:

  • USB Drives: /dev/daX
  • SATA/SAS/IDE Drives: /dev/adaX
  • NVMe Drives: /dev/nvmeX
  • RAID Volumes: /dev/mfidX, /dev/raidX

Partitioning the Drive

Now that we know the device name, we need to set up a partition table and create a FAT32 partition.

Destroying Existing Partitions

If the drive has existing partitions, remove them:

gpart destroy -F /dev/da0

This ensures a clean slate.

Creating a Partition Table

We create a Master Boot Record (MBR) partition table using:

gpart create -s mbr /dev/da0
  • -s mbr: Specifies an MBR (Master Boot Record) partition scheme.
  • Other options include gpt (GUID Partition Table), which is more modern but may not be supported by all systems.

Adding a FAT32 Partition

Now, we create a FAT32 partition:

gpart add -t fat32 /dev/da0
  • -t fat32: Specifies the FAT32 partition type.
  • Other valid types include freebsd-ufs (FreeBSD UFS), freebsd-swap (swap partition), freebsd-zfs (ZFS), and linux-data (Linux filesystem).

After running this command, the new partition should be created as /dev/da0s1.

Formatting the Partition as FAT32

To format the partition, we use newfs_msdos:

newfs_msdos -L DISKNAME -F 32 /dev/da0s1
  • -L DISKNAME: Assigns a label to the volume.
  • -F 32: Specifies FAT32.
  • /dev/da0s1: The newly created partition.

Why /dev/da0s1 instead of /dev/da0?
When using MBR, partitions are numbered starting from s1 (slice 1), meaning that the first partition on da0 becomes da0s1. Using /dev/da0 would format the entire disk, not just a partition.

Wrapping Up

At this point, your USB drive is formatted as FAT32 and ready to use. You can mount it manually if needed:

mount -t msdosfs /dev/da0s1 /mnt

To safely remove the drive:

umount /mnt

Volumetric Fog in Shaders

03 Feb 2025

Introduction

Rendering realistic 3D environments is more than just defining surfaces—atmospheric effects like fog, mist, and light scattering add a layer of depth and realism that makes a scene feel immersive. In this post, we’ll explore volumetric fog and how we can implement it in our ray-marched Mandelbulb fractal shader.

What is Volumetric Fog?

Volumetric fog is an effect that simulates light scattering through a medium, such as:

  • Mist over a landscape
  • Dense fog hiding distant objects
  • Hazy light beams filtering through an object

Unlike simple screen-space fog, volumetric fog interacts with geometry, light, and depth, making it appear more natural. In our case, we’ll use it to create a soft, atmospheric effect around our Mandelbulb fractal.

How Does It Work?

Volumetric fog in ray marching is achieved by stepping through the scene and accumulating fog density based on distance. This is done using:

  • Exponential Fog – A basic formula that fades objects into the fog over distance.
  • Light Scattering – Simulates god rays by accumulating light along the ray path.
  • Procedural Noise Fog – Uses random noise to create a more natural, rolling mist effect.

We’ll build each of these effects step by step, expanding on our existing Mandelbulb shader to enhance its atmosphere. If you haven’t seen them already, suggested reading are the previous articles in this series:

Basis

We will start with the following code, which is our phong shaded, lit, mandelbulb with the camera spinning around it.

float mandelbulbSDF(vec3 pos) {
    vec3 z = pos;
    float dr = 1.0;
    float r;
    const int iterations = 8;
    const float power = 8.0;

    for (int i = 0; i < iterations; i++) {
        r = length(z);
        if (r > 2.0) break;

        float theta = acos(z.z / r);
        float phi = atan(z.y, z.x);
        float zr = pow(r, power - 1.0);
        dr = zr * power * dr + 1.0;
        zr *= r;
        theta *= power;
        phi *= power;

        z = zr * vec3(sin(theta) * cos(phi), sin(theta) * sin(phi), cos(theta)) + pos;
    }

    return 0.5 * log(r) * r / dr;
}

vec3 getNormal(vec3 p) {
    vec2 e = vec2(0.001, 0.0);
    return normalize(vec3(
        mandelbulbSDF(p + e.xyy) - mandelbulbSDF(p - e.xyy),
        mandelbulbSDF(p + e.yxy) - mandelbulbSDF(p - e.yxy),
        mandelbulbSDF(p + e.yyx) - mandelbulbSDF(p - e.yyx)
    ));
}

// Basic Phong shading
vec3 phongLighting(vec3 p, vec3 viewDir) {
    vec3 normal = getNormal(p);

    // Light settings
    vec3 lightPos = vec3(2.0, 2.0, -2.0);
    vec3 lightDir = normalize(lightPos - p);
    vec3 ambient = vec3(0.1); // Ambient light

    // Diffuse lighting
    float diff = max(dot(normal, lightDir), 0.0);
   
    // Specular highlight
    vec3 reflectDir = reflect(-lightDir, normal);
    float spec = pow(max(dot(viewDir, reflectDir), 0.0), 16.0); // Shininess factor
   
    return ambient + diff * vec3(1.0, 0.8, 0.6) + spec * vec3(1.0); // Final color
}

// Soft Shadows (traces a secondary ray to detect occlusion)
float softShadow(vec3 ro, vec3 rd) {
    float res = 1.0;
    float t = 0.02; // Small starting step
    for (int i = 0; i < 24; i++) {
        float d = mandelbulbSDF(ro + rd * t);
        if (d < 0.001) return 0.0; // Fully in shadow
        res = min(res, 10.0 * d / t); // Soft transition
        t += d;
    }
    return res;
}

void mainImage(out vec4 fragColor, in vec2 fragCoord) {
    vec2 uv = (fragCoord - 0.5 * iResolution.xy) / iResolution.y;

    // Rotating Camera
    float angle = iTime * 0.5;
    vec3 rayOrigin = vec3(3.0 * cos(angle), 0.0, 3.0 * sin(angle));
    vec3 target = vec3(0.0);
    vec3 forward = normalize(target - rayOrigin);
    vec3 right = normalize(cross(vec3(0, 1, 0), forward));
    vec3 up = cross(forward, right);
    vec3 rayDir = normalize(forward + uv.x * right + uv.y * up);

    // Ray marching
    float totalDistance = 0.0;
    const int maxSteps = 100;
    const float minDist = 0.001;
    const float maxDist = 10.0;
    vec3 hitPoint;

    for (int i = 0; i < maxSteps; i++) {
        hitPoint = rayOrigin + rayDir * totalDistance;
        float dist = mandelbulbSDF(hitPoint);

        if (dist < minDist) break;
        if (totalDistance > maxDist) break;

        totalDistance += dist;
    }

    // Compute lighting only if we hit the fractal
    vec3 color;
    if (totalDistance < maxDist) {
        vec3 viewDir = normalize(rayOrigin - hitPoint);
        vec3 baseLight = phongLighting(hitPoint, viewDir);
        float shadow = softShadow(hitPoint, normalize(vec3(2.0, 2.0, -2.0)));
        color = baseLight * shadow; // Apply shadows
    } else {
        color = vec3(0.1, 0.1, 0.2); // Background color
    }

    fragColor = vec4(color, 1.0);
}

Depth-based Blending

To create a realistic sense of depth, we can use depth-based blending to gradually fade objects into the fog as they move further away from the camera. This simulates how light scatters in the atmosphere, making distant objects appear less distinct.

In ray marching, we calculate fog intensity using exponential depth functions like:

\[\text{fogAmount} = 1.0 - e^{-\text{distance} \times \text{densityFactor}}\]

where distance is how far along the ray we’ve traveled, and densityFactor controls how quickly objects fade into fog.

By blending our object’s color with the fog color based on this function, we achieve a smooth atmospheric fade effect. Let’s implement it in our shader.

void mainImage(out vec4 fragColor, in vec2 fragCoord) {
    vec2 uv = (fragCoord - 0.5 * iResolution.xy) / iResolution.y;

    // Rotating Camera
    float angle = iTime * 0.5;
    vec3 rayOrigin = vec3(3.0 * cos(angle), 0.0, 3.0 * sin(angle));
    vec3 target = vec3(0.0);
    vec3 forward = normalize(target - rayOrigin);
    vec3 right = normalize(cross(vec3(0, 1, 0), forward));
    vec3 up = cross(forward, right);
    vec3 rayDir = normalize(forward + uv.x * right + uv.y * up);

    // Ray marching
    float totalDistance = 0.0;
    const int maxSteps = 100;
    const float minDist = 0.001;
    const float maxDist = 10.0;
    vec3 hitPoint;

    for (int i = 0; i < maxSteps; i++) {
        hitPoint = rayOrigin + rayDir * totalDistance;
        float dist = mandelbulbSDF(hitPoint);

        if (dist < minDist) break;
        if (totalDistance > maxDist) break;

        totalDistance += dist;
    }

    // Compute lighting only if we hit the fractal
    vec3 color;
    if (totalDistance < maxDist) {
        vec3 viewDir = normalize(rayOrigin - hitPoint);
        vec3 baseLight = phongLighting(hitPoint, viewDir);
        float shadow = softShadow(hitPoint, normalize(vec3(2.0, 2.0, -2.0)));
        color = baseLight * shadow;
    } else {
        color = vec3(0.1, 0.1, 0.2); // Background color
    }

    // Apply depth-based exponential fog
    float fogAmount = 1.0 - exp(-totalDistance * 0.15);  
    color = mix(color, vec3(0.5, 0.6, 0.7), fogAmount);  

    fragColor = vec4(color, 1.0);
}

Once this is running, you should see some fog appear to obscure our Mandelbulb:

Light Scattering

When light passes through a medium like fog, dust, or mist, it doesn’t just stop—it scatters in different directions, creating beautiful effects like god rays or a soft glow around objects. This is known as volumetric light scattering.

In ray marching, we can approximate this effect by tracing secondary rays through the scene and accumulating light contribution along the path. The more dense the medium (or the more surfaces the ray encounters), the stronger the scattering effect. A simplified formula for this accumulation looks like:

\[L = \sum_{i=0}^{n} \text{density}(p_i) \cdot \text{stepSize}\]

where:

  • \(L\) is the total scattered light along the ray.
  • \(\text{density}(p_i)\) measures how much fog or medium is present at each step.
  • \(\text{stepSize}\) controls how frequently we sample along the ray.

By applying this technique, we can simulate light beams filtering through objects, making our Mandelbulb feel immersed in an atmospheric environment.

First we need a function to calcuate our light:

float volumetricLight(vec3 ro, vec3 rd) {
    float density = 0.0;
    float t = 0.1;
    for (int i = 0; i < 50; i++) {
        vec3 pos = ro + rd * t;
        float d = mandelbulbSDF(pos);
        if (d < 0.001) density += 0.02; // Accumulate light scattering
        t += 0.1;
    }
    return density;
}

We also update the mainImage() function to add the light accumuation to the resulting pixel:

// Compute volumetric lighting effect
float lightScattering = volumetricLight(rayOrigin, rayDir);
color += vec3(1.0, 0.8, 0.5) * lightScattering; // Warm glow

You can see the god rays through the centre of our fractal:

With this code we’ve:

  • Shot a secondary ray into the scene which accumulates scattered light
  • The denser the fractal, the more light it scatters
  • density += 0.02 controls the intensity of the god rays

Noise-based Fog

Real-world fog isn’t uniform—it swirls, shifts, and forms dense or sparse patches. To create a more natural effect, we can use procedural noise to simulate rolling mist or dynamic fog layers.

Instead of applying a constant fog density at every point, we introduce random variations using a noise function:

\[\text{fogDensity}(p) = \text{baseDensity} \times \text{noise}(p)\]

where:

  • \(\text{fogDensity}(p)\) determines the fog’s thickness at position \(p\).
  • \(\text{baseDensity}\) is the overall fog intensity.
  • \(\text{noise}(p)\) generates small-scale variations to make fog look natural.

By sampling noise along the ray, we can create wispy, uneven fog that behaves more like mist or smoke, enhancing the realism of our scene. Let’s implement this effect next.

We’ll add procedural noise to simulate smoke or rolling mist.

float noise(vec3 p) {
    return fract(sin(dot(p, vec3(12.9898, 78.233, 45.164))) * 43758.5453);
}

float proceduralFog(vec3 ro, vec3 rd) {
    float fogDensity = 0.0;
    float t = 0.1;
    for (int i = 0; i < 50; i++) {
        vec3 pos = ro + rd * t;
        fogDensity += noise(pos * 0.5) * 0.02;
        t += 0.1;
    }
    return fogDensity;
}

Finally, we blend the noise fog into the final colour inside of the mainImage() function:

// Apply procedural noise fog
float fog = proceduralFog(rayOrigin, rayDir);
color = mix(color, vec3(0.7, 0.8, 1.0), fog);

After these modifications, you should start to see the fog moving as we rotate:

The final version of this shader can be found here.

Conclusion

By adding volumetric effects to our ray-marched Mandelbulb, we’ve taken our scene from a simple fractal to a rich, immersive environment.

These techniques not only enhance the visual depth of our scene but also provide a foundation for more advanced effects like clouds, smoke, fire, or atmospheric light absorption.

Raymarching Reflections

03 Feb 2025

Introduction

Ray tracing is known for producing stunning reflections, we can achieve the same effect using ray marching. In this post, we’ll walk through a classic two-sphere reflective scene, but instead of traditional ray tracing, we’ll ray march our way to stunning reflections.

This post builds on previous articles:

Let’s get started!

Setup

The first step is defining a scene with two spheres and a ground plane. In ray marching, objects are defined using signed distance functions (SDFs). Our scene SDF is just a combination of smaller SDFs.

SDFs

The SDF for a sphere gives us the distance from any point to the surface of the sphere:

float sdfSphere(vec3 p, vec3 center, float radius) {
    return length(p - center) - radius;
}

The SDF for a ground plane:

float sdfGround(vec3 p) {
    return p.y + 1.5;  // Flat ground at y = -1.5
}

Finally, we combine the objects into a scene SDF:

float sceneSDF(vec3 p) {
    float sphere1 = sdfSphere(p, vec3(-1.0, 0.0, 3.0), 1.0);
    float sphere2 = sdfSphere(p, vec3(1.0, 0.0, 3.0), 1.0);
    float ground = sdfGround(p);
    return min(ground, min(sphere1, sphere2));
}

Raymarching

Now we trace a ray through our scene using ray marching.

vec3 rayMarch(vec3 rayOrigin, vec3 rayDir, int maxSteps, float maxDist) {
    float totalDistance = 0.0;
    vec3 hitPoint;

    for (int i = 0; i < maxSteps; i++) {
        hitPoint = rayOrigin + rayDir * totalDistance;
        float dist = sceneSDF(hitPoint);
        if (dist < 0.001) break;  // Close enough to surface
        if (totalDistance > maxDist) return vec3(0.5, 0.7, 1.0); // Sky color
        totalDistance += dist;
    }

    return hitPoint; // Return the hit location
}

Surface Normals

For lighting and reflections, we need surface normals. These are estimated using small offsets in each direction:

vec3 getNormal(vec3 p) {
    vec2 e = vec2(0.001, 0.0);
    return normalize(vec3(
        sceneSDF(p + e.xyy) - sceneSDF(p - e.xyy),
        sceneSDF(p + e.yxy) - sceneSDF(p - e.yxy),
        sceneSDF(p + e.yyx) - sceneSDF(p - e.yyx)
    ));
}

Reflections

Reflections are computed using the reflect function:

\[R = I - 2 (N \cdot I) N\]

where:

  • \(I\) is the incoming ray direction,
  • \(N\) is the surface normal,
  • \(R\) is the reflected ray.

In GLSL, this is done using:

vec3 reflectedDir = reflect(rayDir, getNormal(hitPoint));

Now, we ray march again along the reflected direction:

vec3 computeReflection(vec3 hitPoint, vec3 rayDir) {
    vec3 normal = getNormal(hitPoint);
    vec3 reflectedDir = reflect(rayDir, normal);
    
    vec3 reflectionHit = rayMarch(hitPoint + normal * 0.01, reflectedDir, 50, 10.0);
    return phongLighting(reflectionHit, -reflectedDir);
}

Full Shader

void mainImage(out vec4 fragColor, in vec2 fragCoord) {
    vec2 uv = (fragCoord - 0.5 * iResolution.xy) / iResolution.y;

    // Camera Setup
    vec3 rayOrigin = vec3(0, 0, -5);
    vec3 rayDir = normalize(vec3(uv, 1.0));

    // Perform Ray Marching
    vec3 hitPoint = rayMarch(rayOrigin, rayDir, 100, 10.0);

    // If we hit an object, apply shading
    vec3 color;
    if (hitPoint != vec3(0.5, 0.7, 1.0)) {
        vec3 viewDir = normalize(rayOrigin - hitPoint);
        vec3 baseLight = phongLighting(hitPoint, viewDir);
        vec3 reflection = computeReflection(hitPoint, rayDir);
        color = mix(baseLight, reflection, 0.5); // Blend reflections
    } else {
        color = vec3(0.5, 0.7, 1.0); // Sky color
    }

    fragColor = vec4(color, 1.0);
}

Running this shader, you should see two very reflective spheres reflecting each other.

Conclusion

With just a few functions, we’ve recreated a classic ray tracing scene using ray marching. This technique allows us to:

  • Render reflective surfaces without traditional ray tracing
  • Generate soft shadows using SDF normals
  • Extend the method for refraction and more complex materials