9297752
Edge insertion for optimal triangulations
Edge insertion iteratively improves a triangulation of a finite point set in ℜ2 by adding a new edge, deleting old edges crossing the new edge, and retriangulating the polygonal regions on either side of the new edge. This paper presents an abstract view of the edge insertion paradigm, and then shows that it gives polynomial-time algorithms for several types of optimal triangulations, including minimizing the maximum slope of a piecewise-linear interpolating surface.
12046561
An upper bound for conforming Delaunay triangulations
A plane geometric graph <italic>C</italic> in <italic>R</italic><supscrpt>2</supscrpt> <italic>conforms</italic> to another such graph <italic>G</italic> if each edge of <italic>G</italic> is the union of some edges of <italic>C</italic>. It is proved that for every <italic>G</italic> with <italic>n</italic> vertices and <italic>m</italic> edges, there is a completion of a Delaunay triangulation of O(<italic>m</italic><supscrpt>2</supscrpt><italic>n</italic>) points that conforms to <italic>G</italic>. The algorithm that constructs the points is also described.
14857874
Anti-aliasing and Continuity with Trapezoidal Shadow Maps
This paper proposes a new shadow map technique termed trapezoidal shadow maps to calculate high quality shadows in real-time applications. To address the resolution problem of the standard shadow map approach, our technique approximates the eye's frustum as seen from the light with a trapezoid to warp it onto a shadow map. Such a trapezoidal approximation, which may first seem straightforward, is carefully designed to achieve the goal of good shadow quality for objects from near to far, and to address the continuity problem that is found in all existing shadow map approaches. The continuity problem occurs mainly when the shadow map quality changes significantly from frame to frame due to the motion of the eye or the light. This results in flickering of shadows. On the whole, our proposed approach is simple to implement without using complex data structures and it maps well to graphics hardware as shown in our experiments with large virtual scenes of hundreds of thousands to over a million of triangles.
7282879
Jump flooding in GPU with applications to Voronoi diagram and distance transform
This paper studies jump flooding as an algorithmic paradigm in the general purpose computation with GPU. As an example application of jump flooding, the paper discusses a constant time algorithm on GPU to compute an approximation to the Voronoi diagram of a given set of seeds in a 2D grid. The errors due to the differences between the approximation and the actual Voronoi diagram are hardly noticeable to the naked eye in all our experiments. The same approach can also compute in constant time an approximation to the distance transform of a set of seeds in a 2D grid. In practice, such constant time algorithm is useful to many interactive applications involving, for example, rendering and image processing. Besides the experimental evidences, this paper also confirms quantitatively the effectiveness of jump flooding by analyzing the occurrences of errors. The analysis is a showcase of insights to the jump flooding paradigm, and may be of independent interests to other applications of jump flooding.
7171205
An optimal bound for high-quality conforming triangulations
AbstractThis paper shows that, for any plane geometric graph
$$\mathcal{G}$$
 withn vertices, there is a triangulation
$$\mathcal{T}$$
 that conforms to
$$\mathcal{G}$$
, i.e., each edge of
$$\mathcal{G}$$
 is the union of some edges of
$$\mathcal{T}$$
, where
$$\mathcal{T}$$
 hasO(n2) vertices with each angle of its triangles measuring no more than 11/15π. Additionally,
$$\mathcal{T}$$
 can be computed inO(n2 logn) time.
