U.S. Pat. No. 8,814,677

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Embodiments of the present invention are directed to techniques for providing a painting and thinning mechanic within a computer-generated environment. For purposes of illustration, embodiments of the present invention are described in the context of a video game; however, more generally the invention may be embodied in any computer simulation environment, such as professional flight training simulators, architectural design applications, etc. The painting and thinning mechanic allows geometry within the computer-generated environment to be “painted” or “thinned.” More specifically, painting and thinning refers to a game mechanic that involves making parts of the game world visibly and collidably transparent (thinning) or visibly and collidably opaque (painting). Users may interact directly with the results of a painting or thinning operation, e.g., thinned sections of the world could be passed through, while painted sections could be hung on, landed on, traversed, etc. An in-game character could access units of a “painting” or “thinning” substance and throw, launch or otherwise release it into the computer-generated environment, resulting in the paint (or thinner) material intersecting with elements of the world geometry.

In one embodiment, this mechanic may be achieved using binary space partitioning (BSP) trees. As described in greater detail below, the intersection of paint or thinner with the world geometry may result in changes to a painted or thinned state associated with elements of that geometry. Specifically, changes to a painted or thinned state of faces (in two-dimensions) or volumes (in three dimensions) in geometry representing the gaming environment may be determined by merging a BSP tree representing the world geometry and a BSP tree representing the paint (or thinner) material. The particular change to a state of a given face (or volume) may be determined using an algebra describing the results of intersecting paint (or thinner) with an element of world geometry having a painted or thinned state.

Additionally, in one embodiment, the BSP trees generated to determine changes in the painting of thinned state of world geometry may be transformed into a collection of geometry (e.g., a collection of vertices) suitable for rendering by a graphics processing unit (GPU).

In the following, reference is made to embodiments of the invention. However, it should be understood that the invention is not limited to specific described embodiments. Instead, any combination of the following features and elements, whether related to different embodiments or not, is contemplated to implement and practice the invention. Furthermore, although embodiments of the invention may achieve advantages over other possible solutions and/or over the prior art, whether or not a particular advantage is achieved by a given embodiment is not limiting of the invention. Thus, the following aspects, features, embodiments and advantages are merely illustrative and are not considered elements or limitations of the appended claims except where explicitly recited in a claim(s). Likewise, reference to “the invention” shall not be construed as a generalization of any inventive subject matter disclosed herein and shall not be considered to be an element or limitation of the appended claims except where explicitly recited in a claim(s).

As will be appreciated by one skilled in the art, aspects of the present invention may be embodied as a system, method or computer program product. Accordingly, aspects of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “circuit,” “module” or “system.” Furthermore, aspects of the present invention may take the form of a computer program product embodied in one or more computer readable medium(s) having computer readable program code embodied thereon.

Any combination of one or more computer readable medium(s) may be utilized. The computer readable medium may be a computer readable signal medium or a computer readable storage medium. A computer readable storage medium may be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of the computer readable storage medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer readable storage medium may be any tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus or device.

A computer readable signal medium may include a propagated data signal with computer readable program code embodied therein, for example, in baseband or as part of a carrier wave. Such a propagated signal may take any of a variety of forms, including, but not limited to, electro-magnetic, optical, or any suitable combination thereof. A computer readable signal medium may be any computer readable medium that is not a computer readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with an instruction execution system, apparatus, or device.

Program code embodied on a computer readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, RF, etc., or any suitable combination of the foregoing.

Computer program code for carrying out operations for aspects of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language such as Java, Smalltalk, C++ or the like and conventional procedural programming languages, such as the “C” programming language or similar programming languages. The program code may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider).

Aspects of the present invention are described below with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

These computer program instructions may also be stored in a computer readable medium that can direct a computer, other programmable data processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks.

The computer program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus or other devices to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

The flowchart and block diagrams in the Figures illustrate the architecture, functionality and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts, or combinations of special purpose hardware and computer instructions.

