Search

The characterisation of geometric shapes produces their concise description and is, therefore, important for subsequent analyses, for example in Computer Vision, Machine Learning, or shape matching. A new method for extracting characterisation vectors of 2D geometric shapes is proposed in this paper. The shape of interest, embedded into a raster space, is swept several times by sweep-lines having different slopes. The interior shape’s points, being in the middle of its boundary and laying on the actual sweep-line, are identified at each stage of the sweeping process. The midpoints are then connected iteratively into chains. The chains are filtered, vectorised, and normalised. The obtained polylines from the vectorisation step are used to design the shape’s characterisation vector for further application-specific analyses. The proposed method was verified on numerous shapes, where single- and multi-threaded implementations were compared. Finally, characterisation vectors, among which some were rotated and scaled, were determined for these shapes. The proposed method demonstrated a good rotation- and scaling-invariant identification of equal shapes.

Zrcadlová symetrie je potenciálně velmi užitečná vlastnost, kterou vykazuje mnoho reálných objektů. Nalezne využití v různých aplikacích jako zarovnání objektů, komprese, symetrická editace nebo rekonstrukce neúplných objektů. V tomto článku navrhujeme novou, diferencovatelnou míru symetrie, která umožňuje použití gradientní optimalizace k hledání symetrie v geometrických objektech. Dále navrhujeme novou metodu pro nalezení roviny symetrie 3D objektu, založenou na táto myšlence. Zmíněná metoda funguje velmi dobře na dokonale i přibližně symetrických objektech, je robustní vůči šumu a vůči chybějícím částem. Navíc ji lze použít pro diskrétní množinu bodů, tudíž metoda neklade prakticky žádné požadavky na vstupní data. Díky flexibilitě navrhované míry symetrie je metoda také velmi snadno rozšiřitelná, např. přidáním více informací o vstupním objektu a jejich využitím pro další zlepšení jejich výsledků. Navržená metoda byla testována s velmi dobrými výsledky na mnoha objektech včetně neúplných a zašuměných objektů a porovnána s dalšími moderními metodami, které překonala v mnoha aspektech. Reflectional symmetry is a potentially very useful feature which many real-world objects exhibit. It is instrumental in a variety of applications such as object alignment, compression, symmetrical editing or reconstruction of incomplete objects. In this paper, we propose a novel differentiable symmetry measure, which allows using gradient-based optimization to find symmetry in geometric objects. We further propose a new method for symmetry plane detection in 3D objects based on this idea. The method performs well on perfectly as well as approximately symmetrical objects, it is robust to noise and to missing parts. Furthermore, it works on discrete point sets and therefore puts virtually no constraints on the input data. Due to flexibility of the symmetry measure, the method is also easily extensible, e.g., by adding more information about the input object and using it to further improve its performance. The proposed method was tested with very good results on many objects, including incomplete objects and noisy objects, and was compared to other state-of-the-art methods which it outperformed in most aspects

A new algorithm is presented for detecting the global reflection symmetry of geometric objects. The algorithm works for 2D and 3D objects which may be open or closed and may or may not contain holes. The algorithm accepts a point cloud obtained by sampling the object’s surface at the input. The points are inserted into a uniform grid and so-called boundary cells are identified. The centroid of the boundary cells is determined, and a testing symmetry axis/plane is set through it. In this way, the boundary cells are split into two parts and they are faced with the symmetry estimation function. If the function estimates the symmetric case, the boundary cells are further split until a given threshold is reached or a non-symmetric result is obtained. The new testing axis/plane is then derived and tested by rotation around the centroid. This paper introduces three techniques to accelerate the computation. Competitive results were obtained when the algorithm was compared against the state of the art.

