Wednesday, January 16, 2013

Pi-A-Sketch code review

Python code repository

Are you guys ready to look at the entrails of the Python? We are going to review the code for the Pi-A-Sketch. Liz already published the URL for the Pi-A-Sketch code on the raspberrypi.org site, but just in case, here it is again:

piasketch.py (bitbucket)

To clone it to your local machine:

hg clone https://fdion@bitbucket.org/fdion/pi-a-sketch

Of course you have to have mercurial installed. But for the sake of our discussion, you don't need to do that right now. We are going to display the code right here, and then talk about it.

Initial thought process


Initially, I wanted a function to draw a line, and a function to draw a circle. That meant that I would have to write the guts of:

def line(x, y):
    pass

def circle(radius):
    pass

Right away I knew that I would need to do something based on Bresenham's line drawing algorithm. Horizontal lines are trivial (turn one motor), and so are vertical lines (turn the other motor). Perfect diagonals are also easy to accomplish, since it is just a matter of turning both motors at the same time, for each step. Based on the direction of the steps, 4 different diagonal directions can be done.

Yet, with Bresenham's algorithm, you can do a line of any slope. In order to save time, I was not going to do special case handling, and just do everything with his algorithm.



Bresenham's algorithm was also adapted to drawing circles. It is usually found under the name "midpoint circle algorithm".

I also knew that I would be reusing the stepper() function I had designed earlier (see PyHack step by step article), and that meant importing the RPi.GPIO module and setting up the pins. I also wanted to have the demo code in a main() function, and only execute this if the program was run directly and not imported. That would allow me to use the program as a module also.

With that in mind, all I had left was a function to move my X/Y assembly by so many steps, on an axis and a specific direction, and I already had one done for another piece of the workshop. Oh, and of course do the guts of my functions.

Overall, it left me with very few choices as to how to implement this, given all these preliminary.

Before we jump into the code, for any of this to make sense, you will have to read the PyHack step by step article, so you understand at least a little bit how stepper motors operate, and see some simpler Python code. 

And if you are just starting and dont know anything about RPi.GPIO, I'd recommend checking out the Tutorial section in the menu at the top of the site, and in particular PyHack Workshop #01 and RPi.GPIO dot dash

Code

Let's first look at the whole listing:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#!/usr/bin/env python
""" piasketch - The Pi-A-Sketch program draws a few circles
It is also a basic library for steppers controlling an X/Y device.

The main functions are line(x,y) and circle(radius).
"""
import RPi.GPIO as gpio
import time

PINS_A = [4, 25, 24, 23]
PINS_B = [22, 21, 18, 17]
PINS = PINS_A + PINS_B
SEQA = [(4, ), (4, 25), (25, ), (25, 24), (24, ), (24, 23), (23, ), (23, 4)]
RSEQA = SEQA[::-1][1:] + SEQA[::-1][:1]
SEQB = [(22, ), (22, 21), (21, ), (21, 18), (18, ), (18, 17), (17, ), (17, 22)]
RSEQB = SEQB[::-1][1:] + SEQB[::-1][:1]

CORRECTION = 22


def setallpins():
    """
    Before we can use them, we need to set the pins for both motors
    """
    gpio.setmode(gpio.BCM)
    for pin in PINS:
        gpio.setup(pin, gpio.OUT)


def stepper(sequence, pins, delay=0.002):
    """
    One full step, based on an ordered sequence and corresponding pins
    """
    for step in sequence:
        for pin in pins:
            gpio.output(pin, gpio.HIGH if pin in step else gpio.LOW)
        time.sleep(delay)


def move(steps, axis="x"):
    """
    Move a certain number of steps on a specific axis. sign for direction
    """
    (seq, pins) = (SEQA, PINS_A) if axis == "x" else (SEQB, PINS_B)
    if steps < 0:
        steps = -steps
        seq = RSEQA if axis == "x" else RSEQB
    for _ in range(steps):
        stepper(seq, pins)


def line(x1, y1):
    """
    Bresenham's line algorithm from rosetta code (ADA/Python),
    adapted to relative positioning. It will be drawn from current
    position to x1,y1. Negative number goes in other direction.
    """
    dx = abs(x1)
    dy = abs(y1)
    x, y = 0, 0
    px, py = x, y
    sx = -1 if 0 > x1 else 1
    sy = -1 if 0 > y1 else 1
    if dx > dy:
        err = dx / 2.0
        while x != x1:
            if x - px is not 0:
                move(x - px)
            if y - py is not 0:
                move(y - py, "y")
            px, py = x, y
            err -= dy
            if err < 0:
                y += sy
                err += dx
            x += sx
    else:
        err = dy / 2.0
        while y != y1:
            if x - px is not 0:
                move(x - px)
            if y - py is not 0:
                move(y - py, "y")
            px, py = x, y
            err -= dx
            if err < 0:
                x += sx
                err += dy
            y += sy
    if x - px is not 0:
        move(x - px)
    if y - py is not 0:
        move(y - py, "y")


