|
|
|
| 3D maze design and modeling |
| WANG Kang, WU Wenming, LIU Ligang |
| School of Mathematical Sciences, University of Science and Technology of China, Hefei 230026, China |
|
|
|
Abstract 3D maze has reached a high level in terms of complexity and fun. By improving the algorithm of generating a 2D maze, we propose the concept of loop maze and the complexity formula of the maze. Then, an algorithm for designing a 3D maze is presented based on the quadrilateral mesh surface. This approach mainly consists of three steps:Firstly, the quadrilateral mesh is generated on the given 3D surface; Secondly, the start point and end point of the maze are chosen alternatively, and the maze on the quadrilateral mesh surface is obtained by the algorithm of generating a 2D maze which is based on a spanning tree algorithm; At last, the maze is turned into 3D structure, and 3D maze is generated by Boolean operation between the 3D structure and the original 3D model. Several personalized 3D maze toys are produced by 3D printer, which consumedly enhances fun and user experience.
|
|
Received: 05 July 2016
Published: 08 July 2017
|
|
|
三维迷宫的设计与建模
三维迷宫在难度和趣味性上达到了一个更高的水平.通过改进二维迷宫的生成算法，提出了循环迷宫的概念和迷宫复杂度公式.进而，提出一种基于四边形网格曲面的三维迷宫设计算法.该算法分3个步骤：首先，将给定的三维曲面四边形网格化；再确定迷宫的起点和终点，采用基于生成树的二维迷宫生成算法，在网格表面生成迷宫路径；最后，将迷宫实体化为三维结构，并与原始三维模型做布尔运算，得到三维迷宫.通过3D打印机制造出个性化的三维迷宫玩具，大大增强了迷宫的趣味性，改善了用户体验.
关键词：
三维迷宫,
建模,
生成树,
复杂度,
三维打印
|
|
[1] 余洋,张伶伶,杨晓军."迷宫"——景观的神秘体验[J].华中建筑,2010(2):29-31. YU Y, ZHANG L L, YANG X J. "Labyrinth":The landscape mystical experience[J]. Huazhong Architecture,2010(2):29-31.
[2] CHENG T K, XIANG L M, LYN T Y, et al. To?:journey or destination?[C]//Proceedings of the 12th International Conference on Advances in Computer Entertainment Technology. New York:ACM,2015:37.
[3] WANG D, ZHANG C, WANG H. T-maze:A tangible programming tool for children[C]//Proceedings of the 10th International Conference on Interaction Design and Children. Now York:ACM,2011:127-135.
[4] LLOTET J, KIRTON T. The maze EV:A two player installation game[C]//Proceedings of the 8th International Conference on Advances in Computer Entertainment Technology. New York:ACM,2011:1-2.
[5] HUANG T W, WU P C, WONG M D F. UI-route:An ultra-fast incremental maze routing algorithm[C]//Proceedings of SLIP (System Level Interconnect Prediction) on System Level Interconnect Prediction Workshop. New York:ACM,2014:1-8.
[6] PHILLIPS A. The topology of Roman mosaic mazes[J]. Leonardo,1993,25(3/4):65-73.
[7] MCCLENDON M S. The complexity and difficulty of a maze[C]//Bridges:Mathematical Connections in Art, Music, and Science. Bridges Conference,2001:213-222. http//archive.bridges mathart.org/2001/bridges2001-213pdf.
[8] XU J, KAPLAN C S. Vortex maze construction[J]. Journal of Mathematics and the Arts,2007,1(1):7-20.
[9] XU J, KAPLAN C S. Image-guided maze construction[J]. ACM Transactions on Graphics,2007,26(3):Article No.29.
[10] 袁开,友杨勇.平面迷宫地图随机生成树算法设计与实现[J].科学咨询,2013(1):138-139. YUAN K, YOU Y Y. Plane random tree algorithm design and implementation of maze map[J]. Scientific Consult,2013(1):138-139.
[11] 田翠花,许卫平,陈玉明.深度优先遍历算法、随机布点法及回溯法在迷宫游戏中的应用[J].河北北方学院学报,2013,29(3):19-24. TIAN C H, XU W P, CHEN Y M. Application of depth-first traversal, randomly distributed point algorithm and backtracking method to maze game[J]. Journal of Hebei North University:Natural Science Edition,2013,29(3):19-24.
[12] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2007. YAN W M, WU W M. Data Structure (C Language Version)[M]. Beijing:Tsinghua University Press,2007. |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
