L. H. de Figueiredo and J. Stolfi. Adaptive enumeration of implicit surfaces with affine arithmetic. Computer Graphics Forum, 15(5):287--296, 1996.  Home/Search   Document Details and Download   Summary   Related Articles   Check

....finding fast and guaranteed reliable solutions is one of the subjects of recent research [22, 23, 31] The most expensive way to visualize an implicit object is direct ray tracing [18] especially for objects with high algebraic degree. Other solutions are based on enumeration algorithms [3, 6, 7, 11, 12, 22, 30, 31], marching squares cubes triangles [1, 14, 27] particle systems [10, 17] or stochastic differential equations [25] These methods can be used directly for visualization, as preprocessing step for further rendering, or polygonization of the object. A wide variety of solutions exists also for the ....

....with respect to the interval vector corresponding to the axes aligned box to be tested. If the resulting interval contains zero, the box may contain a part of the object and further subdivision is performed. To reduce overestimations caused by interval arithmetic, De Figuereido and Stolfi [11] replace in their algorithm interval arithmetic by affine arithmetic. Voiculescu et al. 31] introduce two further methods to improve the results in the case of algebraic curves and surfaces: They show that a reformulation of the equation into Bernstein Bezier form and or the use of a modified ....

[Article contains additional citation context not shown here]

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

....computed with AA (that is, affine forms for the results of the computation are simply converted to intervals) the automatic exploitation of first order correlations in primitive operations translates into better interval estimates for the results. For more examples in actual applications, see [3, 4, 8, 7]. For examples that do exploit the additional information on joint ranges, see [2, 5] 5. Affine arithmetic versus generalized interval arithmetic Affine arithmetic is similar to generalized interval arithmetic (GIA) a computation model proposed by Hansen in 1975 [6] and recently studied in ....

.... is evident when one considers the joint range of two quantities u and v when they are described in either model: As we have seen, in AA the joint range is always a zonotope, whereas in GIA it is typically a bowtie shaped as shown Figure 7 for the GIA forms u = 0, 0] 1, 3] x v = 0, 0] [1, 4] x, where x is the only input variable, which ranges over [ 1, 1] Moreover, since the GIA coefficients are intervals, rather than numbers, uncertainty cancellations will not be as complete as it can be in AA. For example, if u is the form given above, then the GIA evaluation of u u will ....

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

No context found.

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

....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 expect that performance will be improved, specially when computing estimates G(T ) for pieces of the curve and the corresponding distance estimates D(X ; ....

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

....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 ; which is a polynomial of degree 1 in noise symbols i , whose values are unknown but assumed to lie in the interval [ 1; 1] From this ....

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

....final cells of varying size, but the resulting approximation is not adapted to the curvature. Hickey et al. 35] described a robust program based on interval arithmetic for plotting implicit curves and relations. Tupper [36] described a similar, commercial quality program. Figueiredo and Stolfi [37] showed that adaptive enumerations can be computed more efficiently by using tighter interval estimates provided by affine arithmetic. 5 Conclusion We have described an algorithm for robust adaptive approximation of implicit curves. As far as we know, this is the page 6 of 12 first algorithm ....

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

....This allowed his algorithm to produce an enumeration that has final cells of varying size, but the resulting approximation is not adapted to the curvature. Hickey et al. 16] described a robust program based on interval arithmetic for plotting implicit curves and relations. Figueiredo and Stolfi [10] showed that adaptive enumerations can be computed more efficiently by using tighter interval estimates provided by affine arithmetic. 5 Conclusion We have described an algorithm for robust adaptive approximation of implicit curves. As far as we know, this is the first algorithm which computes a ....

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

....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 in interval methods for ray casting implicit surfaces. As we argue in Section 5, affine arithmetic promises to be useful in ray casting. Section 6 describes our experimental results, which are discussed in ....

....evaluation) Nevertheless, better range estimates usually imply overall faster algorithms, because fewer range estimates have to be computed, even if each individual estimate is expensive. This phenomenon has been observed in several interval methods based on AA: enumeration of implicit surfaces [7], intersection of parametric surfaces [6] sampling [12] and ray tracing [11] procedural shaders. 5 Affine arithmetic and ray casting There are two main reasons for expecting AA to give good results in ray casting an implicit surface given by h(x; y; z) 0. First, AA automatically notices the ....

[Article contains additional citation context not shown here]

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