Search

NURBS method is the standard mathematical method for describing the shapes of curves/surfaces/volumes, and it is extensively used in computer-aided design, computer-aided manufacturing, and computer graphics. The injectivity of NURBS volumes means that they do not have self-intersections. Since the injectivity of parameterizations depend on the signs of their Jacobian functions, and the Jacobian of a NURBS volume is determined by the determinant of its tangent vectors in three directions, we first propose a method to compute the bounding vectors of the tangent cones of NURBS volume in this paper. Then the sufficient condition for the injectivity of NURBS volume is proposed. A checking algorithm is also presented. Some examples are given to verify the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

B-spline functions are widely used in many industrial applications such as computer graphic representations, computer aided design, computer aided manufacturing, computer numerical control, etc. Recently, there exist some demands, e.g. in reverse engineering (RE) area, to employ B-spline curves for non-trivial cases that include curves with discontinuous points, cusps or turning points from the sampled data. The most challenging task in these cases is in the identification of the number of knots and their respective locations in non-uniform space in the most efficient computational cost. This paper presents a new strategy for fitting any forms of curve by B-spline functions via local algorithm. A new two-step method for fast knot calculation is proposed. In the first step, the data is split using a bisecting method with predetermined allowable error to obtain coarse knots. Secondly, the knots are optimized, for both locations and continuity levels, by employing a non-linear least squares technique. The B-spline function is, therefore, obtained by solving the ordinary least squares problem. The performance of the proposed method is validated by using various numerical experimental data, with and without simulated noise, which were generated by a B-spline function and deterministic parametric functions. This paper also discusses the benchmarking of the proposed method to the existing methods in literature. The proposed method is shown to be able to reconstruct B-spline functions from sampled data within acceptable tolerance. It is also shown that, the proposed method can be applied for fitting any types of curves ranging from smooth ones to discontinuous ones. In addition, the method does not require excessive computational cost, which allows it to be used in automatic reverse engineering applications. [ABSTRACT FROM AUTHOR]

This paper proposed a visualization algorithm based on UG/Open for the loading of boundary conditions during the pre-processing of the boundary face method analysis model. The algorithm firstly used the boundary representation data of geometric model in UG system to generate the background grid and calculated the coordinates of the display points in the parameter space. And then these coordinates were mapped to the three-dimensional space for graphical display. This mapping could guarantee the accuracy of geometric information. This algorithm not only achieves the seamless connection with UG system,automatic display of load and displacement constraints,but also facilitates the integration of CAD and CAE models. [ABSTRACT FROM AUTHOR]

The increasing popularity of 3D printing is drawing the interest of the research community to the possibilities and challenges of this manufacturing method. Amongst its many uncertainties, we are concerned here with one of its certainties-that reduction of the material required in 3D printing is critical for efficiency and affordability. In this paper, we propose a solution to the computer graphics problem of, given a volume boundary, automatically defining the mesh of a low density internal structure that is 3D-printable. The proposed solution involves two steps. The first step is to define a cell complex partition for the internal space of a volume defined by its boundaries. The second step, is to apply the Skin4Skeleton algorithm, which uses the cell complex dual to produce a 3D-printable cell-complex mesh with a parametrised thickness. [ABSTRACT FROM AUTHOR]

Multiple sequence alignment is a crucial task in a number of biological analyses like secondary structure prediction, domain searching, phylogeny, etc. MSAProbs is currently the most accurate alignment algorithm, but its effectiveness is obtained at the expense of computational time. In the paper we present QuickProbs, the variant of MSAProbs customised for graphics processors. We selected the two most time consuming stages of MSAProbs to be redesigned for GPU execution: the posterior matrices calculation and the consistency transformation. Experiments on three popular benchmarks (BAliBASE, PREFAB, OXBench-X) on quad-core PC equipped with high-end graphics card show QuickProbs to be 5.7 to 9.7 times faster than original CPU-parallel MSAProbs. Additional tests performed on several protein families from Pfam database give overall speed-up of 6.7. Compared to other algorithms like MAFFT, MUSCLE, or ClustalW, QuickProbs proved to be much more accurate at similar speed. Additionally we introduce a tuned variant of QuickProbs which is significantly more accurate on sets of distantly related sequences than MSAProbs without exceeding its computation time. The GPU part of QuickProbs was implemented in OpenCL, thus the package is suitable for graphics processors produced by all major vendors. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents an irregular stock cutting system (NEST) developed on AutoCAD software platform. A detail description to its mechanism is included. This development is based on two known techniques: the bitmap representation to transform all shapes drawn by AutoCAD into pixel matrices before nesting, and the bottom-left-fill algorithm for nesting. The system NEST is developed for further research works on practical stock cutting problems. It provides two important parameters: one is the precision level which decides how the bitmap representation can precisely describe a shape and therefore affects the time taken by nesting procedure; the other is the unit rotation angle which make a shape self-rotates in steps with small angle and to be finally placed on sheet material with its best self-rotation angle. NEST can tightly position every shape on a sheet material and performs satisfyingly from practical view point. The nesting result is demonstrated by the original drawings of all shapes and the sheet material instead of their graphics transformed from pixel matrices. Several tests are carried out to show its performance. [Copyright &y& Elsevier]