Vlastnost symetrie ve 3D objektech je užitečná v různých aplikacích jako zarovnání objektů, komprese, symetrická editace nebo rekonstrukce neúplných objektů. Její robustní a efektivní detekce je však náročný úkol. Dva nejčastěji se vyskytující typy symetrie jsou pravděpodobně zrcadlová a rotační symetrie. Zatímco metod pro detekci zrcadlové symetrie existuje poměrně dost, nezdá se, že by tomu tak bylo u detekce rotační symetrie. V tomto článku je navrženo použití přibližných zrcadlových symetrií k odvození přijatelných rotačních symetrií, které lze integrovat s různými přístupy pro detekci zrcadlové symetrie. Jeden takový specifický přístup, založený na maximalizaci dané míry symetrie, je zvolen a kombinován s touto myšlenkou. Dále je navržena modifikace maximalizačního kroku pro rotace pomocí jednoduché, ale účinné, kvaternionové parametrizace transformace rotace, která se zdá být v oblasti detekce symetrie nová. Výsledky potvrzují, že tato kombinace poskytuje robustní a efektivní řešení pro nalezení rotační symetrie v 3D množině bodů a zvládne data s přibližnou symetrií, vstup poškozený šumem nebo dokonce částečná data. The property of symmetry in 3D objects is helpful in various applications such as object alignment, compression, symmetrical editing or reconstruction of incomplete objects. However, its robust and efficient detection is a challenging task. The two most commonly occurring types of symmetry are probably reflectional and rotational symmetry. While reflectional symmetry detection methods are quite plentiful, this does not seem to be the case with rotational symmetry detection. In this paper a use of approximate reflectional symmetries to derive plausible approximate rotational symmetries is proposed that can be integrated with multiple different approaches for reflectional symmetry detection. One such specific approach, based on maximizing a given symmetry measure, is chosen and combined with this idea. A modification of the maximization step for rotations is further proposed using a simple, yet efficient, quaternion-based parameterization of the rotation transformation which seems novel in the field of symmetry detection. The results confirm that this combination provides a robust and efficient solution for finding rotational symmetry in a 3D point set and can handle approximate symmetry, noisy input or even partial data.

Kinetické datové struktury představují rozšíření běžných datových struktur, ve kterém se uvažují časově závislá generující data (např. pohybující se body). V tomto článku definujeme kinetickou lokálně minimální triangulaci (KLMT) jako datovou strukturu rozšiřující standardní lokálně minimální triangulaci v eukleidovské rovině. Zkoumáme její obecné vlastnosti, abychom ukázali, s jakými typy událostí je nutno nakládat během jejího života; také se zabýváme predikáty, které určují tyto události. Abychom mohli popsat její základní kinetické vlastnosti, ukazujeme, že KLMT je responzivní, kompaktní, efektivní a není lokální. V části zabývající se kombinatorickou analýzou stručně popisujeme matematický apaprát, který se běžně využívá pro výzkum výpočetní složitosti v kontextu kinetických datových struktur a používáme jej, abychom stanovili meze počtu událostí, které je potřeba zpracovat během života této datové struktury. Nakonec porovnáváme získané informace s kinetickou Delaunayovou triangulací, abychom ukázali, že ve srovnání s ní má KLMT některé potenciální výhody. Jmenovitě se jedná o jednodušší matematické rovnice, které je nutno řešit za účelem výpočtu časů událostí. Kinetic data structures represent an extension to ordinary data structures, where the underlying data become time-dependent (e.g., moving points). In this paper, we define the kinetic locally minimal triangulation (KLMT) as a kinetic data structure extension to the locally minimal triangulation in the Euclidean plane. We explore the general properties of this data structure in order to show what types of events need to be considered during its lifecycle; we also describe the predicates associated with these events. To describe the general kinetic features, we prove that KLMT is responsive, compact, efficient, and non-local. In the combinatorial analysis of KLMT, we briefly describe the mathematical apparatus commonly used to investigate computational complexity properties of kinetic data structures and use it to establish the bounds on the number of events processed during the lifecycle of this data structure. Finally, the obtained results are compared to the kinetic Delaunay triangulation showing that KLMT may provide some benefits over kinetic Delaunay triangulation, namely simplifying the mathematical equations that need to be computed in order to obtain the times of events.

