Precomputing data for an interactive system having discrete control inputs

• US 10,147,220 B2
• Filed: 03/13/2015
• Issued: 12/04/2018
• Est. Priority Date: 03/14/2014
• Status: Active Grant

• Current Assignee: Carnegie Mellon University, Regents of the University of California (University of California)
• Original Assignee: Carnegie Mellon University
• Inventors: Stanton, Matthew, Treuille, Adrien, Fatahalian, Kayvon, O'Brien, James, Humberston, Ben, Kase, Brandon
• Primary Examiner(s): Buttram, Todd
• Application Number:
  US15/126,149
• Publication Number:
  US 20170076488A1
• Time in Patent Office: 1,362 Days
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 13/60 of natural phenomena, e.g. rain, snow, water or plants
• CPC Class Codes: G06T 15/503 Blending, e.g. for anti-aliasing
• CPC Class Codes: G06T 2207/20092 Interactive image processing based on input by user

Abstract

A computer-implemented method includes accessing a plurality of sets of outputs for an interactive animation, with each set of outputs being associated with a different sequence of a plurality of sequences of discrete control inputs, and with each set of outputs comprising an output that provides a stored portion of the animation; and transmitting, to a client device, information indicative of at least one of the plurality of sets of outputs for the animation and the output that provides the stored portion of the animation, which when rendered by the client device causes the animation to be presented to a user.

Claims

1. A method comprising:

accessing a plurality of sets of outputs for an interactive animation, with each set of outputs being associated with a different sequence of a plurality of sequences of discrete control inputs, and with each set of outputs comprising an output that provides a stored portion of the interactive animation;

identifying a particular output of the plurality of sets of outputs that provides a blend of first and second stored portions of the interactive animation, the blend being associated with an error value above a threshold, wherein the error value represents a difference between the first stored portion of the interactive amination included in the blend and the second stored portion of the interactive animation included in the blend;

in accordance with the error value being above the threshold, modifying the particular output to provide a third stored portion of the interactive animation;

replacing, in the particular output, the blend of the first and second stored portions of the interactive animation with the third stored portion; and

transmitting, to a client device, information indicative of at least one of the plurality of sets of outputs that includes the particular output that provides the third stored portion of the interactive animation, which when rendered by the client device causes the interactive animation to be presented to a user.

2. The method of claim 1, further comprising generating the plurality of sets of outputs for the interactive animation prior to transmitting the information to the client device.

3. The method of claim 2, wherein generating the plurality of sets of outputs for the interactive animation comprises:

generating a directed graph comprising a plurality of vertices and a plurality of edges, with each of the plurality of vertices representing a state of the interactive animation that is responsive to a discrete control input, with each of the plurality of vertices connected to a number of outgoing edges where the number is equivalent to a number of possible discrete control inputs, and with each edge connecting two of the plurality of vertices and representing an output of the plurality of sets of outputs.

4. The method of claim 2, wherein generating the plurality of sets of outputs for the interactive animation comprises:

generating the plurality of sets of outputs for the interactive animation based on a heuristic user model.

5. The method of claim 2, wherein generating the plurality of sets of outputs for the interactive animation comprises:

generating the plurality of sets of outputs for the interactive animation based on receiving, from a plurality of client devices, sequences of discrete control inputs that are associated with sets of outputs of the plurality of sets of outputs for the interactive animation.

6. The method of claim 2, wherein generating the plurality of sets of outputs for the interactive animation comprises:

generating the plurality of sets of outputs for the interactive animation using a kernel density estimator combined with a Markov prior.

7. The method of claim 1, wherein a stored portion of the interactive animation comprises at least one of a static image, a sequence of static images, one or more signed distance functions, or a sequence of polygon meshes.

8. The method of claim 1, wherein the output that provides the stored portion of the interactive animation is a first output that provides a first stored portion of the interactive animation, and the method further comprises:

receiving a sequence of discrete control inputs for the at least one of the plurality of sets transmitted;

generating, by one or more processing devices, a second output for the at least one of the sets of outputs in accordance with the received sequence of discrete control inputs so that the second output provides a second stored portion of the interactive animation, the second output to be provided after the first output of the set of outputs during presentation of the interactive animation; and

updating the plurality of sets of outputs for the interactive animation with the second output for the set of outputs associated with the received sequence of discrete control inputs.

