IP Library › Granted Patent US 12,190,427
Granted Patent B2
US 12,190,427 · App. 17/965,213 · Granted Jan 7, 2025

Hidden surface removal for layered clothing for an avatar body

Inventors: Sergei Makeev (Foster City, CA); Byungmoon Kim (San Jose, CA); Si Chen (San Mateo, CA)
Assignee: Roblox Corporation
G06T13/40G06T19/20G06T2210/16
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,190,427
App. No.
17/965,213
Granted
Jan 7, 2025
Kind
B2
Abstract

An automated cage-to-cage fitting technique is used to fit three-dimensional (3D) geometry to target 3D geometry for 3D avatars in a 3D environment, such as an online game. Each graphical representation of items of clothing is provided with an inner cage and an outer cage. The inner cage of a clothing item (a current layer) is mapped to the outer cage of another clothing item (a previous/underlying layer) that has been fitted on the 3D avatar. This mapping enables the current layer to conform to the shape of the previous layer. The technique allows any body geometry to be fitted with any clothing geometry, including enabling layers of clothing to be fitted over underlying layer(s). Hidden surface removal (HSR) operations may be performed to identify surfaces of an underlying layer that are hidden by an overlying layer, and such hidden surfaces are not rendered.

Claims (75)

1. A computer-implemented method to provide layered clothing on three-dimensional (3D) avatars, the method comprising:

identifying body feature points of a body cage of a 3D avatar having an avatar body represented by a body mesh, wherein the body cage overlies the body mesh;

mapping inner feature points, of an inner cage of a first piece of clothing, to the body feature points of the body cage to obtain a deformed first piece of clothing that conforms to the avatar body;

performing first hidden surface removal (HSR) operations to identify faces of the body cage that are hidden by the deformed first piece of clothing;

fitting the deformed first piece of clothing onto the avatar body by at least partially enveloping the avatar body with the deformed first piece of clothing, wherein faces of the avatar body that correspond to the identified faces of the body cage are not rendered;

mapping inner feature points, of an inner cage of a second piece of clothing, to outer feature points of an outer cage of the deformed first piece of clothing to obtain a deformed second piece of clothing that conforms to the outer cage of the first piece of clothing;

performing second HSR operations to identify faces of the outer cage of the deformed first piece of clothing that are hidden by the deformed second piece of clothing; and

fitting the deformed second piece of clothing onto the avatar body by at least partially enveloping the avatar body, having the deformed first piece of clothing fitted thereon, with the deformed second piece of clothing, wherein faces of the deformed first piece of clothing that correspond to the identified faces of the outer cage are not rendered.

2. The method of claim 1 , wherein performing the second HSR operations includes:

for a first face, of a mesh of the deformed first piece of clothing, which is hidden, identifying at least a first face of the outer cage of the first piece of clothing that is related to the hidden first face of the deformed first piece of clothing; and

for a second face, of the mesh of the deformed first piece of clothing, that is visible, identifying at least a second face of the outer cage of the first piece of clothing that is related to the visible second face of the deformed first piece of clothing,

wherein the related at least the second face is used in a subsequent visibility determination with respect to a third piece of clothing, and wherein the related at least the first face is hidden with respect to the third piece of clothing.

3. The method of claim 1 , wherein performing the second HSR operations to identify the faces of the outer cage of the deformed first piece of clothing that are hidden includes:

shooting a plurality of rays from at least one point on a face of the outer cage of the first piece of clothing;

determining the face to be visible if at least one ray of the plurality of rays misses the second piece of clothing; and

determining the face to be hidden if all of the plurality of rays hit the second piece of clothing.

4. The method of claim 1 , wherein performing the first and second HSR operations includes:

with respect to the first piece of clothing, encoding first visibility of a particular face of the body cage using at least a first slice of a sphere;

with respect to the second piece of clothing, encoding second visibility of the particular face of the body cage using at least a second slice of the sphere; and

performing a logical operation between the encoded first visibility and the encoded second visibility to determine visibility of the particular face of the body cage when both the first and second pieces of clothing are fitted onto the avatar body.

5. The method of claim 1 , wherein performing the first HSR operations includes performing a clustering technique so that first faces of the avatar body that hide together are clustered into a first group and second faces of the avatar body that show together are clustered into a second group.

