Abstract Intersecting algorithms, especially line clipping in $${E^{2}}$$ E 2 and $${E^{3}}$$ E 3 in computer graphics, have been studied for a long time. Many different algorithms have been developed. The simplest case is a line clipping by a convex polygon in $${E^{2}}$$ E 2 with O(N) computational complexity and with known polygon edges orientation. This contribution presents a new algorithm for a line clipping by a convex polygon in E $$^{2}$$ 2 with O(lg N) complexity, which is based on the point-in-half plane test. The proposed algorithm does not require prior knowledge of the polygon edge orientation. The vertices of the convex polygon and the clipped line can be given in projective space using homogeneous coordinates. The algorithm uses vector–vector operations for efficient implementation with SSE or AVX vector–vector instructions or on GPUs. It is simple and robust.

There are many practical applications based on the Least Square Error (LSE) approximation.It is based on a square error minimization "on a vertical" axis.The LSE method is simple and easy also for analytical purposes.However, if data span is large over several magnitudes or non-linear LSE is used, severe numerical instability can be expected.The presented contribution describes a simple method for large span of data LSE computation.It is especially convenient if large span of data are to be processed, when the "standard" pseudoinverse matrix is ill conditioned.It is actually based on a LSE solution using orthogonal basis vectors instead of orthonormal basis vectors.The presented approach has been used for a linear regression as well as for approximation using radial basis functions.

The tutorial gives a practical overview of projective geometry and its applications in geometry, GPU computations and games. It will show how typical geometrical and computational problems can be solved easily if reformulated using the projective geometry. Presented algorithms are easy to understand, implement and they are robust. Homogeneous coordinates and projective geometry are mostly connected with geometric transformations only. However the projective extension of the Euclidean system allows reformulation of geometrical problems which can be easily solved. In many cases quite complicated formulae are becoming simple from the geometrical and computational point of view. In addition they lead to simple parallelization and to matrix-vector operations which are convenient for matrix-vector hardware architecture like GPU. In this short tutorial we will introduce "practical theory" of the projective space and homogeneous coordinates. We will show that a solution of linear system of equations is equivalent to generalized cross product and how this influences basic geometrical algorithms. The projective formulation is also convenient for computation of barycentric coordinates, as it is actually one cross-product implemented as one clock instruction on GPU. Additional speed up can be expected, too. Moreover use of projective representation enables to postpone division operations in many geometrical problems, which increases robustness and stability of algorithms. There is no need to convert coordinates of points from the homogeneous coordinates to the Euclidean one as the projective formulation supports homogeneous coordinates natively. The presented approach can be applied in computational problems, games and visualization applications as well. The tutorial is targeted to algorithm developers in geometry and graphics, visualization and games. The course is also intended for educators and attendees interested in computational issues in general.

There are multiple areas of computer graphics where triangular meshes are being altered in order to reduce their size or complexity, while attempting to preserve the original shape of the mesh as closely as possible. Recently, this area of research has been extended to cover even a dynamic case, i.e., surface animations which are compressed and simplified. However, to date very little effort has been made to develop methods for evaluating the results, namely the amount of distortion introduced by the processing. Even the most sophisticated compression methods use distortion evaluation by some kind of mean squared error while the actual relevance of such measure has not been verified so far. In this paper, we point out some serious drawbacks of the existing error measures. We present results of the subjective testing that we have performed, and we derive a new measure called Spatiotemporal edge difference (STED) which is shown to provide much better correlation with subjective opinions on mesh distortion.

Abstract The task of dynamic mesh compression seeks to find a compact representation of a surface animation, while the artifacts introduced by the representation are as small as possible. In this paper, we present two geometric predictors, which are suitable for PCA‐based compression schemes. The predictors exploit the knowledge about the geometrical meaning of the data, which allows a more accurate prediction, and thus a more compact representation. We also provide rate/distortion curves showing that our approach outperforms the current PCA‐based compression methods by more than 20%.

Utilisation of Radial Basis Functions (RBF) for reconstruction of damaged images became common technique nowadays. This paper deals with computation and utilisation of auxiliary points in order to further increase the ability of RBF to restore damaged areas in image. Our goal was to achieve the best possible results in acceptable time of computation. We put stress mainly on cases, where the image is heavily damaged e.g. by extreme noise. In these cases our new proposed approach achieved very usable results that even surpassed our expectations.

