We propose the first GPU algorithm for the 3D constrained Delaunay refinement problem. For an input of a piecewise linear complex G and a constant B, it produces, by adding Steiner points, a constrained Delaunay triangulation conforming to G and containing tetrahedra mostly with radiusedge ratios smaller than B. Our implementation of the algorithm shows that it can be an order of magnitude faster than the best CPU software while using similar quantities of Steiner points to produce triangulations of comparable qualities. It thus reduces the computing time of triangulation refinement from possibly an hour to a few seconds or minutes for possible use in interactive applications.

We propose the first working GPU algorithm for the 2D Delaunay refinement problem. Our algorithm adds Steiner points to an input planar straight line graph (PSLG) to generate a constrained Delaunay mesh with triangles having no angle smaller than an input θ. It is shown to run from a few times to an order of magnitude faster than the well-known Triangle software, which is the fastest CPU Delaunay mesh generator. Our implementation handles degeneracy and is numerically robust. It is proven to terminate with finite output size for an input PSLG with no angle smaller than 60° and θ ≥ 20.7°. In addition, we notice meshes generated by our algorithm are of similar sizes to that by Triangle, which has incorporated good consideration in keeping output small in size.

Flip is a simple and local operation to transform one triangulation to another. It makes changes only to some neighboring simplices, without considering any attribute or configuration global in nature to the triangulation. Thanks to this characteristic, several flips can be independently applied to different small, non-overlapping regions of one triangulation. Such operation is favored when designing algorithms for data-parallel, massively multithreaded hardware, such as the GPU. However, most existing flip algorithms are designed to be executed sequentially, and usually need some restrictions on the execution order of flips, making them hard to be adapted to parallel computation. In this paper, we present an in depth study of flip algorithms in low dimensions, with the emphasis on the flexibility of their execution order. In particular, we propose a series of provably correct flip algorithms for regular triangulation and convex hull in 2D and 3D, with implementations for both CPUs and GPUs. Our experiment shows that our GPU implementation for constructing these structures from a given point set achieves up to two orders of magnitude of speedup over other popular single-threaded CPU implementation of existing algorithms.

We propose the first algorithm to compute the 3D Delaunay triangulation (DT) on the GPU. Our algorithm uses massively parallel point insertion followed by bilateral flipping, a powerful local operation in computational geometry. Although a flipping algorithm is very amenable to parallel processing and has been employed to construct the 2D DT and the 3D convex hull on the GPU, to our knowledge there is no such successful attempt for constructing the 3D DT. This is because in 3D when many points are inserted in parallel, flipping gets stuck long before reaching the DT, and thus any further correction to obtain the DT is costly. In contrast, we show that by alternating between parallel point insertion and flipping, together with picking an appropriate point insertion order, one can still obtain a triangulation very close to Delaunay. We further propose an adaptive star splaying approach to subsequently transform this result into the 3D DT efficiently. In addition, we introduce several GPU speedup techniques for our implementation, which are also useful for general computational geometry algorithms. On the whole, our hybrid approach, with the GPU accelerating the main work of constructing a near-Delaunay structure and the CPU transforming that into the 3D DT, outperforms all existing sequential CPU algorithms by up to an order of magnitude, in both synthetic and real-world inputs. We also adapt our approach to the 2D DT problem and obtain similar speedup over the best sequential CPU algorithms, and up to 2 times over previous GPU algorithms.

Flipping is a local and efficient operation to construct the convex hull in an incremental fashion. However, it is known that the traditional flip algorithm is not able to compute the convex hull when applied to a polyhedron in R3. Our novel Flip-Flop algorithm is a variant of the flip algorithm. It overcomes the deficiency of the traditional one to always compute the convex hull of a given star-shaped polyhedron with provable correctness. Applying this to construct convex hull of a point set in R3, we develop ffHull, a flip algorithm that allows nonrestrictive insertion of many vertices before any flipping of edges. This is unlike the well-known incremental fashion of strictly alternating between inserting a single vertex and flipping. The new approach is not only simpler and more efficient for CPU implementation but also maps well to the massively parallel nature of the modern GPU. As shown in our experiments, ffHull running on the CPU is as fast as the best-known convex hull implementation, qHull. As for the GPU, ffHull also outperforms all known prior work. From this, we further obtain the first known solution to computing the 2D regular triangulation on the GPU.

A novel algorithm is presented to compute the convex hull of a point set in ℝ 3 using the graphics processing unit (GPU). By exploiting the relationship between the Voronoi diagram and the convex hull, the algorithm derives the approximation of the convex hull from the former. The other extreme vertices of the convex hull are then found by using a two-round checking in the digital and the continuous space successively. The algorithm does not need explicit locking or any other concurrency control mechanism, thus it can maximize the parallelism available on the modern GPU. The implementation using the CUDA programming model on NVIDIA GPUs is exact and efficient. The experiments show that it is up to an order of magnitude faster than other sequential convex hull implementations running on the CPU for inputs of millions of points. The works demonstrate that the GPU can be used to solve nontrivial computational geometry problems with significant performance benefit.

