最近读研期间上了计算机可视化的课，老师也对计算机图形学的实现布置了相关的作业。虽然我没有系统地学过图形可视化的课，但是我之前逆向过一些游戏引擎，除了保护驱动之外，因为要做透视，接触过一些计算机图形学的基础常识。这次的作业主要分为2个主要模块，一个是实现画线，画圆的算法，还有填充的算法，以及裁剪的算法。

之前工作的时候虽然参与过一些数据可视化大屏的设计，但是当时主要的工作使用Echarts或者G2做业务组件开发，并没有对画线，填充，裁剪等基础算法做过实现。这次就着这个机会我就想了解一些。实现的效果如下(动图加载可能有些慢)：

扫描线填充过程

裁剪过程（根据鼠标位置，实时裁剪多边形，右边的蓝色是裁剪后的图形）

为什么选择win32 api画图

选择win32的原因是我想做一些与众不同的实现方法，比起用D3或者Echarts这种webGL的实现方式，我更想直接在显示器上画出图像，看起来更极客一些。这也导致了录屏软件没办法捕捉，只能用手机来录制

为什么不选C++而选择python

主要是python能对内存做个管理，C++直接调这种底层的接口会把内存搞坏掉，导致电脑变得特别卡。。不信大家可以在电脑上编译运行这段代码2分钟试一试，如果你电脑没炸，算你有钱。。

#include <windows.h>

// g++ a.cpp -o a.exe -lgdi32 && a.exe

void bresenham(int x0,int y0,int x1,int y1){

    int dx = abs(x1-x0);

    int dy = abs(y1-y0);

    int sx = x0<x1 ? 1 : -1;

    int sy = y0<y1 ? 1 : -1;

    int err = dx-dy;

    int e2;

    while(1){

        SetPixel(GetDC(0),x0,y0,RGB(255,0,0));

        if(x0==x1 && y0==y1) break;

        e2 = 2*err;

        if(e2>-dy){

            err = err-dy;

            x0 = x0+sx;

        }

        if(e2<dx){

            err = err+dx;

            y0 = y0+sy;

        }

    }

}

void draw_polygon(int x[], int y[], int n)

{

    int i;

    for (i = 0; i < n - 1; i++)

        bresenham(x[i], y[i], x[i + 1], y[i + 1]);

    bresenham(x[n - 1], y[n - 1], x[0], y[0]);

}

int main()

{

    HDC hdc = GetDC(0);

    int x[4] = {100,200,300,100};

    int y[4] = {100,100,200,200};

    while (1)

    {

        draw_polygon(x,y,4);

        ReleaseDC(0, hdc);

    }

    return 0;

}

画线

对于画线部分，我这里使用了一个叫bresenham算法。。虽然我念不出名字，但是这个算法能够帮助我们实现画线运算，还有后面的中心圆填充，多边形绘画等方法。而且不通过浮点数的运算，直接变成整数运算，算法实现的函数如下所示，看起来比较简单，运行速度也很快。

def bresenham(x0, y0, x1, y1 , color):

    dx = abs(x1 - x0)

    dy = abs(y1 - y0)

    sx = 1 if x0 < x1 else -1

    sy = 1 if y0 < y1 else -1

    err = dx - dy

    while True:

        win32gui.SetPixel(dc, x0, y0, color)

        if x0 == x1 and y0 == y1:

            break

        e2 = 2 * err

        if e2 > -dy:

            err -= dy

            x0 += sx

        if e2 < dx:

            err += dx

            y0 += sy

我的屏幕分辨率是1920x1080的，只要在电脑里调用这个函数，把两个点的坐标填进去，就可以在显示器屏幕上画一条线。

中心圆算法

这个中心圆算法相对来说就比画线的算法在理解上面难很多，但是实现起来更简单一些，分成8个关于直线的和坐标轴对称的区域画圆，因此知道一个就可以画出其他几个，下面是实现过程。

