Date of Graduation

Fall 2015

Document Type

Honors Research Project

Degree Name

Bachelor of Science in Computer Science


Computer Science - Systems

Research Sponsor

Yingcai Xiao

First Reader

Zhong-Hui Duan

Second Reader

En Cheng


In video games today, world geometry is often represented as a polygon mesh. While this representation is able to represent terrain, it must be done so using an elevation grid. For each X and Z location, an elevation grid stores the height of the terrain at that location. This has a major drawback: it is unable to allow terrain with overhangs and caves, and is unable to allow for destructible terrain. In this project, an alternative technique using voxels is explored to overcome these limitations for a game engine. A voxel is the 3D equivalent of a pixel and allows for 3D model manipulation by adding and removing discrete units. Because voxel objects require O(n^3) memory to represent, a number of challenges must be overcome to allow efficient manipulation, including effective use of cache memory, minimization of polygon count, efficient communication between the CPU and GPU, efficient collision detection when brute force methods require O(n^6) collision checks, and deletion of triangles from fixed-size Vertex Buffer Objects. The purpose of this project is to investigate and create solutions for these problems and successfully implement a simple game engine in C++ that allows for destructible terrain and terrain generation from mathematical formulas.