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

polygon.h File Reference

#include "vector.h"
#include "vertex.h"

Go to the source code of this file.

Compounds

class  POLYGON

Functions

void DeleteList (POLYGON *Poly)
int SplitPolygon (POLYGON *PolygonToSplit, POLYGON inputplanePolygon, POLYGON *front, POLYGON *back)
int SplitTriangle (POLYGON triangleToSplit, POLYGON planeTriangle, POLYGON *triangles)
int ClassifyPolygon (POLYGON *Polygon, POLYGON planePolygon)
void InvertPolygon (POLYGON *Polygon)
VECTOR GetEdgeIntersection (VECTOR point0, VECTOR point1, POLYGON planePolygon)

Variables

const int maxPolygonVerts = 20


Function Documentation

int ClassifyPolygon POLYGON   Polygon,
POLYGON    planePolygon
 

Definition at line 577 of file polygon.cpp.

References Back, ClassifyPoint(), VERTEX::coords, CrossVector(), Front, POLYGON::numVertices, OnPartition, PolygonWasSplit, and POLYGON::Vertex.

Referenced by CSGClipPolygon().

00578 {
00579     int numVerts = Polygon->numVertices;
00580     int count = 0;
00581     VECTOR planeNormal, polysNormal, pointOnPlane, edge1, edge2, temp;
00582 
00583     // get a point on the plane
00584     pointOnPlane = planePolygon.Vertex[0].coords;
00585 
00586     // get the planes normal
00587     edge1 = planePolygon.Vertex[1].coords - planePolygon.Vertex[0].coords;
00588     edge2 = planePolygon.Vertex[2].coords - planePolygon.Vertex[0].coords;
00589     planeNormal = CrossVector(edge1, edge2);
00590 
00591     // get the normal of the Polygon
00592     edge1 = Polygon->Vertex[1].coords - Polygon->Vertex[0].coords;
00593     edge2 = Polygon->Vertex[2].coords - Polygon->Vertex[0].coords;
00594     polysNormal = CrossVector(edge1, edge2);
00595 
00596     // check if the polygon lies on the plane
00597     for (int loop = 0; loop < numVerts; loop++)
00598     {
00599         temp = Polygon->Vertex[loop].coords;
00600         if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00601             count++;
00602         else
00603             break;
00604     }
00605     if (count == numVerts)
00606             return OnPartition;
00607 
00608     // find if all of the points are infront of or behind the plane
00609     int result, frontcount = 0, backcount = 0;
00610     for (int loop = 0; loop < numVerts; loop++)
00611     {
00612         temp = Polygon->Vertex[loop].coords;
00613         result = ClassifyPoint(temp, pointOnPlane, planeNormal);
00614         if (result == 0)
00615         {
00616             frontcount++;
00617             backcount++;
00618         }
00619         else
00620             if (result == 1)
00621                 frontcount++;
00622         else
00623             if (result == -1)
00624                 backcount++;
00625     }
00626     if (frontcount == numVerts)
00627             return Front;
00628     if (backcount == numVerts)
00629             return Back;
00630 
00631     return PolygonWasSplit;
00632 }

void DeleteList POLYGON   Poly
 

Definition at line 164 of file polygon.cpp.

References POLYGON::GetNext(), and POLYGON::IsLast().

Referenced by CSGAddition(), DeleteList(), and ResetBrushes().

00165 {
00166     if (Poly->IsLast())
00167     {
00168         delete Poly;
00169         return;
00170     }
00171 
00172     DeleteList(Poly->GetNext());
00173     delete Poly;
00174 }

VECTOR GetEdgeIntersection VECTOR    point0,
VECTOR    point1,
POLYGON    planePolygon
 

Definition at line 127 of file polygon.cpp.

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

Referenced by SplitPolygon(), SplitPortal(), and SplitTriangle().

