1# -*- coding: utf-8 -*-
2"""Pygame Drawing algorithms written in Python. (Work in Progress)
3
4Implement Pygame's Drawing Algorithms in a Python version for testing
5and debugging.
6"""
7from __future__ import absolute_import, division
8from collections import namedtuple
9import sys
10
11if sys.version_info >= (3, 0, 0):
12    from math import floor, ceil
13else:
14    # Python2.7
15    # FIXME : the import of the builtin math module is broken ...
16    def floor(value):
17        """
18        Get the floor int from a float.
19
20        :param value:
21        :return: an int
22        """
23        int_value = int(value)
24        return (int_value
25                if (value == int_value or value > 0)
26                else int_value - 1)
27
28
29    def ceil(value):
30        """
31        Get the ceil int from a float.
32
33        :param value:
34        :return: an int
35        """
36        int_value = int(value)
37        return (int_value
38                if (int_value == value or value < 0)
39                else int_value + 1)
40
41
42#   H E L P E R   F U N C T I O N S    #
43
44# fractional part of x
45
46def frac(value):
47    """return fractional part of x"""
48    return value - floor(value)
49
50
51def inv_frac(value):
52    """return inverse fractional part of x"""
53    return 1 - (value - floor(value))  # eg, 1 - frac(x)
54
55
56BoundingBox = namedtuple('BoundingBox', ['left', 'top', 'right', 'bottom'])
57Point = namedtuple('Point', ['x', 'y'])
58
59
60#   L O W   L E V E L   D R A W   F U N C T I O N S   #
61# (They are too low-level to be translated into python, right?)
62
63def set_at(surf, in_x, in_y, color):
64    """ Set the color of a pixel in a surface"""
65    surf.set_at((in_x, in_y), color)
66
67
68def draw_pixel(surf, pos, color, bright, blend=True):
69    """draw one blended pixel with given brightness."""
70    try:
71        other_col = surf.get_at(pos) if blend else (0, 0, 0, 0)
72    except IndexError:  # pixel outside the surface
73        return
74    new_color = tuple((bright * col + (1 - bright) * pix)
75                      for col, pix in zip(color, other_col))
76    # FIXME what should happen if only one, color or surf_col, has alpha?
77    surf.set_at(pos, new_color)
78
79
80def _drawhorzline(surf, color, x_from, in_y, x_to):
81    if x_from == x_to:
82        surf.set_at((x_from, in_y), color)
83        return
84
85    start, end = (x_from, x_to) if x_from <= x_to else (x_to, x_from)
86    for line_x in range(start, end + 1):
87        surf.set_at((line_x, in_y), color)
88
89
90def _drawvertline(surf, color, in_x, y_from, y_to):
91    if y_from == y_to:
92        surf.set_at((in_x, y_from), color)
93        return
94
95    start, end = (y_from, y_to) if y_from <= y_to else (y_to, y_from)
96    for line_y in range(start, end + 1):
97        surf.set_at((in_x, line_y), color)
98
99
100#    I N T E R N A L   D R A W   L I N E   F U N C T I O N S    #
101
102def _clip_and_draw_horizline(surf, color, x_from, in_y, x_to):
103    """draw clipped horizontal line."""
104    # check Y inside surf
105    clip = surf.get_clip()
106    if in_y < clip.y or in_y >= clip.y + clip.h:
107        return
108
109    x_from = max(x_from, clip.x)
110    x_to = min(x_to, clip.x + clip.w - 1)
111
112    # check any x inside surf
113    if x_to < clip.x or x_from >= clip.x + clip.w:
114        return
115
116    _drawhorzline(surf, color, x_from, in_y, x_to)
117
118
119def _clip_and_draw_vertline(surf, color, in_x, y_from, y_to):
120    """draw clipped vertical line."""
121    # check X inside surf
122    clip = surf.get_clip()
123
124    if in_x < clip.x or in_x >= clip.x + clip.w:
125        return
126
127    y_from = max(y_from, clip.y)
128    y_to = min(y_to, clip.y + clip.h - 1)
129
130    # check any y inside surf
131    if y_to < clip.y or y_from >= clip.y + clip.h:
132        return
133
134    _drawvertline(surf, color, in_x, y_from, y_to)
135
136
137# These constants xxx_EDGE are "outside-the-bounding-box"-flags
138LEFT_EDGE = 0x1
139RIGHT_EDGE = 0x2
140BOTTOM_EDGE = 0x4
141TOP_EDGE = 0x8
142
143
144def encode(pos, b_box):
145    """returns a code that defines position with respect to a bounding box"""
146    # we use the fact that python interprets booleans (the inequalities)
147    # as 0/1, and then multiply them with the xxx_EDGE flags
148    return ((pos[0] < b_box.left) * LEFT_EDGE +
149            (pos[0] > b_box.right) * RIGHT_EDGE +
150            (pos[1] < b_box.top) * TOP_EDGE +
151            (pos[1] > b_box.bottom) * BOTTOM_EDGE)
152
153
154def clip_line(line, b_box, use_float=False):
155    """Algorithm to calculate the clipped line.
156
157    We calculate the coordinates of the part of the line segment within the
158    bounding box (defined by left, top, right, bottom). The we write
159    the coordinates of the line segment into "line", much like the C-algorithm.
160    With `use_float` True, clip_line is usable for float-clipping.
161
162    Returns: true if the line segment cuts the bounding box (false otherwise)
163    """
164
165    def inside(code):
166        return not code
167
168    def accept(code_a, code_b):
169        return not (code_a or code_b)
170
171    def reject(code_a, code_b):
172        return code_a and code_b
173
174    assert isinstance(line, list)
175    x_1, y_1, x_2, y_2 = line
176    dtype = float if use_float else int
177
178    while True:
179        # the coordinates are progressively modified with the codes,
180        # until they are either rejected or correspond to the final result.
181        code1 = encode((x_1, y_1), b_box)
182        code2 = encode((x_2, y_2), b_box)
183
184        if accept(code1, code2):
185            # write coordinates into "line" !
186            line[:] = x_1, y_1, x_2, y_2
187            return True
188        if reject(code1, code2):
189            return False
190
191        # We operate on the (x_1, y_1) point,
192        # and swap if it is inside the bbox:
193        if inside(code1):
194            x_1, x_2 = x_2, x_1
195            y_1, y_2 = y_2, y_1
196            code1, code2 = code2, code1
197        slope = (y_2 - y_1) / float(x_2 - x_1) if (x_2 != x_1) else 1.0
198        # Each case, if true, means that we are outside the border:
199        # calculate x_1 and y_1 to be the "first point" inside the bbox...
200        if code1 & LEFT_EDGE:
201            y_1 += dtype((b_box.left - x_1) * slope)
202            x_1 = b_box.left
203        elif code1 & RIGHT_EDGE:
204            y_1 += dtype((b_box.right - x_1) * slope)
205            x_1 = b_box.right
206        elif code1 & BOTTOM_EDGE:
207            if x_2 != x_1:
208                x_1 += dtype((b_box.bottom - y_1) / slope)
209            y_1 = b_box.bottom
210        elif code1 & TOP_EDGE:
211            if x_2 != x_1:
212                x_1 += dtype((b_box.top - y_1) / slope)
213            y_1 = b_box.top
214
215
216def _draw_line(surf, color, start, end):
217    """draw a non-horizontal line (without anti-aliasing)."""
218    # Variant of https://en.wikipedia.org/wiki/Bresenham's_line_algorithm
219    #
220    # This strongly differs from craw.c implementation, because we use a
221    # "slope" variable (instead of delta_x and delta_y) and a "error" variable.
222    # And we can not do pointer-arithmetic with "BytesPerPixel", like in
223    # the C-algorithm.
224    if start.x == end.x:
225        # This case should not happen...
226        raise ValueError
227
228    slope = abs((end.y - start.y) / (end.x - start.x))
229    error = 0.0
230
231    if slope < 1:
232        # Here, it's a rather horizontal line
233
234        # 1. check in which octants we are & set init values
235        if end.x < start.x:
236            start.x, end.x = end.x, start.x
237            start.y, end.y = end.y, start.y
238        line_y = start.y
239        dy_sign = 1 if (start.y < end.y) else -1
240
241        # 2. step along x coordinate
242        for line_x in range(start.x, end.x + 1):
243            set_at(surf, line_x, line_y, color)
244            error += slope
245            if error >= 0.5:
246                line_y += dy_sign
247                error -= 1
248    else:
249        # Case of a rather vertical line
250
251        # 1. check in which octants we are & set init values
252        if start.y > end.y:
253            start.x, end.x = end.x, start.x
254            start.y, end.y = end.y, start.y
255        line_x = start.x
256        slope = 1 / slope
257        dx_sign = 1 if (start.x < end.x) else -1
258
259        # 2. step along y coordinate
260        for line_y in range(start.y, end.y + 1):
261            set_at(surf, line_x, line_y, color)
262            error += slope
263            if error >= 0.5:
264                line_x += dx_sign
265                error -= 1
266
267
268def _draw_aaline(surf, color, start, end, blend):
269    """draw an anti-aliased line.
270
271    The algorithm yields identical results with _draw_line for horizontal,
272    vertical or diagonal lines, and results changes smoothly when changing
273    any of the endpoint coordinates.
274
275    Note that this yields strange results for very short lines, eg
276    a line from (0, 0) to (0, 1) will draw 2 pixels, and a line from
277    (0, 0) to (0, 1.1) will blend 10 % on the pixel (0, 2).
278    """
279    # The different requirements that we have on an antialiasing algorithm
280    # implies to make some compromises:
281    # 1. We want smooth evolution wrt to the 4 endpoint coordinates
282    #    (this means also that we want a smooth evolution when the angle
283    #     passes +/- 45°
284    # 2. We want the same behavior when swapping the endpoints
285    # 3. We want understandable results for the endpoint values
286    #    (eg we want to avoid half-integer values to draw a simple plain
287    #     horizontal or vertical line between two integer l endpoints)
288    #
289    # This implies to somehow make the line artificially 1 pixel longer
290    # and to draw a full pixel when we have the  endpoints are identical.
291    d_x = end.x - start.x
292    d_y = end.y - start.y
293
294    if d_x == 0 and d_y == 0:
295        # For smoothness reasons, we could also do some blending here,
296        # but it seems overshoot...
297        set_at(surf, int(start.x), int(start.y), color)
298        return
299
300    if start.x > end.x or start.y > end.y:
301        start.x, end.x = end.x, start.x
302        start.y, end.y = end.y, start.y
303        d_x = -d_x
304        d_y = -d_y
305
306    if abs(d_x) >= abs(d_y):
307        slope = d_y / d_x
308
309        def draw_two_pixel(in_x, float_y, factor):
310            flr_y = floor(float_y)
311            draw_pixel(surf, (in_x, flr_y), color,
312                       factor * inv_frac(float_y), blend)
313            draw_pixel(surf, (in_x, flr_y + 1), color,
314                       factor * frac(float_y), blend)
315
316        _draw_aaline_dx(d_x, slope, end, start, draw_two_pixel)
317    else:
318        slope = d_x / d_y
319
320        def draw_two_pixel(float_x, in_y, factor):
321            fl_x = floor(float_x)
322            draw_pixel(surf, (fl_x, in_y), color,
323                       factor * inv_frac(float_x), blend)
324            draw_pixel(surf, (fl_x + 1, in_y), color,
325                       factor * frac(float_x), blend)
326
327        _draw_aaline_dy(d_y, slope, end, start, draw_two_pixel)
328
329
330def _draw_aaline_dy(d_y, slope, end, start, draw_two_pixel):
331    g_y = ceil(start.y)
332    g_x = start.x + (g_y - start.y) * slope
333    # 1. Draw start of the segment
334    if start.y < g_y:
335        draw_two_pixel(g_x - slope, floor(start.y), inv_frac(start.y))
336    # 2. Draw end of the segment
337    rest = frac(end.y)
338    s_y = ceil(end.y)
339    if rest > 0:
340        s_x = start.x + slope * (d_y + 1 - rest)
341        draw_two_pixel(s_x, s_y, rest)
342    else:
343        s_y += 1
344    # 3. loop for other points
345    for line_y in range(g_y, s_y):
346        line_x = g_x + slope * (line_y - g_y)
347        draw_two_pixel(line_x, line_y, 1)
348
349
350def _draw_aaline_dx(d_x, slope, end, start, draw_two_pixel):
351    # A and G are respectively left and right to the "from" point, but
352    # with integer-x-coordinate, (and only if from_x is not integer).
353    # Hence they appear in following order on the line in general case:
354    #  A   from-pt    G    .  .  .        to-pt    S
355    #  |------*-------|--- .  .  . ---|-----*------|-
356    g_x = ceil(start.x)
357    g_y = start.y + (g_x - start.x) * slope
358    # 1. Draw start of the segment if we have a non-integer-part
359    if start.x < g_x:
360        # this corresponds to the point "A"
361        draw_two_pixel(floor(start.x), g_y - slope, inv_frac(start.x))
362    # 2. Draw end of the segment: we add one pixel for homogeneity reasons
363    rest = frac(end.x)
364    s_x = ceil(end.x)
365    if rest > 0:
366        # Again we draw only if we have a non-integer-part
367        s_y = start.y + slope * (d_x + 1 - rest)
368        draw_two_pixel(s_x, s_y, rest)
369    else:
370        s_x += 1
371    # 3. loop for other points
372    for line_x in range(g_x, s_x):
373        line_y = g_y + slope * (line_x - g_x)
374        draw_two_pixel(line_x, line_y, 1)
375
376
377#   C L I P   A N D   D R A W   L I N E   F U N C T I O N S    #
378
379def _clip_and_draw_line(surf, rect, color, pts):
380    """clip the line into the rectangle and draw if needed.
381
382    Returns true if anything has been drawn, else false."""
383    # "pts" is a list with the four coordinates of the two endpoints
384    # of the line to be drawn : pts = x1, y1, x2, y2.
385    # The data format is like that to stay closer to the C-algorithm.
386    if not clip_line(pts, BoundingBox(rect.x, rect.y,
387                                      rect.x + rect.w - 1,
388                                      rect.y + rect.h - 1)):
389        # The line segment defined by "pts" is not crossing the rectangle
390        return 0
391    if pts[1] == pts[3]:  # eg y1 == y2
392        _drawhorzline(surf, color, pts[0], pts[1], pts[2])
393    elif pts[0] == pts[2]:  # eg x1 == x2
394        _drawvertline(surf, color, pts[0], pts[1], pts[3])
395    else:
396        _draw_line(surf, color, Point(pts[0], pts[1]), Point(pts[2], pts[3]))
397    return 1
398
399
400def _clip_and_draw_line_width(surf, rect, color, line, width):
401    yinc = xinc = 0
402    if abs(line[0] - line[2]) > abs(line[1] - line[3]):
403        yinc = 1
404    else:
405        xinc = 1
406    newpts = line[:]
407    if _clip_and_draw_line(surf, rect, color, newpts):
408        anydrawn = 1
409        frame = newpts[:]
410    else:
411        anydrawn = 0
412        frame = [10000, 10000, -10000, -10000]
413
414    for loop in range(1, width // 2 + 1):
415        newpts[0] = line[0] + xinc * loop
416        newpts[1] = line[1] + yinc * loop
417        newpts[2] = line[2] + xinc * loop
418        newpts[3] = line[3] + yinc * loop
419        if _clip_and_draw_line(surf, rect, color, newpts):
420            anydrawn = 1
421            frame[0] = min(newpts[0], frame[0])
422            frame[1] = min(newpts[1], frame[1])
423            frame[2] = max(newpts[2], frame[2])
424            frame[3] = max(newpts[3], frame[3])
425
426        if loop * 2 < width:
427            newpts[0] = line[0] - xinc * loop
428            newpts[1] = line[1] - yinc * loop
429            newpts[2] = line[2] - xinc * loop
430            newpts[3] = line[3] - yinc * loop
431            if _clip_and_draw_line(surf, rect, color, newpts):
432                anydrawn = 1
433                frame[0] = min(newpts[0], frame[0])
434                frame[1] = min(newpts[1], frame[1])
435                frame[2] = max(newpts[2], frame[2])
436                frame[3] = max(newpts[3], frame[3])
437
438    return anydrawn
439
440
441def _clip_and_draw_aaline(surf, rect, color, line, blend):
442    """draw anti-aliased line between two endpoints."""
443    if not clip_line(line,
444                     BoundingBox(rect.x - 1, rect.y - 1,
445                                 rect.x + rect.w,
446                                 rect.y + rect.h),
447                     use_float=True):
448        return  # TODO Rect(rect.x, rect.y, 0, 0)
449    _draw_aaline(surf, color,
450                 Point(line[0], line[1]),
451                 Point(line[2], line[3]),
452                 blend)
453    return  # TODO Rect(-- affected area --)
454
455
456#    D R A W   L I N E   F U N C T I O N S    #
457
458def draw_aaline(surf, color, from_point, to_point, blend=True):
459    """draw anti-aliased line between two endpoints."""
460    line = [from_point[0], from_point[1], to_point[0], to_point[1]]
461    return _clip_and_draw_aaline(surf, surf.get_clip(), color, line, blend)
462
463
464def draw_line(surf, color, from_point, to_point, width=1):
465    """draw anti-aliased line between two endpoints."""
466    line = [from_point[0], from_point[1], to_point[0], to_point[1]]
467    return _clip_and_draw_line_width(surf, surf.get_clip(), color, line, width)
468
469
470#   M U L T I L I N E   F U N C T I O N S   #
471
472def _multi_lines(surf, color, closed,  # pylint: disable=too-many-arguments
473                 points, width=1, blend=False,
474                 aaline=False):
475    """draw several lines, either anti-aliased or not."""
476    # The code for anti-aliased or not is almost identical, so it's factorized
477    if len(points) <= 2:
478        raise TypeError
479    line = [0] * 4  # store x1, y1 & x2, y2 of the lines to be drawn
480
481    xlist = [pt[0] for pt in points]
482    ylist = [pt[1] for pt in points]
483    line[0] = xlist[0]
484    line[1] = ylist[0]
485    b_box = BoundingBox(left=xlist[0], right=xlist[0],
486                        top=ylist[0], bottom=ylist[0])
487
488    for line_x, line_y in points[1:]:
489        b_box.left = min(b_box.left, line_x)
490        b_box.right = max(b_box.right, line_x)
491        b_box.top = min(b_box.top, line_y)
492        b_box.bottom = max(b_box.bottom, line_y)
493
494    rect = surf.get_clip()
495    for loop in range(1, len(points)):
496
497        line[0] = xlist[loop - 1]
498        line[1] = ylist[loop - 1]
499        line[2] = xlist[loop]
500        line[3] = ylist[loop]
501        if aaline:
502            _clip_and_draw_aaline(surf, rect, color, line, blend)
503        else:
504            _clip_and_draw_line_width(surf, rect, color, line, width)
505
506    if closed:
507        line[0] = xlist[len(points) - 1]
508        line[1] = ylist[len(points) - 1]
509        line[2] = xlist[0]
510        line[3] = ylist[0]
511        if aaline:
512            _clip_and_draw_aaline(surf, rect, color, line, blend)
513        else:
514            _clip_and_draw_line_width(surf, rect, color, line, width)
515
516    # TODO Rect(...)
517
518
519def draw_lines(surf, color, closed, points, width=1):
520    """draw several lines connected through the points."""
521    return _multi_lines(surf, color, closed, points, width, aaline=False)
522
523
524def draw_aalines(surf, color, closed, points, blend=True):
525    """draw several anti-aliased lines connected through the points."""
526    return _multi_lines(surf, color, closed, points, blend=blend, aaline=True)
527
528
529def draw_polygon(surface, color, points, width):
530    """ Draw a polygon"""
531    if width:
532        draw_lines(surface, color, 1, points, width)
533        return  # TODO Rect(...)
534    num_points = len(points)
535    point_x = [x for x, y in points]
536    point_y = [y for x, y in points]
537
538    miny = min(point_y)
539    maxy = max(point_y)
540
541    if miny == maxy:
542        minx = min(point_x)
543        maxx = max(point_x)
544        _clip_and_draw_horizline(surface, color, minx, miny, maxx)
545        return  # TODO Rect(...)
546
547    for y_coord in range(miny, maxy + 1):
548        x_intersect = []
549        for i in range(num_points):
550            _draw_polygon_inner_loop(i, point_x, point_y,
551                                     y_coord, x_intersect)
552
553        x_intersect.sort()
554        for i in range(0, len(x_intersect), 2):
555            _clip_and_draw_horizline(surface, color, x_intersect[i], y_coord,
556                                     x_intersect[i + 1])
557
558    # special case : horizontal border lines
559    for i in range(num_points):
560        i_prev = i - 1 if i else num_points - 1
561        if miny < point_y[i] == point_y[i_prev] < maxy:
562            _clip_and_draw_horizline(surface, color, point_x[i], point_y[i],
563                                     point_x[i_prev])
564
565    return  # TODO Rect(...)
566
567
568def _draw_polygon_inner_loop(index, point_x, point_y, y_coord, x_intersect):
569    i_prev = index - 1 if index else len(point_x) - 1
570
571    y_1 = point_y[i_prev]
572    y_2 = point_y[index]
573
574    if y_1 < y_2:
575        x_1 = point_x[i_prev]
576        x_2 = point_x[index]
577    elif y_1 > y_2:
578        y_2 = point_y[i_prev]
579        y_1 = point_y[index]
580        x_2 = point_x[i_prev]
581        x_1 = point_x[index]
582    else:  # special case handled below
583        return
584
585    if ((y_2 > y_coord >= y_1) or
586            ((y_coord == max(point_y)) and (y_coord <= y_2))):
587        x_intersect.append((y_coord - y_1) *
588                           (x_2 - x_1) //
589                           (y_2 - y_1) + x_1)
590