J. L. D. Comba and J. Stolfi, "Affine arithmetic and its applications to computer graphics", in Proceedings of SIBGRAPI'93, pp. 9--18, (October 1993).  Home/Search   Document Details and Download   Summary   Related Articles   Check

....3 directly affects the efficiency of interval algorithms that use IA: the larger the overestimation, the longer it will take to discard 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 [6, 5, 16, 15, 4] A natural next step is to use affine arithmetic instead of interval arithmetic in the global processing algorithms we have described here. We ....

Comba, J. L. D. and J. Stolfi: 1993, `Affine arithmetic and its applications to computer graphics'. In: Proceedings of SIBGRAPI'93. pp. 9--18.

....whole intervals this is much more powerful and robust than point sampling. However, as we shall see briefly in Section 3, interval arithmetic suffers from a overestimation problem that can negatively impact the performance of interval algorithms. Affine arithmetic, introduced in SIBGRAPI 93 [3] and briefly described in Section 4, is a variant of interval arithmetic that is more resistant to overestimation this has led to faster algorithms for several problems in computer graphics [6, 7, 11, 12] In this paper, we continue this research and study the performance of affine arithmetic ....

....of the computed intervals decreases exponentially, and they soon become too wide to be useful, by many orders of magnitude. Unfortunately, long computation chains are not uncommon in computer graphics applications. 4 Affine arithmetic Affine arithmetic (AA) introduced by Comba and Stolfi [3], is a technique for range analysis that was designed with the explicit goal of handling the dependency problem of IA. Like standard interval arithmetic, AA can provide guaranteed bounds for the computed results, taking into account input, truncation, and rounding errors. Unlike IA, however, AA ....

J. L. D. Comba and J. Stolfi. Affine arithmetic and its applications to computer graphics. Proceedings of SIBGRAPI'93, pages 9--18, October 1993.

....3 directly affects the efficiency of interval algorithms that use IA: the larger the overestimation, the longer it will take to discard 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 ....

J. L. D. Comba and J. Stolfi. Affine arithmetic and its applications to computer graphics. In Proceedings of SIBGRAPI'93, pages 9--18, October 1993.

....as we point out in Section 3, the excessive conservatism of interval arithmetic may greatly reduce the efficiency of the decomposition. In Section 4, we briefly describe affine arithmetic, a recent technique for range analysis that generally provides much tighter bounds than interval arithmetic [5]. In Section 5, we review the algorithm proposed by Gleicher and Kass [3] and give some evidence that their algorithm can be improved by replacing interval arithmetic with affine arithmetic. Section 6 contains some conclusions and outlines directions for future work. 2 Previous work Continuation ....

....intersect. Gleicher and Kass use interval arithmetic for computing ranges. In this paper, we show that their method can be improved by replacing interval arithmetic with affine arithmetic, a tool recently introduced for range analysis that generally produces better bounds than interval arithmetic [5]. Since decomposition methods work directly on parameter domains, no inverse problem needs to be solved to find trimming curves. On the other hand, decomposition methods compute trimming curves in a piecewise, unstructured way; the pieces must be somehow glued together into complete curves. In ....

[Article contains additional citation context not shown here]

J. L. D. Comba and J. Stolfi. Affine arithmetic and its applications to computer graphics. In Proceedings of VI SIBGRAPI (Brazilian Symposium on Computer Graphics and Image Processing), pages 9--18, 1990. Available at http://dcc.unicamp.br/home/staff/stolfi/EXPORT/affine-arith/.

....as we point out in Section 3, the excessive conservatism of interval arithmetic may greatly reduce the efficiency of the decomposition. In Section 4, we briefly describe affine arithmetic, a recent technique for range analysis that generally provides much tighter bounds than interval arithmetic [5]. In Section 5, we review the surface intersection algorithm proposed by Gleicher and Kass [2] and give some evidence that it can be improved by replacing interval arithmetic with affine arithmetic, specially when applied to surfaces commonly used in CAGD. 2 Previous work Continuation methods, ....

....intersect. Gleicher and Kass use interval arithmetic for computing ranges. In this paper, we show that their method can be improved by replacing interval arithmetic with affine arithmetic, a tool recently introduced for range analysis that generally produces better bounds than interval arithmetic [5]. Since decomposition methods work directly on parameter domains, no inverse problem needs to be solved to find trimming curves. On the other hand, decomposition methods compute trimming curves in a piecewise, unstructured way; the pieces must be somehow glued together into complete curves. In ....

[Article contains additional citation context not shown here]

J. L. D. Comba and J. Stolfi. Affine arithmetic and its applications to computer graphics. In Proceedings of VI SIBGRAPI (Brazilian Symposium on Computer Graphics and Image Processing), pages 9--18, 1990. Available at http://dcc.unicamp.br/~stolfi/.

....and they soon become too wide to be useful, by many orders of magnitude. Unfortunately, long computations chains are not uncommon in computer graphics applications. 6 L. H. de Figueiredo, J. Stolfi 4 Affine arithmetic To address the error explosion problem in IA, Comba and Stolfi [5] proposed a new model for numerical computation, called affine arithmetic (AA) Like standard IA, affine arithmetic keeps track automatically of the round off and truncation errors affecting each computed quantity. Unlike IA, however, affine arithmetic keeps track of correlations between those ....

....the multiplication of two affine forms x, y is given by z 0 = x 0 y 0 z i = x 0 y i y 0 x i (i = 1; n) z k = uv; where u = n X i=1 jx i j ; v = n X i=1 jy i j : Similar formulas can be given for the other elementary operations and functions. For instance, it turns out [5] that the square root of an affine form x = x 0 x 1 1 Delta Delta Delta x n n Adaptive enumeration of implicit surfaces with affine arithmetic 9 is given by z 0 = ffx 0 fi z i = ffx i (i = 1; n) z k = ffi; where ff = 1 p a p b fi = p a p b 8 1 2 p a ....

J. L. D. Comba and J. Stolfi. Affine arithmetic and its applications to computer graphics. In Proceedings of VI SIBGRAPI (Brazilian Symposium on Computer Graphics and Image Processing), pages 9--18, 1990.

.... optimization methods based on range analysis use interval arithmetic [10, 23] In this paper, we show that such methods can be improved by combining previous accelerations techniques, including Back Boxing [27] with a recently developed alternative 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 ....

....the interval [a . b] where a is the minimum value and b is the maximum value of the coefficients of f in the Bernstein B ezier basis. In this section, we describe interval arithmetic, a classical range analysis method of wide applicability, and some generalizations, including affine arithmetic [2]. 3.1 Interval arithmetic Interval arithmetic (IA) is the natural technique for computing range estimates [18, 20, 22] IA was invented by Moore [18] with the explicit goal of improving the reliability of numerical computation. It has since been successfully applied to many numerical problems ....

[Article contains additional citation context not shown here]

J. L. D. Comba and J. Stolfi, Affine arithmetic and its applications to computer graphics, in Proceedings of VI SIBGRAPI (Brazilian Symposium on Computer Graphics and Image Processing), 1993, pp. 9--18. Available at http://dcc.unicamp.br/~stolfi/.

....2 =2 Gamma 1=4. The estimates provided by interval arithmetic are too conservative; in complex expressions having many coupled sub expressions, these estimates can quickly become useless. An alternative to interval arithmetic, 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 ....

J. Comba, J. Stolfi, Affine arithmetic and its applications to computer graphics, Proc. VI SIBGRAPI (1993) 9--18. (Brazilian Symposium on Computer Graphics and Image Processing).

....separately, they say only that x [1, 5] and y [1, 7] This result is exact because AA handles affine operations without truncation errors, and in this case also without rounding errors. For a less extreme example, take to be the parabolic segment given by g(t) t , t) for t [0, 2]. Then computing x and y with AA gives x = t = 1.5 2e 1 0.5e 2 y = t = 1 1e 1 The new noise symbol e 2 comes from the (non affine) squaring operation: the second order term e 1 , whose range is [0, 1] is replaced by 0.5 0.5e 2 , losing its correlation with e 1 . Nevertheless, ....

....information on first order correlation between x and y is preserved because x and y share e 1 . This information is sufficient to yield a good approximation for the joint range of x and y. Indeed, taken separately, these equations say only that x lies in the interval X = 1,4] and y lies in Y = [0, 2]. However, taken jointly, they say that (x, y) lies in the dark parallelogram shown in Figure 4, which is substantially smaller than the rectangle X = 1,4] 0, 2] shown in light grey, which would be produced by standard interval arithmetic. Computing bounding rectangles with affine ....

[Article contains additional citation context not shown here]

J. L. D. Comba and J. Stolfi, "Affine arithmetic and its applications to computer graphics", in Proceedings of SIBGRAPI'93, pp. 9--18, (October 1993).

....of the P . This rectangle is not necessarily the smallest rectangle containing P , but it is easy to compute and the resulting strip tree has good performance in practice. In this paper, we show how to compute a strip tree representation for a general parametric curve, using affine arithmetic [2] to find good rectangles containing pieces of the curve. Figure 1 shows an example of a rectangle covering of a parametric curve computed with our algorithm. In Section 2 we review the details of how polygonal curves are represented by strip trees as described by Ballard [1] In Section 3 we ....

....and Wong [10] in their arc tree. The midpoint of P may be difficult to compute; a much simpler choice for the splitting point is the point in P corresponding to the midpoint of T . We shall adopt this choice in the sequel. 4 Affine arithmetic Affine arithmetic (AA) was introduced in SIBGRAPI 93 [2] as a tool for validated numerics [20] Since then, AA has been applied to the robust solution of several graphics problems [4,6,7,11,12] where it has successfully replaced interval arithmetic [16] In AA, a quantity x is represented as an affine form, x = x 0 x 1 1 xn n ; ....

J. L. D. Comba and J. Stolfi. Affine arithmetic and its applications to computer graphics. In Proceedings of SIBGRAPI '93, pages 9--18, October 1993.

.... optimization methods based on range analysis use interval arithmetic [10, 23] In this paper, we show that such methods can be improved by combining previous accelerations techniques, including Back Boxing [27] with a recently developed alternative 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 ....

....the interval [a . b] where a is the minimum value and b is the maximum value of the coefficients of f in the Bernstein B ezier basis. In this section, we describe interval arithmetic, a classical range analysis method of wide applicability, and some generalizations, including affine arithmetic [2]. 3.1. Interval arithmetic. Interval arithmetic (IA) is the natural technique for computing range estimates [18, 20, 22] IA was invented by Moore [18] with the explicit goal of improving the reliability of numerical computation. It has since been UNCONSTRAINED GLOBAL OPTIMIZATION WITH AFFINE ....

[Article contains additional citation context not shown here]

J. L. D. Comba and J. Stolfi, Affine arithmetic and its applications to computer graphics, in Proceedings of VI SIBGRAPI (Brazilian Symposium on Computer Graphics and Image Processing), 1993, pp. 9--18. Available at http://dcc.unicamp.br/~stolfi/.

No context found.

J. L. D. Comba and J. Stolfi, "Affine arithmetic and its applications to computer graphics ", in Proceedings of VI SIBGRAPI (Brazilian Symposium on Computer Graphics and Image Processing), pp. 9--18, (1990). Available at http://dcc.unicamp.br/~stolfi/.

....one often observes an error explosion : as the evaluation advances down the chain, the relative accuracy of the computed intervals decreases exponentially, and they soon become too wide to be useful, by many orders of magnitude. 4 Affine arithmetic To address this error explosion problem, Comba and Stolfi (1993) proposed a new model for numerical computation, called affine arithmetic (AA) Like standard interval arithmetic, affine arithmetic keeps track automatically of the round off and truncation errors affecting each computed quantity. Unlike interval arithmetic, however, affine arithmetic keeps track ....

J. L. D. Comba, J. Stolfi, Affine arithmetic and its applications to computer graphics, Proceedings of VI SIBGRAPI (1993) 9--18 (VI Brazilian Symposium on Computer Graphics and Image Processing, Recife, 1993).

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


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