Summary: U.S. Patent No. 8,814,677 (the ‘677 Patent) relates to the Disney video game Epic Mickey, specifically the game mechanic allowing players to manipulate the game world using in-game paint and paint thinner. Epic Mickey followed Mickey Mouse as fights ink-blobs who invaded the Cartoon Wasteland, a place where the forgotten or obscure Disney cartoons live. The game was primarily a 3D platformer. In the game, Mickey wields a paintbrush which can spray paint or paint thinner. Spraying paint in a certain area would cause a hidden object to appear while spraying paint thinner would make the object disappear. The ‘677 Patent describes the method behind this game mechanic. The game causes the objects to appear or disappear based on the spray pattern using two binary space partitioning (BSP) trees. The first BSP determines the physical shape of the object before any paint or thinner is applied. A second BSP identifies the spray pattern. The game merges the two BSPs to create a new version of the object with the applied spray pattern.

Abstract: Techniques are described for providing a painting and thinning mechanic within a computer-generated environment (e.g., in a video game). The painting and thinning mechanic allows geometry within the computer-generated environment to be “painted” or “thinned.” Painting and thinning refers to a mechanic that involves making parts of the virtual environment visibly and collidably transparent (thinning) or visibly and collidably opaque (painting). The painting/thinning mechanic may be achieved using binary space partitioning (BSP) trees.

Illustrative Claim: 1. A computer-implemented method for executing a video game, comprising: receiving an input indicating to apply a liquid paint or a liquid thinner material to a first set of geometry in the video game, wherein the liquid paint or the liquid thinner material is rendered as a capsule held by a game character and wherein the input directs the game character to throw the capsule at the first set of geometry; determining a burst location on the first set of geometry where the capsule impacts the first set of geometry; determining a second set of geometry corresponding to a spreading effect of the liquid paint or the liquid thinner material from the burst location to an area of the first set of geometry, wherein the spreading effect of the liquid paint or the liquid thinner material is determined by a physics engine; merging, by operation of one or more processors, a first binary space partitioning (BSP) tree with a second BSP tree to create a merged BSP tree, wherein the first BSP tree represents the first set of geometry, wherein the second BSP tree represents the second set of geometry, of the liquid paint or the liquid thinner material, wherein one or more elements of geometry represented in the first BSP tree are associated with a respective paint/thinning state, and wherein the merged BSP tree represents a merged set of geometry created from the first and second sets of geometry;updating, based on the spreading effect determined by the physics engine of the liquid paint or the liquid thinner material on the area of the first set of geometry, a paint/thinning state associated with a respective one or more elements of the merged set of geometry in the merged BSP tree; and rendering the respective one or more elements of the merged set of geometry opaque or transparent based on the paint/thinning states of the respective one or more elements in the merged set of geometry.