Method and system for inversion of detail-in-context presentations with folding

• US 20030231177A1
• Filed: 05/12/2003
• Published: 12/18/2003
• Est. Priority Date: 05/17/2002
• Status: Active Grant

• Current Assignee: Accessify, LLC (Ascend Innovation Management, LLC)
• Original Assignee: IDELIX Software Inc. (Lat49 Media Inc.)
• Inventors: Tigges, Mark, Montagnese, Catherine
• Granted Patent: US 6,961,071 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• CPC Class Codes: G06F 3/0481 based on specific properties of the displayed interaction object or a metaphor-based environment, e.g. interaction with desktop elements like windows or icons, or assisted by a cursor's changing behaviour or appearance
• 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: G06T 3/047 Fisheye or wide-angle transformations
• CPC Class Codes: H04N 5/2628 Alteration of picture size, shape, position or orientation, e.g. zooming, rotation, rolling, perspective, translation

Abstract

A method is for inverting a distorted surface presentation into an undistorted surface presentation in a detail-in-context presentation system including the steps of: selecting an input point on the undistorted surface; calculating a vector from the input point to a reference viewpoint; locating a starting point lying above the distorted surface and on the vector; locating a first bracketing point for a first intersection point of the vector and the distorted surface lying above the distorted surface and on the vector; locating a second bracketing point for the first intersection point lying below the distorted surface, and below the first intersection point, but above any subsequent intersection points of the vector and the distorted surface; locating a midpoint between the first and second bracketing points; and, determining if the midpoint is an acceptable approximation for the first intersection point thus being an inversion point corresponding to the input point.

Claims

1. A method for inverting a distorted surface presentation into an undistorted surface presentation in a detail-in-context presentation system comprising the steps of:

a) selecting an input point {overscore (p)}_input on said undistorted surface;

b) calculating a vector {overscore (ν

)} from said input point {overscore (p)}_input to a reference viewpoint v{overscore (r)}p;

c) locating a starting point {overscore (p)}_i+1, said starting point {overscore (p)}_i+1 lying above said distorted surface and on said vector {overscore (ν

)};

d) locating a first bracketing {overscore (p)}_i for a first intersection point of said vector {overscore (ν

)} and said distorted surface, said first bracketing point {overscore (p)}_i lying above said distorted surface and on said vector {overscore (ν

)};

e) locating a second bracketing point {overscore (p)}_i+1 for said first intersection point, said second bracketing point {overscore (p)}_i+1 lying below said distorted surface, and below said first intersection point, but above any subsequent intersection points of said vector {overscore (ν

)} and said distorted surface;

f) locating a midpoint {overscore (p)}_mid between said first and second bracketing points {overscore (p)}_i, {overscore (p)}_i+1; and

,

g) determining if said midpoint {overscore (p)}_mid is an acceptable approximation for said first intersection point, said acceptable approximation being an inversion point corresponding to said input point {overscore (p)}_input.

2. The method of claim 1 and further comprising the step of repeating steps (a) through (g) for remaining input points {overscore (p)}_input.

3. The method of claim 1 wherein said step of locating said starting point {overscore (p)}_i−

1 comprises the step of;

adding to said input point {overscore (p)}_input said vector {overscore (ν

)} scaled by a predetermined step value step added to a ratio of said height h and a z-axis component of said vector {overscore (ν

)}, that is, {overscore (p)}<sub>i−

1</sub>={overscore (p)}_input+(h/ν

₂+step) {overscore (ν

)}.

4. The method of claim 1 wherein said step of locating said first bracketing point {overscore (p)}_i comprises the step of:

subtracting from said starting point {overscore (p)}_i+1 said vector {overscore (ν

)} scaled by said predetermined step value step, that is, {overscore (p)}_i={overscore (p)}_i+1−

step·

{overscore (ν

)}.

5. The method of claim 1 wherein said step of locating said second bracketing point {overscore (p)}_i+1 comprises the steps of:

subtracting from said first bracketing point {overscore (p)}_i said vector {overscore (ν

)} scaled by said predetermined step value step, that is, {overscore (p)}_i+1={overscore (p)}_i−

