3D CAGE GENERATION USING SIGNED DISTANCE FUNCTION APPROXIMANT

Some implementations relate to methods, systems, and computer-readable media to generate 3D objects including 3D meshes and 3D cages. A signed distance function (SDF) approximant for a 3D mesh is determined by combining radial basis functions (RBFs) originating on the 3D mesh. A cage for the 3D mesh is generated by positioning cage vertices using the SDF approximant such that the cage overlays the 3D mesh. The generated 3D object includes the 3D mesh and the cage.

TECHNICAL FIELD

Implementations relate generally to automated 3D mesh cage generation.

BACKGROUND

Multi-user electronic gaming environments typically involve the use of avatars, which represent the players in an electronic game. Avatars are often three-dimensional (3D) avatars that differ in geometry/shapes from one avatar to another. For example, avatars may have different body shapes (e.g., tall, short, muscular, thin, male, female, human, animal, alien, etc.), number and types of limbs, and are customizable with multiple pieces clothing and/or accessories worn by the avatar (e.g., shirt worn over the torso, jacket worn over the shirt, scarf worn over the jacket, hat worn over the head, etc.).

To provide clothing and/or accessories for avatars, game developers traditionally use a unified topology for the body and clothing, so that the geometry of the clothing fits the geometry of the body. Thus, these techniques use pre-defined shapes to achieve some rudimentary geometry-to-geometry matching between the clothing and the body. However, such techniques (due to the presence of pre-defined shapes) provide limited capability to customize body shapes and clothing.

When more customization is needed (e.g., due to non-uniform body shapes of avatars and clothing), more intensive user input and graphical programming is required. For instance, these techniques require the creator user (e.g., one that provides the clothing items and/or different body shapes) to perform complex computations in order to graphically generate clothing having geometry that matches the geometry of the body. These processes are complex, and also require close coordination and cooperation between body shape creators and clothing creators.

SUMMARY

Aspects of the disclosure relate to methods, systems, and computer-readable media to generate 3D objects including 3D meshes and 3D cages.

In one aspect, a method is described. The method may comprise determining a signed distance function (SDF) approximant for a three-dimensional (3D) mesh by combining a plurality of radial basis functions (RBFs), where each of the plurality of radial basis functions has an origin on the 3D mesh; generating a cage for the 3D mesh, the cage comprising a plurality of cage vertices, by positioning the plurality of cage vertices using the SDF approximant such that the cage overlays the 3D mesh; and generating a 3D object comprising the 3D mesh and the cage.

In some implementations of the method, the 3D mesh comprises a plurality of mesh vertices and the origin for each RBF is located at a respective mesh vertex.

In some implementations of the method, generating the cage for the 3D mesh comprises determining a normal vector for each mesh vertex, determining a gradient of the SDF along each normal vector, positioning the plurality of cage vertices on normal vectors, and moving the plurality of cage vertices in directions indicated by the gradients until the value of the SDF reaches a distance parameter.

In some implementations of the method, the 3D mesh is an inner body cage of a body of a 3D avatar, the cage is an outer body cage for the 3D avatar, and generating the 3D object comprises causing the 3D avatar to be displayed according to the inner body cage and the outer body cage.

In some implementations of the method, determining the SDF approximant comprises determining a respective weight for each of the plurality of RBFs, and the SDF approximant comprises a weighted sum of the plurality of RBFs using the respective weights.

In some implementations of the method, determining the respective weight for each plurality of RBFs comprises calculating the weights such that the value of the weighted sum evaluated at each mesh vertex is a common constant.

In some implementations of the method, determining the SDF approximant comprises determining an average magnitude of gradient vectors of the weighted sum evaluated at the mesh vertices, and normalizing the weights according to the average magnitude such that the SDF comprises a sum of the RBFs weighted by the normalized weights.

In some implementations of the method, the 3D mesh is an outer body cage of a body of a 3D avatar, the cage is an outer clothing cage for a piece of clothing for the 3D avatar, and generating the 3D object comprises causing the 3D avatar to be displayed according to the body of the 3D avatar, the piece of clothing, and the outer clothing cage.

In some implementations of the method, determining the SDF proximant comprises determining a respective weight function for each of the plurality of RBFs and the SDF approximant comprises a weighted sum of the plurality of RBFs using the respective weight functions.

In some implementations of the method, determining the weight function for each of the plurality of RBFs comprises calculating the weight functions such that the weighted sum evaluated at respective pairs of points on the normal vectors and centered at the vertices is equal to the signed distance from each point to the respective central vertex.

In some implementations of the method, determining the weight function for each plurality of RBFs comprises calculating the weight functions such that the weighted sum of the plurality of RBFs equals a constraint constant at constraining distances around the 3D mesh, and the constraint constant and constraining distances are greater than a characteristic length of the 3D mesh.

In another aspect, non-transitory computer-readable medium is described. The non-transitory computer-readable medium may have instructions stored thereon that, responsive to execution by a processor, cause the processor to perform or control performance of operations that comprise determining a signed distance function (SDF) approximant for a three-dimensional (3D) mesh by combining a plurality of radial basis functions (RBFs), where the 3D mesh comprises a plurality of vertices and each of the plurality of radial basis functions has an origin on the 3D mesh at a respective mesh vertex; generating a cage for the 3D mesh, the cage comprising a plurality of cage vertices, by determining a normal vector for each mesh vertex, determining a gradient of the SDF along each normal vector, positioning the plurality of cage vertices on normal vectors, and moving the plurality of cage vertices in directions indicated by the gradients until the value of the SDF reaches a distance parameter such that the cage overlays the 3D mesh; and generating a 3D object comprising the 3D mesh and the cage.

In some implementations of the non-transitory computer-readable medium, determining the SDF approximant comprises determining a respective weight for each of the plurality of RBFs such that the value of the weighted sum evaluated at each mesh vertex is a common constant, and the SDF approximant comprises a weighted sum of the plurality of RBFs using the respective weights.

In some implementations of the non-transitory computer-readable medium, the 3D mesh is an inner body cage of a body of a 3D avatar, the cage is an outer body cage for the 3D avatar, and the operation of generating the 3D object further comprises causing the 3D avatar to be displayed according to the inner body cage and the outer body cage.

In some implementations of the non-transitory computer-readable medium, determining the SDF approximant comprises determining a respective weight function for each of the plurality of RBFs such that the weighted sum evaluated at respective pairs of points on the normal vectors and centered at the vertices is equal to the signed distance from each point to the respective central vertex and the SDF approximant comprises a weighted sum of the plurality of RBFs using the respective weight functions.

In some implementations of the non-transitory computer-readable medium, the 3D mesh is an outer body cage of a body of a 3D avatar, the cage is an outer clothing cage for a piece of clothing for the 3D avatar, and the operation of generating the 3D object further comprises causing the 3D avatar to be According to yet another aspect, portions, features, and implementation details of the systems, methods, and non-transitory computer-readable media may be combined to form additional aspects, including some aspects which omit and/or modify some or portions of individual components or features, include additional components or features, and/or other modifications; and all such modifications are within the scope of this disclosure.displayed according to the body of the 3D avatar, the piece of clothing, and the outer clothing cage.