We propose the first graphics processing unit (GPU) solution to compute the 2D constrained Delaunay triangulation (CDT) of a planar straight line graph (PSLG) consisting of points and edges. There are many existing CPU algorithms to solve the CDT problem in computational geometry, yet there has been no prior approach to solve this problem efficiently using the parallel computing power of the GPU. For the special case of the CDT problem where the PSLG consists of just points, which is simply the normal Delaunay triangulation (DT) problem, a hybrid approach using the GPU together with the CPU to partially speed up the computation has already been presented in the literature. Our work, on the other hand, accelerates the entire computation on the GPU. Our implementation using the CUDA programming model on NVIDIA GPUs is numerically robust, and runs up to an order of magnitude faster than the best sequential implementations on the CPU. This result is reflected in our experiment with both randomly generated PSLGs and real-world GIS data having millions of points and edges.

We propose the first GPU solution to compute the 2D constrained Delaunay triangulation (CDT) of a planar straight line graph (PSLG) consisting of points and edges. There are many CPU algorithms developed to solve the CDT problem in computational geometry, yet there has been no known prior approach using the parallel computing power of the GPU to solve this problem efficiently. For the special case of the CDT problem with a PSLG consisting of just points, which is the normal Delaunay triangulation problem, a hybrid approach has already been presented that uses the GPU together with the CPU to partially speed up the computation. Our work, on the other hand, accelerates the whole computation by the GPU. Our implementation using the CUDA programming model on NVIDIA GPUs is numerically robust with good speedup, of up to an order of magnitude, compared to the best sequential implementations on the CPU. This result is reflected in our experiment with both randomly generated PSLGs and real world GIS data with millions of points and edges.

We present a novel approach, termed gHull, to compute the convex hull for a 3D point set using the GPU. We exploit the fast computation of the digital Voronoi diagram and its relationship with the convex hull to compute the answer from the former rather than directly. Our algorithm is robust, while able to maximizes the parallelism available in the GPU to achieve significant speed up.

We propose a Parallel Banding Algorithm (PBA) on the GPU to compute the exact Euclidean Distance Transform (EDT) for a binary image in 2D and higher dimensions. Partitioning the image into small bands to process and then merging them concurrently, PBA computes the exact EDT with optimal linear total work, high level of parallelism and a good memory access pattern. This work is the first attempt to exploit the enormous power of the GPU in computing the exact EDT, while prior works are only on approximation. Compared to these other algorithms in our experiments, our exact algorithm is still a few times faster in 2D and 3D for most input sizes. We illustrate the use of our algorithm in applications such as computing the Euclidean skeleton using the integer medial axis transform, performing morphological operations of 3D volumetric data, and constructing 2D weighted centroidal Voronoi diagrams.

10.1145/1342250.1342264

This paper proposes a novel model-guided segmentation framework utilizing a statistical surface wavelet model as a shape prior. In the model building process, a set of training shapes are decomposed through the subdivision surface wavelet scheme. By interpreting the resultant wavelet coefficients as random variables, we compute prior probability distributions of the wavelet coefficients to model the shape variations of the training set at different scales and spatial locations. With this statistical shape model, the segmentation task is formulated as an optimization problem to best fit the statistical shape model with an input image. Due to the localization property of the wavelet shape representation both in scale and space, this multi-dimensional optimization problem can be efficiently solved in a multiscale and spatial-localized manner. We have applied our method to segment cerebral caudate nuclei from MRI images. The experimental results have been validated with segmentations obtained through human expert. These show that our method is robust, computationally efficient and achieves a high degree of segmentation accuracy.

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.

This paper studies the usage of the GPU as a collection of groups of related processing units, where each group communicates in some way to complete a computation efficiently and effectively. In particular, we use the GPU to perform jump flooding to pass information among groups of processing units in the design of two simple real-time soft shadow algorithms. These two algorithms are purely image-based in generating plausible soft shadows. Their computational costs depend mainly on the resolution of the shadow map or the screen. They run on an order of magnitude faster than existing comparable methods.

This paper studies pre-fetching mechanisms that support walkthroughs of virtual environments with overall data sizes exceeding current core memory capacities of PCs. Specifically, it formulates the pre-fetch problem using motion characteristics of the viewer, the data density of the virtual environment, and the data transfer capability of the disk. It further analyzes two fundamental classes of pre-fetching schemes, which are classified by their uses of certain pre-assigned spatial or temporal thresholds. The analysis is supported and verified by experiments on terrain walkthroughs performed on different configurations of PCs. An interesting finding is the understanding of how the terrain data density supportable is a function of the duration of time allocated to disk-level pre-fetching. On the whole, this paper provides a methodology for analyzing prefetch performance as well as presents insights instrumental in the design and optimization of out-of-core walkthrough systems.

