Image-guided maze construction

ABSTRACT

We present a set of graphical and combinatorial algorithms for designing mazes based on images. The designer traces regions of interest in an image and annotates the regions with style parameters. They can optionally specify a solution path, which provides a rough guide for laying out the maze's actual solution. The system uses novel extensions to well-known maze construction algorithms to build mazes that approximate the tone of the source image, express the desired style in each region, and conform to the user's solution path.

REFERENCES

• 1: Berg, C. 2001. Amazeing Art: Wonders of the Ancient World. Harper Collins.
• 2: Berg, C., 2005. Amazeing art. http://www.amazeingart.com.
• 3: Cgal Editorial Board. 2006. CGAL-3.2 User and Reference Manual. http://www.cgal.org.
• 4: Conceptis Limited, 2006. Conceptis puzzles. http://www.conceptispuzzles.com.
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: Fisher, A. 2006. The Amazing Book of Mazes. Harry N. Abrams, Inc.
• 7: James Hays , Irfan Essa, Image and video based painterly animation, Proceedings of the 3rd international symposium on Non-photorealistic animation and rendering, June 07-09, 2004, Annecy, France [doi>10.1145/987657.987676]
• 8: Huang, J., and Feigenson, G. W. 1999. A microscopic interaction model of maximum solubility of cholesterol in lipid bilayers. Biophysical Journal 76, 4, 2142--2157.
• 9: Jobard, B., and Lefer, W. 1997. Creating evenly-spaced streamlines of arbitrary density. In Visualization in Scientific Computing '97. Proceedings of the Eurographics Workshop in Boulogne-sur-Mer, France, Springer Verlag, 43--56.
• 10: Kaplan, C. S., and Bosch, R. 2005. TSP art. In Bridges 2005: Mathematical Connections in Art, Music and Science, 301--308.
• 11: Karp, R. M. 1975. On the computational complexity of combinatorial problems. Networks, 5, 45--68.
• 12: Kern, H. 2000. Through the Labyrinth: designs and meanings over 5000 years. Prestel.
• 13: Morales, J. E., 2006. Virtual Mo. http://www.virtualmo.com.
• 14: Mortensen, E. N., and Barrett, W. A. 1995. Intelligent scissors for image composition. ACM Press, 191--198.
• 15: Victor Ostromoukhov, Digital facial engraving, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.417-424, July 1999 [doi>10.1145/311535.311604]
• 16: Peatfield, G., 2005. Maze creator, http://www.mazecreator.com/.
• 17: Hans Pedersen , Karan Singh, Organic labyrinths and mazes, Proceedings of the 4th international symposium on Non-photorealistic animation and rendering, June 05-07, 2006, Annecy, France [doi>10.1145/1124728.1124742]
• 18: Pullen, W. D., 2005. Think labyrinth. http://www.astrolog.org/labyrnth/maze.htm.
• 19: Neil Robertson , P D Seymour, Graph minors. VI. Disjoint paths across a disc, Journal of Combinatorial Theory Series B, v.41 n.1, p.115-138, Aug. 1986 [doi>10.1016/0095-8956(86)90031-6]
• 20: Michael P. Salisbury , Michael T. Wong , John F. Hughes , David H. Salesin, Orientable textures for image-based pen-and-ink illustration, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.401-406, August 1997 [doi>10.1145/258734.258890]
• 21: Sethian, J. A. 1999. Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge University Press.
• 22: Shivers, O., 2005. Maze generation. http://www.cc.gatech.edu/~shivers/mazes.html.
• 23: Stevens, P. S. 1974. Patterns in Nature. Little, Brown.
• 24: Hitoshi Suzuki , Takehiro Akama , Takao Nishizeki, Finding Steiner forests in planar graphs, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.444-453, January 22-24, 1990, San Francisco, California, United States
• 25: Greg Turk, Generating textures on arbitrary surfaces using reaction-diffusion, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.289-298, July 1991
• 26: Georges Winkenbach , David H. Salesin, Computer-generated pen-and-ink illustration, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.91-100, July 1994 [doi>10.1145/192161.192184]
• 27: Xu, J., and Kaplan, C. S. 2007. Vortex maze construction. Journal of Mathematics and the Arts 1, 1 (March), 7--20.
• 28: Zhang, L., Dugas-Phocion, G., Samson, J., and Seitz, S. 2001. Single view modeling of free-form scenes. In Proc. of CVPR, 2001, vol. 1, 990--997.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.m Miscellaneous

Additional Classification:
  J. Computer Applications
  J.5 ARTS AND HUMANITIES

Keywords:
halftoning, labyrinth, line drawing, maze, streamline