Constructing Doubly Connected Edge Lists on the GPU
Authors:
Ivan Espinosa, Allen HsuMentor:
Kevin Wortman, Assistant Professor Department of Computer Science, California State University FullertonAbstract. Our research entails building the doubly connected edge list (DCEL) on the Graphics Processing Unit (GPU) and then analysing the time differences between it and the Central Processing Unit (CPU). The doubly connected edge list (DCEL) is a pivotal aspect of many algorithms involving computational geometry, which finds applications in geographical information systems (GIS), computer aided design (CAD), graphics and data visualization, gaming, and spatial databases. By allowing algorithms access to topological information about a N-Dimensional surface, the DCEL can be used as a basis for many computational geometric algorithms. However, the work required to generate such an arrangement of hyperplanes can be astronomical depending on the number of inputs. In recent years, the number of processors on GPUs have grown immensely. This enables us to process hundreds of inputted data in parallel. We hypothesise that our results will show the algorithm can be successfully implemented on GPU and this implementation will be comparable or superior to a CPU implementation.