Abstract In this paper, we present an extension of dynamic mesh compression techniques based on PCA. Such representation allows very compact representation of moving 3D surfaces; however, it requires some side information to be transmitted along with the main data. The biggest part of this information is the PCA basis, and since the data can be encoded very efficiently, the size of the basis cannot be neglected when considering the overall performance of a compression algorithm. We present a new work in this area, as none of the papers about PCA based compression really addresses this issue. We will show that for an efficient and accurate encoding there are better choices than even sophisticated algorithms such as LPC. We will present results showing that our approach can reduce the size of the basis by 90% with respect to direct encoding, which can lead to approximately 25% increase of performance of the compression algorithm without any significant loss of accuracy. Such improvement moves the performance of the PCA encoder beyond the performance of current state of the art dynamic mesh compression algorithms, such as the recently adopted MPEG standard, FAMC.

Abstract We present a new approach to dynamic mesh compression, which combines compression with simplification to achieve improved compression results, a natural support for incremental transmission and level of detail. The algorithm allows fast progressive transmission of dynamic 3D content. Our scheme exploits both temporal and spatial coherency of the input data, and is especially efficient for the case of highly detailed dynamic meshes. The algorithm can be seen as an ultimate extension of the clustering and local coordinate frame (LCF)‐based approaches, where each vertex is expressed within its own specific coordinate system. The presented results show that we have achieved better compression efficiency compared to the state of the art methods. Copyright © 2008 John Wiley & Sons, Ltd.

We describe a method for computing an implicit function that represents a surface by its zero level set, given a set of points scattered over the surface and associated with surface normal vectors. This implicit function is defined as a linear combination of compactly supported radial basis functions. Our method is suitable for testing whether a given point is interior or exterior to the surface, previously only associated with globally supported or globally regularized radial basis functions. We use a two-level interpolation approach. In the coarse scale interpolation, we set basis function centers by a grid that covers the enlarged bounding box of the given point set and compute their signed distances to the underlying surface using local quadratic approximations of the nearest surface points. Then a fitting to the residual errors on the surface points and additional off-surface points is performed with fine scale basis functions. The final function is the sum of the two intermediate functions and is a good approximation of the signed distance field to the surface in the bounding box. Examples of surface reconstruction and set operations between shapes are provided.

This work presents an adaptive method for polygonization of implicit surfaces. The method insists on the shape of triangles and the accuracy of resulting approximation as well. The main advantages of the triangulation presented are simplicity and the stable features that can be used for next expanding. The implementation is not complicated and only the standard data structures are used. The presented algorithm is based on the surface tracking scheme and it is compared with the other algorithms based on the similar principle, such as the Marching cubes and the Marching triangles algorithms.

Algorithms for line clipping against convex polygon have been studied for a long time and many research papers have been published so far. In spite of the latest graphical hardware development and significant increase of performance the clipping is still a bottleneck of the graphical pipeline. This paper presents a new robust and fast algorithm for line clipping by a convex polygon. The algorithm uses a small preprocessing in order to obtain significant speed up. The proposed algorithm is especially convenient for applications where points or lines are represented in homogeneous coordinates. The algorithm does not use division in floating point representation as the resulting points are in homogeneous coordinates. The algorithms benefit if vector-vector hardware supported operations can be used

An algorithm complexity is a very crucial issue in the algorithm design, especially if large data sets are to be processed. Data search is very often used in many algorithms and hash function use gives us a possibility to speed up the process significantly. Nevertheless, it is very difficult to design a good hash function especially for geometric applications. This paper describes a new hash function, its behaviour and use for non-trivial problems. Some problems can be solved effectively using the principle of duality and the hash data structure. Also some problems that cannot be solved in Euclidean space can be solved if dual representation is used and some examples are presented too.

Abstract A new algorithm for clipping lines against convex polyhedron with O(N) complexity is given with modification for non‐convex polyhedron. The suggested algorithm is faster for higher number of facets of the given polyhedron than the traditional Cyrus‐Beck's algorithm. Some principal results of comparison of all algorithms are shown and give some ideas how the proposed algorithm could be used effectively.

The solution of many engineering problems have as a result functions of two variables. that can be given either by an explicit function description, or by a table of the function values. The functions have been usually