step·

{overscore (ν

)};

determining if said second bracketing point {overscore (p)}_i+1 lies below said distorted surface, and below said first intersection point, but above any subsequent intersection points of said vector {overscore (ν

)} and said distorted surface by;

locating a first back-projection point {overscore (p)}_back(i) by projecting said first bracketing point {overscore (p)}_i parallel to a direction of displacement of said distorted surface {overscore (d)} onto said undistorted surface;

locating a second back-projection point {overscore (p)}_back(i+1) by projecting said second bracketing point {overscore (p)}_i+1 parallel to said direction of displacement {overscore (d)} onto said undistorted surface;

determining a first field function value sign SIGN(F({overscore (p)}_i)) for said first bracketing point {overscore (p)}_i by;

taking the sign of a first field function value F({overscore (p)}_i);

said first field function value F({overscore (p)}_i) determined by;

calculating a first three-dimensional distortion function point for said first back-projection point D₃({overscore (p)}_back(i)) by applying said three-dimensional distortion function D₃ to said first back-projection point {overscore (p)}_back(i) and subtracting from a z-axis component of said first three-dimensional distortion function point D₃({overscore (p)}_back(i)) a z-axis component of said first bracketing point {overscore (p)}_i, that is, F({overscore (p)}_i)=D₃({overscore (p)}_back(i))_z−

({overscore (p)}_i)_z;

determining a second field function value sign SIGN(F({overscore (p)}_i+1)) for said second bracketing point {overscore (p)}_i+1 by;

taking the sign of a second field function value F({overscore (p)}_i+1);

said second field function value F({overscore (p)}_i+1) determined by;

calculating a second three-dimensional distortion function point for said second back-projection point D₃({overscore (p)}_back(i+1)) by applying said three-dimensional distortion function D₃ to said second back-projection point {overscore (p)}_back(i+1) and subtracting from a z-axis component of said second three-dimensional distortion function point D₃({overscore (p)}_back(i+1)) a z-axis component of said second bracketing point {overscore (p)}_i+1, that is, F({overscore (p)}_i+1)=D₃({overscore (p)}_back(i+1))_z−

({overscore (p)}_i+1)_z;

comparing said first field function value sign SIGN(F({overscore (p)}_i)) to said second field function value sign SIGN(F({overscore (p)}_i+1));

said second bracketing point {overscore (p)}_i+1 lying below said distorted surface, and below said first intersection point, but above any subsequent intersection points of said vector {overscore (ν

)} and said distorted surface if said first field function value sign SIGN(F({overscore (p)}_i)) is not equal to said second field function value sign, that is, SIGN(F({overscore (p)}_i+1))≠

SIGN(F({overscore (p)}_i+1)); and

,

relocating said second bracketing point {overscore (p)}_i+1 if said second bracketing point {overscore (p)}_i+1 does not lie below said distorted surface, and below said first intersection point, but above any subsequent intersection points of said vector {overscore (ν

)}, that is, SIGN(F({overscore (p)}_i+1))=SIGN(F({overscore (p)}_i+1)), by;

determining a first field function slope value sign SIGN(F′

({overscore (p)}_i)) for said first bracketing point {overscore (p)}_i;

determining a second field function slope value sign SIGN(F′

({overscore (p)}_i+1)) for said second bracketing point {overscore (p)}_i+1;

comparing said first field function slope value sign SIGN(F′

({overscore (p)}_i)) and said second field function slope value sign SIGN(F′

({overscore (p)}_i+1)); and

,

if said first field function slope value sign SIGN(F′

({overscore (p)}_i)) equals said second field function slope value sign SIGN(F′

({overscore (p)}_i+1)), that is, SIGN(F′

({overscore (p)}_i+1))=SIGN(F′

({overscore (p)}_i+1)), then redefining said second bracketing point {overscore (p)}_i+1 as said first bracketing point {overscore (p)}_i and repeating said step of locating said second bracketing point {overscore (p)}_i+1, or if said first field function slope value sign SIGN(F′

({overscore (p)}_i)) does not equal said second field function slope value sign SIGN(F′

({overscore (p)}_i)), that is, SIGN(F′

({overscore (p)}_i+1))≠