In other aspect, an apparatus is described. The apparatus may comprise a processor; and a non-transitory computer-readable medium coupled to the processor and having instructions stored thereon that, responsive to execution by the processor, cause the processor to perform or control performance of operations that comprise: determining a signed distance function (SDF) approximant for a three-dimensional (3D) mesh by combining a plurality of radial basis functions (RBFs), where the 3D mesh comprises a plurality of vertices and each of the plurality of radial basis functions has an origin on the 3D mesh at a respective mesh vertex; generating a cage for the 3D mesh, the cage comprising a plurality of cage vertices, by determining a normal vector for each mesh vertex, determining a gradient of the SDF along each normal vector, positioning the plurality of cage vertices on normal vectors, and moving the plurality of cage vertices in directions indicated by the gradients until the value of the SDF reaches a distance parameter such that the cage overlays the 3D mesh; and generating a 3D object comprising the 3D mesh and the cage.

In some implementations of the apparatus, determining the SDF approximant comprises determining a respective weight for each of the plurality of RBFs such that the value of the weighted sum evaluated at each mesh vertex is a common constant, and the SDF approximant comprises a weighted sum of the plurality of RBFs using the respective weights.

In some implementations of the apparatus, the 3D mesh is an inner body cage of a body of a 3D avatar, the cage is an outer body cage for the 3D avatar, and the operation of generating the 3D object further comprises causing the 3D avatar to be displayed according to the inner body cage and the outer body cage.

In some implementations of the apparatus, the 3D mesh is an outer body cage of a body of a 3D avatar, the cage is an outer clothing cage for a piece of clothing for the 3D avatar, and determining the SDF approximant comprises determining a respective weight function for each of the plurality of RBFs such that the weighted sum evaluated at respective pairs of points on the normal vectors and centered at the vertices is equal to the signed distance from each point to the respective central vertex and the SDF approximant comprises a weighted sum of the plurality of RBFs using the respective weight functions, and the operation of generating the 3D object further comprises causing the 3D avatar to be displayed according to the body of the 3D avatar, the piece of clothing, and the outer clothing cage.

According to yet another aspect, portions, features, and implementation details of the systems, methods, and non-transitory computer-readable media may be combined to form additional aspects, including some aspects which omit and/or modify some or portions of individual components or features, include additional components or features, and/or other modifications; and all such modifications are within the scope of this disclosure.

DETAILED DESCRIPTION

In the following detailed description, reference is made to the accompanying drawings, which form a part hereof. In the drawings, similar symbols typically identify similar components, unless context dictates otherwise. The illustrative implementations described in the detailed description, drawings, and claims are not meant to be limiting. Other implementations may be utilized, and other changes may be made, without departing from the spirit or scope of the subject matter presented herein. Aspects of the present disclosure, as generally described herein, and illustrated in the Figures, can be arranged, substituted, combined, separated, and designed in a wide variety of different configurations, all of which are contemplated herein.

References in the specification to “some implementations”, “an implementation”, “an example implementation”, etc. indicate that the implementation described may include a particular feature, structure, or characteristic, but every implementation may not necessarily include the particular feature, structure, or characteristic. Moreover, such phrases are not necessarily referring to the same implementation. Further, when a particular feature, structure, or characteristic is described in connection with an implementation, such feature, structure, or characteristic may be effected in connection with other implementations whether or not explicitly described.

The present disclosure provides techniques to automatically generate cage meshes for 3D objects such as clothing, bodies, and accessories. These cages may be used to create 3D objects. For example, two identically indexed inner and outer cages may be used to define a layer of 3D vector fields that represent a 3D object. In some cases, the inner cage is a template for the object, which can be customized by a user or can be automatically conformed to an underlying object. For example, the inner cage may be a body mesh that can be customized by a user or content creator; or the inner cage may a template for an article of clothing that will be fitted to an underlying body mesh.

The described technique allows any body geometry to be fitted with any clothing geometry, including enabling layers of clothing to be fitted over underlying layer(s) of clothing, thereby providing customization without the limits imposed by pre-defined geometries or requiring complex computations to make a clothing item compatible with arbitrary body shapes of avatars or other clothing items. The cage-to-cage fitting is also performed algorithmically by a gaming platform or gaming software (or other platform/software that operates to provide a 3D environment), without requiring avatar creators (also referred to as avatar body creators, or body creators) or clothing item creators to perform complex computations. The terms “clothing” or “clothing item” used herein are understood to include clothing and accessories, and any other item that can be placed on an avatar in relation to specific parts of an avatar cage.

The implementations described herein enable the work of the avatar body creators to be decoupled from the work of the clothing creators. For example, avatar body creators can create bodies having geometries of any desired/customized shape and size, and publish the bodies in a body library hosted by a 3D platform. Clothing creators can independently create generic templates of any piece of clothing, such as shirts, pants, etc., and publish the clothing templates in a clothing library hosted by the 3D platform.

Purely for purposes of illustration and explanation, various embodiments are described herein in the context of 3D avatars that are used in a 3D game provided by a gaming platform. It is appreciated that such gaming environments are merely examples. Other implementations of the cage-to-cage layering techniques described herein may be applied to other types of 3D environments, such as a virtual reality (VR) conference, a 3D session (e.g., an online lecture or other type of presentation involving 3D avatars), an augmented reality (AR) session, or in other types of 3D environments that may include one or more users that are represented in the 3D environment by one or more 3D avatars.

At runtime during a game or other 3D session, a player/user accesses the body library to select a particular body, and accesses the clothing library to select pieces of clothing to place on the selected body. The 3D environment platform that presents the avatars then implements the cage-to-cage fitting techniques to adjust (by suitable deformations, determined automatically) a piece of clothing to conform to the shape of the body, thereby automatically fitting the piece of clothing onto the body (and any intermediate layers, if worn by the avatar). The user can further select an additional piece of clothing to fit over an underlying piece of clothing (layered clothing), with the additional piece of clothing deforming to match the geometry of the underlying piece of clothing.

The implementations described herein are based on the concept of “cages” and “meshes.” A body mesh is the actual visible geometry of an avatar. A body mesh includes the graphical representation of the arms, legs, torso, head parts, etc. and can be of arbitrary shape, size, and geometric topology. Analogously, a clothing mesh can be any arbitrary mesh that graphically represents a piece of clothing, such as a shirt, pants, hat, shoes, etc. or parts thereof.

In comparison, a cage represents an envelope of features points around the avatar body that is much simpler than the body mesh and has correspondence to the vertices of the body mesh. As will be explained in further detail later below, a cage may also be used to represent not only the set of feature points on an avatar body, but also a set of feature points on a piece of clothing.

FIG.1is a diagram of an example system architecture for simulation of rigid body objects, in accordance with some implementations.FIG.1and the other figures use like reference numerals to identify similar elements. A letter after a reference numeral, such as “110,” indicates that the text refers specifically to the element having that particular reference numeral. A reference numeral in the text without a following letter, such as “110,” refers to any or all of the elements in the figures bearing that reference numeral (e.g. “110” in the text refers to reference numerals “110a,” “110b,” and/or “110n” in the figures).

The system architecture100(also referred to as “system” herein) includes online virtual experience server102, data store120, client devices110a,110b, and110n(generally referred to as “client device(s)110” herein), and developer devices130aand130n(generally referred to as “developer device(s)130” herein). Virtual experience server102, data store120, client devices110, and developer devices130are coupled via network122. In some implementations, client devices(s)110and developer device(s)130may refer to the same or same type of device.

