(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210854902.6 (22)申请日 2022.07.19 (71)申请人 浙江大学 地址 315400 浙江省宁波市余 姚市凤山 街 道冶山路479号科创大厦12 楼 (72)发明人 张昱晓　王进　陆国栋　张旭生　 (74)专利代理 机构 杭州浙科专利事务所(普通 合伙) 33213 专利代理师 陈洁 (51)Int.Cl. G06T 17/00(2006.01) G06T 7/11(2017.01) (54)发明名称 一种基于方形模块链的三维模型构建及变 形方法 (57)摘要 本发明属于三 维可变形模型重构领域， 公开 了一种基于方形模块链的三维模型构建及变形 方法。 方法采用贪心思想： 对输入的三维模型， 首 先计算基本模块——方形模块的父级模块—— 立方体模块的树连接设计， 再对树内父模块逐个 求解方形模块子链的最优解并连接生成最优链。 对父模块的树连接， 采用先分层求解其链连接 路 径后做层间连接， 再连接遗留模块作为树节点的 方式。 对方形模块子链的求解， 提出基于无向图 的配置方法。 本发明可以将任意三维模型构建成 以方形模块链 为基本结构的三维可变形模型， 从 而实现多形状间的相互变换。 发 明提出的算法可 以应用在建 筑结构、 艺 术造型设计等领域。 权利要求书4页 说明书10页 附图14页 CN 115359176 A 2022.11.18 CN 115359176 A 1.一种基于方 形模块链的三维模型构建及变形 方法， 其特 征在于， 包括如下步骤： 步骤1， 对输入 模型进行划分， 将模型转换为 立方体模块的集 合； 步骤2， 将立方体模块集合连接成树结构， 先采用基于层次的方法计算连接尽可能多的 立方体模块的最长链， 再 连接遗留的模块作为 树节点； 步骤3， 对立方体模块树内的每个立方体模块进行方形模块模块链配置， 采用基于无向 图的方法， 构建方 形模块子链并连接构成面状模块链构形。 2.根据权利要求1所述的基于方形模块链的三维模型构建及变形方法， 其特征在于， 所 述步骤1为了获取模 型的方形模块链构形， 先将其转换为由多个立方体模块组成的集合， 每 个立方体模块的每个面都作为后续放置方形子模块的参考， 输入模型被分割为多个棱长均 为单位长度1的立方体， 这个过程被称为模型划分， 得到的立方体形状即为父模块。 3.根据权利要求1所述的基于方形模块链的三维模型构建及变形方法， 其特征在于， 所 述步骤1包括如下 具体步骤： 步骤1‑1， 缩放模型： 首先对输入模型进行缩放处理。 默认将模型包围盒最小方向缩放为4， 输入后可通过模 型控制器手动调整比例， 假设尺寸最小方向为z方向， 最值顶点坐标为 和 (xmax,ymax,zmax)， 确定缩放比例sca： 步骤1‑2， 模型划分： 采用基于八叉树的体素化方法， 得到立方体模块存 储矩阵Mvox； 记生成的立方体模块集合内模块数量为n， 集合记为 其中， Ci为第i个立方体模 块， i∈[0,n)。 4.根据权利要求1所述的基于方形模块链的三维模型构建及变形方法， 其特征在于， 所 述步骤2计算立方体模块的树连接， 目的是找到立方体模块集合内连接最多模块的树 方法按层 次进行计算， 首先选取首层的立方体模块链的起点， 而后以基于八叉 树的搜索算法， 规定层间节点选取标准， 计算层内不重复连接模块的最长链， 再连接所有层 内链构成整体的立方体模块最长链， 对于未连接入链内的遗留模块， 在其同层的立方体模 块链路径内的模块、 相邻的上层或下层的立方体模块链路径内的模块中搜索近邻模块并建 立连接关系， 成为 树节点， 从而构成立方体模块 树。 5.根据权利要求1所述的基于方形模块链的三维模型构建及变形方法， 其特征在于， 所 述步骤2包括如下 具体步骤： 步骤2‑1， 进行立方体模块链层间节点选取； 立方体模块链首层起点直接选取首层的第 一行内的首个模块， 层内终点选取与下一层 立方体模块中的任意一个相连接的模块以连接两层立方体模块链， 层内起点按顺时针的优 先级顺序在与上一层终点相连的9个模块方位中选择； 步骤2‑2， 计算层内不重复最长链； 不重复最长链是链连接过程中每个模块仅会被连接一次的链， 对立方体模块集合， 分 别对于每一层进行不重复最长链计算；权　利　要　求　书 1/4 页 2 CN 115359176 A 2采用基于八叉节点的回溯搜索算法， 设当前层数为第h层， 该层的总模块数量为nh， 模块 集合记为 从选定的起点模块C0开始， 向相邻八个方向展开模块搜索， 找到最长链路 径 最长链路径包 含的模块数目为 假设当前模 块Ci的层内坐标值为(xi,zi)， 回溯算 法的终止条件 为满足以下任 一项：①xi 或zi超出模块存储矩阵范围， 即xi＜0或xi＜l， 或者zi＜0或zi＞w；②当前模块Ci不在 中；③模块Ci已连接到当前的链中； ④当前链内模块的数量 等于该层内总模块数nh， 且终 点模块符合层内终点选取原则； 其中， l为x轴 方向上输入模型的包围盒的长度向上取整后 的数值， 即x轴方向上的立方体模块层数， w为z轴方向上输入模型的包围盒的长度向上取整 后的数值， 即z轴方向上的立方体模块层数； 计算得到每一层的不重复最长链路径后， 将相邻层次的链首尾相连， 得到整体的不重 复最长链路径 为连入不重复最长链路径的立方体模块数量； 步骤2‑3， 遗留模块连接方法； 具有n个立方体模 块的集合 内仍有未连接入 不重复最长链的模 块， 将此类模 块称 为遗留模块； 记遗留模块集合 遗留模块的数量为n'， 第i'个模块为 对于这些模 块， 将他们与同层或上层的近邻模块建立连接关系； 定义遗留模块存储表Mrem， 记录遗留模块与其上层相邻模块的对应关系， Mrem内有n'个 元素， 第i'个元 素记录了遗留模块 的位置信息及与其有连接关系的模块 的位置信息： 其中， i′∈[0,n′)。 定义立方体模块 的近邻模块为其周围相接触 的26个模块， 其编码值为σ1～σ26， 在对 遗留立方体模块集合 中的每一个模块 按图中标识的序号， 以σ1～σ26的次序， 寻 找已连入立方体模块树的近邻模块， 将搜索到的第一个符合条件的近邻模块记为遗留模块 的连接对象 将其对应关系记入遗留模块存 储表Mrem； 遗留模块存储表Mrem与最长链路径 共同描述了最终的立方体模块树 其中， i∈[0,n)， n 为立方体模块 树中所有模块的数量。 6.根据权利要求1所述的基于方形模块链的三维模型构建及变形方法， 其特征在于， 所 述步骤3在获取立方体模块树 后， 针对树内每个立方体模块， 将模块内的面连接 关系构建为无向图， 并找到连接尽可能多的面的最长路径； 然后以模块内的面作为方形模 块放置的位置， 以最长路径指导方形模块子链配置顺序， 确定相 邻模块交点的选择， 得到方 形模块子链配置， 所有子链首尾相连 得到模型的方 形模块链构形。 7.根据权利要求1所述的基于方形模块链的三维模型构建及变形方法， 其特征在于， 所 述步骤3包括如下 具体步骤：权　利　要　求　书 2/4 页 3 CN 115359176 A 3