Referring now toFIG. 1, a block diagram illustrates a client-server view of a computing environment100, according to one embodiment of the invention. As shown, computing environment100includes client computers120, a network160and a server system140. In one embodiment, the environment100may include existing computer systems, e.g., desktop computers, server computers, laptop computers, tablet computers, gaming platforms and the like. The computing environment100illustrated inFIG. 1, however, is merely an example of one computing environment. Embodiments of the present invention may be implemented on other computing platforms, regardless of whether the computer systems are dedicated video-game or home-media platforms, complex multi-user computing systems, such as a cluster of individual computers connected by a high-speed network, single-user workstations or network appliances lacking non-volatile storage, etc. Further, whileFIG. 1illustrates a client-server model, other models are contemplated such as a peer-to-peer model.

As shown, each client computer120includes a processing unit122, which obtains instructions and data via a bus121from a client memory130and client storage123. Processing unit122is a programmable logic device that performs instruction, logic and mathematical processing, and may be representative of one or more CPUs and/or GPUs. Client storage123stores application programs and data for use by client computer120.

The memory130is any memory sufficiently large to hold the necessary programs and data structures. Memory130could be one or a combination of memory devices, including Random Access Memory (e.g., DRAM modules), nonvolatile or backup memory (e.g., programmable or Flash memories, read-only memories, etc.).

Client storage123includes hard-disk drives, solid-state drives (SSD), flash memory devices, optical media and the like. As shown, client computer120is connected to the network160. Client memory130includes an operating system (OS)131and a gaming program132. Operating system131is the software used for managing the operation of the client computer120. Examples of OS131include UNIX, versions of the Microsoft Windows® operating system, and distributions of the Linux® operating system. Video game platforms typically use an operating system developed for the particular set of hardware in a given platform. In one embodiment, each client computer120may be a dedicated gaming console, such as a Sony PS3®, Nintendo Wii® or Xbox 360®, capable of executing the gaming program132. In another embodiment, each client is a general purpose computer configured to run any variety of gaming and non-gaming software.

As shown, client storage123stores a set of world geometry125, character geometry127and tool geometry129. The world geometry125provides a model of a virtual environment. That is, the world geometry125describes the shape and structure of each object within a virtual environment. As is known, geometry for computer-generated images is typically represented by a collection of vertices, which form polygonal faces. The vertices give an object a defined shape, and an appearance may be created by coloring each visible polygonal face. Similarly, the character geometry127describes the shape and structure of one or more player characters within a gaming environment. And tool geometry129corresponds to the geometry of a painting or thinning tool within the gaming environment. As discussed below, the intersection of paint or thinner tool geometry129with the world geometry125(or character geometry127) may result in changes to a painted or thinned state associated with elements of that geometry.

The output of gaming program132may be viewed on a display device170, such as an LCD, LED or CRT monitor display, and controlled using input devices180which may be, e.g., a keyboard, mouse and/or a controller. As shown, the gaming program132includes a rendering engine134, a physics engine136and a binary space partitioning tree (BSP) engine136. The rendering engine134is configured to take the world geometry125, character geometry127and tool geometry129and render images sent to the display device170at a frame rate sufficient to give the appearance of continuous motion. The physics engine136is configured to simulate the behavior certain simple physical systems, such as rigid body dynamics (including collision detection), soft body dynamics and fluid dynamics for elements of the gaming environment. Thus, objects in the gaming environment may behave in a manner consistent with how objects in reality respond to gravity, force, motion, acceleration etc. Of course, a gaming environment may be configured with alternative rules of behavior (e.g., portions of the world could exhibit anti-gravity).

The BSP engine136may be configured to generate binary space partitioning (BSP) trees to represent elements of world geometry125, character geometry127and/or tool geometry129. As is known, a BSP tree is a data structure which provides a recursive, hierarchical subdivision, dividing an n-dimensional space into convex subspaces. In a three-dimensional space, a BSP tree generally contains all of the polygons of a given set of geometry. At any given level of the BSP tree, all of the polygons to the right of a partitioning tree are on one side of a hyper plane division, and all of the polygons to the left of the partitioning are on the other. As is known, BSP trees provide an effective approach for determining whether a given polygon in a set of geometry (e.g., world geometry125) is visible or occluded by others.

