Lecture 1 Turtle Graphics the turtle and the crane and the swallow observe the time of their coming 1 Jeremiah 8 7 Turtle Graphics Motion generates geometry The turtle is a handy paradigm for investigating curves generated by motion Imagine a turtle that after each step leaves a trail connecting her previous location to her new location As this turtle crawls around on a flat surface the turtle may traverse paths that form intriguing geometric patterns see Figure 1 Figure 1 Some interesting geometric patterns generated by turtle paths Some of you may have encountered this mythical turtle before in the programming language LOGO LOGO has been used in primary schools to introduce young children to programming but the turtle is more than just a toy for young children In their book Turtle Geometry Abelson and DiSessa use turtles to investigate many advanced topics ranging from elementary differential geometry and topology to Einstein s General Theory of Relativity The study of geometry using programming is the branch of Computer Science called Computational Geometry We shall begin our investigation of Computer Graphics with Turtle Graphics After developing a simple variant of LOGO we will see that Turtle Graphics can be used to generate many diverse shapes ranging from simple polygons to complex fractals 2 Turtle Commands To help understand the ideas behind Turtle Graphics we introduce a virtual turtle The virtual turtle is a simple creature she knows only where she is in which direction she is facing and her step size The virtual turtle obeys solely simple commands to change either her location or her heading or her notion of scale Consider such a virtual turtle living on a virtual plane The turtle s location can be represented by a point P a dot given by a pair of coordinates x y similarly the turtle s heading can be represented by a vector w an arrow given by another pair of coordinates u v see Figure 2 The step size of the turtle is simply the length of the vector w Thus the step size of the turtle is w u2 v 2 w P Figure 2 The virtual turtle is represented by a point P dot and a vector w arrow Location is a point direction is a vector Points are represented by dots vectors are have position but no direction or length vectors have direction and represented by arrows Points length but no fixed position In many branches of science and engineering the distinction between points and vectors is often overlooked but this distinction is very important in Computer Graphics We shall see shortly that computationally points and vectors are treated quite differently in LOGO The pair P w is called the turtle s state Although internally the computer stores the coordinates x y and u v the turtle and the turtle programmer has no access to these global coordinates the turtle knows only the local information P w not the global information x y and u v That is the turtle knows only that she is here at P facing there in the direction w she does how P and w are related to some global origin or coordinate axes to other heres and not know theres This state model for the turtle is similar to the model of a billiard ball in classical mechanics where physicists keep track of a ball s position and momentum Turtle location is analogous to the position of the billiard ball and turtle direction is analogous to the momentum of the billiard ball The main difference between these two models is that for billiard balls the laws of physics differential equations govern the position and momentum of the ball in contrast we shall write our own programs to change the location and direction of the turtle The turtle responds to four basic commands FORWARD MOVE TURN and RESIZE These commands affect the turtle in the following ways FORWARD D The turtle moves forward D steps along a straight line from her current position in the direction of her current heading and draws a straight line from her initial position to her final position MOVE D Same as FORWARD D without drawing a line TURN A The turtle changes her heading by rotating her direction vector in the plane counterclockwise from her current heading by the angle A RESIZE S The turtle changes the length of her step size direction vector by the factor S 2 These four turtle commands are implemented internally in the following fashion FORWARD D and MOVE D Translation see Figure 3 x new x D u y new y D v TURN A Rotation see Figure 4 unew u cos A v sin A unew v new u sin A v cos A RESIZE S Scaling see Figure 5 S unew S u unew v new u v v new S v 0 cos A sin A v new u v sin A cos A 0 S We shall also adopt the following conventions D 0 FORWARD D moves the turtle backwards A 0 TURN A rotates the turtle counterclockwise A 0 TURN A rotates the turtle clockwise S 0 RESIZE S rotates the turtle by 180o and then scales the direction vector by S Notice that the TURN and RESIZE commands can be implemented using matrix multiplication but that the FORWARD and MOVE commands cannot This distinction arises because rotation and scaling are linear transformations on vectors but translation is an affine not a linear transformation on points A point is not a vector so transformations on points are inherently different from transformations on vectors We shall discuss linear and affine transformations their precise meanings as well as their similarities and differences in detail in Lecture 4 The formulas for executing the four turtle commands can be derived easily from simple geometric arguments We illustrate the effect of each of these turtle commands in Figures 3 5 Pnew P Dw w w Dw P Figure 3 The command FORWARD D changes the turtle s location but leaves her direction and step size unchanged The new turtle location is Pnew P D w Thus in terms of coordinates x new x D u y new y D v 3 w wnew w sin P w cos w Figure 4 The command TURN changes the turtle s heading but leaves her position and step work in the turtle s local coordinate system size unchanged To derive the turtle s new heading we Let P w be the turtle s current state and let w denote the vector perpendicular to w of the same length as w Then wnew w cos w sin But if w u v then w v u see Exercise 11 Therefore in terms of coordinates unew u cos v sin v new v cos u sin or in matrix notation cos sin unew v new u v sin cos Sw w Figure 5 The command RESIZE S changes the turtle s step size by a factor of S but leaves her position and heading unchanged The turtle s new direction vector is given by wnew S w Thus in terms of coordinates unew S …