Controlling distribution of error in 2D and 3D manipulation

• US 8,289,316 B1
• Filed: 04/01/2010
• Issued: 10/16/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: Davidson, Philip L., Reisman, Jason L., Han, Jefferson Y
• Primary Examiner(s): WANG, JIN CHENG
• Application Number:
  US12/753,085
• Time in Patent Office: 929 Days
• Field of Search: 345419-427, 345/650, 345/619, 345/629, 345/440, 345581-582, 345173-174, 715/849, 715/863
• 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

Each touch point placed on a multi-touch display device is matched with a contact point on a surface of a three-dimensional object displayed on the multi-touch display device. A three-dimensional transformation of the object is calculated by a solver using an algorithm that reduces deviation between projected two-dimensional locations of the three-dimensional contact points after object transformation and two dimensional locations of their matching touch points. The solver, in calculating the three-dimensional transformation, assigns a weighting value to each touch point to distribute an aggregate amount of deviation calculated by the solver among the touch points such that a magnitude of the deviation between the projected two-dimensional location of one of the contact points and that of its matching touch point is different from a magnitude of the deviation between the projected two dimensional location of another contact point and that of its matching touch point.

Claims

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

displaying a three-dimensional object in two dimensions on the multi-touch display device by projecting the three-dimensional object onto an image plane, the three-dimensional object having an initial three-dimensional location and an initial three-dimensional rotational orientation;

detecting touching by one or more input mechanisms of multiple touch points on the multi-touch display device, the multiple touch points including a first touch point, a second touch point and a third touch point on the multi-touch display device;

determining a first initial two-dimensional location of the first touch point on the multi-touch display device;

determining a second initial two-dimensional location of the second touch point on the multi-touch display device;

determining a third initial two-dimensional location of the third touch point on the multi-touch display device;

matching the first touch point to a first three-dimensional contact point on a surface of the three-dimensional object, the first three-dimensional contact point being displayed at the first initial two-dimensional location of the first touch point when the first three-dimensional contact point is projected for display onto the image plane;

matching the second touch point to a second three-dimensional contact point on the surface of the three-dimensional object, the second three-dimensional contact point being displayed at the second initial two-dimensional location of the second touch point when the second three-dimensional contact point is projected for display onto the image plane;

matching the third touch point to a third three-dimensional contact point on the surface of the three-dimensional object, the third three-dimensional contact point being displayed at the third initial two-dimensional location of the third touch point when the third three-dimensional contact point is projected for display onto the image plane;

detecting, 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 two-dimensional location to a first final two-dimensional location;

using a solver to calculate a three-dimensional transformation of the three-dimensional object that specifies at least one of a new three-dimensional rotational orientation and a new three-dimensional location for the three-dimensional object, the three-dimensional transformation being calculated by the solver using an algorithm that reduces deviation between a projected two-dimensional location of the first three-dimensional contact point and the first final two-dimensional location of the first touch point, a projected two-dimensional location of the second three-dimensional contact point and the second initial two-dimensional location of the second touch point, and a projected two-dimensional location of the third three-dimensional contact point and the third initial two-dimensional location of the third touch point, and the solver, in calculating the three-dimensional transformation, assigns weighting values to the multiple touch points to distribute an aggregate amount of deviation calculated by the solver among the multiple touch points, including among the first touch point, the second touch point and the third touch point such that a magnitude of the deviation between the projected two-dimensional location of the first three-dimensional contact point and the first final two-dimensional location of the first touch point is different than a magnitude of the deviation between the projected two-dimensional location of the second three-dimensional contact point and the second initial two-dimensional location of the second touch point;

transforming, using at least one computer processor, the three-dimensional object using the three-dimensional transformation such that the transformed three-dimensional object is positioned and rotated in accordance with the at least one of the new three-dimensional location and the new three-dimensional rotational orientation; and

displaying the transformed three-dimensional object on the multi-touch display device by projecting the transformed three-dimensional object onto the image plane.

2. The method of claim 1, wherein the three-dimensional transformation is calculated by the solver using an algorithm that reduces Euclidean distances between the projected two-dimensional location of the first three-dimensional contact point and the first final two-dimensional location of the first touch point, the projected two-dimensional location of the second three-dimensional contact point and the second initial two-dimensional location of the second touch point, and the projected two-dimensional location of the third three-dimensional contact point and the third initial two-dimensional location of the third touch point.