00128 {
00129     VECTOR edge1, edge2, planeNormal, pointOnPlane, intersection, temp;
00130     float numerator, denominator, t;
00131 
00132     // get a point on the plane
00133     pointOnPlane = planePolygon.Vertex[0].coords;
00134 
00135     // get the splitting planes normal
00136     edge1 = planePolygon.Vertex[1].coords - planePolygon.Vertex[0].coords;
00137     edge2 = planePolygon.Vertex[2].coords - planePolygon.Vertex[0].coords;
00138     planeNormal = CrossVector(edge1, edge2);
00139 
00140 // find edge intersection:
00141 // intersection = p0 + (p1 - p0) * t
00142 // where t = (planeNormal . (pointOnPlane - p0)) / (planeNormal . (p1 - p0))
00143 
00144     //planeNormal . (pointOnPlane - point0)
00145     temp = pointOnPlane - point0;
00146     numerator = DotProduct(planeNormal, temp);
00147 
00148     //planeNormal . (point1 - point0)
00149     temp = point1 - point0;
00150     denominator = DotProduct(planeNormal, temp);
00151 
00152     if (denominator)
00153         t = numerator / denominator;
00154     else
00155         t = 0.0;
00156 
00157     intersection.x = point0.x + temp.x * t;
00158     intersection.y = point0.y + temp.y * t;
00159     intersection.z = point0.z + temp.z * t;
00160 
00161     return intersection;
00162 }

void InvertPolygon POLYGON   Polygon
 

Definition at line 634 of file polygon.cpp.

References POLYGON::numVertices, POLYGON::SetNormal(), and POLYGON::Vertex.

00635 {
00636     POLYGON temppolygon = *Polygon;
00637     for (int loop = 0; loop < Polygon->numVertices; loop++)
00638         Polygon->Vertex[loop] = temppolygon.Vertex[(Polygon->numVertices - 1) - loop];
00639     Polygon->SetNormal();
00640     return;
00641 }

int SplitPolygon POLYGON   PolygonToSplit,
POLYGON    inputplanePolygon,
POLYGON   front,
POLYGON   back
 

Definition at line 176 of file polygon.cpp.

References Back, ClassifyPoint(), VERTEX::coords, CrossVector(), Front, GetEdgeIntersection(), POLYGON::numVertices, OnPartition, PolygonWasSplit, VERTEX::polyNumber, POLYGON::removable, POLYGON::SetNormal(), POLYGON::Texture, VERTEX::u, VERTEX::v, POLYGON::Vertex, VECTOR::x, VECTOR::y, and VECTOR::z.

Referenced by CSGClipPolygon().