Online virtual experience server102can include, among other things, a virtual experience engine104, one or more virtual experiences106, and graphics engine108. In some implementations, the graphics engine108may be a system, application, or module that permits the online virtual experience server102to provide graphics and animation capability. In some implementations, the graphics engine108may perform one or more of the operations described below in connection with the flowchart shown inFIG.6. A client device110can include a virtual experience application112, and input/output (I/O) interfaces114(e.g., input/output devices). The input/output devices can include one or more of a microphone, speakers, headphones, display device, mouse, keyboard, game controller, touchscreen, virtual reality consoles, etc.

A developer device130can include a virtual experience application132, and input/output (I/O) interfaces134(e.g., input/output devices). The input/output devices can include one or more of a microphone, speakers, headphones, display device, mouse, keyboard, game controller, touchscreen, virtual reality consoles, etc.

System architecture100is provided for illustration. In different implementations, the system architecture100may include the same, fewer, more, or different elements configured in the same or different manner as that shown inFIG.1.

In some implementations, network122may include a public network (e.g., the Internet), a private network (e.g., a local area network (LAN) or wide area network (WAN)), a wired network (e.g., Ethernet network), a wireless network (e.g., an 802.11 network, a Wi-Fi® network, or wireless LAN (WLAN)), a cellular network (e.g., a 5G network, a Long Term Evolution (LTE) network, etc.), routers, hubs, switches, server computers, or a combination thereof.

In some implementations, the data store120may be a non-transitory computer readable memory (e.g., random access memory), a cache, a drive (e.g., a hard drive), a flash drive, a database system, or another type of component or device capable of storing data. The data store120may also include multiple storage components (e.g., multiple drives or multiple databases) that may also span multiple computing devices (e.g., multiple server computers). In some implementations, data store120may include cloud-based storage.

In some implementations, the online virtual experience server102can include a server having one or more computing devices (e.g., a cloud computing system, a rackmount server, a server computer, cluster of physical servers, etc.). In some implementations, the online virtual experience server102may be an independent system, may include multiple servers, or be part of another system or server.

In some implementations, the online virtual experience server102may include one or more computing devices (such as a rackmount server, a router computer, a server computer, a personal computer, a mainframe computer, a laptop computer, a tablet computer, a desktop computer, etc.), data stores (e.g., hard disks, memories, databases), networks, software components, and/or hardware components that may be used to perform operations on the online virtual experience server102and to provide a user with access to online virtual experience server102. The online virtual experience server102may also include a website (e.g., a web page) or application back-end software that may be used to provide a user with access to content provided by online virtual experience server102. For example, users may access online virtual experience server102using the virtual experience application112on client devices110.

In some implementations, virtual experience session data are generated via online virtual experience server102, virtual experience application112, and/or virtual experience application132, and are stored in data store120. With permission from virtual experience participants, virtual experience session data may include associated metadata, e.g., virtual experience identifier(s); device data associated with the participant(s); demographic information of the participant(s); virtual experience session identifier(s); chat transcripts; session start time, session end time, and session duration for each participant; relative locations of participant avatar(s) within a virtual experience environment; purchase(s) within the virtual experience by one or more participants(s); accessories utilized by participants; etc.

In some implementations, online virtual experience server102may be a type of social network providing connections between users or a type of user-generated content system that allows users (e.g., end-users or consumers) to communicate with other users on the online virtual experience server102, where the communication may include voice chat (e.g., synchronous and/or asynchronous voice communication), video chat (e.g., synchronous and/or asynchronous video communication), or text chat (e.g., 1:1 and/or N:N synchronous and/or asynchronous text-based communication). A record of some or all user communications may be stored in data store120or within virtual experiences106. The data store120may be utilized to store chat transcripts (text, audio, images, etc.) exchanged between participants.

In some implementations, the chat transcripts are generated via virtual experience application112and/or virtual experience application132or and are stored in data store120. The chat transcripts may include the chat content and associated metadata, e.g., text content of chat with each message having a corresponding sender and recipient(s); message formatting (e.g., bold, italics, loud, etc.); message timestamps; relative locations of participant avatar(s) within a virtual experience environment, accessories utilized by virtual experience participants, etc. In some implementations, the chat transcripts may include multilingual content, and messages in different languages from different sessions of a virtual experience may be stored in data store120.

In some implementations, chat transcripts may be stored in the form of conversations between participants based on the timestamps. In some implementations, the chat transcripts may be stored based on the originator of the message(s).

In some implementations of the disclosure, a “user” may be represented as a single individual. However, other implementations of the disclosure encompass a “user” (e.g., creating user) being an entity controlled by a set of users or an automated source. For example, a set of individual users federated as a community or group in a user-generated content system may be considered a “user.”

In some implementations, online virtual experience server102may be a virtual gaming server. For example, the gaming server may provide single-player or multiplayer games to a community of users that may access as “system” herein) includes online gaming server102, data store120, client or interact with virtual experiences using client devices110via network122. In some implementations, virtual experiences (including virtual realms or worlds, virtual games, other computer-simulated environments) may be two-dimensional (2D) virtual experiences, three-dimensional (3D) virtual experiences (e.g., 3D user-generated virtual experiences), virtual reality (VR) experiences, or augmented reality (AR) experiences, for example. In some implementations, users may participate in interactions (such as gameplay) with other users. In some implementations, a virtual experience may be experienced in real-time with other users of the virtual experience.

In some implementations, virtual experience engagement may refer to the interaction of one or more participants using client devices (e.g.,110) within a virtual experience (e.g.,106) or the presentation of the interaction on a display or other output device (e.g.,114) of a client device110. For example, virtual experience engagement may include interactions with one or more participants within a virtual virtual experience or the presentation of the interactions on a display of a client device.

In some implementations, a virtual experience106can include an electronic file that can be executed or loaded using software, firmware or hardware configured to present the virtual experience content (e.g., digital media item) to an entity. In some implementations, a virtual experience application112may be executed and a virtual experience106rendered in connection with a virtual experience engine104. In some implementations, a virtual experience106may have a common set of rules or common goal, and the environment of a virtual experience106shares the common set of rules or common goal. In some implementations, different virtual experiences may have different rules or goals from one another.

In some implementations, virtual experiences may have one or more environments (also referred to as “virtual experience environments” or “virtual environments” herein) where multiple environments may be linked. An example of an environment may be a three-dimensional (3D) environment. The one or more environments of a virtual experience106may be collectively referred to as a “world” or “virtual experience world” or “gaming world” or “virtual world” or “universe” herein. An example of a world may be a 3D world of a virtual experience106. For example, a user may build a virtual environment that is linked to another virtual environment created by another user. A character of the virtual virtual experience may cross the virtual border to enter the adjacent virtual environment.

It may be noted that 3D environments or 3D worlds use graphics that use a three-dimensional representation of geometric data representative of virtual experience content (or at least present virtual experience content to appear as 3D content whether or not 3D representation of geometric data is used). 2D environments or 2D worlds use graphics that use two-dimensional representation of geometric data representative of virtual experience content.

In some implementations, the online virtual experience server102can host one or more virtual experiences106and can permit users to interact with the virtual experiences106using a virtual experience application112of client devices110. Users of the online virtual experience server102may play, create, interact with, or build virtual experiences106, communicate with other users, and/or create and build objects (e.g., also referred to as “item(s)” or “virtual experience objects” or “virtual virtual experience item(s)” herein) of virtual experiences106.

