45-剪裁算法代码实现

内容

1.Clipper类以及sutherlandHodgman算法
2.GPU绘制流程加入剪裁
3.绘制示例

dataStructures.h

#pragma once
#include "../global/base.h"
#include "../math/math.h"

//VAO之中，用于描述属性读取方式的Description
struct BindingDescription {
    uint32_t    mVboId{ 0 };
    size_t      mItemSize{ 0 };
    size_t      mStride{ 0 };
    size_t      mOffset{ 0 };
};

struct VsOutput {
    math::vec4f mPosition{ 0.0f, 0.0f, 0.0f, 1.0f };
    math::vec4f mColor;//此处颜色改为0.0-1.0之间表达0-255的量
    math::vec2f mUV;
};

struct FsOutput {
    math::vec2i mPixelPos;
    float mDepth;
    RGBA mColor;//此处使用0-255来进行颜色显示
};

clipper.h

对外提供静态函数，只提供功能doClipSpace

#pragma once
#include "dataStructures.h"

class Clipper {
public:
    //执行剪裁功能
    static void doClipSpace(const uint32_t& drawMode, const std::vector<VsOutput>& primitives, std::vector<VsOutput>& outputs);

private:
    //剪裁算法
    static void sutherlandHodgman(const uint32_t& drawMode, const std::vector<VsOutput>& primitive, std::vector<VsOutput>& outputs);

    //判定当前point是否在plane的正面
    static bool inside(const math::vec4f& point, const math::vec4f& plane);

    //传入last点和current点，求交点位置，颜色，uv
    static VsOutput intersect(const VsOutput& last, const VsOutput& current, const math::vec4f& plane);
};

clipper.cpp

#include "clipper.h"
#include "../math/math.h"

void Clipper::doClipSpace(const uint32_t& drawMode, const std::vector<VsOutput>& primitives, std::vector<VsOutput>& outputs) {
    //保证输出为空
    outputs.clear();

    if (drawMode == DRAW_TRIANGLES) {//对三角形进行剪裁
        std::vector<VsOutput> primitive;//可能包含多个三角形的顶点信息
        std::vector<VsOutput> results;//运行剪裁算法后得到的顶点集合

        for (uint32_t i = 0; i < primitives.size(); i += 3) {//每三个点确定一个三角形
            primitive.clear();
            results.clear();
            auto start = primitives.begin() + i;
            auto end = primitives.begin() + i + 3;
            primitive.assign(start, end);//将start到end的三个点保存到primitive中

            Clipper::sutherlandHodgman(drawMode, primitive, results);//执行剪裁算法

            if (results.empty()) {
                continue;
            }

            //进行三角形缝补（依次缝补编织三角形）
            for (uint32_t c = 0; c < results.size() - 2; ++c) {
                outputs.push_back(results[0]);
                outputs.push_back(results[c + 1]);
                outputs.push_back(results[c + 2]);
            }
        }
    }
    else if (drawMode == DRAW_LINES) {//对直线进行剪裁
        std::vector<VsOutput> primitive;
        std::vector<VsOutput> results;

        for (uint32_t i = 0; i < primitives.size(); i += 2) {
            primitive.clear();
            results.clear();
            auto start = primitives.begin() + i;
            auto end = primitives.begin() + i + 2;
            primitive.assign(start, end);
            Clipper::sutherlandHodgman(drawMode, primitive, results);

            outputs.push_back(results[0]);
            outputs.push_back(results[1]);//顶点最多只能被剪裁出两个点
        }
    }
}