SIGN(F′

({overscore (p)}_i+1)), then reducing said predetermined step value step by a predetermined amount and repeating said step of locating said second bracketing point {overscore (p)}_i+1.

6. The method of claim 1 wherein said step of locating a midpoint {overscore (p)}_mid between said first and second bracketing points {overscore (p)}_i, {overscore (p)}_i+1 comprises the step of:

adding said first and second bracketing points {overscore (p)}_i, {overscore (p)}_i+1 and dividing by two, that is, {overscore (p)}_mid=½

({overscore (p)}_i+{overscore (p)}_i+1).

7. The method of claim 1 wherein said step of determining if said midpoint {overscore (p)}_mid is an acceptable approximation for said first intersection point comprises the steps of:

locating a midpoint back-projection point {overscore (p)}_midback by projecting said midpoint {overscore (p)}_mid parallel to said direction of displacement {overscore (d)} onto said undistorted surface;

calculating a two-dimensional distortion function point for said midpoint back-projection point D₂({overscore (p)}_midback) by applying a two-dimensional distortion function D₂ to said midpoint back-projection point {overscore (p)}_midback;

said two-dimensional distortion function D₂ being said three-dimensional distortion function D₃ in said xy plane;

calculating a magnitude of the difference between said two-dimensional distortion function point D₂({overscore (p)}_midback) and said input point {overscore (p)}_input, that is, ∥

D₂({overscore (p)}_midback)−

{overscore (p)}_input∥

; and

,

comparing said magnitude of the difference ∥

D₂({overscore (p)}_midback)−

{overscore (p)}_input∥

to a predetermined tolerance ε

;

said midpoint {overscore (p)}_mid being said acceptable approximation for said first intersection point if said magnitude of the difference is less than said predetermined tolerance ε

, that is, ∥

D₂({overscore (p)}_midback)−

{overscore (p)}_input∥

<

ε

; and

, if said magnitude of the difference ∥

D₂({overscore (p)}_midback)−

{overscore (p)}_input∥

is not less than said predetermined tolerance ε

, then redefining one of said first and second bracketing points {overscore (p)}_i, {overscore (p)}_i+1 as said midpoint {overscore (p)}_mid and repeating said step of locating a midpoint {overscore (p)}_mid and said step of determining if said midpoint {overscore (p)}_mid is an acceptable approximation for said first intersection point, until said acceptable approximation is located for said first intersection point;

said acceptable approximation being an inversion point corresponding to said input point {overscore (p)}_input.

8. The method of claim 1 wherein said presentation system establishing a notional three-dimensional perspective viewing frustrum with respect to an x, y, and z-axis coordinate system;

said frustrum including a reference viewpoint v{overscore (r)}p at an apex lying on said z-axis, a base in an xy-plane including said undistorted surface, and a reference view plane lying between said reference viewpoint v{overscore (r)}p and said undistorted surface and upon which said distorted surface is projected;

said presentation system including a display screen for viewing said reference view plane by a user; and

, said distorted surface created by the application of a three-dimensional distortion function D₃ to said undistorted surface.

9. The method of claims 3, 4, or 5 and further comprising the step of selecting a value for said predetermined step value step.

10. The method of claim 5 and further comprising the step of selecting a value for said predetermined amount by which said predetermined step value step is reduced.

11. The method of claim 7 and further comprising the step of selecting a value for said predetermined tolerance ε

.

12. The method of claim 11 wherein said predetermined tolerance ε

is selected as a fraction of the width of a pixel for said computer display screen.

13. The method of claim 12 wherein said fraction is one half.

14. The method of claim 8 wherein said distortion function D₃ is an n-dimensional function, said n being an integer greater than two.

15. The method of claim 8 wherein said distortion function D₃ is a lens function.

16. The method of claim 8 wherein said detail-in-context presentation system is suitable for generating detail-in-context presentations in accordance with Elastic Presentation Space graphics technology.

17. The method of claim 8 wherein said base is said undistorted surface.