BDPT

a small renderer that draws a modified Cornell box with bidirectional path tracing (BDPT), right here in the page. it was written to be read, not to be fast - plain TypeScript on the CPU, a few web workers, no GPU, no frameworks. the point is to see why BDPT exists: next to it runs a plain path tracer, and the controls let you switch the lights, turn the balls into mirrors or glass, and look at the individual pieces BDPT builds the image from

the image keeps refining as long as it's on screen. a few things to try:

• make the right ball glass and compare bdpt with path tracing - the caustic on the floor
• switch the lights off one by one - the side panels are small, and small lights are where the two differ the most
• open advanced, pick one (s, t) - more on that below
• download png saves the current image, by default with the settings and stats underneath

the code is on GitHub, the short version of this page is its README

light, paths and averages

a pixel's colour is the light that reaches the camera through it - light that left a lamp, bounced around the room a few times, and ended up in the lens. every such route is a path: lamp → wall → ball → camera. the pixel is the sum over all the possible paths, which is an integral nobody can solve exactly, so we guess: pick paths at random, compute how much light each carries, divide by how likely we were to pick it, average. that's Monte Carlo integration - the average is right on average (unbiased), and the noise goes away as samples pile up, slowly: 4× the samples for half the noise

so the whole game is which paths we pick. picking them in proportion to how much light they carry would be perfect, and every trick below is an attempt to get closer to that…

path tracing

