《Marching cubes: A high resolution 3D surface construction algorithm》论文阅读笔记:3D表面构造算法

虽然这篇论文年龄比我还大很多0.0,但是真是超级经典的一篇了,一万多的引用量

前排放上论文地址:https://dl.acm.org/doi/10.1145/37401.37422


这篇文章提出了一种高分辨率3D表面构造算法。这种算法和其他的图像到网格的算法相比,生成的网格质量好并且可并行性高,所以应用范围很广。

这个算法最初是用在医学上对3D解剖结构进行可视化的,所以论文前面部分一些涉及医学图像生成的部分我就没咋看了,后面部分是一些优化和医学效果图也没咋看,重点看表面生成的部分,有些不理解的地方结合了看的一些其他资料来说明。

MARCHING CUBES ALGORITHM

基本概念

首先是“体元(Cell)”的概念。使用分治法将表面定位在由八个像素创建的逻辑立方体中,两个相邻的切片各四个。如下图:(就是建立了空间网格),体元就是8个体素构成的方格,每个体素都被8个体元共享。

该算法确定曲面如何与该立方体相交,然后移动到下一个立方体。

表面内外

这个算法是基于标量场的,所以本来是不知道这个网格点在表面内还是表面外的,需要借助一个隐函数,f(x,y,z)=0表示表面上的点集。

如果这8个顶点连续的两个有一个>0一个<0,也就是一个在表面外一个在内,那么表面肯定在这两个顶点之间,那么之后通过插值就可以获得表面的位置。

256种方式

每个立方体有八个顶点,因此曲面与立方体相交的方式有2^8=256种。

15种类型

然后对着256种方式考虑两种对称性:

  • 第一种是互补的情况,因为取x个点其实和取互补的8-x个是一样的表面,所以只需要考虑0-4个点的情况,那么总方式减为256/2=128
  • 第二种是旋转的情况,在上面只考虑0-4个点的基础上加上旋转,最后可以总结出下图15种类型的结构:

索引

接下来根据顶点的状态为每种情况创建一个索引。使用下图中的顶点编号,八位索引的每个位表示一个顶点v。

举个例子,点索引是78,也就是二进制的01001110,对应的点集就是(1,2,3,6),对应的三角形集合是:{(3,11,6),(0,3,6),(0,6,5),(0,5,9)},这样可以得到一张网上代代流传的三角形表(附在文末)(256*16的二维数组,每行对应一种方式的三角形集,-1或者255代表无效)

上图还给12条边e编了号,最后的三角片面的顶点都在边上,所以再用边建立一个索引。

也举个例子,点索引是1,二进制的00000001,那么只有v1在表面内,所以三角面片的点就在边e1,e4,e9上,那么二进制的边索引就是001000001001,也就是十六进制的0x109,根据这个可以列出另一个边表(附在文末)。

然后就可以利用三角形表获得三角形面片集合,利用边表来获取在表面的顶点。

插值

最后一步是为每个三角形顶点计算一个单位法线。渲染算法使用该法线生成 Gouraud-shaded 图像。

下面这部分有点没看懂,说的是梯度向量是密度的导数。然后就是要计算这个梯度向量,首先计算顶点处的梯度,相交点处的靠插值来计算。

算法总体思路

最终的对一个体元绘制表面的思路是这样的:

  • 对于一个体元,根据八个体素(顶点)的像素值,可以确定一个体元配置V
  • 根据这个体元配置V,从三角形表中获取对应的三角形面片集合A
  • 根据这个三角面片集合A,根据边表可以获得边的索引
  • 根据每组边索引可以得到对应的两个端点
  • 根据两个端点坐标可以得到边上的插值坐标,从而得到三角表面的坐标

附表