6. The method of claim 1 , further comprising shrinking at least one of the body cage and the outer cage of the first piece of clothing, wherein the shrinking reduces bleed through by an underlying face.

7. The method of claim 1 , further comprising adjusting a puffiness caused by the deformed second piece of clothing being fitted over the deformed first piece of clothing.

8. A non-transitory computer-readable medium having instructions stored thereon that, responsive to execution by a processor, cause the processor to perform or control performance of operations to:

identify body feature points of a body cage of a 3D avatar having an avatar body represented by a body mesh, wherein the body cage overlies the body mesh;

map inner feature points, of an inner cage of a first piece of clothing, to the body feature points of the body cage to obtain a deformed first piece of clothing that conforms to the avatar body;

perform first hidden surface removal (HSR) operations to identify faces of the body cage that are hidden by the deformed first piece of clothing;

fit the deformed first piece of clothing onto the avatar body by at least partially enveloping the avatar body with the deformed first piece of clothing, wherein faces of the avatar body that correspond to the identified faces of the body cage are not rendered;

map inner feature points, of an inner cage of a second piece of clothing, to outer feature points of an outer cage of the deformed first piece of clothing to obtain a deformed second piece of clothing that conforms to the outer cage of the first piece of clothing;

perform second HSR operations to identify faces of the outer cage of the deformed first piece of clothing that are hidden by the deformed second piece of clothing; and

fit the deformed second piece of clothing onto the avatar body by at least partially enveloping the avatar body, having the deformed first piece of clothing fitted thereon, with the deformed second piece of clothing, wherein faces of the deformed first piece of clothing that correspond to the identified faces of the outer cage are not rendered.

9. The non-transitory computer-readable medium of claim 8 , wherein the operations to perform the second HSR operations include operations to:

for a first face, of a mesh of the deformed first piece of clothing, that is hidden, identify at least a first face of the outer cage of the first piece of clothing that is related to the hidden first face of the deformed first piece of clothing; and

for a second face, of the mesh of the deformed first piece of clothing, that is visible, identify at least a second face of the outer cage of the first piece of clothing that is related to the visible second face of the deformed first piece of clothing,

wherein the related at least the second face is used in a subsequent visibility determination with respect to a third piece of clothing, and wherein the related at least the first face is hidden with respect to the third piece of clothing.

10. The non-transitory computer-readable medium of claim 8 , wherein the operations to perform the second HSR operations, to identify the faces of the outer cage of the deformed first piece of clothing that are hidden, include operations to:

shoot a plurality of rays from at least one point on a face of the outer cage of the first piece of clothing;

determine the face to be visible if at least one ray of the plurality of rays misses the second piece of clothing; and

determine the face to be hidden if all of the plurality of rays hit the second piece of clothing.

11. The non-transitory computer-readable medium of claim 8 , wherein the operations to perform the first and second HSR operations include operations to:

with respect to the first piece of clothing, encode first visibility of a particular face of the body cage using at least a first slice of a sphere;

with respect to the second piece of clothing, encode second visibility of the particular face of the body cage using at least a second slice of the sphere; and

perform a logical operation between the encoded first visibility and the encoded second visibility to determine visibility of the particular face of the body cage when both the first and second pieces of clothing are fitted onto the avatar body.

12. The non-transitory computer-readable medium of claim 8 , wherein the operations to perform the first HSR operations includes operations to:

perform a clustering technique so that first faces of the avatar body that hide together are clustered into a first group and second faces of the avatar body that show together are clustered into a second group.

13. The non-transitory computer-readable medium of claim 8 , wherein the instructions further cause the processor to perform operations to:

shrink at least one of the body cage and the outer cage of the first piece of clothing, wherein the shrinking reduces bleed through by an underlying face.

14. An apparatus, comprising:

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 to:

identify body feature points of a body cage of a 3D avatar having an avatar body represented by a body mesh, wherein the body cage overlies the body mesh;

map inner feature points, of an inner cage of a first piece of clothing, to the body feature points of the body cage to obtain a deformed first piece of clothing that conforms to the avatar body;

perform first hidden surface removal (HSR) operations to identify faces of the body cage that are hidden by the deformed first piece of clothing;