386735
Variants of Jump Flooding Algorithm for Computing Discrete Voronoi Diagrams
Jump flooding algorithm (JFA) is an interesting way to utilize the graphics processing unit to efficiently compute Voronoi diagrams and distance transforms in 2D discrete space. This paper presents three novel variants of JFA. They focus on different aspects of JFA: the first variant can further reduce the errors of JFA; the second variant can greatly increase the speed of JFA; and the third variant enables JFA to compute Voronoi diagrams in 3D space in a slice-by-slice manner, without a high end graphics processing unit. These variants are orthogonal to each other. In other words, it is possible to combine any two or all of them together.
10936404
Affine invariant texture signatures
We develop a new approach for texture classification independent of affine transforms. Based on a spectral representation of texture images under affine transform, anisotropic scale invariant signatures of the orientation spectrum distribution are extracted. A peaks distribution vector (PDV) obtained on the distribution of these signatures captures texture properties invariant to affine distortion. The PDV is used to measure the similarity between textures. Experimental results show the efficiency of the PDV for affine invariant texture classification.
11321791
A new face detection method based on shape information
Automatic detection of human faces is one of the most difficult problems in pattern recognition. In many practical applications (e.g. personal identification using photo-IDs), face images often have a simple background. In this paper, we propose a new method based on shape information. Our system can be very efficient for images with simple background. Input image is first enhanced by means of histogram equalization, followed by edge detection based on a multiple-scale filter. The extracted edges are then linked using a method based on an energy function. The face contour is finally extracted using the direction information of the linked edges. Experimental results are included to verify the effectiveness of this method. (C) 2000 Elsevier Science B.V. All rights reserved.
625121
A comprehensive high-level synthesis system for control-flow intensive behaviors
In this paper, we describe a comprehensive high-level synthesis system for control-flow intensive as well as data-dominated behaviors. We propose a new control-data flow graph model to preserve the parallelism inherent in the application, as well as to facilitate high-level synthesis. Our algorithm, which is based on an iterative improvement strategy, performs clock selection, scheduling, module selection, resource allocation and assignment simultaneously to fully derive the benefits of design space exploration at the behavior level. The system can be used to optimize area, power or energy, by selecting the cost function accordingly. Experimental results show that for energy-optimized designs, energy is reduced by up to 79.4% (an average of 42.2%), with an average of 24.8% area overhead, compared to area-optimized designs. For power-optimized designs, power is reduced by up to 70.8% (an average of 56.7%), with an average of 25.2% area overhead, compared to area-optimized designs. No Vdd scaling is performed to obtain the above results.
8559676
A simulation framework for energy-consumption analysis of OS-driven embedded applications
Energy consumption has become a major focus in the design of embedded systems (e.g., mobile computing and wireless communication devices). In particular, a shift of emphasis from hardware-oriented low-energy design techniques to energy-efficient embedded software design has occurred progressively in the past few years. To that end, various techniques have been developed for the design of energy-efficient embedded software. In operating system (OS)-driven embedded systems, the OS has a significant impact on the system's energy consumption directly (energy consumption associated with the execution of the OS functions and services), as well as indirectly (interaction of the OS with the application software). As a first step toward designing energy-efficient OS-based embedded systems, it is important to analyze the energy consumption of embedded software by taking the OS energy characteristics into account. To facilitate such studies, we present, in this work, an energy simulation framework that can be used to analyze the energy consumption characteristics of an embedded system featuring the embedded Linux OS running on the StrongARM processor. The framework allows software designers to study the energy consumption of the system software in relation to the application software, identify the energy hot spots, and perform design changes based on the knowledge of the OS energy consumption characteristics as well as application-OS interactions.
2598412
Embedded operating system energy analysis and macro-modeling
A large and increasing number of modern embedded systems are subject to tight power/energy constraints. It has been demonstrated that the operating system (OS) can have a significant impact on the energy efficiency of the embedded system. Hence, analysis of the energy effects of the OS is of great importance. Conventional approaches to energy analysis of the OS (and embedded software, in general) require the application software to be completely developed and integrated with the system software, and that either measurement on a hardware prototype or detailed simulation of the entire system be performed. Since this process requires significant design effort, unfortunately, it is typically too late in the design cycle to perform high-level or architectural optimizations on the embedded software, restricting the scope of power savings. Our work recognizes the need to provide embedded software designers with feedback about the effect of different OS services on energy consumption early in the design cycle. As a first step in that direction, this paper presents a systematic methodology to perform energy analysis and macro-modeling of an embedded OS. Our energy macro-models provide software architects and developers with an intuitive model for the OS energy effects, since they directly associate energy consumption with OS services and primitives that are visible to the application software. Our methodology consists of (i) an analysis stage, where we identify a set of energy components, called energy characteristics, which are useful to the designer in making OS-related design trade-offs, and (ii) a subsequent macromodeling stage, where we collect data for the identified energy components and automatically derive macro-models for them. We validate our methodology by deriving energy macro-models for two state-of-the-art embedded OS's, /spl mu/C/OS and Linux OS.