def draw_circle(x, y, r):

    x0 = 0

    y0 = r

    d = 3 - 2 * r

    while x0 <= y0:

        win32gui.SetPixel(dc, x + x0, y + y0, 0xffffff)

        win32gui.SetPixel(dc, x + y0, y + x0, 0xffffff)

        win32gui.SetPixel(dc, x - y0, y + x0, 0xffffff)

        win32gui.SetPixel(dc, x - x0, y + y0, 0xffffff)

        win32gui.SetPixel(dc, x - x0, y - y0, 0xffffff)

        win32gui.SetPixel(dc, x - y0, y - x0, 0xffffff)

        win32gui.SetPixel(dc, x + y0, y - x0, 0xffffff)

        win32gui.SetPixel(dc, x + x0, y - y0, 0xffffff)

        if d < 0:

            d += 4 * x0 + 6

        else:

            d += 4 * (x0 - y0) + 10

            y0 -= 1

        x0 += 1

在中心圆填充这里，可以取个巧，把几个顶点直接用画线的算法一行一行填充上去。就可以实现下面的效果。代码如下

# 画实心圆

def draw_circle_fill(x0, y0, r):

    x = 0

    y = r

    d = 3 - 2 * r

    while x <= y:

        time.sleep(0.01)

        bresenham(x0 + x, y0 + y, x0 - x, y0 + y)

        time.sleep(0.01)

        bresenham(x0 + x, y0 - y, x0 - x, y0 - y)

        time.sleep(0.01)

        bresenham(x0 + y, y0 + x, x0 - y, y0 + x)

        time.sleep(0.01)

        bresenham(x0 + y, y0 - x, x0 - y, y0 - x)

        if d < 0:

            d += 4 * x + 6

        else:

            d += 4 * (x - y) + 10

            y -= 1

        x += 1

扫描线填充

扫描线填充的算法就比较难实现了，需要找到起始的种子，还有每行的种子，因为我这里仅仅用顶点实现起来过于复杂，就索性偷懒用了数组。下面的算法实现部分仅供参考，具体的实现包括种子的选择等等，可以更好一些。

maps = [[0 for x in range(0,400)] for x in range(0,400)]

for i in range(200,300):

    maps[i][200] = 1

    maps[200][i] = 1

    maps[i][300] = 1

    maps[300][i] = 1

for i in range(230,270):

    maps[i][230] = 1

    maps[i][270] = 1

    maps[230][i] = 1

    maps[270][i] = 1

# 扫描填充maps

def scan_fill():

    seed = (271,296)

    stack = []

    stack.append(seed)

    while len(stack) > 0:

        (x,y) = stack.pop()

        # 如果已经被填充过，则跳过

        if(maps[x][y] == 1):

            continue

        # 横向填充并记录lx rx

        i=0

        time.sleep(0.01)

        while(maps[x+i][y] == 0):

            maps[x+i][y] = 1

            win32gui.SetPixel(dc, x+i, y, 0xffffff)

            i += 1

        rx = x+i-1

        i=1

        while(maps[x-i][y] == 0):

            maps[x-i][y] = 1

            win32gui.SetPixel(dc, x-i, y, 0xffffff)

            i+=1

        lx = x-i+1

        # 下一个种子

        if y+1>=300:

            continue

        i=0

        while(maps[lx+i][y+1] == 0):

            if(maps[lx+i+1][y+1]==1):

                stack.append((lx+i,y+1))

                break

            i+=1

        i=0

        while(maps[rx-i][y+1] == 0):

            if(maps[rx-i-1][y+1]==1):

                stack.append((rx-i,y+1))

                break

            i+=1

        if y-1<=0:

            continue

        i=0

        while(maps[lx+i][y-1] == 0):

            if(maps[lx+i+1][y-1]==1):

                stack.append((lx+i,y-1))

                break

            i+=1

        i=0

        while(maps[rx-i][y-1] == 0):

            if(maps[rx-i-1][y-1]==1):

                stack.append((rx-i,y-1))

                break

            i+=1

scan_fill()

这里是所有代码

上面的代码都是剪切过的，完整的代码如下所示，运行后大家就可以在显示器上看到运行过程：

import time

import win32gui

dc = win32gui.GetDC(0)

maps = [[0 for x in range(0,400)] for x in range(0,400)]

