We compare several methods for approximate implicitization by piece-wise polynomials which have been developed by the authors, and a linear-algebra-based numerical method for implicitization which is provided as a par...
详细信息
ISBN:
(纸本)354033274X
We compare several methods for approximate implicitization by piece-wise polynomials which have been developed by the authors, and a linear-algebra-based numerical method for implicitization which is provided as a part of MAPLE. We investigate both quantitative criteria (such as computing time, memory use, and the error of the approximation) and qualitative criteria. As demonstrated by the results, piecewise approximate implicitization is able to handle surfaces arising in industrial applications. However, special care has to be taken to avoid additional branches and unwanted singularities.
We address the following problem: given a curve in parametric form, compute the implicit representation of another one that approximates the parametric curve on a certain domain of interest. We study this problem from...
详细信息
ISBN:
(纸本)354033274X
We address the following problem: given a curve in parametric form, compute the implicit representation of another one that approximates the parametric curve on a certain domain of interest. We study this problem from the numerical point of view: what happens with the output curve if the input curve is slightly changed? It is shown that for any approximate parameterization of the given curve, the curve obtained by an approximate implicitization with a given precision is contained within a certain perturbation region.
In this paper, it is shown that Grobner bases allow efficient computation with real parametric varieties without implicitizing them. The differences between a real parametric variety and its complex and implicit count...
详细信息
ISBN:
(纸本)354033274X
In this paper, it is shown that Grobner bases allow efficient computation with real parametric varieties without implicitizing them. The differences between a real parametric variety and its complex and implicit counterparts are made explicit. The fundamental operations described are the intersection of two parametric varieties, the computation of the singular locus and the distance between a point and the variety. The latter operation provides a robust algorithm for identifying the parameters values of an approximately given point on the variety.
In this paper, we consider two basic questions about presenting a homogeneous polynomial f: how many variables are needed for presenting f? How can one find a presentation of f involving as few variables as possible? ...
详细信息
ISBN:
(纸本)354033274X
In this paper, we consider two basic questions about presenting a homogeneous polynomial f: how many variables are needed for presenting f? How can one find a presentation of f involving as few variables as possible? We give a complete answer to both questions, determining the minimal number of variables needed, Ness (f), and describing these variables through their linear span, EssVar (f). Our results give rise to effective algorithms which we implemented in the computer algebra system CoCoA [4].
In this paper we present a sampling algorithm which detects and describes the self-intersection locus of a parametric surface. We provide several criteria of injectivity, they serve to decompose the domain of the para...
详细信息
ISBN:
(纸本)354033274X
In this paper we present a sampling algorithm which detects and describes the self-intersection locus of a parametric surface. We provide several criteria of injectivity, they serve to decompose the domain of the parametrization to get a family of smaller patches. The organization of our algorithm relies on a segmentation of the surface based on simple informations such as partial derivatives. Its implementation makes an important use of 2d and 3d bounding boxes trees. We provide some examples with timings and illustrations.
The paper is devoted to the parametrization extension problem: given a loop composed of 3 (resp. 4) rational Bezier curves on a rational surface X, find a triangular (resp. tensor product) Bezier patch on X of optimal...
详细信息
ISBN:
(纸本)354033274X
The paper is devoted to the parametrization extension problem: given a loop composed of 3 (resp. 4) rational Bezier curves on a rational surface X, find a triangular (resp. tensor product) Bezier patch on X of optimal degree bounded by these curves. The constructive solution to the formulated problem is presented in details for cases where X is a sphere or a hyperbolic paraboloid. Then X is an almost toric surface the general solution is outlined using the universal rational parametrization theory. Also an open problem of a linear precision property for toric Bezier patches is discussed.
Recent trends in algebraic geometry emphasize effective computation over transcendent theory. The theme of this paper is that from the perspective of geometric modeling this trend is largely misguided - that for the p...
详细信息
ISBN:
(纸本)354033274X
Recent trends in algebraic geometry emphasize effective computation over transcendent theory. The theme of this paper is that from the perspective of geometric modeling this trend is largely misguided - that for the purpose of geometric modeling the true role of algebraic geometry is insight not computation.
Modern geometric constraint solvers use combinatorial graph algorithms to recursively decompose the system of polynomial constraint equations into generically rigid subsystems and then solve the overall system by solv...
详细信息
ISBN:
(纸本)354033274X
Modern geometric constraint solvers use combinatorial graph algorithms to recursively decompose the system of polynomial constraint equations into generically rigid subsystems and then solve the overall system by solving subsystems, from the leave nodes up, to be able to access any and all solutions. Since the overall algebraic complexity of the solution task is dominated by the size of the largest subsystem, such graph algorithms attempt to minimize the fan-in at each recombination stage. Recently, we found that, especially for 3D geometric constraint systems, a further graph-theoretic optimization of each rigid subsystem is both possible, and often necessary to solve wel-lconstrained systems: a minimum spanning tree characterizes what partial eliminations should be performed before a generic algebraic or numeric solver is called. The weights and therefore the elimination hierarchy defined by this minimum spanning tree computation depend crucially on the representation of the constraints. This paper presents a simple representation that turns many previously untractable systems into easy exercises. We trace a solution family for varying constraint data.
This paper describes a method, exploiting approximation complexes, for computing the implicit equation of a parameterized hypersurface. The fundamental ingredients and properties used in this approach are recalled and...
ISBN:
(纸本)354033274X
This paper describes a method, exploiting approximation complexes, for computing the implicit equation of a parameterized hypersurface. The fundamental ingredients and properties used in this approach are recalled and illustrated on simple examples.
A relatively recent area of study in geometric modeling concerns toric Bezier patches. In this line of work, several questions reduce to testing whether a given convex lattice polygon can be decomposed into a Minkowsk...
详细信息
ISBN:
(纸本)354033274X
A relatively recent area of study in geometric modeling concerns toric Bezier patches. In this line of work, several questions reduce to testing whether a given convex lattice polygon can be decomposed into a Minkowski sum of two such polygons and, if so, to finding one or all such decompositions. Other motivations for this problem include sparse resultant computation, especially for the implicitization of parametric surfaces, and factorization of bivariate polynomials. Particularly relevant for geometric modeling are decompositions where at least one summand has a small number of edges. We study the complexity of Minkowski decomposition and propose efficient algorithms for the case of constant-size summands. We have implemented these algorithms and illustrate them by various experiments with random lattice polygons and on all convex lattice polygons with zero or one interior lattice points. We also express the general problem by means of standard and well-studied problems in combinatorial optimization. This leads to an improvement in asymptotic complexity and, eventually, to efficient randomized algorithms and implementations.
暂无评论