3. The method of claim 2, wherein the algorithm that reduces the Euclidean distances comprises a least squares minimization algorithm.

4. The method of claim 3, wherein the least squares minimization algorithm comprises a Levenberg-Marquardt algorithm.

5. The method of claim 1,

wherein detecting touching by the one or more input mechanisms of the multiple touch points on the multi-touch display device comprises detecting touching by the one or more input mechanisms of at least the first touch point, the second touch point, the third touch point, and a fourth touch point,

further comprising:

determining a first initial two-dimensional location of the fourth touch point on the multi-touch display device, and

matching the fourth touch point to a fourth three-dimensional contact point on the surface of the three-dimensional object, the fourth three-dimensional contact point being displayed at the fourth initial two-dimensional location of the fourth touch point when the fourth three-dimensional contact point is projected for display onto the image plane; and

wherein the algorithm used by the solver to calculate the three-dimensional transformation comprises an algorithm that reduces deviation between a projected two-dimensional location of the first three-dimensional contact point and the first final two-dimensional location of the first touch point, a projected two-dimensional location of the second three-dimensional contact point and the second initial two-dimensional location of the second touch point, a projected two-dimensional location of the third three-dimensional contact point and the third initial two-dimensional location of the third touch point, and a projected two-dimensional location of the fourth three-dimensional contact point and the fourth initial two-dimensional location of the fourth touch point and the solver, in calculating the three-dimensional transformation, assigns weighting values to the multiple touch points to distribute an aggregate amount of deviation calculated by the solver among the multiple touch points, including among the first touch point, the second touch point, the third touch point and the fourth touch point such that a magnitude of the deviation between the projected two-dimensional location of the first three-dimensional contact point and the first final two-dimensional location of the first touch point is different than a magnitude of the deviation between the projected two-dimensional location of the second three-dimensional contact point and the second initial two-dimensional location of the second touch point.

6. The method of claim 1, wherein detecting touching by the one or more input mechanisms of the first touch point comprises detecting hovering by the one or more input mechanisms over the first touch point on the multi-touch display device without the one or more input mechanisms physically contacting the first touch point.

7. The method of claim 1, wherein detecting touching by the one or more input mechanisms of the first touch point comprises detecting the one or more input mechanisms physically contacting the first touch point on the multi-touch display device.

8. The method of claim 1, wherein the one or more input mechanisms include one or more fingers of a user of the multi-touch display device.

9. The method of claim 1, wherein the one or more input mechanisms include a stylus.

10. The method of claim 1, wherein the solver, in calculating the three-dimensional transformation, assigns a weighting value to each of the first touch point, the second touch point, and the third touch point.

11. The method of claim 10, wherein the solver, in calculating the three-dimensional transformation, assigns a weighting value to each of multiple touch points.

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

displaying a three-dimensional object in two dimensions on the multi-touch display device by projecting the three-dimensional object onto an image plane, the three-dimensional object having an initial three-dimensional location and an initial three-dimensional rotational orientation;

detecting touching by one or more input mechanisms of multiple touch points on the multi-touch display device, the multiple touch points including a first touch point, a second touch point and a third touch point on the multi-touch display device;

determining a first initial two-dimensional location of the first touch point on the multi-touch display device;

determining a second initial two-dimensional location of the second touch point on the multi-touch display device;

determining a third initial two-dimensional location of the third touch point on the multi-touch display device;

matching the first touch point to a first three-dimensional contact point on a surface of the three-dimensional object, the first three-dimensional contact point being displayed at the first initial two-dimensional location of the first touch point when the first three-dimensional contact point is projected for display onto the image plane;

matching the second touch point to a second three-dimensional contact point on the surface of the three-dimensional object, the second three-dimensional contact point being displayed at the second initial two-dimensional location of the second touch point when the second three-dimensional contact point is projected for display onto the image plane;

matching the third touch point to a third three-dimensional contact point on the surface of the three-dimensional object, the third three-dimensional contact point being displayed at the third initial two-dimensional location of the third touch point when the third three-dimensional contact point is projected for display onto the image plane;

detecting, based on movement of the one or more input mechanisms while the one or more input mechanisms remain touching the multi-touch display device, concurrent movement of the first touch point from the first initial two-dimensional location to a first final two-dimensional location and the second touch point from the second initial two-dimensional location to a second final two-dimensional location;

