Search

We describe a computing method of the computable (or constructive) real numbers based on analysis of expressions. This method take precision estimate into account in order to get a better algorithm than Ménissier-Morain's method, which is also based on the representation of constructive reals. We solve two problems which appear in exact real arithmetic based on the representation of constructive reals. First, by balancing every item's precision in the expression, we can avoid unnecessary precision growth. Second, by distributing different weights to different operations, we can make sure that complex operations do not waste much time when to compute the whole expression. In these ways, we finally get a more efficient and proper method than prior implementations. [ABSTRACT FROM AUTHOR]

An algorithm for constructing constrained Delaunay triangulation (CDT) of a planar straight-line graph (PSLG) is presented. Although the uniform grid method can reduce the time cost of visibility determinations, the time needed to construct the CDT is still long. The algorithm proposed in this paper decreases the number of edges involved in the computation of visibility by replacing traditional visibility with Delaunay visibility. With Delaunay visibility introduced, all strongly Delaunay edges are excluded from the computation of visibility. Furthermore, a sufficient condition for DT (CDT whose triangles are all Delaunay) existence is presented to decrease the times of visibility determinations. The mesh generator is robust and exhibits a linear time complexity for randomly generated PSLGs. [ABSTRACT FROM AUTHOR]

The presentation of Bézier surfaces affects the results of rendering and tessellating applications greatly. To achieve optimal parameterization, we present two reparameterization algorithms using linear Möbius transformations and quadratic transformations, respectively. The quadratic reparameterization algorithm can produce more satisfying results than the Möbius reparameterization algorithm with degree elevation cost. Examples are given to show the performance of our algorithms for rendering and tessellating applications. [ABSTRACT FROM AUTHOR]

An algorithm for surface fitting to curves with energy control is proposed in this paper. Given four boundary curves and a set of unorganized curves, we impose the constrained energy on the desired surface, and covert the minimum energy problem into a linear equation system of the control points of the surface. We prove that there is one unique solution of this equation system. The proposed algorithm is independent of the coordinate system, and experience shows that the resultant surface is fair. [ABSTRACT FROM AUTHOR]

We propose an adaptive geometry compression method based on 4-point interpolatory subdivision schemes. It can work on digital curves of arbitrary dimensions. With the geometry compression method, a digital curve is adaptively compressed into several segments with different compression levels. Each segment is a 4-point subdivision curve with a subdivision step. In the meantime, we provide high-speed 4-point interpolatory subdivision curve generation methods for efficiently decompressing the compressed data. In the decompression methods, we consider both the open curve case and the closed curve case. For an arbitrary positive integer k, formulae of the number of the resultant control points of an open or closed 4-point subdivision curve after k subdivision steps are provided. The time complexity of the new approaches are O(n), where n is the number of the points in the given digital curve. Examples are provided as well to illustrate the efficiency of the proposed approaches. Keywords: geometry compression, subdivision scheme, 4-point subdivision, interpolatory subdivision, high-speed curve generation. [ABSTRACT FROM AUTHOR]

A second order forward differences based subdivision depth computation technique for extra-ordinary Catmull-Clark subdivision surface (CCSS) patches is presented. The new technique improves a previous technique in that the computation of the subdivision depth is based on the patch's curvature distribution, instead of its dimension. Hence, with the new technique, no excessive subdivision is needed for extra-ordinary CCSS patches to meet the precision requirement and, consequently, one can make trimming, finite element mesh generation, boolean operations, and tessellation of CCSSs more efficient. [ABSTRACT FROM AUTHOR]