Main Page   Namespace List   Class Hierarchy   Compound List   File List   Compound Members   File Members  

polygon.cpp File Reference

#include <windows.h>
#include "polygon.h"
#include "locmath.h"
#include "collision.h"
#include "general.h"
#include "bsp.h"
#include "mmgr.h"

Go to the source code of this file.

Functions

VECTOR GetEdgeIntersection (VECTOR point0, VECTOR point1, POLYGON planePolygon)
int SplitPolygon (POLYGON triangleToSplit, POLYGON planeTriangle, POLYGON *triangles)


Function Documentation

VECTOR GetEdgeIntersection VECTOR    point0,
VECTOR    point1,
POLYGON    planePolygon
 

Definition at line 66 of file polygon.cpp.

References CrossVector(), DotProduct(), POLYGON::Vertex, VECTOR::x, VERTEX::x, VECTOR::y, VERTEX::y, VECTOR::z, and VERTEX::z.

Referenced by SplitPolygon(), and SplitPortal().

00067 {
00068     VECTOR edge1, edge2, planeNormal, pointOnPlane, intersection, temp;
00069     float numerator, denominator, t;
00070 
00071     // get a point on the plane
00072     pointOnPlane.x = planePolygon.Vertex[0].x;
00073     pointOnPlane.y = planePolygon.Vertex[0].y;
00074     pointOnPlane.z = planePolygon.Vertex[0].z;
00075 
00076     // get the splitting planes normal
00077     edge1.x = planePolygon.Vertex[1].x - planePolygon.Vertex[0].x;
00078     edge1.y = planePolygon.Vertex[1].y - planePolygon.Vertex[0].y;
00079     edge1.z = planePolygon.Vertex[1].z - planePolygon.Vertex[0].z;
00080     edge2.x = planePolygon.Vertex[2].x - planePolygon.Vertex[0].x;
00081     edge2.y = planePolygon.Vertex[2].y - planePolygon.Vertex[0].y;
00082     edge2.z = planePolygon.Vertex[2].z - planePolygon.Vertex[0].z;
00083     planeNormal = CrossVector(edge1, edge2);
00084 
00085 // find edge intersection:
00086 // intersection = p0 + (p1 - p0) * t
00087 // where t = (planeNormal . (pointOnPlane - p0)) / (planeNormal . (p1 - p0))
00088 
00089     //planeNormal . (pointOnPlane - point0)
00090     temp.x = pointOnPlane.x - point0.x;
00091     temp.y = pointOnPlane.y - point0.y;
00092     temp.z = pointOnPlane.z - point0.z;
00093     numerator = DotProduct(planeNormal, temp);
00094 
00095     //planeNormal . (point1 - point0)
00096     temp.x = point1.x - point0.x;
00097     temp.y = point1.y - point0.y;
00098     temp.z = point1.z - point0.z;
00099     denominator = DotProduct(planeNormal, temp);
00100 
00101     if (denominator)
00102         t = numerator / denominator;
00103     else
00104         t = 0.0;
00105 
00106     intersection.x = point0.x + temp.x * t;
00107     intersection.y = point0.y + temp.y * t;
00108     intersection.z = point0.z + temp.z * t;
00109 
00110     return intersection;
00111 }

int SplitPolygon POLYGON    triangleToSplit,
POLYGON    planeTriangle,
POLYGON   triangles
 

Definition at line 384 of file polygon.cpp.

References Back, ClassifyPoint(), CrossVector(), Front, GetEdgeIntersection(), POLYGON::numVertices, OneFrontOneBack, OneFrontTwoBack, POLYGON::SetNormal(), TwoFrontOneBack, VERTEX::u, VERTEX::v, POLYGON::Vertex, VECTOR::x, VERTEX::x, VECTOR::y, VERTEX::y, VECTOR::z, and VERTEX::z.

Referenced by BuildBSP(), and SelectPartitionfromList().

