Constraining motion in 2D and 3D manipulation

• US 8,325,181 B1
• Filed: 04/01/2010
• Issued: 12/04/2012
• Est. Priority Date: 04/01/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Perceptive Pixel Incorporated (Microsoft Corporation)
• Inventors: Reisman, Jason L., Davidson, Philip L., Han, Jefferson Y.
• Primary Examiner(s): WANG, JIN CHENG
• Application Number:
  US12/753,093
• Time in Patent Office: 978 Days
• Field of Search: 345419-427, 345/619, 345/629, 345581-582, 345173-174, 715/863, 715/849
• US Class Current: 345/419
• CPC Class Codes: G06F 3/0425 using a single imaging device like a video camera for tracking the absolute position of a single or a plurality of objects with respect to an imaged reference surface, e.g. video camera imaging a display or a projection screen, a table or a wall surface, on which a computer generated image is displayed or projected tracking a projected light spot to determine a position on a display surface G06F3/0386
• CPC Class Codes: G06F 3/04815 Interaction with a metaphor-based environment or interaction object displayed as three-dimensional, e.g. changing the user viewpoint with respect to the environment or object
• CPC Class Codes: G06F 3/0488 using a touch-screen or digitiser, e.g. input of commands through traced gestures
• CPC Class Codes: G06F 3/04883 for inputting data by handwriting, e.g. gesture or text

Abstract

Techniques for constraining motion of 3D objects displayed on a 2D display interface are described. Touch points are placed by a user on the 2D display interface to manipulate a displayed object. Each touch point is matched with a contact point on the surface of the object. The motion of the object is restricted by adding penalty terms to an energy equation that includes terms that measure deviation between the screen-space location of the touch points and that of their matching contact points. The penalty terms measure deviation from an ideal value. In response to movement of at least one touch point to a new screen-space location, a transformation of the object is determined by applying an algorithm that operates on the energy equation to reduce deviations between the screen-space location of the touch points and that of their matching contact points while also reducing deviation from the ideal value or values set by the penalty term or terms.

Claims

1. A computer-implemented method of manipulating a three-dimensional object displayed in a multi-touch display device, the method comprising:

accessing a three-dimensional object-space data set from a computer memory storage device, the three-dimensional object-space data set representing a three-dimensional object in object-space and specifying points on a surface of the three dimensional object in three dimensions in object-space;

accessing an initial object transformation vector that specifies at least a location and a rotational orientation of the three-dimensional object in world-space;

determining, using at least one computer processor, a three-dimensional world-space data set by applying the initial object transformation vector to the three-dimensional object-space data set, the three-dimensional world-space data set representing the three dimensional object in world-space and specifying points on the surface of the three dimensional object in three dimensions in world-space;

accessing, from the computer memory storage device, data representing an image plane in world-space;

determining a two-dimensional screen-space data set corresponding to a three-dimensional view of the three-dimensional object by projecting the three-dimensional world-space data set onto the image plane based on the data representing the image plane, the two-dimensional screen-space data set specifying points on the surface of the three dimensional object as viewed on the image plane in two dimensions in screen-space;

rendering, on the multi-touch display device, the three-dimensional view of the three-dimensional object based on the two-dimensional screen-space data set;

detecting touching by one or more input mechanisms of a first touch point on the multi-touch display device, the first touch point being located at a first initial screen-space location;

matching the first touch point to a first contact point on the surface of the three-dimensional object, the first contact point being a point on the surface of the three dimensional object in object-space that, when transformed into world-space using the initial object transformation vector and then projected onto the image plane for rendering, is displayed by the multi-touch display device at the first initial screen-space location of the first touch point;

tracking, based on movement of the one or more input mechanisms while the one or more input mechanisms remain touching the multi-touch display device, movement of the first touch point from the first initial screen-space location to a first final screen-space location;

accessing an object-space constraint point, the object-space constraint point being a point on the surface of the three-dimensional object in object-space;

determining a world-space constraint point by transforming the object-space constraint point using the initial object transformation vector, the world-space constraint point being located at a first world-space location;

