Real-time Rasterization Of Algebraic Curves

In geometric modeling, algebraic curves and surfaces are the alternatives suitable for describing the smooth shapes of complex topology. They are important complements to prevalent shape representation method, i.e., NURBS curves and surfaces. Algebraic curves and surfaces in terms of tensor-product B-splines are piecewise ones, which have advantages of simplicity, locality, piecewise smoothness etc. Due to the problems of topological complexity, numerical instability of singular points computations, numerical inaccuracy of displayed curves etc, high-quality real-time rendering of algebraic curves and surfaces is still an open problem, which is also one of fundamental problems in interactive applications. In their thesis, we proposed two GPU-based real-time rasterization algorithms for displaying algebraic curves in pixel accuracy by isolating the singular points. The results provide the display solutions in algebraic curve modeling.In Chapter 1, we briefly review curves and surfaces in geometric modeling. Then we give the definition of piecewise algebraic curve in terms of B-spline and Bernstein polynomials. Finally, we introduce the framework and contributions of the thesis.In Chapter 2, we survey the state of the art of algebraic curves rendering algorithms and indicate the obstacles in real-time high-quality rendering of algebraic curves.In Chapter 3, we propose a real-time rasterization algorithm for algebraic curves based on Cylinder Algebraic Decomposition. First the Interval Arithmetic method is adopted to isolate the singular points in the pixel accuracy. The curve is decomposed into several curve segments, which can approximated as line segments. Finally, these line segments are refined to the pixel accuracy with antialiasing. The algorithm can achieve real-time rendering of algebraic curves in pixel accuracy and avoid the expensive computations to find the singular points.In Chapter 4, we propose a real-time ratserization algorithm for algebraic B-spline curves based on the regularization condition. The algebraic B-spline curve is first converted into piecewise algebraic curves in terms of Bernstein polynomials. Then each curve segment is subdivided till the regularization condition is satisfied. In each sub-domain in which regularization condition is satisfied, the curve segment is simply defined. Furthermore, the singular points can also be isolated into pixel accuracy. Similarly, the proposed algorithm also avoids the expensive singular points computations and achieve real-time rendering of algebraic B-spline curve.At the end, we conclude our works and indicate the future work.