Abstract: Copyright violation and illegal manipulation of digital data have been acute challenges for many sectors since the very same set of enabling techniques for generating and processing digital data started to emerge. Although traditional protective methods, such as encryption and digital signatures, have been in use for decades, their inability to provide protection after decryption and locating tampering has prompted the development of digital watermarking. In this paper, a semi-fragile watermarking algorithm for authenticating 2D CAD engineering graphics based on log-polar coordinate mapping is proposed. Firstly, the vertices are divided into groups, and for each group, the vertices for carrying a watermark are mapped to the log-polar coordinate system. Then the watermark is embedded in the mantissa of the real-valued log-polar coordinates via bit substitution. Theoretical analysis and experimental results show that the proposed algorithm is not only robust against incidental global operations such as rotation, translation and scaling, but can also detect and locate malicious attacks such as entity modification and entity addition/deletion. [ABSTRACT FROM AUTHOR]

Abstract: The proximity and topology among particles are often the most important factor for understanding the spatial structure of particles. Reasoning the morphological structure of molecules and reconstructing a surface from a point set are examples where proximity among particles is important. Traditionally, the Voronoi diagram of points, the power diagram, the Delaunay triangulation, and the regular triangulation, etc. have been used for understanding proximity among particles. In this paper, we present the theory of the -shape and the -complex and the corresponding algorithms for reasoning proximity among a set of spherical particles, both using the quasi-triangulation which is the dual of the Voronoi diagram of spheres. Given the Voronoi diagram of spheres, we first transform the Voronoi diagram to the quasi-triangulation. Then, we compute some intervals called -intervals for the singular, regular, and interior states of each simplex in the quasi-triangulation. From the sorted set of simplexes, the -shape and the -complex corresponding to a particular value of can be found efficiently. Given the Voronoi diagram of spheres, the quasi-triangulation can be obtained in time in the worst case, where represents the number of simplexes in the quasi-triangulation. Then, the -intervals for all simplexes in the quasi-triangulation can also be computed in time in the worst case. After sorting the simplexes using the low bound values of the -intervals of each simplex in time, the -shape and the -complex can be computed in O time in the worst case by a binary search followed by a sequential search in the neighborhood, where represents the number of simplexes in the -shape or the -complex. The presented theory of the -shape and the -complex will be equally useful for diverse areas such as structural biology, computer graphics, geometric modelling, computational geometry, CAD, physics, and chemistry, where the core hurdle lies in determining the proximity among spherical particles. [Copyright &y& Elsevier]

Abstract: The problem of identifying the topology implied by wireframe drawings of polyhedral objects requires the identification of face loops, loops of edges which correspond to a face in the object the drawing portrays. In this paper, we survey the advantages and limitations of known approaches, and present and discuss test results which illustrate the successes and failures of a currently popular approach based on Dijkstra’s Algorithm. We conclude that the root cause of many failure cases is that the underlying algorithm assumes that the cost of traversing an edge is fixed. We propose a new polynomial-order algorithm for finding faces in wireframes. This algorithm could be adapted to any graph-theoretical least-cost circuit problem where the cost of traversing an edge is not fixed but context-dependent. [Copyright &y& Elsevier]

We have developed a general-purpose Monte Carlo simulation code, called penMesh, that combines the accuracy of the radiation transport physics subroutines from PENELOPE and the flexibility of a geometry based on triangle meshes. While the geometric models implemented in most general-purpose codes-such as PENELOPE's quadric geometry-impose some limitations in the shape of the objects that can be simulated, triangle meshes can be used to describe any free-form (arbitrary) object. Triangle meshes are extensively used in computer-aided design and computer graphics. We took advantage of the sophisticated tools already developed in these fields, such as an octree structure and an efficient ray-triangle intersection algorithm, to significantly accelerate the triangle mesh ray-tracing. A detailed description of the new simulation code and its ray-tracing algorithm is provided in this paper. Furthermore, we show how it can be readily used in medical imaging applications thanks to the detailed anatomical phantoms already available. In particular, we present a whole body radiography simulation using a triangulated version of the anthropomorphic NCAT phantom. An example simulation of scatter fraction measurements using a standardized abdomen and lumbar spine phantom, and a benchmark of the triangle mesh and quadric geometries in the ray-tracing of a mathematical breast model, are also presented to show some of the capabilities of penMesh. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we propose a novel method that represents the highly complex point sets by clustering and reconstructing the points to normal-mapped B-spline surfaces (NBSs). The main idea is to construct elaborate normal maps on simple surfaces for the realistic rendering of complex point-set models. Based on this observation, we developed the coarse, NBSs to approximate the original point datasets with fine surface details. In our algorithm, a genetic clustering algorithm is proposed to automatically segment the point samples into several clusters according to their statistical properties, and a network of B-spline patches with normal maps are constructed according to the clustering results. In respect to signal processing, our algorithm decouples the original data into two collections: coarse geometry information and fine surface details. The multi-level B-spline surfaces are employed to describe the coarse geometry information, and the normal maps are constructed to capture the fine surface details. Our experimental results show that this representation facilitates the modeling and rendering of complex point sets without losing the visual qualities. [Copyright &y& Elsevier]