def _circlepoints(radius):
    """
    mid point circle drawing algorithm - basically Bresenham's.
    It was converted for use with relative. Cant use the bitmap
    approach of the original algorithm. Points are sequential
    clockwise. It works, but it is ugly. I only had a few
    minutes to write this. It needs to be cleaned up.
    """
    points = []
    segment = []
    for seg in range(8):
        x0, y0 = 0, -radius
        f = 1 - radius
        ddf_x, ddf_y = 1, -2 * radius
        x, y = 0, radius

        segment = []
        while x < y:
            if seg == 0:
                segment.append((x0 + x, y0 + y))
            elif seg == 1:
                segment.append((x0 + y, y0 + x))
            elif seg == 2:
                segment.append((x0 + y, y0 - x))
            elif seg == 3:
                segment.append((x0 + x, y0 - y))
            elif seg == 4:
                segment.append((x0 - x, y0 - y))
            elif seg == 5:
                segment.append((x0 - y, y0 - x))
            elif seg == 6:
                segment.append((x0 - y, y0 + x))
            elif seg == 7:
                segment.append((x0 - x, y0 + y))

            if f >= 0:
                y -= 1
                ddf_y += 2
                f += ddf_y
            x += 1
            ddf_x += 2
            f += ddf_x
        if seg % 2:
            points.extend(segment[::-1])
        else:
            points.extend(segment)
    return points


def circle(radius):
    """
    Draw a circle of specified radius. It is not centered. It will start
    drawing a circle at its current position, going right and down.
    """
    points = _circlepoints(radius)
    #print points
    dx, dy = 1, 1
    px, py = 0, 0
    counter = 0
    total = len(points)
    quarter = total / 4
    #print total, quarter
    for (x, y) in points:
        counter += 1
        dx, dy = x - px, y - py
        px, py = x, y
        # print dx, dy
        if dx is not 0:
            move(dx)
        if dy is not 0:
            move(dy, "y")
        if counter == quarter:
            move(-CORRECTION)
        elif counter == quarter * 2:
            move(CORRECTION, "y")
        elif counter == quarter * 3:
            move(CORRECTION)
        elif counter == total:
            move(-CORRECTION, "y")


def main():
    """
    As a standalone app, draw a few circles
    """
    setallpins()
    #line(-50, -200)
    #line(5,0)
    #circle(350)
    for radius in range(100,400,25):
        circle(radius)
    gpio.cleanup()

if __name__ == "__main__":
    main()


It's all in the details

Documentation

Documentation of any program is really important. Don't skip this step, and don't forget to document all the functions too:

1:  #!/usr/bin/env python  
2:  """ piasketch - The Pi-A-Sketch program draws a few circles  
3:  It is also a basic library for steppers controlling an X/Y device.  
4:    
5:  The main functions are line(x,y) and circle(radius).  
6:  """  

You would want to add document encoding instructions at the top, on line 2, if you had to use strings with special characters or accents (like in french, spanish or russian).

Imports

Logically the next step in a Python script is to import modules, if we need any.

7:  import RPi.GPIO as gpio  
8:  import time  

On line 7 we import RPi.GPIO but with an alias of gpio, so we don't have to fully qualify the namespace for every gpio function we call. Please use lowercase gpio. Uppercase in Python is usually for constants (yes, I know that the RPi.GPIO module name itself is not following the standard).

Line 8, we import time, as we will need time.delay() to prevent stalling the steppers (we will use that on line 37).

And speaking of importing a module, the last 2 lines of code allow us to either run this program (see the main() function) or import it as a module:
189:  if __name__ == "__main__":  
190:    main()  

Constants

In Python, all uppercase indicates a constant. This is a convention, since there is no enforcing of the type.

10:  PINS_A = [4, 25, 24, 23]  
11:  PINS_B = [22, 21, 18, 17]  
12:  PINS = PINS_A + PINS_B  
13:  SEQA = [(4, ), (4, 25), (25, ), (25, 24), (24, ), (24, 23), (23, ), (23, 4)]  
14:  RSEQA = SEQA[::-1][1:] + SEQA[::-1][:1]  
15:  SEQB = [(22, ), (22, 21), (21, ), (21, 18), (18, ), (18, 17), (17, ), (17, 22)]  
16:  RSEQB = SEQB[::-1][1:] + SEQB[::-1][:1]  
17:    
18:  CORRECTION = 22  