The article introduces a new method of planning paths for big groups in dynamic environments represented by a graph of vertices and edges, where the edge weight as well as the graph topology may change, but the method is also applicable to environments with a different representation. The utilization of clustering enables the use of a computed path for a group of agents. In this way, a speed-up and memory savings are achieved at a cost of some path sub-optimality. Examples of proper applications of the suggested approach are crowd simulation in urban environments or path-planning-based tasks in molecular biology. The experiments showed good behaviour of the method to speed-up, relative error and online computation.

Tento článek představuje novou metodu plánování pohybu založenou na náhodném vzorkování, která je vhodná pro problém úzkých průchodů. Navrhovaná metoda byla inspirována metodou výstupních bodů pro dutiny v proteinových modelech a je založena na rychlém zkoumání náhodného stromu (RRT). Na rozdíl od jiných metod může také zjistit přesnou pozici úzkých průchodů. Tato informace je nesmírně důležitá, neboť pomáhá prozkoumat tuto část prostoru podrobněji a dokonce pomáhá rozhodnout, zda cesta přes toto úzké místo existuje či nikoliv. U dat s úzkými průchody najde navrhovaná metoda větší počet cest za kratší dobu. Pro data bez úzkých průchodů je navrhovaná metoda pomalejší, ale přesto poskytuje správné cesty. The paper introduces a new randomized sampling-based method of motion planning suitable for the problem of narrow passages. The proposed method was inspired by the method of exit points for cavities in protein models and is based on the Rapidly Exploring Random Tree (RRT). Unlike other methods, it can also provide locations of the exact positions of narrow passages. This information is extremely important as it helps to solve this part of space in more detail and even to decide whether a path through this bottleneck exists or not. For data with narrow passages, the proposed method finds more paths in a shorter time, for data without narrow passages, the proposed method is slower but still provides correct paths.

This paper describes various representations of the space of planes. The main focus is on the plane space representation in the symmetry plane detection in \(E^3\) where many candidate planes for many pairs of points of the given object are created and then the most often candidate is found as a mode in the candidate space, so-called Mode-based approach. The result depends on the representation used in the mode-seeking process. The most important aspect is how well distances in the space correspond to similarities of the actual planes with respect to the input object. So, we describe various usable distance functions and compare them both theoretically and practically. The results suggest that, when using the Mode-based approach, representing planes by reflection transformations is the best way but other simpler representations are applicable as well. On the other hand, representations using 3D dual spaces are not very appropriate. Furthermore, we introduce a novel way of representing the reflection transformations using dual quaternions.

In this paper, the shortest paths search for all departure times (profile search) are discussed. This problem is called a time-dependent shortest path problem (TDSP) and is suitable for time-dependent travel-time analysis. Particularly, this paper deals with the &epsilon, approximation of profile search computation. The proposed algorithms are based on a label correcting modification of Dijkstra&rsquo, s algorithm (LCA). The main idea of the algorithm is to simplify the arrival function after every relaxation step so that the maximum relative error is maintained. When the maximum relative error is 0.001, the proposed solution saves more than 97% of breakpoints and 80% of time compared to the exact version of LCA. Furthermore, the runtime can be improved by other 15% to 40% using heuristic splitting of the original departure time interval to several subintervals. The algorithms we developed can be used as a precomputation step in other routing algorithms or for some travel time analysis.

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. Proteiny mají složitou trojrozměrnou strukturu s dutinami a tunely v prostoru mezi atomy a tyto prostorové útvary jsou často velmi významné pro správnou biologickou funkci proteinu. Bylo vyvinuto mnoho diskrétních i analytických metod pro výpočet, vizualizaci a analýzu těchto prostorových útvarů. V tomto článku se zaměřujeme na propojení dutin s vnějším prostorem proteinu. Takové propojení by bylo normálně popsáno pomocí tunelů, ale počet takových řešení může být poměrně vysoký. Množina řešení pak vyžaduje netriviální ořezání, aby bylo dosaženo zobrazení jen několika reprezentativních řešení. Proto jsme navrhli alternativní typ prostorových útvarů, kterým říkáme exit regiony dutin. Tyto regiony zachycují kritické pozice, ve kterých sférická sonda, původně umístěná v nějaké dutině, dokáže bezkolizně opustit protein, pokud je jí dovoleno se zmenšovat. Tvar těchto exit regionů je více detailní než v případě jednoduchých kruhových profilů tunelů. Tunely, na druhou stranu, poskytují více informací o přesné cestě.

