找回密码
 注册帐号

扫一扫,访问微社区

MemoryC 【MemoryC图形学基础系列】(一)Unity中Mesh的半边数据结构构建

13
回复
1456
查看
[ 复制链接 ]
排名
1347
昨日变化

29

主题

273

帖子

2756

积分

Rank: 9Rank: 9Rank: 9

UID
175038
好友
47
蛮牛币
3350
威望
0
注册时间
2016-10-12
在线时间
634 小时
最后登录
2019-6-19

专栏作家活力之星

2018-12-19 20:30:43 显示全部楼层 阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?注册帐号

x
本帖最后由 MemoryC 于 2018-12-19 20:30 编辑

【MemoryC图形学基础系列】(一)              

————Unity中Mesh的半边数据结构构建
1,什么是半边数据结构

三维模型我们一般采用Mesh(网格)进行表示,一个三维模型包含很多由点相互连接形成面。为了记录这些三维模型的信息,我们有多种方式进行数据的保存,最常见的有以下几种。

(1)以面为中心的数据结构:记录网格的每个三角面的三个顶点的坐标,常见的*.stl文件就是以这种方式进行存储的。数据结构是最简单的,但是缺点也很多,比如不会记录相邻三角面共同顶点的共享信息信息比较冗余,只适合用来记录面数较少的三维模型,不适合作网格的变形处理;

(2)共享顶点的数据结构:记录每一个顶点的坐标信息和每个三角面所引用的顶点的序号,常见的*.obj格式的文件即采用共享顶点的数据结构。其数据结构相对简单,且记录了相邻三角面之间的共享顶点信息,数据冗余较小,比较适合用来记录三维模型,并可以用来作简单的变形处理。但这种数据结构的缺点是不包含边信息,而且无法快速获取每个点的邻点以及邻面等信息;

(3)邻接矩阵数据结构:以矩阵的形式保存定点之间的连接关系。如果顶点Vi和Vj之间有连线,那么矩阵AdjMat[i,j]=1,否则AdjMat[i,j]=0。因为点之间的连接没有方向性,所以AdjMat[i,j]=AdjMat[j,i]即邻接矩阵是堆成矩阵;这种数据格式不包含顶点信息,也不包含面信息。

以上几种三维模型的数据结构都是基于数组的数据结构,在C语言等面向过程的语言中应用比较多。但是由于以上数据结构不利于检索,检索过程需要大量的遍历,不仅耗时费力也难以理解。此时基于面向对象思维的半边数据结构应运而生了。

半边数据结构以半边为中心,这种数据结构保存了三角网格的定点信息,面信息,边信息。半边是一种有方向的边,因为两个方向相反的边才能表示一个“边”,因此这两个有方向且方向相反的边被称为“半边”。

半边数据结构包含5种类实体:网格Mesh,顶点Vertex,半边HalfEdge,面Face,边Edge(个人认为Edge不要也行,但很多文献里是有的); 所有数据通过HalfEdge为枢纽联系起来;即,每个Vertex,Face,Edge都依赖于一个HalfEdge对象。

Half-edge-data-structure.png

半边数据结构示意图

【来源:https://www.researchgate.net/figure/Half-edge-data-structure_fig1_260133435

最经典全面的半边数据结构介绍图

最经典全面的半边数据结构介绍图

最经典的半边数据结构实体关系图

【来源:https://people.eecs.berkeley.edu/~sequin/CS285/TEXT/HalfEdgeDS.html】

其相互关系如上图,实体关系如下:每个HalfEdge包含:起始顶点FromVertex、目标顶点ToVertex,相反半边Opposite(或伴生半边Twin),前序半边(Previous)、后序半边(Next)、所在面(Face)、所在边(Edge)每个Vertex包含:坐标,所在半边HalfEdge每个Face包含:半边HalfEdge列表每个Edge包含:对应任意一个半边HalfEdge

另外,点、半边、面的相邻点、相邻半边、相邻面的关系也可以通过上述的实体关系得到,因此,也可以将相邻信息放到实体对应的类中并在构造或使用的时候给其初始化。


2,半边数据结构的用途

在Unity中,Mesh是由一堆数组来表示的,如 Vector3[] vertices记录顶点坐标,int[] triangles记录三角面片顶点序号, Vector3[] normals记录顶点法线信息,Vector2[] uv记录网格顶点对应贴图的归一化坐标信息。这些用来做游戏的模型现实和渲染是足够的,但是如果使用这种数据格式做网格变形,其效率是远远不能满足要求的,尤其是做点面数较多的网格的变形。这时候我们就需要用到半边数据结构,因为这种数据结构能够记录所有的点面线之间的连接信息,检索起来比较方便快捷,而且有大量的变形类库是支持半边数据结构的。


3,Unity中如何构建半边数据结构

为了在Unity中构建半边数据结构,我们首先要设定好设计原则,MemoryC的设计原则如下:

1、半边数据结构依赖关系正确

2、半边数据结构网格 与 Unity的Mesh网格 可快速相互转换;

3、能快速的根据Unity的Mesh网格中顶点或面的索引找到半边数据结构网格中相应的点或者面,反之亦然;

4、Unity的Mesh网格能同步其对应的半边数据结构网格的变化;