For example, in generating user-generated virtual items, users may create characters, decoration for the characters, one or more virtual environments for an interactive virtual experience, or build structures used in a virtual experience106, among others. In some implementations, users may buy, sell, or trade virtual virtual experience objects, such as in-platform currency (e.g., virtual currency), with other users of the online virtual experience server102. In some implementations, online virtual experience server102may transmit virtual experience content to virtual experience applications (e.g.,112). In some implementations, virtual experience content (also referred to as “content” herein) may refer to any data or software instructions (e.g., virtual experience objects, virtual experience, user information, video, images, commands, media item, etc.) associated with online virtual experience server102or virtual experience applications. In some implementations, virtual experience objects (e.g., also referred to as “item(s)” or “objects” or “virtual objects” or “virtual virtual experience item(s)” herein) may refer to objects that are used, created, shared or otherwise depicted in virtual experience applications106of the online virtual experience server102or virtual experience applications112of the client devices110. For example, virtual experience objects may include a part, model, character, accessories, tools, weapons, clothing, buildings, vehicles, currency, flora, fauna, components of the aforementioned (e.g., windows of a building), and so forth.

It may be noted that the online virtual experience server102hosting virtual experiences106, is provided for purposes of illustration. In some implementations, online virtual experience server102may host one or more media items that can include communication messages from one user to one or more other users. With user permission and express user consent, the online virtual experience server102may analyze chat transcripts data to improve the virtual experience platform. Media items can include, but are not limited to, digital video, digital movies, digital photos, digital music, audio content, melodies, website content, social media updates, electronic books, electronic magazines, digital newspapers, digital audio books, electronic journals, web blogs, real simple syndication (RSS) feeds, electronic comic books, software applications, etc. In some implementations, a media item may be an electronic file that can be executed or loaded using software, firmware or hardware configured to present the digital media item to an entity.

In some implementations, a virtual experience106may be associated with a particular user or a particular group of users (e.g., a private virtual experience), or made widely available to users with access to the online virtual experience server102(e.g., a public virtual experience). In some implementations, where online virtual experience server102associates one or more virtual experiences106with a specific user or group of users, online virtual experience server102may associate the specific user(s) with a virtual experience106using user account information (e.g., a user account identifier such as username and password).

In some implementations, online virtual experience server102or client devices110may include a virtual experience engine104or virtual experience application112. In some implementations, virtual experience engine104may be used for the development or execution of virtual experiences106. For example, virtual experience engine104may include a rendering engine (“renderer”) for 2D, 3D, VR, or AR graphics, a physics engine, a collision detection engine (and collision response), sound engine, scripting functionality, animation engine, artificial intelligence engine, networking functionality, streaming functionality, memory management functionality, threading functionality, scene graph functionality, or video support for cinematics, among other features. The components of the virtual experience engine104may generate commands that help compute and render the virtual experience (e.g., rendering commands, collision commands, physics commands, etc.) In some implementations, virtual experience applications112of client devices110, respectively, may work independently, in collaboration with virtual experience engine104of online virtual experience server102, or a combination of both.

In some implementations, both the online virtual experience server102and client devices110may execute a virtual experience engine (104and112, respectively). The online virtual experience server102using virtual experience engine104may perform some or all the virtual experience engine functions (e.g., generate physics commands, rendering commands, etc.), or offload some or all the virtual experience engine functions to virtual experience engine104of client device110. In some implementations, each virtual experience106may have a different ratio between the virtual experience engine functions that are performed on the online virtual experience server102and the virtual experience engine functions that are performed on the client devices110. For example, the virtual experience engine104of the online virtual experience server102may be used to generate physics commands in cases where there is a collision between at least two virtual experience objects, while the additional virtual experience engine functionality (e.g., generate rendering commands) may be offloaded to the client device110. In some implementations, the ratio of virtual experience engine functions performed on the online virtual experience server102and client device110may be changed (e.g., dynamically) based on virtual experience engagement conditions. For example, if the number of users engaging in a particular virtual experience106exceeds a threshold number, the online virtual experience server102may perform one or more virtual experience engine functions that were previously performed by the client devices110.

For example, users may be playing a virtual experience106on client devices110, and may send control instructions (e.g., user inputs, such as right, left, up, down, user election, or character position and velocity information, etc.) to the online virtual experience server102. Subsequent to receiving control instructions from the client devices110, the online virtual experience server102may send experience instructions (e.g., position and velocity information of the characters participating in the group experience or commands, such as rendering commands, collision commands, etc.) to the client devices110based on control instructions. For instance, the online virtual experience server102may perform one or more logical operations (e.g., using virtual experience engine104) on the control instructions to generate experience instruction(s) for the client devices110. In other instances, online virtual experience server102may pass one or more or the control instructions from one client device110to other client devices (e.g., from client device110ato client device110b) participating in the virtual experience106. The client devices110may use the experience instructions and render the virtual experience for presentation on the displays of client devices110.

In some implementations, the control instructions may refer to instructions that are indicative of actions of a user's character within the virtual experience. For example, control instructions may include user input to control action within the experience, such as right, left, up, down, user selection, gyroscope position and orientation data, force sensor data, etc. The control instructions may include character position and velocity information. In some implementations, the control instructions are sent directly to the online virtual experience server102. In other implementations, the control instructions may be sent from a client device110to another client device (e.g., from client device110bto client device110n), where the other client device generates experience instructions using the local virtual experience engine104. The control instructions may include instructions to play a voice communication message or other sounds from another user on an audio device (e.g., speakers, headphones, etc.), for example voice communications or other sounds generated using the audio spatialization techniques as described herein.

In some implementations, experience instructions may refer to instructions that enable a client device110to render a virtual experience, such as a multiparticipant virtual experience. The experience instructions may include one or more of user input (e.g., control instructions), character position and velocity information, or commands (e.g., physics commands, rendering commands, collision commands, etc.).

In some implementations, characters (or virtual experience objects generally) are constructed from components, one or more of which may be selected by the user, that automatically join together to aid the user in editing.

In some implementations, a character is implemented as a 3D model and includes a surface representation used to draw the character (also known as a skin or mesh) and a hierarchical set of interconnected bones (also known as a skeleton or rig). The rig may be utilized to animate the character and to simulate motion and action by the character. The 3D model may be represented as a data structure, and one or more parameters of the data structure may be modified to change various properties of the character, e.g., dimensions (height, width, girth, etc.); body type; movement style; number/type of body parts; proportion (e.g. shoulder and hip ratio); head size; etc.

One or more characters (also referred to as an “avatar” or “model” herein) may be associated with a user where the user may control the character to facilitate a user's interaction with the virtual experience106.

In some implementations, a character may include components such as body parts (e.g., hair, arms, legs, etc.) and accessories (e.g., t-shirt, glasses, decorative images, tools, etc.). In some implementations, body parts of characters that are customizable include head type, body part types (arms, legs, torso, and hands), face types, hair types, and skin types, among others. In some implementations, the accessories that are customizable include clothing (e.g., shirts, pants, hats, shoes, glasses, etc.), weapons, or other tools.

In some implementations, for some asset types, e.g. shirts, pants, etc. the online virtual experience platform may provide users access to simplified 3D virtual object models that are represented by a mesh of a low polygon count, e.g. between about 20 and about 30 polygons.

In some implementations, the user may also control the scale (e.g., height, width, or depth) of a character or the scale of components of a character. In some implementations, the user may control the proportions of a character (e.g., blocky, anatomical, etc.). It may be noted that is some implementations, a character may not include a character virtual experience object (e.g., body parts, etc.) but the user may control the character (without the character virtual experience object) to facilitate the user's interaction with the virtual experience (e.g., a puzzle game where there is no rendered character game object, but the user still controls a character to control in-game action).

