L.H. de Figueiredo and J. Stolfi. Adaptive enumeration of implicit surfaces with affine arithmetic. In Proceedings Eurographics Workshop on Implicit Surfaces, pages 161--170. INRIA, 1995.  Home/Search   Document Not in Database   Summary   Related Articles   Check

....curve and its piecewise linear approximation. The topology may be different, and some small components of the Real curve may be forgotten. But this technique is perfectly robust. Of course, it is better to use some optimizations not to consider all lattice cells, like some interval computations [dFS95, Tau93] or like using continuity: once a starting tetrahedron crossed by the surface is known, the sides by which the contour surface leaves the tetrahedron are easily computed and the contour surface is then followed in the neighboring tetrahedron. It is also possible to approximate better the ....

L.H. de Figueiredo and J. Stolfi. Adaptive enumeration of implicit surfaces with affine arithmetic. In Proceedings Eurographics Workshop on Implicit Surfaces, pages 161--170. INRIA, 1995.

....to interval arithmetic, called affine arithmetic [2] which often provides much tighter estimates. It has been shown that some methods for numerical problems in computer graphics can be improved, in terms of both speed and accuracy, by replacing interval arithmetic with affine arithmetic [3, 4]. Here, we continue this research, applying affine arithmetic in interval methods for unconstrained global optimization. In x2, we describe the general branch and bound technique, specialized for box constrained global minimization. In x3, we review some common methods for obtaining robust range ....

L. H. de Figueiredo and J. Stolfi, Adaptive enumeration of implicit surfaces with affine arithmetic, Computer Graphics Forum, 15 (1996), pp. 287--296.

....curve is located between the two lines: y 0 = 3:3x 0 0:9 and y 0 = 3:3x 0 2:2. It is then easy to compute bounds for area of the pixel parts covered by f(x; y) 0 and by f(x;y) 0. This technique resembles the affine interval arithmetic proposed by L.H. de Figueiredo and J. Stolfi [dFS95], though they don t use it to delimit curves (surfaces) between parallel lines (planes) inside a pixel (voxel) This technique may be easily extended to 3D and to parametric forms. 8 Improvements, open questions and further works We are currently implementing a more general prototype to test ....

L.H. de Figueiredo and J. Stolfi. Adaptive enumeration of implicit surfaces with affine arithmetic. In Proceedings Eurographics Workshop on Implicit Surfaces, pages 161--170. INRIA, 1995.

....its piecewise linear approximation. The topology may be different, and some small components of the real curve may be forgotten. But this technique is perfectly robust. Of course, it is better to use some optimizations to not consider all cells of the lattice, like some computation by intervals [dFS95, Tau93] or like exploiting the continuity: once a starting tetrahedron crossed by the surface is known, the sides by which the contour surface leaves the tetrahedron are easily computed and the contour surface is then followed in the neighbouring tetrahedron. These optimizations are beyond the ....

L.H. de Figueiredo and J. Stolfi. Adaptive enumeration of implicit surfaces with affine arithmetic. In Proceedings Eurographics Workshop on Implicit Surfaces, pages 161--170. INRIA, 1995.

....subregions. It is natural then to consider alternatives to IA that suffer less from the dependency problem and can provide tighter estimates. Affine arithmetic [3] is one of these tools, and its use in interval methods has resulted in faster algorithms for several problems in computer graphics [4, 5, 7, 16, 17]. Our next step is to use affine arithmetic instead of interval arithmetic in the global processing algorithms we have described here. We expect that performance will be improved, specially when computing estimates G(T ) for pieces of the curve and the corresponding distance estimates D(X;T ) ....

L. H. de Figueiredo and J. Stolfi. Adaptive enumeration of implicit surfaces with affine arithmetic. Computer Graphics Forum, 15(5):287--296, 1996.