Line 10 defines the GPIOs for the first stepper (Broadcom GPIO nomenclature) while line 11 defines the GPIOs for the second motor. On a REV2 board, some of the GPIOs have to be adjusted. Specifically, GPIO21 is GPIO27 on a REV2. From these two lists, we create a new one combining all the pins on line 12.

Line 13 and 15 correspond to the sequences for each motors to step forward. In the previous article, the backward sequences were also spelled out like this. Here, on lines 14 and 16, we create the correct backward sequence from two reversed slices of the forward sequence. Spend a bit of time understanding this. If you've never used slices before, it would be a good idea to read the Python tutorial on lists and also this thread on stackoverflow

Finally, on line 18, we define the correction factor (to deal with hysteresis). This is the amount of stepping that has to be done to undo the slack in the Etch-A-Sketch when we reverse direction.

Preliminary GPIO operations


We are now getting into the GPIO code. In an interactive session or a main() program, setallpins() has to be called before line() and circle() can be used.

21:  def setallpins():  
22:    """  
23:    Before we can use them, we need to set the pins for both motors  
24:    """  
25:    gpio.setmode(gpio.BCM)  
26:    for pin in PINS:  
27:      gpio.setup(pin, gpio.OUT)  

Line 21 defines the function, with no arguments. It uses our global PINS constant. It would be a better idea to not use globals, but for such a small module, in a workshop setting, this is an acceptable compromise. Again, don't forget to document your code (lines 22-24)...

Line 25 sets the gpio module to Broadcom GPIO numbering (BCM). Line 26 establishes a loop that will iterate through all the elements of the list PINS, and call line 27 to set up each pin (element) as OUTput.

Basic stepper movement

Reusing the function we defined in the stepper section of PyHack:

30:  def stepper(sequence, pins, delay=0.002):  
31:    """  
32:    One full step, based on an ordered sequence and corresponding pins  
33:    """  
34:    for step in sequence:  
35:      for pin in pins:  
36:        gpio.output(pin, gpio.HIGH if pin in step else gpio.LOW)  
37:      time.sleep(delay)  

On line 30 we are defining a function, with 2 required arguments, and an optional argument: a sequence and pins, and the optional delay (will default to 0.002 seconds if not provided).

Line 34 starts iterating through the sequence, and for each step in that sequence (notice how the Python is written just like english or pseudocode?) we will iterate through all the pins in order to set them HIGH or LOW. We do that through a ternary operator on line 36:

gpio.HIGH if pin in step else gpio.LOW

In other words, if the pin I'm looking at is in that step, return a gpio.HIGH value, else return a gpio.LOW value. We then pass that as the second argument to gpio.output().

Multiple steps on one axis and one direction

The previous function does one step based on a sequence. This one leverages stepper() to do many steps.

40:  def move(steps, axis="x"):  
41:    """  
42:    Move a certain number of steps on a specific axis. sign for direction  
43:    """  
44:    (seq, pins) = (SEQA, PINS_A) if axis == "x" else (SEQB, PINS_B)  
45:    if steps < 0:  
46:      steps = -steps  
47:      seq = RSEQA if axis == "x" else RSEQB  
48:    for _ in range(steps):  
49:      stepper(seq, pins)  

On line 40 we define the function, with steps as required and by default it will happen on the X axis. if we pass "y" (really anything else but "x") it will change sequence to the one that controls the other motor.

On line 44 we build a tuple that will control motor A (x axis) or B (y axis), depending on the axis. It is again a ternary operator that is used. We are almost ready to call the stepper() function, but first, we have to figure out which direction we are going on the axis. On line 45, if we have negative steps, it means we need to reverse the sequence. We convert the negative number into a positive one on line 46 and use a reversed sequence on line 47 (RSEQA if  we are on the x axis, else we use RSEQB).
Finally, on line 48 we loop for the number of steps, calling the stepper() function for each steps.

Drawing lines

This is where we ask Bresenham for help:

On Rosetta code, you'll find an article that works on bitmaps (absolute positioning). If we look at the core itself:
        while x != x1:
            self.set(x, y)
            err -= dy
            if err < 0:
                y += sy
                err += dx
            x += sx
 
This corresponds to our lines 66, 72-76:
 
