共查询到20条相似文献,搜索用时 406 毫秒
1.
Midpoint subdivision generalizes the Lane–Riesenfeld algorithm for uniform tensor product splines and can also be applied to non-regular meshes. For example, midpoint subdivision of degree 2 is a specific Doo–Sabin algorithm and midpoint subdivision of degree 3 is a specific Catmull–Clark algorithm. In 2001, Zorin and Schröder were able to prove C1-continuity for midpoint subdivision surfaces analytically up to degree 9. Here, we develop general analysis tools to show that the limiting surfaces under midpoint subdivision of any degree ?2 are C1-continuous at their extraordinary points. 相似文献
2.
This paper presents an algorithm for simultaneously fitting smoothly connected multiple surfaces from unorganized measured
data. A hybrid mathematical model of B-spline surfaces and Catmull–Clark subdivision surfaces is introduced to represent objects
with general quadrilateral topology. The interconnected multiple surfaces are G
2 continuous across all surface boundaries except at a finite number of extraordinary corner points where G
1 continuity is obtained. The algorithm is purely a linear least-squares fitting procedure without any constraint for maintaining
the required geometric continuity. In case of general uniform knots for all surfaces, the final fitted multiple surfaces can
also be exported as a set of Catmull–Clark subdivision surfaces with global C
2 continuity and local C
1 continuity at extraordinary corner points.
Published online: 14 May 2002
Correspondence to: W. Ma 相似文献
3.
Ever since its introduction by Stam and Loop, the quad/triangle subdivision scheme, which is a generalization of the well-known
Catmull–Clark subdivision and Loop subdivision, has attracted a great deal of interest due to its flexibility of allowing
both quads and triangles in the same model. In this paper, we present a novel biorthogonal wavelet—constructed through the
lifting scheme—that accommodates the quad/triangle subdivision. The introduced wavelet smoothly unifies the Catmull–Clark
subdivision wavelet (for quadrilateral meshes) and the Loop subdivision wavelet (for triangular meshes) in a single framework.
It can be used to flexibly and efficiently process any complicated semi-regular hybrid meshes containing both quadrilateral
and triangular regions. Because the analysis and synthesis algorithms of the wavelet are composed of only local lifting operations
allowing fully in-place calculations, they can be performed in linear time. The experiments demonstrate sufficient stability
and fine fitting quality of the presented wavelet, which are similar to those of the Catmull–Clark subdivision wavelet and
the Loop subdivision wavelet. The wavelet analysis can be used in various applications, such as shape approximation, progressive
transmission, data compression and multiresolution edit of complex models.
相似文献
Kai Tang (Corresponding author)Email: |
4.
This paper presents a generalization of Catmull–Clark-variant Doo–Sabin surfaces and non-uniform biquadratic B-spline surfaces called Non-Uniform Recursive Doo–Sabin Surfaces (NURDSes). One step of NURDS refinement can be factored into one non-uniform linear subdivision step plus one dual step. Compared to the prior non-uniform Doo–Sabin surfaces (i.e., quadratic NURSSes), NURDSes are convergent for arbitrary n-sided faces. Closed form limit point rules, which are important for applications in adaptive rendering and NC machining, are given as well. 相似文献
5.
Interpolating an arbitrary topology mesh by a smooth surface plays important role in geometric modeling and computer graphics.
In this paper we present an efficient new algorithm for constructing Catmull–Clark surface that interpolates a given mesh.
The control mesh of the interpolating surface is obtained by one Catmull–Clark subdivision of the given mesh with modified
geometric rule. Two methods—push-back operation based method and normal-based method—are presented for the new geometric rule.
The interpolation method has the following features: (1) Efficiency: we obtain a generalized cubic B-spline surface to interpolate
any given mesh in a robust and simple manner. (2) Simplicity: we use only simple geometric rule to construct control mesh
for the interpolating subdivision surface. (3) Locality: the perturbation of a given vertex only influences the surface shape
near this vertex. (4) Freedom: for each edge and face, there is one degree of freedom to adjust the shape of the limit surface.
These features make interpolation using Catmull–Clark surfaces very simple and thus make the method itself suitable for interactive
free-form shape design. 相似文献
6.
Based on an optimal estimate of the convergence rate of the second order norm, an improved error estimate for extraordinary
Catmull–Clark subdivision surface (CCSS) patches is proposed. If the valence of the extraordinary vertex of an extraordinary
CCSS patch is even, a tighter error bound and, consequently, a more precise subdivision depth for a given error tolerance,
can be obtained. Furthermore, examples of adaptive subdivision illustrate the practicability of the error estimation approach. 相似文献
7.
Given an n-sided region bounded by a loop of n polylines, we present a general algorithm to fill such a region by a quad mesh suitable for a subdivision scheme. Typically, the approach consists of two phases: the topological phase and the geometrical phase. In the first part, the connectivity of the mesh is based on determining a partitioning of the region into rectangular subregions across which regular grid could be constructed. The geometrical phase generalizes discrete Coon's patches to position the vertices in the 3D space. The generated mesh could be taken as input to any quad-based subdivision scheme, such as that of Catmull–Clark or Doo–Sabin to generate the corresponding limit surface. The goal of the algorithm is to generate smooth meshes with minimum number and less valence of extraordinary vertices deemed undesirable in such subdivision schemes. 相似文献
8.
A new algorithm for clipping a line segment against a pyramid in E
3 is presented. This algorithm avoids computation of intersection points that are not end points of the output line segment.
It also solves all cases more effectively. The performance of this algorithm is shown to be consistently better than that
of existing algorithms, including the Cohen–Sutherland, Liang–Barsky, and Cyrus–Beck algorithms. 相似文献
9.
Quad/Triangle Subdivision 总被引:10,自引:0,他引:10
In this paper we introduce a new subdivision operator that unifies triangular and quadrilateral subdivision schemes. Designers often want the added flexibility of having both quads and triangles in their models. It is also well known that triangle meshes generate poor limit surfaces when using a quad scheme, while quad‐only meshes behave poorly with triangular schemes. Our new scheme is a generalization of the well known Catmull‐Clark and Loop subdivision algorithms. We show that our surfaces are C 1 everywhere and provide a proof that it is impossible to construct such a C 2 scheme at the quad/triangle boundary. However, we provide rules that produce surfaces with bounded curvature at the regular quad/triangle boundary and provide optimal masks that minimize the curvature divergence elsewhere. We demonstrate the visual quality of our surfaces with several examples. ACM CSS: I.3.5 Computer Graphics—Curve, surface, solid, and object representations 相似文献
10.
Efficient admission control algorithms for multimedia servers 总被引:3,自引:0,他引:3
In this paper, we have proposed efficient admission control algorithms for multimedia storage servers that are providers
of variable-bit-rate media streams. The proposed schemes are based on a slicing technique and use aggressive methods for admission
control. We have developed two types of admission control schemes: Future-Max (FM) and Interval Estimation (IE). The FM algorithm uses the maximum bandwidth requirement of the future to estimate the bandwidth requirement. The IE
algorithm defines a class of admission control schemes that use a combination of the maximum and average bandwidths within
each interval to estimate the bandwidth requirement of the interval. The performance evaluations done through simulations
show that the server utilization is improved by using the FM and IE algorithms. Furthermore, the quality of service is also
improved by using the FM and IE algorithms. Several results depicting the trade-off between the implementation complexity,
the desired accuracy, the number of accepted requests, and the quality of service are presented. 相似文献
11.
Young In Yeo Tianyun Ni Ashish Myles Vineet Goel Jörg Peters 《The Visual computer》2009,25(8):757-769
For use in real-time applications, we present a fast algorithm for converting a quad mesh to a smooth, piecewise polynomial
surface on the Graphics Processing Unit (GPU). The surface has well-defined normals everywhere and closely mimics the shape
of Catmull–Clark subdivision surfaces. It consists of bicubic splines wherever possible, and a new class of patches—c-patches—where a vertex has a valence different from 4. The algorithm fits well into parallel streams so that meshes with 12,000 input
quads, of which 60% have one or more non-4-valent vertices, are converted, evaluated and rendered with 9×9 resolution per
quad at 50 frames per second. The GPU computations are ordered so that evaluation avoids pixel dropout.
相似文献
Young In YeoEmail: |
12.
This paper presents subdivision schemes with subdivision stencils near an extraordinary vertex that are free from or with substantially reduced polar artifact in extraordinary regions while maintaining the best possible bounded curvature at extraordinary positions. The subdivision stencils are firstly constructed to meet tangent plane continuity with bounded curvature at extraordinary positions. They are further optimized towards curvature continuity at an extraordinary position with additional measures for removing or for minimizing the polar artifact in extraordinary regions. The polar artifact for subdivision stencils of lower valences is removed by applying an additional constraint to the subdominant eigenvalue to be the same as that of subdivision at regular vertices, while the polar artifact for subdivision stencils of higher valances is substantially reduced by introducing an additional thin‐plate energy function and a penalty function for maintaining the uniformity and regularity of the characteristic map. A new tuned subdivision scheme is introduced by replacing subdivision stencils of Catmull‐Clark subdivision with that from this paper for extraordinary vertices of valences up to nine. We also compare the refined meshes and limit surface quality of the resulting subdivision scheme with that of Catmull‐Clark subdivision and other tuned subdivision schemes. The results show that subdivision stencils from our method produce well behaved subdivision meshes with the least polar artifact while maintaining satisfactory limit surface quality. 相似文献
13.
《Computer Aided Geometric Design》2014,31(7-8):475-485
In this paper, we introduce triangular subdivision operators which are composed of a refinement operator and several averaging operators, where the refinement operator splits each triangle uniformly into four congruent triangles and in each averaging operation, every vertex will be replaced by a convex combination of itself and its neighboring vertices. These operators form an infinite class of triangular subdivision schemes including Loop's algorithm with a restricted parameter range and the midpoint schemes for triangular meshes. We analyze the smoothness of the resulting subdivision surfaces at their regular and extraordinary points by generalizing an established technique for analyzing midpoint subdivision on quadrilateral meshes. General triangular midpoint subdivision surfaces are smooth at all regular points and they are also smooth at extraordinary points under certain conditions. We show some general triangular subdivision surfaces and compare them with Loop subdivision surfaces. 相似文献
14.
Deadlock detection in distributed database systems: a new algorithm and a comparative performance analysis 总被引:4,自引:0,他引:4
Natalija Krivokapić Alfons Kemper Ehud Gudes 《The VLDB Journal The International Journal on Very Large Data Bases》1999,8(2):79-100
This paper attempts a comprehensive study of deadlock detection in distributed database systems. First, the two predominant
deadlock models in these systems and the four different distributed deadlock detection approaches are discussed. Afterwards,
a new deadlock detection algorithm is presented. The algorithm is based on dynamically creating deadlock detection agents (DDAs), each being responsible for detecting deadlocks in one connected component of the global wait-for-graph (WFG). The
DDA scheme is a “self-tuning” system: after an initial warm-up phase, dedicated DDAs will be formed for “centers of locality”,
i.e., parts of the system where many conflicts occur. A dynamic shift in locality of the distributed system will be responded
to by automatically creating new DDAs while the obsolete ones terminate. In this paper, we also compare the most competitive
representative of each class of algorithms suitable for distributed database systems based on a simulation model, and point
out their relative strengths and weaknesses. The extensive experiments we carried out indicate that our newly proposed deadlock
detection algorithm outperforms the other algorithms in the vast majority of configurations and workloads and, in contrast
to all other algorithms, is very robust with respect to differing load and access profiles.
Received December 4, 1997 / Accepted February 2, 1999 相似文献
15.
16.
In packet audio applications, packets are buffered at a receiving site and their playout delayed in order to compensate for
variable network delays. In this paper, we consider the problem of adaptively adjusting the playout delay in order to keep
this delay as small as possible, while at the same time avoiding excessive “loss” due to the arrival of packets at the receiver
after their playout time has already passed. The contributions of this paper are twofold. First, given a trace of packet audio
receptions at a receiver, we present efficient algorithms for computing a bound on the achievable performance of any playout delay adjustment algorithm. More precisely, we compute upper and lower bounds (which are shown to be tight for the
range of loss and delay values of interest) on the optimum (minimum) average playout delay for a given number of packet losses
(due to late arrivals) at the receiver for that trace. Second, we present a new adaptive delay adjustment algorithm that tracks
the network delay of recently received packets and efficiently maintains delay percentile information. This information, together
with a “delay spike” detection algorithm based on (but extending) our earlier work, is used to dynamically adjust talkspurt
playout delay. We show that this algorithm outperforms existing delay adjustment algorithms over a number of measured audio
delay traces and performs close to the theoretical optimum over a range of parameter values of interest. 相似文献
17.
In this paper, we propose a novel progressive lossless mesh compression algorithm based on Incremental Parametric Refinement, where the connectivity is uncontrolled in a first step, yielding visually pleasing meshes at each resolution level while saving connectivity information compared to previous approaches. The algorithm starts with a coarse version of the original mesh, which is further refined by means of a novel refinement scheme. The mesh refinement is driven by a geometric criterion, in spirit with surface reconstruction algorithms, aiming at generating uniform meshes. The vertices coordinates are also quantized and transmitted in a progressive way, following a geometric criterion, efficiently allocating the bit budget. With this assumption, the generated intermediate meshes tend to exhibit a uniform sampling. The potential discrepancy between the resulting connectivity and the original one is corrected at the end of the algorithm. We provide a proof-of-concept implementation, yielding very competitive results compared to previous works in terms of rate/distortion trade-off. 相似文献
18.
We propose a novel method, based on the two-pass Z-buffer algorithm, to calculate shadows with sufficient precision and efficiency for rendering a daytime landscape with solar
penumbrae. The special feature of the proposed method is that the shadows can be preserved with a precision superior to that
of any visible surface. We use the optimal number of plural shadow buffers to do this; it gives a fairly satisfying trade–off
between computation time and quality of shadows. 相似文献
19.
We propose a new lossy to lossless progressive compression scheme for triangular meshes, based on a wavelet multiresolution theory for irregular 3D meshes. Although remeshing techniques obtain better compression ratios for geometric compression, this approach can be very effective when one wants to keep the connectivity and geometry of the processed mesh completely unchanged. The simplification is based on the solving of an inverse problem. Optimization of both the connectivity and geometry of the processed mesh improves the approximation quality and the compression ratio of the scheme at each resolution level. We show why this algorithm provides an efficient means of compression for both connectivity and geometry of 3D meshes and it is illustrated by experimental results on various sets of reference meshes, where our algorithm performs better than previously published approaches for both lossless and progressive compression. 相似文献
20.
In this paper a class of subdivision schemes generalizing the algorithm of Loop is presented. The stencils have the same support as those from the algorithm of Loop, but allow a variety of weights. By varying the weights a class of C 1 regular subdivision schemes is obtained. This class includes the algorithm of Loop and the midpoint schemes of order one and two for triangular nets. The proof of C 1 regularity of the limit surface for arbitrary triangular nets is provided for any choice of feasible weights. The purpose of this generalization of the subdivision algorithm of Loop is to demonstrate the capabilities of the applied analysis technique. Since this class includes schemes that do not generalize box spline subdivision, the analysis of the characteristic map is done with a technique that does not need an explicit piecewise polynomial representation. This technique is computationally simple and can be used to analyze classes of subdivision schemes. It extends previously presented techniques based on geometric criteria. 相似文献