TY - GEN

T1 - Methods for precise false-overlap detection in tile-based rendering

AU - Hsieh, Hsiu Ching

AU - Hsiao, Chih Chieh

AU - Yang, Hui Chin

AU - Chung, Chung-Ping

AU - Shann, Jyh-Jiun

PY - 2009/12/3

Y1 - 2009/12/3

N2 - 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 falseoverlap 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), and Counting X-Ratio (CXR). 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.

AB - 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 falseoverlap 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), and Counting X-Ratio (CXR). 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.

KW - False-overlap

KW - Tile list

KW - Tile-based rendering

UR - http://www.scopus.com/inward/record.url?scp=70749135423&partnerID=8YFLogxK

U2 - 10.1109/CSE.2009.466

DO - 10.1109/CSE.2009.466

M3 - Conference contribution

AN - SCOPUS:70749135423

SN - 9780769538235

T3 - Proceedings - 12th IEEE International Conference on Computational Science and Engineering, CSE 2009

SP - 414

EP - 419

BT - Proceedings - 12th IEEE International Conference on Computational Science and Engineering, CSE 2009 - 7th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, EUC 2009

Y2 - 29 August 2009 through 31 August 2009

ER -