Coherent Occlusion Culling(CHC)演算法的原理與實現
CHC演算法是Jiˇrí Bittner在2004年提出的一種遮擋剔除的演算法，其中主要運用到了渲染的（Temporal coherence）時間相干性以及（Spatial coherence）空間相干性，同時運用BVH（Bounding Volume Hirachical）管理場景並且通過基於硬體的遮擋查詢對遮擋物進行剔除，提高渲染速度。
演算法背景
Hardware Occlusion Culling
CHC演算法主要建立在基於硬體的遮擋查詢（Hardware Occlusion Culling）的基礎上。Hardware Occlusion Culling基於一個十分簡單的思想，在判斷物體是否被遮擋時，將物體的深度值傳遞給GPU，GPU將自己現存的最低的深度值與物體的深度值進行對比，並返回查詢結果（可見像素點個數）。
優點
- API簡單易用，不需要額外管理信息，能迅速集成進現有系統
- 基於GPU進行判斷，效率高，充分挖掘GPU性能
存在問題
- 基於GPU的判斷效率高，但涉及數據傳輸，在大規模場景下會造成CPU一直等待GPU查詢結果返回造成GPU性能飢餓的情況
- 雖然基於GPU判斷效率高，不過在複雜場景下仍有大量渲染目標需要被測試，仍有提升空間
Coherent Occlusion Culling（CHC）
目標
- 減少進行遮擋查詢的次數
- 避免CPU出現瓶頸而GPU飢餓的情況
演算法核心
- 利用BVH（Bounding Volume Hirachical）管理場景，並利用Spatial Coherence（空間相關性）減少每一幀需要進行遮擋查詢的次數。
- 重用上一幀的查詢結果，利用Time Coherence（時間相關性）進一步減少查詢次數
- 維護一個查詢隊列，延遲進行查詢的時間，並利用渲染部分場景的時間來填充CPU等待GPU查詢結果返回的時間，減少GPU的飢餓。
演算法介紹
Spatial Coherence
在實際的渲染過程中，一個渲染場景通常會有大量物體，如果將他們都渲染出來會對GPU造成極大的性能負擔，所以需要對看不見的物體從渲染隊列中剔除。例如View Frustum Culling演算法：只渲染在視角範圍內的物體。而對於一個複雜場景來說，經過View Frustum裁剪過後的物體對於渲染管線仍有很大壓力。
而對於CHC演算法的基礎Hardware Occlusion Culling演算法來說，對每一個物體都進行一次查詢仍然是難以負擔的任務。為了減少進行查詢的次數，CHC演算法的作者採用了一種層次化管理場景(BVH)的方法。將場景中的物體基於空間信息利用樹狀結構進行管理，相鄰的物體存在於葉節點中。
(圖片來源Wikipedia)
如圖所示，場景中一共有6個物體，而樹狀結構一共有4個內部節點，每個物體都被它的父節點包圍，每個內部節點也被它的父節點包圍。
演算法流程如下：在渲染開始時會從根節點依次往下遍歷，並利用Hardware Occlusion Culling的方法檢測節點包圍盒對於當前場景是否可見，如果可見則遍歷子節點直至葉節點。如不可見則證明該包圍盒下所有節點都不可見，則跳過該節點繼續遍歷。
如上圖，從根節點A開始遍歷，發現右下角部分可視，則遍歷子節點B與C。對於B節點的可見性測試失敗，則跳過B節點的所有子節點，開始遍歷C節點，直至遍歷到葉節點開始渲染。
從上面例子中可以見到，通過這樣一個場景管理的方法能夠很有效的減少對於物體級別的操作次數。
Tips
在實際的遮擋物檢測中，必須注意到物體渲染先後次數的問題。Hardware Occlusion Culling是將待查詢物體的深度與屏幕緩存中現有物體深度進行比較，考慮物體A被物體B擋在後面，完全不可見。但遍歷樹時首先遍歷到物體A，這是物體B還沒有被渲染，那麼物體A的可見性測試將是True。所以使用BVH結合Occlusion Culling是必須考慮以從前往後的方式遍歷樹結構。在《Phisical Based Rendering》P297頁介紹了一種成本很低的從前往後遍歷的方法。具體實現見下方
Time Coherence
即使利用了BVH管理場景，場景中仍具有大量待查詢的物體。CHC演算法的作者繼續採用了一種假設的方法去消除一部分查詢。
CHC演算法將樹內部的節點分為Open Node與Terminal Node（下文以O與T表示）。O是指上一幀可見的非葉節點。除此之外都是T（也就是上一幀不可見的節點或者是所有葉節點）。實際代碼中是這樣判斷的：
//Is visible in last frame?
bool wasVisible = curNode->visible && (curNode->lastVisited == frameID - 1);
//Is leaf node?
bool opened = wasVisible && !curNode->isLeaf;
在渲染的第一幀初始化兩類節點的值，從第二幀的遍歷開始，如果遇到O，則假設它這一幀能夠被看到，初始化查詢加入查詢隊列，但不等待查詢結果返回就直接發出渲染命令，同時將可見性設為false。同時在每一次遍歷新節點是查看隊列中的查詢結果，如果未返回則繼續遍歷，如果返回則處理查詢結果並設置相應的可見性。
如果遇到T，初始化查詢，並且阻塞到查詢結果返回。
CHC演算法的秘訣：
- 遍歷時跳過所有O的可見度測試並默認通過，同時將其可見屬性設為false，根據它的子葉節點的可見度測試結果重置它的可見屬性。這種方法的作用是顯而易見的，它有效的減少了執行可見度測試的次數，而他帶來的影響：
假設上一幀可見的物體這一幀也可見：對於物體（葉節點）來說，在初始化查詢後不等待其可見還是不可見的結果就立即發出渲染命令。這個假設第一不會影響到場景的正確性，因為所有的物體都會執行深度測試再次被裁剪。第二，初始化查詢時將可見性設為false，這樣在處理查詢結果時也根據查詢結果對這個節點以及其父節點賦予O或是T的屬性從而影響到下一幀，也就是他的誤差率是±1幀。
- 讓CPU執行樹的遍歷與GPU執行可見性測試交錯執行，這樣能夠有效的消除CPU的性能瓶頸以及GPU的飢餓。
CHC演算法的流程圖：
while(true){
//PART 1:Query and process finished queries
while (!queryQueue.empty()|| doneTravel == true) {
if (!queryQueue.empty()&& resultAvailable(queryQueue.front())) {
//Previous invisible is ready
//······
}
else if (!queryQueueForNextFrame.empty()&& resultAvailable(queryQueueForNextFrame.front())) {
//previous visible is ready
//······
}
if (queryQueue.empty() && queryQueueForNextFrame.empty()) break;
}
//PART 2:Check if the algorithm is done
if (queryQueue.empty() && queryQueueForNextFrame.empty() && doneTravel)
break;
//PART 3:traversal
curNode = &root[curVisitOffset];
bool wasVisible = curNode->visible && (curNode->lastVisited == frameID - 1);
bool opened = wasVisible && !curNode->isLeaf;
curNode->visible = false;
curNode->lastVisited = frameID;
if (!opened) {
issueOcculusionQuery(curNode,true);
wasVisible ? queryQueueForNextFrame.push(curNode) : queryQueue.push(curNode);
}
if (wasVisible)
traversalNode(curNode, curVisitOffset, toVisit);
if (curNode->isLeaf) {
//Travel in front-to-back order
if (!toVisit.empty()) {
curVisitOffset = toVisit.top();
toVisit.pop();
} else {
doneTravel = true;
curVisitOffset = 0;
}
}
}
如圖
這樣，1.減少可見性查詢的次數；2.消除CPU的性能瓶頸以及GPU的飢餓；兩個目的就達到了~
演算法實現
（關於BVH演算法，《Phisical Based Rendering》P255-P308頁有詳細介紹，我的代碼也是基於它實現的，讀者可以自行查找或下載我的源代碼）
（我是將CHC演算法用於VR引擎，會有左右眼渲染兩次，所以有些時候會進行兩次可見性測試，讀者實驗時可以刪去多餘代碼）
定義變數
//All of the objects
Objects = gIsLeft? leftBvhAccel->getOrderedMesh():rightBvhAccel->getOrderedMesh();
//For occlusion query(Terminal Node)
std::queue<LinearBVHNode*> queryQueue;
//For occlusion query(Open Node)
std::queue<LinearBVHNode*> queryQueueForNextFrame;
//For travel in front-back order
int curVisitOffset = 0;
std::stack<int> toVisit;
//For travel
LinearBVHNode* curNode;
LinearBVHNode* root = gIsLeft ? leftBvhAccel->getLinearNodes() : rightBvhAccel->getLinearNodes();
//Judge the travel is done
bool doneTravel = false;
循環主體
while(true){
//PART 1:Query and process finished queries
while (!queryQueue.empty()|| doneTravel == true) {
//······
}
//PART 2:Check if the algorithm is done
if (queryQueue.empty() && queryQueueForNextFrame.empty() && doneTravel)
break;
//PART 3:traversal
//······
}
PART 1:Query and process finished queries
while (!queryQueue.empty()|| doneTravel == true) {
if (!queryQueue.empty()&& resultAvailable(queryQueue.front())) {
//Previous invisible is ready
//······
}
else if (!queryQueueForNextFrame.empty()&& resultAvailable(queryQueueForNextFrame.front())) {
//previous visible is ready
//······
}
if (queryQueue.empty() && queryQueueForNextFrame.empty()) break;
}
Previous invisible is ready
if (!queryQueue.empty()&& resultAvailable(queryQueue.front())) {
//Previous invisible is ready
curNode = queryQueue.front();
queryQueue.pop();
//If it is visible
if (getOcculusionResult(curNode) > 1) {
traversalNode(curNode, curVisitOffset, toVisit);
pullUpVisibility(root, curNode);
glDeleteQueriesARB(1, &curNode->queryID);
} else {
//If it is not visible,query for the other eyes
//It is only for VR!
issueOcculusionQuery(curNode, false);
if (getOcculusionResult(curNode) > 1) {
//If the target is visible
traversalNode(curNode, curVisitOffset, toVisit);
//Set its visible property as same as its parent
pullUpVisibility(root, curNode);
glDeleteQueriesARB(1, &curNode->queryID);
}
else {
//The target is not visible
if (toVisit.empty() && curVisitOffset == 0) {
doneTravel = true;
break;
} else if (toVisit.empty() && !curNode->isLeaf) {
//the last invisible node
doneTravel = true;
break;
} else if (!curNode->isLeaf) {
//invisible node
curVisitOffset = toVisit.top();
toVisit.pop();
}
}
}
}
Previous visible is ready
else if (!queryQueueForNextFrame.empty()&& resultAvailable(queryQueueForNextFrame.front())) {
//previous visible is ready
curNode = queryQueueForNextFrame.front();
queryQueueForNextFrame.pop();
if (getOcculusionResult(curNode) > 1) {
pullUpVisibility(root, curNode);
glDeleteQueriesARB(1, &curNode->queryID);
}
else {
issueOcculusionQuery(curNode, false);
if (getOcculusionResult(curNode) > 1) {
pullUpVisibility(root, curNode);
glDeleteQueriesARB(1, &curNode->queryID);
}
}
}
PART 3:Traversal
curNode = &root[curVisitOffset];
bool wasVisible = curNode->visible && (curNode->lastVisited == frameID - 1);
bool opened = wasVisible && !curNode->isLeaf;
curNode->visible = false;
curNode->lastVisited = frameID;
if (!opened) {
issueOcculusionQuery(curNode,true);
wasVisible ? queryQueueForNextFrame.push(curNode) : queryQueue.push(curNode);
}
if (wasVisible)
traversalNode(curNode, curVisitOffset, toVisit);
if (curNode->isLeaf) {
if (!toVisit.empty()) {
curVisitOffset = toVisit.top();
toVisit.pop();
} else {
doneTravel = true;
curVisitOffset = 0;
}
}
Function:issueOcculusionQuery
void issueOcculusionQuery(LinearBVHNode* vCurNode, bool isLeft) {
glDepthMask(GL_FALSE);
glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE);
glGenQueriesARB(1, &(vCurNode->queryID));
glBeginQueryARB(GL_SAMPLES_PASSED_ARB, vCurNode->queryID);
drawBound(vCurNode, isLeft);
glEndQueryARB(GL_SAMPLES_PASSED_ARB);
glDepthMask(GL_TRUE);
glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE);
}
Function:drawBound
void drawBound(LinearBVHNode* vCurNode, bool isLeft){
//Draw the Nodes Bounding Box
}
Function:traversalNode
void traversalNode(LinearBVHNode* curNode, int& curVisitOffset, stack<int>& toVisit) {
if (curNode->isLeaf) {
drawNode(curNode,true);
glBindFramebuffer(GL_FRAMEBUFFER, 0);
glBindFramebuffer(GL_FRAMEBUFFER, drawingRightFbo);
drawNode(curNode,false);
glBindFramebuffer(GL_FRAMEBUFFER, drawingLeftFbo);
}
else {
glm::vec3 EyeToCentroid = curNode->bounds.getCentroid() - camera.Position;
int DirisNeg[3]{ EyeToCentroid.x < 0, EyeToCentroid.y < 0, EyeToCentroid.z < 0 };
if (DirisNeg[curNode->axis]) {
toVisit.push(curVisitOffset + 1);
curVisitOffset = curNode->secondChildOffset;
} else {
toVisit.push(curNode->secondChildOffset);
++curVisitOffset;
}
}
}
Function:pullUpVisibility
void pullUpVisibility(LinearBVHNode* root, LinearBVHNode* curNode) {
while (!curNode->visible) {
curNode->visible = true;
curNode = &root[curNode->parentOffset];
}
}
Function:getOcculusionResult
GLuint getOcculusionResult(LinearBVHNode* curNode) {
GLuint sampleCount;
glGetQueryObjectuivARB(curNode->queryID, GL_QUERY_RESULT_ARB, &sampleCount);
return sampleCount;
}
Function:resultAvailable
bool resultAvailable(LinearBVHNode* node) {
GLint available;
glGetQueryObjectivARB(node->queryID, GL_QUERY_RESULT_AVAILABLE_ARB, &available);
// glGetOcclusionQueryuivNV(node->queryID, GL_PIXEL_COUNT_AVAILABLE_NV,&available);
return available;
}
項目地址
Coherent Occlusion Culling(CHC) 演算法的原理與實現
推薦閱讀：
