[toc] 之前有记录过 GPU 硬件相关的知识，现在学习一下 ComputeShader.

# ComputeShader 线程组概念

首先，编写 ComputeShader 时需要我们指定核函数，即 #pragma kernel 名字 ，核函数的构造一般如下:

#pragma kernel Circles

[numthreads(8,8,1)]
void Circles (uint3 id : SV_DispatchThreadID)
{
    int2 center = (texResolution >> 1);
    int radius = 80;
    drawCircle(center,radius);
}

如上所示，kernel 函数需要一个分配线程组的声明 [numthreads] ，其中三维便是一个线程组内的线程数量，如上述函数一个线程组内的线程数量是 (8*8*1) = 64 个，即一次计算会有 64 个线程同时进行。
而每次进行并发计算时，还会存在一个名叫线程 Id 的标识，如上述函数中的入参 id 就是所谓的线程 Id, 它也是 xyz 三维的一个下标标识符

x: 线程组的列数
y: 线程组的行数
z: 线程组的深度

每次进入核函数进行运算时线程 Id 就是通过上述三个变量确定的，以及对应的线程组。如上图，实际的 DispatchId 和 ThreadId 的映射公式如下：线程组大小 [10,8,3]
1. SV_GroupThreadID : (7,5,0) 目标组内 Id 2. SV_GroupID : (2,1,0) 目标组 3. SV_DispatchThreadID : ([(2,1,0)*(10,8,3)] + (7,5,0)) = (27,13,0) 对应的线程 ID
4. SV_GroupIndex : 0*10*8+5*10+7=57 组内一维下的坐标

附: 3.2 可以简单理解为：目标线程 ID = (SV_GroupID * 线程组大小) + 组内 Id

# 举个栗子：使用线程组填充图片

由上面的讨论，我们可以知道，对于每个核函数而言，存在一个下标索引 ID, 同时线程组内核的数量也对应着并发的数量，而图片是二维的，如果我们需要使每个算子计算每个图片上的像素，则只需要让线程 Id 和像素坐标匹配上就可以了。比如我们有一个 256*256 的图片，我们的核函数可以这样写:

// Each #kernel tells which function to compile; you can have many kernels
#pragma kernel CSMain

// Create a RenderTexture with enableRandomWrite flag and set it
// with cs.SetTexture
RWTexture2D<float4> Result;
int kernelCount;
int x,y;

[numthreads(8,8,1)]
void CSMain (uint3 id : SV_DispatchThreadID)
{
    // TODO: insert actual code here!

    //Result[id.xy] = float4(id.x & id.y, (id.x & 15)/15.0, (id.y & 15)/15.0, 0.0);

    float AS = kernelCount  *1.0;
    float res = (id.x * id.y) /(AS*AS);
    Result[id.xy] = float4(x/16.0,y/16.0,1 , 1.0);
}

即每个线程组是 8x8x1 大小的，深度始终保持为 1, 就可以让三维降低为二维。相应的，我们需要在 Dispatch 时根据核函数的大小来确定我们分配的组的 Id (不能大于图片的大小) 比如在图片大小为 256*256
线程并发度为 8*8*1 的条件下每个 ThreadGroup 可以在 texture 上绘制的范围就是 8*8
GroupId 变化时:
X 每 + 1, 横向扩展 8 像素
Y 每 + 1, 纵向扩展 8 像素即 X/Y 的 ID 上限为 256/8 验证:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AssignTexture : MonoBehaviour
{
    public ComputeShader shader;

    public int texResolution = 256;

    private Renderer rend;

    private RenderTexture outputTexture;

    private int kernelHandle;

    private int X, Y;

    // Start is called before the first frame update
    void Start()
    {
        outputTexture = new RenderTexture( texResolution, texResolution,0);
        outputTexture.enableRandomWrite = true;
        outputTexture.Create();
        X = 1; 
        Y = 1;
        rend = GetComponent<Renderer>();
        rend.enabled = true;

        InitShader();
    }

    private void InitShader()
    {
        kernelHandle = shader.FindKernel("CSMain");
        shader.SetTexture(kernelHandle,"Result",outputTexture);
        shader.SetInt("kernelCount",(int)texResolution);
        rend.material.SetTexture("_MainTex",outputTexture);

        DispatchShader();
    }

    private void DispatchShader()
    {
        shader.SetInt("x",(int)X);
        shader.SetInt("y",(int)Y);
        shader.Dispatch(kernelHandle,X,Y,1);
    }

    // Update is called once per frame
    void Update()
    {
        if (Input.GetKeyUp(KeyCode.X))
        {
            X++;
            DispatchShader();
        }

        if (Input.GetKeyUp(KeyCode.Y))
        {
            Y++;
            DispatchShader();
        }

        if (Input.GetKeyUp(KeyCode.Z))
        {
            X--;
            if (X <= 0) X = 1;
            DispatchShader();
        }
        if (Input.GetKeyUp(KeyCode.T))
        {
            Y--;
            if (Y <= 0) Y = 1;
            DispatchShader();
        }
    }


}

