Adaptive Semantic Snapping - A Technique For Semantic Feedback At The .
April 1990CHI 90 PmceedrwsADAPTIVE SEMANTIC SNAPPING - A TECHNIQUEFOR SEMANTIC FEEDBACK AT THE LEXICAL LEVELScott E. HudsonDepartment of Computer ScienceUniversity of ArizonaTucson, AZ 85721hudson@cs.arizona.eduABSTRACTThis paper describes the implementation of semanticsnapping - an interaction technique that provides semanticfeedback at the lexical level while dragging a graphicalobject on the screen. Like conventional snapping, orgravity Betis, semantic snapping includes a geometriccomponent where objects in close proximity are drawntogether or “snap” into position. However, semanticsnapping goes further by allowing non-geometric(semantic) properties of objects to place additionalconstraints on snapping. Semantic snapping also providesmore complex lexical feedback which reflects potentialsemantic consequencesof a snap. This paper motivates theuse of semantic snapping and describes how this techniquehas been implemented in a window-based toolkit. Thisimplementation works in an adaptive manner to provide thebest interactive response in situations where semantic testsare very time consuming and strain the limits of acceptableperformance.INTRODUCTIONANDMOTIVATIONThe interaction technique of snapping or gravityfields wasintroduced as part of someof the earliest work in interactivecomputer graphics. This technique is applied whengraphical objects are dragged or stretched on the screen.Screen positions that correspond to correct or preferredending points for the drag are given gravity - that is, whenthe cursor is near one of these points (or lines) it is attractedto, or snapped to, that point. For example, in a schematicdiagram editor, component symbols and wires are typicallyattached to each other rather than being placed in arbitraryunconnected positions. Snapping allows these legalconnected positions to be specified in preference to illegalunconnected positions. This allows the user to specifyThis work was supported in part by the National ScienceFoundation under grant W-8702784.connections more easily and with less precise movements.As a result, for tasks that can employ snapping, it issometimes possible to overcome the fundamentallimitations of human performance described by Fitts’ lawIFitt54].Unfortunately, snapping has not been supported by thetoolkits now popular for user interface development (see forexample [McCo88, Lint89]) and the use of snapping inmodern systems in general has not been widespread. Anotable exception to this is the Gargoyle drawing editor[Bier86a]. In this system, reference objects that are not partof the final drawing may be used as guides for alignmentand geometric construction. These reference objects, aswell as their intersection points, are given gravity to makealignment and construction easier. Becausethese referenceobjects represent a locus of semantically interesting points,the techniques employed by the Gargoyle drawing editor(and in related work [Bier86b, Bier88]) can be seen as aform of semantic snapping. However, these techniques relysolely on geometric constraints to control snapping andprovide feedback. ‘Ihe techniques presented here arespecifically designed to compliment this approach bysupporting additional control and feedback based onsemantic properties that are not adequately expressed in ageometric context.A good example of this occurs in visual programmingenvironments such as the one shown in Figure 1. In thisenvironment computational elements are represented byicons and dataflow between thesecomputational elements isrepresentedby lines. An editor for.constructing thesevisualprograms should perform type and other semantic checking.For example, the system shown in Figure 1 must ensurethat connected ports send and receive data values ofcompatible types and that cycles are not introduced. Ingeneral, we support the view that:It is better to prevent errors than to simplyreport them after they occur.Permission to copy without fee all or part of this material is grantedprovided that the copies are not made or distributed for directcommercial advantage, the ACM copyright notice and the title ofthe publication and its date appear, and notice is given that copyingis by permission of the Association for Computing Machinery. Tocopy otherwise, or to republish requires a fee and/or specificpermission.0 1990 ACM O-89791 -345-O/90/0004-00651.50Consequently, one goal of a program editor like the oneshown in Figure 1 might be to not only detect cycles andtype conflicts, but prevent them. This can be done usingsemantic snapping. As dataflow lines are stretched between65
CHI 90 ProceedingsApfil1990./ 1 j:;.Iii.I :’ 1.jiiI .IFigure 1. A Visual Programming Applicationports, they snap only to legal connecting ports and never toports which would represent an error. Figure I shows thefeedback for such a legal snap between the “Select” and“Extend” nodes.important in situations where semantic tests are complexand strain the limits of acceptable response time. Finally,Section 4 will present conclusions.SNAPPINGAs shown in Figure 2, illegal ports can supply anri-gravitywhich provides negative feedback for illegal connections.In this example, the user is attempting to create a cycle byconnecting to the port at the left hand comer. Theconnection is of course disallowed, but the system alsoprovides appropriate feedbackindicating why the connectioncan’t be made. In general, any desirable or undesirableproperty of a connection between objects can be tested andused as the basis for snapping control and feedback. Thisallows important but otherwise invisible properties of theobjects being manipulated to be made apparent. It alsoallows the consequences of user actions to be indicatedbefore the user commits to these actions. Both theseproperties serve to improve the directness of the interface utc86].In the next section a simple set of primitive snappingconcepts will be considered along with techniques to aIlowthe user more control over snapping. In Section 3, animplementation of semantic snapping in a window-basedtoolkit will be described. This implementation employsnovel techniques that directly measure the progression ofreal time in order to adapt the system to the timing requiredfor good interactive response. This is particularly66CONCEPTSIn a wide range of interfaces such as graph, diagram, orschematic editors, the result of dragging is often to make aconnection or relationship between two underlying objects.For example, in some systems [Myer86, Myer89, Huds89],geometric positions are used to infer constraints. Suchconstraints and relationships normally have implications inthe underlying application domain. A primary purpose ofsemantic snapping is to express these important semanticimplications to the user as early as possible.Semantic snapping is built on a geometric basis - anobject or set of objects that represent legal, desirable, orsemantically interesting locations. These locations areoften fixed, but sometimes must be computed “on the fly”based on factors such as the state of the interaction, valuesfound in the underlying application data, and the objectcurrently being dragged. These locations are often points,however, snapping to line segments and circles can also beuseful.Each object that supports snapping may have one or moresnapping locations, or sires, associated with it. Allsnapping is done on the basis of snap sites rather thanwhole objects, IEachsite may be active or inactive at any
Apil19!30CHI 90 Ptoceedir- Figure 2. Anti-gravity Feedback for an Illegal Connectiongiven time. Activity or inactivity of a site is determined bya predicate function supplied by the site. This function hasaccess to the internal state of the object and may testarbitrary semantic properties to determine its result. Forexample, the sites used in the visual programming systemshown in Figures 1 and 2 are disabled when their maximumfan-in or fan-out has beenexceeded.Once a set of sites has been declared, it is the job of thesnapping system to continuously search for a valid snapsite and to provide appropriate feedbackwhen one is found.This is done by finding the site closest to the cursor which:a) is active, b) is within a critical snapping distance, and c)passessemantic tests provided by the snap sites involved.In particular, each snap site provides a predicate functionthat can dynamically test whether a potential snap issemantically valid. One of the major focuses of the workpresented here is a set of implementation techniques thatattempts to provide the best possible response in situationswhere these semantic tests are time consuming.!t is also the job of the snapping system is to providefeedback about snaps. Whenever a new valid snap site isfound, both the object being dragged and the object beingsnapped to are informed by calling a feedback function.This function is implemented by the object so that it canprovide feedbackthat reflects both the state of the object andsemantic consequencesof the snap. Similarly, whenever anexisting snap is broken - either by moving too k awayor by explicit user action (see below) - both objects areinformed so that feedback can be removed. In addition, tonormal snap feedback, each site has the option of providingnegative “anti-gravity” feedback. As illustrated in Figure 2,this feedback serves the purpose of an error message,indicating that a snap cannot be perf6rmed and why. Antigravity feedback is applied only when no valid snap can befound. Like normal feedback it is applied to the closest sitewhich: a) is active, b) is within snapping distance, c) failssemantic tests, and d) has requested the application of antigravity.In addition to the application of feedback, the snap systemis responsible for resolving ambiguous snaps and forproviding a user controlled reject capability. Because theactive region of a snap site extends over au area rather thana single point (of line or circle), sites that have overlappinggravity fields may be difficult to select correctly. Inaddition, it may be possible for one cursor location to beequally close to more than one site, resulting in anambiguous situation. This is particularly difficult to dealwith if two or more sites occur at exactly the same pixellocation (e.g. when both a line segment and its endpointsare snap sites). In situations where snaps are ambiguous, apriority scheme is used to select one site from among ties.However, this system is too limited to serve in all cases.To overcome this problem it is essential that a snap systemalso allow user controlled rejection of snaps. In the systemdescribed here, users may explicitly reject a snap by67
CHI 90 Pmeediqspushing another locator button or a designated keyboardkey. Once a snap is rejected, the corresponding site istemporarily inactivated so that it does not interfere withselection of nearby sites. An inactivated site may bereactivated either by starting a new drag, or by moving faraway from the snap site then returning.IMPLEMENTATIONThe snapping concepts introduced in the last section havebeen implemented in Artkitthe Arizona RetargetableToolkit. This system is an object-oriented toolkit writtenin C and C which is designed to be hosted by a numberof different underlying window systems. The toolkitcurrently runs under both the X and the SunView windowsystems and can be easily retargeted to additional windowsystems.The primary challenge of implementing semantic snappingis making it run quickly enough so that good interactiveresponse can be provided even when time consumingsemantic tests need to be performed.The Artkitimplementation uses four techniques to produce a fastimplementation - a good geometric search algorithm,declaration and optimization of common special cases,“hiding” of work based on non-linear human perception ofresponse time, and most importantly, adaptation based onmonitoring of actual real-time performance.Becausethe geometric proximity tests required for snapping(i.e., finding all the sites within the critical snappingdistance) are typically faster than semantic tests, geometricsearching is done first. Semantic tests are performed onlyon the small set of active snap sites found to be withinsnapping distance.The geometric search done in the Artkit implementation isbased on a bucketing technique. In this scheme, eachwindow is broken up into square buckets of a fixed size andeach snap site is assigned to the bucket or buckets it occursin. Most sites have a static position and stay in onebucket, but some sites may have to have their bucketrecomputed when dragging starts. The system currentlyuses a fixed bucket size of 32x32 pixels. This sizerepresents a good compromise in space versus speed. If1024x1024 is assumedto be the largest window size, therewill be at most 1024 buckets in a window. Thus, space forthe bucket structure itself is not unreasonable (a maximumof 4k bytes per window). Furthermore, using the highdensity rejection technique described below, it is possible toguarantee that no more than 114 snap sites occur in onebucket. This corresponds to a snap site at every third pixeland is a reasonable approximation to the upper limit ofwhat the user can handle interactively. Since the cursormay be near the corner of a bucket and hence the snappingarea may overlap 4 buckets, this leads to an absolutemaximum of 456 snap sites that must be considered at anytime.Large numbers of snap sites that occnr very close together(within a few pixels) can place a heavy burden on the snap68April 1!390test algorithm, requiring many sites to be tested for eachcursor movement and potentially overloading somebuckets.In addition, when snap sites occur close together, it isdifficult for the user to select the desired site even when theexact pixel position of the site can be determinerl visually.In casesof ambiguity, the system makes what amounts to areasonable guess (the closest site with ties broken bypriority) in its :selection of a snap site. It then allows theuser to explicitly reject this point if the guess was wrong.In order to limit. the number of sites that must be consideredon each cursor movement, the snap search algorithmmodifies the way this guess is made in instances wheresites are very close together (within 3 pixels in x and y). Inparticular, the system temporarily eliminates fromconsideration snap sites that are too close to other (higherpriority) snap sites. If a site is explicitly rejected, anypreviously eliminated site will be placed back intoconsideration so that it can be subsequently picked by theuser. This approach keeps the system from bogging downwhen overloaded, resulting in better performance when thesystem is saturated, with little or no effect on the end user.Once the set of sites within snapping distance has beendetermined, semantic tests are performed (closest snap sitefirst) to make a final selection. Semantic tests areperformed by calling a predicate function provided by eachsnap site. In some rare cases, the result of the predicatedepends on a continuously varying value. However,usually, the result of the predicate depends only on valuesthat do not change over the course of a single dragginginteraction and the predicate neednot be evaluated more thanonce for each drag. In some other situations, the result of apredicate does n,ot depend on the object being dragged andchanges only rarely. Here, the underlying application caninform the snap system whenever changes occur. Thesystem handles each of these cases - conthuous, single,and demand evaluation - separately. For demandevaluation, the application informs the snapping systemwhenever the result of the semantic test might change. Thesystem then evaluates the test function and remembers theresult. By default, single evaluation is used so that thesystem evaluates each test function at most once andremembers the result for the duration of the drag. Only inthe case of continuous evaluation does the system evaluatethe semantic test function each time the cursor moves.Human perception of response time in dragging tasks hasnot been widely studied and to the author’s knowledge, nostudy has ever been made of dragging with snapping.However, early studies of remote control manipulation ofobjects under time delay (see for example (Sher631) alongwith informal experience with dragging tasks, indicates thatdragging with long lags in response is difficult to control.Conversely, delays below a small threshold tend to remainunnoticed. The system uses these facts to attempt to ensuregood interactive response.The system directly monitors real-time performance andadapts in an effort to meet response time goals. Inparticular, the system uses soft limits for the time spent at
CHI 90 l’mxedimthe beginning of a drag (usually after a locator button downevent) and for the time spent after each cursor movementevent. The system performs semantic tests until either asnap site is determined or the time limit has expired and anew event is waiting to be processed (note: time limits arenon-preemptive). if the time limit has expired, the bestsnap site found thus far is used. If no valid snap sites arefound within the time limit, no snap is made, but thesystem resumes testing where it left off when processingthe next movement event. This ensures that if the cursorstays in the area of a valid snap site, the system willeventually find it. While the system cannot always meetresponse time goals, this approach allows the system todegrade gracefully. In situations where it cannot meetperformance goals, the system either selects a nearby validsnap site or delays snapping for several movement events.In either case, disruption of normal system functioning isminimized. Furthermore, this approach allows the systemto automatically respond to varying system load as well asproviding transparent portability to new processors withdifh-ing speed.In addition to real-time response goals, the system alsoattempts to “hide” work by making use of the non-linearhuman perception of response time. When a snap site isfound very quickly, additional time - up to a minimumtarget time designed to remain unnoticed by the user - isspent evaluating the semantic functions of nearby snapsites. This allows work to be hidden in unperceived delaysin hopes of shortening later delays. Similarly, informalexperience indicates more user tolerance for delay at theimmediate beginning of a drag (i.e., after a locator buttonhas been pressed but before selection feedback has beenprovided) than during the drag itself. Consequently, thetime limit at this point in the interaction is made longer.This allows the system to get a head start by evaluating thesemantic functions of snap sites near the initial cursorposition.The system allows the application to provide time limits.However, it also provides defaults for these values. Thecurrent, defaults were arrived at by trail and error and areonly preliminary approximations - no claim is made as totheir “correctness” from a human factors point of view. Amore formal and complete study is neededto determine howthesedefault values should really be set in practice.The four techniques described above - a good geometricsearch algorithm, declaration and optimization of commonspecial cases, “hiding” of work , and most importantly,adaptation based on monitoring of actual real-timeperformance - serve to create an implementation which isvery robust and which degradesgracefully in the presenceofexpensive semantic tests. This allows applicationsdesigners to use semantic snapping with confidence,knowing the system will automatically adapt to varyingloads and exceptional situations.Apfill990CONCLUSIONThis paper has considered an implementation of semanticsnapping.Semantic snapping offers a number ofadvantages by increasing the level of feedback provided tothe user and by allowing errors to be prevented rather thansimply detected. An adaptive implementation technique forsemantic snapping has also been discussed. This techniqueuses soft real-time limits to monitor interactive responseofthe system and to automatically adapt the performance ofthe system. This allows the system to degrade gracefullyand provide the best responseunder high load situations.REFERENCES[Bier86a]Bier, E., Stone, C., Snap-Dragging, ComputerGraphics, 20, n4, August 1986, pp. 233-240.[Bier86b]Bier, E., Skitters and Jacks: Interactive 3DPositioning Tools. Proceedings of the ACMSIGGRAPH Workshop on Interactive 30Graphics, Chapel Hill, NC, October 1986, pp.183-196.[Bier881Bier, E., Snap-Dragging: Interactive GeometricDesign in Two and Three Dimensions,University of California, Berkeley, TechnicalReport UCBKSD 881416,April 1988.[BOWBoming, A., Defining Constraints Graphically,Proceedings of CHI ‘86, Boston, April 1986,pp. 137-143.[Card881Cardelli, L., Building User Interfaces by DirectManipulation,Proceedings of the ACMSIGGRAPH Symposium on User InterfaceSoftwnre, Banff, Alberta, Canada, October1988, pp. 152-166.[Fitt54]Fitts, P., The Information Capacity of theHuman Motor System in Controlling theAmplitudeof Movement, Journal ofExperimental Psychology, v 41, June 1954,pp. 381-391.[Gold831Goldberg, A., Robson, D., Smalltalk-80: lieLanguage and its Implementation, AddisonWesley, Reading, Mass;, 1983.wuds89]Hudson, S., Graphical Specification of FlexibleUser Interface Displays, Proceedings of theACM SIGGRAPH Symposium on UserInterface Software and Technology, November1989, pp. 105-l 14.69
CHI 90 l’meedimmutc86]Hutchins, E., H&II, J., Norman, D., DirectManipulation Interfaces, in User Centeredsystems Design, D. Norman and S. Draper(ed), Lawrence Erlboum Associates, Hillsdale,New Jersey, 1.986,pp. 87-124.[Lint891Linton, M., Vlissides, J., Calder, R.,Composing 1Jser Interfaces with Interviews,IEEE Computer, 22, 2, February 1989, pp.8-22.[McCo88] McCormack, J., Asente, P., An Overview ofthe X Toolkit, Proceedings of the ACMSIGGRAPH Symposium on User InterfaceSojbvare, Banff, Alberta, Canada, October1988, pp. 46-55.70FIYer lMyers, B., Buxton, W., Creating HighlyInteractive Graphical User Interfaces byDemonstration, Computer Graphics, 20, n4,August 1986, pp. 249-258.[Meyr89]Myers, B., Vander Zanden, B., Dannenberg, R.,Creating Graphical Interactive ApplicationObjects by Demonstration, Proceedings of theACM SIGGRAPH Symposium on UserInterface Sojbvare and Technology, November1989, pp. 95-104.[Sher63]Sheridan, T., Ferrell, W., Remote Manipulative Control With Transmission Delay,IEEE Transactions on Human Factors inEZectronics, vHFE-4, nl, September 1963, pp.25-29.&nil 1990
(semantic) properties of objects to place additional constraints on snapping. Semantic snapping also provides more complex lexical feedback which reflects potential semantic consequences of a snap. This paper motivates the use of semantic snapping and describes how this technique has been implemented in a window-based toolkit. This
Ø External snapping hip: the iliotibial (IT) band moves over the greater trochanter, resulting in a "snap" that can be felt or heard with walking, dancing, or going to sit in a chair. Ø Internal (or anterior) snapping hip: the iliopsoas tendon snapping over the front of the femur Ø Labral tear of the hip (aka intra articular snapping hip
Welcome to Snapping Shoals Electric Membership Corporation. We appreciate the opportunity to serve you. Snapping Shoals EMC is a consumer-owned electric cooperative that has been serving this area since 1938. During our more than six decades as an energy provider, we have built a strong reput
Semantic Analysis Chapter 4 Role of Semantic Analysis Following parsing, the next two phases of the "typical" compiler are –semantic analysis –(intermediate) code generation The principal job of the semantic analyzer is to enforce static semantic rules –constructs a syntax tree (usua
WibKE – Wiki-based Knowledge Engineering @WikiSym2006 Our Goals: Why are we doing this? zWhat is the semantic web? yIntroducing the semantic web to the wiki community zWhere do semantic technologies help? yState of the art in semantic wikis zFrom Wiki to Semantic Wiki yTalk: „Doing Scie
tive for patients with semantic impairments, and phono-logical tasks are effective for those with phonological impairments [4,5]. One of the techniques that focus on semantic impair-ments is Semantic Feature Analysis (SFA). SFA helps patients with describing the semantic features which ac-tivate the most distinguishing features of the semantic
Sybase Adaptive Server Enterprise 11.9.x-12.5. DOCUMENT ID: 39995-01-1250-01 LAST REVISED: May 2002 . Adaptive Server Enterprise, Adaptive Server Enterprise Monitor, Adaptive Server Enterprise Replication, Adaptive Server Everywhere, Adaptive Se
Keywords: Adaptive Educational System, Semantic Integration, User Model Interoperability, Ontology 1 Introduction Over the last 10 years, a number of adaptive systems have migrated from research labs to real life. Web recommender systems [1], mobile tourist guides [2] and adaptive educational systems (AES) [3] are now employed by thousands of .
Nazism and the Rise of Hitler 49 In the spring of 1945, a little eleven-year-old German boy called Helmuth was lying in bed when he overheard his parents discussing something in serious tones. His father, a prominent physician, deliberated with his wife whether the time had come to kill the entire family, or if he should commit suicide alone. His father spoke about his fear of revenge, saying .
