Bad Apple But It's Suzanne

Recreation of the Bad Apple music video with raytraced Suzanne the Blender Monkey

Goals

Global Objective

For each frame, over all white pixels with monkeys and leave black pixels uncovered.

Constraint

Keep monkeys within the camera frustum.

Save monkeys between frames to prevent strobing.

Algorithm

I originally tried a complete ADMM with random initialization which was able to optimize the first frame but got stuck in a local minimum immediately after. Shortly after, I moved to a greedy approach that leverages knowledge of the entire space. The cost function contains a small regularizer that encourages monkeys to not cover each other.

For each frame
    // phase 1 - greedily prune existing shapes
    For each shape from previous frame largest to smallest
        Add shape to this frame
        Reset penalty and lambda for shape
        Repeat n times
              Augmented Lagrangian ADAM step
              Armijo style line search, break if we are rejected
        Remove the shape if it increased the cost

    // phase 2 - greedily add new shapes
    Find clusters of uncovered pixels using BFS
    For each cluster centroid
        Add shape on cluster with raycast
        Repeat n times
              Augmented Lagrangian ADAM step
              Armijo style line search, break if we are rejected
        Remove the shape if it increased the cost
        Full block coordinate descent step

Reasoning

Shapes were optimized individually since the global solution did not care about which shapes covered what white pixels, only that they were covered. I found that optimizing one shape at a time instead of block coordinate descent worked better. From the perspective of a single shape, using a block coordinate descent can drastically change the cost function between iterations. Fixing all other shapes while we optimize over many iterations worked better for algorithms like L-BFGS or ADAM which rely on history.

Sorting shapes from largest to smallest preserves larger more recognizable objects.

I reset the penalty and lambda each frame since the cost function drastically changes.

I was originally planning on using L-BFGS for stepping but went with ADAM since I was worried about the curvature history becoming stale with changing lagrangians. ADAM seemed like a better choice over Gauss-Newton or LM since the curvature was incredibly chaotic.

The block coordinate step at the end allows shapes to make slight movements to fill in small holes left behind.