fit the deformed first piece of clothing onto the avatar body by at least partially enveloping the avatar body with the deformed first piece of clothing, wherein faces of the avatar body that correspond to the identified faces of the body cage are not rendered;

map inner feature points, of an inner cage of a second piece of clothing, to outer feature points of an outer cage of the deformed first piece of clothing to obtain a deformed second piece of clothing that conforms to the outer cage of the first piece of clothing;

perform second HSR operations to identify faces of the outer cage of the deformed first piece of clothing that are hidden by the deformed second piece of clothing; and

fit the deformed second piece of clothing onto the avatar body by at least partially enveloping the avatar body, having the deformed first piece of clothing fitted thereon, with the deformed second piece of clothing, wherein faces of the deformed first piece of clothing that correspond to the identified faces of the outer cage are not rendered.

15. The apparatus of claim 14 , wherein the operations to perform the second HSR operations include operations to:

for a first face, of a mesh of the deformed first piece of clothing, that is hidden, identify at least a first face of the outer cage of the first piece of clothing that is related to the hidden first face of the deformed first piece of clothing; and

for a second face, of the mesh of the deformed first piece of clothing, that is visible, identify at least a second face of the outer cage of the first piece of clothing that is related to the visible second face of the deformed first piece of clothing,

wherein the related at least the second face is used in a subsequent visibility determination with respect to a third piece of clothing, and wherein the related at least the first face is hidden with respect to the third piece of clothing.

16. The apparatus of claim 14 , wherein the operations to perform the second HSR operations, to identify the faces of the outer cage of the deformed first piece of clothing that are hidden, include operations to:

shoot a plurality of rays from at least one point on a face of the outer cage of the first piece of clothing;

determine the face to be visible if at least one ray of the plurality of rays misses the second piece of clothing; and

determine the face to be hidden if all of the plurality of rays hit the second piece of clothing.

17. The apparatus of claim 14 , wherein the operations to perform the first and second HSR operations include operations to:

with respect to the first piece of clothing, encode first visibility of a particular face of the body cage using at least a first slice of a sphere;

with respect to the second piece of clothing, encode second visibility of the particular face of the body cage using at least a second slice of the sphere; and

perform a logical operation between the encoded first visibility and the encoded second visibility to determine visibility of the particular face of the body cage when both the first and second pieces of clothing are fitted onto the avatar body.

18. The apparatus of claim 14 , wherein the operations to perform the first HSR operations includes operations to:

perform a clustering technique so that first faces of the avatar body that hide together are clustered into a first group and second faces of the avatar body that show together are clustered into a second group.

19. The apparatus of claim 14 , wherein the instructions further cause the processor to perform operations to:

shrink at least one of the body cage and the outer cage of the first piece of clothing, wherein the shrinking reduces bleed through by an underlying face.

20. The apparatus of claim 14 , wherein the instructions further cause the processor to perform operations to:

