Wednesday, August 15, 2007

Maze complexity and aesthetics: deep problems in computer graphics

Craig S. Kaplan is an Assistant Professor at the Computer Graphics Lab, The David R. Cheriton School of Computer Science, University of Waterloo, Ontario, Canada. Studying the use of computer graphics in the creation of geometric art and ornament, Professor Kaplan's interests extend into non-photorealistic rendering.

I happen know at least two high-end software engineers fighting similar research area and aware of some of its complexities and difficulties. Yet, Professor Kaplan's Maze Design is certainly one of the most spectacular amazing presentations of discrete geometry and non-photorealistic rendering techniques I have ever seen.

Creating computer generated mazes using human designer input, Professor Kaplan and his PhD student, Jie Xu, were interested in two complementary questions with respect to maze design: Complexity and Aesthetics. According to Kaplan computer-based maze design requires a mix of techniques from discrete geometry and non-photorealistic rendering. Thus, the two questions of complexity and aesthetics in mazes both represent profound problems in computer graphics.

Kaplan and Jie Xu were trying to answer the following questions:


"What makes a maze difficult to solve? The more we consider this question, the more elusive it becomes. It's certainly possible to begin defining mathematical measures of a maze's complexity, but complexity must depend on aspects of human perception as well. For example, the eye can easily become lost in a set of parallel passages. Complexity also depends on how the maze is to be solved. Are you looking down on the maze, solving it by eye? With a pencil? What if you're walking around inside the maze? And of course, complexity isn't necessarily what we want to measure. Ultimately we'd like to generate compelling puzzles, which may or may not have a high degree of complexity."


"How do we construct attractive mazes, particularly mazes that resemble real-world scenes? Here, maze design interacts with problems in non-photorealistic rendering. There are many great projects for producing line drawings from images. Our goal is similar, except that our lines must also contrive to have the geometry of a maze. This additional constraint affects how we think about creating a line drawing in the first place."

Also according to their page, mazes can be used to represent images in two different ways with the most obvious using non-photorealistic line art as in the fantastic examples by Christopher Berg and the less obvious as in the "great new Maze-a-pix puzzles being produced by Conceptis Puzzles".

Following are a few of those creations linked to their corresponding HUGE originals. Click on any of them to download a PDF or PNG of the maze from their website for solving on paper. If you are REALLY interested with the subject you can also download the full Vortex Maze Construction paper by Jie Xu and Craig S. Kaplan (be patient. it's a big one and might take time to download).

Note: All images are courtesy of and copyrighted (2005) by Jie Xu and Craig S. Kaplan. you are free to use any of the images for personal and non-commercial purposes but please check with the owners about any other uses.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.