In one embodiment, the BSP engine138generates a BSP tree describing the world geometry125, character geometry127and tool geometry129. Additionally, the resulting BSP trees may characterize each region (i.e., each polygon) of world geometry125as has having a painted or thinned state. As noted above, the painted state in a visible polygon has a painted volume rendered opaquely (i.e., visible) and opaque to collisions. That is, the polygon will collide with polygons of other objects (or itself) as determined by the physics engine136. In contrast, the thinned state in a visible polygon results in a polygon being rendered visibly transparent and transparent to collisions. The amount of transparency may be complete (i.e., a thinned region of geometry may be invisible) or limited to some level of transparency which allows the thinned volume to be observed within the gaming environment to a greater or lesser degree, depending on the level of transparency. Also note, tool geometry129representing paint or thinner remains collidable with world geometry, regardless of that geometry being in a painted or thinned state.

Further, the BSP engine may be configured to merge a BSP tree representing the tool geometry129with, e.g., the world geometry125. If the tool geometry129represents a painting tool, then the state of some polygons in the world geometry125may be updated to have a painted state, i.e., thinned regions of geometry become painted. Conversely, if the tool geometry129represents a thinning tool, then painted regions may be converted to a thinned state. In one embodiment, the regions of geometry may be specified as having a painted, thinned, inert or exterior state. As noted, thinning converts the intersection of geometry with a thinning tool into a thinned volume, rendered visibly transparent and transparent to collisions, while painting converts the intersection into a painted volume, rendered opaquely and opaque to collisions. Inert is used for volumes whose state connect be changed, i.e., cannot be thinned (if paint is applied) or painted (if thinner is applied). The following table presents an algebra for determining the resulting state of a region of geometry (as represented by a BSP tree) when that region is intersected with a painting or thinning tool.

TABLE IPainting and Thinning AlgebraEnvironmentToolResultPaint@Paint =PaintPaint@Thinner =ThinnerThinner@Paint =PaintThinner@Thinner =ThinnerInert@Paint =InertInert@Thinner =InertExterior@Paint =ExteriorExterior@Thinner =Exterior
Note, “exterior” refers to a region of geometry labeled as being outside of a given element of world geometry. Because of the algebra, the world-geometry125(or character geometry127) remains restorative in response to painting and thinning operations. That is, the geometry of an object is unaffected by a painting or thinning operation, but its appearance and collidability for purposes of physics and game play is changed. Thus, thinning a previously painted object or repainting a thinned object restores the painting/thinning state of that geometry without altering its two- or three-dimensional structure. Compare this with an algebra used for constructive solid geometry (CSG):

TABLE IIConstructive Solid Geometry Algebra - Union operationEnvironmentToolResultInterior@Interior =InteriorInterior@Exterior =InteriorExterior@Interior =InteriorExterior@Exterior =Exterior
Both painting/thinning operations and CSG operations may be used to modify the underlying geometry of an object. However, painting/thinning operations, unlike CSG operations, maintain the original “fully painted” state within the BSP tree, even though the BSP tree and the object's underlying geometry have been modified. In other words, given a fully painted object on which many thinning operations are performed, the fully painted state of the object may be easily restored through painting operations, because the thinning operation does not destroy information about the original, fully painted state.

As shown, the server system140includes the same basic hardware elements as the client computers120. Specifically, the server system140includes a processing unit142(representative of one or more CPUs and/or GPUs), a memory144and storage143connected via a bus141. The server system140may be operably connected to the network160, which generally represents any kind of data communications network. Accordingly, the network160may represent both local and wide area networks, including the Internet. In one embodiment, the server system140hosts an on-line gaming environment to which one or more of the client computers120connect. In this case, server-side gaming software146may be located in memory144of the server system140and cooperates with client-side gaming software (e.g., game program132) located on the respective client computers120.

FIGS. 2A-2Billustrate an example of paint material being applied to the geometry of a gaming environment, according to an embodiment of the invention. In this Example,FIG. 2Ashows a still-image200of a video game where the world geometry includes a chasm215and a thinned bridge230. As shown, an initial plank220of the thinned bridge230is shown in a painted state. The plank220may provide a clue to the user that some of the world geometry is present but in a thinned state. Further, although thinned bridge230is shownFIG. 2Aas dashed lines, as noted above, material in a thinned state may be fully invisible.

A character205is stuck on one side of the chasm215. The character205is shown holding a capsule210of painting material. Assume the character205throws the capsule210at thinned bridge230, and further, the physics engine is configured to treat the paint material as a liquid. In one embodiment, this may be approximated by determining a location where the capsule210hits and merging a tool representing a fixed approximation of the paint (or thinner) “spreading.”

