Accurate Visualization of Graphs of Functions of Two Real Variables
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.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:49724", author = "Zeitoun D. G. and Thierry Dana-Picard", title = "Accurate Visualization of Graphs of Functions of Two Real Variables", 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", volume = "4", number = "7", pages = "764-11", }
