[an error occurred while processing this directive]
// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= // // // Project: Talina Gaming System (TgS) (∂) // File: TgS Collision - Triangle-Linear.cpp // Author: Andrew Aye (EMail: andrew.aye@gmail.com, Web: http://www.andrewaye.com) // Version: 3.11 // // ------------------------------------------------------------------------------------------------------------------------------ // // // Copyright: © 2002-2008, Andrew Aye. All Rights Reserved. // // This software is free for non-commercial use. Redistribution and use in source and binary forms, with or without modification, // are permitted provided that the following conditions are met: // Redistributions of source code must retain this copyright notice, this list of conditions and the following disclaimers. // Redistributions in binary form must reproduce this copyright notice, this list of conditions and the following // disclaimers in the documentation and other materials provided with the distribution. // // Neither the names of the copyright owner nor the names of its contributors may be used to endorse or promote products derived // from this software without specific prior written permission. // // The intellectual property rights of the algorithms used reside with Andrew Aye. You may not use this software, in whole or // in part, in support of any commercial product without the express written consent of the author. // // There is no warranty or other guarantee of fitness of this software for any purpose. It is provided solely "as is". // // =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= // // ============================================================================================================================== // // // Triangle Definition: T0(α,β) = P0 + α•E0 + β•E1 | α ε [ 0, 1], β ε [ 0, 1], (α + β) ε [0, 1] // Segment Definition: G1(γ) = P3 + γ•D1 | γ ε [ 0, 1] // // Derivation: // // // . . . . // . G . . G . NOTE: Keep in mind that in regions C, E and G, an obtuse angle can lead // . . . . to having significant projections along the other edge. // . . . . E0 // .. .. . // .2 . F . // |\ |\ . // | \ | \. // B | \ F B | /. E // | A \ |/ . // .....|____\..... E0 .O . // O. .1 .. . // . . . . D . // C . D . E . . // . . . C . // . . // E1 E1 // // // Let P0,P1,P2 be the three defining vertices of a triangle with E0 = P1 - P0 and E1 = P2 - P0. // Let P3, D1 by the origin and the vector of a line segment respectively. // // Let DS = P3 - P0 // // Let TG1, TE0, TE1 represent the co-ordinates in their respective reference frames of the extrapolated point // of contact between the line(segment) and the plane(triangle). // // [D1•D1 D1•E0 D1•E1] [TG1] [DS•D1] // [D1•E0 E0•E0 E0•E1] [TE0] = [DS•E0] // [D1•E1 E0•E1 E1•E1] [TE1] [DS•E1] // // Let C(ij) be the cofactor matrix of row i and column j We know that the determinant can be computed by // adding: det = (D1•E0)•C01 + (E0•E0)•C11 + (E0•E1)•C12 // // Let K = 1.0/det // // [TG1] [C00 C01 C02] [K_(DS•D1,DIM)] // [TE0] = [C01 C11 C12] [K_(DS•E0,DIM)] // [TE1] [C02 C12 C22] [K_(DS•E1,DIM)] // // However, it is known that TG1 ε [ 0, 1], TE0 ε [ 0, 1], TE1 ε [ 0, 1], and (TE0 + TE1) ε [ 0, 1] // These limitations present us with these possible cases. // // [1] TG1 ε (-∞, 0) // If the given condition is met, then the line segment is tested against the specified triangle edge. // Triangle Edge 2 • (TE0 + TE1) ε ( 1, ∞) // Triangle Edge 0 • TE0 ε (-∞, 0) // Triangle Edge 1 • TE1 ε (-∞, 0) // [2] TG1 ε [ 0, 1] // [A] (TE0 + TE1) ε (-∞, 1] // Triangle Edge 0 • TE0 ε (-∞, 0) // Triangle Edge 1 • TE1 ε (-∞, 0) // Intersection • TE0 ε [ 0, 1], TE1 ε [ 0, 1] // [B] (TE0 + TE1) ε ( 1, ∞) // Triangle Edge 2 // Triangle Edge 0 • TE0 ε (-∞, 0) // Triangle Edge 1 • TE1 ε (-∞, 0) // [3] TG1 ε ( 1, ∞) // If the given condition is met, then the line segment is tested against the specified triangle edge. // Triangle Edge 2 • (TE0 + TE1) ε ( 1, ∞) // Triangle Edge 0 • TE0 ε (-∞, 0) // Triangle Edge 1 • TE1 ε (-∞, 0) // // If the triangle and the segment happen to be parallel then, // The distance between the line segment and the triangle can be found by checking the distance of the segment // against the three triangle edges (line segments) and the triangle against the two end points of the line // segment. The resulting minimal value (with any corresponding extra information) will be the desired result. // // ============================================================================================================================== // namespace TGS { // START TGS /////////////////////////////////////////////////////////////////////////////////////////////////////// namespace COL { // START COL /////////////////////////////////////////////////////////////////////////////////////////////////////// // ============================================================================================================================== // // ---- F_ClosestSq ------------------------------------------------------------------------------------------------------------- // // -- Internal Function -- bC0, bC1 : Indicate the termination condition of the linear {bc0,bC1} // // Input: tgST0: Space triangle primitive // Input: tvS0,tvD0: Origin and Direction for the Linear // Output: _tyET0, _tyET1: Parametric parameters to generate point of minimal distance on the triangle // Output: _tyLN0: Parametric parameter to generate point of minimal distance on the linear // Return: Minimal distance between the two primitives or negative type max if they intersect or are invalid. // ------------------------------------------------------------------------------------------------------------------------------ // template <typename TYPE, int DIM, bool bC0, bool bC1> TYPE TTgCSQ_STLN<TYPE,DIM,bC0,bC1>::DO( TYPE *ptyET0, TYPE *ptyET1, TYPE *ptyLN0, CR_(STRI,DIM) tgST0, M_(VECTOR,DIM) tvS0, M_(VECTOR,DIM) tvD0 ) { TgASSERT(tgST0.Is_Valid() && MATH::F_Is_Point_Valid( tvS0 ) && MATH::F_Is_Vector_Valid( tvD0 )) // ==== Perform the requested primitive-primitive data function. ==== // If the linear is not parallel to the triangle, check to see if the two geometries intersect each other. if (!Near_Zero( MATH::F_DOT(tvD0,tgST0.Query_Normal()) )) { C_TgRESULT tgResult = TTgINT_ETLN<TYPE,DIM,bC0,bC1>::DO( ptyET0,ptyET1, ptyLN0, tgST0.Query_ET(), tvS0,tvD0 ); if (TgSUCCEEDED(tgResult) || (TgFAILED(tgResult) && TgE_NOINTERSECT != tgResult)) { // Some property of the triangle was illegal - return back an error state. // The linear may have intersected the triangle. return (-LIMITS<TYPE>::MAX); }; }; const TYPE tyNegE = -LIMITS<TYPE>::EPSILON; C_(VECTOR,DIM) tvS2 = MATH::F_ADD( tvS0, tvD0 ); TgINT iTest = 0; // Determine which feature tests need to be executed given the linear parameters. const TYPE ty00 = bC0 ? F_Dist( tgST0.Query_EdgePlane0(), tvS0 ) : -LIMITS<TYPE>::MAX; const TYPE ty01 = bC0 ? F_Dist( tgST0.Query_EdgePlane1(), tvS0 ) : -LIMITS<TYPE>::MAX; const TYPE ty02 = bC0 ? F_Dist( tgST0.Query_EdgePlane2(), tvS0 ) : -LIMITS<TYPE>::MAX; const TYPE tyK0 = MATH::F_DOT( tgST0.Query_EdgePlane0().Query_Normal(), tvD0 ); const TYPE tyK1 = MATH::F_DOT( tgST0.Query_EdgePlane1().Query_Normal(), tvD0 ); const TYPE tyK2 = MATH::F_DOT( tgST0.Query_EdgePlane2().Query_Normal(), tvD0 ); const TYPE ty10 = bC1 ? F_Dist( tgST0.Query_EdgePlane0(), tvS2 ) : tyK0; const TYPE ty11 = bC1 ? F_Dist( tgST0.Query_EdgePlane1(), tvS2 ) : tyK1; const TYPE ty12 = bC1 ? F_Dist( tgST0.Query_EdgePlane2(), tvS2 ) : tyK2; iTest |= (bC0 && ty00 > tyNegE && ty01 > tyNegE && ty02 > tyNegE) ? (1 << 3) : 0; iTest |= (bC1 && ty10 > tyNegE && ty11 > tyNegE && ty12 > tyNegE) ? (1 << 4) : 0; TYPE tyET0 = LIMITS<TYPE>::MAX, tyET1 = LIMITS<TYPE>::MAX, tyL1 = LIMITS<TYPE>::MAX; TYPE tyT0,tyT1,tyDistSq = LIMITS<TYPE>::MAX; // Test the first capped point if it is contained within the triangle space. if (0 != (iTest & (1 << 3))) { const TYPE tyTest = F_ClosestSq( &tyT0,&tyT1, tgST0.Query_ET(), tvS0 ); if (tyTest < tyDistSq) { tyDistSq = tyTest; tyL1 = TYPE(0.0); tyET0 = tyT0; tyET1 = tyT1; }; }; // Test the second capped point if it is contained within the triangle space. if (0 != (iTest & (1 << 4))) { const TYPE tyTest = F_ClosestSq( &tyT0,&tyT1, tgST0.Query_ET(), tvS2 ); if (tyTest < tyDistSq) { tyDistSq = tyTest; tyL1 = TYPE(1.0); tyET0 = tyT0; tyET1 = tyT1; }; }; if (0 != (iTest & (3 << 3))) { return (tyDistSq); }; iTest |= (bC0 ? (ty00 < LIMITS<TYPE>::EPSILON) : (ty10 > LIMITS<TYPE>::EPSILON)) ? (1 << 0) : 0; iTest |= (bC0 ? (ty01 < LIMITS<TYPE>::EPSILON) : (ty11 > LIMITS<TYPE>::EPSILON)) ? (1 << 1) : 0; iTest |= (bC0 ? (ty02 < LIMITS<TYPE>::EPSILON) : (ty12 > LIMITS<TYPE>::EPSILON)) ? (1 << 2) : 0; iTest |= (bC1 ? (ty10 < LIMITS<TYPE>::EPSILON) : (ty10 < tyNegE)) ? (1 << 0) : 0; iTest |= (bC1 ? (ty11 < LIMITS<TYPE>::EPSILON) : (ty11 < tyNegE)) ? (1 << 1) : 0; iTest |= (bC1 ? (ty12 < LIMITS<TYPE>::EPSILON) : (ty12 < tyNegE)) ? (1 << 2) : 0; TgASSERT(0 != iTest) // Check minimal distance between linear and edge 0, if any part of the line crosses into the negative space of the edge plane. if (0 != (iTest & (1 << 0))) { const TYPE tyTest = TTgCSQ_LNLN<TYPE,DIM,1,1,bC0,bC1>::DO( &tyT0,&tyT1, tgST0.Query_Point0(),tgST0.Query_Edge0(), tvS0,tvD0 ); if (tyTest < tyDistSq) { tyDistSq = tyTest; tyL1 = tyT1; tyET0 = tyT0; tyET1 = TYPE(0.0); }; }; // Check minimal distance between linear and edge 1, if any part of the line crosses into the negative space of the edge plane. if (0 != (iTest & (1 << 1))) { const TYPE tyTest = TTgCSQ_LNLN<TYPE,DIM,1,1,bC0,bC1>::DO( &tyT0,&tyT1, tgST0.Query_Point1(),tgST0.Query_Edge1(), tvS0,tvD0 ); if (tyTest < tyDistSq) { tyDistSq = tyTest; tyL1 = tyT1; tyET0 = TYPE(1.0) - tyT0; tyET1 = tyT0; }; }; // Check minimal distance between linear and edge 2, if any part of the line crosses into the negative space of the edge plane. if (0 != (iTest & (1 << 2))) { const TYPE tyTest = TTgCSQ_LNLN<TYPE,DIM,1,1,bC0,bC1>::DO( &tyT0,&tyT1, tgST0.Query_Point2(),tgST0.Query_Edge2(), tvS0,tvD0 ); if (tyTest < tyDistSq) { tyDistSq = tyTest; tyL1 = tyT1; tyET0 = TYPE(0.0); tyET1 = TYPE(1.0) - tyT0; }; }; *ptyET0 = tyET0; *ptyET1 = tyET1; *ptyLN0 = tyL1; return (tyDistSq); }; // ============================================================================================================================== // // ---- F_Contact_Intersect ----------------------------------------------------------------------------------------------------- // // -- Internal Function -- bC0, bC1 : Indicate the termination condition of the linear {bc0,bC1} // // Input: tgET0: Edge triangle primitive // Input: tvS0,tvD0: Origin and Direction for the Linear // Output: _tyET0, _tyET1: Parametric parameters to generate point of contact on the triangle // Output: _tyLN0: Parametric parameter to generate point of contact on the linear // Return: Result Code // ------------------------------------------------------------------------------------------------------------------------------ // template <typename TYPE, int DIM, bool bC0, bool bC1> TgRESULT TTgINT_ETLN<TYPE,DIM,bC0,bC1>::DO( TYPE *ptyET0, TYPE *ptyET1, TYPE *ptyLN0, CR_(ETRI,DIM) tgET0, M_(VECTOR,DIM) tvS0, M_(VECTOR,DIM) tvD0 ) { TgASSERT(tgET0.Is_Valid() && MATH::F_Is_Point_Valid( tvS0 ) && MATH::F_Is_Vector_Valid( tvD0 )); C_(VECTOR,DIM) tvDS = MATH::F_SUB( tvS0, tgET0.Query_Origin() ); const TYPE tyDS_DS = MATH::F_LSQ( tvDS ); if (tyDS_DS <= LIMITS<TYPE>::EPSILON) { // Quick Out - the segment origin is within tolerance of triangle origin. *ptyET0 = TYPE(0.0); *ptyET1 = TYPE(0.0); *ptyLN0 = TYPE(0.0); return (TgS_OK); }; const TYPE tyD1_N = MATH::F_DOT(tvD0,tgET0.Query_Normal()); if (P::ABS( tyD1_N ) <= LIMITS<TYPE>::EPSILON) { // Linear is parallel to the plane of the triangle. return (TgE_NOINTERSECT); }; const TYPE tyInvA = TYPE(1.0) / tyD1_N; const TYPE tyT0 = tyInvA*MATH::F_DOT(tvDS,tgET0.Query_Normal()); if ((bC0 && tyT0 < TYPE(0.0)) || (bC1 && tyT0 > TYPE(1.0))) { return (TgE_NOINTERSECT); }; *ptyLN0 = tyT0; const TYPE tyET0 = tyInvA*MATH::F_DOT( tvD0, MATH::F_CX( tgET0.Query_Edge1(), tvDS ) ); if (tyET0 < TYPE(0.0) || tyET0 > TYPE(1.0)) { return (TgE_NOINTERSECT); }; *ptyET0 = tyET0; const TYPE tyET1 = tyInvA*MATH::F_DOT( tvD0, MATH::F_CX( tgET0.Query_Edge0(), tvDS ) ); if (tyET1 < TYPE(0.0) || tyET0 + tyET1 > TYPE(1.0)) { return (TgE_NOINTERSECT); }; *ptyET1 = tyET1; return (TgS_OK); }; // ============================================================================================================================== // // ---- F_ClipF ----------------------------------------------------------------------------------------------------------------- // // -- Internal Function -- bC0, bC1 : Indicate the termination condition of the linear {bc0,bC1} // // Input: tgST0: Space triangle primitive - F_Clip-space is the region defined by the infinite extrusion along the normal. // Input: tvS0,tvD0: Origin and Direction for the Linear // Output: _tyLN0,_tyLN1: Parametric parameter to generate point of contact on the linear // Output: _iCode: PT0 Valid | PT1 Valid | PT0 Not Reduced | PT1 Not Reduced // Return: Result Code // ------------------------------------------------------------------------------------------------------------------------------ // template <typename TYPE, int DIM, bool bC0, bool bC1> TgRESULT TTgCLF_STLN<TYPE,DIM,bC0,bC1>::DO( TYPE *ptyLN0, TYPE *ptyLN1, PC_TgINT piCode, CR_(STRI,DIM) tgST0, M_(VECTOR,DIM) tvS0, M_(VECTOR,DIM) tvD0 ) { TYPE tyT0 = TYPE(0.0), tyT1 = TYPE(0.0); TgINT iCode = 0; for (TgINT iEdge = 0; iEdge < 3; ++iEdge) { const TYPE tyD1_N = MATH::F_DOT(tgST0.Query_EdgePlane( iEdge ).Query_Normal(),tvD0); const TYPE tyDist = F_Dist( tgST0.Query_EdgePlane( iEdge ), tvS0 ); if (tyDist < TYPE(0.0)) { // Check to see if its impossible for this linear to intersect the triangle space by seeing if it rests entirely in the // exterior half-space of the traingle-edge normal space. This can occur if the linear is near parallel to the resulting // partitioning plane, if the linear is start-capped and directed away from the plane and if its end-capped and the end // point is also behind the plane. if ((P::ABS( tyD1_N ) <= LIMITS<TYPE>::EPSILON) || (bC0 && tyD1_N < TYPE(0.0)) || (bC1 && (tyD1_N + tyDist < TYPE(0.0)))) { *piCode = 0; return (TgE_NOINTERSECT); }; }; if (tyD1_N > LIMITS<TYPE>::EPSILON) { const TYPE tyK0 = (bC1 && tyDist > tyD1_N) ? TYPE(1.0) : tyDist / tyD1_N; const TYPE tyTest = (bC0 && tyDist < TYPE(0.0)) ? TYPE(0.0) : tyK0; if (iCode & 1) { if (tyT0 < tyTest) { tyT0 = tyTest; iCode &= tgST0.Test_Edge( iEdge ) ? ~0 : ~4; }; } else { tyT0 = tyTest; iCode |= tgST0.Test_Edge( iEdge ) ? (1+4) : 1; }; } else if (tyD1_N < -LIMITS<TYPE>::EPSILON) { const TYPE tyK1 = (bC1 && tyDist < tyD1_N) ? TYPE(1.0) : tyDist / tyD1_N; const TYPE tyTest = (bC0 && tyDist > TYPE(0.0)) ? TYPE(0.0) : tyK1; if (iCode & 2) { if (tyT1 > tyTest) { tyT1 = tyTest; iCode &= tgST0.Test_Edge( iEdge ) ? ~0 : ~8; }; } else { tyT1 = tyTest; iCode |= tgST0.Test_Edge( iEdge ) ? (2+8) : 2; }; }; }; TgASSERT( iCode == 3 ); *ptyLN0 = tyT0; *ptyLN1 = tyT1; *piCode = iCode; return (TgS_OK); }; // ============================================================================================================================== // // ---- F_ClipF ----------------------------------------------------------------------------------------------------------------- // // -- Internal Function -- bC0, bC1 : Indicate the termination condition of the linear {bc0,bC1} // // Input: tgST0: Space triangle primitive - F_Clip-space is the region defined by the infinite extrusion along the normal. // Input: tvS0,tvD0: Origin and Direction for the Linear // Output: tgCL: The resulting point list - points created from clipping on a reduced edge are not added to the list. // Return: Result Code // ------------------------------------------------------------------------------------------------------------------------------ // template <typename TYPE, int DIM, bool bC0, bool bC1> TgRESULT TTgCLF_STLN<TYPE,DIM,bC0,bC1>::DO( PC_(CLIP_LIST,DIM) ptgCL, CR_(STRI,DIM) tgST1, M_(VECTOR,DIM) tvS0, M_(VECTOR,DIM) tvD0 ) { if (ptgCL->m_niMax < 2) { return (TgE_FAIL); }; TYPE tyT0, tyT1; TgINT iCode; C_TgRESULT tgResult = TTgCLF_STLN<TYPE,DIM,bC0,bC1>::DO( &tyT0,&tyT1, &iCode, tgST1, tvS0,tvD0 ); if (TgFAILED(tgResult) || 0 == (iCode & 12)) { ptgCL->m_niPoint = 0; return (tgResult); }; if (12 != (iCode & 12)) { if (P::ABS( tyT0 - tyT1 ) <= LIMITS<TYPE>::EPSILON) { ptgCL->m_ptvPoint[0] = MATH::F_ADD( tvS0, MATH::F_MUL( tyT0, tvD0 ) ); ptgCL->m_niPoint = 1; } else { ptgCL->m_ptvPoint[0] = MATH::F_ADD( tvS0, MATH::F_MUL( tyT0, tvD0 ) ); ptgCL->m_ptvPoint[1] = MATH::F_ADD( tvS0, MATH::F_MUL( tyT1, tvD0 ) ); ptgCL->m_niPoint = 2; }; } else if (4 != (iCode & 4)) { ptgCL->m_ptvPoint[0] = MATH::F_ADD( tvS0, MATH::F_MUL( tyT0, tvD0 ) ); ptgCL->m_niPoint = 1; } else if (8 != (iCode & 8)) { ptgCL->m_ptvPoint[0] = MATH::F_ADD( tvS0, MATH::F_MUL( tyT1, tvD0 ) ); ptgCL->m_niPoint = 1; }; return (TgS_OK); }; // ============================================================================================================================== // // ---- F_Clip ------------------------------------------------------------------------------------------------------------------ // // -- Internal Function -- bC0, bC1 : Indicate the termination condition of the linear {bc0,bC1} // // Input: tgST0: Space triangle primitive - F_Clip-space is the region defined by the infinite extrusion along the normal. // Input: tvS0,tvD0: Origin and Direction for the Linear // Output: tgCL: The resulting segment list. // Return: Result Code // ------------------------------------------------------------------------------------------------------------------------------ // template <typename TYPE, int DIM, bool bC0, bool bC1> TgRESULT TTgCLP_STLN<TYPE,DIM,bC0,bC1>::DO( PC_(CLIP_LIST,DIM) ptgCL, CR_(STRI,DIM) tgST1, M_(VECTOR,DIM) tvS0, M_(VECTOR,DIM) tvD0 ) { if (ptgCL->m_niMax < 2) { return (TgE_FAIL); }; TYPE tyT0, tyT1; TgINT iCode; C_TgRESULT tgResult = TTgCLF_STLN<TYPE,DIM,bC0,bC1>::DO( &tyT0,&tyT1, &iCode, tgST1, tvS0,tvD0 ); if (TgFAILED(tgResult)) { ptgCL->m_niPoint = 0; return (tgResult); }; if (P::ABS( tyT0 - tyT1 ) <= LIMITS<TYPE>::EPSILON) { ptgCL->m_ptvPoint[0] = MATH::F_ADD( tvS0, MATH::F_MUL( tyT0, tvD0 ) ); ptgCL->m_niPoint = 1; } else { ptgCL->m_ptvPoint[0] = MATH::F_ADD( tvS0, MATH::F_MUL( tyT0, tvD0 ) ); ptgCL->m_ptvPoint[1] = MATH::F_ADD( tvS0, MATH::F_MUL( tyT1, tvD0 ) ); ptgCL->m_niPoint = 2; }; return (TgS_OK); }; // ============================================================================================================================== // template struct TTgINT_ETLN<TgFLOAT32,4,0,0>; template struct TTgINT_ETLN<TgFLOAT32,4,1,0>; template struct TTgINT_ETLN<TgFLOAT32,4,1,1>; template struct TTgCSQ_STLN<TgFLOAT32,4,0,0>; template struct TTgCSQ_STLN<TgFLOAT32,4,1,0>; template struct TTgCSQ_STLN<TgFLOAT32,4,1,1>; template struct TTgCLP_STLN<TgFLOAT32,4,0,0>; template struct TTgCLP_STLN<TgFLOAT32,4,1,0>; template struct TTgCLP_STLN<TgFLOAT32,4,1,1>; template struct TTgCLF_STLN<TgFLOAT32,4,0,0>; template struct TTgCLF_STLN<TgFLOAT32,4,1,0>; template struct TTgCLF_STLN<TgFLOAT32,4,1,1>; // ============================================================================================================================== // }; // END COL ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// }; // END TGS //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////[an error occurred while processing this directive]