Accordingly, when the capsule210intersects the bridge230, the paint material in capsule210spreads across the surface of thinned bridge, resulting in sections of the bridge230being painted. In one embodiment, to determine what sections of the bridge are painted by the paint material, a BSP tree representing the paint material and a BSP tree representing the thinned bridge230are merged, and the state of painted/thinned sections of the bridge geometry are updated. If the paint material did not intersect a sufficient portion of the bridge to allow the character205to cross, additional paint material could be applied. This result of applying the paint material to the thinned bridge230is shown inFIG. 2B, where painted bridge230′ now allows the character205to cross to the other side of the chasm215.

FIGS. 3A-3Billustrate an example of thinner material being applied to some of the geometry of the gaming environment ofFIGS. 2A-2B, according to an embodiment of the invention. In this example,FIG. 3Ashows a still-image300of the video game after the character205has crossed the chasm215(on painted bridge230′) and reached a rocky mountain face330. As shown, the rocky mountain face330is impassable. However, the character205is shown holding a capsule310of thinning material. Assume the character205throws the capsule310at rocky mountain face330, and further, the physics engine is configured to treat the thinning material as a liquid. Accordingly, when the capsule310intersects the rocky mountain face330, the thinning material in capsule310spreads across the surface of rocky mountain face330, resulting in sections being thinned. In one embodiment, to determine what regions of the world geometry are “thinned” by the thin material, as with the paint material, a BSP tree representing the thinning material and a BSP tree representing the rocky mountain face330are merged, and the state of painted/thinned sections of the rocky mountain face330are updated. If the paint material did not intersect a sufficient area of rocky mountain face330to reveal the passage behind the rocky mountain face330, additional thinning material could be applied.

As noted, in a thinned state, the geometry of rocky mountain face330is treated as transparent to collisions and may be rendered in a semi-visible state or not at all. This result of applying the thinning material to the rocky mountain face330is shown inFIG. 3B, where open passage340is now visible, allowing the character205to enter a cave behind the rocky mountain face330. Of course, the examples ofFIGS. 2A-2Band3A-3B represent just one example of how the painting and thinning mechanic may be used within a video game and any number of in-game scenarios for using the painting and thinning mechanic to alter the appearance and collidability of in game geometry is contemplated. For example, the geometrical regions need not be represented by vertices. Other representations are possible (e.g., a pure hyperplane/subhyperplane approach). Similarly, an in game character may be provided with access to the paint or thinner material using a variety of mechanisms in addition to the capsule approach described for paint capsule210and thinner capsule310. Further, the examples ofFIGS. 2A-2Band3A-3B provide an example where the user controlling the in-game character controls the application of paint or thinner to the world. Of course, other variations are possible. That is, elements of the world geometry itself may provide the paint or thinner material. For example, a waterfall could be made of thinner material. In such a case, if a cave is accessible only by traversing under the waterfall, objects held by the in-game character that are susceptible to be thinned (based on the paining or thinning state of their object geometry) would be thinned when the in-game character traverses under the waterfall. Conversely, the waterfall could be paint material. Assume an in-game character is attacked by game-controlled characters throwing thinner capsules at the in-game character, resulting in a thinned in-game character unable to interact with the world geometry of the game. In such a case, the paint waterfall would allow the user to reanimate the in-game character.

FIG. 4illustrates an example of a section of two-dimensional geometry to which a paint and thinner tool is applied based on an algebra describing the results of intersecting paint (or thinner) with the geometry, according to one embodiment of the invention. InFIG. 4, the geometry is represented using a set of regions, defined by a set of vertices Additionally, each region in the geometry is associated with a painting/thinning state of exterior, paint, thinned, or inert, according to the labels shown in a legend400.

Illustratively, the geometry405includes a painted region415, an inert region420and a thinned region425, bounded on each side by an exterior region.FIG. 4shows also shows the geometry of a thinning tool410applied to geometry405. In particular, the thinning tool410intersects a portion of each of the painted region415, the inert region420and the thinned region425. The results of applying the thinning tool410to each region are shown in geometry430. The thinned region425′ and the inert region420′ are unchanged by the application of thinner. However, the painted region415is now divided into painted region415′ and thinned region435. That is, the application of the thinning tool410results in a new thinned region435being introduced to the geometry430.