In geometric modeling and processing, computer graphics and computer vision, smooth surfaces are approximated by discrete triangular meshes reconstructed from sample points on the surfaces. A fundamental problem is to design rigorous algorithms to guarantee the geometric approximation accuracy by controlling the sampling density. This paper gives explicit formulae to the bounds of Hausdorff distance, normal distance and Riemannian metric distortion between the smooth surface and the discrete mesh in terms of principle curvature and the radii of geodesic circum-circle of the triangles. These formulae can be directly applied to design sampling density for data acquisitions and surface reconstructions. Furthermore, we prove that the meshes induced from the Delaunay triangulations of the dense samples on a smooth surface are convergent to the smooth surface under both Hausdorff distance and normal fields. The Riemannian metrics and the Laplace–Beltrami operators on the meshes are also convergent to those on the smooth surfaces. These theoretical results lay down the foundation for a broad class of reconstruction and approximation algorithms in geometric modeling and processing. Practical algorithms for approximating surface Delaunay triangulations are introduced based on global conformal surface parameterizations and planar Delaunay triangulations. Thorough experiments are conducted to support the theoretical results. [Copyright &y& Elsevier]

Abstract: The majority of the existing techniques for surface reconstruction and the closely related problem of normal reconstruction are deterministic. Their main advantages are the speed and, given a reasonably good initial input, the high quality of the reconstructed surfaces. Nevertheless, their deterministic nature may hinder them from effectively handling incomplete data with noise and outliers. An ensemble is a statistical technique which can improve the performance of deterministic algorithms by putting them into a statistics based probabilistic setting. In this paper, we study the suitability of ensembles in normal and surface reconstruction. We experimented with a widely used normal reconstruction technique [Hoppe H, DeRose T, Duchamp T, McDonald J, Stuetzle W. Surface reconstruction from unorganized points. Computer Graphics 1992;71–8] and Multi-level Partitions of Unity implicits for surface reconstruction [Ohtake Y, Belyaev A, Alexa M, Turk G, Seidel H-P. Multi-level partition of unity implicits. ACM Transactions on Graphics 2003;22(3):463–70], showing that normal and surface ensembles can successfully be combined to handle noisy point sets. [Copyright &y& Elsevier]

Abstract: This paper presents an intuitive, freehand sketching application for Computer Aided Design (CAD) that can reconstruct a 3D object from a single, flat, freehand sketch. A pen is used to draw 2D sketches consisting of straight and curved strokes connected at vertices. The sketches are processed by a reconstruction algorithm that uses the angular distribution of the strokes and their connectivity to determine an orthogonal 3D axis system whose projection correlates with the observed stroke orientations. The axis system is used to determine a plausible depth for each vertex. This approach works well for drawings of objects whose edges predominantly conform to some overall orthogonal axis system. A second, independent optimization procedure is then used to reconstruct each curved stroke in the original sketch, assuming that the curve is planar. New strokes can be attached to the 3D object, or drawn directly onto the object''s faces. An implementation of the reconstruction algorithm based on Levenberg–Marquardt optimization allows objects with over 50 strokes to be reconstructed in interactive time. [Copyright &y& Elsevier]

Point-based geometric models are gaining popularity in both the computer graphics and CAD fields. A related design/modelling problem is the focus of the reported research: drawing curves onto digital surfaces represented by clouds of points. The problem is analyzed and solved, and a set of ‘design tools’ are proposed which allow the user/designer to efficiently perform ‘product development’ (alternative name: ‘detail design’) tasks which require efficient processing of a ‘digital surface’. The primary tool is a robust and efficient point projection algorithm combined with a smoothing technique for producing smooth ‘digital curves’ lying onto the cloud surface. The new design tools are tested on a real-life industrial example with very satisfactory results, which are thoroughly presented in the paper. [Copyright &y& Elsevier]

This paper presents an innovative computer graphic method for viewshed generation from big point clouds. The proposed approach consists in simplification of typical methods for viewshed formation that are based on sorting and binary trees. The proposed method is based on the k-d tree concept optimized with radial segmentation and a dedicated mathematical algorithm for subtree rejection. The final visualization of the viewshed is designed with a graphic method using triangulated irregular network (TIN) surfaces from the accepted subtrees. [ABSTRACT FROM AUTHOR]