Asymptotic decider

Last updated

In scientific visualization the asymptotic decider is an algorithm developed by Nielson and Hamann in 1991 that creates isosurfaces from a given scalar field. It was proposed as an improvement to the marching cubes algorithm, which can produce some "bad" topology, [1] but can also be considered an algorithm in its own right. [2]

Contents

Principle

The algorithm first divides the scalar field into uniform cubes. It draws topologically correct contours on the sides (interface) of the cubes. These contours can then be connected to polygons and triangulated. The triangles of all cubes form the isosurfaces and are thus the output of the algorithm. [1] Sometimes there is more than one way to connect adjacent constructs. This algorithm describes a method for resolving these ambiguous configurations in a consistent manner. [3]

Ambiguous cases often occur if diagonally opposing points are found on the same side of the isoline, but on a different side to the other points in the square (for 2D systems) or cube (for 3D systems). [3] In a 2D case this means that there are two possibilities. If we suppose that we mark the corners as positive if their value is greater than that of the isoline, or negative if it is less, then either the positive corners are separated by two isolines, or the positive corners are in the main section of the square and the negative corners are separated by two isolines. The correct situation depends on the value at the asymptote of the isolines. Isolines are hyperbolae which can be described using the following formula:

where is the normalised distance in the square from the left-hand side, and is the normalised distance in the square from the bottom. The values and are therefore the coordinates of the asymptotes, and is the value at the position . This point ought to belong to the section which contains two corners. Therefore, if is greater than the value of the isoline the positive corners are in the main section of the square and the negative corners are separated by two isolines, and if is less than the value of isoline the negative corners are in the main section of the square and the positive corners are separated by two isolines. [4] A similar solution is used the 3D version.

See also

Nuvola apps kalzium.svg   Scienceportal

Related Research Articles

Astronomical coordinate systems System for specifying positions of celestial objects

Astronomical coordinate systems are organized arrangements for specifying positions of satellites, planets, stars, galaxies, and other celestial objects relative to physical reference points available to a situated observer. Coordinate systems in astronomy can specify an object's position in three-dimensional space or plot merely its direction on a celestial sphere, if the object's distance is unknown or trivial.

Least squares Approximation method in statistics

The method of least squares is a standard approach in regression analysis to approximate the solution of overdetermined systems by minimizing the sum of the squares of the residuals made in the results of each individual equation.

Gamma distribution Probability distribution

In probability theory and statistics, the gamma distribution is a two-parameter family of continuous probability distributions. The exponential distribution, Erlang distribution, and chi-square distribution are special cases of the gamma distribution. There are two different parameterizations in common use:

  1. With a shape parameter k and a scale parameter θ.
  2. With a shape parameter α = k and an inverse scale parameter β = 1/θ, called a rate parameter.

In abstract algebra and number theory, Kummer theory provides a description of certain types of field extensions involving the adjunction of nth roots of elements of the base field. The theory was originally developed by Ernst Eduard Kummer around the 1840s in his pioneering work on Fermat's Last Theorem. The main statements do not depend on the nature of the field – apart from its characteristic, which should not divide the integer n – and therefore belong to abstract algebra. The theory of cyclic extensions of the field K when the characteristic of K does divide n is called Artin–Schreier theory.

In mathematics and computing, the Levenberg–Marquardt algorithm, also known as the damped least-squares (DLS) method, is used to solve non-linear least squares problems. These minimization problems arise especially in least squares curve fitting. The LMA interpolates between the Gauss–Newton algorithm (GNA) and the method of gradient descent. The LMA is more robust than the GNA, which means that in many cases it finds a solution even if it starts very far off the final minimum. For well-behaved functions and reasonable starting parameters, the LMA tends to be slower than the GNA. LMA can also be viewed as Gauss–Newton using a trust region approach.

Isosurface Surface representing points of constant value within a volume

An isosurface is a three-dimensional analog of an isoline. It is a surface that represents points of a constant value within a volume of space; in other words, it is a level set of a continuous function whose domain is 3-space.

Gauss–Newton algorithm

The Gauss–Newton algorithm is used to solve non-linear least squares problems, which is equivalent to minimizing a sum of squared function values. It is an extension of Newton's method for finding a minimum of a non-linear function. Since a sum of squares must be nonnegative, the algorithm can be viewed as using Newton's method to iteratively approximate zeroes of the sum, and thus minimizing the sum. It has the advantage that second derivatives, which can be challenging to compute, are not required.