三角形表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
#define X 255
const int triTable[256][16] = {
{X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X},
{0,8,3,X,X,X,X,X,X,X,X,X,X,X,X,X},
{0,1,9,X,X,X,X,X,X,X,X,X,X,X,X,X},
{1,8,3,9,8,1,X,X,X,X,X,X,X,X,X,X},
{1,2,10,X,X,X,X,X,X,X,X,X,X,X,X,X},
{0,8,3,1,2,10,X,X,X,X,X,X,X,X,X,X},
{9,2,10,0,2,9,X,X,X,X,X,X,X,X,X,X},
{2,8,3,2,10,8,10,9,8,X,X,X,X,X,X,X},
{3,11,2,X,X,X,X,X,X,X,X,X,X,X,X,X},
{0,11,2,8,11,0,X,X,X,X,X,X,X,X,X,X},
{1,9,0,2,3,11,X,X,X,X,X,X,X,X,X,X},
{1,11,2,1,9,11,9,8,11,X,X,X,X,X,X,X},
{3,10,1,11,10,3,X,X,X,X,X,X,X,X,X,X},
{0,10,1,0,8,10,8,11,10,X,X,X,X,X,X,X},
{3,9,0,3,11,9,11,10,9,X,X,X,X,X,X,X},
{9,8,10,10,8,11,X,X,X,X,X,X,X,X,X,X},
{4,7,8,X,X,X,X,X,X,X,X,X,X,X,X,X},
{4,3,0,7,3,4,X,X,X,X,X,X,X,X,X,X},
{0,1,9,8,4,7,X,X,X,X,X,X,X,X,X,X},
{4,1,9,4,7,1,7,3,1,X,X,X,X,X,X,X},
{1,2,10,8,4,7,X,X,X,X,X,X,X,X,X,X},
{3,4,7,3,0,4,1,2,10,X,X,X,X,X,X,X},
{9,2,10,9,0,2,8,4,7,X,X,X,X,X,X,X},
{2,10,9,2,9,7,2,7,3,7,9,4,X,X,X,X},
{8,4,7,3,11,2,X,X,X,X,X,X,X,X,X,X},
{11,4,7,11,2,4,2,0,4,X,X,X,X,X,X,X},
{9,0,1,8,4,7,2,3,11,X,X,X,X,X,X,X},
{4,7,11,9,4,11,9,11,2,9,2,1,X,X,X,X},
{3,10,1,3,11,10,7,8,4,X,X,X,X,X,X,X},
{1,11,10,1,4,11,1,0,4,7,11,4,X,X,X,X},
{4,7,8,9,0,11,9,11,10,11,0,3,X,X,X,X},
{4,7,11,4,11,9,9,11,10,X,X,X,X,X,X,X},
{9,5,4,X,X,X,X,X,X,X,X,X,X,X,X,X},
{9,5,4,0,8,3,X,X,X,X,X,X,X,X,X,X},
{0,5,4,1,5,0,X,X,X,X,X,X,X,X,X,X},
{8,5,4,8,3,5,3,1,5,X,X,X,X,X,X,X},
{1,2,10,9,5,4,X,X,X,X,X,X,X,X,X,X},
{3,0,8,1,2,10,4,9,5,X,X,X,X,X,X,X},
{5,2,10,5,4,2,4,0,2,X,X,X,X,X,X,X},
{2,10,5,3,2,5,3,5,4,3,4,8,X,X,X,X},
{9,5,4,2,3,11,X,X,X,X,X,X,X,X,X,X},
{0,11,2,0,8,11,4,9,5,X,X,X,X,X,X,X},
{0,5,4,0,1,5,2,3,11,X,X,X,X,X,X,X},
{2,1,5,2,5,8,2,8,11,4,8,5,X,X,X,X},
{10,3,11,10,1,3,9,5,4,X,X,X,X,X,X,X},
{4,9,5,0,8,1,8,10,1,8,11,10,X,X,X,X},
{5,4,0,5,0,11,5,11,10,11,0,3,X,X,X,X},
{5,4,8,5,8,10,10,8,11,X,X,X,X,X,X,X},
{9,7,8,5,7,9,X,X,X,X,X,X,X,X,X,X},
{9,3,0,9,5,3,5,7,3,X,X,X,X,X,X,X},
{0,7,8,0,1,7,1,5,7,X,X,X,X,X,X,X},
{1,5,3,3,5,7,X,X,X,X,X,X,X,X,X,X},
{9,7,8,9,5,7,10,1,2,X,X,X,X,X,X,X},
{10,1,2,9,5,0,5,3,0,5,7,3,X,X,X,X},
{8,0,2,8,2,5,8,5,7,10,5,2,X,X,X,X},
{2,10,5,2,5,3,3,5,7,X,X,X,X,X,X,X},
{7,9,5,7,8,9,3,11,2,X,X,X,X,X,X,X},
{9,5,7,9,7,2,9,2,0,2,7,11,X,X,X,X},
{2,3,11,0,1,8,1,7,8,1,5,7,X,X,X,X},
{11,2,1,11,1,7,7,1,5,X,X,X,X,X,X,X},
{9,5,8,8,5,7,10,1,3,10,3,11,X,X,X,X},
{5,7,0,5,0,9,7,11,0,1,0,10,11,10,0,X},
{11,10,0,11,0,3,10,5,0,8,0,7,5,7,0,X},
{11,10,5,7,11,5,X,X,X,X,X,X,X,X,X,X},
{10,6,5,X,X,X,X,X,X,X,X,X,X,X,X,X},
{0,8,3,5,10,6,X,X,X,X,X,X,X,X,X,X},
{9,0,1,5,10,6,X,X,X,X,X,X,X,X,X,X},
{1,8,3,1,9,8,5,10,6,X,X,X,X,X,X,X},
{1,6,5,2,6,1,X,X,X,X,X,X,X,X,X,X},
{1,6,5,1,2,6,3,0,8,X,X,X,X,X,X,X},
{9,6,5,9,0,6,0,2,6,X,X,X,X,X,X,X},
{5,9,8,5,8,2,5,2,6,3,2,8,X,X,X,X},
{2,3,11,10,6,5,X,X,X,X,X,X,X,X,X,X},
{11,0,8,11,2,0,10,6,5,X,X,X,X,X,X,X},
{0,1,9,2,3,11,5,10,6,X,X,X,X,X,X,X},
{5,10,6,1,9,2,9,11,2,9,8,11,X,X,X,X},
{6,3,11,6,5,3,5,1,3,X,X,X,X,X,X,X},
{0,8,11,0,11,5,0,5,1,5,11,6,X,X,X,X},
{3,11,6,0,3,6,0,6,5,0,5,9,X,X,X,X},
{6,5,9,6,9,11,11,9,8,X,X,X,X,X,X,X},
{5,10,6,4,7,8,X,X,X,X,X,X,X,X,X,X},
{4,3,0,4,7,3,6,5,10,X,X,X,X,X,X,X},
{1,9,0,5,10,6,8,4,7,X,X,X,X,X,X,X},
{10,6,5,1,9,7,1,7,3,7,9,4,X,X,X,X},
{6,1,2,6,5,1,4,7,8,X,X,X,X,X,X,X},
{1,2,5,5,2,6,3,0,4,3,4,7,X,X,X,X},
{8,4,7,9,0,5,0,6,5,0,2,6,X,X,X,X},
{7,3,9,7,9,4,3,2,9,5,9,6,2,6,9,X},
{3,11,2,7,8,4,10,6,5,X,X,X,X,X,X,X},
{5,10,6,4,7,2,4,2,0,2,7,11,X,X,X,X},
{0,1,9,4,7,8,2,3,11,5,10,6,X,X,X,X},
{9,2,1,9,11,2,9,4,11,7,11,4,5,10,6,X},
{8,4,7,3,11,5,3,5,1,5,11,6,X,X,X,X},
{5,1,11,5,11,6,1,0,11,7,11,4,0,4,11,X},
{0,5,9,0,6,5,0,3,6,11,6,3,8,4,7,X},
{6,5,9,6,9,11,4,7,9,7,11,9,X,X,X,X},
{10,4,9,6,4,10,X,X,X,X,X,X,X,X,X,X},
{4,10,6,4,9,10,0,8,3,X,X,X,X,X,X,X},
{10,0,1,10,6,0,6,4,0,X,X,X,X,X,X,X},
{8,3,1,8,1,6,8,6,4,6,1,10,X,X,X,X},
{1,4,9,1,2,4,2,6,4,X,X,X,X,X,X,X},
{3,0,8,1,2,9,2,4,9,2,6,4,X,X,X,X},
{0,2,4,4,2,6,X,X,X,X,X,X,X,X,X,X},
{8,3,2,8,2,4,4,2,6,X,X,X,X,X,X,X},
{10,4,9,10,6,4,11,2,3,X,X,X,X,X,X,X},
{0,8,2,2,8,11,4,9,10,4,10,6,X,X,X,X},
{3,11,2,0,1,6,0,6,4,6,1,10,X,X,X,X},
{6,4,1,6,1,10,4,8,1,2,1,11,8,11,1,X},
{9,6,4,9,3,6,9,1,3,11,6,3,X,X,X,X},
{8,11,1,8,1,0,11,6,1,9,1,4,6,4,1,X},
{3,11,6,3,6,0,0,6,4,X,X,X,X,X,X,X},
{6,4,8,11,6,8,X,X,X,X,X,X,X,X,X,X},
{7,10,6,7,8,10,8,9,10,X,X,X,X,X,X,X},
{0,7,3,0,10,7,0,9,10,6,7,10,X,X,X,X},
{10,6,7,1,10,7,1,7,8,1,8,0,X,X,X,X},
{10,6,7,10,7,1,1,7,3,X,X,X,X,X,X,X},
{1,2,6,1,6,8,1,8,9,8,6,7,X,X,X,X},
{2,6,9,2,9,1,6,7,9,0,9,3,7,3,9,X},
{7,8,0,7,0,6,6,0,2,X,X,X,X,X,X,X},
{7,3,2,6,7,2,X,X,X,X,X,X,X,X,X,X},
{2,3,11,10,6,8,10,8,9,8,6,7,X,X,X,X},
{2,0,7,2,7,11,0,9,7,6,7,10,9,10,7,X},
{1,8,0,1,7,8,1,10,7,6,7,10,2,3,11,X},
{11,2,1,11,1,7,10,6,1,6,7,1,X,X,X,X},
{8,9,6,8,6,7,9,1,6,11,6,3,1,3,6,X},
{0,9,1,11,6,7,X,X,X,X,X,X,X,X,X,X},
{7,8,0,7,0,6,3,11,0,11,6,0,X,X,X,X},
{7,11,6,X,X,X,X,X,X,X,X,X,X,X,X,X},
{7,6,11,X,X,X,X,X,X,X,X,X,X,X,X,X},
{3,0,8,11,7,6,X,X,X,X,X,X,X,X,X,X},
{0,1,9,11,7,6,X,X,X,X,X,X,X,X,X,X},
{8,1,9,8,3,1,11,7,6,X,X,X,X,X,X,X},
{10,1,2,6,11,7,X,X,X,X,X,X,X,X,X,X},
{1,2,10,3,0,8,6,11,7,X,X,X,X,X,X,X},
{2,9,0,2,10,9,6,11,7,X,X,X,X,X,X,X},
{6,11,7,2,10,3,10,8,3,10,9,8,X,X,X,X},
{7,2,3,6,2,7,X,X,X,X,X,X,X,X,X,X},
{7,0,8,7,6,0,6,2,0,X,X,X,X,X,X,X},
{2,7,6,2,3,7,0,1,9,X,X,X,X,X,X,X},
{1,6,2,1,8,6,1,9,8,8,7,6,X,X,X,X},
{10,7,6,10,1,7,1,3,7,X,X,X,X,X,X,X},
{10,7,6,1,7,10,1,8,7,1,0,8,X,X,X,X},
{0,3,7,0,7,10,0,10,9,6,10,7,X,X,X,X},
{7,6,10,7,10,8,8,10,9,X,X,X,X,X,X,X},
{6,8,4,11,8,6,X,X,X,X,X,X,X,X,X,X},
{3,6,11,3,0,6,0,4,6,X,X,X,X,X,X,X},
{8,6,11,8,4,6,9,0,1,X,X,X,X,X,X,X},
{9,4,6,9,6,3,9,3,1,11,3,6,X,X,X,X},
{6,8,4,6,11,8,2,10,1,X,X,X,X,X,X,X},
{1,2,10,3,0,11,0,6,11,0,4,6,X,X,X,X},
{4,11,8,4,6,11,0,2,9,2,10,9,X,X,X,X},
{10,9,3,10,3,2,9,4,3,11,3,6,4,6,3,X},
{8,2,3,8,4,2,4,6,2,X,X,X,X,X,X,X},
{0,4,2,4,6,2,X,X,X,X,X,X,X,X,X,X},
{1,9,0,2,3,4,2,4,6,4,3,8,X,X,X,X},
{1,9,4,1,4,2,2,4,6,X,X,X,X,X,X,X},
{8,1,3,8,6,1,8,4,6,6,10,1,X,X,X,X},
{10,1,0,10,0,6,6,0,4,X,X,X,X,X,X,X},
{4,6,3,4,3,8,6,10,3,0,3,9,10,9,3,X},
{10,9,4,6,10,4,X,X,X,X,X,X,X,X,X,X},
{4,9,5,7,6,11,X,X,X,X,X,X,X,X,X,X},
{0,8,3,4,9,5,11,7,6,X,X,X,X,X,X,X},
{5,0,1,5,4,0,7,6,11,X,X,X,X,X,X,X},
{11,7,6,8,3,4,3,5,4,3,1,5,X,X,X,X},
{9,5,4,10,1,2,7,6,11,X,X,X,X,X,X,X},
{6,11,7,1,2,10,0,8,3,4,9,5,X,X,X,X},
{7,6,11,5,4,10,4,2,10,4,0,2,X,X,X,X},
{3,4,8,3,5,4,3,2,5,10,5,2,11,7,6,X},
{7,2,3,7,6,2,5,4,9,X,X,X,X,X,X,X},
{9,5,4,0,8,6,0,6,2,6,8,7,X,X,X,X},
{3,6,2,3,7,6,1,5,0,5,4,0,X,X,X,X},
{6,2,8,6,8,7,2,1,8,4,8,5,1,5,8,X},
{9,5,4,10,1,6,1,7,6,1,3,7,X,X,X,X},
{1,6,10,1,7,6,1,0,7,8,7,0,9,5,4,X},
{4,0,10,4,10,5,0,3,10,6,10,7,3,7,10,X},
{7,6,10,7,10,8,5,4,10,4,8,10,X,X,X,X},
{6,9,5,6,11,9,11,8,9,X,X,X,X,X,X,X},
{3,6,11,0,6,3,0,5,6,0,9,5,X,X,X,X},
{0,11,8,0,5,11,0,1,5,5,6,11,X,X,X,X},
{6,11,3,6,3,5,5,3,1,X,X,X,X,X,X,X},
{1,2,10,9,5,11,9,11,8,11,5,6,X,X,X,X},
{0,11,3,0,6,11,0,9,6,5,6,9,1,2,10,X},
{11,8,5,11,5,6,8,0,5,10,5,2,0,2,5,X},
{6,11,3,6,3,5,2,10,3,10,5,3,X,X,X,X},
{5,8,9,5,2,8,5,6,2,3,8,2,X,X,X,X},
{9,5,6,9,6,0,0,6,2,X,X,X,X,X,X,X},
{1,5,8,1,8,0,5,6,8,3,8,2,6,2,8,X},
{1,5,6,2,1,6,X,X,X,X,X,X,X,X,X,X},
{1,3,6,1,6,10,3,8,6,5,6,9,8,9,6,X},
{10,1,0,10,0,6,9,5,0,5,6,0,X,X,X,X},
{0,3,8,5,6,10,X,X,X,X,X,X,X,X,X,X},
{10,5,6,X,X,X,X,X,X,X,X,X,X,X,X,X},
{11,5,10,7,5,11,X,X,X,X,X,X,X,X,X,X},
{11,5,10,11,7,5,8,3,0,X,X,X,X,X,X,X},
{5,11,7,5,10,11,1,9,0,X,X,X,X,X,X,X},
{10,7,5,10,11,7,9,8,1,8,3,1,X,X,X,X},
{11,1,2,11,7,1,7,5,1,X,X,X,X,X,X,X},
{0,8,3,1,2,7,1,7,5,7,2,11,X,X,X,X},
{9,7,5,9,2,7,9,0,2,2,11,7,X,X,X,X},
{7,5,2,7,2,11,5,9,2,3,2,8,9,8,2,X},
{2,5,10,2,3,5,3,7,5,X,X,X,X,X,X,X},
{8,2,0,8,5,2,8,7,5,10,2,5,X,X,X,X},
{9,0,1,5,10,3,5,3,7,3,10,2,X,X,X,X},
{9,8,2,9,2,1,8,7,2,10,2,5,7,5,2,X},
{1,3,5,3,7,5,X,X,X,X,X,X,X,X,X,X},
{0,8,7,0,7,1,1,7,5,X,X,X,X,X,X,X},
{9,0,3,9,3,5,5,3,7,X,X,X,X,X,X,X},
{9,8,7,5,9,7,X,X,X,X,X,X,X,X,X,X},
{5,8,4,5,10,8,10,11,8,X,X,X,X,X,X,X},
{5,0,4,5,11,0,5,10,11,11,3,0,X,X,X,X},
{0,1,9,8,4,10,8,10,11,10,4,5,X,X,X,X},
{10,11,4,10,4,5,11,3,4,9,4,1,3,1,4,X},
{2,5,1,2,8,5,2,11,8,4,5,8,X,X,X,X},
{0,4,11,0,11,3,4,5,11,2,11,1,5,1,11,X},
{0,2,5,0,5,9,2,11,5,4,5,8,11,8,5,X},
{9,4,5,2,11,3,X,X,X,X,X,X,X,X,X,X},
{2,5,10,3,5,2,3,4,5,3,8,4,X,X,X,X},
{5,10,2,5,2,4,4,2,0,X,X,X,X,X,X,X},
{3,10,2,3,5,10,3,8,5,4,5,8,0,1,9,X},
{5,10,2,5,2,4,1,9,2,9,4,2,X,X,X,X},
{8,4,5,8,5,3,3,5,1,X,X,X,X,X,X,X},
{0,4,5,1,0,5,X,X,X,X,X,X,X,X,X,X},
{8,4,5,8,5,3,9,0,5,0,3,5,X,X,X,X},
{9,4,5,X,X,X,X,X,X,X,X,X,X,X,X,X},
{4,11,7,4,9,11,9,10,11,X,X,X,X,X,X,X},
{0,8,3,4,9,7,9,11,7,9,10,11,X,X,X,X},
{1,10,11,1,11,4,1,4,0,7,4,11,X,X,X,X},
{3,1,4,3,4,8,1,10,4,7,4,11,10,11,4,X},
{4,11,7,9,11,4,9,2,11,9,1,2,X,X,X,X},
{9,7,4,9,11,7,9,1,11,2,11,1,0,8,3,X},
{11,7,4,11,4,2,2,4,0,X,X,X,X,X,X,X},
{11,7,4,11,4,2,8,3,4,3,2,4,X,X,X,X},
{2,9,10,2,7,9,2,3,7,7,4,9,X,X,X,X},
{9,10,7,9,7,4,10,2,7,8,7,0,2,0,7,X},
{3,7,10,3,10,2,7,4,10,1,10,0,4,0,10,X},
{1,10,2,8,7,4,X,X,X,X,X,X,X,X,X,X},
{4,9,1,4,1,7,7,1,3,X,X,X,X,X,X,X},
{4,9,1,4,1,7,0,8,1,8,7,1,X,X,X,X},
{4,0,3,7,4,3,X,X,X,X,X,X,X,X,X,X},
{4,8,7,X,X,X,X,X,X,X,X,X,X,X,X,X},
{9,10,8,10,11,8,X,X,X,X,X,X,X,X,X,X},
{3,0,9,3,9,11,11,9,10,X,X,X,X,X,X,X},
{0,1,10,0,10,8,8,10,11,X,X,X,X,X,X,X},
{3,1,10,11,3,10,X,X,X,X,X,X,X,X,X,X},
{1,2,11,1,11,9,9,11,8,X,X,X,X,X,X,X},
{3,0,9,3,9,11,1,2,9,2,11,9,X,X,X,X},
{0,2,11,8,0,11,X,X,X,X,X,X,X,X,X,X},
{3,2,11,X,X,X,X,X,X,X,X,X,X,X,X,X},
{2,3,8,2,8,10,10,8,9,X,X,X,X,X,X,X},
{9,10,2,0,9,2,X,X,X,X,X,X,X,X,X,X},
{2,3,8,2,8,10,0,1,8,1,10,8,X,X,X,X},
{1,10,2,X,X,X,X,X,X,X,X,X,X,X,X,X},
{1,3,8,9,1,8,X,X,X,X,X,X,X,X,X,X},
{0,9,1,X,X,X,X,X,X,X,X,X,X,X,X,X},
{0,3,8,X,X,X,X,X,X,X,X,X,X,X,X,X},
{X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X}
};
#undef X

