Parallel polygon scan conversion on hypercube multiprocessors

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the ACM Symposium on Applied Computing
PublisherAssociation for Computing Machinery
Pages110-114
Number of pages5
ISBN (Print)1581130864
StatePublished - 1 Jan 1999
EventProceedings of the 1999 14th ACM Symposium on Applied Computing, SAC-99 - San Antonio, TX, USA
Duration: 28 Feb 19992 Mar 1999

Other

OtherProceedings of the 1999 14th ACM Symposium on Applied Computing, SAC-99
CitySan Antonio, TX, USA
Period28/02/992/03/99

Fingerprint

Computer graphics
Parallel algorithms
Rasterization

Cite this

Jenq, J. (1999). Parallel polygon scan conversion on hypercube multiprocessors. In Proceedings of the ACM Symposium on Applied Computing (pp. 110-114). Association for Computing Machinery.
Jenq, John. / Parallel polygon scan conversion on hypercube multiprocessors. Proceedings of the ACM Symposium on Applied Computing. Association for Computing Machinery, 1999. pp. 110-114
@inproceedings{d9668e65e1364e82b02bb99c27576090,
title = "Parallel polygon scan conversion on hypercube multiprocessors",
abstract = "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.",
author = "John Jenq",
year = "1999",
month = "1",
day = "1",
language = "English",
isbn = "1581130864",
pages = "110--114",
booktitle = "Proceedings of the ACM Symposium on Applied Computing",
publisher = "Association for Computing Machinery",

}

Jenq, J 1999, Parallel polygon scan conversion on hypercube multiprocessors. in Proceedings of the ACM Symposium on Applied Computing. Association for Computing Machinery, pp. 110-114, Proceedings of the 1999 14th ACM Symposium on Applied Computing, SAC-99, San Antonio, TX, USA, 28/02/99.

Parallel polygon scan conversion on hypercube multiprocessors. / Jenq, John.

Proceedings of the ACM Symposium on Applied Computing. Association for Computing Machinery, 1999. p. 110-114.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Parallel polygon scan conversion on hypercube multiprocessors

AU - Jenq, John

PY - 1999/1/1

Y1 - 1999/1/1

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

M3 - Conference contribution

AN - SCOPUS:0032667511

SN - 1581130864

SP - 110

EP - 114

BT - Proceedings of the ACM Symposium on Applied Computing

PB - Association for Computing Machinery

ER -

Jenq J. Parallel polygon scan conversion on hypercube multiprocessors. In Proceedings of the ACM Symposium on Applied Computing. Association for Computing Machinery. 1999. p. 110-114