Ray Tracer

README.md

Ray Tracing

Introduction

Ray Tracing is the Computer Science behind modern computer graphics in movies.

The Ray Tracing algorithm attempts to produce highly realistic images by using the principles of Geometric Optics.

ToDo

1. Operator overloading for the Vector class.
2. Complete inline documentation.
3. Performance analysis.

Credits

Microsoft produced the original ray tracing program as a demonstration of the TypeScript language.

The program has been refactored into multiple modules.

Camera.ts

import { cross } from './gibbs'
import { Vector } from './Vector'

/**
 * A reference frame consiting of three orthonormal vectors.
 * The camera also has a position property.
 * The down direction is assumed to be -e2.
 */
export class Camera {
    /**
     * Unit vector for the direction in which the camera is pointing.
     */
    forward: Vector

    /**
     *
     */
    right: Vector

    /**
     * The up direction of the camera (unit vector).
     * This is not the same as -down!
     */
    up: Vector

    /**
     * 
     */
    constructor(public pos: Vector, lookAt: Vector) {
        const down = new Vector(0.0, -1.0, 0.0)
        this.forward = Vector.norm(Vector.minus(lookAt, this.pos))
        // This looks more like 'left' to me.
        this.right = Vector.times(1.5, Vector.norm(cross(this.forward, down)))
        // This will be up
        this.up = Vector.times(1.5, Vector.norm(cross(this.forward, this.right)))
    }
}

Color.ts

export class Color {

    constructor(public r: number, public g: number, public b: number) {
    }

    static scale(k: number, v: Color): Color {
        return new Color(k * v.r, k * v.g, k * v.b)
    }

    static plus(v1: Color, v2: Color): Color {
        return new Color(v1.r + v2.r, v1.g + v2.g, v1.b + v2.b)
    }

    static times(v1: Color, v2: Color): Color {
        return new Color(v1.r * v2.r, v1.g * v2.g, v1.b * v2.b)
    }

    static white = new Color(1.0, 1.0, 1.0)
    static grey = new Color(0.5, 0.5, 0.5)
    static black = new Color(0.0, 0.0, 0.0)
    static background = Color.black
    static defaultColor = Color.black

    static toDrawingColor(c: Color) {
        const legalize = (d: number) => d > 1 ? 1 : d
        return {
            r: Math.floor(legalize(c.r) * 255),
            g: Math.floor(legalize(c.g) * 255),
            b: Math.floor(legalize(c.b) * 255)
        }
    }
}

defaultScene.ts

import { Camera } from './Camera'
import { Color } from './Color'
import { Plane } from './Plane'
import { Scene } from './Scene'
import { Sphere } from './Sphere'
import { Vector } from './Vector'
import { checkerboard, shiny } from './Surface'

export function defaultScene(): Scene {
    return {
        things: [
            new Plane(new Vector(0.0, 1.0, 0.0), 0.0, checkerboard),
            new Sphere(new Vector(0.0, 1.0, -0.25), 1.0, shiny),
            new Sphere(new Vector(-1.0, 0.5, 1.5), 0.5, shiny)
        ],
        lights: [
            {
                // A mostly red light (now dimmed out).
                pos: new Vector(-2.0, 2.5, 0.0),
                color: new Color(0.00, 0.00, 0.00)
            },
            {
                // A mostly blue light.
                pos: new Vector(1.5, 2.5, 1.5),
                color: new Color(0.07, 0.07, 0.49)
            },
            {
                // A mostly green light
                pos: new Vector(1.5, 2.5, -1.5),
                color: new Color(0.07, 0.49, 0.07)
            },
            {
                // A light blue light.
                pos: new Vector(0.0, 3.5, 0.0),
                color: new Color(0.21, 0.21, 0.35)
            }
        ],
        camera: new Camera(new Vector(3.0, 2.0, 4.0), new Vector(-1.0, 0.5, 0.0))
    }
}

extend.ts

/*
 * Helper function for extending the properties on objects.
 */
export function extend<T>(destination: T, source: any): T {
    for (const property in source) {
        if (source.hasOwnProperty(property)) {
            destination[property] = source[property]
        }
    }
    return destination
}

gibbs.spec.ts

import { Vector } from './Vector'
import { cross } from './gibbs'

const i = new Vector(1, 0, 0)
const j = new Vector(0, 1, 0)
const k = new Vector(0, 0, 1)