52:  def line(x1, y1):  
53:    """  
54:    Bresenham's line algorithm from rosetta code (ADA/Python),  
55:    adapted to relative positioning. It will be drawn from current  
56:    position to x1,y1. Negative number goes in other direction.  
57:    """  
58:    dx = abs(x1)  
59:    dy = abs(y1)  
60:    x, y = 0, 0  
61:    px, py = x, y  
62:    sx = -1 if 0 > x1 else 1  
63:    sy = -1 if 0 > y1 else 1  
64:    if dx > dy:  
65:      err = dx / 2.0  
66:      while x != x1:  
67:        if x - px is not 0:  
68:          move(x - px)  
69:        if y - py is not 0:  
70:          move(y - py, "y")  
71:        px, py = x, y  
72:        err -= dy  
73:        if err < 0:  
74:          y += sy  
75:          err += dx  
76:        x += sx  
77:    else:  
78:      err = dy / 2.0  
79:      while y != y1:  
80:        if x - px is not 0:  
81:          move(x - px)  
82:        if y - py is not 0:  
83:          move(y - py, "y")  
84:        px, py = x, y  
85:        err -= dx  
86:        if err < 0:  
87:          x += sx  
88:          err += dy  
89:        y += sy  
90:    if x - px is not 0:  
91:      move(x - px)  
92:    if y - py is not 0:  
93:      move(y - py, "y")  

First, I had to add support for relative positioning by adding logic to track the previous position. This is done on lines 61, 71 and 84.

What I then had to do is to add lines 67 through 70, making sure there is something to do (is not 0 condition on lines 67 and 69) and convert the x and y coordinates into a relative movement based on the previously calculated position (lines 68 and 70). Lines 80-83 and 90-93 is more of the same.

This could be refactored into a function and called at these 3 places. And that is a normal part of the coding process. The first pass, you spend only minutes on a specific area of a project, just enough to get it to the point where it can be easily read and maintained, but no more. Then later, when you are done, if you still have some time, do some R&R (refactoring and reengineering) of your code.

Creating a list of coordinates for a circle

It gets worse. Now we have to deal with drawing a circle. What I would suggest is to skip this code and go and check out the circle() function first, then come back to this.
96:  def _circlepoints(radius):  
97:    """  
98:    mid point circle drawing algorithm - basically Bresenham's.  
99:    It was converted for use with relative. Cant use the bitmap  
100:    approach of the original algorithm. Points are sequential  
101:    clockwise. It works, but it is ugly. I only had a few  
102:    minutes to write this. It needs to be cleaned up.  
103:    """  
104:    points = []  
105:    segment = []  
106:    for seg in range(8):  
107:      x0, y0 = 0, -radius  
108:      f = 1 - radius  
109:      ddf_x, ddf_y = 1, -2 * radius  
110:      x, y = 0, radius  
111:    
112:      segment = []  
113:      while x < y:  
114:        if seg == 0:  
115:          segment.append((x0 + x, y0 + y))  
116:        elif seg == 1:  
117:          segment.append((x0 + y, y0 + x))  
118:        elif seg == 2:  
119:          segment.append((x0 + y, y0 - x))  
120:        elif seg == 3:  
121:          segment.append((x0 + x, y0 - y))  
122:        elif seg == 4:  
123:          segment.append((x0 - x, y0 - y))  
124:        elif seg == 5:  
125:          segment.append((x0 - y, y0 - x))  
126:        elif seg == 6:  
127:          segment.append((x0 - y, y0 + x))  
128:        elif seg == 7:  
129:          segment.append((x0 - x, y0 + y))  
130:    
131:        if f >= 0:  
132:          y -= 1  
133:          ddf_y += 2  
134:          f += ddf_y  
135:        x += 1  
136:        ddf_x += 2  
137:        f += ddf_x  
138:      if seg % 2:  
139:        points.extend(segment[::-1])  
140:      else:  
141:        points.extend(segment)  
142:    return points 

The code here is the midpoint circle algorithm. The main issue with that algorithm is that it is very efficient and generate points in a non sequential way.

On lines 107-110 I set up the calculation initial state, before hitting a while loop.

If you look at a circle, we can easily see that at a minimum, it is made for four identical quarters. And a quarter is mirrored around each axis. So, by calculating half of a quarter circle (1/8 of a circle, an octant), we have basically calculated all the points we need, simply by flipping the signs and axis.

Symmetry



On the Rosetta code page, it is basically implemented with these lines:

        self.set(x0 + x, y0 + y, colour)
        self.set(x0 - x, y0 + y, colour)
        self.set(x0 + x, y0 - y, colour)
        self.set(x0 - x, y0 - y, colour)
        self.set(x0 + y, y0 + x, colour)
        self.set(x0 - y, y0 + x, colour)
        self.set(x0 + y, y0 - x, colour)
        self.set(x0 - y, y0 - x, colour)