9. The method of claim 8, wherein each set of outputs of the accessed plurality of sets of outputs comprises a third output that provides a blend of stored portions of the interactive animation, the third output to be provided after the first output of the set of outputs during presentation of the interactive animation.

10. The method of claim 9, wherein updating the plurality of sets of outputs for the interactive animation with the second output comprises:

replacing the third output of the set of outputs associated with the received sequence of discrete control inputs with the second output.

11. The method of claim 10, further comprising:

generating a fourth output that provides a blend of stored portions of the interactive animation, the fourth output to be provided after the second output during presentation of the interactive animation.

12. The method of claim 1, further comprising:

while the interactive animation is being presented to the user, generating data in real-time for presentation to the user along with the interactive animation.

13. The method of claim 1, wherein transmitting, to the client device, the information indicative of the at least one of the plurality of sets of outputs for the interactive animation comprises:

generating a renderable representation of the interactive animation provided by the at least one of the plurality of sets of outputs; and

transmitting the renderable representation of the interactive animation for rendering by the client device in real-time.

14. The method of claim 1, wherein transmitting, to the client device, the information indicative of the at least one of the plurality of sets of outputs for the interactive animation comprises:

transmitting visualization data for the interactive animation, which when processed by the client device causes the client device to generate a renderable representation of the interactive animation and to render the renderable representation for presentation of the interactive animation to the user.

15. The method of claim 1, wherein transmitting the information indicative of the at least one of the plurality of sets of outputs for the interactive animation comprises:

transmitting information for an online game that comprises the at least one of the plurality of sets of outputs for the interactive animation.

16. The method of claim 1, wherein transmitting the information indicative of the at least one of the plurality of sets of outputs for the interactive animation comprises:

transmitting the information indicative of the at least one of the plurality of sets of outputs for the interactive animation based on a prediction of a sequence of discrete control inputs to be received during presentation of the interactive animation to a user.

17. The method of claim 1, wherein each stored portion of the interactive animation is assigned an energy metric, and wherein the error value represents a difference between a first value of the energy metric for the first stored portion of the interactive animation and a second value of the energy metric for the second stored portion of the interactive animation.

18. The method of claim 17, wherein the energy metric is defined in accordance with a kinetic energy value, a potential energy value, and a discrete control input.

19. The method of claim 1, wherein each stored portion of the interactive animation is assigned a shape metric, and wherein the error value represents a difference between a first value of the shape metric for the first stored portion of the interactive animation and a second value of the shape metric for the second stored portion of the interactive animation.

20. The method of claim 19, wherein the shape metric for a given stored portion of the interactive animation is defined in accordance with an occupancy fraction value of the given stored portion of the interactive animation.

21. The method of claim 1, wherein the third stored portion of the interactive animation is simulated by a simulation engine in response to identification of the blend and in response to identifying the particular output.

22. A system comprising:

one or more processing devices; and

one or more computer-readable media storing instructions that are executable by the one or more processing devices to perform operations comprising;

accessing a plurality of sets of outputs for an interactive animation, with each set of outputs being associated with a different sequence of a plurality of sequences of discrete control inputs, and with each set of outputs comprising an output that provides a stored portion of the interactive animation;

identifying a particular output of the plurality of sets of outputs that provides a blend of first and second stored portions of the interactive animation, the blend being associated with an error value above a threshold, wherein the error value represents a difference between the first stored portion of the interactive amination included in the blend and the second stored portion of the interactive animation included in the blend;

in accordance with the error value being above the threshold, modifying the particular output to provide a third stored portion of the interactive animation;

replacing, in the particular output, the blend of the first and second stored portions of the interactive animation with the third stored portion; and

transmitting, to a client device, information indicative of at least one of the plurality of sets of outputs that includes the particular output that provides the third stored portion of the interactive animation, which when rendered by the client device causes the interactive animation to be presented to a user.

23. The system of claim 22, the operations further comprising generating the plurality of sets of outputs for the interactive animation prior to transmitting the information to the client device.

24. The system of claim 23, wherein generating the plurality of sets of outputs for the interactive animation comprises:

generating a directed graph comprising a plurality of vertices and a plurality of edges, with each of the plurality of vertices representing a state of the interactive animation that is responsive to a discrete control input, with each of the plurality of vertices connected to a number of outgoing edges where the number is equivalent to a number of possible discrete control inputs, and with each edge connecting two of the plurality of vertices and representing an output of the plurality of sets of outputs.

