Implicitizing rational surfaces is a fundamental computational task in Computer Graphics and Computer Aided Design. Ray tracing, collision detection, and solid modeling all benefit from implicitization procedures for rational surfaces. The univariate resultant of two moving lines generated by a μ-basis for a rational curve represents the implicit equation of the rational curve. But although the multivariate resultant of three moving planes corresponding to a μ-basis for a rational surface is guaranteed to contain the implicit equation of the surface as a factor, μ-bases for rational surfaces are difficult to compute. Moreover, μ-bases for a rational surface often have high degrees, so these resultants generally contain many extraneous factors. Here we develop fast algorithms to implicitize rational tensor product surfaces by computing the resultant of three moving planes corresponding to three syzygies with low degrees. These syzygies are easy to compute, and the resultants of the corresponding moving planes generally contain fewer extraneous factors than the resultants of the moving planes corresponding to μ-bases. We predict and compute all the possible extraneous factors that may appear in these resultants. Examples are provided to clarify and illuminate the theory.

Given an implicit polynomial equation or a rational parametrization, we develop algorithms to determine whether the set of real and complex points defined by the equation, i.e., the surface defined by the equation, in the sense of Algebraic Geometry, is a cylindrical surface, a conical surface, or a surface of revolution. The algorithms are directly applicable to, and formulated in terms of, the implicit equation or the rational parametrization. When the surface is cylindrical, we show how to compute the direction of its rulings; when the surface is conical, we show how to compute its vertex; and when the surface is a surface of revolution, we show how to compute its axis of rotation directly from the defining equations.

We present an algorithm for extracting the axis of revolution from the implicit equation of an algebraic surface of revolution based on three distinct computational methods: factoring the highest order form into quadrics, contracting the tensor of the highest order form, and using univariate resultants and gcds. We compare and contrast the advantages and disadvantages of each of these three techniques and we derive conditions under which each technique is most appropriate. In addition, we provide several necessary conditions for an implicit algebraic equation to represent a surface of revolution.

We derive explicit formulas for the generating functions of the $q$-Bernstein basis functions in terms of $q$-exponential functions. Using these explicit formulas, we derive a collection of functional equations for these generating functions which we apply to prove a variety of identities, some old and some new, for the $q$-Bernstein bases.

MOTIVATION: Conformational searches in molecular docking are a time-consuming process with wide range of applications. Favorable conformations of the ligands that successfully bind with receptors are sought to form stable ligand-receptor complexes. Usually a large number of conformations are generated and their binding energies are examined. We propose adding a geometric screening phase before an energy minimization procedure so that only conformations that geometrically fit in the binding site will be prompted for energy calculation. RESULTS: Geometric screening can drastically reduce the number of conformations to be examined from millions (or higher) to thousands (or lower). The method can also handle cases when there are more variables than geometric constraints. An early-stage implementation is able to finish the geometric filtering of conformations for molecules with up to nine variables in 1 min. To the best of our knowledge, this is the first time such results are reported deterministically. CONTACT: [email protected].

Fractals are attractors - fixed points of iterated function systems. Bezier curves are polynomials - linear combinations of Bernstein basis functions. The de Casteljau subdivision algorithm is used here to show that Bezier curves are also attractors. Thus, somewhat surprisingly, Bezier curves are fractals. This fractal nature of Bezier curves is exploited to derive a new rendering algorithm for Bezier curves.

We derive necessary and sufficient conditions which guarantee that a multiplying set of monomials generates exactly a Sylvester A-resultant for three bivariate polynomials with a given planar Newton polygon. We show that valid multiplying sets come in complementary pairs, and any two complementary pairs of multiplying sets can be used to index the rows and columns of a pure Bezoutian A-resultant for the same Newton polygon.The necessary and sufficient conditions include a set of Diophantine equations that can be solved to generate the multiplying sets and therefore the corresponding Sylvester $A$-resultants. Examples relevant to Geometric Modeling are provided, including a new family of hexagonal examples for which Sylvester formulas were not previously known. These examples not only flesh out the theory, but also demonstrate that none of the conditions are superfluous and that all the conditions are mutually independent. The proof of the main theorem makes use of tools from algebraic geometry, including sheaf cohomology on toric varieties and Weyman's resultant complex.

Traditionally, computer graphics is based on the mathematics of projective geometry, homogeneous coordinates, and matrix algebra. Recently these mathematical foundations have been called into question by several authors. We examine some possible alternative mathematical underpinnings for computer graphics, including Grassman spaces and Grassman coordinates, tensors and tensor algebra, and Clifford spaces and Clifford algebras.

Today's computer graphics is ostensibly based upon insights from projective geometry and computations on homogeneous coordinates. Paradoxically, however, projective spaces and homogeneous coordinates are incompatible with much of the algebra and a good deal of the geometry currently in actual use in computer graphics. To bridge this gulf between theory and practice, Grassmann spaces are proposed here as an alternative to projective spaces. We establish that unlike projective spaces, Grassmann spaces do support all the algebra and geometry needed for contemporary computer graphics. We then go on to explain how to exploit this algebra and geometry for a variety of applications, both old and new, including the graphics pipeline, shading algorithms, texture maps, and overcrown surfaces.