In some implementations, a component, such as a body part, may be a primitive geometrical shape such as a block, a cylinder, a sphere, etc., or some other primitive shape such as a wedge, a torus, a tube, a channel, etc. In some implementations, a creator module may publish a user's character for view or use by other users of the online virtual experience server102. In some implementations, creating, modifying, or customizing characters, other virtual experience objects, virtual experiences106, or virtual experience environments may be performed by a user using a I/O interface (e.g., developer interface) and with or without scripting (or with or without an application programming interface (API)). It may be noted that for purposes of illustration, characters are described as having a humanoid form. It may further be noted that characters may have any form such as a vehicle, animal, inanimate object, or other creative form.

In some implementations, the online virtual experience server102may store characters created by users in the data store120. In some implementations, the online virtual experience server102maintains a character catalog and virtual experience catalog that may be presented to users. In some implementations, the virtual experience catalog includes images of virtual experiences stored on the online virtual experience server102. In addition, a user may select a character (e.g., a character created by the user or other user) from the character catalog to participate in the chosen virtual experience. The character catalog includes images of characters stored on the online virtual experience server102. In some implementations, one or more of the characters in the character catalog may have been created or customized by the user. In some implementations, the chosen character may have character settings defining one or more of the components of the character.

In some implementations, a user's character can include a configuration of components, where the configuration and appearance of components and more generally the appearance of the character may be defined by character settings. In some implementations, the character settings of a user's character may at least in part be chosen by the user. In other implementations, a user may choose a character with default character settings or character setting chosen by other users. For example, a user may choose a default character from a character catalog that has predefined character settings, and the user may further customize the default character by changing some of the character settings (e.g., adding a shirt with a customized logo). The character settings may be associated with a particular character by the online virtual experience server102.

In some implementations, the client device(s)110may each include computing devices such as personal computers (PCs), mobile devices (e.g., laptops, mobile phones, smart phones, tablet computers, or netbook computers), network-connected televisions, gaming consoles, etc. In some implementations, a client device110may also be referred to as a “user device.” In some implementations, one or more client devices110may connect to the online virtual experience server102at any given moment. It may be noted that the number of client devices110is provided as illustration. In some implementations, any number of client devices110may be used.

In some implementations, each client device110may include an instance of the virtual experience application112, respectively. In one implementation, the virtual experience application112may permit users to use and interact with online virtual experience server102, such as control a virtual character in a virtual virtual experience hosted by online virtual experience server102, or view or upload content, such as virtual experiences106, images, video items, web pages, documents, and so forth. In one example, the virtual experience application may be a web application (e.g., an application that operates in conjunction with a web browser) that can access, retrieve, present, or navigate content (e.g., virtual character in a virtual environment, etc.) served by a web server. In another example, the virtual experience application may be a native application (e.g., a mobile application, app, virtual experience program, or a gaming program) that is installed and executes local to client device110and allows users to interact with online virtual experience server102. The virtual experience application may render, display, or present the content (e.g., a web page, a media viewer) to a user. In an implementation, the virtual experience application may also include an embedded media player (e.g., a Flash® or HTML5 player) that is embedded in a web page.

According to aspects of the disclosure, the virtual experience application may be an online virtual experience server application for users to build, create, edit, upload content to the online virtual experience server102as well as interact with online virtual experience server102(e.g., engage in virtual experiences106hosted by online virtual experience server102). As such, the virtual experience application may be provided to the client device(s)110by the online virtual experience server102. In another example, the virtual experience application may be an application that is downloaded from a server.

In some implementations, each developer device130may include an instance of the virtual experience application132, respectively. In one implementation, the virtual experience application132may permit a developer user(s) to use and interact with online virtual experience server102, such as control a virtual character in a virtual virtual experience hosted by online virtual experience server102, or view or upload content, such as virtual experiences106, images, video items, web pages, documents, and so forth. In one example, the virtual experience application may be a web application (e.g., an application that operates in conjunction with a web browser) that can access, retrieve, present, or navigate content (e.g., virtual character in a virtual environment, etc.) served by a web server. In another example, the virtual experience application may be a native application (e.g., a mobile application, app, virtual experience program, or a gaming program) that is installed and executes local to client device130and allows users to interact with online virtual experience server102. The virtual experience application may render, display, or present the content (e.g., a web page, a media viewer) to a user. In an implementation, the virtual experience application may also include an embedded media player (e.g., a Flash® or HTML5 player) that is embedded in a web page.

According to aspects of the disclosure, the virtual experience application132may be an online virtual experience server application for users to build, create, edit, upload content to the online virtual experience server102as well as interact with online virtual experience server102(e.g., provide and/or engage in virtual experiences106hosted by online virtual experience server102). As such, the virtual experience application may be provided to the client device(s)130by the online virtual experience server102. In another example, the virtual experience application132may be an application that is downloaded from a server. Game application132may be configured to interact with online virtual experience server102and obtain access to user credentials, user currency, etc. for one or more virtual experiences106developed, hosted, or provided by a virtual experience developer.

In some implementations, a user may login to online virtual experience server102via the virtual experience application. The user may access a user account by providing user account information (e.g., username and password) where the user account is associated with one or more characters available to participate in one or more virtual experiences106of online virtual experience server102. In some implementations, with appropriate credentials, a virtual experience developer may obtain access to virtual experience virtual objects, such as in-platform currency (e.g., virtual currency), avatars, special powers, accessories, that are owned by or associated with other users.

In general, functions described in one implementation as being performed by the online virtual experience server102can also be performed by the client device(s)110, or a server, in other implementations if appropriate. In addition, the functionality attributed to a particular component can be performed by different or multiple components operating together. The online virtual experience server102can also be accessed as a service provided to other systems or devices through suitable application programming interfaces (APIs), and thus is not limited to use in websites.

FIGS.2A-2Eillustrate an example process of generating a cage204from a 3D mesh201. In this example, the 3D mesh201is the leg portion of a 3D body mesh and the cage204is the corresponding leg portion of a body cage. The body cage204overlays the external surface/contours of the body cage, i.e., the body cage204at least partially surrounds or at least partially envelopes the body mesh201. The body mesh201may include multiple polygons and their vertices (not shown). For example, the polygons of the body mesh (as well as those of a clothing mesh) may be triangles, with the surface area of each triangle providing a “face” or “mesh face.” In this example, the illustrated body mesh201comprises an interpolated surface that provides a smooth contour while comprising the body vertices and the polygons. In practice, a body mesh201may comprise hundreds or thousands of body vertices and their corresponding polygons.