....curve. An efficient and robust approximation method combines adaptive enumeration with range analysis, and recursively subdivides Omega , using small rectangles only near C. Range analysis allows us to discard large portions of Omega that are guaranteed not to contain any portion of the curve [5, 6, 10, 12]. More precisely, given a function f and a subrectangle R of Omega , we estimate f(R) using an inclusion function F . If 0 62 F (R) then one can be sure that the curve C = f Gamma1 (0) does not intersect R and R can be discarded. Otherwise, the curve may intersect R (recall that range ....

L. H. de Figueiredo and J. Stolfi. Adaptive enumeration of implicit surfaces with affine arithmetic. Computer Graphics Forum, 15(5):287--296, 1996.

....efficient and robust methods for computing surface intersection, mainly for trimming surfaces into patches that can be sewn together to bound complex shapes. Systems that use implicit surfaces as modeling primitives do not suffer from this drawback, but implicit surfaces are harder to approximate [2]. Several methods have been proposed for solving the important problem of computing the intersection of two parametric surfaces. These methods can be classified into two major classes: continuation methods and decomposition methods. In this paper, we describe a variant of a decomposition method ....

....created during a long computation with AA. As one may expect, affine arithmetic is more complex and expensive than ordinary interval arithmetic. However, its higher accuracy is worth the extra cost in many computer graphics applications, including adaptive enumeration of implicit objects [2] and computing the intersection of parametric surfaces, as we show in Section 5. The use of AA for range analysis is simple: First convert all input intervals to affine forms. Then, operate on these affine forms with AA to compute the desired function. Finally, convert the result back into an ....

[Article contains additional citation context not shown here]

L. H. de Figueiredo and J. Stolfi. Adaptive enumeration of implicit surfaces with affine arithmetic. In Proceedings of Implicit Surfaces '95, pages 161--170, April 1995.

....to interval arithmetic, called affine arithmetic [2] which often provides much tighter estimates. It has been shown that some methods for numerical problems in computer graphics can be improved, in terms of both speed and accuracy, by replacing interval arithmetic with affine arithmetic [3, 4]. Here, we continue this research, applying affine arithmetic in interval methods for unconstrained global optimization. Submitted to SIAM Journal of Optimization on March 19, 1997. y LNCC Laborat orio Nacional de Computa c ao Cient ifica, Rua Lauro M uller 455, 22290 160 Rio de Janeiro, RJ, ....

L. H. de Figueiredo and J. Stolfi, Adaptive enumeration of implicit surfaces with affine arithmetic, Computer Graphics Forum, 15 (1996), pp. 287--296.

....much tighter bounds for the computed quantities. In many computer graphics methods based on interval arithmetic, affine arithmetic can transparently replace interval arithmetic. Variants based on affine arithmetic will probably be more efficient, but each case requires separate investigation [3]. This paper describes such an investigation for the surface intersection method by Gleicher and Kass [2] In Section 2, we review some general methods for surface intersection. The most reliable of those seems to be recursive subdivision of parameter space based on range analysis, i.e. on ....

....are dynamically created during a long computation. As one may expect, affine arithmetic is more complex and expensive than ordinary interval arithmetic. However, its higher accuracy is worth the extra cost in many computer graphics applications, including adaptive enumeration of implicit objects [3] and computing the intersection of parametric surfaces, as we show in Section 5. The use of AA for range analysis is simple: First convert all input intervals to affine forms. Then operate on these affine forms with AA to compute the desired function. Finally, convert the result back into an ....

L. H. de Figueiredo and J. Stolfi. Adaptive enumeration of implicit surfaces with affine arithmetic. In Proceedings of Implicit Surfaces '95, pages 161--170, April 1995. Extended version to appear in Computer Graphics Forum.

....called affine arithmetic, has been proposed to overcome this problem [8] Affine arithmetic does handle coupling in expressions and is therefore able to provide better estimates. Adaptive enumeration of implicit objects using affine arithmetic is a promising technique, specially for rendering [9] (Fig. 6) to appear in Computer Graphics 20 #3 (1996) special issue Computer Graphics in Brazil ) Figure 6: Adaptive enumeration with affine arithmetic; h(x; y) x 2 y 2 xy Gamma (xy) 2 =2 Gamma 1=4. Physically based sampling Let V be an object given implicitly in R n by a ....

L. H. de Figueiredo, J. Stolfi, Adaptive enumeration of implicit surfaces with affine arithmetic, Proc. Implicit Surfaces '95, 161--170.

....of implementation and performance. This is mainly due to the 3D combinatorics of the problem, as well as the need of space and time resources. Recently, however, range analysis techniques [21] have been used successfully to avoid full enumeration of implicit surfaces in high resolution meshes [22 25]. Another problem that needs to be faced when computing polygonal approximations for implicit surfaces is the presence of singularities. Although this problem could be present in parametric surfaces too, it is much harder for implicit surfaces, especially in a design environment [26] As mentioned ....

L. H. de Figueiredo and J. Stolfi. Adaptive enumeration of implicit surfaces with affine arithmetic. Computer Graphics Forum, 15(5):287--296, 1996.

Online articles have much greater impact   More about CiteSeer   Add search form to your site   Submit documents   Feedback  


CiteSeer - citeseer.org - Terms of Service - Privacy Policy - Copyright © 1997-2002 NEC Research Institute