Keywords: implicit functions, contouring problem, arc-length method, space surface visualization, parallel programming.

This paper deals with finding contours of a function given in an implicit form. The problem can be reduced to finding a graph of an implicit function. Visualization of explicitly given functions is easily performed with most graphical packages available today. On the contrary, implicitly given functions could still present a challenge.

There are several possibilities available for obtaining the graph of a function. Most computer programs use brute force methods like the marching squares method. The result is raster graphics and special care is required when connecting the resulting points.

The most intuitive procedure for graphical representation of implicit functions is the Newton's algorithm for solving nonlinear equations. That comprises division with partial derivatives that could become zero and thus prohibit the convergence of the method. Newton's method suitable for producing graphs of implicit functions could be easily derived using Taylor's formula for function expansion. The resulting equation is not self-starting, an initial value is required and the solution is strongly determined by its choice. Generally, we know little about the function and the choice for the initial value can become questionable. Also, it is evident that the formula has problems in areas where the tangent is (almost) parallel to the global axis. The problem manifests itself through lack of convergence and the lack of possibility to use one equation for obtaining the graph of the whole function. In order to alleviate problems in the Newton method a novel method for visualization of implicit functions is proposed. The method is based on an arc-length procedure that is well established in the field of computational mechanics.

The arc-length method was modified in order to be applicable for visualization of functions [1] but the principle remains the same: an additional equation is introduced to avoid the singularity of the tangent operator (Jacobian). The main advantage is immediately noticed: the tangent matrix can always be inverted since it never gets singular. The other advantage is that the equation is self-starting. Any point can be used as a starting point for our graph providing that arc-length is large enough to reach the function from that point. The method can be easily extended into three dimensions by separating the problem into independent tasks that produce function graphs in n independent planes ("slices").

The proposed algorithm has an additional benefit of being easily parallelized. Moreover, it belongs to the so-called 'embarrassingly parallel algorithms' class [2]. MPI FORTRAN has been employed for the parallelisation and the results are collected in files that serve as input into a graphical presentation program. Numerical examples of plane and space implicit functions illustrate the text and the proposed method.

1

I. Kozar, "Visualizing non-linear implicit functions", in K. Skala, L. Budin, (Editors), "Proceedings of MIPRO 2007: International Convention on Information and Communication Technology, Electronics and Microelectronics", Opatija, Croatia, 79-83, 2007.

2

L. Budin, K. Skala, "Parallel programming and cluster computing", "Proceedings of MIPRO 2005: International Convention on Information and Communication Technology, Electronics and Microelectronics", Opatija, Croatia, 2005. (in Croatian)

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £50 +P&P)