Simulation of age progression of 3D head models is an open problem in the field of computer graphics. Existing methods usually require a large set of training data, which may not be available. In this paper, a method for aging simulation of models created by deformation-based modeling is proposed that requires no training data. A user defines the position of wrinkles by selecting the position of endpoints of the desired wrinkles and the wrinkles are then generated using an erosion-inspired approach. The method can be used to simulate aging of any head model, however, if used for models created by deformations of a base model, the erosion factors can be calculated only for the base model and applied to the derived models. The results show that the approach is capable of creating visually plausible aged models.

In the field of 3D head modeling and animation, feature points are often needed to mark important regions of the face and can be used to animate or deform the input model. However, an automatic detection of features remains a challenging task. This paper presents a novel approach to feature detection based on curvature and its derived descriptors, such as shape index, curvedness and Willmore energy. Four important feature regions are detected using the proposed approach - eyes, nose, mouth, ears. For each region, feature points are detected. Results show that the feature points are detected with sufficient accuracy for further use.

This paper introduces a new method of planning paths for crowds, applicable to environments described by a graph. The main idea is to group members of the crowd by their common initial and target positions and then plan the path for one member of each group. If the crowd can be divided into a few groups this way, the proposed approach save a huge amount of computational and memory demands in dynamic environments.

This paper is focused on searching the shortest paths for all departure times (profile search). This problem is called a time-dependent shortest path problem (TDSP) and is important for optimization in transportation. Particularly this paper deals with the ε-approximation of TDSP. The proposed algorithm is based on a label correcting modification of Dijkstra's algorithm (LCA). The main idea of the algorithm is to simplify the arrival function after every relaxation step so that the maximum relative error is maintained. When the maximum relative error is 0.001, the proposed solution saves more than 95% of breakpoints and 80% time compared to the exact version of LCA. A more efficient precomputation step for another time-dependent routing algorithms can be built using the developed algorithm.

Registrace 3D objektů je náročný úkol, zejména pro modely obsahující symetrické částí. Registrační algoritmus založený na příznakových vektorech musí být schopen rozlišit levé a pravé části. Symetrická geometrie může být nalezena v těch dvou částech, nicméně, příznakové vektory v tomto případě obsahují stejné hodnoty ačkoli geometrie je ve skutečnosti jiná. Jednou z oblastí, kde tento problém vzniká, je registrace částečně překrývajících se částí lidských tváří nebo celých hlav. Symetrické části v tomto případě jsou často oči, uši, nozdry, koutky úst atd. Tento článek prezentuje modifikaci příznakového vektoru na základě toku vektorového pole a křivosti. Výsledky ukazují, že modifikovaný vektor může vylepšit následný registrační proces. Registration of 3D objects is a challenging task, especially in presence of symmetric parts. A registration algorithm based on feature vectors must be able to distinguish left and right parts. Symmetric geometry can be found in those two parts, however, most popular feature vectors produce equal numbers in this case, even though the geometry is in fact different. One field, where this problem arises, is the registration of partially overlapping parts of human faces or entire heads. The symmetric parts in this case are often eyes, ears, nostrils, mouth corners etc. Using symmetry-oblivious feature vectors makes it hard to distinguish left and right part of the face or head. This paper presents a feature vector modification based on a vector field flux and curvature. Results show that the modified feature vector can improve the subsequent registration process.