determining a new object transformation vector that, when applied to the three-dimensional object-space data set, results in a new three-dimensional world-space data set that when projected onto the image plane results in a new two-dimensional screen-space data set corresponding to a new view of the three dimensional object, the new three-dimensional world-space data set satisfying the constraint that the object-space constraint point, when transformed into world space using the new transformation vector, is positioned substantially at the first world-space location and the new two dimensional screen-space data set satisfying the constraint that the first contact point, when transformed into world-space using the new object transformation vector and then projected onto the image plane for rendering, is displayed substantially at the first final screen-space location; and

rendering, on the multi-touch display device, the new three-dimensional view of the three-dimensional object based on the new two-dimensional screen-space data set, the new three dimensional view being a view of the three-dimensional object wherein each contact point remains displayed by the multi-touch display device substantially underneath its corresponding touch point.

2. The method of claim 1,

wherein determining the new object transformation vector comprises applying an algorithm to reduce Euclidean distances between the first final screen-space location of the first touch point and a screen-space location of the first contact point and between a new world-space location of the object-space constraint point and the first world-space location,

wherein the screen-space location of the first contact point is determined by transforming the first contact point into a world-space contact point using the new object transformation vector and projecting the world-space contact point onto the image plane, and

wherein the new world-space location of the object-space constraint point is determined by transforming the object-space constraint point into world-space using the new object transformation vector.

3. The method of claim 2, wherein determining the new object transformation vector by applying the algorithm comprises determining the new object transformation vector by applying a least squares minimization algorithm.

4. The method of claim 3, wherein determining the new object transformation vector by applying the least squares minimization algorithm comprises determining the new object transformation vector by applying a Levenberg-Marquardt algorithm.

5. The method of claim 1, wherein the new object transformation vector specifies a new location and a new rotational orientation for the three-dimensional object in world-space, the new location being different from the location specified by the initial object transformation vector and the new rotational orientation being different from the rotational orientation specified by the initial object transformation vector.

6. A computer-implemented method of manipulating a three-dimensional object displayed in a multi-touch display device, the method comprising:

accessing a three-dimensional object-space data set from a computer memory storage device, the three-dimensional object-space data set representing a three-dimensional object in object-space and specifying points on a surface of the three dimensional object in three dimensions in object-space;

accessing an initial object transformation vector that specifies at least a location and a rotational orientation of the three-dimensional object in world-space;

determining, using at least one computer processor, a three-dimensional world-space data set by applying the initial object transformation vector to the three-dimensional object-space data set, the three-dimensional world-space data set representing the three dimensional object in world-space and specifying points on the surface of the three dimensional object in three dimensions in world-space;

accessing, from the computer memory storage device, data representing an image plane in world-space;

determining a two-dimensional screen-space data set corresponding to a three-dimensional view of the three-dimensional object by projecting the three-dimensional world-space data set onto the image plane based on the data representing the image plane, the two-dimensional screen-space data set specifying points on the surface of the three dimensional object as viewed on the image plane in two dimensions in screen-space;

rendering, on the multi-touch display device, the three-dimensional view of the three-dimensional object based on the two-dimensional screen-space data set;

detecting touching by one or more input mechanisms of a first touch point on the multi-touch display device, the first touch point being located at a first initial screen-space location;

matching the first touch point to a first contact point on the surface of the three-dimensional object, the first contact point being a point on the surface of the three dimensional object in object-space that, when transformed into world-space using the initial object transformation vector and then projected onto the image plane for rendering, is displayed by the multi-touch display device at the first initial screen-space location of the first touch point;

tracking, based on movement of the one or more input mechanisms while the one or more input mechanisms remain touching the multi-touch display device, movement of the first touch point from the first initial screen-space location to a first final screen-space location;

accessing an object-space constraint point, the object-space constraint point being a point on the surface of the three-dimensional object in object-space;

determining a world-space constraint point by transforming the object-space constraint point using the initial object transformation vector, the world-space constraint point being located at a first world-space location;

