/* ** Command & Conquer Renegade(tm) ** Copyright 2025 Electronic Arts Inc. ** ** This program is free software: you can redistribute it and/or modify ** it under the terms of the GNU General Public License as published by ** the Free Software Foundation, either version 3 of the License, or ** (at your option) any later version. ** ** This program is distributed in the hope that it will be useful, ** but WITHOUT ANY WARRANTY; without even the implied warranty of ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ** GNU General Public License for more details. ** ** You should have received a copy of the GNU General Public License ** along with this program. If not, see . */ #if defined(_MSC_VER) #pragma once #endif #ifndef INTERSEC_INL #define INTERSEC_INL #include "camera.h" /// debug code that will be tossed #ifdef DEBUG_NORMALS #include "d:/g/app/main/debug_o.h" inline bool Verify_Normal(Vector3 &Normal, Vector3 &loc1, Vector3 &loc2, Vector3 &loc3) { double d1 = Vector3::Dot_Product(Normal, loc1); double d2 = Vector3::Dot_Product(Normal, loc2); double d3 = Vector3::Dot_Product(Normal, loc3); double e1 = d1 - d2; double e2 = d2 - d3; double e3 = d3 - d1; if((fabs(e1) > 0.001) || (fabs(e2) > 0.001) || (fabs(e3) > 0.001)) { Debug.Print("----------\n"); Debug.Print("dots", Vector3(d1,d2,d3)); Debug.Print("err", Vector3(e1,e2,e3)); return false; } return true; } inline void Verify_Normal2(Vector3 &Normal, Vector3 &loc1, Vector3 &loc2, Vector3 &loc3) { Vector3 v1 = loc2 - loc1; Vector3 v2 = loc3 - loc1; Vector3 normal = Vector3::Cross_Product(v1,v2); normal.Normalize(); if(!Verify_Normal(Normal, loc1,loc2,loc3)) { Vector3 diff = Normal - normal; if(Verify_Normal(normal, loc1,loc2,loc3)) { Debug.Print("calculated worked.\n"); } } // Normal = normal; } #endif //// end of debug code to toss /* ** Determine the ray that corresponds to the specified screen coordinates with respect ** to the camera location, direction and projection information. */ inline void IntersectionClass::Get_Screen_Ray(float screen_x, float screen_y, const LayerClass &Layer) { // copy screen coords to member data ScreenX = screen_x; ScreenY = screen_y; // extract needed pointers from the world CameraClass *camera = Layer.Camera; // determine the ray corresponding to the camera and distance to projection plane Matrix3D camera_matrix = camera->Get_Transform(); Vector3 camera_location = camera->Get_Position(); // the projected ray has the same origin as the camera *RayLocation = camera_location; // these 6 lines worked for SR 1.1 // build the projected screen vector // float x_offset = width / (float)Scene->width; // render width in pixels divided by display width in pixels = ratio of displayed area // float y_offset = height / (float)Scene->height; // float zmod = Scene->perspective; // float xmod = ((ScreenX / x_offset) * width - xmid - Scene->xstart) * zmod * 16384.0f/ (Scene->axratio * 128.0f); // float ymod = ((ScreenY / y_offset) * height - ymid - Scene->ystart) * zmod * 16384.0f/ (Scene->ayratio * 128.0f); // determine the location of the screen coordinate in camera-model space const ViewportClass &viewport = camera->Get_Viewport(); // float aspect = camera->Get_Aspect_Ratio(); Vector2 min,max; camera->Get_View_Plane(min,max); float xscale = (max.X - min.X); float yscale = (max.Y - min.Y); float zmod = -1.0; // Scene->vpd; // Note: view plane distance is now always 1.0 from the camera float xmod = (-ScreenX + 0.5 + viewport.Min.X) * zmod * xscale;// / aspect; float ymod = (ScreenY - 0.5 - viewport.Min.Y) * zmod * yscale;// * aspect; // float xmod = (ScreenX - 0.5 - viewport.Min.X) * zmod / Scene->axratio; // float ymod = (ScreenY - 0.5 - viewport.Min.Y) * zmod / Scene->ayratio; // sr1.2 // float xmod = (ScreenX - 0.5 - Scene->xstart) * zmod / Scene->axratio; // float ymod = (ScreenY - 0.5 - Scene->ystart) * zmod / Scene->ayratio; // sr1.1 // float xmod = x_offset * zmod; //projection_width; // float ymod = y_offset * zmod; //projection_height; // transform the screen coordinates by the camera's matrix into world coordinates. float x = zmod * camera_matrix[0][2] + xmod * camera_matrix[0][0] + ymod * camera_matrix[0][1]; float y = zmod * camera_matrix[1][2] + xmod * camera_matrix[1][0] + ymod * camera_matrix[1][1]; float z = zmod * camera_matrix[2][2] + xmod * camera_matrix[2][0] + ymod * camera_matrix[2][1]; RayDirection->Set(x,y,z); RayDirection->Normalize(); // set the maximum intersection distance to the back clipping plane MaxDistance = camera->Get_Depth(); //Max_Distance = Scene->zstop * Scene->depth; } /* ** This is the Point_In_Polygon_Z low level function, optimized for use by _Intersect_Triangles_Z. ** If it is inside, it will adjust the Z value of the point to be on the triangle plane. */ inline bool IntersectionClass::_Point_In_Polygon_Z( Vector3 &Point, Vector3 &Corner1, Vector3 &Corner2, Vector3 &Corner3 ) { // these defines could be variables if support for other axis were neccessary #define AXIS_1 0 #define AXIS_2 1 #define AXIS_3 2 double u0 = Point[AXIS_1] - Corner1[AXIS_1]; double v0 = Point[AXIS_2] - Corner1[AXIS_2]; // determine the 2d vectors on the dominant plane from the first vertex to the other two double u1 = Corner2[AXIS_1] - Corner1[AXIS_1]; double v1 = Corner2[AXIS_2] - Corner1[AXIS_2]; double u2 = Corner3[AXIS_1] - Corner1[AXIS_1]; double v2 = Corner3[AXIS_2] - Corner1[AXIS_2]; double alpha, beta; bool intersect = false; // calculate alpha and beta as normalized (0..1) percentages across the 2d projected triangle // and do bounds checking (sum <= 1) to determine whether or not the triangle intersection occurs. if (u1 == 0.0f) { beta = u0 / u2; // beta is the percentage down the edge Corner1->Corner3 if ((beta >= 0.0f) && (beta <= 1.0f)) { // make sure it's within the edge segment alpha = (v0 - beta * v2) / v1; // alpha is the percentage down the edge Corner1->Corner2 // if alpha is valid & the sum of alpha & beta is <= 1 then it's within the triangle // note: 0.00001 added after testing an intersection of a square in the middle indicated // an error of 0.0000001350, apparently due to roundoff. intersect = ((alpha >= 0.0) && ((alpha + beta) <= 1.0)); } } else { beta = (v0 * u1 - u0 * v1) / (v2 * u1 - u2 * v1); if ((beta >= 0.0) && (beta <= 1.0)) { alpha = (u0 - beta * u2) / u1; intersect = ((alpha >= 0.0) && ((alpha + beta) <= 1.0)); } } // if it is inside, adjust the Z value to sit upon the triangle plane. if(intersect) { float u3 = Corner2[AXIS_3] - Corner1[AXIS_3]; float v3 = Corner3[AXIS_3] - Corner1[AXIS_3]; Point[AXIS_3] = u3 * alpha + v3 * beta + Corner1[AXIS_3]; } return intersect; } /* ** Another way to access the Point_In_Polygon function ** */ inline bool IntersectionClass::_Point_In_Polygon_Z( Vector3 &Point, Vector3 Corners[3] ) { return _Point_In_Polygon_Z(Point, Corners[0], Corners[1], Corners[2]); } /* ** This is the general purpose Point_In_Polygon low level function. It can be called directly if you know ** the dominant projection axes, such as in the case of 2d intersecion with heightfields. */ inline bool IntersectionClass::_Point_In_Polygon( Vector3 &Point, Vector3 &loc1, Vector3 &loc2, Vector3 &loc3, int axis_1, int axis_2, float &Alpha, float &Beta) { double u0 = Point[axis_1] - loc1[axis_1]; double v0 = Point[axis_2] - loc1[axis_2]; // determine the 2d vectors on the dominant plane from the first vertex to the other two double u1 = loc2[axis_1] - loc1[axis_1]; double v1 = loc2[axis_2] - loc1[axis_2]; double u2 = loc3[axis_1] - loc1[axis_1]; double v2 = loc3[axis_2] - loc1[axis_2]; double alpha, beta; bool intersect = false; // calculate alpha and beta as normalized (0..1) percentages across the 2d projected triangle // and do bounds checking (sum <= 1) to determine whether or not the triangle intersection occurs. #ifdef DEBUG_NORMALS bool debugmode = false; if(FinalResult->Alpha == 777) { debugmode = true; } #endif if (u1 == 0.0f) { Beta = beta = u0 / u2; // beta is the percentage down the edge loc1->loc3 if ((beta >= 0.0f) && (beta <= 1.0f)) { // make sure it's within the edge segment Alpha = alpha = (v0 - beta * v2) / v1; // alpha is the percentage down the edge loc1->loc2 // if alpha is valid & the sum of alpha & beta is <= 1 then it's within the triangle // note: 0.00001 added after testing an intersection of a square in the middle indicated // an error of 0.0000001350, apparently due to roundoff. intersect = ((alpha >= 0.0) && ((alpha + beta) <= 1.0)); } } else { Beta = beta = (v0 * u1 - u0 * v1) / (v2 * u1 - u2 * v1); if ((beta >= 0.0) && (beta <= 1.0)) { Alpha = alpha = (u0 - beta * u2) / u1; intersect = ((alpha >= 0.0) && ((alpha + beta) <= 1.0)); } } #ifdef DEBUG_NORMALS if(debugmode) { Debug.Print("Intersect", intersect); Debug.Print("Normal ", Normal); Debug.Print("Point 1", loc1); Debug.Print("Point 2", loc2); Debug.Print("Point 3", loc3); Debug.Print("Inter ", FinalResult->Intersection); Debug.Print("a/b", (float) alpha, (float) beta); Debug.Print("sum", (float) alpha + (float) beta); Debug.Print("diff", (float) (alpha - beta)); float d1 = Vector3::Dot_Product(Normal, loc1); float d2 = Vector3::Dot_Product(Normal, loc2); float d3 = Vector3::Dot_Product(Normal, loc3); float e1 = d1 - d2; float e2 = d2 - d3; float e3 = d3 - d1; Debug.Print("dots", Vector3(d1,d2,d3)); Debug.Print("err", Vector3(e1,e2,e3)); } #endif return intersect; } /* ** This version calls the base form using member data from the FinalResult struct for ** some of it's arguments. */ inline bool IntersectionClass::_Point_In_Polygon( IntersectionResultClass *FinalResult, Vector3 &loc1, Vector3 &loc2, Vector3 &loc3, int axis_1, int axis_2) { return (FinalResult->Intersects = _Point_In_Polygon( FinalResult->Intersection, loc1, loc2, loc3, axis_1, axis_2, FinalResult->Alpha, FinalResult->Beta)); } /* ** This version determines the dominant plane of the 3d triangle to be point-in-poly tested ** and then calls the next form of _Point_In_Polygon */ inline bool IntersectionClass::_Point_In_Polygon(IntersectionResultClass *FinalResult, Vector3 &Normal, Vector3 &loc1, Vector3 &loc2, Vector3 &loc3) { // first, find the dominant axis and use the plane perpendicular to it as defined by axis_1, axis_2 int axis_1, axis_2; _Find_Polygon_Dominant_Plane(Normal, axis_1, axis_2); return _Point_In_Polygon(FinalResult, loc1, loc2, loc3, axis_1, axis_2); } /* ** Determine the Z distance to the specified polygon. */ inline float IntersectionClass::Plane_Z_Distance(Vector3 &PlaneNormal, Vector3 &PlanePoint) { // do a parallel check float divisor = (PlaneNormal[0] *(*RayDirection)[0] + PlaneNormal[1] *(*RayDirection)[1] + PlaneNormal[2] * (*RayDirection)[2]); if(divisor == 0) return false; // parallel // determine distance to plane double d = - (PlanePoint[0] * PlaneNormal[0] + PlanePoint[1] * PlaneNormal[1] + PlanePoint[2] * PlaneNormal[2]); float value = - (d + PlaneNormal[0] * (*RayLocation)[0] + PlaneNormal[1] * (*RayLocation)[1] + PlaneNormal[2] * (*RayLocation)[2]) / divisor; return value; } /* ** This function will find the z elevation for the passed Vector3 whose x/y components ** are defined, using the specified vertex & surface normal to determine the correct value */ inline float IntersectionClass::_Get_Z_Elevation( Vector3 &Point, Vector3 &PlanePoint, Vector3 &PlaneNormal) { // do a parallel check if(PlaneNormal[2] == 0) return false; // determine distance to plane double d = - (PlanePoint[0] * PlaneNormal[0] + PlanePoint[1] * PlaneNormal[1] + PlanePoint[2] * PlaneNormal[2]); float value = - (d + PlaneNormal[0] * Point[0] + PlaneNormal[1] * Point[1] ) / PlaneNormal[2]; return value; } /* ** Optimized intersection test that only considers the x/y component of the intersection object ** and will determine the intersection location down the Z axis. */ inline bool IntersectionClass::Intersect_Polygon_Z(IntersectionResultClass *Result, Vector3 &PolygonNormal, Vector3 &v1, Vector3 &v2, Vector3 &v3) { Result->Range = Plane_Z_Distance(PolygonNormal, v1); (Result->Intersection)[0] = (*RayLocation)[0]; (Result->Intersection)[1] = (*RayLocation)[1]; (Result->Intersection)[2] = (*RayLocation)[2] - Result->Range; return _Point_In_Polygon(Result, PolygonNormal, v1, v2, v3); } /* ** Scale the normalized direction ray to the distance of intersection */ void IntersectionClass::Calculate_Intersection(IntersectionResultClass *Result) { (Result->Intersection)[0] = (*RayLocation)[0] + (*RayDirection)[0] * Result->Range; (Result->Intersection)[1] = (*RayLocation)[1] + (*RayDirection)[1] * Result->Range; (Result->Intersection)[2] = (*RayLocation)[2] + (*RayDirection)[2] * Result->Range; } /* ** Plane intersection test that assumes a normalized RayDirection. Only determines if ** plane is parallel and if not, the range to it (which may be negative or beyond MaxRange). ** It doesn't determine point of intersection either. */ inline bool IntersectionClass::Intersect_Plane_Quick(IntersectionResultClass *Result, Vector3 &PlaneNormal, Vector3 &PlanePoint) { // do a parallel check float divisor = (PlaneNormal[0] *(*RayDirection)[0] + PlaneNormal[1] *(*RayDirection)[1] + PlaneNormal[2] * (*RayDirection)[2]); if(divisor == 0) return false; // parallel // determine distance to plane float d = - (PlanePoint[0] * PlaneNormal[0] + PlanePoint[1] * PlaneNormal[1] + PlanePoint[2] * PlaneNormal[2]); Result->Range = - (d + PlaneNormal[0] * (*RayLocation)[0] + PlaneNormal[1] * (*RayLocation)[1] + PlaneNormal[2] * (*RayLocation)[2]) / divisor; return true; } /* ** Determine if the specified ray will intersect the plane; returns false for planes ** parallel and behind ray origin. ** Sets Range to the distance from the ray location to the intersection. ** Note: Range is undefined if an intersection didn't occur. */ inline bool IntersectionClass::Intersect_Plane(IntersectionResultClass *Result, Vector3 &PlaneNormal, Vector3 &PlanePoint) { // normalize the ray direction RayDirection->Normalize(); // call the quick test routine if(!Intersect_Plane_Quick(Result, PlaneNormal, PlanePoint)) return false; // check to make sure it's not behind the ray's origin if(Result->Range <= 0) return false; // check to make sure it's not beyond max distance if(Result->Range > MaxDistance) return false; // determine point of intersection Calculate_Intersection(Result); return true; } /* ** Return the index of the largest normal component 0..2 ** used by Find_Triangle_Dominant_Plane() */ inline int IntersectionClass::_Largest_Normal_Index(Vector3 &v) { float x = fabsf(v[0]); float y = fabsf(v[1]); float z = fabsf(v[2]); if(x > y) { if(x > z) { return 0; // x > y && x > z --> x is the max } return 2; // x > y && !(x > z) --> z is the max } if(y > z) return 1; // x <= y && y > z --> y is the max return 2; // y > x && y > z --> z is the max } /* ** Use the Polygon's currently defined surface normal to determine it's dominant axis. ** Axis_1 and Axis_2 are set to the indices of the two axis that define the dominant plane. */ inline void IntersectionClass::_Find_Polygon_Dominant_Plane(Vector3 &Normal, int &Axis_1, int &Axis_2) { switch (_Largest_Normal_Index(Normal)) { case 0: // Dominant is the X axis Axis_1 = 2; Axis_2 = 1; break; case 1: // Dominant is the Y axis Axis_1 = 2; Axis_2 = 0; break; case 2: // Dominant is the Z axis Axis_1 = 0; Axis_2 = 1; break; } } /* ** Returns true if ray intersects polygon. ** Changes passed Intersection argument to location of intersection if it occurs, ** and sets Range to the distance from the ray location to the intersection. ** If Interpolated_Normal is specified it will interpolate the surface normal based ** on the vertex normals. */ inline bool IntersectionClass::Intersect_Polygon(IntersectionResultClass *Result, Vector3 &PolygonNormal, Vector3 &v1, Vector3 &v2, Vector3 &v3) { // first check to see if it hits the plane; determine plane normal and find point on plane (from a vertex) #ifdef DEBUG_NORMALS Verify_Normal2(PolygonNormal, v1,v2,v3); #endif if(Intersect_Plane(Result, PolygonNormal, v1)) { // then check to see if it it actually intersects the polygon. return _Point_In_Polygon(Result, PolygonNormal, v1, v2, v3); } // doesn't even hit the plane, return false. return false; } /* ** This version will calc the normal for the polygon before calling ** a lower form of Intersect_Polygon */ inline bool IntersectionClass::Intersect_Polygon(IntersectionResultClass *Result, Vector3 &v1, Vector3 &v2, Vector3 &v3) { Vector3 vec1 = v2 - v1; Vector3 vec2 = v3 - v1; Vector3 normal = Vector3::Cross_Product(vec1, vec2); return Intersect_Polygon(Result, normal, v1,v2,v3); } // called after Interpolate_Intersection_Normal. // transform the intersection and the normal from model coords into world coords inline void IntersectionClass::Transform_Model_To_World_Coords(IntersectionResultClass *FinalResult) { FinalResult->Intersection = FinalResult->ModelMatrix * FinalResult->Intersection + FinalResult->ModelLocation; if(IntersectionNormal != 0) { Vector3 normal(*IntersectionNormal); *IntersectionNormal = FinalResult->ModelMatrix * normal; } } bool IntersectionClass::Intersect_Screen_Object( IntersectionResultClass *Final_Result, Vector4 &Area, RenderObjClass *obj) { if(Final_Result->Intersects = ((ScreenX >= Area[0]) && (ScreenX <= Area[2]) && (ScreenY >= Area[1]) && (ScreenY <= Area[3]))) { Final_Result->IntersectionType = IntersectionResultClass::GENERIC; Final_Result->IntersectedRenderObject = obj; Final_Result->Range = 0; return true; } return false; } /* ** Determines the point of intersection, if any between the line segments AB and CD. ** If an intersection occurs, then the UV values are interpolated along AB. ** Disregards the Z value and considers only the X/Y data except for determining ** the Z value of the intersection. ** This function could be easily modified to support other axes. * / void IntersectionClass::_Intersect_Lines_Z( Vector3 &A, Vector3 &B, Vector2 &UVStart, Vector2 &UVEnd, Vector3 &C, Vector3 &D, Vector3 ClippedPoints[6], Vector2 ClippedUV[6], int &DestIndex) { /* Let A,B,C,D be 2-space position vectors. Then the directed line segments AB & CD are given by: AB=A+r(B-A), r in [0,1] CD=C+s(D-C), s in [0,1] If AB & CD intersect, then A+r(B-A)=C+s(D-C), or Ax+r(Bx-Ax)=Cx+s(Dx-Cx) Ay+r(By-Ay)=Cy+s(Dy-Cy) for some r,s in [0,1] Solving the above for r and s yields (Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy) r = ----------------------------- (eqn 1) (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx) (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay) s = ----------------------------- (eqn 2) (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx) Let P be the position vector of the intersection point, then P=A+r(B-A) or Px=Ax+r(Bx-Ax) Py=Ay+r(By-Ay) By examining the values of r & s, you can also determine some other limiting conditions: If 0<=r<=1 & 0<=s<=1, intersection exists r<0 or r>1 or s<0 or s>1 line segments do not intersect If the denominator in eqn 1 is zero, AB & CD are parallel If the numerator in eqn 1 is also zero, AB & CD are coincident If the intersection point of the 2 lines are needed (lines in this context mean infinite lines) regardless whether the two line segments intersect, then If r>1, P is located on extension of AB If r<0, P is located on extension of BA If s>1, P is located on extension of CD If s<0, P is located on extension of DC * / // the numerator is required for all execution routes float numerator = (A[AXIS_2] - C[AXIS_2]) * (D[AXIS_1] - C[AXIS_1]) - (A[AXIS_1] - C[AXIS_1]) * (D[AXIS_2] - C[AXIS_2]); // if the denominator is zero, then the segments are parallel. float denominator = (B[AXIS_1] - A[AXIS_1]) * (D[AXIS_2] - C[AXIS_2]) - (B[AXIS_2] - A[AXIS_2]) * (D[AXIS_1] - C[AXIS_1]); // r & s are percentages through the line segment. float r, s; // check to see if they are parallel if(denominator == 0) { // check to see if they are coincident // a numerator of zero with a denominator of zero indicates coincident lines. if (numerator != 0) { // parallel, not coincident lines (and segments) do not intersect. return; } // perform special case for parallel segments // determine relative position 0..1 of C and D on one of the 1d vectors of A-B float len = B[AXIS_1] - A[AXIS_1]; float cpos,dpos; // if the length of the edge on the first axis is zero, use the other axis instead. if(len) { len = 1.0 / len; cpos = (C[AXIS_1] - A[AXIS_1]) * len; dpos = (D[AXIS_1] - A[AXIS_1]) * len; } else { len = B[AXIS_2] - A[AXIS_2]; // degenerate triangle test if(len == 0) return; len = 1.0 / len; cpos = (C[AXIS_2] - A[AXIS_2]) * len; dpos = (D[AXIS_2] - A[AXIS_2]) * len; } // check to see if there's any overlap // one of the two pos values must be 0>pos>1 or there is no intersection. // this test will ensure that cpos & dpos will not both be outside the same end of the segment. if(((cpos < 0) && (dpos < 0)) || ((cpos > 1) && (dpos > 1))) return; if(cpos < 0) { // C is outside, therefore D is inside or on other side. // use the original vertex. ClippedPoints[DestIndex] = A; ClippedUV[DestIndex++] = UVStart; } else if (cpos > 1) { // C is outside far side, therefore D is inside or on other side. // use the far vertex. ClippedPoints[DestIndex] = B; ClippedUV[DestIndex++] = UVEnd; } else { // C is inside. // Use C as the vertex, and interpolate the UV coords. ClippedPoints[DestIndex] = C; ClippedUV[DestIndex++] = (UVEnd - UVStart) * cpos + UVStart; } if(dpos < 0) { // D is outside near vertex, therefore C is inside or outside far vertex // use near vertex ClippedPoints[DestIndex] = A; ClippedUV[DestIndex++] = UVStart; } else if (dpos > 1) { // D is outside far vertex, therefore C is inside or outside the near vertex. // use the far vertex. ClippedPoints[DestIndex] = B; ClippedUV[DestIndex++] = UVEnd; } else { // D is inside. // Use D as the vertex, and interpolate the UV coords. ClippedPoints[DestIndex] = D; ClippedUV[DestIndex++] = (UVEnd - UVStart) * dpos + UVStart; } return; } // determine the percentage into the line segments that the intersection occurs. // an intersection of segments will produce r & s values between 0 & 1. denominator = 1.0 / denominator; r = numerator * denominator; numerator = (A[AXIS_2] - C[AXIS_2]) * (B[AXIS_1] - A[AXIS_1]) - (A[AXIS_1] - C[AXIS_1]) * (B[AXIS_2] - A[AXIS_2]); s = numerator * denominator; // determine if the line intersect within the defined segments. if((0.0 <= r) && (r <= 1.0) && (0.0 <= s) && (s <= 1.0)) { // they intersect. // determine intersection point Vector3 v = D - C; // float len = v.Length(); ClippedPoints[DestIndex] = C + v * s; // interpolate UV values Vector2 uv = UVEnd - UVStart; // len = uv.Length(); ClippedUV[DestIndex++] = UVStart + uv * r; } } /* A failed attempt to use a graphics gem vol 2 example // Compute a1, b1, c1, where line joining points 1 and 2 // is "a1 x + b1 y + c1 = 0". float a1 = B[AXIS_2] - A[AXIS_2]; float b1 = B[AXIS_1] - A[AXIS_1]; float c1 = B[AXIS_2] * A[AXIS_1] - A[AXIS_1] * B[AXIS_2]; // Compute r3 & r4, the sign values float r3 = a1 * C[AXIS_1] + b1 * C[AXIS_2] + c1; float r4 = a1 * D[AXIS_1] + b1 * D[AXIS_2] + c1; // Check signs of r3 and r4. If both point 3 and point 4 lie on // same side of line 1, the line segments do not intersect. if ( r3 != 0 && r4 != 0 && (((r3 < 0) && (r4 < 0)) || ((r3 > 0) && (r4 > 0))) return; // ( DONT_INTERSECT ); // Compute a2, b2, c2 float a2 = D[AXIS_2] - C[AXIS_2]; float b2 = C[AXIS_1] - D[AXIS_1]; float c2 = D[AXIS_1] * C[AXIS_2] - C[AXIS_1] * D[AXIS_2]; // Compute r1 and r2 float r1 = a2 * A[AXIS_1] + b2 * A[AXIS_2] + c2; float r2 = a2 * B[AXIS_1] + b2 * B[AXIS_2] + c2; // Check signs of r1 and r2. If both point 1 and point 2 lie // on same side of second line segment, the line segments do // not intersect. if ( r1 != 0 && r2 != 0 && (((r1 < 0) && (r2 < 0)) || ((r1 > 0) && (r2 > 0)))) return; // ( DONT_INTERSECT ); // Line segments intersect: compute intersection point. float denom = a1 * b2 - a2 * b1; if ( denom == 0 ) return; // ( COLLINEAR ); float offset = denom < 0 ? - denom * 0.5f : denom * 0.5f; // The denom/2 is to get rounding instead of truncating. It // is added or subtracted to the numerator, depending upon the // sign of the numerator. float num = b1 * c2 - b2 * c1; float x = ( num < 0 ? num - offset : num + offset ) / denom; num = a2 * c1 - a1 * c2; float y = ( num < 0 ? num - offset : num + offset ) / denom; ClippedPoints[DestIndex] = Vector3(x,y,0); ClippedUV[DestIndex++] = Vector3 return; //( DO_INTERSECT ); // lines_intersect */ inline bool IntersectionClass::In_Front_Of_Line ( const Vector3 & p, // point to test const Vector3 & e0, // point on edge const Vector3 & de // direction of edge ) { Vector3 dp = p - e0; float val = de.X*dp.Y - de.Y*dp.X; if (val > 0.0f) { return true; } return false; } inline float IntersectionClass::Intersect_Lines ( const Vector3 & p0, // start of line segment const Vector3 & p1, // end of line segment const Vector3 & e0, // point on clipping edge const Vector3 & de // direction of clipping edge ) { float dpx = p1.X - p0.X; float dpy = p1.Y - p0.Y; float den = de.Y * dpx - de.X * dpy; if (fabs(den) > WWMATH_EPSILON) { float num = p0.Y*de.X - p0.X*de.Y + e0.X*de.Y - e0.Y*de.X; float t = num/den; if ((t >= 0.0f) && (t <= 1.0f)) { return t; } } return 0.0f; } #define EMIT(p,uv) OutPoints[outnum] = p; OutUVs[outnum] = uv; outnum++; inline int IntersectionClass::Clip_Triangle_To_LineXY( int incount, Vector3 * InPoints, Vector2 * InUVs, Vector3 * OutPoints, Vector2 * OutUVs, const Vector3 & edge_point0, const Vector3 & edge_point1 ) { Vector3 e0 = edge_point0; Vector3 de = edge_point1 - edge_point0; // number of verts output. int outnum = 0; // start and end verts of the current edge int p0,p1; p0 = incount-1; // intersection temporaries. float intersection; Vector3 intersection_point; Vector2 intersection_uv; // loop over each edge in the input polygon for (p1=0; p1in, emit intersection and endpoint intersection = Intersect_Lines(InPoints[p0], InPoints[p1], e0, de); intersection_point = (1.0f - intersection) * InPoints[p0] + intersection * InPoints[p1]; intersection_uv = (1.0f - intersection) * InUVs[p0] + intersection * InUVs[p1]; EMIT(intersection_point,intersection_uv); EMIT(InPoints[p1],InUVs[p1]); } } else { if (In_Front_Of_Line(InPoints[p0], e0, de)) { // edge going in->out, emit intersection intersection = Intersect_Lines(InPoints[p0],InPoints[p1], e0, de); intersection_point = (1.0f - intersection) * InPoints[p0] + intersection * InPoints[p1]; intersection_uv = (1.0f - intersection) * InUVs[p0] + intersection * InUVs[p1]; EMIT(intersection_point,intersection_uv); } } // move to next edge p0 = p1; } return outnum; } inline int IntersectionClass::_Intersect_Triangles_Z( Vector3 ClipPoints[3], Vector3 TrianglePoints[3], Vector2 UV[3], Vector3 ClippedPoints[6], Vector2 ClippedUV[6] ) { int count; Vector3 tmp_points[6]; Vector2 tmp_uv[6]; count = Clip_Triangle_To_LineXY(3,TrianglePoints,UV,ClippedPoints,ClippedUV,ClipPoints[0],ClipPoints[1]); count = Clip_Triangle_To_LineXY(count,ClippedPoints,ClippedUV,tmp_points,tmp_uv,ClipPoints[1],ClipPoints[2]); count = Clip_Triangle_To_LineXY(count,tmp_points,tmp_uv,ClippedPoints,ClippedUV,ClipPoints[2],ClipPoints[0]); return count; } /* ** This function will fill the passed array with the set of points & uv values that represent ** the boolean operation of the anding of the ClipPoints with the TrianglePoints. The UV values ** provided for the TrianglePoints triangle are used to generate accurate UV values for any ** new points created by this operation. ** This function returns the number of vertices it required to define the intersection. * / int IntersectionClass::_Intersect_Triangles_Z( Vector3 ClipPoints[3], Vector3 TrianglePoints[3], Vector2 UV[3], Vector3 ClippedPoints[6], Vector2 ClippedUV[6] ) { // first, check to see if all triangle points are inside clip area // the point in polygon will drop any inside points to the clip triangle plane. bool inside[3]; bool noclip; noclip = inside[0] = _Point_In_Polygon_Z(TrianglePoints[0], ClipPoints); noclip &= inside[1] = _Point_In_Polygon_Z(TrianglePoints[1], ClipPoints); noclip &= inside[2] = _Point_In_Polygon_Z(TrianglePoints[2], ClipPoints); // if all points are inside clip area, then copy the triangle points & // UV's to the destination & return 3 (the number of points in the clipped polygon). if(noclip) { ClippedPoints[0] = TrianglePoints[0]; ClippedPoints[1] = TrianglePoints[1]; ClippedPoints[2] = TrianglePoints[2]; ClippedUV[0] = UV[0]; ClippedUV[1] = UV[1]; ClippedUV[2] = UV[2]; return 3; } int points = 0; // number of output polygon points // not all uv triangle points are inside the clip triangle. // Test to see if any clip points are inside the uv triangle float alpha, beta; if(_Point_In_Polygon(ClipPoints[0], TrianglePoints[0], TrianglePoints[1], TrianglePoints[2], 0, 1, alpha, beta)) { ClippedPoints[points] = ClipPoints[0]; Vector2 uv1 = UV[1] - UV[0]; Vector2 uv2 = UV[2] - UV[0]; ClippedUV[points++] = UV[0] + alpha * uv1 + beta * uv2; } if(_Point_In_Polygon(ClipPoints[1], TrianglePoints[0], TrianglePoints[1], TrianglePoints[2], 0, 1, alpha, beta)) { ClippedPoints[points] = ClipPoints[1]; Vector2 uv1 = UV[1] - UV[0]; Vector2 uv2 = UV[2] - UV[0]; ClippedUV[points++] = UV[0] + alpha * uv1 + beta * uv2; } if(_Point_In_Polygon(ClipPoints[2], TrianglePoints[0], TrianglePoints[1], TrianglePoints[2], 0, 1, alpha, beta)) { ClippedPoints[points] = ClipPoints[2]; Vector2 uv1 = UV[1] - UV[0]; Vector2 uv2 = UV[2] - UV[0]; ClippedUV[points++] = UV[0] + alpha * uv1 + beta * uv2; } // if all 3 clip points are inside the decal triangle then return if(points == 3) return; // The clip triangle does not fully contain the uv triangle, and the uv triangle // does not fully contain the clip triangle. // Intersect any edge which has at least one outside point with all of the clip edges. // First, determine which edges to test. Those points that are already clipped (by being inside) // are immediately copied to the clipped point & uv arrays. // these bools indicate which edges of the triangle to be clipped are to be tested. bool test_01 = false; bool test_02 = false; bool test_12 = false; if( inside[0] ) { ClippedPoints[points] = TrianglePoints[0]; ClippedUV[points++] = UV[0]; } else { test_01 = test_02 = true; } if( inside[1] ) { ClippedPoints[points] = TrianglePoints[1]; ClippedUV[points++] = UV[1]; } else { test_01 = test_12 = true; } if( inside[2] ) { ClippedPoints[points] = TrianglePoints[2]; ClippedUV[points++] = UV[2];} else { test_02 = test_12 = true; } // Now test each indicated segment. // Intersect_2D_Lines will interpolate the clipped UV values if an intersection occurs, and it // will also increment the points variable (passed as a reference). // Any intersections are stored in the passed ClippedPoints array. if(test_01) { _Intersect_Lines_Z( TrianglePoints[0], TrianglePoints[1], UV[0], UV[1], ClipPoints[0], ClipPoints[1], ClippedPoints, ClippedUV, points); _Intersect_Lines_Z( TrianglePoints[0], TrianglePoints[1], UV[0], UV[1], ClipPoints[0], ClipPoints[2], ClippedPoints, ClippedUV, points); _Intersect_Lines_Z( TrianglePoints[0], TrianglePoints[1], UV[0], UV[1], ClipPoints[1], ClipPoints[2], ClippedPoints, ClippedUV, points); } if(test_02) { _Intersect_Lines_Z( TrianglePoints[0], TrianglePoints[2], UV[0], UV[2], ClipPoints[0], ClipPoints[1], ClippedPoints, ClippedUV, points); _Intersect_Lines_Z( TrianglePoints[0], TrianglePoints[2], UV[0], UV[2], ClipPoints[0], ClipPoints[2], ClippedPoints, ClippedUV, points); _Intersect_Lines_Z( TrianglePoints[0], TrianglePoints[2], UV[0], UV[2], ClipPoints[1], ClipPoints[2], ClippedPoints, ClippedUV, points); } if(test_12) { _Intersect_Lines_Z( TrianglePoints[1], TrianglePoints[2], UV[1], UV[2], ClipPoints[0], ClipPoints[1], ClippedPoints, ClippedUV, points); _Intersect_Lines_Z( TrianglePoints[1], TrianglePoints[2], UV[1], UV[2], ClipPoints[0], ClipPoints[2], ClippedPoints, ClippedUV, points); _Intersect_Lines_Z( TrianglePoints[1], TrianglePoints[2], UV[1], UV[2], ClipPoints[1], ClipPoints[2], ClippedPoints, ClippedUV, points); } // If no intersections have occurred, then the triangle must be completely outside // the clipping area. /* // if it is determined that no intersections have occurred, then copy the clip triangle points // into the destination array and determine the correct UV values for the subset of the // triangle that was clipped. if(points == 0) { ClippedPoints[0] = ClipPoints[0]; ClippedPoints[1] = ClipPoints[1]; ClippedPoints[2] = ClipPoints[2]; ClippedUV[0] = UV[0]; ClippedUV[1] = UV[1]; ClippedUV[2] = UV[2]; return 3; } * / // points will be 0, 3, 4, 5 or 6 if(!((points == 0) || (points == 3) || (points == 4) || (points == 5) || (points == 6))) { Debug.Print("points", points); return 0; //_Intersect_Triangles_Z( ClipPoints, TrianglePoints, UV, ClippedPoints, ClippedUV); } return points; } */ #endif