1 | // |
---|
2 | // Lol Engine |
---|
3 | // |
---|
4 | // Copyright: (c) 2010-2013 Sam Hocevar <sam@hocevar.net> |
---|
5 | // (c) 2010-2013 Benjamin "Touky" Huet <huet.benjamin@gmail.com> |
---|
6 | // This program is free software; you can redistribute it and/or |
---|
7 | // modify it under the terms of the Do What The Fuck You Want To |
---|
8 | // Public License, Version 2, as published by Sam Hocevar. See |
---|
9 | // http://www.wtfpl.net/ for more details. |
---|
10 | // |
---|
11 | |
---|
12 | // |
---|
13 | // The EasyMesh class |
---|
14 | // ------------------ |
---|
15 | // |
---|
16 | |
---|
17 | #if defined HAVE_CONFIG_H |
---|
18 | # include "config.h" |
---|
19 | #endif |
---|
20 | |
---|
21 | #if defined _XBOX |
---|
22 | # define _USE_MATH_DEFINES /* for M_PI */ |
---|
23 | # include <xtl.h> |
---|
24 | # undef near /* Fuck Microsoft */ |
---|
25 | # undef far /* Fuck Microsoft again */ |
---|
26 | #elif defined _WIN32 |
---|
27 | # define _USE_MATH_DEFINES /* for M_PI */ |
---|
28 | # define WIN32_LEAN_AND_MEAN |
---|
29 | # include <windows.h> |
---|
30 | # undef near /* Fuck Microsoft */ |
---|
31 | # undef far /* Fuck Microsoft again */ |
---|
32 | #endif |
---|
33 | |
---|
34 | #include "core.h" |
---|
35 | |
---|
36 | namespace lol |
---|
37 | { |
---|
38 | |
---|
39 | int CsgBsp::AddLeaf(int leaf_type, vec3 origin, vec3 normal, int above_idx) |
---|
40 | { |
---|
41 | if (leaf_type > 2 && leaf_type < -1) |
---|
42 | return -1; |
---|
43 | |
---|
44 | if ((m_tree.Count() == 0 && above_idx == -1) || |
---|
45 | (above_idx >= 0 && |
---|
46 | above_idx < m_tree.Count() && |
---|
47 | leaf_type > LEAF_CURRENT && |
---|
48 | leaf_type < LEAF_ABOVE && |
---|
49 | m_tree[above_idx].m_leaves[leaf_type] == -1)) |
---|
50 | { |
---|
51 | if (m_tree.Count() != 0) |
---|
52 | m_tree[above_idx].m_leaves[leaf_type] = m_tree.Count(); |
---|
53 | m_tree.Push(CsgBspLeaf(origin, normal, above_idx)); |
---|
54 | return m_tree.Count() - 1; |
---|
55 | } |
---|
56 | |
---|
57 | return -1; |
---|
58 | } |
---|
59 | |
---|
60 | int CsgBsp::TestPoint(int leaf_idx, vec3 point) |
---|
61 | { |
---|
62 | if (leaf_idx >= 0 && leaf_idx < m_tree.Count()) |
---|
63 | { |
---|
64 | vec3 p2o = point - m_tree[leaf_idx].m_origin; |
---|
65 | |
---|
66 | if (length(p2o) < CSG_EPSILON) |
---|
67 | return LEAF_CURRENT; |
---|
68 | |
---|
69 | float p2o_dot = dot(normalize(p2o), m_tree[leaf_idx].m_normal); |
---|
70 | |
---|
71 | if (p2o_dot > CSG_EPSILON) |
---|
72 | return LEAF_FRONT; |
---|
73 | else if (p2o_dot < -CSG_EPSILON) |
---|
74 | return LEAF_BACK; |
---|
75 | } |
---|
76 | return LEAF_CURRENT; |
---|
77 | } |
---|
78 | |
---|
79 | void CsgBsp::AddTriangleToTree(int const &tri_idx, vec3 const &tri_v0, vec3 const &tri_v1, vec3 const &tri_v2) |
---|
80 | { |
---|
81 | //<Leaf_Id, v0, v1, v2> |
---|
82 | Array< int, vec3, vec3, vec3 > tri_to_process; |
---|
83 | //<FW/BW, Leaf_Id, v0, v1, v2, twin_leaf> |
---|
84 | Array< int, int, vec3, vec3, vec3, int > Leaf_to_add; |
---|
85 | |
---|
86 | //Tree is empty, so this leaf is the first |
---|
87 | if (m_tree.Count() == 0) |
---|
88 | { |
---|
89 | AddLeaf(LEAF_CURRENT, tri_v0, cross(normalize(tri_v1 - tri_v0), normalize(tri_v2 - tri_v1)), LEAF_CURRENT); |
---|
90 | m_tree.Last().m_tri_list.Push(tri_idx, tri_v0, tri_v1, tri_v2); |
---|
91 | return; |
---|
92 | } |
---|
93 | |
---|
94 | tri_to_process.Reserve(20); |
---|
95 | tri_to_process.Push(0, tri_v0, tri_v1, tri_v2); |
---|
96 | |
---|
97 | while (tri_to_process.Count()) |
---|
98 | { |
---|
99 | int leaf_idx = tri_to_process.Last().m1; |
---|
100 | vec3 v[3] = { tri_to_process.Last().m2, tri_to_process.Last().m3, tri_to_process.Last().m4 }; |
---|
101 | |
---|
102 | int res_nb[3] = { 0, 0, 0 }; |
---|
103 | int res_side[3] = { -1, -1, -1 }; |
---|
104 | |
---|
105 | //Check where each point is located |
---|
106 | for (int i = 0; i < 3; i++) |
---|
107 | { |
---|
108 | int result = TestPoint(leaf_idx, v[i]); |
---|
109 | if (result != LEAF_CURRENT) |
---|
110 | { |
---|
111 | res_nb[result]++; |
---|
112 | res_side[i] = result; |
---|
113 | } |
---|
114 | } |
---|
115 | |
---|
116 | //Points are located on each sides, let's do the mumbo-jumbo |
---|
117 | if (res_nb[LEAF_BACK] && res_nb[LEAF_FRONT]) |
---|
118 | { |
---|
119 | //there are two intersections, no more. |
---|
120 | vec3 isec_v[2] = { vec3(.0f), vec3(.0f) }; |
---|
121 | int isec_i[2] = { 0, 0 }; |
---|
122 | int isec_base = 0; |
---|
123 | int isec_idx = 0; |
---|
124 | |
---|
125 | for (int i = 0; i < 3; i++) |
---|
126 | { |
---|
127 | vec3 ray = v[(i + 1) % 3] - v[i]; |
---|
128 | |
---|
129 | if (RayIsectPlane(v[i], v[(i + 1) % 3], |
---|
130 | m_tree[leaf_idx].m_origin, m_tree[leaf_idx].m_normal, |
---|
131 | isec_v[isec_idx])) |
---|
132 | isec_i[isec_idx++] = i; |
---|
133 | else |
---|
134 | isec_base = i; |
---|
135 | } |
---|
136 | |
---|
137 | int v_idx0 = (isec_base == 1)?(1):(0); |
---|
138 | int v_idx1 = (isec_base == 1)?(0):(1); |
---|
139 | int leaf_type = res_side[(isec_base + 2) % 3]; |
---|
140 | |
---|
141 | tri_to_process.Pop(); |
---|
142 | |
---|
143 | #if 1 |
---|
144 | if (m_tree[leaf_idx].m_leaves[leaf_type] == LEAF_CURRENT) |
---|
145 | Leaf_to_add.Push(leaf_type, leaf_idx, v[((isec_base + 2) % 3)], isec_v[v_idx1], isec_v[v_idx0], -1); |
---|
146 | else |
---|
147 | tri_to_process.Push(leaf_idx, v[((isec_base + 2) % 3)], isec_v[v_idx1], isec_v[v_idx0]); |
---|
148 | |
---|
149 | if (m_tree[leaf_idx].m_leaves[1 - leaf_type] == LEAF_CURRENT) |
---|
150 | { |
---|
151 | Leaf_to_add.Push(1 - leaf_type, leaf_idx, v[isec_base], v[((isec_base + 1) % 3)], isec_v[v_idx0], -1); |
---|
152 | Leaf_to_add.Push(1 - leaf_type, leaf_idx, v[isec_base], isec_v[v_idx0], isec_v[v_idx1], Leaf_to_add.Count() - 1); |
---|
153 | } |
---|
154 | else |
---|
155 | { |
---|
156 | tri_to_process.Push(m_tree[leaf_idx].m_leaves[1 - leaf_type], v[isec_base], v[((isec_base + 1) % 3)], isec_v[v_idx0]); |
---|
157 | tri_to_process.Push(m_tree[leaf_idx].m_leaves[1 - leaf_type], v[isec_base], isec_v[v_idx0], isec_v[v_idx1]); |
---|
158 | } |
---|
159 | #else |
---|
160 | vec3 new_v[9] = { v[((isec_base + 2) % 3)], isec_v[v_idx1], isec_v[v_idx0], |
---|
161 | v[isec_base], v[((isec_base + 1) % 3)], isec_v[v_idx0], |
---|
162 | v[isec_base], isec_v[v_idx0], isec_v[v_idx1] }; |
---|
163 | |
---|
164 | //Error check : Skip the triangle where two points are on the same location. |
---|
165 | //it fixes the problem of having an intersection with one of the isec-point being on one of the triangle vertices. |
---|
166 | //(the problem being a very funny infinite loop) |
---|
167 | for(int k = 0; k < 9; k += 3) |
---|
168 | { |
---|
169 | bool skip_tri = false; |
---|
170 | for(int l = 0; l < 3; l++) |
---|
171 | { |
---|
172 | if (length(new_v[k + l] - new_v[k + (l + 1) % 3]) < CSG_EPSILON) |
---|
173 | { |
---|
174 | skip_tri = true; |
---|
175 | break; |
---|
176 | } |
---|
177 | } |
---|
178 | |
---|
179 | if (skip_tri) |
---|
180 | continue; |
---|
181 | |
---|
182 | tri_to_process.Push(0, new_v[k], new_v[k + 1], new_v[k + 2]); |
---|
183 | } |
---|
184 | #endif |
---|
185 | } |
---|
186 | //All points are on one side, transfer to the next leaf |
---|
187 | else if (res_nb[LEAF_BACK] || res_nb[LEAF_FRONT]) |
---|
188 | { |
---|
189 | int new_leaf_type = ((res_nb[LEAF_FRONT])?(LEAF_FRONT):(LEAF_BACK)); |
---|
190 | int new_leaf = m_tree[leaf_idx].m_leaves[new_leaf_type]; |
---|
191 | |
---|
192 | //No leaf exist, so add a new one |
---|
193 | if (new_leaf == LEAF_CURRENT) |
---|
194 | { |
---|
195 | tri_to_process.Pop(); |
---|
196 | Leaf_to_add.Push(new_leaf_type, leaf_idx, v[0], v[1], v[2], -1); |
---|
197 | } |
---|
198 | else |
---|
199 | tri_to_process.Last().m1 = new_leaf; |
---|
200 | } |
---|
201 | //All points are on the current leaf, add the tri_idx to the list of this leaf. |
---|
202 | else |
---|
203 | { |
---|
204 | tri_to_process.Pop(); |
---|
205 | |
---|
206 | bool already_exist = false; |
---|
207 | for (int i = 0; !already_exist && i < m_tree[leaf_idx].m_tri_list.Count(); i++) |
---|
208 | already_exist = (m_tree[leaf_idx].m_tri_list[i].m1 == tri_idx); |
---|
209 | if (!already_exist) |
---|
210 | m_tree[leaf_idx].m_tri_list.Push(tri_idx, tri_v0, tri_v1, tri_v2); |
---|
211 | } |
---|
212 | } |
---|
213 | |
---|
214 | //Add all leaves to the tree. |
---|
215 | for (int i = 0; i < Leaf_to_add.Count(); i++) |
---|
216 | { |
---|
217 | //If we had it to an already existing leaf. |
---|
218 | if (Leaf_to_add[i].m2 < m_tree.Count() && m_tree[Leaf_to_add[i].m2].m_leaves[Leaf_to_add[i].m1] == LEAF_CURRENT) |
---|
219 | { |
---|
220 | AddLeaf(Leaf_to_add[i].m1, tri_v0, cross(normalize(tri_v1 - tri_v0), normalize(tri_v2 - tri_v1)), Leaf_to_add[i].m2); |
---|
221 | m_tree.Last().m_tri_list.Push(tri_idx, tri_v0, tri_v1, tri_v2); |
---|
222 | } |
---|
223 | |
---|
224 | /* |
---|
225 | if (Leaf_to_add[i].m6 == -1) |
---|
226 | { |
---|
227 | AddLeaf(Leaf_to_add[i].m1, tri_v0, cross(normalize(tri_v1 - tri_v0), normalize(tri_v2 - tri_v1)), Leaf_to_add[i].m2); |
---|
228 | m_tree.Last().m_tri_list.Push(tri_idx, tri_v0, tri_v1, tri_v2); |
---|
229 | } |
---|
230 | else |
---|
231 | m_tree[Leaf_to_add[i].m6].m_tri_list.Push(tri_idx, tri_v0, tri_v1, tri_v2); |
---|
232 | */ |
---|
233 | } |
---|
234 | } |
---|
235 | |
---|
236 | //return 0 when no split has been done. |
---|
237 | //return 1 when split has been done. |
---|
238 | //return -1 when error. |
---|
239 | int CsgBsp::TestTriangleToTree(vec3 const &tri_v0, vec3 const &tri_v1, vec3 const &tri_v2, |
---|
240 | //In order to easily build the actual vertices list afterward, this list stores each Vertices location and its source vertices & Alpha. |
---|
241 | //<Point_Loc, Src_V0, Src_V1, Alpha> as { Point_Loc = Src_V0 + (Src_V1 - Src_V0) * Alpha; } |
---|
242 | Array< vec3, int, int, float > &vert_list, |
---|
243 | //This is the final triangle list : If Side_Status is LEAF_CURRENT, a new test will be done point by point. |
---|
244 | //<{IN|OUT}side_status, v0, v1, v2> |
---|
245 | Array< int, int, int, int > &tri_list) |
---|
246 | { |
---|
247 | //This list stores the current triangles to process. |
---|
248 | //<Leaf_Id_List, v0, v1, v2, Should_Point_Test> |
---|
249 | Array< Array< int >, int, int, int, int > tri_to_process; |
---|
250 | |
---|
251 | //Tree is empty, ABORT ! |
---|
252 | if (m_tree.Count() == 0) |
---|
253 | return -1; |
---|
254 | |
---|
255 | //Let's push the source vertices in here. |
---|
256 | vert_list.Push(tri_v0, -1, -1, .0f); |
---|
257 | vert_list.Push(tri_v1, -1, -1, .0f); |
---|
258 | vert_list.Push(tri_v2, -1, -1, .0f); |
---|
259 | |
---|
260 | //Let's push the triangle in here. |
---|
261 | tri_to_process.Reserve(20); |
---|
262 | tri_to_process.Push( Array< int >(), 0, 1, 2, 0); |
---|
263 | tri_to_process.Last().m1.Push(0); |
---|
264 | |
---|
265 | while (tri_to_process.Count()) |
---|
266 | { |
---|
267 | while (tri_to_process.Count()) |
---|
268 | { |
---|
269 | int leaf_idx = tri_to_process.Last().m1.Last(); |
---|
270 | int t[3] = { tri_to_process.Last().m2, |
---|
271 | tri_to_process.Last().m3, |
---|
272 | tri_to_process.Last().m4 }; |
---|
273 | vec3 v[3] = { vert_list[t[0]].m1, |
---|
274 | vert_list[t[1]].m1, |
---|
275 | vert_list[t[2]].m1 }; |
---|
276 | |
---|
277 | int res_nb[3] = { 0, 0, 0 }; |
---|
278 | int res_side[3] = { -1, -1, -1 }; |
---|
279 | //Check where each point is located |
---|
280 | for (int i = 0; i < 3; i++) |
---|
281 | { |
---|
282 | int result = TestPoint(leaf_idx, v[i]); |
---|
283 | if (result != LEAF_CURRENT) |
---|
284 | { |
---|
285 | res_nb[result]++; |
---|
286 | res_side[i] = result; |
---|
287 | } |
---|
288 | } |
---|
289 | |
---|
290 | //Points are located on each sides, let's do the mumbo-jumbo |
---|
291 | if (res_nb[LEAF_BACK] && res_nb[LEAF_FRONT]) |
---|
292 | { |
---|
293 | //there are two intersections, no more. |
---|
294 | vec3 isec_v[2] = { vec3(.0f), vec3(.0f) }; |
---|
295 | int isec_i[2] = { 0, 0 }; |
---|
296 | int new_v_idx[2] = { 0, 0 }; |
---|
297 | int isec_base = 0; |
---|
298 | int isec_idx = 0; |
---|
299 | |
---|
300 | int i = 0; |
---|
301 | for (; i < m_tree[leaf_idx].m_tri_list.Count(); i++) |
---|
302 | { |
---|
303 | if (TriangleIsectTriangle(v[0], v[1], v[2], |
---|
304 | m_tree[leaf_idx].m_tri_list[i].m2, m_tree[leaf_idx].m_tri_list[i].m3, m_tree[leaf_idx].m_tri_list[i].m4, |
---|
305 | isec_v[0], isec_v[1])) |
---|
306 | break; |
---|
307 | } |
---|
308 | |
---|
309 | //There was no triangle intersection, the complex case. |
---|
310 | if (i == m_tree[leaf_idx].m_tri_list.Count()) |
---|
311 | { |
---|
312 | if (m_tree[leaf_idx].m_leaves[LEAF_FRONT] == LEAF_CURRENT && |
---|
313 | m_tree[leaf_idx].m_leaves[LEAF_BACK] == LEAF_CURRENT && |
---|
314 | tri_to_process.Last().m1.Count() == 1) |
---|
315 | { |
---|
316 | tri_list.Push(LEAF_CURRENT, tri_to_process.Last().m2, tri_to_process.Last().m3, tri_to_process.Last().m4); |
---|
317 | tri_to_process.Pop(); |
---|
318 | } |
---|
319 | else |
---|
320 | { |
---|
321 | tri_to_process.Last().m1.Pop(); |
---|
322 | |
---|
323 | //Register the triangle as needing to intersect with Front & back leaves. |
---|
324 | if (m_tree[leaf_idx].m_leaves[LEAF_FRONT] != LEAF_CURRENT) |
---|
325 | tri_to_process.Last().m1.Push(m_tree[leaf_idx].m_leaves[LEAF_FRONT]); |
---|
326 | if (m_tree[leaf_idx].m_leaves[LEAF_BACK] != LEAF_CURRENT) |
---|
327 | tri_to_process.Last().m1.Push(m_tree[leaf_idx].m_leaves[LEAF_BACK]); |
---|
328 | //Mark the triangle as needing point by point test |
---|
329 | |
---|
330 | tri_to_process.Last().m5 = 1; |
---|
331 | } |
---|
332 | } |
---|
333 | //there was an intersection, so let's split the triangle. |
---|
334 | else |
---|
335 | { |
---|
336 | //Get intersection on actual triangle sides. |
---|
337 | if (RayIsectTriangleSide(v[0], v[1], v[2], |
---|
338 | isec_v[0], isec_v[1], |
---|
339 | isec_v[0], isec_i[0], isec_v[1], isec_i[1])) |
---|
340 | { |
---|
341 | { |
---|
342 | for(int k = 0; k < 2; k++) |
---|
343 | { |
---|
344 | if (isec_base == isec_i[k]) |
---|
345 | isec_base++; |
---|
346 | |
---|
347 | #if 1 //Skip point creation if it's on the same location a one of the triangle. |
---|
348 | bool skip_point = false; |
---|
349 | int l = 0; |
---|
350 | for(; l < 3; l++) |
---|
351 | { |
---|
352 | if (length(v[l] - isec_v[k]) < CSG_EPSILON) |
---|
353 | { |
---|
354 | skip_point = true; |
---|
355 | new_v_idx[k] = t[l]; |
---|
356 | break; |
---|
357 | } |
---|
358 | } |
---|
359 | |
---|
360 | if (skip_point) |
---|
361 | continue; |
---|
362 | #endif |
---|
363 | new_v_idx[k] = vert_list.Count(); |
---|
364 | vec3 PmV0 = (isec_v[k] - vert_list[t[isec_i[k]]].m1); |
---|
365 | vec3 V1mV0 = (vert_list[t[(isec_i[k] + 1) % 3]].m1 - vert_list[t[isec_i[k]]].m1); |
---|
366 | float alpha = length(PmV0) / length(V1mV0); |
---|
367 | vert_list.Push(isec_v[k], |
---|
368 | t[isec_i[k]], t[(isec_i[k] + 1) % 3], |
---|
369 | //Alpha = length((Point_Loc - Src_V0) / (Src_V1 - Src_V0)); |
---|
370 | alpha); |
---|
371 | } |
---|
372 | |
---|
373 | int v_idx0 = (isec_base == 1)?(1):(0); |
---|
374 | int v_idx1 = (isec_base == 1)?(0):(1); |
---|
375 | //Leaf_type is the type for the triangle that is alone on its side. |
---|
376 | int leaf_type = res_side[(isec_base + 2) % 3]; |
---|
377 | int tri_to_remove = tri_to_process.Count() - 1; |
---|
378 | |
---|
379 | #if 0 |
---|
380 | if (m_tree[leaf_idx].m_leaves[leaf_type] == LEAF_CURRENT && tri_to_process.Last().m1.Last() == 1) |
---|
381 | tri_list.Push(leaf_type, |
---|
382 | t[(isec_base + 2) % 3], new_v_idx[v_idx1], new_v_idx[v_idx0]); |
---|
383 | else |
---|
384 | { |
---|
385 | tri_to_process.Push(Array< int >(), t[(isec_base + 2) % 3], new_v_idx[v_idx1], new_v_idx[v_idx0], 0); |
---|
386 | tri_to_process.Last().m1.Push(0); |
---|
387 | } |
---|
388 | |
---|
389 | if (m_tree[leaf_idx].m_leaves[1 - leaf_type] == LEAF_CURRENT && tri_to_process.Last().m1.Last() == 1) |
---|
390 | { |
---|
391 | tri_list.Push((tri_to_process.Last().m5)?(LEAF_CURRENT):(1 - leaf_type), |
---|
392 | t[isec_base], new_v_idx[((isec_base + 1) % 3)], new_v_idx[v_idx0]); |
---|
393 | tri_list.Push((tri_to_process.Last().m5)?(LEAF_CURRENT):(1 - leaf_type), |
---|
394 | t[isec_base], new_v_idx[v_idx0], new_v_idx[v_idx1]); |
---|
395 | } |
---|
396 | else |
---|
397 | { |
---|
398 | tri_to_process.Push(Array< int >(), t[isec_base], t[((isec_base + 1) % 3)], new_v_idx[v_idx0], 0); |
---|
399 | tri_to_process.Last().m1.Push(0); |
---|
400 | tri_to_process.Push(Array< int >(), t[isec_base], new_v_idx[v_idx0], new_v_idx[v_idx1], 0); |
---|
401 | tri_to_process.Last().m1.Push(0); |
---|
402 | } |
---|
403 | #else |
---|
404 | int new_t[9] = { t[(isec_base + 2) % 3], new_v_idx[v_idx1], new_v_idx[v_idx0], |
---|
405 | t[isec_base], t[((isec_base + 1) % 3)], new_v_idx[v_idx0], |
---|
406 | t[isec_base], new_v_idx[v_idx0], new_v_idx[v_idx1] }; |
---|
407 | int new_side[3] = { res_side[(isec_base + 2) % 3], |
---|
408 | (res_side[isec_base] == LEAF_CURRENT)?(res_side[((isec_base + 1) % 3)]):(res_side[isec_base]), |
---|
409 | res_side[isec_base] }; |
---|
410 | |
---|
411 | //Error check : Skip the triangle where two points are on the same location. |
---|
412 | //it fixes the problem of having an intersection with one of the isec-point being on one of the triangle vertices. |
---|
413 | //(the problem being a very funny infinite loop) |
---|
414 | for(int k = 0; k < 9; k += 3) |
---|
415 | { |
---|
416 | #if 1 //Error check |
---|
417 | bool skip_tri = false; |
---|
418 | for(int l = 0; l < 3; l++) |
---|
419 | { |
---|
420 | if (length(vert_list[new_t[k + l]].m1 - vert_list[new_t[k + (l + 1) % 3]].m1) < CSG_EPSILON) |
---|
421 | { |
---|
422 | skip_tri = true; |
---|
423 | break; |
---|
424 | } |
---|
425 | } |
---|
426 | |
---|
427 | if (skip_tri) |
---|
428 | continue; |
---|
429 | #endif |
---|
430 | #if 0 //Send the newly created triangle back to the beginning |
---|
431 | tri_to_process.Push(Array< int >(), new_t[k], new_t[k + 1], new_t[k + 2], 0); |
---|
432 | tri_to_process.Last().m1.Push(0); |
---|
433 | #else //Inherit parent tree |
---|
434 | if (m_tree[leaf_idx].m_leaves[new_side[k / 3]] == LEAF_CURRENT && tri_to_process[tri_to_remove].m1.Count() == 1) |
---|
435 | tri_list.Push(new_side[k / 3], new_t[k], new_t[k + 1], new_t[k + 2]); |
---|
436 | else |
---|
437 | { |
---|
438 | tri_to_process.Push(Array< int >(), new_t[k], new_t[k + 1], new_t[k + 2], 0); |
---|
439 | tri_to_process.Last().m1 = tri_to_process[tri_to_remove].m1; |
---|
440 | if (m_tree[leaf_idx].m_leaves[new_side[k / 3]] == LEAF_CURRENT) |
---|
441 | tri_to_process.Last().m1.Pop(); |
---|
442 | else |
---|
443 | tri_to_process.Last().m1.Last() = m_tree[leaf_idx].m_leaves[new_side[k / 3]]; |
---|
444 | } |
---|
445 | #endif |
---|
446 | } |
---|
447 | #endif |
---|
448 | |
---|
449 | tri_to_process.Remove(tri_to_remove); |
---|
450 | } |
---|
451 | } |
---|
452 | } |
---|
453 | } |
---|
454 | //All points are on one side, transfer to the next leaf |
---|
455 | else if (res_nb[LEAF_BACK] || res_nb[LEAF_FRONT]) |
---|
456 | { |
---|
457 | int new_leaf_type = ((res_nb[LEAF_FRONT])?(LEAF_FRONT):(LEAF_BACK)); |
---|
458 | int new_leaf = m_tree[leaf_idx].m_leaves[new_leaf_type]; |
---|
459 | |
---|
460 | //No leaf exist, we're at the end |
---|
461 | if (new_leaf == LEAF_CURRENT) |
---|
462 | { |
---|
463 | //We still need to test other leaves. |
---|
464 | if (tri_to_process.Last().m1.Count() > 1) |
---|
465 | tri_to_process.Last().m1.Pop(); |
---|
466 | else |
---|
467 | { |
---|
468 | tri_list.Push((tri_to_process.Last().m5)?(LEAF_CURRENT):(new_leaf_type), |
---|
469 | tri_to_process.Last().m2, tri_to_process.Last().m3, tri_to_process.Last().m4); |
---|
470 | tri_to_process.Pop(); |
---|
471 | } |
---|
472 | } |
---|
473 | else |
---|
474 | tri_to_process.Last().m1.Last() = new_leaf; |
---|
475 | } |
---|
476 | //All points are on the current leaf, add the tri_idx to the list of this leaf. |
---|
477 | else |
---|
478 | { |
---|
479 | //TODO : Special case, handle coplanar cut. |
---|
480 | tri_list.Push(LEAF_CURRENT, tri_to_process.Last().m2, tri_to_process.Last().m3, tri_to_process.Last().m4); |
---|
481 | tri_to_process.Pop(); |
---|
482 | } |
---|
483 | } |
---|
484 | |
---|
485 | //Now that we have all the split points, let's double-check the results |
---|
486 | for (int i = 0; i < tri_list.Count(); i++) |
---|
487 | { |
---|
488 | #define TEST_MAX 4 |
---|
489 | int t[3] = { tri_list[i].m2, |
---|
490 | tri_list[i].m3, |
---|
491 | tri_list[i].m4 }; |
---|
492 | vec3 v[4] = { vert_list[t[0]].m1, |
---|
493 | vert_list[t[1]].m1, |
---|
494 | vert_list[t[2]].m1, |
---|
495 | (vert_list[t[0]].m1 + |
---|
496 | vert_list[t[1]].m1 + |
---|
497 | vert_list[t[2]].m1) / 3.0f }; |
---|
498 | |
---|
499 | int res_total = 0; |
---|
500 | int res_nb[3] = { 0, 0, 0 }; |
---|
501 | |
---|
502 | int res_Leaf[4] = { 0, 0, 0, 0 }; |
---|
503 | int res_side[4] = { -1, -1, -1, -1 }; |
---|
504 | while (res_total < TEST_MAX) |
---|
505 | { |
---|
506 | for (int k = 0; k < TEST_MAX; k++) |
---|
507 | { |
---|
508 | if (res_Leaf[k] != LEAF_CURRENT) |
---|
509 | { |
---|
510 | int result = TestPoint(res_Leaf[k], v[k]); |
---|
511 | if (result != LEAF_CURRENT) |
---|
512 | { |
---|
513 | res_Leaf[k] = m_tree[res_Leaf[k]].m_leaves[result]; |
---|
514 | res_side[k] = result; |
---|
515 | if (res_Leaf[k] == LEAF_CURRENT) |
---|
516 | { |
---|
517 | res_total++; |
---|
518 | res_nb[result]++; |
---|
519 | } |
---|
520 | } |
---|
521 | else |
---|
522 | { |
---|
523 | res_Leaf[k] = LEAF_CURRENT; |
---|
524 | res_side[k] = LEAF_CURRENT; |
---|
525 | res_total++; |
---|
526 | } |
---|
527 | } |
---|
528 | } |
---|
529 | } |
---|
530 | int k = 0; |
---|
531 | if (res_nb[LEAF_BACK] && res_nb[LEAF_FRONT]) |
---|
532 | { |
---|
533 | res_total = res_total; |
---|
534 | tri_list[i].m1 = LEAF_BACK; |
---|
535 | #if 0 |
---|
536 | tri_to_process.Push( Array< int >(), tri_list[i].m2, tri_list[i].m3, tri_list[i].m4, 0); |
---|
537 | tri_to_process.Last().m1.Push(0); |
---|
538 | tri_list.Remove(i--); |
---|
539 | break; |
---|
540 | #endif |
---|
541 | } |
---|
542 | else |
---|
543 | { |
---|
544 | for (; k < TEST_MAX; k++) |
---|
545 | { |
---|
546 | if (res_side[k] != LEAF_CURRENT) |
---|
547 | { |
---|
548 | tri_list[i].m1 = res_side[k]; |
---|
549 | break; |
---|
550 | } |
---|
551 | } |
---|
552 | if (k == TEST_MAX) |
---|
553 | tri_list[i].m1 = LEAF_FRONT; |
---|
554 | } |
---|
555 | } |
---|
556 | } |
---|
557 | |
---|
558 | if (tri_list.Count() == 1) |
---|
559 | return 0; |
---|
560 | return 1; |
---|
561 | } |
---|
562 | |
---|
563 | } /* namespace lol */ |
---|
564 | |
---|