00177 {
00178     const int MaxVerts = 100;
00179     int numVerts = PolygonToSplit->numVertices;
00180     int count = 0, out_c = 0, in_c = 0, sideA, sideB, loop;
00181     VECTOR planeNormal, polysNormal, pointOnPlane, edge1, edge2, temp;
00182     VERTEX ptA, ptB, intersection, outpts[MaxVerts], inpts[MaxVerts];
00183     VERTEX texvert1, texvert2; // texture calculation variables
00184     VECTOR t1, t2;
00185     float scale;
00186     int PolygonNumber = PolygonToSplit->Vertex[0].polyNumber;
00187     int Removable = PolygonToSplit->removable;
00188     GLuint Tex = PolygonToSplit->Texture;
00189 
00190     // get a point on the plane
00191     pointOnPlane = inputplanePolygon.Vertex[0].coords;
00192 
00193     // get the splitting planes normal
00194     edge1 = inputplanePolygon.Vertex[1].coords - inputplanePolygon.Vertex[0].coords;
00195     edge2 = inputplanePolygon.Vertex[2].coords - inputplanePolygon.Vertex[0].coords;
00196     planeNormal = CrossVector(edge1, edge2);
00197 
00198     // get the normal of the portal to split
00199     edge1 = PolygonToSplit->Vertex[1].coords - PolygonToSplit->Vertex[0].coords;
00200     edge2 = PolygonToSplit->Vertex[2].coords - PolygonToSplit->Vertex[0].coords;
00201     polysNormal = CrossVector(edge1, edge2);
00202 
00203     // check if the polygon lies on the plane
00204     for (int loop = 0; loop < numVerts; loop++)
00205     {
00206         temp = PolygonToSplit->Vertex[loop].coords;
00207         if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00208             count++;
00209         else
00210             break;
00211     }
00212 
00213     if (count == numVerts)
00214         return OnPartition;
00215 
00216     // find if all of the points are infront of or behind the plane
00217     int frontcount = 0, backcount = 0;
00218     for (int loop = 0; loop < numVerts; loop++)
00219     {
00220         temp = PolygonToSplit->Vertex[loop].coords;
00221         if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00222         {
00223             frontcount++;
00224             backcount++;
00225         }
00226         else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 1)
00227             frontcount++;
00228         else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == -1)
00229             backcount++;
00230     }
00231     if (frontcount == numVerts)
00232             return Front;
00233     if (backcount == numVerts)
00234             return Back;
00235 
00236     // try to split the polygon
00237     ptA = PolygonToSplit->Vertex[numVerts - 1];
00238     temp = ptA.coords;
00239     sideA = ClassifyPoint(temp, pointOnPlane, planeNormal);
00240     for (int i = -1; ++i < numVerts;)
00241     {
00242         ptB = PolygonToSplit->Vertex[i];
00243         temp = ptB.coords;
00244         sideB = ClassifyPoint(temp, pointOnPlane, planeNormal);
00245         if (sideB > 0)
00246         {
00247             if (sideA < 0)
00248             {
00249                 // find intersection
00250                 edge1 = ptA.coords;
00251                 edge2 = ptB.coords;
00252 
00253                 temp = GetEdgeIntersection(edge1, edge2, inputplanePolygon);
00254                 intersection.coords = temp;
00255 
00256                 // find the new texture coordinates
00257                 texvert1.coords = ptB.coords - ptA.coords;
00258                 texvert2.coords = intersection.coords - ptA.coords;
00259                 texvert1.u = ptA.u;
00260                 texvert2.u = ptB.u;
00261                 texvert1.v = ptA.v;
00262                 texvert2.v = ptB.v;
00263                 t1 = texvert1.coords;
00264                 t2 = texvert2.coords;
00265                 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);
00266                 intersection.u = texvert1.u + (texvert2.u - texvert1.u) * scale;
00267                 intersection.v = texvert1.v + (texvert2.v - texvert1.v) * scale;
00268 
00269                 outpts[out_c++] = inpts[in_c++] = intersection;
00270             }
00271             inpts[in_c++] = ptB;
00272         }
00273         else if (sideB < 0)
00274         {
00275             if (sideA > 0)
00276             {
00277                 // find intersection
00278                 edge1 = ptA.coords;
00279                 edge2 = ptB.coords;
00280 
00281                 temp = GetEdgeIntersection(edge1, edge2, inputplanePolygon);
00282                 intersection.coords = temp;
00283 
00284                 // find the new texture coordinates
00285                 texvert1.coords = ptB.coords - ptA.coords;
00286                 texvert2.coords = intersection.coords - ptA.coords;
00287                 texvert1.u = ptA.u;
00288                 texvert2.u = ptB.u;
00289                 texvert1.v = ptA.v;
00290                 texvert2.v = ptB.v;
00291                 t1 = texvert1.coords;
00292                 t2 = texvert2.coords;
00293                 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);
00294                 intersection.u = texvert1.u + (texvert2.u - texvert1.u) * scale;
00295                 intersection.v = texvert1.v + (texvert2.v - texvert1.v) * scale;
00296 
00297                 outpts[out_c++] = inpts[in_c++] = intersection;
00298             }
00299             outpts[out_c++] = ptB;
00300         }
00301         else
00302             outpts[out_c++] = inpts[in_c++] = ptB;
00303         ptA = ptB;
00304         sideA = sideB;
00305     }
00306 
00307     if (out_c == 0 || in_c == 0)
00308     {
00309         int side;
00310 
00311         for (int loop = 0; loop < numVerts; loop++)
00312         {
00313             temp = PolygonToSplit->Vertex[loop].coords;
00314             side = ClassifyPoint(temp, pointOnPlane, planeNormal);
00315             if (side == 1)
00316                 return Front;
00317             else if (side == -1)
00318                 return Back;
00319         }
00320     }
00321     else
00322     {
00323         front->numVertices = in_c;
00324         back->numVertices = out_c;
00325 
00326         for (int loop = 0; loop < in_c; loop++)
00327         {
00328             front->Vertex[loop] = inpts[loop];
00329             front->Vertex[loop].polyNumber = PolygonNumber;
00330         }
00331         for (int loop = 0; loop < out_c; loop++)
00332         {
00333             back->Vertex[loop] = outpts[loop];
00334             back->Vertex[loop].polyNumber = PolygonNumber;
00335         }
00336         front->removable = Removable;
00337         front->Texture = Tex;
00338         front->SetNormal();
00339         back->removable = Removable;
00340         back->Texture = Tex;
00341         back->SetNormal();
00342         return PolygonWasSplit;
00343     }
00344 
00345     return 0;
00346 }

int SplitTriangle POLYGON    triangleToSplit,
POLYGON    planeTriangle,
POLYGON   triangles
 

Definition at line 363 of file polygon.cpp.

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

