Share Email Print

Proceedings Paper

Partitioning and mapping B-spline surface fitting algorithm into fixed-size VLSI arrays
Author(s): Po-Rong Chang; Share-Young Lee
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

A method of solving the uniform bicubic B-spline surface fitting algorithm is proposed which introduces parallelism in a way that may be effectively exploited by a suitable parallel architecture. This method is based on the observation that a tensor product spline surface fitting problem can be split into two spline curve fitting problems and each of these problems can be realized by a macropipeline of fixed size VLSI arrays. In fact, the heart of curve fitting problem consists of a block tridiagonal linear system. Based on the state-of-art electronic and packaging technologies, the size of VLSI arithmetic devices is limited due to the bounded chip area and I/O packaging constraints. A modular approach to achieve VLSI matrix arithmetic solution for the block tridiagonal linear system is amenable from the viewpoints of feasibility and applicability. A matrix partitioning approach is presented to overcome those technological constraints imposed by the number of I/O pins. A block tridiagonal linear system of size mn is then divided into m simple tridiagonal systems of size n and n simple tridiagonal systems of size m by the Dc Boor partitioning theorem. Each of the simple tridiagonal linear systems could be partitioned and mappied into a series of two fixed size primitive VLSI matrix arithmetic arrays including L-U decomposer and triangular system solver. The L-U decomposer and triangular system solver could be realized by a hex-connected processor array and an inverse perfect shuffle machine respectively. It would be shown that a B-spline surface fitting problem for a grid of mn points can be solved by m hex-connected processor arrays having 4 processors, m inverse perfect shuffle machines having n processors and n inverse perfect shuffle machines having m processors in (3(m+n)+2({logzn1 +flog2n)+4J units of time.

Paper Details

Date Published: 1 August 1990
PDF: 5 pages
Proc. SPIE 1251, Curves and Surfaces in Computer Vision and Graphics, (1 August 1990); doi: 10.1117/12.19735
Show Author Affiliations
Po-Rong Chang, Industrial Technology Research Institute (Taiwan)
Share-Young Lee, Industrial Technology Research Institute (Taiwan)

Published in SPIE Proceedings Vol. 1251:
Curves and Surfaces in Computer Vision and Graphics
Leonard A. Ferrari; Rui J. P. de Figueiredo, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?