Marching cubes Computer graphics algorithm

Marching cubes is a computer graphics algorithm, published in the 1987 SIGGRAPH proceedings by Lorensen and Cline, for extracting a polygonal mesh of an isosurface from a three-dimensional discrete scalar field. The applications of this algorithm are mainly concerned with medical visualizations such as CT and MRI scan data images, and special effects or 3-D modelling with what is usually called metaballs or other metasurfaces. The marching cubes algorithm is meant to be used for 3-D, the 2-D version of this algorithm is called the marching squares algorithm.

In mathematics, a binary quadratic form is a quadratic homogeneous polynomial in two variables

In general relativity, the Gibbons–Hawking–York boundary term is a term that needs to be added to the Einstein–Hilbert action when the underlying spacetime manifold has a boundary.

Marching tetrahedra

Marching tetrahedra is an algorithm in the field of computer graphics to render implicit surfaces. It clarifies a minor ambiguity problem of the marching cubes algorithm with some cube configurations. It was originally introduced in 1991.

Duffing equation Non-linear second order differential equation and its attractor

The Duffing equation, named after Georg Duffing (1861–1944), is a non-linear second-order differential equation used to model certain damped and driven oscillators. The equation is given by

The Lippmann–Schwinger equation is one of the most used equations to describe particle collisions – or, more precisely, scattering – in quantum mechanics. It may be used in scattering of molecules, atoms, neutrons, photons or any other particles and is important mainly in atomic, molecular, and optical physics, nuclear physics and particle physics, but also for seismic scattering problems in geophysics. It relates the scattered wave function with the interaction that produces the scattering and therefore allows calculation of the relevant experimental parameters.

In the Newman–Penrose (NP) formalism of general relativity, Weyl scalars refer to a set of five complex scalars which encode the ten independent components of the Weyl tensor of a four-dimensional spacetime.

The normal-inverse Gaussian distribution (NIG) is a continuous probability distribution that is defined as the normal variance-mean mixture where the mixing density is the inverse Gaussian distribution. The NIG distribution was noted by Blaesild in 1977 as a subclass of the generalised hyperbolic distribution discovered by Ole Barndorff-Nielsen. In the next year Barndorff-Nielsen published the NIG in another paper. It was introduced in the mathematical finance literature in 1997.

Dirichlet process

In probability theory, Dirichlet processes are a family of stochastic processes whose realizations are probability distributions. In other words, a Dirichlet process is a probability distribution whose range is itself a set of probability distributions. It is often used in Bayesian inference to describe the prior knowledge about the distribution of random variables—how likely it is that the random variables are distributed according to one or another particular distribution.

In the mathematical field of numerical analysis, monotone cubic interpolation is a variant of cubic interpolation that preserves monotonicity of the data set being interpolated.

Non-linear least squares is the form of least squares analysis used to fit a set of m observations with a model that is non-linear in n unknown parameters (m ≥ n). It is used in some forms of nonlinear regression. The basis of the method is to approximate the model by a linear one and to refine the parameters by successive iterations. There are many similarities to linear least squares, but also some significant differences. In economic theory, the non-linear least squares method is applied in (i) the probit regression, (ii) threshold regression, (iii) smooth regression, (iv) logistic link regression, (v) Box-Cox transformed regressors.

Multivariate stable distribution

The multivariate stable distribution is a multivariate probability distribution that is a multivariate generalisation of the univariate stable distribution. The multivariate stable distribution defines linear relations between stable distribution marginals. In the same way as for the univariate case, the distribution is defined in terms of its characteristic function.

In mathematics, Ricci calculus constitutes the rules of index notation and manipulation for tensors and tensor fields on a differentiable manifold, with or without a metric tensor or connection. It is also the modern name for what used to be called the absolute differential calculus, developed by Gregorio Ricci-Curbastro in 1887–1896, and subsequently popularized in a paper written with his pupil Tullio Levi-Civita in 1900. Jan Arnoldus Schouten developed the modern notation and formalism for this mathematical framework, and made contributions to the theory, during its applications to general relativity and differential geometry in the early twentieth century.

References

Notes
  1. 1 2 Nielson & Hamann 1991, p. 83.
  2. Seng et al. 2005, abstract. "The asymptotic decider algorithm was employed to solve the ambiguity problem associated with the MC algorithm."
  3. 1 2 Nielson & Hamann 1991, p. 84.
  4. Nielson & Hamann 1991, p. 85.
Bibliography

Further reading