Issue 4 https://diglib.eg.org:443/handle/10.2312/51 Regular Issue 2020-03-04T15:46:03Z An Efficient Adaptive Algorithm for Constructing the Convex Differences Tree of a Simple Polygon https://diglib.eg.org:443/handle/10.2312/6812 An Efficient Adaptive Algorithm for Constructing the Convex Differences Tree of a Simple Polygon Rappoport, Ari The convex differences tree (CDT) representation of a simple polygon is useful in computer graphics, computer vision, computer aided design and robotics. The root of the tree contains the convex hull of the polygon and there is a child node recursively representing every connectivity component of the set difference between the convex hull and the polygon. We give an O(n log K + K log2 n) time algorithm for constructing the CDT, where n is the number of polygon vertices and K is the number of nodes in the CDT. The algorithm is adaptive to a complexity measure defined on its output while still being worst case efficient. For simply shaped polygons, where K is a constant, the algorithm is linear. In the worst case K = O(n) and the complexity is O(n log2 n). We also give an O(n log n) algorithm which is an application of the recently introduced compact interval tree data structure. 1992-01-01T00:00:00Z A New Two Dimensional Line Clipping Algorithm for Small Windows https://diglib.eg.org:443/handle/10.2312/6813 A New Two Dimensional Line Clipping Algorithm for Small Windows Day, J. D. A new algorithm for clipping lines against rectangular windows is described. It is suitable for computations in both object space (floating point arithmetic) and image space (integer arithmetic). The algorithm is compared with other object and image space algorithms and shown to be superior for small windows. 1992-01-01T00:00:00Z X: Why Z? https://diglib.eg.org:443/handle/10.2312/6811 X: Why Z? Bowen, Jonathan P. Window management systems are now used extensively for user interfaces to computer systems. In particular, X11 has come to dominate the workstation market as a widely accepted industry standard on many different hardware platforms. However, no formal standard currently exists for this window system, both in terms of an international standards body (although this is being addressed), and in terms of a precise (mathematical) specification of what the interface is intended to do. This paper advocates the use of a formal notation to describe such an important system to avoid ambiguity and undesired or unintended variations between different implementations of the same system.Theformal notation used for demonstration purposes, Z, is based on set theory, and has been developed at the Programming Research Group in Oxford. 1992-01-01T00:00:00Z Performance of Space Subdivision Techniques in Ray Tracing https://diglib.eg.org:443/handle/10.2312/6810 Performance of Space Subdivision Techniques in Ray Tracing McNeill, M. D. J.; Shah, B. C.; Hebert, M.-P.; Lister, P. F.; Grimsdale, R. L. Whilst providing images of excellent quality, ray tracing is a computationally intensive task. The first part of this paper compares the speed-up achieved in ray tracing using various space subdivision algorithms and discusses the implications of implementing the algorithms on parallel processing systems. The second part addresses the problem of building the data structure within the rendering process, a situation which occurs when the rendering process is parallelised and dynamic scenes are rendered. Greater performance can be achieved with dynamic structure building compared to creation of the structure prior to rendering. The dynamic building algorithm proposed reduces the building time and storage cost of space subdivision structures, and decreases the data structure creation-render cycle time, thus enhancing image parallelism performance. 1992-01-01T00:00:00Z