在區塊著色繪圖處理器中移除錯誤重疊區塊之方法

Abstract

在嵌入式裝置的圖形處理中，在進到tile-binning之前，overlap test是一個很重要的步驟。Primitive 不管是任意大小、形狀、位置，都會有其Bounding Box。然後Bounding box的面積相對於primitive而言，有70%是多餘的。在tile-based rendering中，辨識出在bounding box中沒有與primitive的重疊關係的tile且刪除它，可以節省primitive list的儲存空間大小及後續不必要的動作。現有的false-overlap偵測演算法不是過程繁瑣且不夠直覺，不然就是過於簡略，無法精確找出false-overlap tile。在此，我們提出一些精確找出false-overlap tile的方法：Cross Product Test (CPT), Edge Walk (EW), Count X Ratio (CXR)和Approximation Method。設計重點在於，以較少的硬體設計出時間複雜度低的設計。為了提升效能，我們將bounding box切分成三個矩形，使得primitive的邊會是每個矩形的對角線且都有完整的數學公式來處理此區域內的false-overlap tile。如此一來，也可以平行處理被切分割的primitive。

In graphics processing, overlap test is a crucial step before tile-binning in tile-based rendering for embedded devices. An object in a frame is decomposed into primitives, triangles of different sizes, for processing. In tile-binning process, these triangular primitives are typically represented by bounding boxes. However, the bounding box of a primitive usually covers a significant number of tiles which are not overlapped by the primitive. These tiles are called false-overlap tiles and approximate 70% of the tiles of a bounding box. Therefore, in tile-based rendering, identifying and eliminating those false-overlap tiles in a bounding box to reduce both storage pressures in tile-binning and data accesses of external memory for rasterizer become inviting. Existing false-overlap detection algorithms are either too tedious to reduce computation or too rough to gain high coverage. In this paper, we propose three methods to eliminate all false-overlap tiles: Cross-Product Test (CPT), Edge-Walk Test (EWT), Counting X-Ratio (CXR) and approximation method. We partition the bounding box of a primitive into three rectangles at most according to the number of primitive vertices which are also the vertices of the bounding box. The edges of the primitive then become the diagonals of these rectangles, and false overlap detection becomes a well-formulated math processing. The false-overlap detection of these three rectangles may be processed in parallel to improve performance further. The proposed methods are tested using Doom3 and Quake4 for different screen sizes.