Methods and systems for haptic rendering and creating virtual fixtures from point clouds

• US 9,471,142 B2
• Filed: 06/15/2012
• Issued: 10/18/2016
• Est. Priority Date: 06/15/2011
• Status: Active Grant

• Current Assignee: University of Washington
• Original Assignee: University of Washington
• Inventors: Kosari, Sina Nia, Chizeck, Howard Jay, Rydn, Fredrik, Hannaford, Blake, Gustafsson, Nicklas, King, Hawkeye I.
• Primary Examiner(s): Pappas, Claire X
• Assistant Examiner(s): Casarez, Benjamin
• Application Number:
  US14/125,574
• Publication Number:
  US 20140168073A1
• Time in Patent Office: 1,586 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 3/016 Input arrangements with force or tactile feedback as computer generated output to the user
• CPC Class Codes: G06T 15/405 using Z-buffer
• CPC Class Codes: G06T 2210/28 Force feedback
• CPC Class Codes: G06T 2210/56 Particle system, point based geometry or rendering

Abstract

Methods, articles of manufacture, and devices related to generating haptic feedback for point clouds are provided. A computing device receives depth data about an In-Contact environment. The computing device generates a point cloud from the depth data. The computing device determines a haptic interface point (HIP). The computing device determines a haptic interface point (HIP). The computing device determines a force vector between the HIP and point cloud. The computing device sends an indication of haptic feedback based on the force vector.

Claims

1. A method, comprising:

receiving first depth data about an environment at a computing device;

generating a first point cloud from the first depth data using the computing device;

determining a haptic interface point (HIP) using the computing device;

determining, using the computing device, a first force vector between the HIP and the first point cloud utilizing a proxy, wherein the proxy is configured to select zero or more points near the proxy, wherein the proxy comprises a center of the proxy and at least three scale radii r1, r2, and r3 with r1<

r2≦

r3, and wherein determining the first force vector comprises;

determining a closest point within the first point cloud to the center of the proxy, and a closest distance between the closest point and the center of the proxy;

selecting one or more movement states based on at least one comparison between the closest distance and at least one radius of the three radii;

determining a surface-normal set of points based on points within the first point cloud and within the radius r3 of the center of the proxy;

determining a sum of a number of surface-normal estimates, wherein each surface-normal estimate in the number of surface-normal estimates comprises an estimate of a surface normal between a surface-normal point in the set of surface-normal points and the proxy; and

determining an estimated surface normal n between the proxy and the first point cloud based on the sum of the number of surface-normal estimates;

determining a HIP vector u between the HIP and the center of the proxy, and a negated HIP vector −

u;

determining an angle θ

between −

u and n;

determining whether the angle θ

exceeds a predetermined angle θ

threshold and that the HIP is not at the center of the proxy; and

in response to determining that the angle θ

exceeds the predetermined angle θ

threshold and that the HIP is not at the center of the proxy, moving the proxy;

sending, from the computing device, a first indication of haptic feedback based on the first force vector;

receiving second depth data about the environment at the computing device, wherein the second depth data differs from the first depth data;

generating a second point cloud from the second depth data using the computing device;

determining a second force vector between the HIP and the second point cloud using the computing device; and

sending, from the computing device, a second indication of haptic feedback based on the second force vector.

2. The method of claim 1, wherein the computing device is configured to communicate with a controllable mechanism, wherein sending the indication of haptic feedback based on the force vector from the computing device comprises sending the indication of haptic feedback based on the force vector from the computing device to the controllable mechanism, and wherein the method further comprises:

providing haptic feedback based on the indication of haptic feedback using the controllable mechanism.

3. The method of claim 2, wherein the controllable mechanism comprises a medical intervention device.

4. The method of claim 1, further comprising:

receiving first image data at the computing device, wherein the first image data corresponds to the first depth data; and

generating a virtual environment based on the first depth data and the first image data, wherein the virtual environment comprises an indication of the HIP within the virtual environment.

5. The method of claim 4, wherein the virtual environment comprises a first object and a second object different from the first object, and wherein the method further comprises:

determining a contact between the first object and the second object.

6. The method of claim 1, wherein the computing device is configured to communicate with an underwater robot.

7. The method of claim 1, wherein the proxy further comprises a movement state.

8. The method of claim 7, wherein selecting the one or more movement states based on the at least one comparison between the closest distance and the at least one radius of the three radii comprises:

in response to determining that the closest distance is less than radius r1, determining that the movement state is an entrenched state;

in response to determining that the closest distance is greater than radius r1 but less than radius r2, determining that the movement state is an in-contact state; and

in response to determining that the closest distance is greater than radius r2, determining that the movement state is a free-motion state.

9. The method of claim 8, wherein determining the force vector between the HIP and the first point cloud using the computing device further comprises:

determining whether the movement state is the in-contact state;

determining whether a length ∥

u∥

₂ of u is greater than radius r2; and

in response to determining that the movement state is the in-contact state and that ∥

u∥

₂ is greater than radius r2;

determining u₁ by updating u using an estimate of movement of the first point cloud,

determining a length of u₁ ∥

u₁∥