export default function() {
    describe("cross", function() {
        describe("(i, j)", function() {
            it("should be k", function() {
                expect(cross(i, j).x).toBe(k.x)
                expect(cross(i, j).y).toBe(k.y)
                expect(cross(i, j).z).toBe(k.z)
            })
        })
        describe("(j, k)", function() {
            it("should be i", function() {
                expect(cross(j, k).x).toBe(i.x)
                expect(cross(j, k).y).toBe(i.y)
                expect(cross(j, k).z).toBe(i.z)
            })
        })
        describe("(k, i)", function() {
            it("should be j", function() {
                expect(cross(k, i).x).toBe(j.x)
                expect(cross(k, i).y).toBe(j.y)
                expect(cross(k, i).z).toBe(j.z)
            })
        })
    })
}

gibbs.ts

import { Vector } from './Vector.js'

/**
 * The vector 'cross' product in Euclidean 3D space.
 */
export function cross(v1: Vector, v2: Vector): Vector {
    const x = v1.y * v2.z - v1.z * v2.y
    const y = v1.z * v2.x - v1.x * v2.z
    const z = v1.x * v2.y - v1.y * v2.x
    return new Vector(x, y, z)
}

index.html

<!doctype html>
<html>

<head>
    <base href='/'>
    <title>Vector graphics with canvas</title>
    <script src='https://jspm.io/system@0.19.34.js'></script>
    <link rel='stylesheet' href='style.css'>
</head>

<body>
    <script>
        System.defaultJSExtensions = true
        System.import('./script')

    </script>
</body>

</html>

Intersection.ts

import { Ray } from './Ray'
import { Thing } from './Thing'

/**
 * 
 */
export interface Intersection {
    /**
     * The thing for which the intersection has been computed.
     */
    thing: Thing
    ray: Ray
    dist: number
}

Light.ts

import { Color } from './Color'
import { Vector } from './Vector'

/**
 * A point light at a position and with a color.
 */
export interface Light {
    /**
     * The position vector.
     */
    pos: Vector
    /**
     * The colro of the light.
     */
    color: Color
}

package.json

{
    "description": "Ray Tracer",
    "dependencies": {
        "DomReady": "1.0.0",
        "jasmine": "3.4.0"
    },
    "operatorOverloading": false,
    "name": "ray-tracer",
    "version": "0.1.0",
    "author": "David Geo Holmes",
    "keywords": [
        "Graphics",
        "Ray Tracing",
        "mathdoodle"
    ],
    "linting": true,
    "noLoopCheck": true,
    "hideConfigFiles": true
}

Plane.ts

import { Ray } from './Ray'
import { Surface } from './Surface'
import { Thing } from './Thing'
import { Vector } from './Vector'
import { Intersection } from './Intersection'

/**
 * The scalar product of two vectors.
 */
const dot: (v1: Vector, v2: Vector) => number = Vector.dot

export class Plane implements Thing {

    private n: Vector

    /**
     * 
     */
    private offset: number

    /**
     * 
     */
    constructor(normal: Vector, offset: number, public surface: Surface) {
        this.n = normal
        this.offset = offset
    }

    /**
     *
     */
    intersect(ray: Ray): Intersection | null {
        /**
         * The ray direction (unit vector).
         */
        const r: Vector = ray.dir
        /**
         * The starting point of the ray (position vector).
         */
        // const s: Vector = ray.start
        /**
         * The normal to the plane (unit vector).
         */
        const n: Vector = this.n
        //
        // Let d be vector from origin to plane, d = offset * n.
        // Let w be vector from d to X, the intersection point.
        // w is perpendicular to d.
        //
        // X = d + w        (Eqn.1) (vector equation)
        // X = s + μ * r    (Eqn.2) (vector equation)
        // dot(w,d) = 0     (Eqn.3) (scalar equation)
        //
        // This system of 7 equations has the unknowns X, w, and μ (7 unknowns).
        //
        // We solve to find μ, needed for the intersection information.

        // TODO: This doesn't look right.
        // Imagine a ray travelling towards the plane from the other side from the origin.
        const denom = dot(n, r)
        if (denom > 0) {
            return null
        }
        else {
            const μ = (dot(n, ray.start) + this.offset) / (-denom)
            return { thing: this, ray: ray, dist: μ }
        }
    }