determining a screen-space constraint location by projecting the world-space constraint point onto the image plane based on the data representing the image plane;

determining a new object transformation vector that, when applied to the three-dimensional object-space data set, results in a new three-dimensional world-space data set that when projected onto the image plane results in a new two-dimensional screen-space data set corresponding to a new view of the three dimensional object, the new two dimensional screen- space data set satisfying the constraint that the object-space constraint point, when transformed into world-space using the new object transformation vector and then projected onto the image plane for rendering, is displayed substantially at the screen-space constraint location, and the new two dimensional screen-space data set also satisfying the constraint that the first contact point, when transformed into world-space using the new object transformation vector and then projected onto the image plane for rendering, is displayed substantially at the first final screen-space location; and

rendering, on the multi-touch display device, the new three-dimensional view of the three-dimensional object based on the new two-dimensional screen-space data set, the new three dimensional view being a view of the three-dimensional object wherein each contact point remains displayed by the multi-touch display device substantially underneath its corresponding touch point.

7. The method of claim 6,

wherein determining the new object transformation vector comprises applying an algorithm to reduce Euclidean distances between the first final screen-space location of the first touch point and a screen-space location of the first contact point and between the screen-space constraint location and a new screen-space location of the object-space constraint point,

wherein the screen-space location of the first contact point is determined by transforming the first contact point into a world-space contact point using the new object transformation vector and projecting the world-space contact point onto the image plane, and

wherein the new screen-space location of the object-space constraint point is determined by transforming the object-space constraint point into a new world-space constraint point using the new object transformation vector and projecting the new world-space constraint point onto the image plane.

8. The method of claim 7, wherein determining the new object transformation vector by applying the algorithm comprises determining the new object transformation vector by applying a least squares minimization algorithm.

9. The method of claim 8, wherein determining the new object transformation vector by applying the least squares minimization algorithm comprises determining the new object transformation vector by applying a Levenberg-Marquardt algorithm.

10. The method of claim 6, wherein the new object transformation vector specifies a new location and a new rotational orientation for the three-dimensional object in world-space, the new location being different from the location specified by the initial object transformation vector and the new rotational orientation being different from the rotational orientation specified by the initial object transformation vector.

11. A computer-implemented method of manipulating a three-dimensional object displayed in a multi-touch display device, the method comprising:

accessing a three-dimensional object-space data set from a computer memory storage device, the three-dimensional object-space data set representing a three-dimensional object in object-space and specifying points on a surface of the three dimensional object in three dimensions in object-space;

accessing an initial object transformation vector that specifies at least a location and a rotational orientation of the three-dimensional object in world-space;

determining, using at least one computer processor, a three-dimensional world-space data set by applying the initial object transformation vector to the three-dimensional object-space data set, the three-dimensional world-space data set representing the three dimensional object in world-space and specifying points on the surface of the three dimensional object in three dimensions in world-space;

accessing, from the computer memory storage device, data representing an image plane in world-space;

determining a two-dimensional screen-space data set corresponding to a three-dimensional view of the three-dimensional object by projecting the three-dimensional world-space data set onto the image plane based on the data representing the image plane, the two-dimensional screen-space data set specifying points on the surface of the three dimensional object as viewed on the image plane in two dimensions in screen-space;

rendering, on the multi-touch display device, the three-dimensional view of the three-dimensional object based on the two-dimensional screen-space data set;

detecting touching by one or more input mechanisms of a first touch point on the multi-touch display device, the first touch point being located at a first initial screen-space location;

matching the first touch point to a first contact point on the surface of the three-dimensional object, the first contact point being a point on the surface of the three dimensional object in object-space that, when transformed into world-space using the initial object transformation vector and then projected onto the image plane for rendering, is displayed by the multi-touch display device at the first initial screen-space location of the first touch point;

tracking, based on movement of the one or more input mechanisms while the one or more input mechanisms remain touching the multi-touch display device, movement of the first touch point from the first initial screen-space location to a first final screen-space location;

accessing a first object-space constraint point, the first object-space constraint point being a first point on the surface of the three-dimensional object in object-space;