The illustrated body cage204comprises a plurality of cage vertices205connected by cage edges206to form triangular cage faces207. In other examples, the vertices may be connected in other polygonal fashions. The illustrated body cage204is an outer body cage with vertices205spaced apart from the vertices of the corresponding body mesh201, which serves as an inner body cage. The spacing is sufficiently small such that a clothing mesh (not shown) co-located with the outer body cage may be perceived as being worn by the avatar with body mesh201. For example, in a virtual space with described by metric units the cages may be separated by a length between a fraction of a centimeter and several centimeters. For example, the cages may be separated by a length between 0.5 cm to 10 cm. Different types of meshes may be separated by different typical distances. For example, a clothing mesh with a tight-fitting appearance might have an average separation of 0.5 cm, a normal-fitting appearance might have an average separation between 1-2 cm, or a loose-fitting appearance might have an average separation between 3-5 cm. In the illustrated example, the outer cage204has the same number of vertices as the corresponding body mesh201and the body mesh201serves as an inner cage. In other examples, the outer cage and the inner cage may have different numbers of vertices. For example, after positioning the outer cage vertices, as described below, the outer cage may be subject to vertex merging where vertexes within a threshold distance from each other are replaced with a single vertex. Accordingly, an outer cage vertex may correspond to one or more inner cage vertices. Further, the inner cage and outer cage may have different resolutions. For example, the outer cage may have a lower resolution than the inner cage such that the outer cage vertices correspond to a subset of the inner cage vertices. Further, the inner cage may have a lower resolution than the body mesh201such that the inner cage vertices correspond to a subset of the body mesh vertices. Transitively, the outer cage vertices may then correspond to a subset of the body mesh vertices or may correspond to a subset of a subset of the body mesh vertices.

As described further below, a signed distance function (SDF) approximant may be used to position the vertexes of a cage. A signed distance function for a 3D object maps points in the virtual space surrounding the object to the distance from the point to the object. An SDF approximant mimics the behavior of an SDF near the 3D object. For example, the output of an SDF approximant for a point may be within 1%-5% of the actual distance for points near the 3D object. For example, in a metric-unit 3D space, the SDF approximant might have a value within 3% of the actual SDF within a range of 1 cm to 5 cm from the surface of the 3D object. More generally, the SDF approximant may exhibit similar behaviors to a true SDF. For example, the SDF approximant is positive for points where the distance to the object is positive (i.e., the point is outside the mesh) and is negative where the distance to the object is negative (i.e., the point is inside the mesh). As another example, the SDF approximant may have gradient directionality similar to the true SDF; in other words, the SDF approximant is increasing where the SDF is increasing and the SDF approximant is decreasing where the SDF is decreasing.

FIGS.2B-2Dillustrate the field of an example SDF approximant for the mesh201. Field202(FIG.2C) illustrates positive valued isosurfaces (i.e., level sets) of the SDF appoximant. In other words, all points on a given line have the same (positive) approximate distance to mesh201. Field203(FIG.2D) illustrates negative valued isosurfaces. In other words, all points on a given line have the same (negative) approximate distance to mesh201. Contour line208illustrates the zero valued isosurface. In some examples, the vertices205of the outer cage are positioned in the positive field202near the zero-level isosurface208. For example, the outer cage may be positioned at average separations as described above with respect to clothing meshes. For example, the outer cage may be positioned at a range from 0.5 cm to 2 cm depending on a desired appearance, such as a tight-fitting or normal-fitting appearance. As another example, for loose-fitting clothing or larger clothing, such as clothing mimicking a winter coat, the separation may be 5 cm or more. As described in more detail below, the inner cage may be positioned according to the SDF approximant. For example, the inner cage vertices may be located on the zero-level isosurface208.

FIG.3is a block diagram illustrating an example method for generating a 3D object including a cage and a mesh using an SDF approximant. For example, the illustrated method may be used to generate a 3D avatar having a body cage, an article of clothing or other accessory for a 3D avatar, or combinations thereof.

Block301includes determining the SDF approximant for a 3D mesh. The SDF approximant may be determined by combining a plurality of radial basis functions (RBFs). As used herein, an RBF is a real valued function whose output depends on the distance between a point and a fixed point, where the fixed point is referred to as the “origin” for the RBF. In this description, the distance is generally the Euclidean distance, represented by |x−o| where x is the free variable and o is the origin. Other implementations may utilize other distance metrics, such as the Manhattan distance (i.e., the L1-norm), the sum of squared difference norm (i.e., the squared L2-norm), or other p-norm, for example.

In the example method, each RBF has an origin on the 3D mesh. For example, the origins may be located at mesh vertices. An RBF of this type is denoted |x−vi|, where viis a vertex of the mesh and x is the point to which the distance is evaluated. In other implementations, the origins may be located at other mesh positions such as face or edge centers, or may be located at a combination of different types of mesh elements. As an example, discussed further below, the RBFs may be combined as a weighted sum:

where i indexes the N vertices that are summed over and wiis the weight corresponding to the vertex vi. In some examples, N may be total number of vertices of the 3D mesh such that each vertex of the mesh has an associated RBF |x−vi| and an associated weight wi. In other examples, N may be a subset of the vertices. For example, the N vertices may be selected randomly or by a modulo on the vertex indices (e.g., every second, third, or nth vertex may be selected). As another example, every vertex in lower resolution portions of the mesh could be selected while a subset of the vertices in a higher resolution portion of the mesh could be selected. As described further below, the weights wimay be numbers or may be functions, such as functions of position. In some examples and as discussed further below, the SDF may further comprise various parameters or functions. For example, the SDF may have the form:

where c is a constant.

Block302includes generating a cage for the 3D mesh such that the cage overlays (i.e., surrounds or partially surrounds) the 3D mesh. As described above, the cage comprises a plurality of cage vertices. In some examples, the number of cage vertices is equal to the number of mesh vertices. For instance, the cage vertices may be created by duplicating the mesh vertices. As another example, the cage vertices may have a lower resolution than the mesh vertices. For instance, the cage vertices may be created by sampling the mesh vertices and duplicating the sampled mesh vertices.

Block302includes positioning the cage vertices using the SDF approximant. For example, block302may comprise positioning the cage vertices on an isosurface of the SDF. In some examples, the cage vertices are positioned on normal vectors of their corresponding mesh vertices. Block302is further described with reference toFIG.4for ease of explanation.FIG.4illustrates an example of positioning for a cage vertex410.FIG.4illustrates a portion401of a 3D mesh comprising four vertices401,402,403, and404. These four vertices form three triangular faces405,406, and407.

In some examples, block302may include determining a normal vector for each mesh vertex. InFIG.4, normal vector412corresponds to mesh vertex401. Normal412extends in both a positive direction (illustrated) out of the mesh and a negative direction (not illustrated) into the mesh. In some examples, block302may include determining the normal vector for each mesh vertex by averaging the normal vectors of the faces to which the vertex is connected. InFIG.4, vertex401is connected to faces405,406, and407, which have normals415,413, and414, respectively. The normals are illustrated as originating at point401. In practice, normals provide a direction that is orthogonal to their respective face, such that face normal vectors may originate at arbitrary positions. For example, the normal vector for face407at vertex404would be parallel to normal413. The normal vector412for mesh vertex401is the average of normal vectors413,414, and415. In other implementations, a greater or fewer number of face normals may be averaged to determine the vertex normals. For example, for a mesh that is subdivided into quadrilateral faces, four normals would be averaged to determine the vertex normals.

Block302further comprises positioning the cage vertices on the corresponding mesh vertex normals using the SDF approximant. For example, the gradient of the SDF approximant may be calculated along the vertex normals. The gradient may be calculated using finite difference methods applied to the SDF approximant for points on the vertex normals, using automatic differentiation methods applied to the SDF approximant for the vertex normal line, or using any other gradient calculation technique. The vertex gradients may be used to provide a directionality for the positioning of the cage vertices. For example, a cage vertex may initially be positioned at some location on the vertex normal. The sign of the SDF approximant may be evaluated to determine if the initial location is inside or outside the 3D mesh, and the gradient of the SDF approximant provides a direction to move the cage vertex towards the desired location. For example, the final location may be determined when the value of the SDF approximant reaches a distance parameter. For example, the cage vertex410is positioned at a distance411from its corresponding mesh vertex401. As described above, the SDF approximant approximates a true SDF. Accordingly, the value of the SDF approximant at point410may differ from the actual illustrated distance411. In some examples, the difference between the SDF approximant and a true SDF may depend on the distance from the origin vector. For example, as described above, the SDF approximant may be between 1%-5% (such as 3%) of the true distance at points close to the surface of the mesh (such as 1-5 cm from the mesh), while the SDF approximant may differ by 15% or more at points more distant from the mesh (such as 10 cm or more from the body mesh).