adjust a puffiness caused by the deformed second piece of clothing being fitted over the deformed first piece of clothing.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jan 6, 2023
From: MAKEEV, SERGEI; KIM, BYUNGMOON; CHEN, SI
To: ROBLOX CORPORATION
Reel/Frame 062293/0517 →
Continuity (3)
Provisional Application 63404925 · Sep 8, 2022
Provisional Application 63255489 · Oct 14, 2021
Related Publication 20230124297A1 · Apr 20, 2023
References Cited (62)
US 11321916B1 · Zhang et al. · 2022 [cited by applicant]
US 20070273711A1 · Maffei · 2007 [cited by applicant]
US 20100321386A1 · Lin et al. · 2010 [cited by applicant]
US 20130034276A1 · Hibbard · 2013 [cited by applicant]
US 20130057544A1 · Oh · 2013 [cited by applicant]
US 20140267268A1 · Tipton · 2014 [cited by applicant]
US 20150029198A1 · Sumner et al. · 2015 [cited by applicant]
US 20160171296A1 · Ikenoue · 2016 [cited by examiner]
US 20160284018A1 · Adeyoola et al. · 2016 [cited by applicant]
US 20160379419A1 · Khalili et al. · 2016 [cited by applicant]
US 20170032579A1 · Eisemann et al. · 2017 [cited by applicant]
US 20170161948A1 · Hua et al. · 2017 [cited by applicant]
US 20180315254A1 · Grant et al. · 2018 [cited by applicant]
US 20190088033A1 · Kuchibotla et al. · 2019 [cited by applicant]
US 20190362529A1 · Wedig et al. · 2019 [cited by applicant]
US 20190371080A1 · Sminchisescu · 2019 [cited by examiner]
US 20200035010A1 · Kim et al. · 2020 [cited by applicant]
US 20210082179A1 · Fedyukov · 2021 [cited by examiner]
US 20210150806A1 · Guler et al. · 2021 [cited by applicant]
US 20210224765A1 · Siddique · 2021 [cited by examiner]
US 20220292791A1 · Makeev et al. · 2022 [cited by applicant]
EP 3029635 · 2016 [cited by applicant]
JP 2016110652 · 2016 [cited by applicant]
KR 1020190070884 · 2019 [cited by applicant]
USPTO, Written Opinion for International Patent Application No. PCT/US2022/046523, Feb. 8, 2023, 11 pages. [cited by applicant]
USPTO, International Search Report for International Patent Application No. PCT/US2022/046523, Feb. 8, 2023, 2 pages. [cited by applicant]
“APB: Creating a Powerful Customisation System for a Persistent Online Action Game”, Retrieved from Internet: https://macropolygon.files.wordpress.com/2010/08/apb_customisation_gdc2010.pptx, 2010, 49 pages. [cited by applicant]
“RBF Character Conversion”, Retrieved from Internet: http://www.polygon.me/2018/08/rbf-character-conversion.html, Aug. 9, 2018, 3 pages. [cited by applicant]
Agafonkin, “Edgebreaker, the heart of Google Draco”, Retrieved from Internet: https://observablehq.com/@mourner/edgebreaker-the-heart-of-google-draco, Oct. 16, 2019, 9 pages. [cited by applicant]
Anjyo, et al., “Scattered Data Interpolation for Computer Games”, SIGGRAPH 2014 Course Notes, 2014, 69 pages. [cited by applicant]
Appleby, et al., “Punching Above Your Weight: Small Art Teams, Big Games”, Video; retrieved from Internet: https://www.gdcvault.com/play/1014359/Punching-Above-Your-Weight-Small, 2011, 4 pages. [cited by applicant]
Bailey, et al., “Fast and deep deformation approximations”, ACM Transactions on Graphics, vol. 37, Issue 4, Aug. 2018, 12 pages. [cited by applicant]
Barak, “Adaptive Clothing System in Kingdom Come: Deliverance”, Retrieved from Internet: https://www.gdcvault.com/play/1022822/Adaptive-Clothing-System-in-Kingdom; see also video at: https://www.gdcvault.com/play/102277… [cited by applicant]
Botsch, et al., “Real-Time Shape Editing using Radial Basis Functions”, Eurographics 2005, vol. 24, No. 3, 2005, 11 pages. [cited by applicant]
De Goes, et al., “Mesh Wrap based on Affine-Invariant Coordinates”, ACM SIGGRAPH 2019 Talks, 2019, 2 pages. [cited by applicant]
Desbrun, et al., “Implicit Fairing of Irregular Meshes using Diffusion and Curvature Flow”, SIGGRAPH '99: Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques, Jul. 1999, 8 pages. [cited by applicant]
Feng, et al., “Avatar Reshaping and Automatic Rigging Using a Deformable Model”, Proceedings of the 8th ACM SIGGRAPH Conference on Motion in Games, 2015, 8 pages. [cited by applicant]
Fortier, “Universal Character System in Saints Row 2”, Video; retrieved from Internet: https://www.gdcvault.com/play/1289/Universal-Character-System-in-SAINTS, 2009, 3 pages. [cited by applicant]
Gagliardi, et al., “A Two-Step Mesh Adaption Tool Based on RBF with application to Turbomachinery Optimization Loops”, Evolutionary and Deterministic Methods for Design Optimization and Control With Applications to Indu… [cited by applicant]
Godard, “Plugin and Nodal Demo Reel 2016”, Video; retrieved from Internet: https://vimeo.com/166291982#t=3m33s, 2016, 3 pages. [cited by applicant]
Kim, et al., “GeoFilter: Geometric Selection of Mesh Filter Parameters”, Eurographics, Computer Graphics Forum, available at https://faculty.cc.gatech.edu/˜jarek/papers/GeoFilter.pdf, Jan. 31, 2005, 8 pages. [cited by applicant]
Lalleve, et al., “Character Pipeline and Customization System for ‘Far Cry Primal’”, Retrieved from Internet: https://www.gdcvault.com/play/1024578/Character-Pipeline-and-Customization-System, 2017, 104 pages. [cited by applicant]
Li, et al., “Fitting 3D garment models onto individual human models”, Computers and Graphics 34, 2010, pp. 742-755. [cited by applicant]
Nair, “Innovations in The Sims 4 Character Creator”, Retrieved from Internet: https://www.gdcvault.com/play/1022086/Innovations-in-The-Sims-4, 2015, 89 pages. [cited by applicant]
Niu, et al., “Radial basis function mesh deformation based on dynamic control points”, Aerospace Science and Technology 64; retrieved from Internet: https://dacemirror.sci-hub.tw/journal-article/b485b3a622b0953d5a8c898a… [cited by applicant]
Rossignac, “Edgebreaker: Connectivity compression for triangle meshes”, GVU Technical Report GIT-GVU-98-35, IEEE Transactions on Visualization and Computer Graphics, Jan.-Mar. 1999, 15 pages. [cited by applicant]
Schiffmann, “RBF Interpolation for Mesh Deformation”, Retrieved from Internet: https://imsc.uni-graz.at/haasegu/Lectures/GPU_CUDA/WS16/2016-11-03-HPC1-Schiffmann-RBF.pdf, 2016, 12 pages. [cited by applicant]
Selim MM, et al., “Mesh Deformation Approaches—A Survey”, J. Phys. Math., vol. 7, Issue 2, 2016, 9 pages. [cited by applicant]
Shepherd, “Building Customizable Characters for Bungie's Destiny”, Video; retrieved from Internet: https://www.gdcvault.com/play/1020412/Building-Customizable-Characters-for-Bungie, 2014, 4 pages. [cited by applicant]
Stokan, “Ultimate Customization in Character Creation—Challenges and Innovations”, Video; retrieved from Internet: https://www.gdcvault.com/play/1014370/Ultimate-Customization-in-Character-Creation, 2011, 4 pages. [cited by applicant]
Taubin, “A Signal Processing Approach to Fair Surface Design”, SIGGRAPH '95: Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques, Sep. 1995, 8 pages. [cited by applicant]
Torok, et al., “REDengine 3 Character Pipeline”, Retrieved from Internet: http://fileserv.polter.pl/1594-CDPRED_SIGGRAPH.pdf, 2013, 53 pages. [cited by applicant]
USPTO, Written Opinion for International Patent Application No. PCT/US2022/015246, May 11, 2022, 12 pages. [cited by applicant]
USPTO, International Search Report for International Patent Application No. PCT/US2022/015246, May 11, 2022, 2 pages. [cited by applicant]
USPTO, Non-final Office Action for U.S. Appl. No. 17/375,066, May 24, 2022, 15 pages. [cited by applicant]
USPTO, Notice of Allowance for U.S. Appl. No. 17/375,066, Nov. 8, 2022, 9 pages. [cited by applicant]
Vaisse, “Ubisoft Cloth Simulation: Performance Postmortem and Journey from C++ to Computer Shaders”, Retrieved from Internet: https://www.gdcvault.com/play/1022421/Ubisoft-Cloth-Simulation-Performance-Postmortem, 2015, … [cited by applicant]
Wang, et al., “Delaunay graph-based moving mesh method with damping functions”, Chinese Journal of Aeronautics, vol. 31, Issue 11, Nov. 2018, pp. 2093-2103. [cited by applicant]
Wang, et al., “Mesh deformation on 3D complex configurations using multistep radial basis functions interpolation”, Chinese Journal of Aeronautics, 31(4), 2018, pp. 660-671. [cited by applicant]
USPTO, International Search Report for International Patent Application No. PCT/US2022/046528, Jan. 31, 2023, 2 pages. [cited by applicant]
USPTO, Written Opinion for International Patent Application No. PCT/US2022/046528, Jan. 31, 2023, 6 pages. [cited by applicant]
“Japanese Office Action in JP Application No. 2023-556822”, Sep. 9, 2024, 12 Pages. [cited by applicant]
Cited By (1)
US 12,726,658