FIG. 4also illustrates an example of a painting tool410′ being applied to a set of geometry405′. Like, the geometry405, the geometry405′ includes a painted region455, an inert region450and a thinned region460, bounded on each side by an exterior region. And the painting tool410′ intersects a portion of each of the painted region455, the inert region450and the thinned region460. The results of applying the painting tool410′ to each of these regions are shown in geometry440. The painted region455′ and the inert region450′ are unchanged by the application of paint to the geometry405′. However, the thinned region460is now divided into thinned region470and painted region475. That is, the application of the paint tool410′ results in a new painted region475being introduced to the geometry440.

FIG. 5illustrates a method500for providing a paint/thinner game mechanic, according to an embodiment of the invention. As shown, the method500begins at step505, where a game engine receives user input resulting in paint or thinner material being applied to some portion of world (or character) geometry. For example, as described above, a game may be configured so as to provide users with access to paint or thinner capsules, filled with material treated as a liquid by a physics engine. In such a case, when the capsule impacts elements of the world geometry and bursts, the liquid paint or thinner material spreads across the surface of the geometry.

At step510, the game engine may determine a binary space partitioning (BSP) tree describing a paint/thinned state of each face or volume of the world geometry to which the paint/thinner material was applied at step505. As noted above, in one embodiment, each region of geometry on the world (or character) geometry may have an associated state of painted, thinned, inert or exterior state. At step515, the game engine may generate a BSP tree describing the geometry of the paint/thinner material being applied to the world geometry. At step520, the game engine may merge the BSP trees determined at steps510and515. While a variety of techniques for merging BSP trees may be used, one approach is described in “Merging BSP Trees Yields Polyhedral Set Operations,” by Bruce Naylor published at pages 115-124 in theInternational Conference on Computer Graphics and Interactive Techniques Proceedings of the17th annual Conference on Computer Graphics and Interactive Techniques, and which is hereby incorporated by reference in its entirety.

In one embodiment, the merged tree is used to determine an updated state for the faces of the world geometry. For example, Table I, above, shows algebra for determining a resultant state for the faces of the world geometry which intersects with the paint (or thinner) material, based on an initial state and the application of either paint or thinner material.

Optionally, at step525, the gaming engine may simplify the merged BSP tree representing the world geometry. As noted above, the merged BSP tree represents a set of regions of geometry where each region may have a painted, thinned, inert or exterior state, and the boundary of each region may be derived by a set of vertices. Further, the geometry, as represented in a BSP tree may be used for certain rendering (or physics) operations. As noted, e.g., BSP trees provide an effective approach for determining whether a given polygon in a set of world geometry is visible or occluded by others. However, not all of the different regions in the merged BSP tree are needed for rendering. For example, consider the geometry440shown inFIG. 4, which includes a boundary480and a boundary490. The boundary480and490each separate a painted region and an inert region. As both the properties of an inert region and a painted region are the same (for purposes of rendering), the three distinct regions450′,455′ and475may be collapsed into a single region. That is, as both painted regions and inert regions are painted and opaque to collisions, they need not be distinguished from one another when the geometry is passed to a rendering (or physics) engine. At step530, the vertices of the world geometry are passed to a rendering and/or physics engine, resulting in images being rendered, with geometry having the painted or thinned state.

Advantageously, embodiments described above may be used to provide 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.” More specifically, painting and thinning refers to a game mechanic that involves making parts of the game world visibly and collidably transparent (thinning) or visibly and collidably opaque (painting). Users may interact directly with the results of a painting or thinning operation, e.g., thinned sections of the world could be passed through, while painted sections could be hung on, landed on, traversed, etc. An in-game character could access units of a “painting” or “thinning” substance and throw, launch or otherwise release it into the computer-generated environment, resulting in the paint (or thinner) material intersecting with elements of the world geometry. In one embodiment, the painting/thinning mechanic may be achieved using binary space partitioning (BSP) trees.

The aforementioned operations to be performed by a gaming program provides a platform gaming experience that advantageously provides an additional method of direct interaction with gaming elements with an improved user experience. While the foregoing is directed to embodiments of the present invention, other and further embodiments of the invention may be devised without departing from the basic scope thereof, and the scope thereof is determined by the claims that follow.