| 420 | //---------------------------------------------------------------------------- |
| 421 | |
| 422 | bool DepthSortList::overlap(Poly * poly1, Poly * poly2) |
| 423 | { |
| 424 | // check for overlap without any shortcuts |
| 425 | S32 sz1 = poly1->vertexCount; |
| 426 | S32 sz2 = poly2->vertexCount; |
| 427 | |
| 428 | Point3F * a1, * b1; |
| 429 | Point3F * a2, * b2; |
| 430 | Point2F norm; |
| 431 | F32 dot; |
| 432 | b1 = &mVertexList[mIndexList[poly1->vertexStart+sz1-1]].point; |
| 433 | S32 i; |
| 434 | for (i=0; i<sz1; i++) |
| 435 | { |
| 436 | a1 = b1; |
| 437 | b1 = &mVertexList[mIndexList[poly1->vertexStart+i]].point; |
| 438 | |
| 439 | // get the mid-point of this edge |
| 440 | Point3F mid1 = *a1+*b1; |
| 441 | mid1 *= 0.5f; |
| 442 | bool midOutside = false; |
| 443 | |
| 444 | b2 = &mVertexList[mIndexList[poly2->vertexStart+sz2-1]].point; |
| 445 | for (S32 j=0; j<sz2; j++) |
| 446 | { |
| 447 | a2 = b2; |
| 448 | b2 = &mVertexList[mIndexList[poly2->vertexStart+j]].point; |
| 449 | |
| 450 | // test for intersection of a1-b1 and a2-b2 (on x-z plane) |
| 451 | |
| 452 | // they intersect if a1 & b1 are on opp. sides of line a2-b2 |
| 453 | // and a2 & b2 are on opp. sides of line a1-b1 |
| 454 | |
| 455 | norm.set(a2->z - b2->z, b2->x - a2->x); // normal to line a2-b2 |
| 456 | dot = norm.x * a2->x + norm.y * a2->z; // dot of a2 and norm |
| 457 | if (norm.x * mid1.x + norm.y * mid1.z - dot >= 0) // special check for midpoint of line |
| 458 | midOutside = true; |
| 459 | if ( ((norm.x * a1->x + norm.y * a1->z) - dot) * ((norm.x * b1->x + norm.y * b1->z) - dot) >= 0 ) |
| 460 | // a1 & b1 are on the same side of the line a2-b2...edges don't overlap |
| 461 | continue; |
| 462 | |
| 463 | norm.set(a1->z - b1->z, b1->x - a1->x); // normal to line a1-b1 |
| 464 | dot = norm.x * a1->x + norm.y * a1->z; // dot of a1 and norm |
| 465 | if ( ((norm.x * a2->x + norm.y * a2->z) - dot) * ((norm.x * b2->x + norm.y * b2->z) - dot) >= 0 ) |
| 466 | // a2 & b2 are on the same side of the line a1-b1...edges don't overlap |
| 467 | continue; |
| 468 | |
| 469 | return true; // edges overlap, so polys overlap |
| 470 | } |
| 471 | if (!midOutside) |
| 472 | return true; // midpoint of a1-b1 is inside the poly |
| 473 | } |
| 474 | |
| 475 | // edges don't overlap...but one poly might be contained inside the other |
| 476 | Point3F center = mVertexList[mIndexList[poly2->vertexStart]].point; |
| 477 | for (i=1; i<sz2; i++) |
| 478 | center += mVertexList[mIndexList[poly2->vertexStart+i]].point; |
| 479 | center *= 1.0f / (F32)poly2->vertexCount; |