the classic: start at the camera, shoot a ray through the pixel, and at every surface it hits, pick a new direction (by the surface's material - a mirror reflects, a diffuse wall scatters anywhere) and keep going. each bounce multiplies the path's throughput - how much of the light arriving there makes it back to the camera

waiting to hit a lamp by chance would take forever with small lamps, so at every bounce the tracer also picks a random point on a light and shoots a shadow ray at it - if nothing's in the way, that light counts. this is next event estimation (NEE), and it's what makes path tracing usable at all

radiance(cameraRay: Ray, random: Random): Color {
  let ray = cameraRay
  let radiance = Color.BLACK
  let throughput = Color.WHITE
  let countEmitted = true

  // `depth` = bounces so far: light emitted at this hit has bounced `depth` times on its
  // way to the camera, light sampled by NEE here will have bounced `depth + 1` times
  for (let depth = 0; depth <= this.options.maxDepth; depth++) {
    const hit = this.scene.intersect(ray)
    if (!hit) break

    const wo = ray.direction.negated()
    const { material, light } = hit.object

    if (countEmitted && light) {
      radiance = radiance.add(throughput.mul(light.emitted(hit.normal, wo)))
    }

    if (depth === this.options.maxDepth) break

    if (!material.isDelta) {
      radiance = radiance.add(throughput.mul(this.directLight(hit, wo, random)))
    }

    const scattered = material.sample(wo, hit.normal, random, 'radiance')
    if (!scattered || scattered.pdf === 0) break

    const cosine = Math.abs(scattered.direction.dot(hit.normal))
    throughput = throughput.mul(scattered.value).scale(cosine / scattered.pdf)
    countEmitted = scattered.isDelta

    if (depth >= ROULETTE_MIN_DEPTH) {
      const survival = Math.min(throughput.maxComponent(), 0.95)
      if (random.next() >= survival) break
      throughput = throughput.scale(1 / survival)
    }

    ray = Ray.spawn(hit.point, hit.normal, scattered.direction)
  }

  return radiance
}

note countEmitted: a lamp hit by chance only counts straight from the camera or right after a mirror / glass bounce. everywhere else NEE has already counted that light, and counting it twice is the classic path tracer bug

where path tracing gives up

NEE needs a straight, unobstructed line from the surface to the lamp. glass breaks that - light focused by a glass ball onto the floor (a caustic) reaches the floor through the glass, and a shadow ray from the floor just hits the ball. the only way left is the slow one: bounce off the floor, go through the glass, and happen to hit the lamp

bidirectional path tracing

if light is hard to find from the camera, go find the camera from the light. BDPT traces two random paths for every pixel sample - a camera subpath, exactly like the path tracer's, and a light subpath that starts at a random point on a lamp and bounces around the same way. then it connects every vertex of one to every vertex of the other with a shadow ray

each connection is a separate way - a strategy - of building a complete path. a strategy (s, t) takes the first s vertices of the light subpath and the first t of the camera subpath:

• s = 0 - no light vertices: the camera subpath hit a lamp by itself
• s = 1 - one light vertex, freshly picked on a lamp: that's NEE, the path tracer's trick
• t = 1 - one camera vertex, the camera itself: the light subpath is connected straight to the camera - light tracing. the result doesn't land in the pixel being rendered, but wherever that surface point is seen, so it's splatted into the image there
• anything else - the two subpaths joined somewhere in the middle

a path with k bounces has k + 2 vertices, and k + 2 strategies can build it (one fewer here - see the gotchas). the caustic above is easy for light tracing: lamp → glass → glass → floor, then a shadow ray from the floor to the camera

renderSample(x: number, y: number, sink: SampleSink, random: Random): void {
  const { scene } = this
  const { maxDepth, heuristic, only } = this.options
  // a path with `maxDepth` bounces has `maxDepth + 2` vertices, camera and light included
  const cameraPath = generateCameraSubpath(
    scene,
    x + random.next(),
    y + random.next(),
    maxDepth + 2,
    random,
  )
  const lightPath = generateLightSubpath(scene, maxDepth + 1, random)

  let radiance = Color.BLACK
  for (let t = 1; t <= cameraPath.length; t++) {
    for (let s = 0; s <= lightPath.length; s++) {
      const bounces = s + t - 2
      if (bounces < 0 || bounces > maxDepth || (s === 1 && t === 1)) continue
      if (only && (s !== only.s || t !== only.t)) continue

      const contribution = connect(scene, lightPath, cameraPath, s, t, heuristic, random)
      if (!contribution) continue

      const weight = only && !only.weighted ? 1 : contribution.misWeight
      const weighted = contribution.radiance.scale(weight)
      if (contribution.filmPosition) {
        const { x: filmX, y: filmY } = contribution.filmPosition
        sink.addSplat(filmX, filmY, weighted)
      } else {
        radiance = radiance.add(weighted)
      }
    }
  }
  sink.addSample(x, y, radiance)
}

export function connect(
  scene: Scene,
  lightPath: readonly PathVertex[],
  cameraPath: readonly PathVertex[],
  s: number,
  t: number,
  heuristic: MisHeuristic,
  random: Random,
): Contribution | null {
  let lightEnd = s > 0 ? lightPath[s - 1] : null
  let cameraEnd = cameraPath[t - 1]
  let radiance: Color
  let filmPosition: Contribution['filmPosition'] = null

  if (s === 0) {
    radiance = cameraEnd.beta.mul(cameraEnd.emittedToward(cameraPath[t - 2]))
  } else if (t === 1) {
    if (!lightEnd || lightEnd.isDelta) return null
    const toCamera = connectToCamera(scene, lightEnd)
    if (!toCamera) return null
    cameraEnd = toCamera.vertex
    filmPosition = toCamera.filmPosition
    radiance = lightEnd.beta
      .mul(lightEnd.bsdf(cameraEnd))
      .mul(cameraEnd.beta)
      .scale(lightEnd.cosineToward(cameraEnd))
  } else if (s === 1) {
    if (cameraEnd.isDelta) return null
    lightEnd = sampleLightVertex(scene, cameraEnd, random)
    if (!lightEnd) return null
    radiance = cameraEnd.beta
      .mul(cameraEnd.bsdf(lightEnd))
      .mul(lightEnd.beta)
      .scale(cameraEnd.cosineToward(lightEnd))
  } else {
    if (!lightEnd || lightEnd.isDelta || cameraEnd.isDelta) return null
    radiance = lightEnd.beta
      .mul(lightEnd.bsdf(cameraEnd))
      .mul(cameraEnd.bsdf(lightEnd))
      .mul(cameraEnd.beta)
      .scale(geometryTerm(lightEnd, cameraEnd))
  }

  if (radiance.isBlack()) return null
  if (s > 0 && lightEnd && !isVisible(scene, lightEnd, cameraEnd)) return null

  const misPath = buildMisPath(scene, lightPath, cameraPath, s, t, lightEnd, cameraEnd)
  return { radiance, misWeight: misWeight(misPath, s, heuristic), filmPosition }
}

beta is a vertex's throughput so far - for the camera end, how much of the light arriving there reaches the camera; for the light end, how much light got there. a connection multiplies the two, the materials at both ends (bsdf), and the geometry term - how well the two points see each other: the cosines at both ends over the squared distance. mirrors and glass (delta materials, scattering into exactly one direction) can't be connected to: a shadow ray in some random direction is never the direction

multiple importance sampling

so a path can be built by several strategies. add up all of them and every path is counted several times - the image comes out several times too bright. the fix is to weight them: give each strategy a share, the shares of one path summing to 1

any shares that add up to 1 are correct, but some are much less noisy. Veach's multiple importance sampling (MIS) gives each strategy a share by how likely it was to produce that very path - its probability density p:

• balance heuristic - p_s / Σ p_i
• power heuristic - p_s² / Σ p_i², the default - leans even more on the strategy that's best for the given path
• uniform - every usable strategy gets the same share. still correct, just noisy - the closest thing to "MIS off" that doesn't count paths twice

computing every p_i from scratch would be slow and messy. but neighbouring strategies differ in one vertex only - which side generated it - so p_(s+1) / p_s is just (density of that vertex from the light side) / (density from the camera side). each vertex keeps both densities, and the weight is a walk outwards from s multiplying those ratios

export function misWeight(
  vertices: readonly MisVertex[],
  s: number,
  heuristic: MisHeuristic,
): number {
  const n = vertices.length
  let sumOfRatios = 0

  // strategies with more light vertices: s + 1, s + 2, ...
  let ratio = 1
  for (let other = s + 1; other < n; other++) {
    const vertex = vertices[other - 1] // switches from camera side to light side
    ratio *= orNonZero(vertex.pdfFromLight) / orNonZero(vertex.pdfFromCamera)
    if (isUsable(vertices, other)) sumOfRatios += remap(ratio, heuristic)
  }

  // strategies with fewer light vertices: s - 1, s - 2, ... 0
  ratio = 1
  for (let other = s - 1; other >= 0; other--) {
    const vertex = vertices[other] // switches from light side to camera side
    ratio *= orNonZero(vertex.pdfFromCamera) / orNonZero(vertex.pdfFromLight)
    if (isUsable(vertices, other)) sumOfRatios += remap(ratio, heuristic)
  }

  return 1 / (1 + sumOfRatios)
}

function isUsable(vertices: readonly MisVertex[], s: number): boolean {
  const n = vertices.length
  const t = n - s
  if (t < 1 || (s === 1 && t === 1)) return false
  const lightEndIsDelta = s > 0 && vertices[s - 1].isDelta
  return !lightEndIsDelta && !vertices[s].isDelta
}

PBRT does the same walk, but edits the vertices in place and restores them afterwards. here the full path is first copied into a flat list of { pdfFromLight, pdfFromCamera, isDelta } - the few densities around the new connection get filled in there, and the loop above reads like the formula

looking at one strategy

the advanced section of the demo can show a single strategy instead of the full image. weighted shows its share - all the shares together make the image. unweighted shows what it would render on its own: all the light along paths of its length, with its own kind of noise

the pictures below have the top light only, a glass ball on the right and 128 samples per pixel. the full image, for reference:

one bounce

direct light - lamp → surface → camera - can be built three ways. unweighted, all three render the same thing, with very different noise:

• (0, 3) waits for the camera path to hit the lamp - a small lamp means rare hits and lots of noise
• (1, 2) aims at the lamp from every surface - NEE, nearly clean
• (2, 1) lights the surfaces from the lamp's side and splats them onto the image - decent, noisier where the lamp sees the surface at a grazing angle
• the glass ball is black in all three - nothing can connect to it - and so is the lamp: seeing it takes no bounce at all

weighted, MIS hands almost everything to NEE. (0, 3) keeps only what nobody else can do - the lamp's reflection in the glass ball:

three bounces - the caustic

the caustic under the glass ball is lamp → glass → glass → floor → camera. the two glass vertices rule out every connection that touches them, which leaves (0, 5) - bounce off the floor, through the glass, hit the lamp by chance - and (4, 1) - follow the light through the glass to the floor, connect the floor to the camera. weighted, the caustic belongs to (4, 1) almost entirely:

and unweighted, the same caustic as each of the two finds it on its own. the left one is all a path tracer has:

worth trying in the demo: max depth 2 makes the caustic disappear (it needs three bounces), and switching between weighted and unweighted on the same (s, t) shows how much of a strategy MIS actually trusts

where BDPT struggles too

BDPT isn't magic. make both balls mirrors, keep only the top light, and the reflections in the balls get salted with bright pixels that take ages to go away. each is a path camera → mirror → diffuse → mirror → lamp - a caustic thrown by one ball onto a wall or the floor, seen reflected in the other one. the only diffuse vertex sits between two mirrors, and every connection needs a non-delta vertex at both ends - so no connection can build it. what's left is s = 0, hitting the lamp by chance, which is exactly what the path tracer does

these are specular-diffuse-specular (SDS) paths, the classic blind spot of BDPT. two mirror balls make it about as bad as it gets - the reflected caustic is tiny, so finding it by chance is rare. the real fix is a different family of algorithms, photon mapping or vertex merging, which accept a little bias in exchange…

per sample BDPT is still ahead - about 4× fewer bright outliers around the ball. but a BDPT sample costs ~4× the rays of a path tracer's (two subpaths, plus all the connections), so in the same time the path tracer collects several times more samples, and on these paths it can end up looking smoother. the stats under the demo show both counts - a comparison means little without saying whether it's equal samples or equal time

gotchas

things that cost the most time here - or would have, without tests catching them. most of them break nothing visibly: the image just comes out a bit too dark or too bright, which you won't notice without something to compare against

shadow rays: nudge both ends

a ray starting exactly on a surface tends to hit that same surface again, at distance ~0, from rounding errors - so new rays get nudged a tiny bit off their surface first. the usual way is to move the origin along the normal and keep the direction. for a connection between two given points that's wrong: the whole line shifts sideways, so near the far end it passes beside the target point - and when the target is on a ball, half the time that's inside the ball. the shadow ray then hits the ball just before reaching its target, and the light counts as blocked

here it silently cost BDPT ~20% of the direct light on the floating ball, and only showed up as a disagreement with the path tracer, whose shadow rays go the other way (from the surface towards the lamp) and happen to be immune. the fix is to nudge both ends off their surfaces, then aim between the nudged points:

static between(
  from: Vec3,
  fromNormal: Vec3 | null,
  to: Vec3,
  toNormal: Vec3 | null,
): { ray: Ray; distance: number } {
  const origin = nudgeToward(from, fromNormal, to)
  const target = nudgeToward(to, toNormal, from)
  const toTarget = target.sub(origin)
  const distance = toTarget.length()
  return { ray: new Ray(origin, toTarget.scale(1 / distance)), distance }
}

/** moves a surface point off its surface, to the side `toward` is on */
function nudgeToward(point: Vec3, normal: Vec3 | null, toward: Vec3): Vec3 {
  if (!normal) return point
  const side = toward.sub(point).dot(normal) > 0 ? RAY_EPSILON : -RAY_EPSILON
  return point.add(normal.scale(side))
}

MIS must count exactly the strategies you evaluate

(s, t) = (1, 1) - a point picked on a lamp, connected straight to the camera - is never evaluated: it's the camera seeing the lamp, which s = 0 does just as well. but if MIS still counts it as a candidate, the lamps visible in the image get half their weight from a strategy that never runs, and come out at half brightness. same for anything else skipped - a strategy limited by the max depth, a connection to a mirror

splats are averaged over all the light paths

a pixel's own samples are averaged per pixel. light tracing (t = 1) contributions land on random pixels though, so they're divided by the number of light paths traced for the whole image - one per camera sample. with the camera's "importance" normalized over the whole film, that's exactly right, and a pixel that no light path happens to reach this time isn't skewed

max depth must mean the same thing everywhere

comparing two renderers only tells you something if they compute the same thing. path tracing with NEE counts one more bounce than it seems - the shadow ray at the last surface is a bounce too. here maxDepth means max bounces, in both

glass isn't symmetric

refraction squeezes light into a narrower cone entering glass and spreads it out leaving - so radiance carried from the camera side gets scaled by (η_i / η_t)², while importance, carried from the light side, doesn't. getting it wrong changes nothing in this scene: every path through a closed glass ball goes in and back out, and the factors cancel. it would show with e.g. a diffuse object under water - the kind of bug only a unit test of the material itself catches

testing a renderer that's never exactly right

an unbiased renderer is never exactly right, only right on average - so the test can't be "pixel equals value". two things worked:

• a furnace: a closed box where every wall glows with Le and reflects a fraction ρ of what hits it - every point then sees Le / (1 - ρ) in every direction, a number you can check. it catches double-counted light, missing cosines, pdf mix-ups
• BDPT against the path tracer, block by block - not within a fixed tolerance, though: with glass in the scene the path tracer is the noisy one, and any tolerance is either too tight or useless. instead both render in independent batches, and the spread between batches says how noisy each block is - they must agree within 4 standard errors

and then break the code on purpose - make NEE 10% darker - and check the tests notice. the first version of the comparison didn't

debugging a BDPT that's off

every strategy on its own is a complete estimator. render each (s, t) of one path length alone, unweighted, and compare with brute force (no NEE, just bouncing until a lamp is hit) restricted to the same length - they must all agree. the one that doesn't holds the bug. that's how the shadow ray problem above was found: (1, 2) was 20% short on the floating ball while (0, 3) and (2, 1) matched

how the code is organised

• src/math/ - vectors, rays, sampling, an orthonormal basis around a normal
• src/scene/ - spheres and quads, the three materials, area lights, the pinhole camera, and the Cornell box itself
• src/integrators/path-tracer.ts - the baseline
• src/integrators/bdpt/ - subpaths.ts (the random walks), connect.ts (one strategy), mis.ts (weights), path-vertex.ts (what a vertex knows about itself)
• src/film/ - per-pixel averages plus the splats
• src/render/ - the workers: each builds its own copy of the scene, renders bands of rows and sends back plain number arrays. every row has its own random seed per pass, so the image doesn't depend on which worker rendered what
• src/embed/ - the <bdpt-demo> element - a shadow DOM, a plain <form> of controls, the stats

most of it has tests next to it - the furnace and the BDPT vs path tracer comparison in src/integrators/

references

• Eric Veach, Robust Monte Carlo Methods for Light Transport Simulation, PhD thesis, 1997 - ch. 9 is MIS, ch. 10 BDPT
• Matt Pharr, Wenzel Jakob, Greg Humphreys, Physically Based Rendering, 3rd ed., ch. 16.3 - the structure this code follows
• Csaba Kelemen et al., A Simple and Robust Mutation Strategy for the Metropolis Light Transport Algorithm, 2002 - the next step, maybe some day
• path tracing and Cornell box on Wikipedia
• the code: github.com/Paskvil/paskvil-bdpt