25. The system of claim 23, wherein generating the plurality of sets of outputs for the interactive animation comprises:

generating the plurality of sets of outputs for the interactive animation based on a heuristic user model.

26. The system of claim 23, wherein generating the plurality of sets of outputs for the interactive animation comprises:

generating the plurality of sets of outputs for the interactive animation based on receiving, from a plurality of client devices, sequences of discrete control inputs that are associated with sets of outputs of the plurality of sets of outputs for the interactive animation.

27. The system of claim 23, wherein generating the plurality of sets of outputs for the interactive animation comprises:

generating the plurality of sets of outputs for the interactive animation using a kernel density estimator combined with a Markov prior.

28. The system of claim 22, wherein a stored portion of the interactive animation comprises at least one of a static image, a sequence of static images, one or more signed distance functions, or a sequence of polygon meshes.

29. The system of claim 22, wherein the output that provides the stored portion of the interactive animation is a first output that provides a first stored portion of the interactive animation, and the operations further comprise:

receiving a sequence of discrete control inputs for the at least one of the plurality of sets transmitted;

generating, by one or more processing devices, a second output for the at least one of the sets of outputs in accordance with the received sequence of discrete control inputs so that the second output provides a second stored portion of the interactive animation, the second output to be provided after the first output of the set of outputs during presentation of the interactive animation; and

updating the plurality of sets of outputs for the interactive animation with the second output for the set of outputs associated with the received sequence of discrete control inputs.

30. The system of claim 29, wherein each set of outputs of the accessed plurality of sets of outputs comprises a third output that provides a blend of stored portions of the interactive animation, the third output to be provided after the first output of the set of outputs during presentation of the interactive animation.

31. The system of claim 30, wherein updating the plurality of sets of outputs for the interactive animation with the second output comprises:

replacing the third output of the set of outputs associated with the received sequence of discrete control inputs with the second output.

32. The system of claim 31, the operations further comprising:

generating a fourth output that provides a blend of stored portions of the interactive animation, the fourth output to be provided after the second output during presentation of the interactive animation.

33. The system of claim 22, the operations further comprising:

while the interactive animation is being presented to the user, generating data in real-time for presentation to the user along with the interactive animation.

34. The system of claim 22, wherein transmitting, to the client device, the information indicative of the at least one of the plurality of sets of outputs for the interactive animation comprises:

generating a renderable representation of the interactive animation provided by the at least one of the plurality of sets of outputs; and

transmitting the renderable representation of the interactive animation for rendering by the client device in real-time.

35. The system of claim 22, wherein transmitting, to the client device, the information indicative of the at least one of the plurality of sets of outputs for the interactive animation comprises:

transmitting visualization data for the interactive animation, which when processed by the client device causes the client device to generate a renderable representation of the interactive animation and to render the renderable representation for presentation of the interactive animation to the user.

36. The system of claim 22, wherein transmitting the information indicative of the at least one of the plurality of sets of outputs for the interactive animation comprises:

transmitting information for an online game that comprises the at least one of the plurality of sets of outputs for the interactive animation.

37. The system of claim 22, wherein transmitting the information indicative of the at least one of the plurality of sets of outputs for the interactive animation comprises:

transmitting the information indicative of the at least one of the plurality of sets of outputs for the interactive animation based on a prediction of a sequence of discrete control inputs to be received during presentation of the interactive animation to a user.

38. One or more non-transitory computer-readable media storing instructions that are executable by one or more processing devices to perform operations comprising:

accessing a plurality of sets of outputs for an interactive animation, with each set of outputs being associated with a different sequence of a plurality of sequences of discrete control inputs, and with each set of outputs comprising an output that provides a stored portion of the interactive animation;

identifying a particular output of the plurality of sets of outputs that provides a blend of first and second stored portions of the interactive animation, the blend being associated with an error value above a threshold, wherein the error value represents a difference between the first stored portion of the interactive amination included in the blend and the second stored portion of the interactive animation included in the blend;

in accordance with the error value being above the threshold, modifying the particular output to provide a third stored portion of the interactive animation;

replacing, in the particular output, the blend of the first and second stored portions of the interactive animation with the third stored portion; and

transmitting, to a client device, information indicative of at least one of the plurality of sets of outputs that includes the particular output that provides the third stored portion of the interactive animation, which when rendered by the client device causes the interactive animation to be presented to a user.