Block303comprises generating a 3D object that includes the 3D mesh and the cage. For example, block303may include instantiating a 3D object as an avatar body, item of avatar clothing, or accessory for an avatar, as described above with respect toFIG.1. Block303may further include causing the 3D object to be displayed. For example, the 3D objected may be displayed as an aspect of participation in a virtual world as described above.

For example, the 3D mesh may be an inner body cage of a body of a 3D avatar, and the cage may be an outer body cage for the 3D avatar. Block303may then include causing the 3D avatar to be displayed. For example, the 3D avatar may be displayed for customization of the avatar's clothing. In this example, the selected clothing may include mesh vertices that are located on the outer cage. As a further example, the 3D avatar may be displayed for participation in a virtual world as described above. In some examples, the outer body cage may serve as a simulated outer surface for simulated physical interactions (e.g., the outer body cage may serve as a “hit box”).

As another example, the 3D mesh may be an outer body cage of a body of a 3D avatar and the cage may be an outer clothing cage for a piece of clothing for the 3D avatar. In this example, generating the 3D object may include instantiating the 3D mesh and cages and causing the 3D avatar to be displayed according to the body of the 3D avatar, the piece of clothing, and the outer clothing cage. For example, the inner cage of an article of clothing may be located at an outer body cage. In these examples, the outer cage of the body may also be generated according to the method ofFIG.3or the outer cage of the body may be generated according to other cage generation methods. In some examples, the method may be used to generate multiple layers of clothing. For example, the cage may comprise an outer clothing cage for the second article of clothing and the 3D mesh may comprise a first outer clothing layer of a first article of clothing or a second inner clothing cage located at the first outer clothing cage.

As discussed with respect to block301ofFIG.3, determining an SDF approximant for a mesh may include determining weights for a plurality of RBFs and forming a weighted sum of such RBFs using the weights.FIG.5illustrates an example method of determining weights and forming a weighted sum. For example, the method ofFIG.5may be implemented for generating a body cage for a body mesh or may be implemented for generating a clothing cage for a clothing mesh. To assist in explanation,FIG.5will be described with reference toFIGS.6A and6B, which illustrate an example mesh wire frame (i.e., with faces unillustrated) and lines representing the RBFs evaluated for an example vertex at every other mesh vertex.

Block501includes evaluating the RBFs centered at each vertex at each other vertex. In other words, block501includes evaluating RBF(vi−vj) for all vertexes i,j within the mesh. For example,FIGS.6A-Binclude mesh600having vertices601a-601l. Block501includes evaluating the RBF between every pair of points.FIG.6Billustrates lines segments602b-602loriginating from vertex601a. For example, if the RBF is the Euclidean or absolute distance RBF(x)=|x|, then the RBF(vi−vj) for vj=601aand for all other viis the length of the corresponding line segment.

Block502includes determining weights for the RBFs by solving a linear system of equations. In this example, the linear system can be written as:

where i,j index over the vertices to be used for cage generation, wiare the weights and b(vi) are parameters representing properties or values configured according to the desired behavior of the SDF. When the RBF is the absolute distance, this may be written as:

In matrix notation, this may be written as:

where A is a matrix where Aij=RBF(vi−vj) (for example, Aij=|vi−vj|), w is a column vector of weights [wi] and b is a column vector of parameters [bi] where bi=b(vi). Solving this matrix for w may be performed by multiplying b by the inverse of A:

In this example, the matrix is symmetric and has a size is equal to the number of cage vertices. The solution to this system may be determined according to various automated linear algebra solving routines. Such methods for matrices the size of the number of vertices are typically very computationally inexpensive, such that they may be quickly performed for one or a large number of meshes by user devices or application servers. In some examples, the parameter is selected such that the sum of the RBFs at each mesh vertex is a common constant. In other words, the system to be solved may be written as:

This may be implemented by setting the column vector b to be [c] (i.e., b is a column vector consisting of the constant c repeated for the number of cage vertices). In one example, c=1 and the weights are determined by solving Aw=[1]. In these examples, the constant may be subtracted from the weighted sum to generate the SDF approximate. Accordingly, the SDF approximant may be written as:

and in the particular example where c=1:

FIGS.7A-7Billustrate the application of this SDF approximant to a 3D torso mesh701.FIG.7Aillustrates the original 3D mesh701.FIG.7Billustrates various aspects702of the SDF approximant for mesh701, including gradient vectors703at various locations arrows703, contour lines704for a slice of the SDF on the xy plane, and the zero level isosurface705. As illustrated, the gradient vectors703at points outside the mesh point outwards, the contour lines704surround the mesh701and have a smooth profile that reflects increasing distance from the mesh, and the zero level isosurface705closely matches the mesh701.

In some examples, it may be beneficial to adjust the SDF approximant to control the magnitude of the gradient field near the 3D mesh. For example, this may assist with gradient walking techniques for cage vertex placement as described above with respect to block302ofFIG.3. Block503and504illustrate operations to provide normalized gradients. Block503includes determining the magnitudes of the gradients (i.e., slopes of the SDF approximant) at the mesh vertices corresponding to the cage being generated. Block503further includes averaging these magnitudes to determine an average gradient magnitude for the set of mesh vertices. Block504includes normalizing the weights widetermined in step502according to the average gradient magnitude to generate normalized weights w′i.

In these examples, block505is performed to generate the final SDF approximant to be used in cage generation. Block505includes generating the SDF approximant as a weighted sum of the RBFs using the normalized weights. Accordingly, in the example of c=1:

As discussed with respect to block301ofFIG.3, determining an SDF approximant for a mesh may include determining weights for a plurality of RBFs and forming a weighted sum of such RBFs using the weights.FIG.8illustrates a method of determining weights for the SDF using the normal vectors of the mesh vertices. Compared to the weight determination method ofFIG.5, this method may result in an SDF approximant with more fidelity to the gradient of a true SDF. Accordingly, this method may be useful in clothing cage determination, but may also be used in body cage generation.

In block801, the RBFs for each vertex are evaluated at a pair of offset points located on the vertex normals.FIG.9illustrates a portion900of an example mesh with vertices901a,901b, vertex normals902a,902b, and point pairs903a,904a, and903b,904b. Each of the points are offset an equal absolute distance from their respective vertices. One point903a,903bis located at a positive offset distance (i.e., an offset distance in the positive normal direction) and the other point904a,904bis located at a negative offset distance (i.e., an offset distance in the negative normal direction). The respective vertices901a,901b, are located in the center of the normal line connecting the pairs of points. In the described example, the absolute offset distance e is the same for each vertex in the mesh. In other examples, different offset distances may be used for different vertices. In some examples, e may be defined according to a desired spacing between meshes. For example, e may be set according to a desired spacing between a body mesh and a clothing mesh, as discussed above (e.g., between 0.5 cm and 5 cm, depending on desired appearance). The RBF for each vertex is evaluated at each point of the point pairs. In other words RBF(vi−eN−vj) and RBF(vi+eN+vj) is evaluated for all vertices i and j. Lines905a-dillustrate |vi−eN−vj|, |vi+eN−vj| for the illustrated vertices and point pairs.

