US006414677B1
`(10) Patent No.:
`a2) United States Patent
`US 6,414,677 B1
`Robertson etal.
`(45) Date of Patent:
`Jul. 2, 2002
`
`
`(54) METHODS, APPARATUS AND DATA
`STRUCTURES FOR PROVIDING A USER
`INTERFACE, WHICH EXPLOITS SPATIAL
`MEMORYIN THREE-DIMENSIONS, TO
`
`OTHER PUBLICATIONS
`
`ae
`Fahlen et al (“A Space Based Model for User Interaction 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
`(US)
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`US.C. 154(b) by 150 days.
`
`(*) Notice:
`
`(21) Appl. No.: 09/152,712
`:
`22)
`Filed:
`Sep. 14, 1998
`(22)
`File
`ep.
`7
`(51)
`Tint. C0 eee cneseneeeceneneeenees GO06T 15/00
`(52) US. Cl
`345/419: 345/848; 345/764
`(58) Field of Search .ccccssssssssssesssseeee 345/419, 425,
`345/334, 335, 339, 348, 355, 149, 967,
`977, 716, 751, 752, 753, 694, 762, 763,
`764, 765, 766, 767, 768, 769, 810, 812,
`825, 835-839, 848
`
`(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 Mackinlay et al.
`.......... 395/160
`3/1994 Robertson et al.
`7/1994 Robertson ............
`. 395/155
`
`8/1994 Robertsonetal. .......... 395/157
`10/1994 Robertson etal... 395/119
`1/1995 Mackinlay et al.
`......... 395/152
`4/1996 Robertsonetal. .......... 395/119
`
`.........
`... 389/670
`6/1996. Stefik et al.
`3/1997 Robertson ............
`we. 395/127
`9/1997 Robertson etal. .......... 345/139
`11/1997 Mackinlay et al.
`......... 345/427
`
`we. 395/127
`11/1997 Robertson............
`6/1998 Sheridon etal. .............. 345/84
`
`
`
`Introducing MAPA,
`“Dynamic Diagrams”, Products
`MAPA™, download from http:/Awww.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. Hightoweret al, “Graphical Multiscale Web Histories:
`A Study of PadPrints”, Hyper Text 98, pp. 58-65.
`S.K. Card et al, “The WebBook and the Web Forager: An
`,
`g
`Information Workspace for the World—Wide Web”.
`R.L. Kullberg, “Dynamic Timelines Visualizing Historical
`information in Three Dimensions”, Masters Thesis, B.S.
`Environmental Science, Massachusetts Institute of Technol-
` 08¥» Cambridge, MA (1995).
`(List continued on next page.)
`
`Primary Examiner—Mark Zimmerman
`Assistant Examiner—Mano Padmanabhan
`(74) Attorney, Agent, or Firm—Michaelson & Wallace;
`Peter L. Michaelson
`
`(57)
`
`ABSTRACT
`
`A graphical user interface in which object thumbnails are
`rendered on a simulated three-dimensional surface which(i)
`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)
`
`2200
`
`2210
`
`
`Object Activated
`(Cursor
`object),
`INITIAL OR
`
`OBJECT
`DEFAULT
`
`NH”|"ACTIVE"
`Object Selected
`STATE
`
`
`
`(Click)
`Object Deactivated
`
`{Cursoroffobject)
`Object
`one
`Dragged,
`Released
`Dragged
`OBJECT
`
`a Object
`"SELECTED"
`
`2240 OBJECT\ReleasedObject within
`
`OTHER\Predetermined\"MOVING"
`Distance of
`OBJECT
`“PUSHED"/
`Another Object
`2230
`/ Object No Longer
`| within Predetermined
`4
`{ Distance ofthe Pre-
`\ push Location ofthe = ——~ .7
`\ Other Object=7 OTHER ~.
`\
`‘ opvect
`\
`[
`RESUMES
`\ PREPusH /
`~~». POSITION,/
`Sse
`
`Object
`Daselected
`(Click)
`
`2220
`
`4
`ft
`
`é
`
`204s
`
`NS
`
`~.
`
`1
`
`APPLE 1004
`
`APPLE 1004
`
`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”, Human 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. Mander et 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 B1
`
`|||||||||
`
`||||||||||
`
` ZOb|(Shuavads|VLSAYNDSISin(mmokzt
`
`
`opp|SBLNIOd|VUSWWO|
`
`ocLEbelgz,
`
`dyvoONNOS
`
`(YOLVYAISIOVSOINdVHO
`_—SIOCYVH
`
`HLIM)YdLdvavOCIA
`a—3a
`
`SFINGON|(g\wwuDoud|WLSAS
`ONISSSIOYd
`MEHLO.|NOWVOMddy|ONILWYadO
`
`
`
`ASIGYVH
`
`SAMO
`
`Zet
`
`BEL
`
`WALSAS
`
`NOILVONddV¥
`
`(S)WvedOud
`
`WvuOOud
`
`S3INGOW
`
`YSHLO
`
` WvdoOud
`
`L
`
`SFL
`
`(S)LINN
`
`A0VsySLNI
`HYOMLSN
`
`LYOdTvidas
`30vsy3LNI
`SACXSIG
`JOVsIYaLNI
`WollLdO
`3AMCXSId
`JOVAYALNI
`30VAYSLNI
`
`QILANOVW
`
`82L
`
`ONILVWYSdO
`
`
`
`
`ouspave,renrove]!
`
`rabyt
`
`YALNdWOO:
`
`6rl
`
`OOL
`
`Wvdd0ud
`VLVG
`WvuoOud
`
`3
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 2 of 62
`
`US 6,414,677 B1
`
`/LNdNI
`
`LNdLno
`
`JOVSAYSLNI
`
`(S)LINA
`
`OL
`
`MYOMLANYOSNEWALSAS
`
`cob
`
`(S)\YOSSS0ONd
`
`901
`
`
`
`(S)ADIAZG39VYOLS
`
`qbFYNSls
`
`4
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 3 of 62
`
`US 6,414,677 B1
`
`Losardo
`
`ONIMAIA
`
`$S390ud
`
`e972
`
`LINAWS9VNVAN
`
`LNdLno
`
`SALLOSdSu3d
`
`SSI90udMalA
`
`SSa90ud
`
`OaudAsaYd
`Ssdd0udd
`
`olanv
`
`LNdLNO
`
`OAdIA
`
`LAdLNO
`
`ssdo00ud
`
`ssad0ud
`
`ssd00ud
`
`NOILWNIWYAL3S0
`NOILVINNIS
`
`$$3900ud
`
`SS300ud
`
`ALINIXOdd
`
`YSLSNTO
`
`xXvTIvevd
`NOILVYANAS
`NOILWNIWYSLSG
`
`LILd-dOd
`
`
`
`LNIOdONIMGIA
`
`
`6°98)SS9WWI“B'a)SHOVIOL2av3H6°8)MSINIOd
`
`
`
`
`
`(Sava(SdvWI8aov4unsNOLLY01LNdNI(aSNOW
`
`
`
`sLoaradoS$L03argoCc0OD91z
`HOIHo/z{MOTv2Zzp12
`
`
`
`892LIOMdWIdNdOd9cz‘ALLOW,‘6'e)
`vseSMYVWONVT
`
`
`
`
`v97ssg00ud39900udSSLveeONY(.GSHSNd.
`|
`NOLLYNINYSLAd
`
`NOLLM10S3uNOLLMIOS3u$2
`
`
`99YALSN1OLOarGOGSNINNaLIGaue06Z
`
`
`822ADO10dOLLNdNISasen
`
`
`
`AYaNdNOLLYZMVLLeSLoargo‘,GSAOW,‘.CSLO3T3S.,
`YOSGHOMASYOSIdO.LLOArGOAOVeOLsS
`
`ozALIMOWdCcYOOTOSINILwoz@aenNdis
`
`Z92092NOILV9O1
`
`olanyIWSLOarEO
`
`SSa90uda2zINSLSISUZd
`
`
`
`AYVeOdWAL
`
`dOA9VYOLS
`
`
`
`GNv)LNSYYND
`
`(SNOIAZYd
`
`31VLS
`
`ose
`
`9SZ202
`
`OLe
`
`922
`
`aNvSS300ud
`
`ss3z00ud
`
`LN3SWA9VNVA
`SSd00ud
`
`LAdNI
`
`QeOLAZ
`
`ONIddVW
`
`anand
`
`LN3ASoee
`
`yOsSYND
`
`NOLLWOO71
`
`NOILVNINYSLad
`
`SS390ud
`
`Ble
`
`3ONVGIOAV
`
`
`
`NOISN1090ssa00ud
`
`5
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 4 of 62
`
`US 6,414,677 B1
`
`00€€aYyNSl4
`
`vOe
`
`39VdANV
`
`éQ351L94148
`
`ovis
`
` OLEZLEeg0€e
`LO373S.|.ALOV.|Hsnd-aua|NOHV90T||oargo
`
`HOLV
`
`QIOHSSYHL
`
`SNITONIdi
`
`
`
`ATONVdvVW
`
`3OvsYyNs
`
`
`
`NOILV901YOSYND
`
`ONIMBSIA
`
`LNIOd
`
`NOILVOO71
`
`al
`
`9ee
`
`(AdAL
`
`Be)FUNLXAL
`
`
`YSadvdTIVM-
`dOYasWNN
`
`SLOArado
`
`6
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 5 of 62
`
`US 6,414,677 B1
`
`+SYNDIS(dWWLIGTaXId79Ag9““6'8)VLVGSDVWINOILNIOSAYMOTdiLoarao
`
`
`
`
`
`
`
`GAYNYDIA(dVLIGTaXidZSAg21S‘6'8)VivdSOVWINOILNIOSSYHOIHdlLOargo
`
`Z3xgnNdIs
`
`002
`
`aeLoarao
`
`GSNINYALaAGSYdYOSGUOMAAMYOSOldOl
`-SONOTSELOSPOHOIHMOL(S)YSLSNTD
`
`
`vOrcOP
`70SZ0S
`sauneld[sui|aussre
`volZ0d
`
`09009z09
`
`
`
`
`
`
`
`
`
`7
`
`
`
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 6 of 62
`
`US 6,414,677 B1
`
`hate. Ne cin
`
`:
`
`;
`
`’
`
`"
`
`
`
`| fist
`
`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
`
`eee
`
`Swimooe y
`
`10
`
`10
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 9 of 62
`
`US 6,414,677 B1
`
`i egao oe ae
`
`Ae
`
`ISLISELY
`
`Dt gee
`dew auvutas
`
`
`
`eetSerer
`
`
`
`pieeetiecce
`
`NEhe
`
`11
`
`11
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 10 of 62
`
`US 6,414,677 B1
`
`find heir accessts much facter.
`
`We're announcing ou twa rien serrer
`farms, one in London, the other in
`Toya, By connecting bo ag Web site
`& through these mimo sibes, many of our
`customers outshde North America may
`
`ARIEL
`
`WellManagedWindowsfase
`
`
`
`SolutionsOffertheLowestCO
`4 yecent Gartner Grup research note
`iolects that 3 well manegat, 32-bit
`Microsoft Windows-based desktop can
`reduce TCO by up to 35 nerent.
`
`wap Bony
`
`12
`
`12
`
`

`

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

`

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

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 13 of 62
`
`US 6,414,677 B1
`
`acyoe
`
`sae
`
`.
`
`s==iea
`
`15
`
`15
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 14 of 62
`
`US 6,414,677 B1
`
`(AB OTAUE aA
`eaeenefibre
`
`
`
`hy Copal
`iid
`
`esi
`
`6 pnb
`© Foca
`
`16
`
`16
`
`

`

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

`

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

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 17 of 62
`
`US 6,414,677 B1
`
`we
`
`Se
`
`is
`
`soprceane
`
`ianRd
`
`19
`
`19
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 18 of 62
`
`US 6,414,677 B1
`
`me
`
`eta yy a Aj
`
`Arpiccnletieudistelies
`
`acieteteretgteete
`
`20
`
`20
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 19 of 62
`
`US 6,414,677 B1
`
`eeSaeeeees
`
`rowenta
`
`bee
`
`21
`
`21
`
`

`

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

`

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

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 22 of 62
`
`US 6,414,677 B1
`
`seeeaen
`
`ocean
`
`te
`
`bh
`
`j
`
`24
`
`24
`
`

`

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

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 24 of 62
`
`US 6,414,677 B1
`
`es
`
`ee
`eas
`
`ij Ryde. ARES
`leaireSacer3
`Shed OEE
`aye
`.
`
`-
`
`ee
`se
`Ses
`i
`
`IGUR
`
`-
`al
`.
`ee edie
`:
`
`:
`
`26
`
`26
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 25 of 62
`
`US 6,414,677 B1
`
`oea©oR
`
`==—Ra
`
`Me:
`
`f
`
`ove ath
`
`ari
`
`27
`
`27
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 26 of 62
`
`US 6,414,677 B1
`
`z
`
`=
`
`%|
`
`oe
`
`==ee2she
`
`28
`
`28
`
`

`

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

`

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

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 29 of 62
`
`US 6,414,677 B1
`
`
`
`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 B1
`
`
`
`FREE
`
`wll
`mM@
`
`33
`
`33
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 32 of 62
`
`US 6,414,677 B1
`
`Sys ise
`
`SLR UES
`ResaSantee 9
`
`ae
`nce
`
`34
`
`34
`
`

`

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

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 34 of 62
`
`US 6,414,677 B1
`
`Siateak
`
`or pse
`
`ae2ceee
`
`ere
`
`36
`
`36
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 35 of 62
`
`US 6,414,677 B1
`
`
`
`11200
`
`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
`
` 4208
`
`|
`
`4200"
`
`FIGURE 120
`
`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
`
`FIGURE 12E
`
`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
`
`PeelaagARSe
`
`piss SealsWea geteo:
`pdpoitidi,soldpuesRae
`‘asedeg
`eaSheenTicker
`ae
`
`FIGURE 13A
`
`43
`
`43
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 42 of 62
`
`US 6,414,677 B1
`
`
`
`it,NoaHehpbasicSati,
`
`Buvealaeendian
`
`1800
`
`FIGURE 138
`
`44
`
`44
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 43 of 62
`
`US 6,414,677 B1
`
`a. Pa"
`
`1302":
`
`en eae meat ee
`
`solanheUae
`:
`Meolipba-
`Sent sere Tpke tak
`Sraghaarerie
`
`ee
`
`5 Nieet
`Sipte
`
`5
`
`‘
`
`1300"
`
`FIGURE13C
`
`45
`
`45
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 44 of 62
`
`US 6,414,677 B1
`
`See
`
`302"
`
`Seema
`
`ee
`
`oyae
`oeee
`
`71300"
`
`FIGURE 130
`
`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
`
`
`
`FIGURE 15A
`
`49
`
`49
`
`

`

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

`

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

`

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

`

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

`

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

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 53 of 62
`
`US 6,414,677 B1
`
`1930
`
`1962
`
`
`STORE
`:
`
`
`1928
`
`
`OBJECTIS
`
`"MOVING" AND
`
`ALL OTHER
`OBJECTS ARE
`
`NOT "MOVING"
`
`
`
`OF OBJECT(S)
`
`TO PERSISTENT
`STORAGE
`
`LOCATION
`
`
`
`LOCATION
`
`1934
`
`YES
`
`UPDATE
`
`ANIMATION
`
`NO
`
`PREDETERMINED
`DISTANCE OF
`
`ANOTHER
`
`
`
`AVOID OBJECT
`OCCLUSION
`
`936
`193
`
`1938
`
`FIGURE 19B
`
`1918
`
`GENERATE DISPLAY
`AND AUDIO BASED
`ON CURRENT (AND
`PREVIOUS) OBJECT
`STATES, VIEW POINT
`AND CURSOR
`
`1940
`
`55
`
`55
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 54 of 62
`
`US 6,414,677 B1
`
`
`
`OBJECT OCCLUSION
`AVOIDANCE PROCESS
`
`
`
`
`
`
`SET LOCATION
`OF OTHER
`
`
`
`
`
`STORED LOCATION
`OBJECT BACK
`OF OTHER
`TO ITS STORED
`
`
`
`(PRE-PUSH)
`LOCATION?
`
`
`
`OTHER OBJECT
`IS "PUSHED"
`
`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 B1
`
`OBJECT OCCLUSION
`AVOIDANCE PROCESS
`
`2052
`
`2054
`
`OTHER OBJECT
`iS "PUSHED"
`
`
`
`
`
`1936"
`
`
`
`2056 (\
`IS
`
`
`
`UPDATED
`
`LOCATION OF OTHER
`
`OBJECT WITHIN A
`PREDETERMINED
`DISTANCE OF
`
`LOCATION OF
`ANY OTHER
`OBJECT
`?
`
`
`
`
`
`FIGURE 20B
`
`UPDATE LOCATION OF OTHER
`OBJECT TO MAINTAIN A MINIMUM
`DISTANCE BETWEENIT AND THE
`OBJECT (TO AVOID OCCLUSION)
`
`
`
`2058
`
`
`
`RETURN
`
`o7
`
`57
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 56 of 62
`
`US 6,414,677 B1
`
`DISPLAY/AUDIO
`GENERATION PROCESS
`
`1938'
`
`DISPLAY CURSOR AT
`CURSOR LOCATION
`
`
`
`DISPLAY LANDSCAPE,
`WITH LANDMARKS
`(BASED ON VIEW POINT)
`
`
`
`
`INITIALIZE OBJECT LOOP:
`OB_CT = 1
`
`
`
`FIGURE
`21A
`
`FIGURE
`1B
`
`FIGURE
`21C
`
`2102
`
`2104
`
`2106
`
`24144
`
`2108
`
`2110
`
`FIGURE 21
`
`
`
`DETERMINESIZE OF
`
`
`OBJECT (OB_CT) BASED
`
`ON ITS LOCATION
`
`
`
`DISPLAY SCALED (LOW
`RESOLUTION) OBJECT
`(OB_CT) AT ITS
`LOCATION
`
`2114
`
`2112
`
`
`
`
`
`
`Is
`OBJECT (OB_CT)
`"ACTIVE"
`
`?
`
`
`
`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
`
`NO,|PLAY ACTIVATION
`"ACTIVE" IN
`PRECEDING
`CYCLE
`?
`
`AUDIO
`
` OBJECT (OB_CT)
`
`
`
`
`
`DISPLAY COLORED HALO
`AROUND PERIPHERY OF
`
`
`OBJECT (OB_CT)
`
`2124
`
`FIGURE 21B
`
`2126
`
`DISPLAY VISUAL INDICATION OF
`OBJECTS DETERMINED TO BE RELATED
`TO OBJECT (OB_CT)
`
`2130
`
`OBJECT (OB_CT)
`
`"MOVING"
`
`
`
`59
`
`59
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 58 of 62
`
`US 6,414,677 B1
`
`— 2116
`
`2134
`
`
`
`2132
`DISPLAY HIGH
`is <<
`
`
`
`
`
`
`RESOLUTION VERSION
`OBJECT (OB_CT)
`OF OBJECT AT
`
`
`
`SELECTED
`PREFERRED VIEWING
`
`
`;
`LOCATION
`
`
`2136
`
`YES
`
`
`
`
`is
`OBJECT (OB_CT)\_
`
`
`“PUSHED"
`?
`
`
`
`2138
`
`PLAY PUSHING AUDIO
`
`PROCESS NEXT OBJECT:
`OB CT=OB CT +1
`
`2140
`
`FIGURE 21C
`
` 2144
`
`YES
`
`- 2146
`
`RETURN
`
`60
`
`60
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 59 of 62
`
`US 6,414,677 B1
`
`Loarao
`
`wO3.LO3T3S.
`
`pebbeg
`
`yoalqo
`
`LOardo
`
`UIYIIM|ozzzHaNONe280//
`pajoejasj2elqOWINLOW\eeSLVLS
`
`
`
`(4919)pe}eAjoeegj0elGO
`
`eee798/90pebbaiq
`'198190
`
`obec00zz
`Of2%Zwoelqoseyjouy=/qaHsnd,
`
`peseojoy
`seyio—N avez!snd-dud\SNsawnssy|~,Loarao,.\YSHLO+=yoelqo
`
`
`hoeiqaTENOT6Sin9)
`(oefgoyo40sinD)
`
`pejeajoy19efGO
`é¢AYNOSIS
`wONIAOWL
`pebbeigpesfenoY
`
`LOarao
`¢~S—~—~—ayjjouojeso7ysnd\77“Gley}JOBOURISIC|/peujULejepele}
`fNOUISOD\e
`
`“’_U_L____ee
`
`peujuule}epeleYSHLO
`40B0UBISICLoarao
`
`ulyj9eIGO
`YOTVILINI
`Linvs3a
`
`=~
`
`“\
`
`OFeZ
`
`61
`
`61
`
`
`
`
`
`

`

`U.S. Patent
`
`Jul. 2, 2002
`
`Sheet 60 of 62
`
`US 6,414,677 B1
`
`qunolsa2aynold
`aezESa.vez
`
`PpEYoveziorec
`
`9SE2
`
`SEZySEe
`
` 902/!
`a:z0ezaZ0ez
`et|
`
`voc?
`
`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
`
`2510B
`
`2520B
`
`2522
` 2520A
`
`FIGURE 25
`
`FIGURE 26
`
`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 Field of the Invention
`The present invention concernsa user interface 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.
`
`§1.2.1 Known User Interfaces
`
`The way in which people interact with computing
`machines has evolved over the 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 concludethat learning
`to interact with computers would not be worth their time.
`Thus, computer use was usually limited to professionals
`(e.g., accountants, engineers, andscientists), 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
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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 due 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 past five (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 wasfueled by the ability to link (e.g., via
`Hyper-textlinks) resources (e.g., World Wide Web pages) so
`that users could seamlessly transition from various
`resources, even when such resources were stored at geo-
`graphically remote resource servers. More specifically, the
`Hyper-text markup language (or “HTML”) permits docu-
`ments to include hyper-text links. These hyper-text links,
`whichare typically renderedin a textfile 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 want to access is 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 GUIs should therefore help people find information
`that they want, or that they might want. Unfortunately, the
`
`65
`
`65
`
`

`

`3
`very vastness of available data can overwhelm a user;
`desired data can becomedifficult to find and search heuris-
`
`US 6,414,677 B1
`
`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
`Recognizing the trend towards the use of computers for
`information access,the article: Robertson, et al., “The Next
`services have organized content based onahierarchy of
`categories. A user may then navigate through a series of
`Generation GUIs: Information Visualization Using 3D Inter-
`hierarchical menusto find content that may be ofinterest to
`active Animation,” Communications of the ACM, Vol. 35,
`them. An example of such a service is the YAHOO™ World
`No. 4, pages 57-71 (April 1993) (hereinafter referred to as
`Wide Website on the Internet. Unfortunately, content, in the
`“the Information Visualizer article”) discusses various pro-
`form of Internet “web sites” for example, must be organized
`posals for an “Information Workspace”. More specifically, a
`by the service and users must navigate through a predeter-
`three-dimensional rooms metaphor, three dimensional hier-
`mined hierarchy of menus. If a user mistakenly believesthat
`archical cone trees, and perspective walls are discussed as
`a category will be of interest or include what they were
`means to present information to users. Each of these tech-
`looking for, but the category turns out to be irrelevant, the
`niques is introduced below.
`user must backtrack through one or more hierarchical levels
`Although the three-dimensional room metaphor exploits,
`of categories.
`at least to some degree, a person’s spatial memory, the
`Again in the context of the Internet for example, some
`person has to manipulate objects or move to disambiguate
`services provide “search engines” which search database
`images and reveal hidden information.
`content or “web sites” pursuant to a user query. In response
`Although the three-dimensional hierarchical cone trees
`to a user’s query, a rank ordered list, which includes brief
`are useful for visualizing large amounts(e.g., 600 directories
`descriptions of the uncovered content, as well as a hypertext
`of 10,000 files) of hierarchical data, they lend themselves to
`links (text, having associated Internet address information,
`predetermined hierarchies such asfile directories, organiza-
`which, when activated, commands a computer to retrieve
`tional structure, etc. Thatis, it is believed that the strength
`content from the associated Internet address) to the uncov-
`of three-dimensional hierarchical cone trees lies in present-
`ered content is returned. The rank ordering of the list is
`ing information, not building or updating hierarchies of
`information.
`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.
`
`4
`Moreover, the use of hierarchies does not fully exploit the
`spatial memory (This concept has also been referred to as
`“where it is is what it is”.) of people.
`
`§1.2.2.1.2 Information Visualizer
`
`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 wall as 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 which a 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-dimensionalhier-
`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
`
`10
`
`15
`
`20
`
`35
`
`The foregoing means permit users to find content of
`interest to them,or to deliver content that may beof interest
`to a user. Unfortunately, neither of the foregoing meansis
`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
`
`Someso-called “Internet browser” program services, such
`as Microsoft’s Internet Explorer™ for example, permit
`peopleto createlists of favorite Internet locations (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.
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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. Hypertext links 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 effect 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 WebBook type
`book and,if the web pageis in another WebBooktype book
`on a simulated bookshelf, will open that WebBook type book
`to the selected web page. The user can flip or ruffle 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 numberof
`limitations. First, the book metaphor limits the number of
`web pages that can be seen at one time—mostpages are
`occluded. Second,
`the book metaphor does not exploit
`spatial memory. That is, it is believed that user will only
`rememberthe ordered pages in 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 upon bythe user. The
`immediate memory space uses the metaphorof a desk top.
`The secondary storage area uses several tiers in Z-space, in
`which objects