Nuwan Herath (Gamble) will defend his thesis, entitled “Fast high-resolution drawing of algebraic curves and surfaces”, on Friday June 2nd at 2pm in room C005.
Scientific visualization allows users to build an intuition and to get an understanding of their data. Its applications are numerous: modeling for simulations, mechanism design, medical imaging… We address the problem of visualizing implicit algebraic plane curves and surfaces, that are solutions of a polynomial equation P(x, y) = 0 or Q(x, y, z) = 0. More specifically, we handle the problem of drawing high degree curves or surfaces at a high resolution. In this case, most state-of-the-art approaches fail to produce drawings in a reasonable time due to the high evaluation cost of the polynomial.
Our main contribution is to combine standard visualization algorithms from computer graphics with multipoint evaluation methods from computer algebra. More precisely, we use the fast Discrete Cosine Transform (DCT), which can be computed efficiently with the Fast Fourier Transform (FFT) algorithm. In most of our algorithms, we have combined that idea with a classical subdivision process in order to reduce the number of evaluations.
Using exact error bound computation and interval arithmetic, we propose new algorithms which produce certified drawings. We compare them experimentally on two classes of high degree polynomials. Notably, some of those approaches are faster than state-of-the-art drawing software.