00385 {
00386     VECTOR planeNormal, polysNormal, pointOnPlane, edge1, edge2, temp;
00387     VERTEX ptA, ptB, outpts[4], inpts[4], intersection;
00388     int count = 0, out_c = 0, in_c = 0, sideA, sideB, outputFlag;
00389     VERTEX texvert1, texvert2; // texture calculation variables
00390     VECTOR t1, t2;
00391     float scale;
00392 
00393     // get a point on the plane
00394     pointOnPlane.x = planeTriangle.Vertex[0].x;
00395     pointOnPlane.y = planeTriangle.Vertex[0].y;
00396     pointOnPlane.z = planeTriangle.Vertex[0].z;
00397 
00398     // get the splitting planes normal
00399     edge1.x = planeTriangle.Vertex[1].x - planeTriangle.Vertex[0].x;
00400     edge1.y = planeTriangle.Vertex[1].y - planeTriangle.Vertex[0].y;
00401     edge1.z = planeTriangle.Vertex[1].z - planeTriangle.Vertex[0].z;
00402     edge2.x = planeTriangle.Vertex[2].x - planeTriangle.Vertex[0].x;
00403     edge2.y = planeTriangle.Vertex[2].y - planeTriangle.Vertex[0].y;
00404     edge2.z = planeTriangle.Vertex[2].z - planeTriangle.Vertex[0].z;
00405     planeNormal = CrossVector(edge1, edge2);
00406 
00407     // get the normal of the triangle to split
00408     edge1.x = triangleToSplit.Vertex[1].x - triangleToSplit.Vertex[0].x;
00409     edge1.y = triangleToSplit.Vertex[1].y - triangleToSplit.Vertex[0].y;
00410     edge1.z = triangleToSplit.Vertex[1].z - triangleToSplit.Vertex[0].z;
00411     edge2.x = triangleToSplit.Vertex[2].x - triangleToSplit.Vertex[0].x;
00412     edge2.y = triangleToSplit.Vertex[2].y - triangleToSplit.Vertex[0].y;
00413     edge2.z = triangleToSplit.Vertex[2].z - triangleToSplit.Vertex[0].z;
00414     polysNormal = CrossVector(edge1, edge2);
00415 
00416     // check if the triangle lies on the plane
00417     for (int loop = 0; loop < 3; loop++)
00418     {
00419         temp.x = triangleToSplit.Vertex[loop].x;
00420         temp.y = triangleToSplit.Vertex[loop].y;
00421         temp.z = triangleToSplit.Vertex[loop].z;
00422         if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00423             count++;
00424         else
00425             break;
00426     }
00427     if (count == 3)
00428     {
00429         if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == 1)
00430             return Front;
00431         if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == -1)
00432             return Back;
00433     }
00434 
00435     // find if all of the points are infront of or behind the plane
00436     int frontcount = 0, backcount = 0;
00437     for (int loop = 0; loop < 3; loop++)
00438     {
00439         temp.x = triangleToSplit.Vertex[loop].x;
00440         temp.y = triangleToSplit.Vertex[loop].y;
00441         temp.z = triangleToSplit.Vertex[loop].z;
00442         if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00443         {
00444             frontcount++;
00445             backcount++;
00446         }
00447         else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 1)
00448             frontcount++;
00449         else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == -1)
00450             backcount++;
00451     }
00452     if (frontcount == 3)
00453             return Front;
00454     if (backcount == 3)
00455             return Back;
00456 
00457     // try to split the triangle
00458     ptA = triangleToSplit.Vertex[2];
00459     temp.x = ptA.x;
00460     temp.y = ptA.y;
00461     temp.z = ptA.z;
00462     sideA = ClassifyPoint(temp, pointOnPlane, planeNormal);
00463     for (int i = -1; ++i < 3;)
00464     {
00465         ptB = triangleToSplit.Vertex[i];
00466         temp.x = ptB.x;
00467         temp.y = ptB.y;
00468         temp.z = ptB.z;
00469         sideB = ClassifyPoint(temp, pointOnPlane, planeNormal);
00470         if (sideB > 0)
00471         {
00472             if (sideA < 0)
00473             {
00474                 // find intersection
00475                 edge1.x = ptA.x;
00476                 edge1.y = ptA.y;
00477                 edge1.z = ptA.z;
00478                 edge2.x = ptB.x;
00479                 edge2.y = ptB.y;
00480                 edge2.z = ptB.z;
00481 
00482                 temp = GetEdgeIntersection(edge1, edge2, planeTriangle);
00483                 intersection.x = temp.x;
00484                 intersection.y = temp.y;
00485                 intersection.z = temp.z;
00486 
00487                 // find the new texture coordinates
00488                 texvert1.x = ptB.x - ptA.x;
00489                 texvert1.y = ptB.y - ptA.y;
00490                 texvert1.z = ptB.z - ptA.z;
00491                 texvert2.x = intersection.x - ptA.x;
00492                 texvert2.y = intersection.y - ptA.y;
00493                 texvert2.z = intersection.z - ptA.z;
00494                 texvert1.u = ptA.u;
00495                 texvert2.u = ptB.u;
00496                 texvert1.v = ptA.v;
00497                 texvert2.v = ptB.v;
00498                 t1.x = texvert1.x;
00499                 t1.y = texvert1.y;
00500                 t1.z = texvert1.z;
00501                 t2.x = texvert2.x;
00502                 t2.y = texvert2.y;
00503                 t2.z = texvert2.z;
00504                 scale = sqrt(t2.x*t2.x+t2.y*t2.y+t2.z*t2.z)/sqrt(t1.x*t1.x+t1.y*t1.y+t1.z*t1.z);
00505                 intersection.u = texvert1.u + (texvert2.u - texvert1.u) * scale;
00506                 intersection.v = texvert1.v + (texvert2.v - texvert1.v) * scale;
00507 
00508                 outpts[out_c++] = inpts[in_c++] = intersection;
00509             }
00510             inpts[in_c++] = ptB;
00511         }
00512         else if (sideB < 0)
00513         {
00514             if (sideA > 0)
00515             {
00516                 // find intersection
00517                 edge1.x = ptA.x;
00518                 edge1.y = ptA.y;
00519                 edge1.z = ptA.z;
00520                 edge2.x = ptB.x;
00521                 edge2.y = ptB.y;
00522                 edge2.z = ptB.z;
00523 
00524                 temp = GetEdgeIntersection(edge1, edge2, planeTriangle);
00525                 intersection.x = temp.x;
00526                 intersection.y = temp.y;
00527                 intersection.z = temp.z;
00528 
00529                 // find the new texture coordinates
00530                 texvert1.x = ptB.x - ptA.x;
00531                 texvert1.y = ptB.y - ptA.y;
00532                 texvert1.z = ptB.z - ptA.z;
00533                 texvert2.x = intersection.x - ptA.x;
00534                 texvert2.y = intersection.y - ptA.y;
00535                 texvert2.z = intersection.z - ptA.z;
00536                 texvert1.u = ptA.u;
00537                 texvert2.u = ptB.u;
00538                 texvert1.v = ptA.v;
00539                 texvert2.v = ptB.v;
00540                 t1.x = texvert1.x;
00541                 t1.y = texvert1.y;
00542                 t1.z = texvert1.z;
00543                 t2.x = texvert2.x;
00544                 t2.y = texvert2.y;
00545                 t2.z = texvert2.z;
00546                 scale = sqrt(t2.x*t2.x+t2.y*t2.y+t2.z*t2.z)/sqrt(t1.x*t1.x+t1.y*t1.y+t1.z*t1.z);
00547                 intersection.u = texvert1.u + (texvert2.u - texvert1.u) * scale;
00548                 intersection.v = texvert1.v + (texvert2.v - texvert1.v) * scale;
00549 
00550                 outpts[out_c++] = inpts[in_c++] = intersection;
00551             }
00552             outpts[out_c++] = ptB;
00553         }
00554         else
00555             outpts[out_c++] = inpts[in_c++] = ptB;
00556             ptA = ptB;
00557             sideA = sideB;
00558     }
00559 
00560     if (in_c == 4)          // two triangles are infront, one behind
00561     {
00562         outputFlag = TwoFrontOneBack;
00563         if (triangles)
00564         {
00565             triangles[0].Vertex[0] = inpts[0];
00566             triangles[0].Vertex[1] = inpts[1];
00567             triangles[0].Vertex[2] = inpts[2];
00568             triangles[0].numVertices = 3;
00569             triangles[0].SetNormal();
00570             triangles[1].Vertex[0] = inpts[0];
00571             triangles[1].Vertex[1] = inpts[2];
00572             triangles[1].Vertex[2] = inpts[3];
00573             triangles[1].numVertices = 3;
00574             triangles[1].SetNormal();
00575             triangles[2].Vertex[0] = outpts[0];
00576             triangles[2].Vertex[1] = outpts[1];
00577             triangles[2].Vertex[2] = outpts[2];
00578             triangles[2].numVertices = 3;
00579             triangles[2].SetNormal();
00580         }
00581     }
00582     else if (out_c == 4)    // one triangle is infront, two behind
00583     {
00584         outputFlag = OneFrontTwoBack;
00585         if (triangles)
00586         {
00587             triangles[0].Vertex[0] = inpts[0];
00588             triangles[0].Vertex[1] = inpts[1];
00589             triangles[0].Vertex[2] = inpts[2];
00590             triangles[0].numVertices = 3;
00591             triangles[0].SetNormal();
00592             triangles[1].Vertex[0] = outpts[0];
00593             triangles[1].Vertex[1] = outpts[1];
00594             triangles[1].Vertex[2] = outpts[2];
00595             triangles[1].numVertices = 3;
00596             triangles[1].SetNormal();
00597             triangles[2].Vertex[0] = outpts[0];
00598             triangles[2].Vertex[1] = outpts[2];
00599             triangles[2].Vertex[2] = outpts[3];
00600             triangles[2].numVertices = 3;
00601             triangles[2].SetNormal();
00602         }
00603     }
00604     else if (in_c == 3 && out_c == 3)  // plane bisects the triangle
00605     {
00606         outputFlag = OneFrontOneBack;
00607         if (triangles)
00608         {
00609             triangles[0].Vertex[0] = inpts[0];
00610             triangles[0].Vertex[1] = inpts[1];
00611             triangles[0].Vertex[2] = inpts[2];
00612             triangles[0].numVertices = 3;
00613             triangles[0].SetNormal();
00614             triangles[1].Vertex[0] = outpts[0];
00615             triangles[1].Vertex[1] = outpts[1];
00616             triangles[1].Vertex[2] = outpts[2];
00617             triangles[1].numVertices = 3;
00618             triangles[1].SetNormal();
00619         }
00620     }
00621     else // then triangle must be totally infront of or behind the plane
00622     {
00623         int side;
00624 
00625         for (int loop = 0; loop < 3; loop++)
00626         {
00627             temp.x = triangleToSplit.Vertex[loop].x;
00628             temp.y = triangleToSplit.Vertex[loop].y;
00629             temp.z = triangleToSplit.Vertex[loop].z;
00630             side = ClassifyPoint(temp, pointOnPlane, planeNormal);
00631             if (side == 1)
00632             {
00633                 outputFlag = Front;
00634                 break;
00635             }
00636             else if (side == -1)
00637             {
00638                 outputFlag = Back;
00639                 break;
00640             }
00641         }
00642     }
00643     return outputFlag;
00644 }


Generated on Fri Dec 23 05:19:58 2005 for Particles by doxygen1.2.15