39. The one or more non-transitory computer-readable media of claim 38, the operations further comprising generating the plurality of sets of outputs for the interactive animation prior to transmitting the information to the client device.

40. The one or more non-transitory computer-readable media of claim 39, wherein generating the plurality of sets of outputs for the interactive animation comprises:

generating a directed graph comprising a plurality of vertices and a plurality of edges, with each of the plurality of vertices representing a state of the interactive animation that is responsive to a discrete control input, with each of the plurality of vertices connected to a number of outgoing edges where the number is equivalent to a number of possible discrete control inputs, and with each edge connecting two of the plurality of vertices and representing an output of the plurality of sets of outputs.

41. The one or more non-transitory computer-readable media of claim 39, wherein generating the plurality of sets of outputs for the interactive animation comprises:

generating the plurality of sets of outputs for the interactive animation based on a heuristic user model.

42. The one or more non-transitory computer-readable media of claim 39, wherein generating the plurality of sets of outputs for the interactive animation comprises:

generating the plurality of sets of outputs for the interactive animation based on receiving, from a plurality of client devices, sequences of discrete control inputs that are associated with sets of outputs of the plurality of sets of outputs for the interactive animation.

43. The one or more non-transitory computer-readable media of claim 39, wherein generating the plurality of sets of outputs for the interactive animation comprises:

generating the plurality of sets of outputs for the interactive animation using a kernel density estimator combined with a Markov prior.

44. The one or more non-transitory computer-readable media of claim 38, wherein a stored portion of the interactive animation comprises at least one of a static image, a sequence of static images, one or more signed distance functions, or a sequence of polygon meshes.

45. The one or more non-transitory computer-readable media of claim 38, wherein the output that provides the stored portion of the interactive animation is a first output that provides a first stored portion of the interactive animation, and the operations further comprise:

receiving a sequence of discrete control inputs for the at least one of the plurality of sets transmitted;

generating, by one or more processing devices, a second output for the at least one of the sets of outputs in accordance with the received sequence of discrete control inputs so that the second output provides a second stored portion of the interactive animation, the second output to be provided after the first output of the set of outputs during presentation of the interactive animation; and

updating the plurality of sets of outputs for the interactive animation with the second output for the set of outputs associated with the received sequence of discrete control inputs.

46. The one or more non-transitory computer-readable media of claim 45, wherein each set of outputs of the accessed plurality of sets of outputs comprises a third output that provides a blend of stored portions of the interactive animation, the third output to be provided after the first output of the set of outputs during presentation of the interactive animation.

47. The one or more non-transitory computer-readable media of claim 46, wherein updating the plurality of sets of outputs for the interactive animation with the second output comprises:

replacing the third output of the set of outputs associated with the received sequence of discrete control inputs with the second output.

48. The one or more non-transitory computer-readable media of claim 47, the operations further comprising:

generating a fourth output that provides a blend of stored portions of the interactive animation, the fourth output to be provided after the second output during presentation of the interactive animation.

49. The one or more non-transitory computer-readable media of claim 38, the operations further comprising:

while the interactive animation is being presented to the user, generating data in real-time for presentation to the user along with the interactive animation.

50. The one or more non-transitory computer-readable media of claim 38, wherein transmitting, to the client device, the information indicative of the at least one of the plurality of sets of outputs for the interactive animation comprises:

generating a renderable representation of the interactive animation provided by the at least one of the plurality of sets of outputs; and

transmitting the renderable representation of the interactive animation for rendering by the client device in real-time.

51. The one or more non-transitory computer-readable media of claim 38, wherein transmitting, to the client device, the information indicative of the at least one of the plurality of sets of outputs for the interactive animation comprises:

transmitting visualization data for the interactive animation, which when processed by the client device causes the client device to generate a renderable representation of the interactive animation and to render the renderable representation for presentation of the interactive animation to the user.

52. The one or more non-transitory computer-readable media of claim 38, wherein transmitting the information indicative of the at least one of the plurality of sets of outputs for the interactive animation comprises:

transmitting information for an online game that comprises the at least one of the plurality of sets of outputs for the interactive animation.

53. The one or more non-transitory computer-readable media of claim 38, wherein transmitting the information indicative of the at least one of the plurality of sets of outputs for the interactive animation comprises:

transmitting the information indicative of the at least one of the plurality of sets of outputs for the interactive animation based on a prediction of a sequence of discrete control inputs to be received during presentation of the interactive animation to a user.