3333407
Creating solid models from single 2D sketches
We describe a method of constructing a B-rep solid model from a single hidden-line removed sketch view of a 3D object. The main steps of our approach are as follows. The sketch is first tidied in 2D (to remove digitisation errors). Line labelling is used to deduce the initial topology of the object and to locate hidden faces. Constraints are then produced from the line labelling and features in the drawing (such as probable symmetry) involving the unknown face coefficients and point depths. A least squares solution is found to the linear system and any grossly incompatible equations are rejected. Vertices are recalculated as the intersections of the faces to ensure we have a reconstructible solid. Any incomplete faces are then completed as far as possible from neighbouring faces, producing a solid model from the initial sketch, if successful. The current software works for polyhedral objects with trihedral vertices. CR Descriptors: I.3.5 [Computer Graphics]: Computational Geometry and Object Modelling Geometric algorithms, languages and systems; I.2.10 [Artificial Intelligence]: Vision and Scene Understanding Perceptual reasoning; I.3.6 [Computer Graphics]: Methodology and Techniques Interaction techniques; J.6 [Computer Applications]: CAE CAD.
2214669
Fast degree elevation and knot insertion for B-spline curves
We give a new, simple algorithm for simultaneous degree elevation and knot insertion for B-spline curves. The method is based on the simple approach of computing derivatives using the control points, resampling the knot vector, and then computing the new control points from the derivatives. We compare our approach with previous algorithms and illustrate it with examples.
750888
Detecting approximate incomplete symmetries in discrete point sets
Motivated by the need to detect design intent in approximate boundary representation models, we give an algorithm to detect incomplete symmetries of discrete points, giving the models' potential local symmetries at various automatically detected tolerances. Here, incomplete symmetry is defined as a set of incomplete cycles which are constructed by, e.g., a set of consecutive vertices of an approximately regular polygon, induced by a single isometry. All seven 3D elementary isometries are considered for symmetry detection. Incomplete cycles are first found using a tolerance-controlled point expansion approach. Subsequently, these cycles are clustered for incomplete symmetry detection. The resulting clusters have welldefined, unambiguous approximate symmetries suitable for design intent detection, as demonstrated experimentally.
17590358
Constructing Regularity Feature Trees for Solid Models
Approximate geometric models, e.g. as created by reverse engineering, describe the approximate shape of an object, but do not record the underlying design intent. Automatically inferring geometric aspects of the design intent, represented by feature trees and geometric constraints, enhances the utility of such models for downstream tasks. One approach to design intent detection in such models is to decompose them into regularity features. Geometric regularities such as symmetries may then be sought in each regularity feature, and subsequently be combined into a global, consistent description of the model's geometric design intent. This paper describes a systematic approach for finding such regularity features based on recovering broken symmetries in the model. The output is a tree of regularity features for subsequent use in regularity detection and selection. Experimental results are given to demonstrate the operation and efficiency of the algorithm.
27145850
A non-Euclidean implementation of LOGO
Abstract This paper describes an implementation of the LOGO Turtle Graphics programming environment in non-Euclidean geometry. Turtle graphics and non-Euclidean geometry are described briefly, and consideration is given to some of the details and problems of implementation. We describe the ways in which the LOGO language must be modified for a non-Euclidean environment, and the geometrical problems encountered during implementation.
5659182
Finding approximate shape regularities in reverse engineered solid models bounded by simple surfaces
Current reverse engineering systems are able to generate simple valid boundary representation (B-rep) models from 3D range data. Such models suffer from various inaccuracies caused by noise in the input data and algorithms. The quality of reverse engineered geometric models can potentially be improved by finding candidate shape regularities in such an initial model, and imposing a suitable subset of them on the model by using constraints, in a postprocessing step called beautification. Finding such candidate regularities is a necessary first step, and is discussed in this paper. Algorithms for analysis are presented which use feature objects to describe properties of faces, edges and vertices, and small groups of these elements in a B-rep model with only planar, spherical, cylindrical, conical and toroidal faces. The methods seek similarities between feature objects, e.g. axes which are parallel, for each property type. For each group of similar feature objects they also try to find a special feature object which might represent the group, e.g. an integer value which approximates the radius of similar cylinders. The feature objects used represent shape parameters, directions, axes and positions present in the model. Experiments show that the regularities found by these algorithms include the desired regularities. Although other spurious regularities which must be discarded in subsequent beautification steps are also produced, their number can be reduced by appropriate choice of tolerance values.
18074193
Dynamic Diffusion Load Balancing
We consider the problem of dynamic load balancing in arbitrary (connected) networks on n nodes. Our load generation model is such that during each round, n tasks are generated on arbitrary nodes, and then (possibly after some balancing) one task is deleted from every non-empty node. Notice that this model fully saturates the resources of the network in the sense that we generate just as many new tasks per round as the network is able to delete. We show that even in this situation the system is stable, in that the total load remains bounded (as a function of n alone) over time. Our proof only requires that the underlying “communication” graph be connected. (It of course also works if we generate less than n new tasks per round, but the major contribution of this paper is the fully saturated case.) We further show that the upper bound we obtain is asymptotically tight (up to a moderate multiplicative constant) by demonstrating a corresponding lower bound on the system load for the particular example of a linear array (or path). We also show some simple negative results (i.e., instability) for work-stealing based diffusion-type algorithms in this setting.
34342205
Pfaffian Algorithms for Sampling Routings on Regions with Free Boundary Conditions
Sets of non-intersecting, monotonic lattice paths, or fixed routings, provide a common representation for several combinatorial problems and have been the key element for designing sampling algorithms. Markov chain algorithms based on routings have led to efficient samplers for tilings, Eulerian orientations [8] and triangulations [9], while an algorithm which successively calculates ratios of determinants has led to a very fast method for sampling fixed routings [12]. We extend Wilson’s determinant algorithm [12] to sample free routings where the number of paths, as well as the endpoints, are allowed to vary. The algorithm is based on a technique due to Stembridge for counting free routings by calculating the Pfaffian of a suitable matrix [11] and a method of Colbourn, Myrvold and Neufeld [1] for efficiently calculating ratios of determinants. As an application, we show how to sample tilings on planar lattice regions with free boundary conditions.
6378032
Adding random edges to dense graphs
This paper investigates the addition of random edges to arbitrary dense graphs; in particular, we determine the number of random edges required to ensure various monotone properties including the appearance of a fixed size clique, small diameter and k-connectivity.
119154847
How many random edges make a dense graph hamiltonian
This paper investigates the number of random edges required to add to an arbitrary dense graph in order to make the resulting graph hamiltonian with high probability. Adding $\Theta(n)$ random edges is both necessary and sufficient to ensure this for all such dense graphs. If, however, the original graph contains no large independent set, then many fewer random edges are required. We prove a similar result for directed graphs.
16901231
A Noise Suppression System for the AMR Speech Codec
In this paper we describe a noise reduction preprocessing algorithm for the adaptive multirate (AMR) speech codec of the GSM system. The algorithm is based on spectral weighting and explicitly takes into account the properties of the human auditory system. The weighting rule results in the smallest possible speech distortion under the constraint that the background noise should exhibit no audible distortions. The algorithm was implemented in 16 Bit fixed-point arithmetic and submitted to the ETSI AMR noise reduction standardization contest. Compared to other algorithms, our noise reduction method gave very good results in CCR tests and good results in ACR tests.