Simulace eroze je důležitým problémem v oblasti počítačové grafiky. Nejvýznamnějšími erozními procesy v přírodě jsou zvětrávání a hydraulická eroze. Mnoho metod řeší tyto problémy, ale jsou většinou založeny na výškových mapách nebo objemových datech. Výškové mapy neumožňují simulaci komplexních plně 3D scén, zatímco objemová data mají vysoké nároky na paměť. Navrhujeme sjednocený přístup pro zvětrávání a hydraulickou erozi pracující přímo na trojúhelníkových sítích, což zjednodušuje použití metody v široké škále scénářů. Bereme v úvahu fakt, že rychlost eroze v přírodě je ovlivněna lokálním tvarem erodovaného objektu. Pro odhad rychlosti eroze používáme odhad průměrné křivosti, což má za následek vizuálně věrohodnou simulaci erozních procesů. Výsledky metody demonstrujeme na umělých 3D modelech i na reálných datech. The significant properties of the maximum likelihood (ML) estimate are consistency, normality, and efficiency. While it has been proven that these properties are valid when the sample size approaches infinity, the behavior of an ML estimator when working with small sample sizes is largely unknown. However, in real tasks, we usually do not have sufficient data to completely fulfill the conditions of an optimal ML estimate. The question arises as to what amount of data is required to be able to estimate a Gaussian model that provides sufficiently accurate likelihood estimates. This issue is addressed with respect to the number of dimensions of the pattern space.

Grafy sousednosti (proximity), jako je graf nejbližších sousedů, nejbližší dvojice, graf relativního sousedství a graf k nejbližších sousedů jsou nástroje užitečné v mnoha problémech, kde se zkoumají vzájemné vztahy, podobnost a blízkost objektů. Článek se věnuje vztahu grafů sousednosti k lokálně minimální triangulaci (LMT) a ukazuje, že ve většině případů LMT obsahuýje všechny hrany Neighbourhood (or proximity) graphs, such as nearest neighbour graph, closest pairs, relative neighbourhood graph and k-nearest neighbour graph are useful tools in many tasks inspecting mutual relations, similarity and closeness of objects. Some of neighbourhood graphs are subsets of Delaunay triangulation (DT) and this relation can be used for efficient computation of these graphs. This paper concentrates on relation of neighbourhood graphs to the locally minimal triangulation (LMT) and shows that, although generally these graphs are not LMT subgraphs, in most cases LMT contains all or many edges of these graphs. This fact can also be used for the neighbourhood graphs computation, namely in kinetic problems, because LMT computation is easier.

Haptic devices are nowadays gaining popularity because of their increasing availability. These special input/output devices provide, unlike mouse or keyboard, a native 3D manipulation, especially a more precise control and a force interaction. With more accurate description of the model, haptics can achieve more realistic force feedback. Therefore, triangulated surface models are often used for an authentic interpretation of 3D models. A common task in haptic visualization using triangulated surface models is to find a triangle which is in the collision trajectory of the haptic probe. Since the render rate of the haptic visualization is relatively high (usually about 1kHz), the task becomes highly non-trivial for complex mesh models, especially for the meshes which are changing over time. The paper presents a fast and novel location algorithm able to find the triangle which is close to the haptic probe and in the direction of the probe motion vector. The algorithm has negligible additional memory requirements, since it does not need additional searching data structures and uses only the information usually available for triangulated models. Therefore, the algorithm could handle even triangular meshes changing over time. Results show that the proposed algorithm is fast enough to be used in haptic visualization of complex-shaped models with hundreds of thousands of triangles.