determining a first world-space constraint point by transforming the first object- space constraint point using the initial object transformation vector, the first world-space constraint point being located at a first world-space location;

determining a first screen-space constraint location by projecting the first world-space constraint point onto the image plane based on the data representing the image plane;

accessing a second object-space constraint point, the second object-space constraint point being a second point on the surface of the three-dimensional object in object-space;

determining a second world-space constraint point by transforming the second object-space constraint point using the initial object transformation vector, the second world-space constraint point being located at a second world-space location;

determining a second screen-space constraint location by projecting the second world-space constraint point onto the image plane based on the data representing the image plane;

defining a constraint distance as a Euclidean distance between the first screen-space constraint point location and the second screen-space constraint point location;

determining a new object transformation vector that, when applied to the three-dimensional object-space data set, results in a new three-dimensional world-space data set that when projected onto the image plane results in a new two-dimensional screen-space data set corresponding to a new view of the three dimensional object, the new two dimensional screen-space data set satisfying the constraint that a displayed distance between the first and the second object-space constraint points, when the first and the second object-space constraint points are transformed into world-space using the new object transformation vector and then projected onto the image plane for rendering, is substantially the same as the constraint distance, and the new two dimensional screen-space data set also satisfying the constraint that the first contact point, when transformed into world-space using the new object transformation vector and then projected onto the image plane for rendering, is displayed substantially at the first final screen-space location; and

rendering, on the multi-touch display device, the new three-dimensional view of the three-dimensional object based on the new two-dimensional screen-space data set, the new three dimensional view being a view of the three-dimensional object wherein each contact point remains displayed by the multi-touch display device substantially underneath its corresponding touch point.

12. The method of claim 11,

wherein determining the new object transformation vector comprises applying an algorithm to reduce a Euclidean distance between the first final screen-space location of the first touch point and a screen-space location of the first contact point and to reduce a difference between the constraint distance and a new displayed distance between the first and the second object-space constraint points,

wherein the screen-space location of the first contact point is determined by transforming the first contact point into a world-space contact point using the new object transformation vector and projecting the world-space contact point onto the image plane, and

wherein the new displayed distance between the first and the second object-space constraint points is determined by:

transforming the first object-space constraint point into a new first world-space constraint point using the new object transformation vector and projecting the new first world-space constraint point onto the image plane at a new first constraint point screen-space location,

transforming the second object-space constraint point into a new second world-space constraint point using the new object transformation vector and projecting the new second world-space constraint point onto the image plane at a new second constraint point screen-space location, and

determining the new displayed distance to be a Euclidean distance between the new first constraint point screen-space location and the new second constraint point screen-space location.

13. The method of claim 12, wherein determining the new object transformation vector by applying the algorithm comprises determining the new object transformation vector by applying a least squares minimization algorithm.

14. The method of claim 13, wherein determining the new object transformation vector by applying the least squares minimization algorithm comprises determining the new object transformation vector by applying a Levenberg-Marquardt algorithm.

15. The method of claim 11, wherein the new object transformation vector specifies a new location and a new rotational orientation for the three-dimensional object in world-space, the new location being different from the location specified by the initial object transformation vector and the new rotational orientation being different from the rotational orientation specified by the initial object transformation vector.

16. A computer-implemented method of manipulating a three-dimensional object displayed in a multi-touch display device, the method comprising:

accessing a three-dimensional object-space data set from a computer memory storage device, the three-dimensional object-space data set representing a three-dimensional object in object-space and specifying points on a surface of the three dimensional object in three dimensions in object-space;

accessing an initial object transformation vector that specifies at least a location and a rotational orientation of the three-dimensional object in world-space;

determining, using at least one computer processor, a three-dimensional world-space data set by applying the initial object transformation vector to the three-dimensional object-space data set, the three-dimensional world-space data set representing the three dimensional object in world-space and specifying points on the surface of the three dimensional object in three dimensions in world-space;

accessing, from the computer memory storage device, data representing an image plane in world-space;