for i in range(200,300):

    maps[i][200] = 1

    maps[200][i] = 1

    maps[i][300] = 1

    maps[300][i] = 1

for i in range(230,270):

    maps[i][230] = 1

    maps[i][270] = 1

    maps[230][i] = 1

    maps[270][i] = 1

# 中点算法画圆

def draw_circle(x, y, r):

    x0 = 0

    y0 = r

    d = 3 - 2 * r

    while x0 <= y0:

        time.sleep(0.01)

        win32gui.SetPixel(dc, x + x0, y + y0, 0xffffff)

        time.sleep(0.01)

        win32gui.SetPixel(dc, x + y0, y + x0, 0xffffff)

        time.sleep(0.01)

        win32gui.SetPixel(dc, x - y0, y + x0, 0xffffff)

        time.sleep(0.01)

        win32gui.SetPixel(dc, x - x0, y + y0, 0xffffff)

        time.sleep(0.01)

        win32gui.SetPixel(dc, x - x0, y - y0, 0xffffff)

        time.sleep(0.01)

        win32gui.SetPixel(dc, x - y0, y - x0, 0xffffff)

        time.sleep(0.01)

        win32gui.SetPixel(dc, x + y0, y - x0, 0xffffff)

        time.sleep(0.01)

        win32gui.SetPixel(dc, x + x0, y - y0, 0xffffff)

        if d < 0:

            d += 4 * x0 + 6

        else:

            d += 4 * (x0 - y0) + 10

            y0 -= 1

        x0 += 1

# 画线

def bresenham(x0, y0, x1, y1):

    dx = abs(x1 - x0)

    dy = abs(y1 - y0)

    sx = 1 if x0 < x1 else -1

    sy = 1 if y0 < y1 else -1

    err = dx - dy

    while True:

        #time.sleep(0.01)

        win32gui.SetPixel(dc, x0, y0, 0xffffff)

        if x0 == x1 and y0 == y1:

            break

        e2 = 2 * err

        if e2 > -dy:

            err -= dy

            x0 += sx

        if e2 < dx:

            err += dx

            y0 += sy

# 画实心圆

def draw_circle_fill(x0, y0, r):

    x = 0

    y = r

    d = 3 - 2 * r

    while x <= y:

        time.sleep(0.01)

        bresenham(x0 + x, y0 + y, x0 - x, y0 + y)

        time.sleep(0.01)

        bresenham(x0 + x, y0 - y, x0 - x, y0 - y)

        time.sleep(0.01)

        bresenham(x0 + y, y0 + x, x0 - y, y0 + x)

        time.sleep(0.01)

        bresenham(x0 + y, y0 - x, x0 - y, y0 - x)

        if d < 0:

            d += 4 * x + 6

        else:

            d += 4 * (x - y) + 10

            y -= 1

        x += 1

# 画多边形

def draw_polygon(points):

    for i in range(len(points)):

        x0 = points[i][0]

        y0 = points[i][1]

        x1 = points[(i + 1) % len(points)][0]

        y1 = points[(i + 1) % len(points)][1]

        bresenham(x0, y0, x1, y1)

# 画椭圆

def draw_ellipse(x0, y0, a, b):

    x = 0

    y = b

    a2 = a * a

    b2 = b * b

    d = b2 - a2 * b + a2 / 4

    while b2 * x <= a2 * y:

        win32gui.SetPixel(dc, x0 + x, y0 + y, 0xffffff)

        win32gui.SetPixel(dc, x0 - x, y0 + y, 0xffffff)

        win32gui.SetPixel(dc, x0 + x, y0 - y, 0xffffff)

        win32gui.SetPixel(dc, x0 - x, y0 - y, 0xffffff)

        if d < 0:

            d += b2 * (2 * x + 3)

        else:

            d += b2 * (2 * x - 2 * y + 5)

            y -= 1

        x += 1

    d1 = b2 * (x + 0.5) * (x + 0.5) + a2 * (y - 1) * (y - 1) - a2 * b2

    while y >= 0:

        win32gui.SetPixel(dc, x0 + x, y0 + y, 0xffffff)

        win32gui.SetPixel(dc, x0 - x, y0 + y, 0xffffff)

        win32gui.SetPixel(dc, x0 + x, y0 - y, 0xffffff)

        win32gui.SetPixel(dc, x0 - x, y0 - y, 0xffffff)

        if d1 > 0:

            d1 -= a2 * (2 * y - 1)

        d1 += b2 * (2 * x + 3)

        x += 1

        y -= 1