I've done something similar with lines 115, 117, 119, 121, 123, 125, 127 and 129. But since I am not using a bitmap and I want an ordered list of points (clockwise), I had to loop 8 times (line 106) and add if statements ( lines 114, 116, 118 etc) in front of every calculations. It is slightly slower this way, but at least I'm not calculating these points 7 times too many. Once a segment is complete (generated by the while loop on line 113), I add that segment to my points list, but with yet another twist. If the segment is odd, it has been generated through a mirror coordinate, so it was built in reverse. So we check on line 138 if the segment modulo 2 has a remainder. If it does (odd number) then we add the segment in reverse on line 139 ( [::-1] ), else, we add it straight on line 141.

When we are done, we return the whole list, on line 142.

Drawing circle based on previous function

Now we are talking. We'll draw a circle based on a given radius. It starts like the Bresenham line drawing algorithm. That's because we are drawing tiny lines.

145:  def circle(radius):  
146:    """  
147:    Draw a circle of specified radius. It is not centered. It will start  
148:    drawing a circle at its current position, going right and down.  
149:    """  
150:    points = _circlepoints(radius)  
151:    #print points  
152:    dx, dy = 1, 1  
153:    px, py = 0, 0  
154:    counter = 0  
155:    total = len(points)  
156:    quarter = total / 4  
157:    #print total, quarter  
158:    for (x, y) in points:  
159:      counter += 1  
160:      dx, dy = x - px, y - py  
161:      px, py = x, y  
162:      # print dx, dy  
163:      if dx is not 0:  
164:        move(dx)  
165:      if dy is not 0:  
166:        move(dy, "y")  
167:      if counter == quarter:  
168:        move(-CORRECTION)  
169:      elif counter == quarter * 2:  
170:        move(CORRECTION, "y")  
171:      elif counter == quarter * 3:  
172:        move(CORRECTION)  
173:      elif counter == total:  
174:        move(-CORRECTION, "y")  

I wrote this, inspired by the line algorithm, but with a few twists. First, the line destination is based on a list of points that is calculated by another function (_circlepoints() ) called on line 150. I reset a counter on line 154 and figure out the total number of points on line 155. We will use this on lines 167-174 to correct the slop at the conclusion of each quarter of the circle, where we are changing direction. Line 158 is where I step through the points in the circle (a list of x/y tuples names points).

Within the for loop, I increment the counter on line 159, calculate the deltas on line 160, save the previous value on line 161 and then lines 163-166 I do the move() logic that I've already covered in the line() function. Since this is the 4th time I do this boilerplate code, it tells me that there is an interface mismatch between what I thought I would need when I defined the move() function, and what I really needed. move() was defined for another project, so it makes sense that there is this mismatch. A quick fix would be to modify move() to accept not just a single value, but an x/y tuple also, and inside move() to exit right away if we have a zero value, or to call itself for the x and y axis (recursion). This would get the 4 line boilerplate code back to 1 line. If you want to see the end result, follow me on twitter @f_dion as I will send an update when I refactor the code.

The demo section

We are almost there.

177:  def main():  
178:    """  
179:    As a standalone app, draw a few circles  
180:    """  
181:    setallpins()  
182:    #line(-50, -200)  
183:    #line(5,0)  
184:    #circle(350)  
185:    for radius in range(100,400,25):  
186:      circle(radius)  
187:    gpio.cleanup()  

The main() function is our main demo program. On line 181, we setup the pins for output, on line 185 I loop with a radius that will start at 100, then will go to 125, 150 etc. We simply call the circle() function with that radius. Finally, on line 187, we cleanup, so the gpios are no longer outputs.

The interactive mode


To use the module in an interactive mode:

Just make sure you qualify the functions using the module name, or the alias if you import as alias
pi@fdion-rpi ~/ $ sudo python
Python 2.7.3rc2 (default, May  6 2012, 20:02:25)
[GCC 4.6.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import piasketch as p
>>> setallpins()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'setallpins' is not defined
>>> p.setallpins()
>>> p.line(25,12)
>>> p.circle(80)
>>> p.gpio.cleanup()
>>> exit()


This concludes our piasketch.py code review!

@f_dion

2 comments:

fab31 said...

Hi! Thanks for writing.
Having png or svg input could be very nice, did you thought about it ?

Francois Dion said...

Yes, we've discussed that quite a bit at the last two workshops. I've done some very preliminary work on it.