Research On Stochastic Clustered-Dot Screen And Path Planning Based On Voronoi

The Voronoi diagram is a very important geometric structure and a very important research topic in computational geometry. A Voronoi diagram records the regions in the proximity of a set of generators. These regions called Voronoi region. Each Voronoi region corresponds to a generator, and these Voronoi regions are not overlapped. According to whether the Voronoi regions are adjacent, we can define the adjacent relationship between the generators of the Voronoi diagram. Because the Voronoi diagram has many fine features, such as proximity and adjacency, and has a systematic theory basis, it has been widely used in many research areas, for example computer graphics, mechanical engineering, virtual reality, GIS, robotics, image processing, CAD etc., and it is also an effective tool to solve other problems in computational geometry, such as collision detection, path planning and so on. We do research on path planning, algorithm for building stochastic clustered-dot screens based on Voronoi diagram in this paper.The problem of path planning we studied in this paper is based on the roving in the virtual museum. Roving among the virtual environment has two ways. One is roving along the regular path; the other is roving by an interactive style. In traditional 3D scene, visitors usually can only choose the simplest browse mode that is using direction keys in keyboard or mouse to control the ongoing direction. Such walkthrough methods lack of flexibility. The interaction between users and system is rather tedious. In the way of roving along the regular path, the system designer should design some basic paths which can be selected by users when roving in advance. In this way users can take part in the processing of path planning limited. Since we're planning to research the path planning methods in the virtual museum, in which the Voronoi diagram is as the basic data structure, so this paper focuses on how to design the roving path efficiently and rapidly in the case of knowing the simple polygon's Voronoi diagram in advance. This paper presents three new path planning methods based on Voronoi diagram, i.e. offset path, skeleton path and the shortest path. These methods make the interactive process between user and system concise, easy to operate, and flexible, and may satisfy users' different visit needs.Particularly, the shortest path planning problem refers to the shortest path computing in the plane. The Euclidean shortest path problem is one of best-know problems in computational geometry. There are many possible versions of the problem, for example, the obstacles are polygons, disks, or the moving object is a point, a polygon, a disk and so on. This paper focuses on what is perhaps the simplest: querying a shortest path SP(s,t) between two points s and t in a simple polygon P in the plane. Most algorithms are based on the classical Dijkstra algorithm. This algorithm can compute the optimism solution, but have low efficiency. In the worst case, the Dijkstra algorithm need O(n~2) time to compute the solution.In addition, how to reproduce continuous tone image with hundreds of gray levels and millions of colors using only one or limit colors is really a difficult but basically problems in the print. In the industrial, people use screens to transfer continuous tone image in to halftoning image. Traditional Amplitude Modulation screens (AM) use different angle and frequency to different color layers. In this method the size of dot is different and disposed orderly, however, this method lead to periodic patterns, moreover when different color layers are disposed together, may generate moires. Frequency Modulated screens (FM), also called stochastic screens, may generate finer dots then AM, and generate no moires when more than three layer disposed together. And the images produced by this method have better tone reproduction and smoother grayscale transition. In this paper, a GPU-based algorithm for building stochastic clustered-dot screens is proposed. In a halftone image generated by our method, the details and highlight part can be better expressed than traditional methods. And our method can generate screens faster and with less memory than traditional algorithms. Moreover, by changing the disk radius, the screen dot size can be adapted to the characteristics of particular printing devices. The controbution of this thesis are:1. This paper proposesa new algorighm for querying the shortest path between two points s and t in a simple polygon P based on Voronoi diagram. Based on the polygon's Voronoi diagram, we first find the Voronoi skeleton path S(s,t) from point s to t, and then along wich we compute the shortest path SP(s,t) by visibility computing simultaneously. SP(s,t) can be reported in time O(n).2. This paper presents three new path planning methods based on Voronoi diagram, i.e. offset path, skeleton path and the shortest path. Especially, the offset path method based on polygon's offset curves, which support user to visit the whole scene with one's favorable visual angle; the skeleton path based on Voronoi skeleton, which supports user to select the destination interactively, and then the system generates the path automatically; the shortest path can be got through computing visibility along the skeleton path. Using the shortest path, user can go to the destination through the shortest distance. These three path planning methods have some advantages that the interactive process is concise, easy to operate, flexible, and may satisfy users' different visit needs.3. In this paper, a GPU-based algorithm for building stochastic clustered-dot screens is proposed. In the algorithm, after stochastically laying screen dot centers within a large dither matrix, Voronoi diagram is constructed to obtain the region of each screen dot, which is implemented with GPU. Then, each screen dot's region is filled to get the stochastic clustered-dot screens, where a better gray density filling method that can be implemented easily on GPU is used. The details and highlight part can be better expressed in the images generated by our method than images generated by traditional methods. And our method can generate screens faster and with less memory than traditional algorithms. Moreover, by changing the disk radius, the screen dot size can be adapted to the characteristics of particular printing devices.The research work researched by this paper can be used in our software systems ICAPD (Integrated Computer Aided Patterns Design and Plate-making System) and Digital Museum Application Supporting System, and has certain academic and practical meanings.