Block802includes solving the nonlinear system resulting from setting the weighted sum at the respective pairs of points on the normal vectors to be equal to the signed distance from each point to its respective vertex. In the illustrated example, where each point is offset the same absolute distance, this nonlinear system may be written as:

where i and j index over the cage vertices. Here, due to the nonlinearity of the system, the weights may be functions of position rather than constants.

Solving this system may be performed using various automatic nonlinear solving techniques. Compared to the method ofFIG.5, this system requires solving for twice as many terms (i.e., the corresponding matrix size is twice that ofFIG.5). However, the solution provides a unitary gradient along the normals in the vicinity of the vertices because the method enforces a slope of 1 for the line segment between the two offset points.

In some examples, it may be desirable for the SDF approximant to have a more accurate gradient at longer distances from the mesh. In these examples, block802may include providing additional constraints to the system. For example, with a small offset e, the magnitude of the gradient may increasingly deviate from the true SDF at increasing distance from the mesh. In these examples, block802may include calculating the weight functions such that the weighted sum of the plurality of RBFs equals a constraint constant at constraining distances around the 3D mesh. For example, a cube of points {(L,L,L), (−L,L,L), (L,−L,L), (−L,−L,L), (L,L,−L), (−L,L,−L), (L,−L,−L), (−L,−L,−L)} may be selected where L is the constraint constant. In this example, an additional 8 equations are added to the system:

for x in the set {(L,L,L), (−L,L,L), (L,−L,L), (−L,−L,L), (L,L,−L), (−L,L,−L), (L,−L,−L), (−L,−L,−L)}. In other examples, other constraining volumes may be selected and different constraint constants may be used for different elements of the additional constraint equations. In typical examples, the constraint constant is longer than the characteristic distance of the mesh (i.e., the length of the longest side of a bounding box containing the mesh). As an example, the constraint constant L may be set to be 10%-50% longer than the characteristic distance (e.g., L between 1.1*BLand 1.5*BLwhere BLis the longest length of a bounding box containing a body mesh).

In these examples, block803is performed to generate the final SDF approximant to be used in cage generation. Block505includes generating the SDF approximant as a weighted sum of the RBFs using the weight functions determined in block802.

FIG.10is a block diagram of an example computing device1000which may be used to implement one or more features described herein. In one example, device1000may be used to implement a computer device (e.g.102and/or110ofFIG.1), and perform appropriate method implementations described herein. Computing device1000can be any suitable computer system, server, or other electronic or hardware device. For example, the computing device1000can be a mainframe computer, desktop computer, workstation, portable computer, or electronic device (portable device, mobile device, cell phone, smartphone, tablet computer, television, TV set top box, personal digital assistant (PDA), media player, game device, wearable device, etc.). In some implementations, device1000includes a processor1002, a memory1004, input/output (I/O) interface1006, and audio/video input/output devices1014.

Processor1002can be one or more processors and/or processing circuits to execute program code and control basic operations of the device1000. A “processor” includes any suitable hardware and/or software system, mechanism or component that processes data, signals or other information. A processor may include a system with a general-purpose central processing unit (CPU), multiple processing units, dedicated circuitry for achieving functionality, or other systems. Processing need not be limited to a particular geographic location, or have temporal limitations. For example, a processor may perform its functions in “real-time,” “offline,” in a “batch mode,” etc. Portions of processing may be performed at different times and at different locations, by different (or the same) processing systems. A computer may be any processor in communication with a memory.

Memory1004is typically provided in device1000for access by the processor1002, and may be any suitable processor-readable storage medium, e.g., random access memory (RAM), read-only memory (ROM), Electrical Erasable Read-only Memory (EEPROM), Flash memory, etc., suitable for storing instructions for execution by the processor, and located separate from processor1002and/or integrated therewith. Memory1004can store software operating on the server device1000by the processor1002, including an operating system1008, one or more applications1010, e.g., an audio spatialization application and application data1012. In some implementations, application1010can include instructions that enable processor1002to perform the functions (or control the functions of) described herein, e.g., some or all of the methods described with respect toFIGS.3,5, and8.

For example, applications1010can include an audio spatialization module1012, which as described herein can provide audio spatialization within an online virtual experience server (e.g.,102). Elements of software in memory1004can alternatively be stored on any other suitable storage location or computer-readable medium. In addition, memory1004(and/or other connected storage device(s)) can store instructions and data used in the features described herein. Memory1004and any other type of storage (magnetic disk, optical disk, magnetic tape, or other tangible media) can be considered “storage” or “storage devices.”

I/O interface1006can provide functions to enable interfacing the server device1000with other systems and devices. For example, network communication devices, storage devices (e.g., memory and/or data store120), and input/output devices can communicate via interface1006. In some implementations, the I/O interface can connect to interface devices including input devices (keyboard, pointing device, touchscreen, microphone, camera, scanner, etc.) and/or output devices (display device, speaker devices, printer, motor, etc.).

The audio/video input/output devices1014can include a user input device (e.g., a mouse, etc.) that can be used to receive user input, a display device (e.g., screen, monitor, etc.) and/or a combined input and display device, that can be used to provide graphical and/or visual output.

For ease of illustration,FIG.10shows one block for each of processor1002, memory1004, I/O interface1006, and software blocks of operating system1008and virtual experience application1010. These blocks may represent one or more processors or processing circuitries, operating systems, memories, I/O interfaces, applications, and/or software engines. In other implementations, device1000may not have all of the components shown and/or may have other elements including other types of elements instead of, or in addition to, those shown herein. While the online virtual experience server102is described as performing operations as described in some implementations herein, any suitable component or combination of components of online virtual experience server102or similar system, or any suitable processor or processors associated with such a system, may perform the operations described.

A user device can also implement and/or be used with features described herein. Example user devices can be computer devices including some similar components as the device1000, e.g., processor(s)1002, memory1004, and I/O interface1006. An operating system, software and applications suitable for the client device can be provided in memory and used by the processor. The I/O interface for a client device can be connected to network communication devices, as well as to input and output devices, e.g., a microphone for capturing sound, a camera for capturing images or video, a mouse for capturing user input, a gesture device for recognizing a user gesture, a touchscreen to detect user input, audio speaker devices for outputting sound, a display device for outputting images or video, or other output devices. A display device within the audio/video input/output devices1014, for example, can be connected to (or included in) the device1000to display images pre-and post-processing as described herein, where such display device can include any suitable display device, e.g., an LCD, LED, or plasma display screen, CRT, television, monitor, touchscreen, 3-D display screen, projector, or other visual display device. Some implementations can provide an audio output device, e.g., voice output or synthesis that speaks text.

One or more methods described herein can be run in a standalone program that can be run on any type of computing device, a program run on a web browser, a mobile application (“app”) run on a mobile computing device (e.g., cell phone, smart phone, tablet computer, wearable device (wristwatch, armband, jewelry, headwear, goggles, glasses, etc.), laptop computer, etc.). In one example, a client/server architecture can be used, e.g., a mobile computing device (as a client device) sends user input data to a server device and receives from the server the final output data for output (e.g., for display). In another example, all computations can be performed within the mobile app (and/or other apps) on the mobile computing device. In another example, computations can be split between the mobile computing device and one or more server devices.