mPlane.cpp
Engine/source/math/mPlane.cpp
More...
Detailed Description
1
2//-----------------------------------------------------------------------------
3// Copyright (c) 2012 GarageGames, LLC
4//
5// Permission is hereby granted, free of charge, to any person obtaining a copy
6// of this software and associated documentation files (the "Software"), to
7// deal in the Software without restriction, including without limitation the
8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
9// sell copies of the Software, and to permit persons to whom the Software is
10// furnished to do so, subject to the following conditions:
11//
12// The above copyright notice and this permission notice shall be included in
13// all copies or substantial portions of the Software.
14//
15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
21// IN THE SOFTWARE.
22//-----------------------------------------------------------------------------
23
24#include "platform/platform.h"
25#include "math/mPlane.h"
26
27#include "math/mathUtils.h"
28#include "math/mBox.h"
29#include "math/mOrientedBox.h"
30#include "math/mSphere.h"
31
32
33//-----------------------------------------------------------------------------
34
35bool PlaneF::intersect( const PlaneF& plane, Point3F& outLinePt, VectorF& outLineDir ) const
36{
37 // Compute direction of intersection line.
38 outLineDir = mCross( *this, plane );
39
40 // If d is zero, the planes are parallel (and separated)
41 // or coincident, so they're not considered intersecting
42 F32 denom = mDot( outLineDir, outLineDir );
43 if ( denom < 0.00001f )
44 return false;
45
46 // Compute point on intersection line
47 outLinePt = - mCross( d * plane - plane.d * *this,
48 outLineDir ) / denom;
49
50 return true;
51}
52
53//-----------------------------------------------------------------------------
54
55bool PlaneF::isParallelTo( const PlaneF& plane, F32 epsilon ) const
56{
57 F32 val = 1.0f - mFabs( mDot( *this, plane ) );
58 return ( val > - epsilon ) && ( val < epsilon );
59}
60
61//-----------------------------------------------------------------------------
62
63bool PlaneF::isPerpendicularTo( const PlaneF& plane, F32 epsilon ) const
64{
65 F32 val = mDot( *this, plane );
66 return ( val > - epsilon) && ( val < epsilon );
67}
68
69//-----------------------------------------------------------------------------
70
71bool PlaneF::clipSegment( const Point3F& start, const Point3F& end, Point3F& outNewEnd ) const
72{
73 // Intersect ray with plane.
74
75 F32 dist = intersect( start, end );
76 if( dist == PARALLEL_PLANE || dist < 0.f || dist > 1.f )
77 return false;
78
79 // Compute distance to point on segment.
80
81 Point3F dir = end - start;
82 dir *= dist;
83
84 // Compute new end point.
85
86 outNewEnd = start + dir;
87
88 return true;
89}
90
91//-----------------------------------------------------------------------------
92
93U32 PlaneF::clipPolygon( const Point3F* inVertices, U32 inNumVertices, Point3F* outVertices ) const
94{
95 // Find the first vertex that lies on the front of the plane.
96
97 S32 start = -1;
98 for( U32 i = 0; i < inNumVertices; i ++ )
99 {
100 Side side = whichSide( inVertices[ i ] );
101 if( side == PlaneF::Front )
102 {
103 start = i;
104 break;
105 }
106 }
107
108 // If nothing was in front of the plane, we're done.
109
110 if( start == -1 )
111 return 0;
112
113 Point3F finalPoints[ 128 ];
114 U32 numFinalPoints = 0;
115
116 U32 baseStart = start;
117 U32 end = ( start + 1 ) % inNumVertices;
118
119 dMemcpy( outVertices, inVertices, inNumVertices * sizeof( Point3F ) );
120
121 while( end != baseStart )
122 {
123 const Point3F& rStartPoint = outVertices[ start ];
124 const Point3F& rEndPoint = outVertices[ end ];
125
126 PlaneF::Side fSide = whichSide( rStartPoint );
127 PlaneF::Side eSide = whichSide( rEndPoint );
128
129 S32 code = fSide * 3 + eSide;
130 switch( code )
131 {
132 case 4: // f f
133 case 3: // f o
134 case 1: // o f
135 case 0: // o o
136 // No Clipping required
137 finalPoints[ numFinalPoints ++ ] = outVertices[ start ];
138 start = end;
139 end = ( end + 1 ) % inNumVertices;
140 break;
141
142
143 case 2: // f b
144 {
145 // In this case, we emit the front point, Insert the intersection,
146 // and advancing to point to first point that is in front or on...
147 //
148 finalPoints[ numFinalPoints ++ ] = outVertices[ start ];
149
150 Point3F vector = rEndPoint - rStartPoint;
151 F32 t = - ( distToPlane( rStartPoint ) / mDot( *this, vector ) );
152
153 Point3F intersection = rStartPoint + ( vector * t );
154 finalPoints[ numFinalPoints ++ ] = intersection;
155
156 U32 endSeek = ( end + 1 ) % inNumVertices;
157 while( whichSide( outVertices[ endSeek ] ) == PlaneF::Back )
158 endSeek = ( endSeek + 1 ) % inNumVertices;
159
160 end = endSeek;
161 start = ( end + ( inNumVertices - 1 ) ) % inNumVertices;
162
163 const Point3F& rNewStartPoint = outVertices[ start ];
164 const Point3F& rNewEndPoint = outVertices[ end ];
165
166 vector = rNewEndPoint - rNewStartPoint;
167 t = - ( distToPlane( rNewStartPoint ) / mDot( *this, vector ) );
168
169 intersection = rNewStartPoint + ( vector * t );
170 outVertices[ start ] = intersection;
171 }
172 break;
173
174 case -1: // o b
175 {
176 // In this case, we emit the front point, and advance to point to first
177 // point that is in front or on...
178 //
179 finalPoints[ numFinalPoints ++ ] = outVertices[ start ];
180
181 U32 endSeek = ( end + 1 ) % inNumVertices;
182 while( whichSide( outVertices[ endSeek ] ) == PlaneF::Back)
183 endSeek = ( endSeek + 1 ) % inNumVertices;
184
185 end = endSeek;
186 start = (end + ( inNumVertices - 1 ) ) % inNumVertices;
187
188 const Point3F& rNewStartPoint = outVertices[ start ];
189 const Point3F& rNewEndPoint = outVertices[ end ];
190
191 Point3F vector = rNewEndPoint - rNewStartPoint;
192 F32 t = - ( distToPlane( rNewStartPoint ) / mDot( *this, vector ) );
193
194 Point3F intersection = rNewStartPoint + ( vector * t );
195 outVertices[ start ] = intersection;
196 }
197 break;
198
199 case -2: // b f
200 case -3: // b o
201 case -4: // b b
202 // In the algorithm used here, this should never happen...
203 AssertISV(false, "SGUtil::clipToPlane: error in polygon clipper");
204 break;
205
206 default:
207 AssertFatal(false, "SGUtil::clipToPlane: bad outcode");
208 break;
209 }
210
211 }
212
213 // Emit the last point.
214 finalPoints[ numFinalPoints ++ ] = outVertices[ start ];
215 AssertFatal( numFinalPoints >= 3, avar("Error, this shouldn't happen! Invalid winding in clipToPlane: %d", numFinalPoints ) );
216
217 // Copy the new rWinding, and we're set!
218 //
219 dMemcpy( outVertices, finalPoints, numFinalPoints * sizeof( Point3F ) );
220 AssertISV( numFinalPoints <= 128, "MaxWindingPoints exceeded in scenegraph. Fatal error.");
221
222 return numFinalPoints;
223}
224
