【游戏技术群】959392658  【游戏出海群】12067810
游戏蛮牛 手机端
开启辅助访问
 找回密码
 注册帐号

扫一扫,访问微社区

开发者专栏

关注:2436

当前位置:游戏蛮牛 技术专区 开发者专栏

__________________________________________________________________________________
开发者干货区版块规则:

  1、文章必须是图文形式。(至少2幅图)
      2、文章字数必须保持在1500字节以上。(编辑器右下角有字数检查)
      3、本版块只支持在游戏蛮牛原创首发,不支持转载。
      4、本版块回复不得无意义,如:顶、呵呵、不错......【真的会扣分的哦】
      5、......
__________________________________________________________________________________
查看: 1077|回复: 12

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

[复制链接]  [移动端链接]
排名
1353
昨日变化
2

29

主题

272

帖子

2715

积分

Rank: 9Rank: 9Rank: 9

UID
175038
好友
46
蛮牛币
3261
威望
0
注册时间
2016-10-12
在线时间
596 小时
最后登录
2019-2-26

专栏作家活力之星

发表于 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 很给力!

查看全部评分


回复

使用道具 举报

5熟悉之中
629/1000
排名
5318
昨日变化
37

2

主题

192

帖子

629

积分

Rank: 5Rank: 5

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

点评

谢谢支持  发表于 2018-12-20 11:06
[发帖际遇]: baiyupei 发帖时在路边捡到 2 蛮牛币,偷偷放进了口袋. 幸运榜 / 衰神榜

回复

使用道具 举报

5熟悉之中
726/1000
排名
8318
昨日变化
2

0

主题

430

帖子

726

积分

Rank: 5Rank: 5

UID
289569
好友
0
蛮牛币
291
威望
0
注册时间
2018-7-12
在线时间
150 小时
最后登录
2019-3-18
发表于 2018-12-20 09:24:32 | 显示全部楼层

可以的
可以的

回复

使用道具 举报

7日久生情
2266/5000
排名
2268
昨日变化
10

0

主题

1276

帖子

2266

积分

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

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

点评

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

回复

使用道具 举报

6蛮牛粉丝
1284/1500
排名
1988
昨日变化
13

0

主题

257

帖子

1284

积分

Rank: 6Rank: 6Rank: 6

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

可以的很不错

点评

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

回复

使用道具 举报

排名
1353
昨日变化
2

29

主题

272

帖子

2715

积分

Rank: 9Rank: 9Rank: 9

UID
175038
好友
46
蛮牛币
3261
威望
0
注册时间
2016-10-12
在线时间
596 小时
最后登录
2019-2-26

专栏作家活力之星

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

回复 支持 反对

使用道具 举报

7日久生情
4639/5000
排名
1686
昨日变化
1

0

主题

3262

帖子

4639

积分

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

UID
185339
好友
1
蛮牛币
3412
威望
0
注册时间
2016-11-20
在线时间
605 小时
最后登录
2019-3-15
发表于 2018-12-24 09:35:30 | 显示全部楼层
3
[发帖际遇]: 步行骑士 被钱袋砸中进医院,看病花了 2 蛮牛币. 幸运榜 / 衰神榜

回复

使用道具 举报

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

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 | 显示全部楼层
很清晰,可以的。。。。

回复

使用道具 举报

排名
48095
昨日变化
15

0

主题

14

帖子

23

积分

Rank: 1

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

回复

使用道具 举报

4四处流浪
432/500
排名
10950
昨日变化
120

1

主题

74

帖子

432

积分

Rank: 4

UID
130631
好友
0
蛮牛币
401
威望
0
注册时间
2015-12-2
在线时间
265 小时
最后登录
2019-3-18
发表于 2019-1-16 10:57:06 | 显示全部楼层
反手就是一个赞  为什么这么晚才发布

回复 支持 反对

使用道具 举报

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

本版积分规则

快速回复 返回顶部 返回列表