void Clipper::sutherlandHodgman(const uint32_t& drawMode, const std::vector<VsOutput>& primitive, std::vector<VsOutput>& outputs) {
    assert(outputs.size() == 0);

    std::vector<math::vec4f> clipPlanes = {//代表7个剪裁平面
        //judge w > 0
        math::vec4f(0.0f, 0.0f, 0.0f, 1.0f),
        //near
        math::vec4f(0.0f, 0.0f, 1.0f, 1.0f),
        //far
        math::vec4f(0.0f, 0.0f, -1.0f, 1.0f),
        //left
        math::vec4f(1.0f, 0.0f, 0.0f, 1.0f),
        //right
        math::vec4f(-1.0f, 0.0f, 0.0f, 1.0f),
        //top
        math::vec4f(0.0f, -1.0f, 0.0f, 1.0f),
        //bottom
        math::vec4f(0.0f, 1.0f, 0.0f, 1.0f)
    };

    //Sutherland-Hodgman algorithm
    outputs = primitive;//获取输入的点（启下）
    std::vector<VsOutput> inputs;

    //遍历每一个平面进行检查
    for (uint32_t i = 0; i < clipPlanes.size(); ++i) {
        //用上一次的输出作为输入点集
        inputs = outputs;//用inputs中的点来进行测试（承上）
        outputs.clear();

        //遍历输入的每一个点
        for (uint32_t p = 0; p < inputs.size(); ++p) {
            //取出点P
            auto current = inputs[p];
            //取出点S（如：p=5,s=(5+10-1)%10=4）
            auto last = inputs[(p + inputs.size() - 1) % inputs.size()];

            //1 判定P点在内部,即3/4情况（s和p都在内侧，或p在内侧s在外侧）
            if (inside(current.mPosition, clipPlanes[i])) {
                //这里加了限制因素，线条如果到了最后一个顶点，不准回头计算交点
                if (drawMode != DRAW_LINES || p != inputs.size() - 1) {

                    //2 判定S点不在内部，情况3
                    if (!inside(last.mPosition, clipPlanes[i])) {
                        //求交点I
                        auto intersectPoint = intersect(last, current, clipPlanes[i]);

                        //按照情况3输出I
                        outputs.push_back(intersectPoint);
                    }
                }
                
                //P点只要在内部，都会输出（情况3/4）
                outputs.push_back(current);
            }
            //P点不在内部，即1/2情况
            else {
                // 这里加了限制因素，线条如果到了最后一个顶点，不准回头计算交点
                if (drawMode != DRAW_LINES || p != inputs.size() - 1) {

                    //S点在内部,情况2,输出交点I
                    if (inside(last.mPosition, clipPlanes[i])) {
                        auto intersectPoint = intersect(last, current, clipPlanes[i]);
                        outputs.push_back(intersectPoint);
                    }
                }

                //S点不在内部，情况1，无输出
                
            }
        }
    }
}

//判定点是否在平面内侧
bool Clipper::inside(const math::vec4f& point, const math::vec4f& plane) {
    return math::dot(point, plane) >= 0.0f;
}

//注意，这里只能插值位于平面两侧的点
VsOutput Clipper::intersect(const VsOutput& last, const VsOutput& current, const math::vec4f& plane) {
    VsOutput output;

    //代入平面方程，求取有向距离
    float distanceLast = math::dot(last.mPosition, plane);
    float distanceCurrent = math::dot(current.mPosition, plane);

    //计算权重（平面两边distanceLast与distanceCurrent异号）
    float weight = distanceLast / (distanceLast - distanceCurrent);

    //根据权重进行线性插值
    output.mPosition = math::lerp(last.mPosition, current.mPosition, weight);
    output.mColor = math::lerp(last.mColor, current.mColor, weight);
    output.mUV = math::lerp(last.mUV, current.mUV, weight);

    return output;
}

添加限制if (drawMode != DRAW_LINES || p != inputs.size() - 1)的原因

如果是画线，且P点是数组中的最后一个，就不要在结果数组output中写入相交点I了，防止重复

出现这个bug主要是因为该剪裁算法对于非封闭图形剪裁导致的，但是对于像三角形这样的封闭图形剪裁就没有问题

gpu.cpp中引入剪裁处理