    /**
     * The normal to a plane at any point is simply the constant normal.
     */
    normal(/*pos: Vector*/): Vector {
        return this.n
    }
}

Ray.ts

import { Vector } from './Vector'

/**
 *
 */
export interface Ray {

    /**
     * The starting position of the ray.
     */
    start: Vector

    /**
     * The direction of the ray.
     */
    dir: Vector
}

RayTracer.ts

import { Camera } from './Camera'
import { Color } from './Color'
import { Intersection } from './Intersection'
import { Light } from './Light'
import { Ray } from './Ray'
import { Scene } from './Scene'
import { Thing } from './Thing'
import { Vector } from './Vector'

/**
 * Computes the closest intersection of a ray with all things in the scene.
 * Returns undefined if the ray does not intersect.
 */
function intersections(ray: Ray, scene: Scene): Intersection | undefined {
    let closest = +Infinity
    let closestInter: Intersection | undefined = undefined
    for (const thing of scene.things) {
        const inter = thing.intersect(ray)
        if (inter !== null && inter.dist < closest) {
            closestInter = inter
            closest = inter.dist
        }
    }
    return closestInter
}

/**
 * Returns the distance to the nearest intersecting thing, or undefined
 * if the ray does not intersect an object in the scene.
 */
function testRay(ray: Ray, scene: Scene): number | undefined {
    const isect = intersections(ray, scene)
    if (typeof isect !== 'undefined') {
        return isect.dist
    }
    else {
        return undefined
    }
}

export class RayTracer {

    private maxDepth = 5

    private traceRay(ray: Ray, scene: Scene, depth: number): Color {
        const isect = intersections(ray, scene)
        if (isect === undefined) {
            return Color.background
        }
        else {
            return this.shade(isect, scene, depth)
        }
    }

    private shade(isect: Intersection, scene: Scene, depth: number) {
        const d = isect.ray.dir
        const pos = Vector.plus(Vector.times(isect.dist, d), isect.ray.start)
        const normal = isect.thing.normal(pos)
        const reflectDir = Vector.minus(d, Vector.times(2, Vector.times(Vector.dot(normal, d), normal)))
        const naturalColor = Color.plus(Color.background,
            this.getNaturalColor(isect.thing, pos, normal, reflectDir, scene))
        const reflectedColor = (depth >= this.maxDepth) ? Color.grey : this.getReflectionColor(isect.thing, pos, normal, reflectDir, scene, depth)
        return Color.plus(naturalColor, reflectedColor)
    }

    private getReflectionColor(thing: Thing, pos: Vector, normal: Vector, rd: Vector, scene: Scene, depth: number) {
        normal = normal
        return Color.scale(thing.surface.reflect(pos), this.traceRay({ start: pos, dir: rd }, scene, depth + 1))
    }

    private getNaturalColor(thing: Thing, pos: Vector, norm: Vector, rd: Vector, scene: Scene) {
        const addLight = (col: Color, light: Light) => {
            const ldis = Vector.minus(light.pos, pos)
            const livec = Vector.norm(ldis)
            const neatIsect = testRay({ start: pos, dir: livec }, scene)
            const isInShadow = (neatIsect === undefined) ? false : (neatIsect <= Vector.mag(ldis))
            if (isInShadow) {
                return col
            }
            else {
                const illum = Vector.dot(livec, norm)
                const lcolor = (illum > 0) ? Color.scale(illum, light.color) : Color.defaultColor
                const specular = Vector.dot(livec, Vector.norm(rd))
                const scolor = (specular > 0) ? Color.scale(Math.pow(specular, thing.surface.roughness), light.color) : Color.defaultColor
                return Color.plus(col, Color.plus(Color.times(thing.surface.diffuse(pos), lcolor), Color.times(thing.surface.specular(pos), scolor)))
            }
        }
        return scene.lights.reduce(addLight, Color.defaultColor)
    }