边表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const unsigned int edgeTable[256] = {
0x0 ,0x109,0x203,0x30a,0x406,0x50f,0x605,0x70c,
0x80c,0x905,0xa0f,0xb06,0xc0a,0xd03,0xe09,0xf00,
0x190,0x99 ,0x393,0x29a,0x596,0x49f,0x795,0x69c,
0x99c,0x895,0xb9f,0xa96,0xd9a,0xc93,0xf99,0xe90,
0x230,0x339,0x33 ,0x13a,0x636,0x73f,0x435,0x53c,
0xa3c,0xb35,0x83f,0x936,0xe3a,0xf33,0xc39,0xd30,
0x3a0,0x2a9,0x1a3,0xaa ,0x7a6,0x6af,0x5a5,0x4ac,
0xbac,0xaa5,0x9af,0x8a6,0xfaa,0xea3,0xda9,0xca0,
0x460,0x569,0x663,0x76a,0x66 ,0x16f,0x265,0x36c,
0xc6c,0xd65,0xe6f,0xf66,0x86a,0x963,0xa69,0xb60,
0x5f0,0x4f9,0x7f3,0x6fa,0x1f6,0xff ,0x3f5,0x2fc,
0xdfc,0xcf5,0xfff,0xef6,0x9fa,0x8f3,0xbf9,0xaf0,
0x650,0x759,0x453,0x55a,0x256,0x35f,0x55 ,0x15c,
0xe5c,0xf55,0xc5f,0xd56,0xa5a,0xb53,0x859,0x950,
0x7c0,0x6c9,0x5c3,0x4ca,0x3c6,0x2cf,0x1c5,0xcc ,
0xfcc,0xec5,0xdcf,0xcc6,0xbca,0xac3,0x9c9,0x8c0,
0x8c0,0x9c9,0xac3,0xbca,0xcc6,0xdcf,0xec5,0xfcc,
0xcc ,0x1c5,0x2cf,0x3c6,0x4ca,0x5c3,0x6c9,0x7c0,
0x950,0x859,0xb53,0xa5a,0xd56,0xc5f,0xf55,0xe5c,
0x15c,0x55 ,0x35f,0x256,0x55a,0x453,0x759,0x650,
0xaf0,0xbf9,0x8f3,0x9fa,0xef6,0xfff,0xcf5,0xdfc,
0x2fc,0x3f5,0xff ,0x1f6,0x6fa,0x7f3,0x4f9,0x5f0,
0xb60,0xa69,0x963,0x86a,0xf66,0xe6f,0xd65,0xc6c,
0x36c,0x265,0x16f,0x66 ,0x76a,0x663,0x569,0x460,
0xca0,0xda9,0xea3,0xfaa,0x8a6,0x9af,0xaa5,0xbac,
0x4ac,0x5a5,0x6af,0x7a6,0xaa ,0x1a3,0x2a9,0x3a0,
0xd30,0xc39,0xf33,0xe3a,0x936,0x83f,0xb35,0xa3c,
0x53c,0x435,0x73f,0x636,0x13a,0x33 ,0x339,0x230,
0xe90,0xf99,0xc93,0xd9a,0xa96,0xb9f,0x895,0x99c,
0x69c,0x795,0x49f,0x596,0x29a,0x393,0x99 ,0x190,
0xf00,0xe09,0xd03,0xc0a,0xb06,0xa0f,0x905,0x80c,
0x70c,0x605,0x50f,0x406,0x30a,0x203,0x109,0x0
};
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2018-2020 LeFlacon

奶茶一杯 快乐起飞

支付宝
微信