It is well-known that the Dixon resultant implicitizes exactly a general tensor product surface. We show that a minor of the Dixon resultant matrix can also implicitize exactly. This occurs when the monomial support of the surface parametrization is a rectangle missing at most one sub-rectangle at each of its its corners. Unlike the Sylvester dialytic method, this way of finding the implicit equation in determinant form is automatic, in bracket form, and uses much smaller matrices.

Poisson approximation extends the Bernstein-Bezier scheme from polynomials to arbitrary analytic functions. A survey of some old and new results in Poisson approximation is presented with special emphasis on algorithmic techniques for analytic functions.

We present a way to construct the Sylvester A-resultant matrix for three bi-degree (m, n) polynomials whose Newton polygon is modified by cutting off rectangles at the corners. We also show that the determinant of this matrix is generically non-singular, so this determinant is indeed the resultant of the three original bivariate polynomials.

In view of the fundamental role that functional composition plays in mathematics, it is not surprising that a variety of problems in geometric modeling can be viewed as instances of the following composition problem: given representations for two functions F and G , compute a representation of the function H = F o G . We examine this problem in detail for the case when F and G are given in either Be´zier or B-spline form. Blossoming techniques are used to gain theoretical insight into the structure of the solution which is then used to develop efficient, tightly codable algorithms. From a practical point of view, if the composition algorithms are implemented as library routines, a number of geometric-modeling problems can be solved with a small amount of additional software.

Macaulay's concise but explicit expression for nmltivariate resultants has many potential applications in computer-aided geometric design.Here we describe its use in solid modeling for finding the intersections of three implicit quadric surfaces.By B6zout's theorem, three quadric surfaces have either at most eight or intlnitely many intersections.Our method finds the intersections, when there are finitely many, by generating a polynomial of degree at most eight whose roots are the intersection coordinates along an appropriate axis.Only addition, subtraction, and multiplication are required to find the polynomial.But when there are pmsibilities of extraneous roots, division and greatest common divisor computations are necessary to identify and remove them.

It is known that certain Catmull-Rom splines [7] interpolate their control vertices and share many properties such as affine invariance, global smoothness, and local control with B-spline curves; they are therefore of possible interest to computer aided design. It is shown here that another property a class of Catmull-Rom splines shares with B-spline curves is that both schemes possess a simple recursive evaluation algorithm. The Catmull-Rom evaluation algorithm is constructed by combining the de Boor algorithm for evaluating B-spline curves with Neville's algorithm for evaluating Lagrange polynomials. The recursive evaluation algorithm for Catmull-Rom curves allows rapid evaluation of these curves by pipelining with specially designed hardware. Furthermore it facilitates the development of new, related curve schemes which may have useful shape parameters for altering the shape of the curve without moving the control vertices. It may also be used for constructing transformations to Bézier and B-spline form.

In Part I, Markov chains were shown to be associated with solutions to several standard problems in computer-aided geometric design. Constraints on these Markov chains were also derived. Examples are given here of Markov chains that either satisfy some of these constraints or solve one of these problems. Subdivision matrices are also studied in special detail.

In vector geometry there are 2 distinct types of entities: points P , Q , R … and vectors u , v , w … Generally, the operattions of vector algebra —addition, subtraction, scalar multiplication, dot product, and cross product—are intrinsically defined only for vectors, not for points. Yet illicit expressions containing terms like P + Q , cP , P X Q , etc. often appear in graphics textbooks, papers, and programs. In this paper we justify the use of such illicit expressions, and we we give criteria for recognizing when such an expression is truly legitimate. In particular we show that an algebraic expression E ( P 1 , …, Pn ) is legitimate if and only if E ( v 1 + w , … v n + w ) = E ( v 1 , …, v n ) + kw , k + 0, 1. We also derive many useful examples of such an expression.

The connection between probability theory and computer-aided geometric design is explored further.Markov chains are shown to be associated with solutions to the following three geometric problems:(1) Given a curve B[P](t), alter the shape of the curve by changing the control points P. (2) Given a curve B[P](t), alter the shape of the curve by changing the blending functions B(t.).(3) Given a curve B[P](t) and blending functions D(t), find control points Q so that D[Q](t) = B[P](t).Constraints imposed on these Markov chains by computer-aided geometric design are also derived.

Article Free Access Share on Solid modeling(Panel Session) Authors: David Gossard MIT MITView Profile , Richard Riesenfeld University of Utah University of UtahView Profile , Herbert Voelcker University of Rochester University of RochesterView Profile , Tony Woo University of Michigan University of MichiganView Profile , Chairman: Ronald N. Goldman Control Data Corporation Control Data CorporationView Profile Authors Info & Claims SIGGRAPH '83: Proceedings of the 10th annual conference on Computer graphics and interactive techniquesJuly 1983 Pages 163–165https://doi.org/10.1145/800059.801146Published:01 July 1983Publication History 0citation349DownloadsMetricsTotal Citations0Total Downloads349Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF