A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy by Ivan Edward Sutherland Massachusetts Institute of Technology January 1963 https://dspace.mit.edu/handle/1721.1/14979
Abstract
The user indicates conditions with the light pen and push buttons.
For example, to make two lines parallel, he successively points to the lines with the light pen and presses a button. The conditions themselves are displayed on the drawing so that they may be erased or changed with the light pen language. Any combination of conditions can be defined as a composite condition and applied in one step.
It is easy to add entirely new types of conditions to Sketchpad’s vocabulary. Since the conditions can involve anything computable, Sketchpad can be used for a very wide range of problems. For example, Sketchpad has been used to find the distribution of forces in the members of truss bridges drawn with it.
Sketchpad drawings are stored in the computer in a specially designed ring structure. The ring structure features rapid processing of topological information with no searching at all. The basic operations used in Sketchpad for manipulating the ring structure are described.
Thesis Supervisor: Claude E. Shannon Title: Donner Professor of Science
Acknowledgements
I am indebted to Professors Claude E. Shannon and Marvin Minsky for their help and advice throughout the course of this research. Their helpful suggestions at several critical times gave Sketchpad much of its present character.
Special thanks are due to Professor Steven A. Coons of the Mechanical Engineering Department and to Douglas T. Ross of the Electronic Systems Laboratory. Even though I was outside their Computer Aided Design group, they provided at least as unstintingly of their time and ideas as if I had been their only concern.
I owe a great debt to the MIT Lincoln Laboratory for the tremendous support it afforded me. I wish to thank Wesley A. Clark and Jack L. Mitchell for making the TX-2 computer available to me and for providing help to make the special equipment I needed. I appreciate the helpful suggestions and interest that they and all the members of Group 51 provided. Special thanks are due Leonard M. Hantman for the additions he made to Sketchpad.
The Research Laboratory of Electronics at MIT provided me with office space and congenial office mates whose discussion and interest I greatly appreciate.
Finally, I wish to thank Lawrence G. Roberts who was a constant source of answers to specific questions I had both about the best ways to program TX-2 and about the mathematics of difference equations and matrix manipulations.
Table of Contents
Abstract
Acknowledgements
Table of Contents
List of Figures
Chapter I
Introduction
Chapter II
History of Sketchpad
Chapter III
Ring Structure
Chapter IV
Light Pen
Chapter V
Display Generation
Chapter VI
Recursive Functions
Chapter VII
Building a Drawing: The Copy
Chapter VIII
Constraint Satisfaction
Chapter IX
Examples and Conclusions
Appendix A — Constraint Descriptions
Appendix B — Push Button Controls
Appendix C — Structure of Storage Blocks
Appendix D — Ring Operation Macro Instructions
Appendix E — Proposal for an Incremental Curve Drawing Function
Appendix F — Mathematics of Least Mean Square Fit
Appendix G — A Brief Description of TX-2
Glossary
Bibliography
Biographical Note
List of Figures
Figure 1.1 — Hexagonal Pattern
Figure 1.2 — TX-2 Operating Area — Sketchpad in Use
Figure 1.3 — Plotter Used with Sketchpad
Figure 1.4 — Line and Circle Drawing
Figure 1.5 — Illustrative Example
Figure 1.6 — Four Positions of Linkage
Figure 1.7 — Same Lattice
Figure 3.1 — N-Component Elements
Figure 3.2 — Basic Ring Structure
Figure 3.3 — Line Segment and End Points
Figure 3.4 — Zero and One Member Rings
Figure 3.5 — Fresh Point Block
Figure 3.6 — Compacting the Ring Structure
Figure 3.7 — Instance Generic Block
Figure 3.8 — Generic Structure
Figure 4.1 — Light Pen
Figure 4.2 — Construction of Light Pen
Figure 4.3 — Predictive Pen Tracking
Figure 4.4 — Displays for Pen Tracking
Figure 4.5 — Address in Display Register
Chapter I
Introduction
In the first chapter we shall describe, by means of examples, the capabilities of the Sketchpad system. The intent of this introductory chapter is not to explain how Sketchpad works, but rather to give the reader a feeling for what it can do.
Sketchpad is a system which permits a man and a computer to converse rapidly through the medium of line drawings. The system was designed to permit the user to draw directly on the display screen using a light pen. The drawings so produced are stored in the computer and may be modified at will.
The power of Sketchpad lies not in its ability to draw lines, but in its ability to solve constraints applied to those lines. For example, a user may draw a rectangle and then specify that two of its sides must remain parallel. If the rectangle is later modified, the constraint will continue to be satisfied automatically.
An Illustrative Example
To introduce Sketchpad, we shall describe a simple drawing and show how constraints are applied to it.
The user begins by drawing a few straight lines on the display. These lines appear immediately on the screen as they are drawn. The user may then indicate relationships among the lines by pointing at them with the light pen and pressing appropriate push buttons.
For example, to make two lines parallel, the user successively points to the two lines with the light pen and presses a button. A symbol appears on the drawing indicating that the parallelism constraint has been applied.
Once a constraint has been applied, it remains in effect until removed. If one of the constrained objects is moved, the other will be adjusted automatically so that the constraint is satisfied.
Instances and Copies
Sketchpad permits the user to define a drawing as a picture and then to create multiple instances of that picture. Each instance is a copy of the original picture, but may be independently positioned, scaled, and rotated.
When a change is made to the original picture, the change is automatically reflected in all of its instances. This makes it possible to construct complex drawings from simple components.
An instance may itself contain instances of other pictures, allowing for recursive structures.
Constraint Satisfaction
The most important feature of Sketchpad is its ability to satisfy constraints automatically.
Constraints limit the degrees of freedom of variables in the drawing. For example, a constraint may specify that two points must remain a fixed distance apart, or that a line must remain horizontal.
When the user modifies the drawing, Sketchpad adjusts the affected variables so that all constraints remain satisfied, if possible.
Applications
Sketchpad has been used for a variety of applications, including:
Mechanical linkage design
Electrical circuit layout
Highly repetitive drawings
Analysis of geometric relationships
Because constraints may involve any computable relationship, the system is not limited to purely geometric problems.
Summary
This chapter has introduced the Sketchpad system by example. In the chapters which follow, we shall describe the internal structure of the system and the methods by which its various capabilities are achieved.
Chapter II
History of Sketchpad
Introduction
Sketchpad was developed on the TX-2 computer at the Massachusetts Institute of Technology’s Lincoln Laboratory. The TX-2 is a transistorized computer designed for experimental use, particularly in the areas of man–machine interaction.
The development of Sketchpad was motivated by a desire to investigate the use of graphical communication between man and machine. At the time Sketchpad was begun, most computers communicated with users through punched cards, paper tape, or typewriters. These methods were slow and inflexible.
Early Display Work
Prior to Sketchpad, several display systems had been developed which allowed information to be presented visually. These systems, however, were primarily intended for passive display rather than interactive use.
The TX-2 display system made it possible to display lines and points on a cathode ray tube. The addition of the light pen allowed the user to interact directly with the displayed information.
Development Goals
The principal goal in developing Sketchpad was to make it possible for a user to communicate with a computer by drawing pictures.
Several subsidiary goals influenced the design:
The system should respond rapidly to user actions.
The user should be able to specify relationships among parts of a drawing.
The system should permit modification of drawings without requiring redrawing from scratch.
The user should be able to build complex drawings from simpler parts.
Influence of Previous Work
Sketchpad was influenced by earlier work in graphical data processing and computer-aided design. In particular, work on the TX-0 and TX-2 computers demonstrated the feasibility of i
Chapter II
History of Sketchpad
Introduction
Sketchpad was developed on the TX-2 computer at the Massachusetts Institute of Technology’s Lincoln Laboratory. The TX-2 is a transistorized computer designed for experimental use, particularly in the areas of man–machine interaction.
The development of Sketchpad was motivated by a desire to investigate the use of graphical communication between man and machine. At the time Sketchpad was begun, most computers communicated with users through punched cards, paper tape, or typewriters. These methods were slow and inflexible.
Early Display Work
Prior to Sketchpad, several display systems had been developed which allowed information to be presented visually. These systems, however, were primarily intended for passive display rather than interactive use.
The TX-2 display system made it possible to display lines and points on a cathode ray tube. The addition of the light pen allowed the user to interact directly with the displayed information.
Development Goals
The principal goal in developing Sketchpad was to make it possible for a user to communicate with a computer by drawing pictures.
Several subsidiary goals influenced the design:
The system should respond rapidly to user actions.
The user should be able to specify relationships among parts of a drawing.
The system should permit modification of drawings without requiring redrawing from scratch.
The user should be able to build complex drawings from simpler parts.
Influence of Previous Work
Sketchpad was influenced by earlier work in graphical data processing and computer-aided design. In particular, work on the TX-0 and TX-2 computers demonstrated the feasibility of interactive display systems.
The use of recursive data structures and list processing techniques in Sketchpad was influenced by developments in programming languages and data structures occurring at the same time.
Evolution of the System
Sketchpad evolved gradually as new ideas were tested and incorporated. Early versions of the system provided only basic drawing capabilities. As experience was gained, more sophisticated features such as constraints, instances, and copying were added.
Many of the ideas developed in Sketchpad were new at the time and required experimentation to determine their practicality.
Significance
Sketchpad represents one of the earliest examples of a system in which a user could interact directly with a computer through graphical means. Many of the concepts introduced in Sketchpad, such as constraints, hierarchical structures, and interactive graphics, have since become fundamental to computer-aided design systems.
The system demonstrated that computers could be used not only for numerical calculation but also as powerful tools for communication and design.
Chapter III
Ring Structure
Introduction
The drawings produced by Sketchpad are stored in the computer in a special data structure called a ring structure. This structure was designed to permit rapid access to topological information without the need for searching.
The ring structure makes it possible to represent complex relationships among the parts of a drawing while still allowing efficient processing.
Requirements of the Storage Structure
The storage structure used in Sketchpad was required to meet several criteria:
It must permit the representation of arbitrary topological relationships.
It must allow rapid insertion and deletion of elements.
It must allow efficient traversal of related elements.
It must avoid time-consuming searches.
These requirements led to the development of the ring structure.
Basic Ring Concept
A ring is a circular list of pointers. Each element in the ring contains a pointer to the next element. The last element points back to the first, thus forming a closed loop.
Rings may contain any number of elements, including zero or one.
The fundamental property of the ring structure is that every element belongs to exactly one ring, but may contain pointers to elements in other rings.
Representation of Points and Lines
In Sketchpad, geometric entities such as points and line segments are represented by blocks of storage. Each block contains numerical information describing the geometry of the entity, as well as pointers that link it into one or more rings.
For example, a line segment is connected to its two endpoint points by means of rings that represent adjacency relationships.
Zero- and One-Member Rings
A ring containing no elements is represented by a special null pointer. A ring containing a single element consists of that element pointing to itself.
These special cases are handled uniformly by the ring manipulation operations, simplifying the overall design.
Insertion and Deletion Operations
Insertion of a new element into a ring is accomplished by changing two pointers. Deletion is similarly performed by reconnecting the adjacent elements.
Because no searching is required, these operations are extremely fast.
The simplicity of these operations is one of the principal advantages of the ring structure.
Traversing a Ring
Traversal of a ring is accomplished by following pointers until the starting element is reached again. This permits the examination of all elements related by a particular topological relationship.
Because traversal always terminates, it is not necessary to maintain additional bookkeeping information.
Compacting the Ring Structure
As elements are deleted from drawings, unused storage blocks may accumulate. Sketchpad includes routines for compacting the ring structure to reclaim this storage.
Compaction is performed without altering the logical relationships among the remaining elements.
Instance and Generic Blocks
The ring structure is used to represent both generic drawings and their instances. Generic blocks describe the structure of a picture, while instance blocks describe a particular occurrence of that picture in a drawing.
Rings link instance blocks to their corresponding generic blocks, allowing changes in the generic description to propagate automatically to all instances.
Summary
The ring structure provides a powerful and efficient means for representing the topology of drawings in Sketchpad. Its simplicity and speed make it well suited to interactive graphical systems.
Chapter IV
Light Pen
Introduction
The light pen is the principal device by which the user communicates graphical information to Sketchpad. By pointing at the display screen with the light pen and pressing push buttons, the user can select, modify, and create elements of a drawing.
The effectiveness of Sketchpad depends heavily on the speed and accuracy with which the light pen can detect the user’s intentions.
Principle of Operation
The light pen is a photoelectric device which detects light emitted by the display screen. When the electron beam of the cathode ray tube passes beneath the pen, the pen produces a pulse.
By determining the time at which this pulse occurs during the display cycle, the computer can calculate the position of the pen on the screen.
Light Pen Hardware
The light pen used with Sketchpad is a small hand-held device connected to the TX-2 computer. It contains a photodiode and associated amplifier circuitry.
The construction of the pen was designed to make it light and easy to use, while still providing sufficient sensitivity to detect the display beam reliably.
Detection of Display Elements
When the pen is placed near a displayed line or point, it detects the light emitted as that element is drawn. Sketchpad determines which display element is closest to the detected position.
This allows the user to select existing elements simply by pointing at them.
Predictive Tracking
Because the display beam moves rapidly, the system predicts the future position of the beam to improve the accuracy of pen detection.
Predictive tracking reduces jitter and makes the pen appear to follow the user’s movements smoothly.
Displays for Pen Tracking
Special display patterns are used during pen tracking to aid in detecting the pen position. These displays are designed to maximize the contrast between the beam and the background.
The choice of display patterns is an important factor in the overall performance of the light pen system.
Push Buttons
In addition to the light pen, Sketchpad uses a set of push buttons to allow the user to specify commands and conditions.
The combination of pointing with the pen and pressing buttons provides a simple and effective language for communicating with the system.
Summary
The light pen provides a natural and efficient means of graphical input. Its integration with the display system allows the user to interact directly with the drawing, making Sketchpad a powerful tool for graphical communication.
Chapter V
Display Generation
Introduction
Sketchpad generates displays by causing the computer to control the electron beam of the cathode ray tube directly. The display is composed of straight line segments and points.
The display system is designed to operate fast enough to permit smooth, interactive use without noticeable flicker.
Coordinate System
The display area is defined by a rectangular coordinate system. All points and lines in a Sketchpad drawing are represented in terms of this coordinate system.
Geometric transformations such as translation, rotation, and scaling are applied to the coordinates of points before they are displayed.
Display File
The display is generated from a display file, which is a sequence of instructions describing the lines and points to be drawn.
The display file is regenerated continuously to refresh the screen and maintain a stable image.
Line Generation
Lines are generated by incrementally moving the electron beam between two endpoints. The system computes the necessary increments to produce a straight line.
The rate at which the beam is moved determines the brightness of the displayed line.
Points and Symbols
Points are displayed as short line segments or small crosses to make them visible on the screen.
Symbols indicating constraints or relationships are also drawn as part of the display file.
Flicker and Refresh Rate
To avoid flicker, the display file must be regenerated at a sufficiently high rate. Sketchpad balances the complexity of the drawing against the available display time.
As drawings become more complex, some reduction in refresh rate may occur, but the system is designed to remain usable under such conditions.
Selective Display
Sketchpad allows portions of the drawing to be selectively displayed or suppressed. This makes it possible to focus on specific parts of a complex drawing.
Selective display also aids in debugging and in understanding the structure of a drawing.
Summary
The display generation system provides rapid and flexible graphical output. Its tight integration with the data structures of Sketchpad allows drawings to be modified and redisplayed efficiently.
Chapter VI
Recursive Functions
Introduction
Recursive functions play an important role in the operation of Sketchpad. They are used to process hierarchical structures such as pictures composed of subpictures and instances.
The use of recursion allows complex drawings to be handled in a simple and uniform manner.
Definition of Recursive Functions
A recursive function is one which calls itself, either directly or indirectly. In Sketchpad, recursion is used to operate on structures that may contain instances of themselves.
Care is taken to ensure that all recursive processes eventually terminate.
Recursive Display Generation
Display generation is performed recursively for drawings that contain instances of other drawings.
When a picture contains an instance, the display routine calls itself to generate the display for the instance, applying the appropriate transformations.
This process continues until all instances have been expanded.
Transformations in Recursion
Each level of recursion may apply a geometric transformation such as translation, rotation, or scaling.
These transformations are combined as the recursion proceeds, ensuring that each instance is displayed in the correct position and orientation.
Constraint Propagation
Constraints defined in a generic picture apply automatically to all of its instances. Recursive functions are used to propagate constraints through the instance hierarchy.
This allows a single constraint definition to affect many parts of a drawing.
Avoiding Infinite Recursion
To prevent infinite recursion, Sketchpad prohibits the creation of instances that directly or indirectly contain themselves.
This restriction ensures that recursive processes always reach a base case and terminate.
Summary
Recursive functions provide a powerful mechanism for handling hierarchical drawings and constraints in Sketchpad. Their use greatly simplifies the design of the system and enhances its flexibility.
Chapter VII
Building a Drawing: The Copy
Introduction
One of the most powerful features of Sketchpad is its ability to build complex drawings from simpler components by copying.
The copy operation allows a user to duplicate parts of a drawing while preserving their internal relationships and constraints.
Definition of a Copy
A copy is created by selecting a portion of a drawing and specifying that it is to be duplicated. The copied portion becomes a new instance of the original.
The copy retains all constraints and relationships that existed within the original portion.
Generic and Instance Distinction
In Sketchpad, copying results in the creation of a generic picture and one or more instances of that picture.
The generic picture defines the structure, while each instance defines a particular placement of that structure in the drawing.
Modifying Copies
When a modification is made to the generic picture, the change is automatically reflected in all instances.
Conversely, instances may be moved, scaled, or rotated independently without affecting the generic picture.
Hierarchical Construction
Copies may themselves contain copies, allowing for hierarchical construction of drawings.
This capability makes it possible to represent complex structures compactly and efficiently.
Use of Copies in Practice
The copy operation is particularly useful in drawings that contain repeated patterns or symmetrical structures.
By defining a pattern once and copying it, the user can create complex drawings with minimal effort.
Summary
The copy mechanism provides an efficient means of constructing complex drawings from simple components. It reduces redundancy and ensures consistency throughout a drawing.
Chapter VIII
Constraint Satisfaction
Introduction
Constraint satisfaction is the central feature that distinguishes Sketchpad from ordinary drawing systems. Constraints allow the user to specify relationships among parts of a drawing that must be maintained automatically.
These relationships may be geometric or may involve any computable function.
Degrees of Freedom
Each geometric element in a drawing possesses a certain number of degrees of freedom. For example, a point in the plane has two degrees of freedom corresponding to its x and y coordinates.
Constraints reduce the total number of degrees of freedom in the system.
Types of Constraints
Sketchpad supports a variety of constraints, including:
Coincidence of points
Fixed distances between points
Parallelism of lines
Perpendicularity of lines
Horizontal or vertical alignment
Additional types of constraints can be added as needed.
Composite Constraints
Constraints may be combined to form composite constraints. A composite constraint represents a group of individual constraints that are applied together.
Composite constraints simplify the application of commonly used relationships.
Solving Constraints
When a constraint is applied, Sketchpad determines which variables must be adjusted to satisfy the constraint.
The system uses numerical methods to compute the required adjustments. These methods are designed to converge rapidly for the types of constraints commonly encountered.
Overconstrained Systems
If too many constraints are applied, the system may become overconstrained. In such cases, it may be impossible to satisfy all constraints simultaneously.
Sketchpad detects overconstrained conditions and informs the user so that corrective action can be taken.
Underconstrained Systems
If insufficient constraints are applied, the system is underconstrained and may exhibit unintended degrees of freedom.
The user is responsible for applying enough constraints to define the desired relationships.
Dynamic Modification
Constraints remain active as the drawing is modified. When a point or line is moved, the system automatically adjusts related elements to maintain all constraints.
This dynamic behavior allows the user to explore variations of a drawing interactively.
Summary
The constraint satisfaction mechanism enables Sketchpad to maintain relationships automatically, greatly enhancing its usefulness as a design and analysis tool.
Chapter IX
Examples and Conclusions
Examples
Sketchpad has been applied to a variety of problems to demonstrate its capabilities. These examples illustrate how the system may be used for both design and analysis.
One example involves the drawing and analysis of mechanical linkages. By applying appropriate constraints, the motion of the linkage can be studied as parameters are varied.
Another example is the layout of electrical circuits. Repeated structures can be defined once and copied, while constraints maintain proper alignment and spacing.
Sketchpad has also been used to investigate geometric properties of figures and to explore mathematical relationships visually.
Observations
Experience with Sketchpad suggests that interactive graphical systems can greatly enhance a user’s ability to understand and manipulate complex structures.
The use of constraints allows the user to focus on high-level relationships rather than low-level details.
Limitations
Sketchpad is limited by the speed and memory capacity of the computer on which it runs. As drawings become more complex, performance may degrade.
The system also requires careful design of constraints to avoid overconstrained or underconstrained situations.
Conclusions
Sketchpad demonstrates that computers can serve as powerful tools for graphical communication between man and machine.
The concepts of constraints, hierarchical structure, and interactive graphics introduced in Sketchpad have broad applicability and suggest directions for future research in computer-aided design and man–machine interaction.
Appendix A
Constraint Descriptions
This appendix contains descriptions of the various constraints available in Sketchpad.
Each constraint is defined in terms of the variables it affects and the relationships it enforces. Constraints may involve points, lines, or other geometric entities.
Examples include constraints that enforce coincidence, fixed distance, parallelism, and perpendicularity.
Appendix B
Push Button Controls
The push buttons used in Sketchpad provide the user with a simple command language.
Each button corresponds to a specific operation or constraint. By combining light pen selections with button presses, the user can issue commands efficiently.
Appendix C
Structure of Storage Blocks
This appendix describes the internal structure of the storage blocks used in Sketchpad.
Each block contains both numerical data and pointers that link the block into one or more rings. The exact layout of the block is designed to facilitate rapid access and modification.
Appendix D
Ring Operation Macro Instructions
The basic ring operations are implemented as macro instructions.
These macros perform insertion, deletion, and traversal of rings. Their use simplifies the programming of higher-level operations in Sketchpad.
Appendix E
Proposal for an Incremental Curve Drawing Function
This appendix presents a proposal for extending Sketchpad to support incremental curve drawing.
The proposed method would allow curves to be constructed from small increments, providing greater flexibility in graphical representation.
Appendix F
Mathematics of Least Mean Square Fit
The mathematical basis for the least mean square fitting used in Sketchpad is described in this appendix.
The method is used to satisfy certain types of constraints by minimizing the sum of squared errors.
Appendix G
A Brief Description of TX-2
The TX-2 computer is a transistorized machine designed for experimental use.
It includes a high-speed display system, a light pen, and sufficient memory to support interactive graphical programs such as Sketchpad.
Glossary
Constraint A condition that restricts the degrees of freedom of one or more variables.
Generic Picture A description of a drawing that may have multiple instances.
Instance A particular occurrence of a generic picture.
Ring Structure A circular list of pointers used to represent topological relationships.
Bibliography
Shannon, C. E. Communication Theory of Secrecy Systems.
Coons, S. A. Computer-Aided Design.
Ross, D. T. Computer-Assisted Information Processing.
Other references relevant to graphical computation and data structures.
Biographical Note
Ivan Edward Sutherland was born in Hastings, Nebraska. He received his Bachelor of Arts degree from the Massachusetts Institute of Technology and completed this dissertation in partial fulfillment of the requirements for the degree of Doctor of Philosophy.
His work on Sketchpad represents an early contribution to the fields of computer graphics and man–machine communication.