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.

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

Early Display Work

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.