# 画矩形

def draw_rectangle(x0, y0, x1, y1):

    bresenham(x0, y0, x1, y0)

    bresenham(x1, y0, x1, y1)

    bresenham(x1, y1, x0, y1)

    bresenham(x0, y1, x0, y0)

# 扫描填充maps

def scan_fill():

    seed = (271,296)

    stack = []

    stack.append(seed)

    while len(stack) > 0:

        (x,y) = stack.pop()

        # 如果已经被填充过，则跳过

        if(maps[x][y] == 1):

            continue

        # 横向填充并记录lx rx

        i=0

        time.sleep(0.01)

        while(maps[x+i][y] == 0):

            maps[x+i][y] = 1

            win32gui.SetPixel(dc, x+i, y, 0xffffff)

            i += 1

        rx = x+i-1

        i=1

        while(maps[x-i][y] == 0):

            maps[x-i][y] = 1

            win32gui.SetPixel(dc, x-i, y, 0xffffff)

            i+=1

        lx = x-i+1

        # 下一个种子

        if y+1>=300:

            continue

        i=0

        while(maps[lx+i][y+1] == 0):

            if(maps[lx+i+1][y+1]==1):

                stack.append((lx+i,y+1))

                break

            i+=1

        i=0

        while(maps[rx-i][y+1] == 0):

            if(maps[rx-i-1][y+1]==1):

                stack.append((rx-i,y+1))

                break

            i+=1

        if y-1<=0:

            continue

        i=0

        while(maps[lx+i][y-1] == 0):

            if(maps[lx+i+1][y-1]==1):

                stack.append((lx+i,y-1))

                break

            i+=1

        i=0

        while(maps[rx-i][y-1] == 0):

            if(maps[rx-i-1][y-1]==1):

                stack.append((rx-i,y-1))

                break

            i+=1

scan_fill()

while True:

    # 画线

    bresenham(400, 900, 1000, 700)

    # 填充圆

    draw_circle_fill(900, 500, 100)

    # 中心圆

    draw_circle(1000, 200, 100)

    # 椭圆

    draw_ellipse(1500, 200, 100, 100)

    # 矩形

    draw_rectangle(1100, 400, 1200, 500)

    # 多边形

    draw_polygon([(900, 1000), (800, 800), (1000, 900), (1100, 1000)])

    #三角形

    draw_polygon([(400, 200), (500, 300), (600, 200)])

裁剪

裁剪这里简直就是我的噩梦，因为我之前为了极客选择了仅仅知道顶点就画出裁剪过的多边形，导致我没有数组，只能设计更极客的算法。

最后我找到了一种裁剪凸多边形的办法，大致就是找到每个线段的交点，然后顺时针方向对交点和在主多边形，副多边形的顶点排序，最后就可以实现裁剪。代码超级复杂，

import win32gui

import math

import pygame

dc = win32gui.GetDC(0)

# 获取鼠标的位置

mouse_x=win32gui.GetCursorPos()[0]

mouse_y=win32gui.GetCursorPos()[1]

temp = win32gui.GetCursorPos()

def get_mouse_pos():

    global mouse_x, mouse_y

    mouse_x = win32gui.GetCursorPos()[0]

    mouse_y = win32gui.GetCursorPos()[1]

clock = pygame.time.Clock()

temp2 = []

def bresenham(x0, y0, x1, y1 , color):

    dx = abs(x1 - x0)

    dy = abs(y1 - y0)

    sx = 1 if x0 < x1 else -1

    sy = 1 if y0 < y1 else -1

    err = dx - dy

    while True:

        win32gui.SetPixel(dc, x0, y0, color)

        if x0 == x1 and y0 == y1:

            break

        e2 = 2 * err

        if e2 > -dy:

            err -= dy

            x0 += sx

        if e2 < dx:

            err += dx

            y0 += sy