Referenced by BuildBSP(), and SelectPartitionfromList().

00364 {
00365     VECTOR planeNormal, polysNormal, pointOnPlane, edge1, edge2, temp;
00366     VERTEX ptA, ptB, outpts[4], inpts[4], intersection;
00367     int count = 0, out_c = 0, in_c = 0, sideA, sideB, outputFlag;
00368     VERTEX texvert1, texvert2; // texture calculation variables
00369     VECTOR t1, t2;
00370     float scale;
00371 
00372     // get a point on the plane
00373     pointOnPlane = planeTriangle.Vertex[0].coords;
00374 
00375     // get the splitting planes normal
00376     edge1 = planeTriangle.Vertex[1].coords - planeTriangle.Vertex[0].coords;
00377     edge2 = planeTriangle.Vertex[2].coords - planeTriangle.Vertex[0].coords;
00378     planeNormal = CrossVector(edge1, edge2);
00379 
00380     // get the normal of the triangle to split
00381     edge1 = triangleToSplit.Vertex[1].coords - triangleToSplit.Vertex[0].coords;
00382     edge2 = triangleToSplit.Vertex[2].coords - triangleToSplit.Vertex[0].coords;
00383     polysNormal = CrossVector(edge1, edge2);
00384 
00385     // check if the triangle lies on the plane
00386     for (int loop = 0; loop < 3; loop++)
00387     {
00388         temp = triangleToSplit.Vertex[loop].coords;
00389         if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00390             count++;
00391         else
00392             break;
00393     }
00394     if (count == 3)
00395     {
00396         if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == 1)
00397             return Front;
00398         if (ClassifyPoint(polysNormal, pointOnPlane, planeNormal) == -1)
00399             return Back;
00400     }
00401 
00402     // find if all of the points are infront of or behind the plane
00403     int frontcount = 0, backcount = 0;
00404     for (int loop = 0; loop < 3; loop++)
00405     {
00406         temp = triangleToSplit.Vertex[loop].coords;
00407         if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 0)
00408         {
00409             frontcount++;
00410             backcount++;
00411         }
00412         else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == 1)
00413             frontcount++;
00414         else if (ClassifyPoint(temp, pointOnPlane, planeNormal) == -1)
00415             backcount++;
00416     }
00417     if (frontcount == 3)
00418             return Front;
00419     if (backcount == 3)
00420             return Back;
00421 
00422     // try to split the triangle
00423     ptA = triangleToSplit.Vertex[2];
00424     temp = ptA.coords;
00425     sideA = ClassifyPoint(temp, pointOnPlane, planeNormal);
00426     for (int i = -1; ++i < 3;)
00427     {
00428         ptB = triangleToSplit.Vertex[i];
00429         temp = ptB.coords;
00430         sideB = ClassifyPoint(temp, pointOnPlane, planeNormal);
00431         if (sideB > 0)
00432         {
00433             if (sideA < 0)
00434             {
00435                 // find intersection
00436                 edge1 = ptA.coords;
00437                 edge2 = ptB.coords;
00438 
00439                 temp = GetEdgeIntersection(edge1, edge2, planeTriangle);
00440                 intersection.coords = temp;
00441 
00442                 // find the new texture coordinates
00443                 texvert1.coords = ptB.coords - ptA.coords;
00444                 texvert2.coords = intersection.coords - ptA.coords;
00445                 texvert1.u = ptA.u;
00446                 texvert2.u = ptB.u;
00447                 texvert1.v = ptA.v;
00448                 texvert2.v = ptB.v;
00449                 t1 = texvert1.coords;
00450                 t2 = texvert2.coords;
00451                 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);
00452                 intersection.u = texvert1.u + (texvert2.u - texvert1.u) * scale;
00453                 intersection.v = texvert1.v + (texvert2.v - texvert1.v) * scale;
00454 
00455                 outpts[out_c++] = inpts[in_c++] = intersection;
00456             }
00457             inpts[in_c++] = ptB;
00458         }
00459         else if (sideB < 0)
00460         {
00461             if (sideA > 0)
00462             {
00463                 // find intersection
00464                 edge1 = ptA.coords;
00465                 edge2 = ptB.coords;
00466 
00467                 temp = GetEdgeIntersection(edge1, edge2, planeTriangle);
00468                 intersection.coords = temp;
00469 
00470                 // find the new texture coordinates
00471                 texvert1.coords = ptB.coords - ptA.coords;
00472                 texvert2.coords = intersection.coords - ptA.coords;
00473                 texvert1.u = ptA.u;
00474                 texvert2.u = ptB.u;
00475                 texvert1.v = ptA.v;
00476                 texvert2.v = ptB.v;
00477                 t1 = texvert1.coords;
00478                 t2 = texvert2.coords;
00479                 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);
00480                 intersection.u = texvert1.u + (texvert2.u - texvert1.u) * scale;
00481                 intersection.v = texvert1.v + (texvert2.v - texvert1.v) * scale;
00482 
00483                 outpts[out_c++] = inpts[in_c++] = intersection;
00484             }
00485             outpts[out_c++] = ptB;
00486         }
00487         else
00488             outpts[out_c++] = inpts[in_c++] = ptB;
00489             ptA = ptB;
00490             sideA = sideB;
00491     }
00492 
00493     if (in_c == 4)          // two triangles are infront, one behind
00494     {
00495         outputFlag = TwoFrontOneBack;
00496         if (triangles)
00497         {
00498             triangles[0].Vertex[0] = inpts[0];
00499             triangles[0].Vertex[1] = inpts[1];
00500             triangles[0].Vertex[2] = inpts[2];
00501             triangles[0].numVertices = 3;
00502             triangles[0].SetNormal();
00503             triangles[1].Vertex[0] = inpts[0];
00504             triangles[1].Vertex[1] = inpts[2];
00505             triangles[1].Vertex[2] = inpts[3];
00506             triangles[1].numVertices = 3;
00507             triangles[1].SetNormal();
00508             triangles[2].Vertex[0] = outpts[0];
00509             triangles[2].Vertex[1] = outpts[1];
00510             triangles[2].Vertex[2] = outpts[2];
00511             triangles[2].numVertices = 3;
00512             triangles[2].SetNormal();
00513         }
00514     }
00515     else if (out_c == 4)    // one triangle is infront, two behind
00516     {
00517         outputFlag = OneFrontTwoBack;
00518         if (triangles)
00519         {
00520             triangles[0].Vertex[0] = inpts[0];
00521             triangles[0].Vertex[1] = inpts[1];
00522             triangles[0].Vertex[2] = inpts[2];
00523             triangles[0].numVertices = 3;
00524             triangles[0].SetNormal();
00525             triangles[1].Vertex[0] = outpts[0];
00526             triangles[1].Vertex[1] = outpts[1];
00527             triangles[1].Vertex[2] = outpts[2];
00528             triangles[1].numVertices = 3;
00529             triangles[1].SetNormal();
00530             triangles[2].Vertex[0] = outpts[0];
00531             triangles[2].Vertex[1] = outpts[2];
00532             triangles[2].Vertex[2] = outpts[3];
00533             triangles[2].numVertices = 3;
00534             triangles[2].SetNormal();
00535         }
00536     }
00537     else if (in_c == 3 && out_c == 3)  // plane bisects the triangle
00538     {
00539         outputFlag = OneFrontOneBack;
00540         if (triangles)
00541         {
00542             triangles[0].Vertex[0] = inpts[0];
00543             triangles[0].Vertex[1] = inpts[1];
00544             triangles[0].Vertex[2] = inpts[2];
00545             triangles[0].numVertices = 3;
00546             triangles[0].SetNormal();
00547             triangles[1].Vertex[0] = outpts[0];
00548             triangles[1].Vertex[1] = outpts[1];
00549             triangles[1].Vertex[2] = outpts[2];
00550             triangles[1].numVertices = 3;
00551             triangles[1].SetNormal();
00552         }
00553     }
00554     else // then triangle must be totally infront of or behind the plane
00555     {
00556         int side;
00557 
00558         for (int loop = 0; loop < 3; loop++)
00559         {
00560             temp = triangleToSplit.Vertex[loop].coords;
00561             side = ClassifyPoint(temp, pointOnPlane, planeNormal);
00562             if (side == 1)
00563             {
00564                 outputFlag = Front;
00565                 break;
00566             }
00567             else if (side == -1)
00568             {
00569                 outputFlag = Back;
00570                 break;
00571             }
00572         }
00573     }
00574     return outputFlag;
00575 }


Variable Documentation

const int maxPolygonVerts = 20
 

Definition at line 9 of file polygon.h.

Referenced by InvertBrushPolygons(), and POLYGON::SetNormal().


Generated on Fri Dec 23 05:15:50 2005 for Constructive Solid Geometry by doxygen1.2.15