Geometric models of molecular structures are often described as a set of balls, where balls represent individual atoms. The ability to describe and explore the empty space among these balls is important, e.g., in the analysis of the interaction of enzymes with substrates, ligands and solvent molecules. Voronoi diagrams from the field of computational geometry are often used here, because they provide a mathematical description of how the whole space can be divided into regions assigned to individual atoms. This paper introduces a combination of two different types of Voronoi diagrams into a new hybrid Voronoi diagram - one part of this diagram belongs to the additively weighted (aw-Voronoi) diagram and the other to the power diagram. The boundary between them is controlled by a user-defined constant (the probe radius). Both parts are computed by different algorithms, which are already known. The reduced aw-Voronoi diagram is then obtained by removing the power diagram part from the hybrid diagram. Reduced aw-Voronoi diagrams are perfectly tailored for the analysis of dynamic molecular structures, their computation is faster and storage requirements are lower than in the case of complete aw-Voronoi diagrams. Here, we showed their application to key proteins in cancer research such as p53 and ARID proteins as case study. We identified a biologically relevant cavity in p53 structural ensembles generated by molecular dynamics simulations and analyzed its accessibility, attesting the potential of our approach. This method is relevant for cancer research since it permits to depict a dynamical view of cavities and pockets in proteins that could be affected by mutations in the disease. Our approach opens novel prospects for the study of cancer-related proteins by molecular simulations and the identification of novel targets for drug design.

A pseudo-triangulation is a planar subdivision into polygons with three convex vertices, useful for ray shooting, visibility problems and kinetic collision detection. As pseudo-triangulations are quite young, there is a lack of specialized algorithms for them. In this paper, we address the question of location in pseudo-triangulations. We propose two location algorithms based on the so-called stochastic walk and present their experimental results. The class of walk location algorithms is very popular for triangulations, namely in engineering applications, due to simplicity and low memory requirements, in spite of their non-optimality. As far as we know, no walk algorithm specialized on pseudo-triangulations has been developed before.

Morphing is a shape transformation where the shape of one object is deformed to the shape of the other object. It is used as an animation or a modeling technique. Classical morphing operates between two input objects but this concept can be extended to multiple input objects - the so called multimorphing. Shapes generated by the multimorphing form a space of shapes motivated by an affine space. Besides the analogy with an affine space we also introduce an inner product and a concept of an orthogonal projection. We also show how to explore space of shapes and how to systematically generate new shapes. The paper focuses on the boundary representation, although some ideas are more general and can be used for other representations, too.

Curvature is an important geometric property in computer graphics that provides information about the behavior of object surfaces. The exact curvature can only be calculated for a limited set of surfaces description. Most of the time, we deal with triangles, point sets or some other discrete representation of the surface. For those, curvature computation is problematic. Moreover, most of existing algorithms were developed for static geometry and can be slow for interactive modeling. This paper proposes a screen space method which estimates the mean and Gaussian curvature at interactive rates. The algorithm uses positions and normals to estimate the curvature from the second fundamental form matrix. Using the screen space has advantages over the classical approach: low-poly geometry can be used and additional detail can be added with normal and bump maps. The screen space curvature can be easily added to existing rendering pipelines. The proposed algorithm was tested on several models and it outperforms current state-of-the-art GPU approaches.

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 popular approach is stripification, i.e., a conversion of a triangulated object surface into strips of triangles. This enables a reduction of the rendering time by reducing the data size which avoids redundant lighting and transformation computations. The problem of finding an optimal decomposition of triangle surface models to a set of strips is NP-hard and there exist a lot of different heuristic stripification techniques. This paper should help to orient in the jungle of stripification algorithms. We present an overview of existing stripification methods and detailed description of several important stripification methods for fully triangulated meshes. As different authors usually use different data sets and different architectures, it is nearly impossible to compare the quality of stripification methods. For this reason we also present a set of tests of these methods to give the reader a better possibility to compare these methods.

Delaunay triangulation construction is one of the fundamental problems we are facing in computer graphics and computational geometry. As a result, many solutions have been developed, incremental insertion being one of the most popular algorithms. Although it is not worst-case optimal, it is simple, robust and behaves well in expected time. This paper suggests two improvements to the algorithm. The first one speeds up the computation without increasing memory requirements. The second refinement decreases memory requirements, trading space for small slow down. Both improvements are easy to implement and can be used either side-by-side or each of them independently.