This paper presents an effective approach to generate a set of small textures from an input texture that can be tiled together to synthesize large textures. Such a small set can be useful in texturing any large area realistically and efficiently while consuming only a small amount of texture memory. Our approach is advantageous in its ability to generate a smaller number of tiles that can embed much more texture patterns and with less conspicuous seams within each tile than earlier approaches. As a result, our approach can generate large textures that look as if each were from a continuous part of the input texture while avoiding highly repetitive patterns. In general, our approach performs very well and shows a particular strength, compared to earlier approaches, for input textures of elaborate or relatively large features, or with distinctive colors.

Bridging the modeling and rendering gap between the existing triangle and point primitives, we explore the use of line segments as a new primitive to represent and render 3D models. Our main contribution extends the anti-aliasing theory in texture mapping to anti-aliased line segment rendering, and presents an approximation algorithm to render high quality anti-aliased opaque and transparent line segments in 3D models. This antialiasing technique is empirically validated by building a software pipeline to render models of any combination of the three types of modeling primitives: triangles, line segments and points. Our experiment shows that models comprising line segments are generally more efficient and effective for high quality rendering as compared to their corresponding pure point models.

Although edge detectors are useful for delineating the road areas in an image, no previous work in road extraction has demonstrated a comprehensive use of edge information. In this paper we propose a semi-automatic scheme that makes use of edge information to extract roads in high-resolution satellite images. A novel edge thinning and division algorithm is first applied to process edges in an image. With such processed edges, texture information, color information together with the user assistance, the proposed scheme is able to extract roads from an image with high reliability. This scheme can also make use of knowledge about road network topology to locate road areas. Experiments on high-resolution satellite images of different environmental settings show that our proposed scheme achieves high accuracy in identifying road areas.

With the availability of very high resolution commercial satellite data, there has been much interest to extract man-made objects from such imagery. We propose a PC-based incremental system, which includes both road and building extraction tasks in a same package, and makes use of IKONOS's stereo pair to generate 3-D city-model. For each image set, we first use the traditional Normalized Difference Vegetation Index (NDVI) to locate the vegetated areas to be used for masking, and apply the Canny operator to the panchromatic images for edge detection. Subsequently, we use the edge thinning and division algorithm to enhance the detected edges. The roads in satellite imagery are extracted in a semiautomatic way. After the major road areas have been extracted, we focus the search for buildings in areas that are neither road nor vegetation instead of searching the whole image. The package also provides user interactions, which make use of some existing techniques for rooftop hypotheses generation. To handle buildings of different sizes in an image, we use a multi-level approach to make 3D building model generation more efficient.

This paper discusses an efficient and effective framework to decompose polygon meshes into components. This is useful in various interactive graphics applications, such as, mesh editing, establishing correspondence between objects for morphing, computation of bounding volume hierarchy for collision detection and ray tracing. In this paper, we formalize the notion of a component as a sub-volume of an object with homogeneous geometric and topological features. Next, we describe the proposed framework, which adapts the idea of edge contraction and space sweeping to decompose an object automatically. Finally, we demonstrate an application of this framework to improve bounding volume hierarchies constructed by state-of-theart collision detection systems such as RAPID and QuickCD.

Proceedings of the Symposium on Interactive 3D Graphics

Proceedings of the Symposium on Interactive 3D Graphics

Proceedings of the Symposium on Interactive 3D Graphics

Proceedings of the Annual Symposium on Computational Geometry

It is shown that a triangulation of a set of n points in the plane that minimizes the maximum edge length can be computed in time $O(n^2 )$. The algorithm is reasonably easy to implement and is based on the theorem that there is a triangulation with minmax edge length that contains the relative neighborhood graph of the points as a subgraph. With minor modifications the algorithm works for arbitrary normed metrics.

A plane geometric graph C in R2 conforms to another such graph G if each edge of G is the union of some edges of C. It is proved that for every G with n vertices and m edges, there is a completion of a Delaunay triangulation of O(m2n) points that conforms to G. The algorithm that constructs the points is also described.

It is shown that a triangulation of a set of n points in the plane that minimizes the maximum edge length can be computed in time O(n/sup 2/). The algorithm is reasonably easy to implement and is based on the theorem that there is a triangulation with minmax edge length that contains the relative neighborhood graph of the points as a subgraph. With minor modifications the algorithm works for arbitrary normed metrics.>

We show that a triangulation of a set of n points in the plane that minimizes the maximum angle can be computed in time O(n2 log n) and space O(n). In the same amount of time and space we can also handle the constrained case where edges are prescribed. The algorithm iteratively improves an arbitrary initial triangulation and is fairly easy to implement.