    /**
     * Renders the scene to the HTML5 canvas 2D context.
     */
    render(scene: Scene, ctx: CanvasRenderingContext2D, screenWidth: number, screenHeight: number) {
        /**
         * Maybe not very well named. I think this is computing the unit vector direction of the ray?
         */
        const getPoint = (x: number, y: number, camera: Camera): Vector => {
            const recenterX = (xInner: number) => (xInner - (screenWidth / 2.0)) / 2.0 / screenWidth
            const recenterY = (yInner: number) => -(yInner - (screenHeight / 2.0)) / 2.0 / screenHeight
            const right = Vector.times(recenterX(x), camera.right)
            const up = Vector.times(recenterY(y), camera.up)
            return Vector.norm(Vector.plus(camera.forward, Vector.plus(right, up)))
        }
        // Compute the color of every pixel by tracing a ray backwards
        for (let y = 0; y < screenHeight; y++) {
            for (let x = 0; x < screenWidth; x++) {
                const color = this.traceRay({ start: scene.camera.pos, dir: getPoint(x, y, scene.camera) }, scene, 0)
                const c = Color.toDrawingColor(color)
                ctx.fillStyle = "rgb(" + String(c.r) + ", " + String(c.g) + ", " + String(c.b) + ")"
                ctx.fillRect(x, y, x + 1, y + 1)
            }
        }
    }

}

Scene.ts

import { Thing } from './Thing'
import { Light } from './Light'
import { Camera } from './Camera'

export interface Scene {
    things: Thing[]
    lights: Light[]
    camera: Camera
}

script.ts

import { defaultScene } from './defaultScene'
import { RayTracer } from './RayTracer'

DomReady.ready(runMe)

function runMe() {
    const canvas = document.createElement("canvas")
    canvas.width = 400
    canvas.height = 400
    document.body.appendChild(canvas)
    const ctx = canvas.getContext("2d")
    if (ctx) {
        const rayTracer = new RayTracer()
        return rayTracer.render(defaultScene(), ctx, canvas.width, canvas.height)
    }
}

Sphere.ts

import { Intersection } from './Intersection'
import { Ray } from './Ray'
import { Surface } from './Surface'
import { Thing } from './Thing'
import { Vector } from './Vector'

export class Sphere implements Thing {

    private radius2: number

    constructor(public center: Vector, radius: number, public surface: Surface) {
        this.radius2 = radius * radius
    }

    normal(pos: Vector): Vector {
        return Vector.norm(Vector.minus(pos, this.center))
    }

    intersect(ray: Ray): Intersection | null {
        const e = Vector.minus(this.center, ray.start)
        const β = Vector.dot(e, ray.dir)
        let μ = 0
        if (β >= 0) {
            const ε = this.radius2 - (Vector.dot(e, e) - β * β)
            if (ε >= 0) {
                μ = β - Math.sqrt(ε)
            }
        }
        if (μ === 0) {
            return null
        }
        else {
            return { thing: this, ray: ray, dist: μ }
        }
    }
}

style.css

body {
    background: blue;
}

canvas {
    position: absolute;
    width: 400px;
    height: 400px;
    top: 20px;
    left: 20px;
}

Surface.ts

import { Color } from './Color'
import { Vector } from './Vector'

export interface Surface {
    diffuse: (pos: Vector) => Color
    specular: (pos: Vector) => Color
    reflect: (pos: Vector) => number
    roughness: number
}

export const shiny: Surface = {
    diffuse: function() { return Color.white },
    specular: function() { return Color.grey },
    reflect: function() { return 0.7 },
    roughness: 250
}

export const checkerboard: Surface = {
    diffuse: function(pos) {
        if ((Math.floor(pos.z) + Math.floor(pos.x)) % 2 !== 0) {
            return Color.white
        } else {
            return Color.black
        }
    },
    specular: function() { return Color.white },
    reflect: function(pos) {
        if ((Math.floor(pos.z) + Math.floor(pos.x)) % 2 !== 0) {
            return 0.1
        } else {
            return 0.7
        }
    },
    roughness: 150
}

tests.html

<!DOCTYPE html>
<html>
  <head>
    <base href='/'>
    <!-- STYLES-MARKER -->
    <style>
    /* STYLE-MARKER */
    </style>
    <!-- SYSTEM-SHIM-MARKER -->
    <!-- SCRIPTS-MARKER -->
  </head>
  <body>
    <script>
    // CODE-MARKER
    </script>
    <script>
    System.defaultJSExtensions = true
    System.import('./tests.js')
    </script>
  </body>
</html>

tests.ts

import { extend } from './extend'
import gibbs from './gibbs.spec'
import Vector from './Vector.spec'

(<any> window)['jasmine'] = jasmineRequire.core(jasmineRequire)

jasmineRequire.html((<any> window)['jasmine'])

const env = jasmine.getEnv()