因此,我们首先要构造 顶点Vertex,半边HalfEdge,面Face,边Edge等类,然后构建包含 定点列表和半边列表的HalfEdgeMesh类;然后我们采用合适的方式,让HalfEdgeMesh可以和Unity的Mesh相互转化;最后,让HalfEdgeMesh的点面变化时,更新对应的Mesh即可。


结合上面的实体关系和构造原则,我们即可构建我们的HalfEdgeMesh。代码我们下一篇讲,2-3天左右。


更多技术问题,欢迎加群讨论:

Unity交流群:425377188

问题原则:开门见山,直说问题;不做伸手党。

另外,如果转载文章到其他论坛,请注明原文链接作者

如果本文感动了您,别忘了点文章下方的"支持""评分"哦~

评分所用鲜花为系统赠送,不用就浪费了~





参与人数 3鲜花 +8 收起 理由
uselessShadow + 2 赞一个!
野麻 + 1
晨丶半 + 5 很给力!

查看全部评分总评分 : 鲜花 +8

回复

使用道具 举报

5熟悉之中
720/1000
排名
5234
昨日变化

2

主题

202

帖子

720

积分

Rank: 5Rank: 5

UID
208267
好友
0
蛮牛币
1538
威望
0
注册时间
2017-2-24
在线时间
242 小时
最后登录
2019-6-19
2018-12-20 09:13:15 显示全部楼层
可以的很不错

点评

谢谢支持  发表于 2018-12-20 11:06
回复

使用道具 举报

5熟悉之中
823/1000
排名
8154
昨日变化

0

主题

448

帖子

823

积分

Rank: 5Rank: 5

UID
289569
好友
0
蛮牛币
368
威望
0
注册时间
2018-7-12
在线时间
225 小时
最后登录
2019-5-24
2018-12-20 09:24:32 显示全部楼层

可以的
可以的
回复

使用道具 举报

7日久生情
2303/5000
排名
2248
昨日变化

0

主题

1285

帖子

2303

积分

Rank: 7Rank: 7Rank: 7Rank: 7

UID
189581
好友
0
蛮牛币
3512
威望
0
注册时间
2016-12-5
在线时间
392 小时
最后登录
2019-6-5
2018-12-20 09:28:56 显示全部楼层
可以的给力啊

点评

感谢支持  发表于 2018-12-20 11:06
回复

使用道具 举报

6蛮牛粉丝
1381/1500
排名
1980
昨日变化

0

主题

271

帖子

1381

积分

Rank: 6Rank: 6Rank: 6

UID
68040
好友
0
蛮牛币
2006
威望
0
注册时间
2015-1-13
在线时间
426 小时
最后登录
2019-6-19
2018-12-20 09:51:21 显示全部楼层

可以的很不错

点评

多谢您的支持  发表于 2018-12-20 11:06
回复

使用道具 举报

排名
1347
昨日变化

29

主题

273

帖子

2756

积分

Rank: 9Rank: 9Rank: 9

UID
175038
好友
47
蛮牛币
3350
威望
0
注册时间
2016-10-12
在线时间
634 小时
最后登录
2019-6-19

专栏作家活力之星

楼主 2018-12-20 18:30:32 显示全部楼层
代码明天早晨发布,可惜没时间弄视频,否则可以一步一步地搭建
回复 支持 反对

使用道具 举报

8常驻蛮牛
5273/10000
排名
1669
昨日变化

0

主题

3769

帖子

5273

积分

Rank: 8Rank: 8

UID
185339
好友
1
蛮牛币
3606
威望
0
注册时间
2016-11-20
在线时间
726 小时
最后登录
2019-6-19
2018-12-24 09:35:30 显示全部楼层
3
回复

使用道具 举报

2初来乍到
112/150
排名
16593
昨日变化

3

主题

26

帖子

112

积分

Rank: 2Rank: 2

UID
132000
好友
0
蛮牛币
4
威望
0
注册时间
2015-12-18
在线时间
41 小时
最后登录
2019-2-20
QQ
2018-12-28 14:12:29 显示全部楼层
很清晰,可以的。。。。
回复

使用道具 举报

排名
48132
昨日变化

0

主题

14

帖子

23

积分

Rank: 1

UID
297178
好友
0
蛮牛币
10
威望
0
注册时间
2018-9-15
在线时间
5 小时
最后登录
2019-2-22
2019-1-2 01:03:23 显示全部楼层
留着慢慢看
回复

使用道具 举报

4四处流浪
467/500
排名
10960
昨日变化

1

主题

79

帖子

467

积分

Rank: 4

UID
130631
好友
0
蛮牛币
493
威望
0
注册时间
2015-12-2
在线时间
293 小时
最后登录
2019-6-19
2019-1-16 10:57:06 显示全部楼层
反手就是一个赞  为什么这么晚才发布
回复 支持 反对

使用道具 举报

6蛮牛粉丝
1192/1500
排名
9303
昨日变化

2

主题

723

帖子

1192

积分

Rank: 6Rank: 6Rank: 6

UID
207270
好友
0
蛮牛币
700
威望
0
注册时间
2017-2-19
在线时间
363 小时
最后登录
2019-6-16
2019-4-19 10:07:50 显示全部楼层
666666666666
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册帐号

本版积分规则