void GPU::drawElement(const uint32_t& drawMode, const uint32_t& first, const uint32_t& count) {
    if (mCurrentVAO == 0 || mShader == nullptr || count == 0) {
        return;
    }

    //1 get vao
    auto vaoIter = mVaoMap.find(mCurrentVAO);
    if (vaoIter == mVaoMap.end()) {
        std::cerr << "Error: current vao is invalid!" << std::endl;
        return;
    }

    const VertexArrayObject* vao = vaoIter->second;
    auto bindingMap = vao->getBindingMap();

    //2 get ebo
    auto eboIter = mBufferMap.find(mCurrentEBO);
    if (eboIter == mBufferMap.end()) {
        std::cerr << "Error: current ebo is invalid!" << std::endl;
        return;
    }

    const BufferObject* ebo = eboIter->second;

    /*
    * VertexShader处理阶段
    * 作用：
    *      按照输入的EBO的index顺序来处理顶点，
    *      依次通过vsShader得到的输出结果按序放入vsOutputs中
    */
    std::vector<VsOutput> vsOutputs{};
    vertexShaderStage(vsOutputs, vao, ebo, first, count);

    if (vsOutputs.empty()) return;

    /*
    * Clip Space剪裁处理阶段
    * 作用：
    *      在剪裁空间，对所有输出的图元进行剪裁拼接等
    *      后面的处理阶段都使用剪裁结果clipOutputs来处理
    */
    std::vector<VsOutput> clipOutputs{};
    Clipper::doClipSpace(drawMode, vsOutputs, clipOutputs);
    if (clipOutputs.empty()) return;

    vsOutputs.clear();

    /*
    * NDC处理阶段
    * 作用：
    *      将顶点转化到NDC下
    */
    for (auto& output : clipOutputs) {
        perspectiveDivision(output);//透视除法,除以W
    }

    /*
    * 屏幕映射处理阶段
    * 作用：
    *      将NDC下的点通过screenMatrix，转换到屏幕空间
    */
    for (auto& output : clipOutputs) {
        screenMapping(output);
    }

    /*
    * 光栅化处理阶段
    * 作用：
    *      离散出所有需要的Fragment
    */
    std::vector<VsOutput> rasterOutputs;
    Raster::rasterize(rasterOutputs, drawMode, clipOutputs);


    if (rasterOutputs.empty()) return;

    /*
    * 颜色输出处理阶段
    * 作用：
    *      将颜色进行输出
    */
    FsOutput fsOutput;
    uint32_t pixelPos = 0;
    for (uint32_t i = 0; i < rasterOutputs.size(); ++i) {
        mShader->fragmentShader(rasterOutputs[i], fsOutput);
        pixelPos = fsOutput.mPixelPos.y * mFrameBuffer->mWidth + fsOutput.mPixelPos.x;
        mFrameBuffer->mColorBuffer[pixelPos] = fsOutput.mColor;
    }
}

绘制示例

uint32_t WIDTH = 800;
uint32_t HEIGHT = 600;

//三个属性对应vbo
uint32_t positionVbo = 0;
uint32_t colorVbo = 0;
uint32_t uvVbo = 0;

//三角形的indices
uint32_t ebo = 0;

//本三角形专属vao
uint32_t vao = 0;

//使用的Shader
DefaultShader* shader = nullptr;

//mvp变换矩阵
math::mat4f modelMatrix;
math::mat4f viewMatrix;
math::mat4f perspectiveMatrix;

float angle = 0.0f;
float cameraZ = 3;
void transform() {
    angle += 0.1f;
    cameraZ -= 0.01f;

    //模型变换
    modelMatrix = math::rotate(math::mat4f(1.0f), angle, math::vec3f{ 0.0f, 1.0f, 0.0f });

    //视图变换
    auto cameraModelMatrix = math::translate(math::mat4f(1.0f), math::vec3f{ 0.0f, 0.0f, cameraZ });
    viewMatrix = math::inverse(cameraModelMatrix);
}