const jasmineInterface = jasmineRequire.interface((<any> window)['jasmine'], env)

extend(window, jasmineInterface)

const htmlReporter = new jasmine.HtmlReporter({
    env: env,
    getContainer: function() { return document.body },
    createElement: function() { return document.createElement.apply(document, arguments) },
    createTextNode: function() { return document.createTextNode.apply(document, arguments) },
    timer: new jasmine.Timer()
})

env.addReporter(jasmineInterface.jsApiReporter)
env.addReporter(htmlReporter)

DomReady.ready(function() {
    htmlReporter.initialize()
    describe("Vector", Vector)
    describe("gibbs", gibbs)
    env.execute()
})

Thing.ts

import { Intersection } from './Intersection'
import { Ray } from './Ray'
import { Surface } from './Surface'
import { Vector } from './Vector'

/**
 * A combination of the geometry of an object and its surface properties.
 */
export interface Thing {
    /**
     * 
     */
    intersect(ray: Ray): Intersection | null
    /**
     *
     */
    normal: (pos: Vector) => Vector
    /**
     *
     */
    surface: Surface
}

tsconfig.json

{
    "allowJs": true,
    "declaration": true,
    "emitDecoratorMetadata": true,
    "experimentalDecorators": true,
    "jsx": "react",
    "module": "system",
    "noImplicitAny": true,
    "noImplicitReturns": true,
    "noImplicitThis": true,
    "noUnusedLocals": true,
    "noUnusedParameters": true,
    "operatorOverloading": true,
    "preserveConstEnums": true,
    "removeComments": false,
    "sourceMap": true,
    "strictNullChecks": true,
    "suppressImplicitAnyIndexErrors": true,
    "target": "es5",
    "traceResolution": true
}

tslint.json

{
    "rules": {
        "array-type": [
            true,
            "array"
        ],
        "curly": false,
        "comment-format": [
            true,
            "check-space"
        ],
        "eofline": true,
        "forin": true,
        "jsdoc-format": true,
        "no-conditional-assignment": false,
        "no-consecutive-blank-lines": true,
        "no-construct": true,
        "no-for-in-array": true,
        "no-magic-numbers": false,
        "no-shadowed-variable": true,
        "no-string-throw": true,
        "no-trailing-whitespace": [
            true,
            "ignore-jsdoc"
        ],
        "no-var-keyword": true,
        "one-variable-per-declaration": [
            true,
            "ignore-for-loop"
        ],
        "prefer-const": true,
        "prefer-for-of": true,
        "prefer-function-over-method": false,
        "radix": true,
        "semicolon": [
            true,
            "never"
        ],
        "trailing-comma": [
            true,
            {
                "multiline": "never",
                "singleline": "never"
            }
        ],
        "triple-equals": true,
        "use-isnan": true
    }
}

Vector.spec.ts

import { Vector } from './Vector'

export default function() {
    describe("constructor", function() {
        const v = new Vector(1, 2, 3)
        it("should initialize x, y, z properties", function() {
            expect(v.x).toBe(1)
            expect(v.y).toBe(2)
            expect(v.z).toBe(3)
        })
    })
}

Vector.ts

/**
 * A representation of a vector in Euclidean 3D space
 * with cartesian coordinates. The basis is implicitly
 * the standard basis, [e1, e2, e3], such that
 * 
 * new Vector(x, y, z) => x * e1 + y * e2 + z * e3.
 */
export class Vector {

    constructor(public x: number, public y: number, public z: number) { }

    static times(k: number, v: Vector) {
        return new Vector(k * v.x, k * v.y, k * v.z)
    }

    static minus(v1: Vector, v2: Vector) {
        return new Vector(v1.x - v2.x, v1.y - v2.y, v1.z - v2.z)
    }

    static plus(v1: Vector, v2: Vector) {
        return new Vector(v1.x + v2.x, v1.y + v2.y, v1.z + v2.z)
    }

    static dot(v1: Vector, v2: Vector): number {
        return v1.x * v2.x + v1.y * v2.y + v1.z * v2.z
    }

    static mag(v: Vector): number {
        return Math.sqrt(v.x * v.x + v.y * v.y + v.z * v.z)
    }

    static norm(v: Vector): Vector {
        const mag = Vector.mag(v)
        const div = (mag === 0) ? Infinity : 1.0 / mag
        return Vector.times(div, v)
    }
}