Changeset 2226 for trunk/src/easymesh/easymesh.cpp
 Timestamp:
 Jan 17, 2013, 9:49:29 PM (7 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/src/easymesh/easymesh.cpp
r2211 r2226 2 2 // Lol Engine 3 3 // 4 // Copyright: (c) 2010201 2Sam Hocevar <sam@hocevar.net>5 // (c) 2009201 2Cédric Lecacheur <jordx@free.fr>6 // (c) 2009201 2 BenjaminHuet <huet.benjamin@gmail.com>4 // Copyright: (c) 20102013 Sam Hocevar <sam@hocevar.net> 5 // (c) 20092013 Cédric Lecacheur <jordx@free.fr> 6 // (c) 20092013 Benjamin "Touky" Huet <huet.benjamin@gmail.com> 7 7 // This program is free software; you can redistribute it and/or 8 8 // modify it under the terms of the Do What The Fuck You Want To … … 76 76 m_gpu.modelview = m_gpu.shader>GetUniformLocation("in_ModelView"); 77 77 m_gpu.view = m_gpu.shader>GetUniformLocation("in_View"); 78 78 m_gpu.invview = m_gpu.shader>GetUniformLocation("in_Inv_View"); 79 79 m_gpu.proj = m_gpu.shader>GetUniformLocation("in_Proj"); 80 80 m_gpu.normalmat = m_gpu.shader>GetUniformLocation("in_NormalMat"); … … 142 142 } 143 143 144 145 // 146 // "Collisions" functions 147 // 148 #define VX_ALONE 2 149 #define VX_MASTER 1 150 151 //helpers func to retrieve a vertex. 152 int FindVertexInDict(int search_idx, Array< int, int > const &vertex_dict) 153 { 154 //Resolve current vertex idx in the dictionnary (if exist) 155 for (int j = 0; j < vertex_dict.Count(); j++) 156 if (vertex_dict[j].m1 == search_idx) 157 return j; 158 return 1; 159 } 160 161 //helpers func to retrieve a triangle. 162 int FindTriangleInDict(int search_idx, Array< int, Array< vec3, vec3, vec3 > > const &triangle_isec) 163 { 164 //Resolve current vertex idx in the dictionnary (if exist) 165 for (int j = 0; j < triangle_isec.Count(); j++) 166 if (triangle_isec[j].m1 == search_idx) 167 return j; 168 return 1; 169 } 170 171 //Will update the given list with all the vertices on the same spot. 172 void EasyMesh::UpdateVertexDict(Array< int, int > &vertex_dict) 173 { 174 //First, build the vertex Dictionnary 175 for (int i = 0; i < m_vert.Count(); i++) 176 { 177 int CurIdx = FindVertexInDict(i, vertex_dict); 178 179 //go through all vertices and do the matchup. 180 if (CurIdx == 1) 181 { 182 for (int j = i + 1; j < m_vert.Count(); j++) 183 { 184 if (sqlength(m_vert[i].m1  m_vert[j].m1) < CSG_EPSILON) 185 { 186 if (CurIdx == 1) 187 { 188 CurIdx = vertex_dict.Count(); 189 vertex_dict.Push(i, VX_MASTER); 190 } 191 vertex_dict.Push(j, CurIdx); 192 } 193 } 194 } 195 } 196 } 197 198 void EasyMesh::MeshCsg(int csg_operation) 199 { 200 //A vertex dictionnary for vertices on the same spot. 201 Array< int, int > vertex_dict; 202 //This list keeps track of the triangle that will need deletion at the end. 203 Array< int > triangle_to_kill; 204 //Listing for each triangle of the vectors intersecting it. <tri_Id, <Point0, Point1, tri_isec_Normal>> 205 Array< int, Array< vec3, vec3, vec3 > > triangle_isec; 206 //keep a track of the intersection point on the triangle. <pos, side_id> 207 Array< vec3, int > triangle_vertex; 208 for (int k = 0; k < 10; k++) 209 triangle_vertex.Push(vec3(.0f), 0); 210 211 //bsp infos 212 CsgBsp mesh_bsp_0; 213 CsgBsp mesh_bsp_1; 214 215 //BSP BUILD : We use the brace logic, csg should be used as : "[ exp .... [exp .... csg]]" 216 int cursor_start = (m_cursors.Count() < 2)?(0):(m_cursors[(m_cursors.Count()  2)].m2); 217 for (int mesh_id = 0; mesh_id < 2; mesh_id++) 218 { 219 int start_point = (mesh_id == 0)?(cursor_start):(m_cursors.Last().m2); 220 int end_point = (mesh_id == 0)?(m_cursors.Last().m2):(m_indices.Count()); 221 CsgBsp &mesh_bsp = (mesh_id == 0)?(mesh_bsp_0):(mesh_bsp_1); 222 for (int i = start_point; i < end_point; i += 3) 223 mesh_bsp.AddTriangleToTree(i, m_vert[m_indices[i]].m1, m_vert[m_indices[i + 1]].m1, m_vert[m_indices[i + 2]].m1); 224 } 225 226 //BSP Useage : let's crunch all triangles on the correct BSP 227 int indices_count = m_indices.Count(); 228 for (int mesh_id = 0; mesh_id < 2; mesh_id++) 229 { 230 int start_point = (mesh_id == 0)?(cursor_start):(m_cursors.Last().m2); 231 int end_point = (mesh_id == 0)?(m_cursors.Last().m2):(indices_count); 232 CsgBsp &mesh_bsp = (mesh_id == 0)?(mesh_bsp_1):(mesh_bsp_0); 233 Array< vec3, int, int, float > vert_list; 234 Array< int, int, int, int > tri_list; 235 vec3 n0(.0f); vec3 n1(.0f); 236 vec4 c0(.0f); vec4 c1(.0f); 237 238 //Reserve some memory 239 vert_list.Reserve(3); 240 tri_list.Reserve(3); 241 242 for (int i = start_point; i < end_point; i += 3) 243 { 244 int Result = mesh_bsp.TestTriangleToTree(m_vert[m_indices[i]].m1, m_vert[m_indices[i + 1]].m1, m_vert[m_indices[i + 2]].m1, vert_list, tri_list); 245 int tri_base_idx = m_indices.Count(); 246 247 //one split has been done, we need to had the new vertices & the new triangles. 248 if (Result == 1) 249 { 250 triangle_to_kill.Push(i); 251 #if 1 252 int base_idx = m_vert.Count(); 253 for (int k = 3; k < vert_list.Count(); k++) 254 { 255 int P0 = (vert_list[k].m2 < 3)?(m_indices[i + vert_list[k].m2]):(base_idx + vert_list[k].m2  3); 256 int P1 = (vert_list[k].m3 < 3)?(m_indices[i + vert_list[k].m3]):(base_idx + vert_list[k].m3  3); 257 258 AddVertex(vert_list[k].m1); 259 260 //Normal : bad calculations there. 261 n0 = m_vert[P0].m2; 262 n1 = m_vert[P1].m2; 263 SetCurVertNormal(normalize(n0 + (n1  n0) * vert_list[k].m4)); 264 265 #if 1 266 //Color 267 c0 = m_vert[P0].m3; 268 c1 = m_vert[P1].m3; 269 vec4 res = c0 + ((c1  c0) * vert_list[k].m4); 270 SetCurVertColor(res); 271 #else 272 if (mesh_id == 0) 273 SetCurVertColor(vec4(1.0f, .0f, .0f, 1.0f)); 274 else 275 SetCurVertColor(vec4(.0f, 1.0f, 1.0f, 1.0f)); 276 #endif 277 } 278 for (int k = 0; k < tri_list.Count(); k++) 279 { 280 int P0 = (tri_list[k].m2 < 3)?(m_indices[i + tri_list[k].m2]):(base_idx + (tri_list[k].m2  3)); 281 int P1 = (tri_list[k].m3 < 3)?(m_indices[i + tri_list[k].m3]):(base_idx + (tri_list[k].m3  3)); 282 int P2 = (tri_list[k].m4 < 3)?(m_indices[i + tri_list[k].m4]):(base_idx + (tri_list[k].m4  3)); 283 AppendTriangle(P0, P1, P2, 0); 284 } 285 #endif 286 } 287 #if 1 288 //Main case 289 if (Result >= 0) 290 { 291 for (int k = 0; k < tri_list.Count(); k++) 292 { 293 int tri_idx = ((tri_list.Count() == 1)?(i):(tri_base_idx + k * 3)); 294 295 //Triangle Kill Test 296 if (//csgu : CSGUnion() > m0_Outside + m1_Outside 297 (csg_operation == CSG_UNION && tri_list[k].m1 == LEAF_BACK)  298 //csgs : CSGSubstract() > m0_Outside + m1_Insideinverted 299 (csg_operation == CSG_SUBSTRACT && 300 ((mesh_id == 0 && tri_list[k].m1 == LEAF_BACK)  301 (mesh_id == 1 && tri_list[k].m1 == LEAF_FRONT)))  302 //csga : CSGAnd() > Inside + Inside 303 (csg_operation == CSG_AND && tri_list[k].m1 == LEAF_FRONT)) 304 { 305 triangle_to_kill.Push(tri_idx); 306 } 307 308 //Triangle Invert Test 309 if (//csgs : CSGSubstract() > m0_Outside + m1_Insideinverted 310 (csg_operation == CSG_SUBSTRACT && mesh_id == 1 && tri_list[k].m1 == LEAF_BACK)  311 //csgx : CSGXor() > Outside/Insideinverted + Outside/Insideinverted 312 (csg_operation == CSG_XOR && tri_list[k].m1 == LEAF_BACK)) 313 { 314 //a Xor means we will share vertices with the outside, so duplicate the vertices. 315 //TODO : This operation disconnect all triangle, in some cases, not a good thing. 316 if (csg_operation == CSG_XOR) 317 { 318 for (int l = 0; l < 3; l++) 319 { 320 AddDuplicateVertex(m_indices[tri_idx + l]); 321 m_indices[tri_idx + l] = m_vert.Count()  1; 322 } 323 } 324 m_indices[tri_idx + 1] += m_indices[tri_idx + 2]; 325 m_indices[tri_idx + 2] = m_indices[tri_idx + 1]  m_indices[tri_idx + 2]; 326 m_indices[tri_idx + 1] = m_indices[tri_idx + 1]  m_indices[tri_idx + 2]; 327 ComputeNormals(tri_idx, 3); 328 } 329 } 330 } 331 #endif 332 vert_list.Empty(); 333 tri_list.Empty(); 334 } 335 } 336 337 for (int i = 0; i < m_vert.Count(); i++) 338 if (length(m_vert[i].m2) < 1.0f) 339 i = i; 340 341 int dir = 1; 342 for (int i = 0; i >= 0 && i < triangle_to_kill.Count()  1; i += dir) 343 { 344 if (triangle_to_kill[i] < triangle_to_kill[i + 1] && dir < 0) 345 dir = 1; 346 if (triangle_to_kill[i] == triangle_to_kill[i + 1]) 347 { 348 triangle_to_kill.Remove(i); 349 dir = 1; 350 } 351 if (triangle_to_kill[i] > triangle_to_kill[i + 1]) 352 { 353 triangle_to_kill[i] += triangle_to_kill[i + 1]; 354 triangle_to_kill[i + 1] = triangle_to_kill[i]  triangle_to_kill[i + 1]; 355 triangle_to_kill[i] = triangle_to_kill[i]  triangle_to_kill[i + 1]; 356 dir = 1; 357 } 358 if (i == 0 && dir == 1) 359 dir = 1; 360 } 361 for (int i = triangle_to_kill.Count()  1; i >= 0; i) 362 m_indices.Remove(triangle_to_kill[i], 3); 363 364 m_cursors.Last().m1 = m_vert.Count(); 365 m_cursors.Last().m2 = m_indices.Count(); 366 367 #if 0 368 UpdateVertexDict(vertex_dict); 369 370 for (int t0 = 0; t0 < m_indices.Count(); t0 += 3) 371 { 372 for (int t1 = t0 + 3; t1 < m_indices.Count(); t1 += 3) 373 { 374 int CommonVertices = 0; 375 //Search for common vertices, if > 1 the two triangle share a side, so no split is required. 376 for (int k = 0; k < 3; k++) 377 { 378 int ref_master = FindVertexInDict(m_indices[t0 + k], vertex_dict); 379 if (ref_master != 1) 380 { 381 if (vertex_dict[ref_master].m2 != VX_MASTER) 382 ref_master = vertex_dict[ref_master].m2; 383 for (int l = 0; l < 3; l++) 384 { 385 int test_master = FindVertexInDict(m_indices[t1 + l], vertex_dict); 386 if (test_master != 1) 387 { 388 if (vertex_dict[test_master].m2 != VX_MASTER) 389 test_master = vertex_dict[test_master].m2; 390 if (test_master == ref_master) 391 { 392 CommonVertices++; 393 break; 394 } 395 } 396 } 397 } 398 } 399 400 if (CommonVertices < 2) 401 { 402 vec3 iP0, iP1; 403 //Build the triangle intersection list 404 if (TriangleIsectTriangle(m_vert[m_indices[t0]].m1, m_vert[m_indices[t0 + 1]].m1, m_vert[m_indices[t0 + 2]].m1, 405 m_vert[m_indices[t1]].m1, m_vert[m_indices[t1 + 1]].m1, m_vert[m_indices[t1 + 2]].m1, 406 iP0, iP1)) 407 { 408 int CurIdx = FindTriangleInDict(t0, triangle_isec); 409 if (CurIdx == 1) 410 { 411 CurIdx = triangle_isec.Count(); 412 triangle_isec.Push(t0, Array<vec3, vec3, vec3>()); 413 } 414 triangle_isec[CurIdx].m2.Push(iP0, iP1, vec3(.0f)); 415 CurIdx = FindTriangleInDict(t1, triangle_isec); 416 if (CurIdx == 1) 417 { 418 CurIdx = triangle_isec.Count(); 419 triangle_isec.Push(t1, Array<vec3, vec3, vec3>()); 420 } 421 triangle_isec[CurIdx].m2.Push(iP0, iP1, vec3(.0f)); 422 } 423 } 424 } 425 } 426 427 /* seems to be counterproductive in some rare cases. */ 428 /* 429 //Every intersection has been found, let's remove those that exist twice. 430 for(int i = 0; i < triangle_isec.Count(); i++) 431 { 432 for(int j = 0; j < triangle_isec[i].m2.Count(); j++) 433 { 434 for(int k = j + 1; k < triangle_isec[i].m2.Count(); k++) 435 { 436 //if the two Dirvector are parallel & the fist Dirvector is parallel to the (P0, P1)vector, this is the same intersection, so kill it. 437 if (abs(dot(normalize(triangle_isec[i].m2[j].m2  triangle_isec[i].m2[j].m1), 438 normalize(triangle_isec[i].m2[k].m2  triangle_isec[i].m2[k].m1))) 439 >= 1.0 && 440 abs(dot(normalize(triangle_isec[i].m2[j].m2  triangle_isec[i].m2[j].m1), 441 normalize(triangle_isec[i].m2[k].m1  triangle_isec[i].m2[j].m1))) 442 >= 1.0 ) 443 triangle_isec[i].m2.Remove(k); 444 } 445 } 446 } 447 */ 448 449 //Now, the triangle intersection tab should be nice and cosy, so we can start actually cutting some triangles. 450 vec3 isecV[2] = { vec3(.0f), vec3(.0f) }; 451 int isecI[2] = { 1, 1 }; 452 int v_idx0 = 0; int v_idx1 = 0; 453 int new_v_idx[2] = { 0, 0 }; 454 vec3 n0(.0f); vec3 n1(.0f); 455 vec4 c0(.0f); vec4 c1(.0f); 456 for(int i = 0; i < triangle_isec.Count(); i++) 457 { 458 int tri_idx = triangle_isec[i].m1; 459 for(int j = 0; j < triangle_isec[i].m2.Count(); j++) 460 { 461 //Get intersection on actual triangle sides. 462 if (RayIsectTriangleSide(m_vert[m_indices[tri_idx]].m1, m_vert[m_indices[tri_idx + 1]].m1, m_vert[m_indices[tri_idx + 2]].m1, 463 triangle_isec[i].m2[j].m1, triangle_isec[i].m2[j].m2, 464 isecV[0], isecI[0], isecV[1], isecI[1])) 465 { 466 //Check if the found intersections point are in the triangle. If not, ignore. 467 //Cases are : 468 // 1) at least one dot is negative (one point in the triangle). 469 // 2) the two dot are positive but the intersection point are on all parts of the triangle, and therefore negative. 470 //If one of the point is on one side, some calculations tweak are needed. 471 //If the two points are on the triangle sides, just go with it. 472 bool should_proceed_with_cutting = true; 473 //find out if points are on one of the side 474 int p0_tri_idx = ((sqlength(triangle_isec[i].m2[j].m1  isecV[0]) < CSG_EPSILON)?(0):( 475 (sqlength(triangle_isec[i].m2[j].m1  isecV[1]) < CSG_EPSILON)?(1):(1))); 476 int p1_tri_idx = ((sqlength(triangle_isec[i].m2[j].m2  isecV[0]) < CSG_EPSILON)?(0):( 477 (sqlength(triangle_isec[i].m2[j].m2  isecV[1]) < CSG_EPSILON)?(1):(1))); 478 if (p0_tri_idx < 0  p1_tri_idx < 0) 479 { 480 float dot0 = (p0_tri_idx >= 0)?(1.0f):(dot(triangle_isec[i].m2[j].m1  isecV[0], 481 triangle_isec[i].m2[j].m1  isecV[1])); 482 float dot1 = (p1_tri_idx >= 0)?(1.0f):(dot(triangle_isec[i].m2[j].m2  isecV[0], 483 triangle_isec[i].m2[j].m2  isecV[1])); 484 float dot2 = dot(triangle_isec[i].m2[j].m1  isecV[(p0_tri_idx == 1)?(0):(1  p0_tri_idx)], 485 triangle_isec[i].m2[j].m2  isecV[(p1_tri_idx == 1)?(0):(1  p1_tri_idx)]); 486 should_proceed_with_cutting = (((dot0 < .0f)  dot1 < .0f)  (dot0 > .0f && dot1 > .0f && dot2 < .0f)); 487 } 488 if (should_proceed_with_cutting) 489 { 490 //Add the new vertices 491 int b_idx = 0; 492 for(int k = 0; k < 2; k++) 493 { 494 if (b_idx == isecI[k]) 495 b_idx++; 496 497 new_v_idx[k] = m_vert.Count(); 498 AddVertex(isecV[k]); 499 //bad calculations of normal there. 500 n0 = m_vert[m_indices[tri_idx + isecI[k]]].m2; 501 n1 = m_vert[m_indices[tri_idx + (isecI[k] + 1) % 3]].m2; 502 SetCurVertNormal(normalize((n0 + n1) * .5f)); 503 //color 504 #if 0 505 c0 = m_vert[m_indices[tri_idx + isecI[k]]].m3; 506 c1 = m_vert[m_indices[tri_idx + (isecI[k] + 1) % 3]].m3; 507 SetCurVertColor((c0 + c1) * .5f); 508 #else 509 SetCurVertColor(vec4(1.0f, 0.0f, 0.0f, 1.0f)); 510 #endif 511 } 512 513 //small trick, b_idx is the side index that has no intersection. 514 v_idx0 = (b_idx == 1)?(1):(0); 515 v_idx1 = (b_idx == 1)?(0):(1); 516 517 //Add the new triangles 518 AppendTriangle(m_indices[tri_idx + b_idx], new_v_idx[v_idx0], new_v_idx[v_idx1], 0); 519 AppendTriangle(m_indices[tri_idx + ((b_idx + 2) % 3)], new_v_idx[v_idx1], new_v_idx[v_idx0], 0); 520 //Replace the current triangle by on of the new one, instead of erasing it. 521 m_indices[tri_idx + ((b_idx + 2) % 3)] = new_v_idx[v_idx0]; 522 523 if (j + 1 < triangle_isec[i].m2.Count()) 524 { 525 triangle_isec[i].m2.Remove(j); 526 //add the two new triangle to the checklist. 527 triangle_isec.Push(m_indices.Count()  6, triangle_isec[i].m2); 528 triangle_isec.Push(m_indices.Count()  3, triangle_isec[i].m2); 529 } 530 } 531 } 532 } 533 } 534 #endif 535 //DONE for the splitting ! 536 } 537 538 539 // 540 144 541 void EasyMesh::ToggleScaleWinding() 145 542 { … … 435 832 * is a vertex at [0 1 0] and [0 1 0] after normalisation. */ 436 833 float phi = 0.5f + 0.5f * sqrt(5.f); 437 mat3 mat = mat3::rotate(asin(1.f / sqrt(2.f + phi)) * (180.f / M_PI),834 mat3 mat = mat3::rotate(asin(1.f / sqrt(2.f + phi)) * (180.f / (float)M_PI), 438 835 vec3(0.f, 0.f, 1.f)); 439 836 for (int i = 0; i < 4; i++) … … 539 936 int i2 = (i + di) % nidiv; 540 937 int j2 = (j + dj) % njdiv; 541 float x = 0.5f * (r1 + r2) + 0.5 * (r2  r1) *lol::cos(2.0 * M_PI * i2 / nidiv);542 float y = 0.5f * (r2  r1) * lol::sin(2.0 * M_PI * i2 / nidiv);938 float x = 0.5f * (r1 + r2) + 0.5f * (r2  r1) * (float)lol::cos(2.0 * M_PI * i2 / nidiv); 939 float y = 0.5f * (r2  r1) * (float)lol::sin(2.0 * M_PI * i2 / nidiv); 543 940 float z = 0.0f; 544 941 545 float ca = lol::cos(2.0 * M_PI * j2 / njdiv);546 float sa = lol::sin(2.0 * M_PI * j2 / njdiv);942 float ca = (float)lol::cos(2.0 * M_PI * j2 / njdiv); 943 float sa = (float)lol::sin(2.0 * M_PI * j2 / njdiv); 547 944 float x2 = x * ca  z * sa; 548 945 float z2 = z * ca + x * sa;
Note: See TracChangeset
for help on using the changeset viewer.