a2) United States Patent
`US 6,414,677 B1
`(10) Patent No.:
`Jul. 2, 2002
`(45) Date of Patent:
`Robertson et al.
`
`US006414677B1
`
`(54) METHODS, APPARATUS AND DATA
`STRUCTURES FOR PROVIDING A USER
`INTERFACE, WHICH EXPLOITS SPATIAL
`MEMORYIN THREE-DIMENSIONS, TO
`
`OTHER PUBLICATIONS
`
`,
`Fahlen et al (A Space Based Model for UserInteraction in
`Shared
`Synthetic
`Environments”:
`1993,
`ACM
`
`PROXIMALLY LOCATED OBJECTS
`
`(75)
`
`Inventors: George G. Robertson; Daniel C.
`Robbins; Maarten Roderik Van
`Dantzich, all of Seattle, WA (US)
`(73) Assignee: Microsoft Corporation, Redmond, WA
`&
`P
`>
`>
`(US)
`Subject to anydisclaimer, the term ofthis
`patent is extended or adjusted under 35
`US.C. 154(b) by 150 days.
`
`(*) Notice:
`
`Introducing MAPA,
`“Dynamic Diagrams”, Products
`MAPA™, download from http:/Avww.dynamicdiagram-
`s.com/products.html.
`“Maya Design Group”, Our Portfolio: Case Study: Case
`Study, Digital Equipment Corporation—Workscape™,
`downloaded from http:/Avww.maya.com/Portfolio/work-
`scape.html on Jul. 7, 1998.
`M.Heydt, “Incorporating the Webbrowser Control into your
`Program”, Microsoft Interactive Developer, The Microsoft
`Magazine for Web Developers, vol. 3, No. 7, pp. 42-51 (Jul.
`1998).
`R.R. Hightoweretal, “Graphical Multiscale Web Histories:
`A Study of PadPrints”, Hyper Text 98, pp. 58-65.
`(21) Appl. No.: 09/152,712
`S.K. Card et al, “The WebBook and the Web Forager: An
`1d.
`Information Workspace for the World-Wide Web”.
`(22)
`Filed:
`Sep. 14, 1998
`R.L. Kullberg, “Dynamic Timelines Visualizing Historical
`7
`(51) Unt, C1 oaseesceeceessseeseeetsssseeseeeseeinee GO6T 15/00Thee Dimensions”, Masters Thesis, BS.
`(52) US. Ch. vececccsseccsseeren 345/419; 345/848; 345/764
`Environmental Science, Massachusetts Institute of Technol-
`(58) Field of Search s.cccccccsccssseeseon 345/419, 425,
` 08Y» Cambridge, MA (1995).
`345/334, 335, 339, 348, 355, 149, 967,
`(List continued on next page.)
`977, 716, 751, 752, 753, 694, 762, 763,
`764, 765, 766, 767, 768, 769, 810, 812,
`825, 835-839, 848
`
`Primary Examiner—Mark Zimmerman
`Assistant Examiner—Mano Padmanabhan
`(74) Aitorney, Agent, or Kirm—Michaelson & Wallace;
`Peter L. Michaelson
`
`
`object), OBJECT
`Released
`OBJECT
`Object
`
`()Released()
`Dragged
`2240
`\ OTHER
`
`+Shjectwithinwithin "SELECTED"
`Predetermined
`
`OBJECT
`Distance of
`"PUSHED"
`Anotheroes
`/ ObjectNoSm{ within Predetermined
`| Distance of the Pre~
`4
`\ push Location ofthe = ——~. 17
`\ Other Object=7 OTHER x
`SY
`/
`opvect
`\
`NS
`{
`RESUMES
`~~ \. PREPUSH }
`~ a POSITION/NLU?
`
`"ACTIVE"
`Object Selected
`(Click)
`Objectspoolbacate
`
`{Cursoroffobject)
`Object
`Daselected
`Dragged
`Object
`Object
`(Click)
`Dragged;
`
`2200
`
`po
`
`(Cursor
`conoe,Activated
`
`/
`
`2220
`
`7
`
`2245
`
`1
`
`APPLE 1009
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,276,785 A
`5,295,243 A
`5,333,254 A
`5,339,390 A
`5,359,703 A
`5,384,908 A
`5,513,303 A
`5,530,235 A
`5,608,850 A
`5,670,984 A
`5,689,287 A
`5,689,628 A
`5,767,826 A
`
`......... 395/127
`1/1994 Mackinlayet al.
`.......... 395/160
`3/1994 Robertson et al.
`7/1994 Robertson ............
`.. 395/155
`8/1994 Robertson etal. .......... 395/157
`10/1994 Robertsonet al.
`.......... 395/119
`1/1995 Mackinlayet al.
`......... 395/152
`4/1996 Robertson et al.
`.......... 395/119
`6/1996. Stefik et al.
`......
`. 389/670
`3/1997 Robertson.........
`... 395/127
`9/1997 Robertson et al.
`.......... 345/139
`11/1997 Mackinlay et al.
`......... 345/427
`11/1997 Robertson ............ s 395/127
`6/1998 Sheridon et al. ........... 345/84
`
`(57)
`
`ABSTRACT
`
`A graphical user interface in which object thumbnails are
`rendered on a simulated three-dimensional surface which (1)
`exploits spatial memory and(ii) allows more objects to be
`rendered on a given screen. The objects may be moved,
`continuously, on the surface with a two-dimensional input
`device
`.
`
`17 Claims, 62 Drawing Sheets
`
`(43 of 62 Drawing Sheet(s) Filed in Color)
`
`APPLE 1009
`
`1
`
`

`

`US 6,414,677 B1
`Page 2
`
`OTHER PUBLICATIONS
`
`J.E. Ball et al, “ReActor: ASystem for Real-Time, Reactive
`Animations”, Conference Companion, CHI ’94, Boston,
`MA,pp. 39-40 (Apr. 24-28, 1994).
`J.M. Ballay, MAYA Design Group, “Designing Work-
`space™: An Interdisciplinary Experience”, Zuman Factors
`in Computing Systems, CHI
`’94—‘Celebrating Interde-
`pence”, pp. 10-15 (Apr. 24-28, 1994).
`
`G.G. Robertson et al, “Information Visualization Using 3D
`Interactive Animation”, Communications of the ACM, vol.
`36, No. 4, pp. 59-71 (Apr. 1993).
`R. Manderet al, Human Interface Group, Advanced Tech-
`nology, Apple Computer, Inc., A ‘Pile’ Metaphor for Sup-
`porting Casual Organization of Information, CHI °92, pp.
`627-634 (May 3-7, 1992).
`
`* cited by examiner
`
`2
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 1 of 62
`
`US 6,414,677 BI
`
`SOVsNSLNI
`AYOMLAN
`
`LY¥OdTVIdaS
`JOvsy3SLNI
`SAC4SIC
`AOVIMSLNI
`WoOllLdO
`ADVAYALNI
`3AIMO4810
`30VSYSLNI
`
`QILANOVA
`
`
`
`ASIGYVWH
`
`
`ayvoONNOS
`
`
`
`H.LIM)YaLdvVaVO3CIA
`ONISSSOONd
`
`(YOLVHSTIIIOVSOIHdVWHO
`
`(S)LINN
`
`ONILVYadO
`op,|YBLNIOdf|VSNviva|Solaony|SWvuOOud|WALSAS
`
`correenneeeaeieeee
`(<aHebgz,Wnnews,
`
`
`3TOT|Wrddoud|NUSETS®|NoWLVorday|ONILVEadO
`SrlLab
`—SeSICGYVH
`
`
`ALOWSY
`
`YALNdNOD
`
`
`
`rowsvows]?
`
`Lu/Uy
`
`6rL
`
`ZlLPL
`
`SAO
`
`gel
`
`Wa.LSAS
`
`NOLLVOIMIddV¥
`
`(S)WWH9OUd
`
`WYeDOud
`
`SaTNGOW
`
`YAHLO|
`
`WvdSOud
`
`Viva
`
`3
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 2 of 62
`
`US 6,414,677 BI
`
`/LNdNI
`
`INdLno
`
`JOVAYALNI
`
`(S)LINN
`
`OL
`
`MYOMLANYOSNEWALSAS
`
`cob
`
`(S)uYOSSSOONd
`
`OL
`
`
`
`(S)S0IARZCSDVYOLS
`
`gbAYNS!s
`
`4
`
`
`
`
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 3 of 62
`
`US 6,414,677 BI
`
`G2
`
`LINANSSVNVA
`
`LnNdino
`
`S$Sa900udIna
`
`
`
`dOAOVYOLS
`
`
`
`GNv)LNAYYND
`
`LN3WASVNVW
`
`ONIMAIA
`
`Loargo
`
`Qaudssaud
`S$a90ud
`
`LAALNO
`
`olan’
`
`
`
`veeSMYVWONVT
`
`
`
`
`
`68)SSOVWIBa)SAOVINI02Zay34‘B°8)MSLNIOd
`
`
`
`(SAVE(SdVWLIGa0v4unsNOLLYO1iNdNi(SNOW
`
`
`S.10araoSLOAPEOcD91z
`
`NOLLNI0S3uNOLLMI0S3uplz
`822ADOIOdOLLNdNISame
`
`
`
`
`
`
`
`HOIH922%MO1212ZbzvLZ
`
`
`wuzALNIOWS>OOTORISINILwoz@3SoNDIS
`
`aNvSs300d
`
`OAOIA
`
`LAdLNO
`
`$$300ud
`
`AYVESOdWAL
`
`Ole
`
`ananod
`
`LN3A30ee
`
`892LIondlNowawasdndOdasz‘WBALLOW,"6'9)
`
`
`
`
`
`
`
`y9essao0ud39300udSIMULeeONY(.GSHSNd.
`|
`
`
`
`AMANOLoarao‘,GJAOW,‘.03L0573S.,
`792092rNOILYOO1
`
`
`
`LVLSLoarao
`
`NOLLWNIAYSLS0
`
`NOISN1090
`
`JONVGIOAY
`
`Ss300ud
`
`992YALSN1OLOArgOGSNINNSLIG3aYa06z
`
`
`YOSGUYOMASYOSdIdO.lLOArGOJSveOLs
`
`
`ssa00Ud22ZINALSISUZd
`
`SALLOSdSaad
`
`SS300uUdMIA
`
`SSa00u"d
`
`(SNOIAZYd
`
`ssg00ud
`
`
`
`ose972
`
`3LVLS
`
`xWTIvevd
`NOILVYANaD
`NOILVNINYALAG
`
`$S390ud
`
`LILdA-dOd
`
`
`
`LNIOdONIMAIA
`
`NOILVNIWYSLad
`
`9SZ202
`
`YyOsSYNd
`
`NOILLWOOT
`
`ssao0ud
`
`sS390ud
`
`NOILYNINYSAL3A0
`NOILVTINWIS
`
`ssa00ud
`
`$S3900Ud
`
`8b2
`
`5
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 4 of 62
`
`US 6,414,677 BI
`
`00€€aYyNdls
`
`v0E
`
`BleZLE—BOE
`
`ONIMIZIA
`
`ANIOd
`
`LOSLOITASesaaisBoML4OYaaWNN
`OvidOvidS103raO
`
`
`
`
`HOLVIN‘agqqly9ATONVdv
`3OVdANYMOHS
`GIOHSSYHL(O13
`wLOATASy|sALLOV.
`‘HSNdANITON!a9
`“B'e)dAL
`
`LNOAWI|9c
`
`NOILVYOO1YOSHND
`AOVIYNS
`HSNd-3dd
`NOILVWDO1
`
`BEE
`
`
`
`(AdAL
`
`6
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 5 of 62
`
`US 6,414,677 BI
`
`
`
`
`
`SANNA(4VWLIDTaXIdZ1SAd21S“6'8)VivdSOVWINOILNTOSSYHOIHalLoargo
`
`Z3yNnSIs
`
`002
`
`asLOarao
`
`GSNINYSLAGSYdYOSGYOMAAMHOSOldOL
`~SONO13ELOSPEOHOIHMOL(S)YALSNT9
`
`
`vOrcOr
`70SzOS
`gaunold|sun|atsoarao
`
`yoo009Z09
`
`vSYHNDSISA(dWWLIGTAXId79Ad79“6'9)VLVGSOVWINOILNTOSAYMOTalLoarao
`
`
`
`
`
`
`
`
`
`7
`
`
`
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 6 of 62
`
`US 6,414,677 B1
`
`
`
`8
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 7 of 62
`
`US 6,414,677 B1
`
`
`
`9
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 8 of 62
`
`US 6,414,677 B1
`
`aB32Entre
`
`Retennces
`
`SOLovawinceew cine
`
`10
`
`10
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 9 of 62
`
`US 6,414,677 B1
`
`
`
`11
`
`11
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 10 of 62
`
`US 6,414,677 B1
`
`ind their access ts rnuch faster.
`
`We're anncuncing our feo see server
`fams, one in London,
`the
`othar ta
`3 Tokye, By connecting to cr Web site
`f through these rnlmor sites, many of our
`8 customers outside Neth america may
`
`WellManaced Windows-fased
`
`nolugensOlfertheLowestFCG
`A recent Gartner Grou research note
`+04
`projects that ¢ well maneged, 22-by
`| Rilorosoft Windows-based desktop esr
`qt rediuos TOO by up to 55 pencent.
`
`12
`
`12
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 11 of 62
`
`US 6,414,677 B1
`
`Rated Peteynti FIGURE 10A
`
`aeese
`eee
`
`13
`
`13
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 12 of 62
`
`US 6,414,677 B1
`
`
`
`14
`
`14
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 13 of 62
`
`US 6,414,677 B1
`
`setahraatelteetaaiatate
`
`15
`
`15
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 14 of 62
`
`US 6,414,677 B1
`
`
`
`rama
`raeRocceeneoesSern
`
`pirpeat
`
`16
`
`16
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 15 of 62
`
`US 6,414,677 B1
`
`Seite
`
`peteenumnunnnunnen
`
`
`
`17
`
`17
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 16 of 62
`
`US 6,414,677 B1
`
`Abe
`
`he
`
`ee
`
`hg CBP eh
`Hobie mahal
`
`18
`
`18
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 17 of 62
`
`US 6,414,677 B1
`
`eerrenrerey
`
`19
`
`19
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 18 of 62
`
`US 6,414,677 B1
`
`Here screens
`
`Arenanutntelict
`Had layrs age
`
`20
`
`20
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 19 of 62
`
`US 6,414,677 BI
`
`eeeunnnnmenine
`
`srtetehnetatateteantanater n teh natashafateh eN ates
`
`sae
`
`Ro
`
`21
`
`21
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 20 of 62
`
`US 6,414,677 B1
`
`Seuareaunaren
`
`ennuannteamancetinc wa
`
`peuranise uaesneneennenin
`
`22
`
`22
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 21 of 62
`
`US 6,414,677 B1
`
`
`
`23
`
`23
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 22 of 62
`
`US 6,414,677 B1
`
`eceeaeeeeeence
`
`sanancamaeest
`
`eireeeen
`
`Sod reat nan
`
`Rea Pa ae
`
`24
`
`24
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 23 of 62
`
`US 6,414,677 BI
`
`SE MOTE sae
`
`‘tosis
`
`Laroty
`Wehaks V9:
`pr eent
`
`ane
`
`25
`
`25
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 24 of 62
`
`US 6,414,677 BI
`
`Materdeere
`
`es.
`ei UAod
`BASAS:
`
`18
`
`Sg Agi ahi
`Buds OE
`
`26
`
`26
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 25 of 62
`
`US 6,414,677 B1
`
`
`
`27
`
`27
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 26 of 62
`
`US 6,414,677 B1
`
`
`
`28
`
`28
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 27 of 62
`
`US 6,414,677 B1
`
`eedHAEMeeea
`
`
`
`29
`
`29
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 28 of 62
`
`US 6,414,677 B1
`
`eueeenr
`
`30
`
`30
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 29 of 62
`
`US 6,414,677 B1
`
`ean
`
`Satirewee
`
`canemrensnencnnctis
`
`point ements
`
`31
`
`31
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 30 of 62
`
`US 6,414,677 B1
`
`
`
`32
`
`32
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 31 of 62
`
`US 6,414,677 BI
`
`etnies
`
`Te terrela
`
`33
`
`33
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 32 of 62
`
`US 6,414,677 B1
`
`sitetateniestete
`
`bere
`
`eeeneunne
`
`2
`
`eae
`
`retesshevaateinnsetnn
`
`Teleane Hertel
`
`34
`
`34
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 33 of 62
`
`US 6,414,677 B1
`
`Metatentaranctiete
`
`setettabertestetiateett
`
`ieanieneneenines
`
`ta
`
`35
`
`35
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 34 of 62
`
`US 6,414,677 BI
`
`suaiennnnomnneieaee
`
`
`
`36
`
`36
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 35 of 62
`
`US 6,414,677 B1
`
`
`
`‘1200
`
`FIGURE 12A
`
`37
`
`37
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 36 of 62
`
`US 6,414,677 B1
`
`
`
`1200"
`
`FIGURE 12B
`
`38
`
`38
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 37 of 62
`
`US 6,414,677 B1
`
`es
`
`FIGURE 12C
`
`39
`
`39
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 38 of 62
`
`US 6,414,677 B1
`
`
`
`40
`
`40
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 39 of 62
`
`US 6,414,677 B1
`
`
`
`41
`
`41
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 40 of 62
`
`US 6,414,677 B1
`
`
`
`42
`
`42
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 41 of 62
`
`US 6,414,677 B1
`
`garaber? REA
`
`ts
`
`Sern
`
`boptertotes seagate :
`gshiies TioanateyndB thal
`iin eet dalyBeater
`deny tentedEowale
`gets
`#
`rosters Fae .
`aposaIEEE ~
`Bladen
`7
`o
`parearewcote e
`
`FIGURE 13A
`
`43
`
`43
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 42 of 62
`
`US 6,414,677 B1
`
`ee
`
`eet
`
`rent
`
`iD,nox sesneedBRad
`etenOe
`
`aie
`aeaneLue
`Fre eeeSE,
`
`1300
`
`FIGURE 138
`
`44
`
`44
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 43 of 62
`
`US 6,414,677 B1
`
`wy, TOES
`
`fr
`
`biggieSpeeRh
`she SeoBSE
`
`pedeet
`
`“
`wen
`
`C3
`poate
`
`et eu
`cape enIe
`
`1300"
`
`FIGURE13C
`
`45
`
`45
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 44 of 62
`
`US 6,414,677 B1
`
`
`
`1300"
`
`FIGURE 13D
`
`46
`
`46
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 45 of 62
`
`US 6,414,677 B1
`
`
`
`47
`
`47
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 46 of 62
`
`US 6,414,677 B1
`
`
`
`FIGURE 14B
`
`48
`
`48
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 47 of 62
`
`US 6,414,677 B1
`
`ie a
`
`FIGURE 15A
`
`49
`
`49
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 48 of 62
`
`US 6,414,677 B1
`
`
`
`FIGURE 158
`
`50
`
`50
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 49 of 62
`
`US 6,414,677 B1
`
`
`
`1600
`
`FIGURE 16
`
`51
`
`51
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 50 of 62
`
`US 6,414,677 B1
`
`
`
`52
`
`52
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 51 of 62
`
`US 6,414,677 B1
`
`
`
`FIGURE18
`
`53
`
`53
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 52 of 62
`
`US 6,414,677 B1
`
`ANIMATION LOOP
`PROCESS
`
`4900
`
`
`GET NEXT EVENT
`(TASK) FROM QUEUE
`
`
`FIGURE
`19A
`
` :
`
`
`EVENT OR HEAD
`
`LOCATION EVENT
`
`POINTER
`
`1908 —,
`
`DETERMINE
`VIEWING POINT
`
`1906
`
`1910
`
`YES
`
`RETURN
`
`NO
`
`1912
`
`1940
`
`1904
`
`|
`
`FIGURE|
`149A
`
`
`
`FIGURE
`19B
`
`FIGURE 19
`
`3D LOCATION
`
`1914
`
`
`
`1916
`
`
`
`
`
`
`
`OBJECTIS "ACTIVE" AND
`ALL OTHER OBJECTS
`NOT "ACTIVE"
`
`ALL OBJECTS NOT"ACTIVE"
`AND NOT "MOVING"
`
`1918
`
`AND ALL OTHER OBJECTS
`NOT "SELECTED"
`
`54
`
`54
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 53 of 62
`
`US 6,414,677 B1
`
`1928
`
`1930
`
`1962
`
`
`
`UPDATE OBJECT
`LOCATION
`
`1934
`
`YES
`
`UPDATE
`ANIMATION
`
`
`PREDETERMINED
`DISTANCE OF
`
`NO
`
`
`
`
`IS
`OBJECT IS
`
`
`OBJECT
`"MOVING" AND
`
`
`BEING
`ALL OTHER
`
`
`DRAGGED
`OBJECTS ARE
`
`
`?
`NOT "MOVING"
`
`
`STORE
`
`
`LOCATION(S)
`lyes
`OF OBJECT(S)
`TO PERSISTENT
`
`STORAGE
`
`LOCATION
`
`AVOID OBJECT
`OCCLUSION
`
`1936
`
`1938
`
`FIGURE 19B
`
`GENERATEDISPLAY
`AND AUDIO BASED
`ON CURRENT (AND
`PREVIOUS) OBJECT
`STATES, VIEW POINT
`AND CURSOR
`
`55
`
`55
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 54 of 62
`
`US 6,414,677 B1
`
`OBJECT OCCLUSION
`AVOIDANCE PROCESS
`
`
`
`OTHER OBJECT
`IS "PUSHED"
`
`
`
` SET LOCATION
`
`THE OBJECT
`MOVED AWAY FROM
`OF OTHER
`
`
`
`OBJECT BACK
`STORED LOCATION
`
`TO ITS STORED
`OF OTHER
`
`
`
`(PRE-PUSH)
`OBJECT
`
`LOCATION? ?
`
`
`
`
`
`
`
`
`
`STORE (PRE-PUSH)
`LOCATION OF
`OTHER OBJECT
`
`UPDATE LOCATION OF OTHER
`OBJECT TO MAINTAIN A MINIMUM
`DISTANCE BETWEENIT AND THE
`OBJECT (TO AVOID OCCLUSION)
`
`2006
`
`RETURN
`
`FIGURE 20A
`
`56
`
`56
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 55 of 62
`
`US 6,414,677 BI
`
`OBJECT OCCLUSION
`AVOIDANCE PROCESS
`
`1936"
`
`2052
`
`OTHER OBJECT
`IS "PUSHED"
`
`2054
`
`
`
`
`
`UPDATE LOCATION OF OTHER
`OBJECT TO MAINTAIN A MINIMUM
`DISTANCE BETWEENIT AND THE
`OBJECT (TO AVOID OCCLUSION)
`
`
`
`
`
`
`
`2056 (\
`is
`
`
`
`UPDATED
`
`LOCATION OF OTHER
`
`OBJECT WITHIN A
`PREDETERMINED
`DISTANCE OF
`
`LOCATION OF
`ANY OTHER
`OBJECT
`
`FIGURE 20B
`
`2058
`
`
`
`RETURN
`
`o7
`
`57
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 56 of 62
`
`US 6,414,677 BI
`
`DISPLAY/AUDIO
`GENERATION PROCESS
`
`1938’
`
`DISPLAY CURSOR AT
`CURSOR LOCATION
`
`
`
`DISPLAY LANDSCAPE,
`WITH LANDMARKS
`(BASED ON VIEW POINT)
`
`
`
`
`
`
`INITIALIZE OBJECT LOOP:
`OB_CT=1
`
`2102
`
`2104
`
`2106
`
`2444
`
`FIGURE
`21A
`
`FIGURE
`21B
`
`21C
`
`FIGURE
`
`FIGURE 21
`
`
`DETERMINE SIZE OF
`
`OBJECT (OB_CT) BASED
`ON ITS LOCATION
`
`
`DISPLAY SCALED (LOW
`RESOLUTION) OBJECT
`(OB_CT) AT ITS
`
`2108
`
`2110
`
`2114
`
`
`LOCATION
`
`
`FIGURE21A
`
`58
`
`58
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 57 of 62
`
`US 6,414,677 B1
`
`— 2114
`
`
`
`DISPLAY POP-UP
`TITLE ABOVE
`OBJECT (OB_CT)
`
`
`
`
`
`2118
`
`2120
`
`2122
`
`
`
`
`
`WAS
`OBJECT (OB_CT)
`NO_,|PLAY ACTIVATION
`"ACTIVE" IN
`
`PRECEDING
`
`CYCLE
`
`?
`
`
`
`
`AUDIO
`
`
`
`DISPLAY COLORED HALO
`AROUND PERIPHERY OF
`
`
`OBJECT (OB_CT)
`
`2124
`
`2126
`
`
`
`DISPLAY VISUAL INDICATION OF
`OBJECTS DETERMINED TO BE RELATED
`TO OBJECT (OB_CT)
`
`FIGURE 21B
`
`2130
`
`OBJECT (OB_CT)
`
`
`"MOVING"
`
`
`
`59
`
`59
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 58 of 62
`
`US 6,414,677 B1
`
`— 2116
`
`2134
`
`
`
`
`
`2136
`
`YES
`
`OBJECT (OB_CT)
`"PUSHED"
`?
`
`
`
`DISPLAY HIGH
`?
`
`
`RESOLUTION VERSION
`OBJECT (OB_CT)
`OF OBJECT AT
`"SELECTED"
`
`PREFERRED VIEWING
`LOCATION
`
`
`
`
`
`
`
`2138
`
`PLAY PUSHING AUDIO
`
`PROCESS NEXT OBJECT:
`OBCT=OBCT +1
`
`2140
`
`FIGURE 21C
`
`2142
`
`Lo
`
`MAXIMUM OB_CT 2144
`
`IS
`
`OB_CT>
`
`O
`
`N
`
`A
`
`YES
`
`- 2146
`
`RETURN
`
`60
`
`60
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 59 of 62
`
`US 6,414,677 BI
`
`ceAYNSIS
`
`
`
`peyeanoy198/90
`
`
`
`pejeAjoeedjef4O
`
`(oelgoyososino)
`
`AVIS
`
`yalGO
`
`
`
`w04SL0373S.peseejey|LOAraoOulyj9efGOOpzz
`Loardoyelqo“—___
`
`
`Olde0022
`
`OfZZyelqoweyjouy§/qaHsnd,
`
`LaredoYOTVILINI
`“‘oeALLOYLinvsaa
`
`
`hoeiqoTeroT6Eno)
`hebBeigpesesjey
`yoelqopebbeg
`
` ysnd\/“Aid84}JoeouEISIQ|/peujuueyepelesUIYYM|JeBuo7onjoel
`
`yo=etyjouoyeso7
`;HsNdsudVNSawnssy|ee\Loarao,.\YSHLO+=joelggseyio.N
`POUILLIAJAPALeYBHLO
`
`
`JOG0UBSIGLoarao
`
`cos
`
`pebbeiq
`
`61
`
`61
`
`
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 60 of 62
`
`US 6,414,677 BI
`
`/(/goez
`
`vOES
`
`sundidttOE
`
`PoE|o1eeHfEE—ovez
`
`95€2
`
`vSEZpsec
`
`
`ey:iZOeziaty
`
`62
`
`62
`
`
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 61 of 62
`
`US 6,414,677 B1
`
`2404
`
`OBJECT] ANIMATION]
`ID
`TYPE
`
`START
`POSITION
`
`2408
`
`2412
`
`
`
`
`
`
`2400
`
`FIGURE 24
`
`63
`
`63
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 62 of 62
`
`US 6,414,677 B1
`
`
` 2520A
`
`FIGURE 25
`
`FIGURE26
`
`2610
`
`2620
`
`64
`
`64
`
`

`

`US 6,414,677 B1
`
`1
`METHODS, APPARATUS AND DATA
`STRUCTURES FOR PROVIDING A USER
`INTERFACE, WHICH EXPLOITS SPATIAL
`MEMORYIN THREE-DIMENSIONS, TO
`OBJECTS AND WHICH VISUALLY GROUPS
`PROXIMALLY LOCATED OBJECTS
`
`§1. BACKGROUND OF THE INVENTION
`
`§1.1 Ficld of the Invention
`The present invention concernsa userinterface to objects,
`such as informational objects for example, which are stored
`on, or accessed via, a machine such as a computer for
`example. The present invention exploits the spatial memory
`of people.
`§1.2 Related Art
`A brief history of user interfaces is provided below.First,
`knownuser interfaces are introduced in §1.2.1. Then, user
`interfaces which facilitate information access, rather than
`information processing, are introduced in §$1.2.2. Finally,
`needs of users which have not yet been met by user
`interfaces are listed in §1.2.3.
`
`10
`
`15
`
`,,
`
`§1.2.1 Known User Interfaces
`
`2
`computers. The casual user no longer needed to learn
`syntactical rules and enter sequences of commands. As
`personal computers penetrated business to an ever greater
`degree, probably duc to popular and time saving word
`processing and spreadsheet applications, operating systems
`began to employ user interfaces which used a office meta-
`phor which included documents, folders, filing cabinets,
`trash cans, telephone directories, etc. These so-called desk-
`top GUIs have served their users well over the past decade
`or so. However, in addition to using computers for data
`entry, storage and manipulation, people are using computers
`for access to information to an ever increasing degree. This
`recent trend is discussed in §1.2.2 below.
`
`§1.2.2 Migration From Information Processing And
`Desktop Metaphor to Information Access
`In recent decades,and in the pastfive (5) to ten (10) years
`in particular, computers have become interconnected by
`networks by an ever increasing extent; initially, via local
`area networks (or “LANs”), and more recently via LANs,
`private wide area networks (or “WANs”) and the Internet.
`The proliferation of networks,
`in conjunction with the
`increased availability of inexpensive data storage means, has
`afforded computer users unprecedented access to a wealth of
`content. Such content may be presented to a user (or
`“rendered’”) in the form of text, images, audio, video, etc.
`The Internet is one means of inter-networking local area
`networks and individual computers. ‘The popularity of the
`Internet has exploded in recent years. Many feel that this
`explosive growth was fueled by the ability to link(e.g., via
`Hyper-text links) resources (e.g., World Wide Web pages) so
`that users could seamlessly transition from various
`resources, cven when such resources were stored at gco-
`graphically remote resource servers. More specifically, the
`Hyper-text markup language (or “HTMT.”) permits docu-
`ments to include hyper-text links. These hyper-text links,
`whichare typically renderedin a text file as text in a different
`font or color, include network address information to related
`resources. More specifically,
`the hyper-text
`link has an
`associated uniform resource locator (or “URL”) whichis an
`Internet address at which the linked resource is located.
`When a user activates a hyper-text link, for example by
`clicking a mouse whena displayed cursor coincides with the
`text associated with the hyper-text link, the related resource
`is accessed, downloaded and rendered to the user. The
`related resource may be accessed by the same resource
`server that provided the previously rendered resource, or
`may be accessed by a geographically remote resource server.
`Such transiting from resource to resource, by activating
`hyper-text links for example, is commonly referred to as
`“surfing”.
`Although people continue to use computers to enter
`information, manipulate information, and store information,
`in view of the foregoing developments people are using
`computers to access information to an ever increasing
`extent. In a departure from the past, the information people
`want to access is often not created by them (which would
`typically reside on the person’s desktop computer), or even
`by a companyor group to which that person belongs (which
`would typically reside on a storage server, accessible via a
`local area network). Rather, given the world wide breadth of
`the Internet, the information people wantto accessis usually
`created by unrelated third parties (or content providers).
`Unfortunately, GUIs using a desktop metaphor are not
`particularly well suited for such information access.
`New GUIsshould therefore help people find information
`that they want, or that they might want. Unfortunately, the
`
`The way in which people interact with computing 5
`machines has evolved overthe last 50 or so years. Initially,
`these machines were typically used as information
`processors, and in particular, for performing mathematical
`operations on numbers. People interacted with such early
`computing machines by punching and ordering cards to
`effect a sequence of commands.
`In later computing
`machines, also typically used to perform mathematical
`operations on numbers, people interacted with such com-
`puting machines by setting switches and viewing light
`emitting diodes to enter commands. With the advent of
`the
`desktop personal computer, people-machine interaction
`evolved from the use of a keyboard to enter lines of
`commands, discussed in §1.2.1.1 below,
`to the use of a
`keyboard and mouse to manipulate icon metaphors of
`the
`real world, discussed in §1.2.1.2 below. cl §1.2.1.1 Com-
`mand Lines
`
`
`
`Early personal computers were also used to perform
`mathematical operations, from engineering applications to
`accounting applications (e.g., spreadsheets). In addition,
`such early personal computers were used to enter, store, and
`manipulate information, such as with word processing appli-
`cations for example, and to effectively access stored
`information, such as with relational database applications
`for example. People typically interacted with such comput-
`ers by entering commands, in accordance with fairly rigid
`syntactical rules, or by entering data via a keyboard and
`viewing results via a video monitor. Unfortunately, since the
`syntactical rules for interacting with a personal computer
`were typically not intuitive, people would have to invest a
`fairly substantial amount of time to master effective inter-
`action with the computer. Until they mastered the syntactical
`rules, people would often become frustrated when using
`computers. Casual users would often conclude that learning
`to interact with computers would not be worth their time.
`Thus, computer use was usually limited to professionals
`(e.g., accountants, engineers, and scientists), who needed the
`computational power of personal computers, and to hobby-
`ists.
`
`§1.2.1.2 Graphical User Interfaces
`The advent of graphical user interfaces (or “GUIs’)
`provided a more intuitive way for people to interact with
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`65
`
`65
`
`

`

`US 6,414,677 B1
`
`3
`very vastness of available data can overwhelm a user;
`desired data can becomedifficult to find and search heuris-
`
`tics employed to locate desired data often return unwanted
`data (also referred to as “noise”).
`Various concepts have been employedto help users locate
`desired data. In the context of the Internet for example, some
`services have organized content based on a hierarchy of
`categories. A user may then navigate through a series of
`hierarchical menusto find content that may be of interest to
`them. An example of such a service is the YAHOO™ World
`Wide Website on the Internet. Unfortunately, content, in the
`form of Internet “web sites” for example, must be organized
`by the service and users must navigate through a predeter-
`mined hierarchy of menus.If a user mistakenly believes that
`a category will be of interest or include what they were
`looking for, bul the category turns oul to be irrelevant, the
`user must backtrack through one or more hierarchical levels
`of categories.
`Again in the context of the Internet for example, some
`services provide “search engines” which search database
`content or “web sitcs” pursuant to a user query. In response
`to a user’s query, a rank ordered list, which includes brief
`descriptions of the uncovered content, as well as a hypertext
`links (text, having associated Internet address information,
`which, when activated, commands a computer to retrieve
`content from the associated Internet address) to the uncov-
`ered content is returned. The rank ordering of the list is
`typically based on a match between words appearing in the
`query and words appearing in the content. Unfortunately,
`however, present limitations of search heuristics often cause
`irrelevant content (or “noise”) to be returned in response to
`a query. Again, unfortunately, the very wealth of available
`content impairs the efficacy of these search engines sinceit
`is difficult to separate irrelevant content from relevant con-
`tent.
`
`The foregoing means permit users to find content of
`interest to them, or to deliver content that may beofinterest
`to a user. Unfortunately, neither of the foregoing means is
`particularly well suited when the user wants to “go back”to
`(or “relocate”) information (or content), to revisit that infor-
`mation or to revisit a familiar content provider to view new
`information (or content). More specifically, a person typi-
`cally does not want
`to go through steps of navigating
`through a hierarchy of menus, or entering a search query to
`get to favored content or favored content providers.
`
`§1.2.2.1 Information Access User Interfaces and
`Their Limitations
`
`In view of the shift towards using computers to access
`information, a numberofuser interfaces has been developed
`to help people revisit or relocate information or content
`providers. A sample of these user interfaces, as well as
`perceived limitations of such user interfaces, is presented
`below.
`
`§1.2.2.1.1 Bookmarks and Favorites Lists
`
`Some so-called “Internet browser” program services, such
`as Microsoft’s Internet Explorer™ for example, permit
`people to create lists of favorite Internetlocations (as located
`by a Uniform Resource Locator or “URL”) represented by
`bookmarks. Unfortunately, as the number of bookmarksin a
`list increases, a person’s ability to find a desired bookmark
`becomes more difficult. Although people can arrange and
`organize such lists of bookmarks into hierarchies,
`this
`requires some effort (mental effort is also referred to as
`“cognitive load’) to organize and maintain the hierarchy.
`
`10
`
`15
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`Moreover, the use of hierarchies does not fully exploit the
`spatial memory (This concept has also been reterred to as
`“where it is is what it is”.) of people.
`
`$1.2.2.1.2 Information Visualizer
`
`Recognizing the trend towards the use of computers for
`information access,the article: Robertson,et al., “The Next
`Generation GUIs: Information Visualization Using 3D Inter-
`active Animation,” Communications of the ACM, Vol. 35,
`No. 4, pages 57-71 (April 1993) (hereinafter referred to as
`“the Information Visualizer article”) discusses various pro-
`posals for an “Information Workspace”. More specifically, a
`three-dimensional rooms metaphor, three dimensional hier-
`archical cone trees, and perspective walls are discussed as
`means to present information to users. Each of these tech-
`niques is introduced below.
`Although the three-dimensional room metaphor exploits,
`least
`to some degree, a person’s spatial memory, the
`at
`person has to manipulate objects or move to disambiguate
`images and reveal hidden information.
`Although the three-dimensional hierarchical cone trees
`are useful for visualizing large amounts (e.g., 600 directories
`of 10,000files) of hierarchical data, they lend themselves to
`predetermined hierarchies such asfile directories, organiza-
`tional structure, etc. Thatis, it is believed that the strength
`of three-dimensional hierarchical cone trees lies in present-
`ing information, not building or updating hierarchies of
`information.
`
`The perspective wall permits information, having some
`sort of linear relationship or thread, to be presented in the
`relatively narrow aspect ratio of a typical video monitor.
`Whenanitem is selected, the wall movesthe item to a center
`portion of the wallas if it were a sheet in a player pianoreel.
`Its intuitive three-dimensional metaphor allows smooth tran-
`sitions among views,
`thereby helping a user to perceive
`object consistency. Files may be classified by their modifi-
`cation date. Although the perspective wall technique lends
`itself to information having a linear(e.g., timeline) thread,
`this technique is less useful for other types of information,
`or for information in whicha linear thread is unimportant. In
`fact, to have maximum impact, the perspective wall should
`be combined with an information retrieval technique for
`highlighting similar or related items to a selected item.
`Moreover, a user is confined to relating information to some
`type of a linear thread.
`Apart from the limitations of the three-dimensional hier-
`archical cone tree and perspective wall techniques intro-
`duced above, in these techniques, there is little user choice
`about where an informational object is located in the user
`interface—it either has a spot in a hierarchy or a spot on a
`linear thread. Although it is true that a user can define a
`hierarchical structure or determine what linear thread the
`informational objects are to be related, once the structure or
`thread is determined, user choice about where to locate the
`information object is removed.
`
`§1.2.2.1.3 Web Book/Web Forager
`Another article, Card, et al., “The WebBook and Web
`Forager: An Information Workspace for the World-Wide
`Web,” Proceedings of CHI ’96, pp. 111-117 (Apr. 13-18,
`1996) (hereafter referred to as “the WebBookarticle”) also
`recognized the trend towards the use of computers for
`information access. Focusing on the use of the Internet, the
`WebBookarticle noted, among other things, that web pages
`are often hard to find, users get lost and have difficulty
`relocating pages, and users have difficulty organizing found
`
`66
`
`66
`
`

`

`US 6,414,677 B1
`
`5
`pages. The article then discussed a WebBook™ type elec-
`tronic book which simulates, in three dimensions, a physical
`book and includes pages, each of which correspond to a web
`page. Hypertextlinks are color coded to indicate whether the
`referenced web page is within the currently opened book or
`not. If the web page referenced by the link is in the book,
`activating the hypertext link will cffect an animation of
`flipping pages to the desired web page. If the web page
`referenced by the link is not in the book, activating the
`hypertext link will close the currently opened WebBooktype
`bookand,if the web page is in another WebBooktype book
`ona simulated bookshelf, will open that WebBooktype book
`to the selected web page. The user can flip or mffle through
`the pages of the WebBook type book using various input
`techniques. Portions of interest on a web page may be
`inspected with panning and zooming operations. The Docu-
`ment Lens feature described in the WebBookarticle is
`related to U.S. Pat. No. 5,670,984 to Robertson
`(incorporated herein by reference).
`Although the WebBook type book uses screen space
`efficiently and uses a familiar metaphor, it has a number of
`limitations. Tirst, the book metaphor limits the number of
`web pages that can be seen at one time—most pages are
`occluded. Second,
`the book metaphor does not exploit
`spatial memory. That is, it is belicved that user will only
`rememberthe ordered pagesin a linear (or one-dimensional)
`manner.
`
`The WebBookarticle also discusses a Web Forager which
`embeds the WebBook type book and other objects in a
`hierarchical three-dimensional workspace. The workspace
`includes four (4) hierarchical levels; namely a focus place,
`an immediate memory space, a secondary storage area, and
`a tertiary storage area.
`In the focus place, objects are
`rendered in full size and can be acted uponby the user. The
`immediate memory space uses the metaphor of a desk top.
`The secondary storage area uses several tiers in Z-space, in
`which objects can be moved. Finally the tertiary storage area
`uses a bookshelf metaphor. A boo