Crumley, Zacharia (2012) Voxel-Space Shape Grammars, MSc.
![[img]](http://pubs.cs.uct.ac.za/style/images/fileicons/application_pdf.png) |
PDF
zcrumley_masters_thesis.pdf Download (5MB) |
Abstract
The field of Procedural Generation is being increasingly used in modern content generation for its ability to significantly decrease the cost and time involved. One such area of Procedural Generation is Shape Grammars, a type of formal grammar that operates on geometric shapes instead of symbols. Conventional shape grammar implementations use mesh representations of shapes, but this has two significant drawbacks. Firstly, mesh representations make Boolean geometry operations on shapes difficult to accomplish. Boolean geometry operations allow us to combine shapes using Boolean operators (and, or, not), producing complex, composite shapes. A second drawback is that sub-, or trans-shape detailing is challenging to achieve. To address these two problems with conventional mesh-based shape grammars, we present a novel extension to shape grammars, in which a voxel representation of the generated shapes is used. We outline a five stage algorithm for using these extensions and discuss a number of optional enhancements and optimizations. The final output of the algorithm is a detailed mesh model, suitable for use in real-time or offline graphics applications. We also test our extension’s performance and range of output with three categories of testing: performance testing, output range testing, and variation testing. The results of the testing with our proof-of-concept implementation show that our unoptimized algorithm is slower than conventional shape grammar implementations, with a running time that is O(N^3) for an N^3 voxel grid. However, there is scope for further optimization to our algorithm, which would significantly reduce running times and memory consumption. We outline and discuss several such avenues for performance enhancement. Additionally, testing reveals that our algorithm is able to successfully produce a broad range of detailed outputs, exhibiting many features that would be very difficult to accomplish using mesh-based shape grammar implementations. This range of 3D models includes fractals, skyscraper buildings, space ships, castles, and more. Further, stochastic rules can be used to produce a variety of models that share a basic archetype, but differ noticeably in their details.
| Item Type: | Electronic thesis or dissertation (MSc) |
|---|---|
| Uncontrolled Keywords: | Procedural Generation, Shape Grammar, Voxel, Boolean geometry |
| Subjects: | Computing methodologies > Computer graphics |
| Date Deposited: | 04 Sep 2012 |
| Last Modified: | 10 Oct 2019 15:33 |
| URI: | http://pubs.cs.uct.ac.za/id/eprint/783 |
Actions (login required)
 |
View Item |