ray tracer

I spent last two months following UCSD's computer graphics course at Coursera, and spent the last month completing the final assignment: writing a ray tracer from scratch.

My code can be found here.

This is also my first not-hello-world project of C++.

The project was very fun to do (I've always been interested in computer graphics, it being the combination of CS, physics, and basically the whole world). It also gave me many frustrating late nights...

Coming from a scala background, it took me some time to get used to the memory allocation and management.

For unit test, I used googletest for unit test. This project also proves Xcode can be a pleasant enough IDE even with pure C++ projects.

The current ray tracer is not very efficient, by my calculation it takes several days to render the stanford dragon. I intended to implement some optimization as mentioned by the course, for example, using grids, but was not successful. I have pushed relevant code onto another branch ("cube") and may work on this in the future.

Below are some images rendered by the ray tracer:

A thousand spheres:

A thousand spheres

Cornell box: I used maxdepth=5 for recursive ray tracing. We should be able to get higher image quality if maxdepth is set higher.

Cornell box

Design Pattern #12: Composite Pattern

These are my notes about the book Headfirst Design Patterns.

The last chapter, finally!

MVC

  • Controller: manipulates model; can ask View to change as well (holds reference to both Model and View)
  • Model: keep state & data; tell View the state has changed (does not know View or Controller -- they register as observers)
  • View: update display; tells Controller of user input; request Model for data (holds reference to both Model and Controller)

Design patterns in MVC

  • Model: Observer pattern to keep View and Controller updated; sometimes use Adapter pattern to adapt a model to work with existing views and controllers.
  • Controller: Strategy pattern. Controller is the "Strategy" behavior for the View. Swappable.
  • View: Composite pattern to manage the windows/display.

Definition

  • A set of patterns combined to solve a general problem.

Design Pattern #11: The Proxy Pattern

These are my notes for the book Headfirst Design Patterns.

Example

Monitor gumball machine remotely.

  • Java's RMI:
    • client object --> client helper (proxy, "stub") --> service helper ("skeleton") --> service object
    • RMI: build client helper + service helper
    • steps:
      • make a remote interface: defines available remote methods
      • make a remote implementation (aka remote service)
      • create stub and skeleton using rmic (both proxy and real object use same interface)
      • start rmi registry
      • start remote service
    • client: does a lookup on RMI registry, RMI registry deserialize and return the stub object. (client must have the stub class, although it always uses the remote interface)

Definition

  • Provides a surrogate or placeholder for another object to control access to it. Maybe remote, expensive to create (virtual proxy) or in need of securing.
  • Control and manage access
  • Remote proxy: acts as a local representative to a remote object.
  • Virtual proxy: delegate requests directly to object after it is created.
  • Protection proxy: invocationHandler decides what method to call on actual object.

Design Pattern #10: State Pattern

These are my notes for the book Headfirst Design Patterns.

Example

Gumball machine.

Implementation 101: focus on action

  • Define states: No quarter; Has quarter; Out of gumballs; Gumballs sold

  • Use instance variable to hold state

  final val SOLD_OUT:Int = 0
  final val NO_QUARTER:Int = 1
  final val HAS_QUARTER:Int = 2
  final val SOLD:Int = 3

  var state:Int = SOLD_OUT
  • Define actions: insert quarter; eject quarter, turn crack, dispense

  • For each action, create a method using conditional statements to determine which behavior is appropriate in each state.

  def insertQuarter = state match {
      // go through every state
      case HAS_QUARTER | SOLD_OUT | SOLD => println("can't insert quarter now")
      case NO_QUARTER => {state = HAS_QUARTER;} // change state
  }
  • Not very flexible for adding new states
  • State transitions are not explicit --> buried in if statements.

Implementation 201: focus on state

  • Localize behavior for each state: each state implements its own actions.

  • Define a State interface that contains a method for every action.

abstract class State{
  def insertQuarter:Unit
  def ejectQuarter:Unit
  def turnCrank:Unit
  def dispense:Unit
}
  • Implement a State class for every state.
class NoQuarterState(machine: GumballMachine) extends State{
  // compose with the machine

  def insertQuarter = machine.setState(machine.hasQuarterState) // change machine's state

  def ejectQuarter = println("cannot eject quarter")

  def turnCrank = println("no quarter")

  def dispense = println("no quarter")
}
  • Delegate to the state class in parent object.
class GumballMachine {

  val hasQuarterState = new HasQuarterState(this)

  var state:State = new NoQuarterState(this) // start with no quarter

  def setState(_state: State):Unit = state = _state

  def insertQuarter = state.insertQuarter // delegate

}

Definition

  • Allows an object to alter its behavior when its internal state changes.
  • Similar to strategy pattern:
    • strategy pattern: client specifies the strategy that is composed
    • state pattern: client usually knows very little about internal state

Design Pattern #9: Iterator and Composite Patterns

These are my notes about the book Head First Design Patterns.

Starting example:

Merge two implementation with ArrayList and Array.

case class MenuItem (
                 name:String,
                 description:String,
                 vegetarian:Boolean,
                 price:Double){

}

class DinerMenu{
  // dinermenu use array
  var menuItems:Array[MenuItem] = null
  var numberOfItems = 0

  def addItem(item: MenuItem):Unit = {
    menuItems(numberOfItems) = item
    numberOfItems += 1
  }

  def getMenu = menuItems
}

class PancakeMenu{
  // pancakeMenu use arraylist
  var menuItems:util.ArrayList[MenuItem] = null

  def addItem(item: MenuItem):Unit = menuItems.add(item)

  def getMenu = menuItems
}

We want to iterate two menus together, without specifying the data type.

Solution: use Iterator interface, and define createIterator method on both classes

abstract class Iterator[T]{
  def hasNext:Boolean
  def next:T
}

class DinerMenuIterator(items:Array[MenuItem]) extends Iterator[MenuItem]{
  var i:Int = 0
  def hasNext = i <= items.length
  def next = {
    val menu:MenuItem = items(i)
    i += 1
    menu
  }
}

class PancakeMenuIterator(items:util.ArrayList[MenuItem]) extends Iterator[MenuItem]{
  var i:Int = 0
  def hasNext = i <= items.size()
  def next = {
    val menu:MenuItem = items.get(i)
    i += 1
    menu
  }
}

// add createIterator method:

class DinerMenu{
  // dinermenu use array
  var menuItems:Array[MenuItem] = null
  var numberOfItems = 0

  def addItem(item: MenuItem):Unit = {
    menuItems(numberOfItems) = item
    numberOfItems += 1
  }

  // createIterator replace getMenu
  def createIterator = new DinerMenuIterator(menuItems)
}

class PancakeMenu{
  // pancakeMenu use arraylist
  var menuItems:util.ArrayList[MenuItem] = null

  def addItem(item: MenuItem):Unit = menuItems.add(item)

  def createIterator = new PancakeMenuIterator(menuItems)
}

Now we can use the iterator interface.

class Waitress(pancakeMenu: PancakeMenu, dinerMenu: DinerMenu){

  def printMenu = {
    val pancakeIterator = pancakeMenu.createIterator
    val dinerIterator = dinerMenu.createIterator
    printMenu(pancakeIterator)
    printMenu(dinerIterator)
  }

  def printMenu(iter:Iterator) = {
    while(iter.hasNext){
      println(iter.next)
    }
  }

}

However, we're still bound to two concrete menu classes --> create a common interface for menu:

abstract class Menu{
  def createIterator:Iterator
}

class PancakeMenu extends Menu{
...}

class DinerMenu extends Menu{
...}

class Waitress(menus:Seq[Menu]){

  def printMenu = {
    menus.map(_.createIterator).foreach(printMenu(_))
  }

  def printMenu(iter:Iterator) = {
    while(iter.hasNext){
      println(iter.next)
    }
  }
}

Composite pattern

Now what if we want to have a dessert "sub menu"? i.e menus within menus.

abstract class MenuComponent{
  def isVegetarian:Boolean = false
  def print:Unit
  def getChild(i:Int):MenuComponent = throw new Exception("unsupported")
}

// "Leaf"
class MenuItem(name:String,
                vegetarian:Boolean) extends MenuComponent{
  override def isVegetarian = vegetarian
  def print = println(s"menu item $name")
}

// "Composite"
class Menu(name:String,
            menus:Seq[MenuComponent]) extends MenuComponent{

  // Menu holds MenuComponents --> recursive

  override def getChild(i:Int) = menus(i)

  def print = println(s"menu component $name ${menus.foreach(_.print)}") // print all children

}


class Waitress(menuComponent: MenuComponent){
  def print = menuComponent.print
}

Definition

Iterator:

  • Encapsulate iteration

  • Allow access elements of an aggregate (aka Menu) sequentially without exposing its underlying representation.

  • Also place the task of traversal on the iterator, not on the aggregate

Composite

  • Compose objects into tree structures

  • Treat individual objects and compositions uniformly --> Transparency

  • Class diagram: Component -> Leaf or Composite

    • Composite: holds Components. addComponent, getChild, operation
    • Leaf: operation

Design Principle

  • A class should be given single responsibility --> have only one reason to change. (eg. aggregate and iterate are two different responsibilities)

Others

  • Use a null iterator can be helpful. (always return false for hasNext)
  • Can create an external iterator to iterate through Component, eg, find veggie menuItems.
    • in Scala, can use pattern matching and flatMap
class Menu(menus:Seq[MenuComponent]) extends MenuComponent{
  ...

  def getVeggie :Seq[MenuItem] = menus.flatMap {
    case m: MenuItem => if (m.isVegetarian) Seq(m) else Nil
    case m: Menu => m.getVeggie
  }

}

Design Pattern #8: Template Method Pattern

These are my notes about the book "Headfirst Design Patterns"

Example

Make coffee and tea.

abstract class CaffeineBeverage{
  def prepare: Unit ={
    boilWater
    brew
    pourInCup
    addCondiments
    hook // hook
  }

  def boilWater:Unit = println("boil water")
  def brew:Unit
  def pourInCup:Unit = println("pour in cup")
  def addCondiments:Unit
  def hook:Unit = {} // "hook": for optional part of algorithm
}

class Coffee extends CaffeineBeverage{

  def brew = println("brewing coffee")

  def addCondiments = println("add sugar")
}

class Tea extends CaffeineBeverage{

  def brew = println("brewing tea")

  def addCondiments = println("add lemon")
}

Definition

  • Defines the steps(aka "template") of an algorithm and allow subclass to provide the implementation of one or more steps.
  • Keep algorithm's structure unchanged.
  • Encapsulate algorithms
  • vs Strategy: strategy = encapsulates interchangeable behaviors and use delegation to decide which behavior to use. In strategy, the class that's composed implements the entire algorithm. While in the template pattern, the algorithm is incomplete without subclass' implementation.
  • Great design for creating frameworks.
  • Factory Method pattern is a special case of Template Method Pattern.

Design principle

  • Don't call us, we'll call you.

  • Allow low level components to hook themselves into a system, but the high level components determine when they're needed, and how.

Design Pattern #7: Adapter and Facade Pattern

These are my notes about the book Head First Design Patterns.

Adapter pattern

If it walks like a duck and quacks like a duck, it might be a turkey wrapped in a duck adapter.

bstract class Duck {
  def fly:Unit
  def quack:Unit
}

abstract class Turkey{
  def gobble:Unit
  def fly:Unit
}

class WildTurky extends Turkey{
  def gobble = println("gobble")
  def fly = println("wildturkey fly")
}

class TurkeyAdapter(turkey: Turkey) extends Duck{ // implement the interface of type adapting to,
  // hold a reference to Turkey through constructor: "composed" with adaptee

  def fly = turkey.fly

  def quack = turkey.gobble // translates request from target interface to adaptee interface

}

Facade pattern

Home theater example.

class HomeTheaterFacade( // access to all subsystems
                       Amplifier amp,
                        DvdPlayer dvd,
                        Projector projector,
                        Screen screen
                         ) {

  def watchMovie:Unit = {
    projector.on
    amp.on
    screen.up
    projector.on
    dvd.on
  }
}

Definition

  • Adapters: converts the interface of a class into another interface the clients expect.
  • Compare to decorators: decorators add new behaviors.
  • Facade pattern: provide a unified interface to a set of interfaces in a subsystem. Subsystem still accessible. Decouple client from subsystem.

OO principle

  • The principle of least knowledge -- talk only to your immediate friends.

When design a system, be careful of the number of classes it interacts with. -- don't have a large number of classes coupled together.

We should only invoke methods that belong to

  • the object itself
  • objects passed in as parameter of the method
  • any object the method creates
  • any component of the object
  • DO NOT call method of an object returned by another call

Example:

without the principle:

public float getTemp(){
    Thermometer thermometer = station.getThermometer(); // DON'T: we're using an object returned by another class, we depend on both station and thermometer class
    return thermometer.getTemperature();
}

with the principle:

public float getTemp(){
    return station.getTemperature(); // station is a component of the object, ok to call its method
}

Design Pattern #6: Command Pattern

These are my notes about the book Head First Design Patterns.

Example problem

Home automation remote control: on, off, undo. Supporting extensible commands.

Cook example

  • Customer <--> Client: customer create command object and call setCommand on invoker
  • Order <--> Command
  • Waitress <--> Invoker: can call execute on the command objects.
  • Cook <--> Receiver
class Order(cook:Cook) { // hold reference to the actual "actor"

  def orderUp() : Unit = { // interface that encapsulates the action
    cook.makeBurger // can vary among different command objects
  }

}

Simple remote control with one slot

abstract class Command {
  def execute:Unit
}

class LightOnCommand(light:Light) extends Command{ // command object
  def execute = light.on
}

class RemoteControl{ // invoker
  var slot:Command = null

  def setCommand(cmd:Command):Unit = slot = cmd

  def buttonPressed:Unit = slot.execute
}

object Main{ // client
  def main(args:Array[String]):Unit = {
    val control = new RemoteControl
    control.setCommand(new LightOnCommand(new Light))
    control.buttonPressed
  }
}

Support undo:

Keep track of last command called.

// NOTE: these are NOT gramatically correct

abstract class Command {
  def execute:Unit
  def undo:Unit
}

class LightOnCommand(light:Light) extends Command{ // command object
  def execute = light.on
  def undo = light.off
}

class RemoteControl{ // invoker
  val slots:Seq[Command] = Nil

  var undoCommand:Command = NoCommand

  def setCommand(i:Int, cmd:Command):Unit = slots[i] = cmd

  def buttonPressed(i:Int):Unit = {
    slots(i).execute
    undoCommand = slots(i) // keep track of last command 
  }

  def undo = undoCommand.undo
}

To support a history of undos, keep a stack.

Use a macro command

class MacroCommand(commands:Seq[Command]) extends Command {
  def execute = commands.foreach(_.execute)
}

Definition

  • Encapsulating a request as an object. Decouple the requester of an action from the object that actually performs the action.
  • "Store them, pass them around, and invoke them when you need them"
  • Roles:
    • Client: create a concrete command and set its receiver
    • Invoker: holds a command and call its execute method
    • Receiver: know how to carry out the request
    • Command: provide execute (and undo) method. Bind together a set of actions on a specific receiver.

Others

  • Implementing a NoCommand can be useful (no need to check null any more). aka "null object" (better handled by Option type in scala)
  • More usages:
    • Job queues: have a group of threads sit on end of the queue, retrieve a command object, call its execute method.
    • Logging requests: as we execute commands, we store a history of them on disk (command object supports save method). When a crash occurs, we reload the command objects (reload method of command object) and invoke execute in order. --> can support all-or-nothing transaction.

Design Pattern #5: Singleton Pattern

These are my notes about the book Head First Design Patterns.

Definition:

  • Ensure one and only one object is instantiated for a given class, and provides a global point of access.

  • Example usage: global resources like connection/thread pools

  • For resource intensive objects, can implemented in lazy manner.

Java implementation:

Use a private constructor.

/**
 * Created by jsun on 11/14/2015 AD.
 */
public class Singleton {

    private static Singleton uniqueInstance = null;

    private Singleton(){};

    // NOT THREAD SAFE!
    public static Singleton getInstance() { // others have to call this method to get instance
        if (uniqueInstance == null){
            uniqueInstance = new Singleton();
        }
        return uniqueInstance;
    }

    // other methods below

}

To be thread safe

  • Use synchronized. Expensive (can decrease performance by 100x) and we actually only need to synchronize during the first time.
public static synchronized Singleton getInstance()
  • Create eagerly

JVM will ensure instance created before any thread access.

public class Singleton {

    private static Singleton uniqueInstance = new Singleton();

    private Singleton(){};

    public static Singleton getInstance() {
        return uniqueInstance;
    }

}
  • Double checked locking: only synchronize if instance is not created yet.
public class Singleton {

    private volatile static Singleton uniqueInstance = new Singleton();

    private Singleton(){};

    public static Singleton getInstance() {

        if (uniqueInstance == null){
            synchronized (Singleton.class){
                if (uniqueInstance == null){ // check again
                    uniqueInstance = new Singleton();
                }
            }
        }
        return uniqueInstance;
    }

}

Scala:

  • Scala has native support for singleton: Object.

Design Pattern #4: Factory Pattern

Example problem: pizza shop

  // this code will need to change if pizza types change in the future
  // i.e not "closed for modification"

  def orderPizza(pizzaType:String):Pizza = { // Pizza is a trait or abstract class
    val pizza = pizzaType match {
      case "cheese" => new CheesePizza
      case "greek" => new GreekPizza
      case "pepperoni" => new PepperoniPizza
    }

    pizza.prepare()
    pizza.bake()
    pizza.cut()
    pizza.box()

    pizza

"Simple Factory Pattern"

  • Use an object to handle object creation.
  • One implementation with no subclassing.
class SimplePizzaFactory{

  def createPizza(pizzaType:String):Pizza =
    pizzaType match {
      case "cheese" => new CheesePizza
      case "greek" => new GreekPizza
      case "pepperoni" => new PepperoniPizza
    }
}

// we pass factory in constructor
class PizzaShop(factory: SimplePizzaFactory) {

  def orderPizza(pizzaType:String):Pizza = {

    val pizza = factory.createPizza(pizzaType)

    pizza.prepare()
    pizza.bake()
    pizza.cut()
    pizza.box()

    pizza

  }
}

The Good:

  • Object creation is now encapsulated.
  • Multiple instances can share one same factory.

What if we need multiple factories?

val nyPizzaFactory = new NYPizzaFactory // extends SimplePizzaFactory
val nyPizzaStore = new PizzaShop(nyPizzaFactory)

val chicagoPizzaFactory = new ChicagoPizzaFactory
val chicagoPizzaStore = new PizzaShop(chicagoPizzaStore)

hmm...

Factory Method Pattern

/**
 * Created by jsun on 11/10/2015 AD.
 */

abstract class Pizza{
  def prepare:Unit
  def bake:Unit
  def cut:Unit
  def box:Unit
}

// we pass factory in constructor
abstract class PizzaShop {

  def createPizza(pizzaType:String):Pizza // subclass must implement this "factory method"

  def orderPizza(pizzaType:String):Pizza = {

    val pizza = createPizza(pizzaType)

    // the rest procedures are localized and will be consistent

    pizza.prepare
    pizza.bake
    pizza.cut
    pizza.box

    pizza

  }
}


class NYPizzaShop extends PizzaShop{
  def createPizza(pizzaType:String) = new NYPizza
}
  • Defer object creation to subclass
  • Can localize other procedures (eg. prepare, bake, cut, box)
  • Creator class (PizzaShop) + Product class (Pizza). "Parallel classes"
  • However, creating one product only.

Now what if you have different families of pizza ingredients?

Abstract Factory Pattern

// "abstract factory"
abstract class PizzaIngredientFactory{
  def createDough:Dough // "Factory Methods"
  def createSauce:Sauce
  // will need to change interface if new ingredients are being added
}

// concrete factory
class NYIngredientFactory extends PizzaIngredientFactory{
  def createDough = new ThinCrustDough
  def createSauce = new MarinaraSauce
}


abstract class Pizza{
  var dough:Dough
  var sauce:Sauce

  def prepare:Unit
  def bake:Unit
  def cut:Unit
  def box:Unit
}

// use concrete factories through composition
class CheesePizza(ingredientFactory: PizzaIngredientFactory) extends Pizza{

  dough = ingredientFactory.createDough
  sauce = ingredientFactory.createSauce

}

class NYPizzaShop extends PizzaShop{

  def createPizza(pizzaType:String) = {
    val ingredientFactory = new NYIngredientFactory
    pizzaType match {
      case "cheese" => new CheesePizza(ingredientFactory)
    }
  }
}
  • For multiple families of object
  • Definition: create families of related or dependent objects (pizza ingredients here) without specifying their concrete classes.

Design Principle (Dependency Inversion Principle)

  • Depend upon abstractions. Do not depend upon concrete classes.

  • No variables should hold a reference to a concrete class. (eg. using new)

  • No class should derive from a concrete class.

  • No method should override an implemented method of any of its base classes.

Reference