void render() {
    transform();
    shader->mModelMatrix = modelMatrix;
    shader->mViewMatrix = viewMatrix;
    shader->mProjectionMatrix = perspectiveMatrix;

    sgl->clear();
    sgl->useProgram(shader);
    sgl->bindVertexArray(vao);
    sgl->bindBuffer(ELEMENT_ARRAY_BUFFER, ebo);
    sgl->drawElement(DRAW_TRIANGLES, 0, 3);
}

void prepare() {
    shader = new DefaultShader();

    perspectiveMatrix = math::perspective(60.0f, (float)WIDTH / (float)HEIGHT, 0.1f, 100.0f);

    auto cameraModelMatrix = math::translate(math::mat4f(1.0f), math::vec3f{ 0.0f, 0.0f, cameraZ });
    viewMatrix = math::inverse(cameraModelMatrix);

    float positions[] = {
        -0.5f, -0.5f, 0.0f,
        -0.5f, 0.5f, 0.0f,
        0.5f, -0.5f, 0.0f,
    };

    float colors[] = {
        1.0f, 0.0f, 0.0f, 1.0f,
        0.0f, 1.0f, 0.0f, 1.0f,
        0.0f, 0.0f, 1.0f, 1.0f,
    };

    float uvs[] = {
        0.0f, 0.0f,
        0.0f, 1.0f,
        1.0f, 0.0f,
    };

    uint32_t indices[] = { 0, 1, 2 };

    //生成indices对应ebo
    ebo = sgl->genBuffer();
    sgl->bindBuffer(ELEMENT_ARRAY_BUFFER, ebo);
    sgl->bufferData(ELEMENT_ARRAY_BUFFER, sizeof(uint32_t) * 3, indices);
    sgl->bindBuffer(ELEMENT_ARRAY_BUFFER, 0);

    //生成vao并且绑定
    vao = sgl->genVertexArray();
    sgl->bindVertexArray(vao);
    
    //生成每个vbo，绑定后，设置属性ID及读取参数
    auto positionVbo = sgl->genBuffer();
    sgl->bindBuffer(ARRAY_BUFFER, positionVbo);
    sgl->bufferData(ARRAY_BUFFER, sizeof(float) * 9, positions);
    sgl->vertexAttributePointer(0, 3, 3 * sizeof(float), 0);

    auto colorVbo = sgl->genBuffer();
    sgl->bindBuffer(ARRAY_BUFFER, colorVbo);
    sgl->bufferData(ARRAY_BUFFER, sizeof(float) * 12, colors);
    sgl->vertexAttributePointer(1, 4, 4 * sizeof(float), 0);

    auto uvVbo = sgl->genBuffer();
    sgl->bindBuffer(ARRAY_BUFFER, uvVbo);
    sgl->bufferData(ARRAY_BUFFER, sizeof(float) * 6, uvs);
    sgl->vertexAttributePointer(2, 2, 2 * sizeof(float), 0);

    sgl->bindBuffer(ARRAY_BUFFER, 0);
    sgl->bindVertexArray(0);
}

int APIENTRY wWinMain(
    _In_ HINSTANCE hInstance,       //本应用程序实例句柄，唯一指代当前程序
    _In_opt_ HINSTANCE hPrevInstance,   //本程序前一个实例，一般是null
    _In_ LPWSTR    lpCmdLine,       //应用程序运行参数
    _In_ int       nCmdShow)        //窗口如何显示（最大化、最小化、隐藏），不需理会
{
    if (!app->initApplication(hInstance, WIDTH, HEIGHT)) {
        return -1;
    }

    //将bmp指向的内存配置到sgl当中 
    sgl->initSurface(app->getWidth(), app->getHeight(), app->getCanvas());

    prepare();

    bool alive = true;
    while (alive) {
        alive = app->peekMessage();
        render();
        app->show();
    }

    delete shader;

    return 0;
}