Applications such as video games or movies often contain deforming meshes. The most-commonly used representation of these types of meshes consists in dense polygonal models. Such a large amount of geometry can be efficiently managed by applying level-of-detail techniques and specific solutions have been developed in this field. However, these solutions do not offer a high performance in real-time applications. We thus introduce a multiresolution scheme for deforming meshes. It enables us to obtain different approximations over all the frames of an animation. Moreover, we provide an efficient connectivity coding by means of triangle strips as well as a flexible framework adapted to the GPU pipeline. Our approach enables real-time performance and, at the same time, provides accurate approximations.

Given a finite point set in R3 scanned by special devices from the object surface, a surface model interpolating or approximating the points set has to be obtained. We use for the reconstruction a CRUST algorithm by Nina Amenta, which selects surface triangles from the Delaunay tetrahedronization using information from the dual Voronoi diagram. This set of candidate surface triangles does not form a manifold, so the manifold extraction step is necessary. We present two improvements for this step, the former is limited to the used algorithm and the latter can be used with any other reconstruction algorithm.

Automatic computation of contour lines on a triangulation is a difficult problem because due to input data digitization and the type of triangulation used, some triangles can be a source of a strange behaviour of the contour lines. In this paper, we show what problems can appear in contour lines when Delaunay or greedy triangulations are used and how the contour lines can be improved using constraints in the triangulation. We improved contour lines by manually imposing constraints in a triangulation editing program. Automation of this process is a next step of our work.

The paper describes a modification of DAG-based location for incremental insertion Delaunay triangulation algorithm in E2 and E3. Instead of the whole simplices, only their separating faces are stored and tested. The proposed technique allows full reuse of results obtained on previous DAG levels. This enables to reduce time for point location and memory requirements. Asymptotic memory and time complexity is not changed.

One of the methods for 3D data model acquisition is real object digitisation followed by surface reconstruction. Many algorithms have been developed to do this, each with its advantages and disadvantages. We use for the reconstruction a CRUST algorithm by Nina Amenta, which selects surface triangles from the Delaunay tetrahedronisation using information from the dual Voronoi diagram. Unfortunately, these candidate surface triangles do not form a manifold, so it is necessary to perform some other steps for manifold extraction. In this paper, we present some observations and modifications for this step, which improve the quality of the resulting mesh especially in the case, when the surface contains boundaries.

The point location problem is one of the most frequent tasks in computational geometry. The walking algorithms are one of the most popular solutions for finding an element in a mesh which contains a query point. Despite their suboptimal complexity, the walking algorithms are very popular because they do not require any additional memory and their implementation is simple. This paper describes the modifications of two walking algorithms for point location on a surface of a star-shaped polyhedron, a generalization of the Remembering Stochastic walk algorithm for a star-shaped polyhedron and a modification of the planar Orthogonal walk algorithm. The latter uses spherical coordinates to transfer the spatial point location problem to the planar point location problem. This way, the problem can be solved by the traditional planar algorithms. Along with the modifications, the paper proposes new methods for finding a proper starting triangle for the walking process with or without preprocessing.

Triangular meshes are important in many fields in both basic and applied research that rely on their correctness and accuracy. Many operations with meshes can lead to undesirable situations and the resulting models can be damaged and further unusable. Self-intersection and mesh-to-mesh intersection are types of operations that are often present and can cause such problems. We propose an accurate geometry-based method for local repair of intersecting meshes. The state-of-the-art methods either solve the problem inaccurately, or use methods such as arbitrary precision arithmetic or virtual perturbation to deal with the troublesome boundary cases. Our method represents a robust way to repair intersecting meshes accurately without the need to manipulate with the input data or to employ arbitrary precision arithmetic. The correct solution is obtained through a careful classification of the cases that could result from a numerical imprecision of the floating point arithmetic.