TY - GEN
T1 - Parallel polygon scan conversion on hypercube multiprocessors
AU - Jenq, John Jing Fu
PY - 1999
Y1 - 1999
N2 - Polygon scan conversion is an important operation in rasterization process for computer graphics application. In this paper, we present parallel algorithm for converting polygon from its object space representation into its image space representation by using hypercube multiprocessors. The total number of SIMD hypercube processor is N × N. Each processor element corresponding to a picture element in the image plane. Our algorithm takes O(log2 N) time and O(1) space for general shape polygons. For convex polygon, an algorithm with O(logN) time and O(1) space was developed which is asymptotically optimal for hypercube computers.
AB - Polygon scan conversion is an important operation in rasterization process for computer graphics application. In this paper, we present parallel algorithm for converting polygon from its object space representation into its image space representation by using hypercube multiprocessors. The total number of SIMD hypercube processor is N × N. Each processor element corresponding to a picture element in the image plane. Our algorithm takes O(log2 N) time and O(1) space for general shape polygons. For convex polygon, an algorithm with O(logN) time and O(1) space was developed which is asymptotically optimal for hypercube computers.
UR - http://www.scopus.com/inward/record.url?scp=0032667511&partnerID=8YFLogxK
U2 - 10.1145/298151.298215
DO - 10.1145/298151.298215
M3 - Conference contribution
AN - SCOPUS:0032667511
SN - 1581130864
SN - 9781581130867
T3 - Proceedings of the ACM Symposium on Applied Computing
SP - 110
EP - 114
BT - Proceedings of the ACM Symposium on Applied Computing
PB - Association for Computing Machinery
T2 - Proceedings of the 1999 14th ACM Symposium on Applied Computing, SAC-99
Y2 - 28 February 1999 through 2 March 1999
ER -