determining a two-dimensional screen-space data set corresponding to a three-dimensional view of the three-dimensional object by projecting the three-dimensional world-space data set onto the image plane based on the data representing the image plane, the two-dimensional screen-space data set specifying points on the surface of the three dimensional object as viewed on the image plane in two dimensions in screen-space;

rendering, on the multi-touch display device, the three-dimensional view of the three-dimensional object based on the two-dimensional screen-space data set;

detecting touching by one or more input mechanisms of a first touch point on the multi-touch display device, the first touch point being located at a first initial screen-space location;

matching the first touch point to a first contact point on the surface of the three-dimensional object, the first contact point being a point on the surface of the three dimensional object in object-space that, when transformed into world-space using the initial object transformation vector and projected onto the image plane for rendering, is displayed by the multi-touch display device at the first initial screen-space location of the first touch point;

tracking, based on movement of the one or more input mechanisms while the one or more input mechanisms remain touching the multi-touch display device, movement of the first touch point from the first initial screen-space location to a first final screen-space location;

accessing a first object-space constraint point, the first object-space constraint point being a first point on the surface of the three-dimensional object in object-space;

determining a first world-space constraint point by transforming the first object-space constraint point using the initial object transformation vector, the first world-space constraint point being located at a first world-space location;

accessing a second object-space constraint point, the second object-space constraint point being a second point on the surface of the three-dimensional object in object-space;

determining a second world-space constraint point by transforming the second object-space constraint point using the initial object transformation vector, the second world-space constraint point being located at a second world-space location;

defining a constraint distance as a Euclidean distance between the first world-space constraint point location and the second world-space constraint point location;

determining a new object transformation vector that, when applied to the three-dimensional object-space data set, results in a new three-dimensional world-space data set that when projected onto the image plane results in a new two-dimensional screen-space data set corresponding to a new view of the three dimensional object, the new three-dimensional world-space data set satisfying the constraint that a distance in world-space between the first and the second object-space constraint points, when the first and the second object-space constraint points are transformed into world-space using the new object transformation vector, is substantially the same as the constraint distance, and the new two dimensional screen-space data set satisfying the constraint that the first contact point, when transformed into world-space using the new object transformation vector and projected onto the image plane for rendering, is displayed substantially at the first final screen-space location; and

rendering, on the multi-touch display device, the new three-dimensional view of the three-dimensional object based on the new two-dimensional screen-space data set, the new three dimensional view being a view of the three-dimensional object wherein each contact point remains displayed by the multi-touch display device substantially underneath its corresponding touch point.

17. The method of claim 16,

wherein determining the new object transformation vector comprises applying an algorithm to reduce a Euclidean distance between the first final screen-space location of the first touch point and a screen-space location of the first contact point and to reduce a difference between the constraint distance and a new world-space distance between the first and the second object-space constraint points,

wherein the screen-space location of the first contact point is determined by transforming the first contact point into a world-space contact point using the new object transformation vector and projecting the world-space contact point onto the image plane, and

wherein the new world-space distance between the first and the second object-space constraint points is determined by:

transforming the first object-space constraint point into a new first world-space constraint point using the new object transformation vector, the new first world-space constraint point being located at a new first world-space location,

transforming the second object-space constraint point into a new second world- space constraint point using the new object transformation vector, the new second world-space constraint point being located at a new second world-space location, and

determining the new world-space distance to be a Euclidean distance between the new first world-space location and the new second world-space location.

18. The method of claim 17, wherein determining the new object transformation vector by applying the algorithm comprises determining the new object transformation vector by applying a least squares minimization algorithm.

19. The method of claim 18, wherein determining the new object transformation vector by applying the least squares minimization algorithm comprises determining the new object transformation vector by applying a Levenberg-Marquardt algorithm.

20. The method of claim 16, wherein the new object transformation vector specifies a new location and a new rotational orientation for the three-dimensional object in world-space, the new location being different from the location specified by the initial object transformation vector and the new rotational orientation being different from the rotational orientation specified by the initial object transformation vector.