using a solver to calculate a three-dimensional transformation of the three-dimensional object that specifies at least one of a new three-dimensional rotational orientation and a new three-dimensional location for the three-dimensional object, the three-dimensional transformation being calculated by the solver using an algorithm that reduces deviation between a projected two-dimensional location of the first three-dimensional contact point and the first final two-dimensional location of the first touch point, a projected two-dimensional location of the second three-dimensional contact point and the second final two-dimensional location of the second touch point, and a projected two-dimensional location of the third three-dimensional contact point and the third initial two-dimensional location of the third touch point, and the solver, in calculating the three-dimensional transformation, assigns weighting values to the multiple touch points to distribute an aggregate amount of deviation calculated by the solver among the multiple touch points, including among the first touch point, the second touch point and the third touch point such that a magnitude of the deviation between the projected two-dimensional location of the first three-dimensional contact point and the first final two-dimensional location of the first touch point is different than a magnitude of the deviation between the projected two-dimensional location of the second three-dimensional contact point and the second final two-dimensional location of the second touch point;

transforming, using at least one computer processor, the three-dimensional object using the three-dimensional transformation such that the transformed three-dimensional object is positioned and rotated in accordance with the at least one of the new three-dimensional location and the new three-dimensional rotational orientation; and

displaying the transformed three-dimensional object on the multi-touch display device by projecting the transformed three-dimensional object onto the image plane.

13. The method of claim 12, wherein the three-dimensional transformation is calculated by the solver using an algorithm that reduces Euclidean distances between the projected two-dimensional location of the first three-dimensional contact point and the first final two-dimensional location of the first touch point, the projected two-dimensional location of the second three-dimensional contact point and the second final two-dimensional location of the second touch point, and the projected two-dimensional location of the third three-dimensional contact point and the third initial two-dimensional location of the third touch point.

14. The method of claim 13, wherein the algorithm that reduces the Euclidean distances comprises a least squares minimization algorithm.

15. The method of claim 14, wherein the least squares minimization algorithm comprises a Levenberg-Marquardt algorithm.

16. The method of claim 12,

wherein detecting touching by the one or more input mechanisms of the multiple touch points on the multi-touch display device comprises detecting touching by the one or more input mechanisms of at least the first touch point, the second touch point, the third touch point, and a fourth touch point,

further comprising:

determining a first initial two-dimensional location of the fourth touch point on the multi-touch display device, and

matching the fourth touch point to a fourth three-dimensional contact point on the surface of the three-dimensional object, the fourth three-dimensional contact point being displayed at the fourth initial two-dimensional location of the fourth touch point when the fourth three-dimensional contact point is projected for display onto the image plane; and

wherein the algorithm used by the solver to calculate the three-dimensional transformation comprises an algorithm that reduces deviation between a projected two-dimensional location of the first three-dimensional contact point and the first final two-dimensional location of the first touch point, a projected two-dimensional location of the second three-dimensional contact point and the second final two-dimensional location of the second touch point, a projected two-dimensional location of the third three-dimensional contact point and the third initial two-dimensional location of the third touch point, and a projected two- dimensional location of the fourth three-dimensional contact point and the fourth initial two- dimensional location of the fourth touch point and the solver, in calculating the three-dimensional transformation, assigns weighting values to the multiple touch points to distribute an aggregate amount of deviation calculated by the solver among the multiple touch points, including among the first touch point, the second touch point, the third touch point and the fourth touch point such that a magnitude of the deviation between the projected two-dimensional location of the first three-dimensional contact point and the first final two-dimensional location of the first touch point is different than a magnitude of the deviation between the projected two- dimensional location of the second three-dimensional contact point and the second final two- dimensional location of the second touch point.

17. The method of claim 12, wherein detecting touching by the one or more input mechanisms of the first touch point comprises detecting hovering by the one or more input mechanisms over the first touch point on the multi-touch display device without the one or more input mechanisms physically contacting the first touch point.

18. The method of claim 12, wherein detecting touching by the one or more input mechanisms of the first touch point comprises detecting the one or more input mechanisms physically contacting the first touch point on the multi-touch display device.

19. The method of claim 12, wherein the one or more input mechanisms include one or more fingers of a user of the multi-touch display device.

20. The method of claim 12, wherein the one or more input mechanisms include a stylus.

21. The method of claim 12, wherein the solver, in calculating the three-dimensional transformation, assigns a weighting value to each of the first touch point, the second touch point, and the third touch point.

22. The method of claim 21, wherein the solver, in calculating the three-dimensional transformation, assigns a weighting value to each of multiple touch points.