臺灣博碩士論文加值系統

在本篇論文中，我們提出一個修改的NURBS演算法，它結合了兩個有用的性質：加總成一及動態分母性質。這新演算法能以較少的除法運算次數及order來改進原有演算法的效率。基於此演算法，我們提出一個整合性VLSI架構來計算各種不同的B-Splines曲線及曲面並以晶片實現。在使用TSMC 0.35-μm SPQM CMOS製程，其工作頻率為100 MHz，而消耗功率只為920mW下，每週期可輸出兩個16-bit字組，即一對曲線或曲面上點及其法向量的坐標值。

B-Splines and Non-Uniform Rational B-Splines (NURBS) have become the essential modeling primitives in computer graphics and geometric modeling applications. In this thesis, we propose a modified NURBS algorithm incorporated with two useful properties, sum up to one and dynamic denominator. This novel algorithm provides less order and fewer division operations than the traditional algorithm reported in the literature. Based on this algorithm, a unified architecture for the computation of various types of B-Spline curves and surfaces is presented. The resultant chip, consisting of approximately 752 K transistors, occupies 3.1 mm by 3.1 mm area in the 0.35-μm SPQM CMOS technology. It operates at 100 MHz with two 16-bit data outputs and consumes only 920mW at a supply voltage of 3.3V. The output data rate is two 16-bit words per cycle, which corresponds to a pair of the coordinate values of a point and its normal on a curve/surface.

Chapter 1 INTRODUCTION 1
1.1 Motivation 1
1.2 Related work 2
1.3 Contributions 3
1.4 Outline 3
Chapter 2 PRELIMINARY OF NURBS 4
2.1 Definition and properties 4
2.2 Computation of normals 8
2.3 Related algorithms 10
Chapter 3 MODIFIED NURBS ALGORITHM 13
3.1 Proposed reduced properties 13
3.1.1 The property I : Sum up to one 13
3.1.2 The Property II : Dynamic denominator 14
3.2 Modified NURBS algorithm 15
3.3 Effects of finite word length 18
3.4 Transforming interfaces 20
3.5 Performance comparison 21
Chapter 4 HARDWARE IMPLEMENTATION 23
4.1 System architecture 23
4.1 Knot vector register file (KRF) 24
4.2 Blending function engine (BFE) 26
4.2 Coordinate engine (CE) 31
4.3 Derivative and cross product unit (DXU) 34
4.5 Post-layout simulations 35
Chapter 5 CONCLUSIONS 38
REFERENCES 39

[1] K. Akeley, “Reality Engine Graphics,” Proc. ACM SIGGRAPH, pp. 109-116, 1993.
[2] IGES, Initial Graphics Exchange Specification, version 3.0. Gaithersburg, Md.: Nat’l Bureau of Standards, 1986.
[3] D. Hearn, M. P. Baker, “Three-Dimensional Object Representations,” Computer Graphics, 2nd ed., pp.304-404, Jan. 1997.
[4] E. Angel, Interactive Computer Graphics, 2nd ed., John Wiley & Sons, 1997.
[5] P. Besl, “Hybrid modeling for manufacturing using NURBS, polygons, and 3D scanner data”, Circuits and Systems, 1998 ISCAS ’98. Proceedings of the 1998 IEEE International Symposium on, vol. 5, pp. 484-487, 1998.
[6] I. Kyu Park, “Constructing NURBS surface model from scattered and unorganized range data”, 1999 proceedings. Second International Conference on 3-D Digital Imaging and Modeling, pp. 312-320, 1999.
[7] C. de Boor, “A Practical Guide to Splines,” Applied Mathematical Sciences, Vol. 27, 1977.
[8] T. Piegl, “The NURBS Book,” Springer-Verlag Berlin Heidelberg, 1995.
[9] C. de Boor, The numerical evaluation of B-splines, Jour. Inst. Math. Applic., Vol. 10, pp.134-149, 1972.
[10] M. Gopi and S. Manohar, “A unified architecture for the computation of B-spline curve and surfaces,” IEEE Tran. on Parallel and Distributed System, vol. 8, no. 12, pp. 1275-1287, Dec. 1997.
[11] A. Edward, Interactive computer graphics: a top-down approach with OpenGL, Addison-Wesley, 1997.
[12] E. Mortenson, Geometric modeling, John Wiley & Sons, 1985.
[13] P. C. Mathias, L.M. Patnaik, and S. Ramesh, “Systolic Architecture I Curve Generation,” Computers and Graphics, vol. 13, no. 4, pp. 561-570, 1989.
[14] G. M. Megson, “Systolic Algorithms for B-Spline Patch Generation,” J. Parallel and Distributed Computing, vol. 11, no. 7,pp. 231-238, 1991.
[15] M. Gopi and S. Manohar, “Parallel Architecture for the Computation of Uniform Rational B-Spline Patches,” J. Parallel and Distributed Computing, vol. 30, no 11, pp. 91-98, Nov. 1995.
[16] W. L. Luken and F. Cheng, “Comparison of Surface and Derivative Evaluation Methods for the Rendering of NURB Surfaces,” ACM Transactions on Graphics, vol. 15, no. 2, pp. 153-178, April 1996.
[17] P. William, Digital image processing, John Wiley & Sons, 2nd ed., 1991.