结果: 每个线程组实际上画的区域是这么一点 (8*8):

# 并发画圆算法 (Bresenhaman 画圆算法)

考虑一个有趣的事情，既然我们可以使用 ComputeShader 在图上画东西了，那么很自然也可以画圆，比如一个最暴力的方法就是并发整个图的像素，然后判断每个像素是否在圆的边界上，且需要着色
但是这样就失去了使用 ComputeShader 的并发优势，且无效计算很多，所以最好的情况是我们可以并发的将圆周画出来，如何实现呢？如上图，我们可以适当将圆划分为 N 等分弧，
每次并发 N 个线程，填充对应区域的一个点，并发次数越多，对应区域填充的点越多
或者并发 M 次，每个线程填充 N 个区域
当一个弧画完时，一个圆就画完了这里我们使用 Bresenham 画圆算法，伪代码如下 (我翻了好几个文章，发现他们最终得到的关于 d 的公式都不太一样，但是都能画出圆 XD, 下面只是其中一个我觉得写的比较好的伪代码):
上述代码看起来很简单，实现起来也很简单，根据伪代码实现的核函数如下:

void plot1(int x,int y,int2 center)
{
    Result[uint2(center.x + x,center.y + y)] = circleColor;
}

void plot8(int x,int y,int2 center)
{
    plot1(x,y,center); plot1(y,x,center);
    plot1(x,-y,center); plot1(y,-x,center);
    plot1(-x,-y,center); plot1(-y,-x,center);
    plot1(-x,y,center); plot1(-y,x,center);
}

void drawCircle(int2 center,int radius)
{
    int x = 0;
    int y = radius;
    int d = 1 - radius;

    while(x<y)
    {
        if(d < 0)
        {
            d += 4*x + 6;
        }else
        {
            d += 4*(x-y) + 10;
            y--;
        }

        plot8(x,y,center);
        x++;
    }
}

[numthreads(1,1,1)]
void Circles (uint3 id : SV_DispatchThreadID)
{
    int2 center = (texResolution >> 1);
    int radius = 80;
    drawCircle(center,radius);
}

但是这段代码隐藏了一个巨大的细节，就是 d 到底是什么，

# Bresenham 画圆算法解析

如上图：对于每一个 x 对应的 y , 和上一个圆周上像素的关系有两种可能
1. y 轴和上一个像素一样

在上一个像素的右下角

y 与 x 的关系可以用一个公式表达那么，我们在累加 X 的时候如何确定下一个 Y 点是在右侧还是右下角呢？
显而易见，如果像素单位为 1, (y(x+1)-y(x) < 0.5) 的时候，选择右侧，大于的时候，选择右下角所以我们提出一个误差值 d 的概念:
1. 像素 y,X+1 距离圆周上的边的距离

2. y-1,X+1 距离圆周上的边的距离
误差值 d = 条件 1 + 条件 2, 得到一个递归式再借助每次下一个只有 y 或者 y-1 这连个像素可以选择的条件知:
1. di<0 时，选择右侧像素，此时 Y_(i+1) = Yi, 代入原式得: