Accurate Visualization of Graphs of Functions of Two Real Variables

Authors: Zeitoun D. G., Thierry Dana-Picard

Abstract:

The study of a real function of two real variables can be supported by visualization using a Computer Algebra System (CAS). One type of constraints of the system is due to the algorithms implemented, yielding continuous approximations of the given function by interpolation. This often masks discontinuities of the function and can provide strange plots, not compatible with the mathematics. In recent years, point based geometry has gained increasing attention as an alternative surface representation, both for efficient rendering and for flexible geometry processing of complex surfaces. In this paper we present different artifacts created by mesh surfaces near discontinuities and propose a point based method that controls and reduces these artifacts. A least squares penalty method for an automatic generation of the mesh that controls the behavior of the chosen function is presented. The special feature of this method is the ability to improve the accuracy of the surface visualization near a set of interior points where the function may be discontinuous. The present method is formulated as a minimax problem and the non uniform mesh is generated using an iterative algorithm. Results show that for large poorly conditioned matrices, the new algorithm gives more accurate results than the classical preconditioned conjugate algorithm.

Keywords: Function singularities, mesh generation, point allocation, visualization, collocation least squares method, Augmented Lagrangian method, Uzawa's Algorithm, Preconditioned Conjugate Gradien

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1328694

References:

[1] Amenta N, Bern M, Kamvysselis M. A new Voronoibased surface reconstruction algorithm. In: Proceedings of ACM SIGGRAPH 98; 1998, 415-21.
[2] Avriel Mordechai, Nonlinear Programming Analysis and methods, Prentice-Hall, Inc, 1976.
[3] Axelsson O. and V.A. Barker, Finite Element Solution of Boundary Value Problems, Theory and Computation, Computer Science and Applied Mathematics, Academic Press, INC. 1984.
[4] Bensabat J.and D.G. Zeitoun, A least squares formulation for the solution of transport problems, Int. J. of Num. Meth. in Fluids, Vol 10,pp. 623-636, 1990.
[5] Bertsekas D. P., Constrained Optimization and Lagrange Multiplier Methods , Academic Press 1982.
[6] Botsch M, Kobbelt L., Resampling feature and blend regions in polygonal meshes for surface antialiasing. In: Proceedings of Eurographics 01; 2001, 402-10.
[7] Bramble J.H. and J. Nitsche, A Generalized Ritz- Least Squares Method for Dirichlet Problems, S.I.A.M. J. Numer. Anal. 10 (1), 1973, 81-93.
[8] Bramble J.H. and A.H. Schatz, Least Squares Methods for 2mth Order Elliptic Boundary Value Problems, Math. Comp. 25 (113), 1971, 1-32.
[9] Bristeau M.O.,O. Pironneau, R. Glowinski, J. Periaux and P. Perrier, On the numerical solution of nonlinear problems in fluid dynamics by least squares and finite element methods, Comp. Methods Appl. Mech. Eng. 17-18, 1979, 619 - 657.
[10] Chen Tsu-Fen, On least squares Approximations to Compressible Flow Problems, Num. Meth. for P.D.E. 2 (1986), 207-228.
[11] Th. Dana-Picard: Enhancing conceptual insight: plane curves in a computerized learning environment, International Journal of Technology in Mathematics Education 12 (1), 33-43, 2005.
[12] Th. Dana-Picard, I. Kidron and D. Zeitoun: To See or not To See II, International Journal of Technology in Mathematics Education 15 (4), 157-166.
[13] Dos Santos S.R. and Brodlie K.W., Visualizing and Investigating Multidimensional Functions, IEEE TCVG Symposium on Visualization, 2002, 1-10. Joint EUROGRAPHICS.
[14] Eason E.D. A review of least squares methods for solving partial differential equations, Int. J. Num. Meth. Eng. 10, 1976, 1021-1046.
[15] Fortin M. and R. Glowinski, Augmented Lagrangian Methods: Applications to the numerical solution of boundary value problems, Studies in Mathematics and its Applications 15, North Holland, 1983.
[16] Golub G.H. and Van Loan C.F., Matrix Computations, The John Hopkins University Press, Baltimore, 1984.
[17] Jespersen D.C., A least squares decomposition method for solving elliptic equations, Mathematics of Computation 31 (140), 1977, 873- 880.
[18] Kobbelt L. and Botsh M., A survey of point-based techniques in computer graphics, Computer and Graphics 28, 2004, 801-814.
[19] Kobbelt L, Botsch M, Schwanecke U, Seidel HP. Feature sensitive surface extraction from volume data. In: Proceedings of ACM SIGGRAPH 01; 2001, 57-66.
[20] W. Koepf: Numeric Versus Symbolic Computation, Plenary Lecture at the 2nd Int. Derive Conf., Bonn, 1995. Available: http://www.zib.de/koepf/bonn.ps.Z.
[21] Lapidus L. and G.F. Pinder, Numerical Solution of Partial Differential Equations in Science and Engineering, John Wiley & Sons, 1982.
[22] Levy Bruno, "Constrained Texture Mapping for Polygonal Meshes", ACM SIGGRAPH 2001, 12-17 August 2001.
[23] Sermer P. and R. Mathon, Least squares methods for mixed-type equations, SIAM Journal of Numerical Analysis 18 (4), 1981, 705 - 723.
[24] Zeitoun D.G., Laible J.P. and G.F. Pinder, An Iterative Penalty Method for the Least Squares Solution of Boundary Value Problems, Numer. Meth. for P.D.E., Vol.13 (1997), 257-281.