The following left figure shows an idealized straight line that can cover a partial pixel. In reality, a pixel can either be turned on or off and the right figure shows how a straight appears under this constraint.
|
|
- Our choices for next pixel ( xk+1, yk+1 ) are either
( xk + 1, yk ) or
( xk + 1, yk + 1 )
Note the difference between yk+1 and yk + 1. - Let
dlower = y - yk = m ( xk + 1 ) + b - yk dupper = ( yk + 1 ) - y = yk + 1 - m ( xk + 1 ) - b
In the equations, y is the y-coordinate of the point on the idealized line at xk + 1 and yk+1 is the y-coordinate of the pixel at xk + 1. - To determine which one is closer to the line path, we calculate the difference
between dupper - dlower as follows.
dupper - dlower = 2m ( xk + 1 ) - 2 yk + 2b - 1 Let m = ( yn - y0 ) / ( xn - x0 ) = Δy / Δx
Define the decision parameter as
pk = Δx ( dlower - dupper ) = 2Δy.xk - 2Δx.yk + c ----- ( 1 ) c = 2Δy + Δx ( 2b - 1 ) is a constant ( independent of pixel position )Therefore,
pk+1 - pk = 2Δy ( xk+1 - xk ) 2Δx ( yk+1 - yk ) But,xk+1 = xk + 1 So,pk+1 = pk + 2Δy - 2Δx ( yk+1 - yk ) ---- ( 2 ) withp0 = 2Δy - Δx In ( 2 ) , yk+1 - yk is either 0 or 1, depending on the sign of pk. From ( 1 ), as Δx >0, if the pixel at yk is closer to the line path than at yk + 1 (i.e. dlower < dupper ), pk is negative and we choose the next pixel to be the lower pixel; otherwise we choose the upper pixel.
|
Brensenham's Line Drawing algorithm for |m| < 1
|
The following figure shows how one draws a line from ( 4, 111 ) to ( 19, 8 ) using such an algorithm.
|
The implementation of the algorithm is shown below. It is adopted from ...?. The member function lineTo(int xn, int yn) of class Surface draws a straight line from the current position to ( xn, yn ). In the code, CP represents the current position and is an object of class Point. We discuss in detail the class Surface in below sections.
/*
point.h -- This file defines the class Point which will be used
in the Surface class as well as many other codes in this book.
*/
#ifndef POINT_H
#define POINT_H
using namespace std;
class Point {
public:
int x;
int y;
Point () { x = y = 0; }
Point ( int x0, int y0 ) { x = x0; y = y0; }
void set ( int x0, int y0 ) { x = x0; y = y0; }
};
#endif
/*
draws a line from current point to new point using Bresenham algorithm
surf is the SDL_Surface of the class
*/
void Surface:: lineTo( int xn, int yn )
{
Uint16 *buffer;
int drawpos;
int dx, dy;
int xinc, yinc, x0, y0;
int sum;
int i;
/* If we need to lock this surface before drawing pixels, do so. */
if (SDL_MUSTLOCK( surf )) {
if (SDL_LockSurface(surf) < 0) {
printf("Error locking surface: %s\n", SDL_GetError());
abort();
}
}
/* Get the surface's data pointer. */
buffer = (Uint16 *)surf->pixels;
x0 = CP.x; y0 = CP.y;
/* Calculate the x and y spans of the line. */
dx = xn - x0 + 1;
dy = yn - y0 + 1;
/* Figure out the correct increment for the major axis.
Account for negative spans (xn < x0, for instance). */
if (dx < 0) {
xinc = -1;
dx = -dx;
} else xinc = 1;
if (dy < 0) {
yinc = -surf->pitch/2;
dy = -dy;
} else yinc = surf->pitch/2;
i = 0;
sum = 0;
/* This is our current offset into the buffer. We use this
variable so that we don't have to calculate the offset at
each step; we simply increment this by the correct amount.
Instead of adding 1 to the x coordinate, we add one to drawpos.
Instead of adding 1 to the y coordinate, we add the surface's
pitch (scanline width) to drawpos. */
drawpos = surf->pitch/2 * y0 + x0;
/* Our loop will be different depending on the
major axis. */
if (dx < dy) {
/* Loop through each pixel along the major axis. */
for (i = 0; i < dy; i++) {
/* Draw the pixel. */
buffer[drawpos] = color;
/* Update the incremental division. */
sum += dx;
/* If we've reached the dividend, advance
and reset. */
if (sum >= dy) {
drawpos += xinc;
sum -= dy;
}
/* Increment the drawing position. */
drawpos += yinc;
}
} else {
/* See comments above. This code is equivalent. */
for (i = 0; i < dx; i++) {
buffer[drawpos] = color;
sum += dy;
if (sum >= dx) {
drawpos += yinc;
sum -= dx;
}
drawpos += xinc;
}
}
CP.set ( xn, yn ); //set new CP position
/* Unlock the surface. */
SDL_UnlockSurface(surf);
}
|
Turtle graphics is a style of computer drawing based on preserved state (position and orientation) and a small number of operations against that state (forward, turn, pen up & down). It is easy to learn and easy for kids to pick up; it was created mainly for educational use. Formally, it was derived from Logo, which is a functional programming language. It is an easier to read adaptation and dialect of the Lisp programming language; some have called it Lisp without the parentheses. ( Some people refer to Lisp as "A Lot of Iritating Silly Parentheses". ).
Drawing turtle graphics was like moving a plotting pen around to produce graphics on a plotter; the plotter looked like a turtle with a pen strapped to it. The drawing state is referred to as the turtle. Programs teach the turtle how to perform simple moves like moving forward 10 spaces and turn around. From these building blocks you can construct more complex shapes like polygons, stars, circles; you can then use these to build complex objects like houses, cars, or landscapes. Combining with fractal geometry, turtle graphics can produce fascinated drawings.
Very often, the turtle moves with commands that are relative to its own position, "turn 90" could mean rotate anticlockwise by 90 degrees. A student could understand ( and predict and reason about ) the turtle's motion by imagining what they would do if they were the turtle. Papert called this "body syntonic" reasoning. The following example demonstrates how you could draw a box using the simple commands "forward" and "turn". "forward 10" means moving forward by 10 units along the current direction and drawing a line while moving. "turn 90" is to turn 90 degrees in an anit-clockwise direction. You can then use the "draw-a-box" as a routine to draw a window as shown below.
to draw-a-box forward 10 turn 90 forward 10 turn 90 forward 10 turn 90 forward 10 turn 90 to draw-a-window draw-a-box turn 90 draw-a-box turn 90 draw-a-box turn 90 draw-a-box turn 90 |
 |
 |
 |