def draw_rectangle(x0, y0, x1, y1):

    bresenham(x0, y0, x1, y0,0xffffff)

    bresenham(x1, y0, x1, y1,0xffffff)

    bresenham(x1, y1, x0, y1,0xffffff)

    bresenham(x0, y1, x0, y0,0xffffff)

def draw_polygon(points):

    for i in range(len(points)):

        x0 = points[i][0]

        y0 = points[i][1]

        x1 = points[(i + 1) % len(points)][0]

        y1 = points[(i + 1) % len(points)][1]

        bresenham(x0, y0, x1, y1,0x00ff00)

def draw_polygon_black(points):

    for i in range(len(points)):

        x0 = points[i][0]

        y0 = points[i][1]

        x1 = points[(i + 1) % len(points)][0]

        y1 = points[(i + 1) % len(points)][1]

        bresenham(x0, y0, x1, y1,0x000000)

# 线段是否相交

def IsRectCross(p1x, p1y, p2x, p2y, q1x, q1y, q2x, q2y):

    return min(p1x,p2x) <= max(q1x,q2x) and min(q1x,q2x) <= max(p1x,p2x) and min(p1y,p2y) <= max(q1y,q2y) and min(q1y,q2y) <= max(p1y,p2y)

def IsLineSegmentCross(pFirst1x,pFirst1y,pFirst2x,pFirst2y,pSecond1x,pSecond1y,pSecond2x,pSecond2y):

    line1 = pFirst1x * (pSecond1y - pFirst2y) + pFirst2x * (pFirst1y - pSecond1y) + pSecond1x * (pFirst2y - pFirst1y)

    line2 = pFirst1x * (pSecond2y - pFirst2y) + pFirst2x * (pFirst1y - pSecond2y) + pSecond2x * (pFirst2y - pFirst1y)

    if (((line1 ^ line2) >= 0) and not (line1 == 0 and line2 == 0)):

        return False

    line1 = pSecond1x * (pFirst1y - pSecond2y) + pSecond2x * (pSecond1y - pFirst1y) + pFirst1x * (pSecond2y - pSecond1y)

    line2 = pSecond1x * (pFirst2y - pSecond2y) + pSecond2x * (pSecond1y - pFirst2y) + pFirst2x * (pSecond2y - pSecond1y)

    if (((line1 ^ line2) >= 0) and not (line1 == 0 and line2 == 0)):

        return False

    return True

def GetCrossPoint(p1x, p1y, p2x, p2y, q1x, q1y, q2x, q2y):

    if(IsRectCross(p1x, p1y, p2x, p2y, q1x, q1y, q2x, q2y)):

        if (IsLineSegmentCross(p1x, p1y, p2x, p2y, q1x, q1y, q2x, q2y)):

            tmpLeft = (q2x - q1x) * (p1y - p2y) - (p2x - p1x) * (q1y - q2y)

            tmpRight = (p1y - q1y) * (p2x - p1x) * (q2x - q1x) + q1x * (q2y - q1y) * (p2x - p1x) - p1x * (p2y - p1y) * (q2x - q1x)

            if (tmpLeft == 0):

                return None

            x = (int)(tmpRight/tmpLeft)

            tmpLeft = (p1x - p2x) * (q2y - q1y) - (p2y - p1y) * (q1x - q2x)

            tmpRight = p2y * (p1x - p2x) * (q2y - q1y) + (q2x- p2x) * (q2y - q1y) * (p1y - p2y) - q2y * (q1x - q2x) * (p2y - p1y)

            if (tmpLeft == 0):

                return None

            y = (int)(tmpRight/tmpLeft)

            return (x,y)

        else:

            return None

    else:

        return None

def draw_rectangle_black(x0, y0, x1, y1):

    bresenham(x0, y0, x1, y0,0x000000)

    bresenham(x1, y0, x1, y1,0x000000)

    bresenham(x1, y1, x0, y1,0x000000)

    bresenham(x0, y1, x0, y0,0x000000)

