Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Efficiency of Strategies for Subdividing Polynomial Triangular Surface Patches
74
0
0.0
(
0
)
Added by
Jean Gallier
Publication date
2006
fields
Informatics Engineering
and research's language is
English
Authors
Jean Gallier
Ask ChatGPT about the research
No Arabic abstract
In this paper, we investigate the efficiency of various strategies for subdividing polynomial triangular surface patches. We give a simple algorithm performing a regular subdivision in four calls to the standard de Casteljau algorithm (in its subdivision version). A naive version uses twelve calls. We also show that any method for obtaining a regular subdivision using the standard de Casteljau algorithm requires at least 4 calls. Thus, our method is optimal. We give another subdivision algorithm using only three calls to the de Casteljau algorithm. Instead of being regular, the subdivision pattern is diamond-like. Finally, we present a ``spider-like subdivision scheme producing six subtriangles in four calls to the de Casteljau algorithm.
rate research
Read More
In this paper, we give several simple methods for drawing a whole rational surface (without base points) as several Bezier patches. The first two methods apply to surfaces specified by triangular control nets and partition the real projective plane RP2 into four and six triangles respectively. The third method applies to surfaces specified by rectangular control nets and partitions the torus RP1 X RP1 into four rectangular regions. In all cases, the new control nets are obtained by sign flipping and permutation of indices from the original control net. The proofs that these formulae are correct involve very little computations and instead exploit the geometry of the parameter space (RP2 or RP1 X RP1). We illustrate our method on some classical examples. We also propose a new method for resolving base points using a simple ``blowing up technique involving the computation of ``resolved control nets.
High dimensional B-splines are catching tremendous attentions in fields of Iso-geometry Analysis, dynamic surface reconstruction and so on. However, the actual measured data are usually sparse and nonuniform, which might not meet the requirement of traditional B-spline algorithms. In this paper, we present a novel dynamic surface reconstruction approach, which is a 3-dimensional key points interpolation method (KPI) based on B-spline, aimed at dealing with sparse distributed data. This method includes two stages: a data set generation algorithm based on Kriging and a control point solving method based on key points interpolation. The data set generation method is designed to construct a grided dataset which can meet the requirement of B-spline interpolation, while promisingly catching the trend of sparse data, and it also includes a parameter reduction method which can significantly reduce the number of control points of the result surface. The control points solving method ensures the 3-dimensional B-spline function to interpolate the sparse data points precisely while approximating the data points generated by Kriging. We apply the method into a temperature data interpolation problem. It is shown that the generated dynamic surface accurately interpolates the sparsely distributed temperature data, preserves the dynamic characteristics, with fewer control points than those of traditional B-spline surface interpolation algorithm.
This paper presents a simple yet effective method for feature-preserving surface smoothing. Through analyzing the differential property of surfaces, we show that the conventional discrete Laplacian operator with uniform weights is not applicable to feature points at which the surface is non-differentiable and the second order derivatives do not exist. To overcome this difficulty, we propose a Half-kernel Laplacian Operator (HLO) as an alternative to the conventional Laplacian. Given a vertex v, HLO first finds all pairs of its neighboring vertices and divides each pair into two subsets (called half windows); then computes the uniform Laplacians of all such subsets and subsequently projects the computed Laplacians to the full-window uniform Laplacian to alleviate flipping and degeneration. The half window with least regularization energy is then chosen for v. We develop an iterative approach to apply HLO for surface denoising. Our method is conceptually simple and easy to use because it has a single parameter, i.e., the number of iterations for updating vertices. We show that our method can preserve features better than the popular uniform Laplacian-based denoising and it significantly alleviates the shrinkage artifact. Extensive experimental results demonstrate that HLO is better than or comparable to state-of-the-art techniques both qualitatively and quantitatively and that it is particularly good at handling meshes with high noise. We will make our source code publicly available.
This paper studies the polynomial basis that generates the smallest $n$-simplex enclosing a given $n^{text{th}}$-degree polynomial curve in $mathbb{R}^n$. Although the Bernstein and B-Spline polynomial bases provide feasible solutions to this problem, the simplexes obtained by these bases are not the smallest possible, which leads to overly conservative results in many CAD (computer-aided design) applications. We first prove that the polynomial basis that solves this problem (MINVO basis) also solves for the $n^text{th}$-degree polynomial curve with largest convex hull enclosed in a given $n$-simplex. Then, we present a formulation that is independent of the $n$-simplex or $n^{text{th}}$-degree polynomial curve given. By using Sum-Of-Squares (SOS) programming, branch and bound, and moment relaxations, we obtain high-quality feasible solutions for any $ninmathbb{N}$, and prove (numerical) global optimality for $n=1,2,3$ and (numerical) local optimality for $n=4$. The results obtained for $n=3$ show that, for any given $3^{text{rd}}$-degree polynomial curve in $mathbb{R}^3$, the MINVO basis is able to obtain an enclosing simplex whose volume is $2.36$ and $254.9$ times smaller than the ones obtained by the Bernstein and B-Spline bases, respectively. When $n=7$, these ratios increase to $902.7$ and $2.997cdot10^{21}$, respectively.
In this article, we consider a collection of geometric problems involving points colored by two colors (red and blue), referred to as bichromatic problems. The motivation behind studying these problems is two fold; (i) these problems appear naturally and frequently in the fields like Machine learning, Data mining, and so on, and (ii) we are interested in extending the algorithms and techniques for single point set (monochromatic) problems to bichromatic case. For all the problems considered in this paper, we design low polynomial time exact algorithms. These algorithms are based on novel techniques which might be of independent interest.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