We shall present some simple examples of turtle graphics in the following sections.
We developed a class called Surface to plot a straight line using the Brensenham's Line Drawing algorithm and use this line primitive to generate turtle graphics. The member functions and data fields are defined below.
//surface.h
//header file for surface.cpp
#ifndef SURFACE_H
#define SURFACE_H
#include <math.h>
#include <SDL/SDL.h>
#include "point.h"
class Surface
{
public:
Surface(int width, int height, char* windowTitle); //constructor
void clearScreen();
void setBackgroundColor(int r, int g, int b);
void setColor(int r, int g, int b);
void lineTo( int x, int y);
void lineTo(Point p);
void moveTo( int x, int y);
void moveTo(Point p);
void moveRel( int dx, int dy);
Point getCP();
//for turtle graphics
void turnTo( float angle );
void turn( float angle );
void forward ( int dist, int isVisible );
SDL_Surface *getSurface();
void updateSurface();
private:
Point CP; //current position in the world
float CD; //current direction, for turtle graphics
SDL_Surface *surf;
Uint16 color;
} ;
#endif
|
The names of the member functions and data fields are almost self-explained. The constructor Surface() constructs an SDL surface with provided windows width, height and title; it sets the video mode to 16-bit hicolor and the color of the surface is set to white. The created SDL surface is pointed at by the private data field, surf and subsequent operations are acted on this surface. The current position, CP is set to ( 0, 0 ).
Surface:: Surface(int width, int height, char* windowTitle)
{
// Fire up SDL.
if (SDL_Init(SDL_INIT_VIDEO | SDL_INIT_AUDIO ) < 0) {
printf("Error initializing SDL: %s\n", SDL_GetError());
exit ( 1 );
}
atexit(SDL_Quit);
// Set a video mode. Force 16-bit hicolor.
if (( surf = SDL_SetVideoMode(width, height, 16, 0x0)) == NULL) {
printf("Error setting a video, 16-bit video mode: %s\n",
SDL_GetError());
exit( 0 ); //should use exception
}
CP.set( 0, 0 ); //initialize the cp to (0,0)
color = 0xFFFFFF; //default is white
} //constructor
|
The member function lineTo() is to draw a line, using the Bresenham's algorithm discussed above, from the current position given by CP to the destination point specified as input parameters to the function; the code has been presented in section 1. moveTo() simply moves CP to the destination without drawing any line. moveRel() moves CP by a distance relative to to its current coordinate values.
void Surface:: moveTo( int x, int y ) //moves current point to ( x, y )
{
CP.set ( x, y );
}
void Surface:: moveRel( int dx, int dy)
{
CP.set(CP.x + dx, CP.y + dy);
}
|
turnTo() sets the current direction CD to the specified angle; turn() is to turn from the current direction the angle specified as the input parameter.
//since the 'origin' is at left upper corner, our direction sense is reversed
// so clockwise and anti-clockwise are reversed
void Surface::turnTo( float angle )
{
CD = -angle; //set current direction
}
//since the 'origin' is at left upper corner, our direction sense is reversed
// so clockwise and anti-clockwise are reversed
void Surface::turn( float angle )
{
CD -= angle; //turn anti-clockwise for positive angle
}
|
Finally, the function forward() moves the turtle forward for a specified distance. While moving forward, it can either draw a line or not drawing anything, depending on if the input parameter isVisisble is set to 1 or 0. The figure on the right side of the code shows how the destination coordinates x and y are calculated; in going forward in the direction CD, the turtle just moves in the x direction a distance dist x cos ( π x CD / 180 ) and in y direction a distance dist x sin ( π x CD / 180 ).
//move line forward by amount dist, if isVisible nonzero, line is drawn
void Surface::forward ( int dist, int isVisible )
{
const float RadPerDeg = 0.017453393; //radians per degree
int x = CP.x + ( int ) ( dist * cos ( RadPerDeg * CD ));
int y = CP.y + ( int ) ( dist * sin ( RadPerDeg * CD ));
if ( isVisible )
lineTo( x, y );
else
moveTo ( x, y );
}//forward
|
|
With the Surface class defined, we can now write turtle graphics applications using the member functions, turn, turnTo, and forward(). The following is the code for drawing a hook using the Surface class. The parameter L specifies the length of the longer side of the hook.
//draw a hook
void draw_hook ( Surface &surf, int L )
{
surf.forward ( L, 1 );
surf.turn( 90 );
surf.forward ( L/5, 1 );
surf.turn ( 90 );
surf.forward ( L/3, 1 );
}
|
|
As shown below, you can easily draw a star pattern using turtle graphics. The only part that requires some work is to figure out the angle that the turtle has to turn in each move.
//draw a star pattern
void draw_star( Surface &surf, int L )
{
for ( int i = 0; i < 5; ++i ) {
surf.forward( L, 1 );
surf.turn( 144 );
}
}
|
|
The Surface class also make drawing a regular n-sided polygon simple. The main part here is to find out the coordinates of the vertices. A vertex coordinates relative to the center of the polygon is given by
| ( R* cos ( angle ), R* sin ( angle ) ) |  |
//draw an n-sided regular polygon
void draw_polygon ( Surface &surf, int n, int radius, float rotAngle )
{
if ( n < 3 ) return; //bad number of sides
int cx = surf.getCP().x;
int cy = surf.getCP().y;
double angle = rotAngle * 3.14159265 / 180; //initial angle
double angleInc = 2 * 3.14159265 / n; //angle increment
surf.moveTo ( ( int) (radius * cos( angle ) + cx),
( int ) ( radius * sin ( angle ) + cy ) );
for ( int k = 0; k < n; k++ ) { //repeat n times
angle += angleInc;
surf.lineTo ( ( int) (radius * cos( angle ) + cx),
( int ) ( radius * sin ( angle ) + cy ) );
}
} //draw_polygon
|
|
Note that we can obtain a circle by drawing a polygon with a large value of n. In practice, a value of 80 generates a smooth circle. In the above piece of code, we draw a ploygon using directly the Surface member function lineTo() and calculating the vertex angles. We can also also draw a polygon using turtle graphics as shown below.
//draw an n-sided regular polygon with length L using turtle graphics
void draw_polygont ( Surface &surf, int n, int L )
{
if ( n < 3 ) return; //bad number of sides
int angle = 360 / n;
for ( int i = 0; i < n; ++i ) {
surf.forward ( L, 1 );
surf.turn ( angle );
}
}
|
|
A complete list of the programs discussed above can be obtained by clicking here, which opens a new window.