# 判断点是否在多边形内

def IsPointInPolygon(points, x, y):

    nCross = 0

    for i in range(len(points)):

        p1x = points[i][0]

        p1y = points[i][1]

        p2x = points[(i + 1) % len(points)][0]

        p2y = points[(i + 1) % len(points)][1]

        if (y > min(p1y, p2y)):

            if (y <= max(p1y, p2y)):

                if (x <= max(p1x, p2x)):

                    if (p1y != p2y):

                        xinters = (y - p1y) * (p2x - p1x) / (p2y - p1y) + p1x

                    if (p1x == p2x or x <= xinters):

                        nCross += 1

    if (nCross % 2 == 0):

        return False

    else:

        return True

def getNonRepeatList(data):

    new_data = []

    for i in range(len(data)):

        if data[i] not in new_data:

            new_data.append(data[i])

    return new_data

# 判断两多边形重叠部分 返回一个多边形

def IsPolygonCross(points1, points2):

    result = []

    for i in range(len(points1)):

        p1x = points1[i][0]

        p1y = points1[i][1]

        p2x = points1[(i + 1) % len(points1)][0]

        p2y = points1[(i + 1) % len(points1)][1]

        for j in range(len(points2)):

            q1x = points2[j][0]

            q1y = points2[j][1]

            q2x = points2[(j + 1) % len(points2)][0]

            q2y = points2[(j + 1) % len(points2)][1]

            if (IsPointInPolygon(points1, q1x, q1y) and (q1x, q1y) not in result):

                result.append((q1x, q1y))

            if (IsPointInPolygon(points1, q2x, q2y) and (q2x, q2y) not in result):

                result.append((q2x, q2y))

            if (IsPointInPolygon(points2, p1x, p1y) and (p1x, p1y) not in result):

                result.append((p1x, p1y))

            if (IsPointInPolygon(points2, p2x, p2y) and (p2x, p2y) not in result):

                result.append((p2x, p2y))

            if (IsRectCross(p1x, p1y, p2x, p2y, q1x, q1y, q2x, q2y)):

                if  GetCrossPoint(p1x, p1y, p2x, p2y, q1x, q1y, q2x, q2y) != None:

                    (x, y) = GetCrossPoint(p1x, p1y, p2x, p2y, q1x, q1y, q2x, q2y)

                    result.append((x, y))

    if (result == []):

        return result

    return (sort_points_in_clockwise_order(result))

w = 60

h = 100

def draw_polygon_red(points):

    for i in range(len(points)):

        x0 = points[i][0]

        y0 = points[i][1]

        x1 = points[(i + 1) % len(points)][0]

        y1 = points[(i + 1) % len(points)][1]

        bresenham(x0, y0, x1, y1,0xff0000)

def sort_points_in_clockwise_order(points):

    center = (0, 0)

    for point in points:

        center = (center[0] + point[0], center[1] + point[1])

    center = (center[0] / len(points), center[1] / len(points))

    points_copy = list(points)

    points_copy.sort(key=lambda point: math.atan2(point[0] - center[0], point[1] - center[1]))

    res = []

    for i in points_copy:

       res.append((i[0]+500,i[1]))

    return res

polygon_Points = [(600,500), (800,500), (900, 600), (900, 400),(600,300)]

while True:

    draw_rectangle_black(temp[0],temp[1],temp[0]+w,temp[1]+h)

    draw_rectangle(mouse_x,mouse_y,mouse_x+w,mouse_y+h)

    temp = (mouse_x,mouse_y)

    get_mouse_pos()

    draw_polygon(polygon_Points)

    res =  IsPolygonCross(polygon_Points,[(mouse_x,mouse_y),(mouse_x+w,mouse_y),(mouse_x+w,mouse_y+h),(mouse_x,mouse_y+h)])

    print(res)

    if temp2 != []:

        draw_polygon_black(temp2)

    if res != [] and res != None:

        draw_polygon_red(res)

        temp2 = res

    clock.tick(120)# 60帧

总结

计算机图形学并没有我之前想的那么好学，踩了很多坑，也补了很多知识。希望后面能再接再厉