₂,

determining the first force vector between the HIP and the first point cloud based on a difference between ∥

u₁∥

₂ and radius r2.

10. The method of claim 9, wherein moving the proxy comprises:

determining an estimated surface of the first point cloud based on n;

moving the proxy along u toward the HIP, when the movement state is the free-motion state;

moving the proxy along n, when either (a) the movement state is the entrenched state or (b) when the movement state is the in-contact state and the HIP is outside the estimated surface; and

moving the proxy along a projection of u onto a plane defined by n, when the movement state is the in-contact state and the HIP is inside the estimated surface.

11. The method of claim 1, wherein the environment comprises an undersea environment.

12. The method of claim 1, wherein determining the first force vector between the HIP and the first point cloud using the computing device further comprises:

determining the first force vector using at least one of;

a position of the HIP, a rate of change of the position of the HIP, a position of the center of the proxy, and a rate of change of the position of the center of the proxy.

13. The method of claim 1, wherein moving the proxy comprises moving the proxy using at least one of:

a position of the HIP, a rate of change of the position of the HIP, a position of the center of the proxy, and a rate of change of the position of the center of the proxy.

14. The method of claim 1, further comprising:

defining a forbidden region within the environment, wherein determining the first force vector between the HIP and the first point cloud comprises inhibiting a proxy center from moving within the forbidden region.

15. The method of claim 1, further comprising:

controlling a motion of an object or character within a virtual environment, wherein the virtual environment comprises at least one virtual object and at least one real surface.

16. An article of manufacture, comprising a physical computer-readable storage medium storing instructions that, upon execution by a processor, cause the processor to perform functions comprising:

receiving first depth data about an environment;

generating a first point cloud from the first depth data;

determining a haptic interface point (HIP);

determining a first force vector between the HIP and the first point cloud utilizing a proxy, wherein the proxy is configured to select zero or more points near the proxy, wherein the proxy comprises a center of the proxy and at least three scale radii r1, r2, and r3 with r1<

r2≦

r3, and wherein determining the first force vector comprises;

determining a closest point within the first point cloud to the center of the proxy, and a closest distance between the closest point and the center of the proxy;

selecting one or more movement states based on at least one comparison between the closest distance and at least one radius of the three radii;

determining a surface-normal set of points based on points within the first point cloud and within the radius r3 of the center of the proxy;

determining a sum of a number of surface-normal estimates, wherein each surface-normal estimate in the number of surface-normal estimates comprises an estimate of a surface normal between a surface-normal point in the set of surface-normal points and the proxy; and

determining an estimated surface normal n between the proxy and the first point cloud based on the sum of the number of surface-normal estimates;

determining a HIP vector u between the HIP and the center of the proxy, and a negated HIP vector −

u;

determining an angle θ

between −

u and n;

determining whether the angle θ

exceeds a predetermined angle θ

_threshold and that the HIP is not at the center of the proxy; and

in response to determining that the angle θ

exceeds the predetermined angle θ

_threshold and that the HIP is not at the center of the proxy, moving the proxy;

sending a first indication of haptic feedback based on the first force vector;

receiving second depth data about the environment, wherein the second depth data differs from the first depth data;

generating a second point cloud from the second depth data;

determining a second force vector between the HIP and the second point cloud; and

sending a second indication of haptic feedback based on the second force vector.

17. A computing device, comprising:

a processor; and

data storage, storing instructions that, upon execution by the processor, cause the computing device to perform functions comprising;

receiving first depth data about an environment;

generating a first point cloud from the first depth data;

determining a haptic interface point (HIP);

determining a first force vector between the HIP and the first point cloud utilizing a proxy, wherein the proxy is configured to select zero or more points near the proxy, wherein the proxy comprises a center of the proxy and at least three scale radii r1, r2, and r3 with r1<

r2≦

r3, and wherein determining the first force vector comprises;

determining a closest point within the first point cloud to the center of the proxy, and a closest distance between the closest point and the center of the proxy;

selecting one or more movement states based on at least one comparison between the closest distance and at least one radius of the three radii;

determining a surface-normal set of points based on points within the first point cloud and within the radius r3 of the center of the proxy;

determining a sum of a number of surface-normal estimates, wherein each surface-normal estimate in the number of surface-normal estimates comprises an estimate of a surface normal between a surface-normal point in the set of surface-normal points and the proxy; and

determining an estimated surface normal n between the proxy and the first point cloud based on the sum of the number of surface-normal estimates;

determining a HIP vector u between the HIP and the center of the proxy, and a negated HIP vector −

u;

determining an angle θ

between −

u and n;

determining whether the angle θ

exceeds a predetermined angle θ

_threshold and that the HIP is not at the center of the proxy; and

in response to determining that the angle θ

exceeds the predetermined angle θ

_threshold and that the HIP is not at the center of the proxy, moving the proxy;

sending a first indication of haptic feedback based on the first force vector;

receiving second depth data about the environment, wherein the second depth data differs from the first depth data;

generating a second point cloud from the second depth data;

determining a second force vector between the HIP and the second point cloud; and

sending a second indication of haptic feedback based on the second force vector.