48-背面剔除算法与代码实现

剔除算法

目的：提前丢弃对最终画面无贡献的三角形，减少不必要的渲染计算

OpenGL中，系统API允许设置三角形剔除：
1、设置“正面”三角形的顶点连接方式（顺时针/逆时针）
2、设置剔除“正面”还是剔除“背面”

举例：
顶点逆时针连接维正面/剔除背面

左手坐标系问题
在NDC坐标中，已经变成了采用左手坐标系表示
在左手坐标系中，向量叉乘必须采用左手来判定叉乘结果向量方向，例如：x与y叉乘，得到z

判定算法

举例：逆时针为正面，剔除背面
以0点为起点，与1点/2点构成两条边e1/e2
求两向量叉乘，e1叉乘e2（左手坐标系）
叉乘结果冲向屏幕内部，左手坐标系下，为z正方向，即z>0
则使用z>0可判定该三角形可保留

若如下图，顺时针排列顶点，e1与e2叉乘得到z<0，则可判定剔除该三角形

总结

以0点为起点，与1点/2点构成两条边e1/e2；
计算e1与e2叉乘，得到其结果z值
分条件判定：
1、剪裁背面/逆时针为正面: z>0 保留
2、剪裁正面/逆时针为正面: z<0 保留
3、剪裁背面/顺时针为正面: z<0 保留
4、剪裁正面/顺时针为正面: z>0 保留

代码实现

内容：
1、GPU中增加cull相关状态，增加状态修改接口
2、Clipper中增加Cull功能
3、Draw流程中，加入cull功能
4、示例

base.h

#pragma once

#include<iostream>
#include<vector>
#include<map>
#include<cmath>
#include<assert.h>

#define PI					3.14159265358979323
#define DEG2RAD(theta)		(0.01745329251994329 * (theta))
#define FRACTION(v)			((v) - (int)(v))

using byte = unsigned char;

struct RGBA {
	byte mB;
	byte mG;
	byte mR;
	byte mA;

	RGBA(
		byte r = 255,
		byte g = 255,
		byte b = 255,
		byte a = 255)
	{
		mR = r;
		mG = g;
		mB = b;
		mA = a;
	}
};

#define ARRAY_BUFFER 0
#define ELEMENT_ARRAY_BUFFER 1

#define DRAW_LINES 0
#define DRAW_TRIANGLES 1

#define CULL_FACE 1  //开启剔除功能

#define FRONT_FACE 0 //正面
#define BACK_FACE 1  //背面
#define FRONT_FACE_CW 0  //顺时针
#define FRONT_FACE_CCW 1 //逆时针

gpu.h

class GPU {
	//... ... ...
	void enable(const uint32_t& value);

	void disable(const uint32_t& value);

	//cull face
	void frontFace(const uint32_t& value);//设置正面是逆时针还是顺时针

	void cullFace(const uint32_t& value);//设置剪裁背面还是正面
    //... ... ...
private:
    //... ... ...	
	//cull face
	bool mEnableCullFace{ true };
	uint32_t mFrontFace{ FRONT_FACE_CCW };//默认逆时针为正面
	uint32_t mCullFace{ BACK_FACE };
};

gpu.cpp

void GPU::enable(const uint32_t& value) {
	switch (value)
	{
	case CULL_FACE:
		mEnableCullFace = true;
		break;
	default:
		break;
	}
}

clipper.h

#pragma once
#include "dataStructures.h"

class Clipper {
public:
	static void doClipSpace(const uint32_t& drawMode, const std::vector<VsOutput>& primitives, std::vector<VsOutput>& outputs);

	static bool cullFace(
		const uint32_t& frontFace, //顺时针或逆时针为正面
		const uint32_t& cullFace, //剔除背面还是正面
		const VsOutput& v0, //三角形的三个顶点
		const VsOutput& v1, 
		const VsOutput& v2
	);

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

	static bool inside(const math::vec4f& point, const math::vec4f& plane);

	static VsOutput intersect(const VsOutput& last, const VsOutput& current, const math::vec4f& plane);
};

clipper.cpp

对应代码：

//... ... ...

bool Clipper::cullFace(
	const uint32_t& frontFace,
	const uint32_t& cullFace,
	const VsOutput& v0,
	const VsOutput& v1,
	const VsOutput& v2) {

	math::vec3f edge1 = v1.mPosition - v0.mPosition;//从v0点连向v1形成向量edge1
	math::vec3f edge2 = v2.mPosition - v0.mPosition;//从v0点连向v2形成向量edge2

	math::vec3f normal = math::cross(edge1, edge2);//向量叉乘，得到z

	//注意，此时NDC坐标已经位于了左手坐标系下，叉乘需要用左手来比划
	if (cullFace == BACK_FACE) {

		//在逆时针情况下,使用左手示意，z>0为front，保留
		if (frontFace == FRONT_FACE_CCW) {
			return normal.z > 0;
		}
		else {
		//在顺时针情况下,使用左手示意，z<0为front，保留
			return normal.z < 0;
		}
	}
	else {
		//在逆时针情况下,使用左手示意，z<0为back，保留
		if (frontFace == FRONT_FACE_CCW) {
			return normal.z < 0;
		}
		else {
		//在顺时针情况下,使用左手示意，z>0为back，保留
			return normal.z > 0;
		}
	}
}

主流程中增加cullFace功能

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
    }

    /*
    * 背面剔除阶段     <-----------------------------------------------------------------+
    * 作用：
    *      背向我们的三角形需要剔除
    */
	std::vector<VsOutput> cullOutputs = clipOutputs;
	if (drawMode == DRAW_TRIANGLES && mEnableCullFace) {
		cullOutputs.clear();
		for (uint32_t i = 0; i < clipOutputs.size() - 2; i += 3) {
			if (Clipper::cullFace(mFrontFace, mCullFace, clipOutputs[i], clipOutputs[i + 1], clipOutputs[i + 2])) {
				auto start = clipOutputs.begin() + i;
				auto end = clipOutputs.begin() + i + 3;
				cullOutputs.insert(cullOutputs.end(), start, end);
			}
		}
	}

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

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


    if (rasterOutputs.empty()) return;

	 /*
    * 透视恢复阶段
    * 作用：
    *      离散出来的像素插值结果，需要乘以自身的w值恢复到正常状态
    */
	for (auto& output : rasterOutputs) {
		perspectiveRecover(output);
	}

    /*
    * 颜色输出处理阶段
    * 作用：
    *      将颜色进行输出
    */
    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 = 2.0f;
void transform() {
	angle += 0.01f;
	//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);

	sgl->enable(CULL_FACE);//启动剔除功能
	sgl->frontFace(FRONT_FACE_CCW);//逆时针为正面
	sgl->cullFace(BACK_FACE);//剔除背面

	float positions[] = {
		-0.5f, 0.0f, 0.0f,
		0.5f, 0.0f, 0.0f,
		0.25f, 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;
}