Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2017, Vol. 44 Issue (2): 127-133    DOI: 10.3785/j.issn.1008-9497.2017.02.001
Chinagraph 2016-几何计算     
三维迷宫的设计与建模
王康, 吴文明, 刘利刚
中国科学技术大学 数学科学学院, 安徽 合肥 230026
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
 全文: PDF(3307 KB)   HTML  
摘要： 三维迷宫在难度和趣味性上达到了一个更高的水平.通过改进二维迷宫的生成算法，提出了循环迷宫的概念和迷宫复杂度公式.进而，提出一种基于四边形网格曲面的三维迷宫设计算法.该算法分3个步骤：首先，将给定的三维曲面四边形网格化；再确定迷宫的起点和终点，采用基于生成树的二维迷宫生成算法，在网格表面生成迷宫路径；最后，将迷宫实体化为三维结构，并与原始三维模型做布尔运算，得到三维迷宫.通过3D打印机制造出个性化的三维迷宫玩具，大大增强了迷宫的趣味性，改善了用户体验.
关键词： 三维迷宫;  建模;  生成树;  复杂度;  三维打印    
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.
Key words: D maze    modeling    spanning tree    complexity    3D printing
收稿日期: 2016-07-05 出版日期: 2017-07-08
CLC:  TP391  
基金资助: 国家自然科学基金资助项目（61222206，11526212）；中科院“百人”计划项目.
通讯作者: 刘利刚     E-mail: ligang.liu@gmail.com
作者简介: 王康(1991-),ORCID:http://orcid.org/0000-0002-6667-3131,男,硕士研究生,主要从事3D打印研究.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
王康
吴文明
刘利刚

引用本文:

王康, 吴文明, 刘利刚. 三维迷宫的设计与建模[J]. 浙江大学学报（理学版）, 2017, 44(2): 127-133.

WANG Kang, WU Wenming, LIU Ligang. 3D maze design and modeling. Journal of Zhejiang University (Science Edition), 2017, 44(2): 127-133.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2017.02.001    或    https://www.zjujournals.com/sci/CN/Y2017/V44/I2/127

[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.
[1] 胡海涛,赵银君,石敏,赵国亮,朱登明. 三维鱼体参数化建模[J]. 浙江大学学报（理学版）, 2022, 49(1): 19-26.
[2] 傅汝佳, 冼楚华, 李桂清, 万隽杰, 曹铖, 杨存义, 高月芳. 面向表型精确鉴定的豆株快速三维重建[J]. 浙江大学学报（理学版）, 2021, 48(5): 531-539.
[3] 林俊聪, 陈萌, 施渝斌, 雷钧, 郭诗辉, 高星, 廖明宏, 金小刚. 面向高级定制的个性化虚拟服装展示[J]. 浙江大学学报（理学版）, 2021, 48(4): 418-426.
[4] 宋建文, 罗江林, 王博, 张倩, 王献悦. 基于故事情景链语法的偶动画短片分析与建模[J]. 浙江大学学报（理学版）, 2020, 47(3): 284-296.
[5] 周晓莉, 张丰, 杜震洪, 曹敏杰, 刘仁义. 基于CRBM算法的时间序列预测模型研究[J]. 浙江大学学报（理学版）, 2016, 43(4): 442-451.
[6] 曾志, 刘仁义, 杜震洪, 张丰. 云格环境下基于P2P的动态资源发现机制[J]. 浙江大学学报（理学版）, 2013, 40(4): 463-468.
[7] 苏中根. 经典组合优化问题的概率极限定理[J]. 浙江大学学报（理学版）, 2000, 27(6): 700-713.
[8] 陈光亭，张国川. 约束最小生成树问题研究[J]. 浙江大学学报（理学版）, 1999, 26(2): 28-32.