Many objects, especially those made by humans, display different kinds of symmetry. The most commonly noticed type is reflection symmetry through a plane. Most existing algorithms for detecting symmetry in geometric models focus on finding orthogonal reflective symmetry. However, models can also be distorted by shear transformations, which these methods do not handle. In this paper, we present an algorithm that detects the plane of shear-reflective symmetry in a 3D point cloud, assuming the shear occurs along one of the coordinate axes.

The paper focuses on the design of an energy-minimizing spline that approximates a curve, fits a set of points, and adapts its shape to nearby obstacles. This issue, significant in many fields, has been addressed numerous times, but the mathematical solutions are often complicated. The proposed spline offers less complicated and straightforward computation and, what is more, introduces additional features, such as replicating the shape of both the approximated curve and obstacles, forming an approximated offset curve and preserving C0 to C2 continuity at a junction point. Its behavior is controlled by user-defined scalar parameters. The model, which combines internal and external energies, can be easily modified and upgraded, is generalizable to higher dimensions, and solved using linear least squares. This spline has many potential applications, particularly in computer graphics, geoinformatics, and cartography. Its properties are demonstrated using both synthetic and real cartographic data.

This paper introduces a new simplification method providing high-quality contour lines derived from the 3D point cloud, minimizing their energy. It combines the simplification potential and the splines with the generalized axial symmetry. Generating results similar to the topological skeleton, it applies to large-scale maps (1:5000–1:25,000). It significantly improves all geometric and shape parameters of contour lines, namely in flatter areas. Extensive cartographic testing on high spatial density point clouds using 17 invariants is performed. The outcomes indicate the significant potential of the proposed method. The simplified contour lines preserve the given vertical error, lie within the vertical buffer, are parallel, aesthetically pleasing, and have similar spacing; their artificial oscillations are significantly reduced. Unlike complex generalization methods, the proposed solution does not interfere with the DTM but performs only a correction of the cartographic representation of contour lines.

Proteins have a complex three dimensional structure with empty cavities and tunnels in the inter-atomic space and these spatial features are often essential for the correct biological function. Many discrete and analytical methods have been developed for the computation, analysis and visualization of these features. In this paper, we focus on the connection of cavities with the space outside a protein. This connection would normally be described by tunnels. However, the number of possible solutions can be very high and therefore a nontrivial pruning of solutions is needed to deliver only a few representatives. Therefore, we propose an alternative kind of spatial features called exit regions of cavities. These regions capture the critical locations where a spherical probe, initially placed in a cavity, can leave the protein if the probe is allowed to shrink. The shape of an exit region is more detailed when compared against the simple circular profile of a tunnel. Tunnels, on the other hand, provide more information about the exact path.

Abstract The Connolly surface defines the boundary between a molecular structure and its environment. Its shape depends on the radius of the probe used to inspect the structure. The exploration of surface features is of great interest among chemists because it helps them to better understand and describe processes in the molecular structure. To help chemists better explore these features, we have combined two things together: a fast extraction of Connolly surfaces from a Voronoi diagram of atoms and a fast visualization based on GPU ray casting. Not only the surface but also the volume description is provided by the diagram. This enables to distinguish surface cavities one from another and compute their properties, e.g. the approximate volume, the maximal filling sphere or the maximal probe that can escape from the cavity to the outer environment. Cavities can be filtered out by applying restrictions to these properties. Views behind the surface and surface clipping improve the perception of the complex internal structure. The surface is quickly recomputed for any probe radius, so interactive changes of the probe radius show the development of cavities, especially how and where they merge together or with the outer environment.

Abstract While it is usually not difficult to compute principal curvatures of a smooth surface of sufficient differentiability, it is a rather difficult task when only a polygonal approximation of the surface is available, because of the inherent ambiguity of such representation. A number of different approaches has been proposed in the past that tackle this problem using various techniques. Most papers tend to focus on a particular method, while an comprehensive comparison of the different approaches is usually missing. We present results of a large experiment, involving both common and recently proposed curvature estimation techniques, applied to triangle meshes of varying properties. It turns out that none of the approaches provides reliable results under all circumstances. Motivated by this observation, we investigate mesh statistics, which can be computed from vertex positions and mesh connectivity information only, and which can help in deciding which estimator will work best for a particular case. Finally, we propose a meta‐estimator, which makes a choice between existing algorithms based on the value of the mesh statistics, and we demonstrate that such meta‐estimator, despite its simplicity, provides considerably more robust results than any existing approach.

Abstract The paper surveys main features of computational geometry and presents the argument that a course oriented to applied computational geometry should be a part of the computer graphics curriculum, as it teaches effective algorithmic methods and helps to develop abstract thinking. Possible contents of the course and forms suitable and interesting for computer graphics students are discussed. The students' feedback on such a course has been mostly positive.

Triangle surface models belong to the most popular type of geometric objects description in computer graphics. Therefore, the problem of fast visualization of this type of data is often solved. One of popular approaches is stripification, i.e., a conversion of triangle surface into strips of triangles. This enables to reduce the rendering time by reduction data size and by avoiding of redundant lighting and transformations computations. In this paper we present a new stripification algorithm for static fully triangulated meshes. Our new algorithm is based on the dual graph of triangulation. The experimental results show that our stripification produces much lower number of triangle strips than other stripification algorithms (except one).

This paper introduces a new algorithm for constructing a 2D Delaunay triangulation. It belongs to the class of incremental insertion algorithms, which are known as less demanding from the implementation point of view. The most time consuming step of the incremental insertion algorithms is locating the triangle containing the next point to be inserted. In this paper, this task is transformed to the nearest point problem, which is solved by a two-level uniform subdivision acceleration technique. Dependencies on the distribution of the input points are reduced using this technique. The algorithm is compared with other popular triangulation algorithms: two variants of Guibas, Knuth, and Sharir's incremental insertion algorithm, two different implementations of Mücke's algorithm, Fortune's sweep-line algorithm, and Lee and Schachter's divide and conquer algorithm. The following point distributions are used for tests: uniform, regular, Gaussian, points arranged in clusters, and real data sets from a GIS database. Among all tested algorithms, the divide and conquer approach turns out to be the best. The proposed algorithm is the second fastest except for input points with highly non-uniform distribution. As implementation of the algorithm is simple, it represents an attractive alternative to other Delaunay triangulation algorithms used in practice.