Parallel Methodologies for a Micropolygon Renderer

Abstract

This paper compares the performance of three different methodologies for a multi-threaded micropolygon-based renderer. We extend the REYES [AG99] algorithm for multi-threaded rendering, which we call CASCADE. CASCADE processes one bucket per thread, forwarding primitives and micropolygons to other buckets/threads through split and dice operations. ROUND_ROBIN runs N single-threaded versions of CASCADE and a compositor, where primitives are distributed to each thread in a semi-random manner. NO_FORWARD executes split and dice operations, but a primitive that spans multiple buckets is processed independently by different threads and the primitives generated through split and dice operations that project outside the current bucket are discarded. In addition, bucket scheduling is used in this case to ensure that no thread is starved for work. Extensive analysis demonstrates that none of these methodologies are clearly superior to the others under all combinations of primitive size, count, transparency, and parallelism, so, a hybrid algorithm is proposed whose performance characteristics make it the best choice under all but the most pathological cases