(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210871928.1 (22)申请日 2022.07.19 (71)申请人 浙江大学 地址 315400 浙江省宁波市余 姚市凤山 街 道冶山路479号科创大厦12 楼 (72)发明人 张昱晓　王进　陆国栋　张旭生　 (74)专利代理 机构 杭州浙科专利事务所(普通 合伙) 33213 专利代理师 陈洁 (51)Int.Cl. G06T 17/00(2006.01) G06T 7/13(2017.01) (54)发明名称 一种基于晶格链的三维模型构建及变形方 法 (57)摘要 本发明属于三 维可变形模型重构领域， 公开 了一种基于晶格链的三维模型构建及变形方法。 方法整体采用贪心思想： 对输入的三维模型， 首 先计算基本模块的父级模块——四棱锥模块的 树连接设计， 再以父模块为单位求解杆状模块子 链的局部最优解并连接生 成最优链。 对父模块的 树连接， 提出先分层求解其链连接路径后做层间 连接， 再连接遗留模块作为树节点的方式。 对杆 状模块子链的求解， 提出基于状态匹配的配置方 法。 此外， 提出基于反向模块的杆状模块链轮廓 优化方法。 本发 明可以将任意三维模 型构建成以 晶格链为基本结构的三维可变形模 型， 从而实现 多形状间的相互变换。 发明提出的算法可以应用 在建筑结构、 艺 术造型设计等领域。 权利要求书5页 说明书12页 附图10页 CN 115359177 A 2022.11.18 CN 115359177 A 1.一种基于晶格链的三维模型构建及变形 方法， 其特 征在于， 包括如下步骤： 步骤1： 对输入 模型进行划分， 将模型转换为四棱锥模块的集 合； 步骤2： 将四棱锥模块集合连接成树结构， 先采用基于层次的方法计算连接尽可能多的 四棱锥模块的最长链， 再 连接遗留的模块作为 树节点； 步骤3： 对四棱锥模块树内的每个四棱锥模块进行杆状模块链配置， 采用基于状态匹配 的方法， 构建杆状模块子链并连接构成初步晶格链构形； 步骤4： 对初步晶格链构形进行轮廓优化， 设计轮廓补充的匹配规则， 根据反向四棱锥 模块构建补充杆状模块链， 并连入初步晶格链构形中构成最终晶格链构形。 2.根据权利要求1所述的基于晶格链的三维模型构建及变形方法， 其特征在于， 所述步 骤1为了获取模型的杆状模块链构形， 先将其转换为由多个四棱锥模块组成的集合， 每个四 棱锥模块的每一条棱 都作为后续放置杆状子模块的参考， 输入模型被分割为多个棱长均为 单位长度1的四棱锥， 这个过程被称为模型划分， 得到的四棱锥形状即为父模块。 3.根据权利要求1所述的基于晶格链的三维模型构建及变形方法， 其特征在于， 所述步 骤1包括如下 具体步骤： 步骤1‑1， 缩放模型； 首先对输入模型进行缩放处理， 默认将模型包围盒最小方向缩放为4， 输入后可通过模 型控制器手动调整比例， 假设尺寸最小方向为z方向， 最值顶点坐标为(xmin,ymin,zmin)和 (xmax,ymax,zmax)， 确定缩放比例sca及各个方向缩放后的长度lenx,leny： 步骤1‑2， 模型划分； 为使模型划分结果更加灵活可调， 设定四棱锥模块分布范围从包围盒最小值顶点坐标 向下取整的位置 开始， 为使划分后的四棱锥模块能够包含整个模型范 围， 将四棱锥模块的分布范围l,w,d在包围盒x,z,y方向的长度向上取整的基础上分别放 大： 将满足三维坐标值 的正向、 反向四棱锥模块分别与输入模 型做布尔运算相交检测， 保留相交的四棱锥模块， 其 中， 在四棱锥模块与输入模 型相交情况下， 相交部分体积与四棱锥体积之比rat小于0.1， 则 认为不相交， 记当前模块 为c， 对应rat的定义 为：权　利　要　求　书 1/5 页 2 CN 115359177 A 2记生成的四棱锥模块集合内模块数量为n， 集合记为 其中， Ci为第i个四棱锥模 块， i∈[0,n)。 4.根据权利要求1所述的基于晶格链的三维模型构建及变形方法， 其特征在于， 所述步 骤2计算四棱锥 模块的树连接， 目的是找到四棱锥 模块集合内连接 最多模块的树 其中， 由于反向四棱锥模块仅作为后 期优化形状的参考， 仅对正向模块做链连接路径搜索， 方法首先选取首层的链起点， 而后以基于 八叉树的搜索算法， 规定层间节点选取标准， 计算 层内不重复连接模块的最长链， 连接所有层内链构成四棱锥模块最长链， 对于未连接入链 内的遗留模块， 在其同层的链路径内的模块、 相邻的上层或下层的链路径内的模块中搜索 相邻模块并建立连接关系作为 树节点， 构成四棱锥模块 树。 5.根据权利要求1所述的基于晶格链的三维模型构建及变形方法， 其特征在于， 所述步 骤2包括如下 具体步骤： 步骤2‑1， 层间节点选取； 对于首层起点的选取， 其具体的位置选择对后续连接路径计算影响不大， 因此， 选择首 层模块第一行内的首个模块作为层间起 点； 对于层内终点的选取， 一层四棱锥模块链的终点必须保证能够与下一层四棱锥模块相 连接， 由于相 邻层次的模块间连接方式为低层次的模块顶部顶点与高层次的模块底面顶点 相连接， 那么低层次模块的顶点共与四个高层次的模块相连接， 对于模块Ci， 选取与下一层 四棱锥模块中的任意一个相连接的模块， 即可作为层内终点连接上下两层， 此外， 由于最后 一层不存在下一层模块， 对它的终点的选取没有任何要求； 对于层内起点选取， 除首层之外， 其他层次的四棱锥模块链起点都与上一层模块的层 内终点相关， 在与上一层终点相连的四个模块方位中， 按顺时针的优先级顺序选择四棱锥 模块作为层内模块链的起 点； 步骤2‑2， 层内不重复最长链计算； 不重复最长链是链连接过程中每个模块仅会被连接一次的链， 对四棱锥模块集合， 分 别对于每一层进行不重复最长链计算； 在层内不重复最长链的计算中， 采用基于八叉节点的回溯搜索算法， 设当前层数为第h 层， 该层的总模块数量为nh， 模块集合记为 从选定的起点模块C0开始， 向相邻八个 方向展开模块搜索， 找到最长链路径 最长链路径包 含的模块数目为 假设当前模 块Ci的层内坐标值为(xi,zi)， 回溯算 法的终止条件 为满足以下任 一项：①xi 或zi超出模块存储矩阵范围， 即xi＜0或xi＜l， 或者zi＜0或zi＞w；②当前模块Ci不在 中；③模块Ci已连接到当前的链中； ④当前链内模块的数量 等于该层内总模块数nh， 且终 点模块符合层内终点选取原则； 计算得到每一层的不重复最长链路径后， 将相邻层次的链首尾相连， 得到整体的不重权　利　要　求　书 2/5 页 3 CN 115359177 A 3