earlyOutPolyList.cpp
Engine/source/collision/earlyOutPolyList.cpp
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 "math/mMath.h" 25#include "console/console.h" 26#include "collision/earlyOutPolyList.h" 27 28 29//---------------------------------------------------------------------------- 30 31EarlyOutPolyList::EarlyOutPolyList() 32{ 33 VECTOR_SET_ASSOCIATION(mPolyList); 34 VECTOR_SET_ASSOCIATION(mVertexList); 35 VECTOR_SET_ASSOCIATION(mIndexList); 36 VECTOR_SET_ASSOCIATION(mPolyPlaneList); 37 VECTOR_SET_ASSOCIATION(mPlaneList); 38 39 mNormal.set(0, 0, 0); 40 mIndexList.reserve(100); 41 42 mEarlyOut = false; 43} 44 45EarlyOutPolyList::~EarlyOutPolyList() 46{ 47 48} 49 50 51//---------------------------------------------------------------------------- 52void EarlyOutPolyList::clear() 53{ 54 // Only clears internal data 55 mPolyList.clear(); 56 mVertexList.clear(); 57 mIndexList.clear(); 58 mPolyPlaneList.clear(); 59 60 mEarlyOut = false; 61} 62 63bool EarlyOutPolyList::isEmpty() const 64{ 65 return mEarlyOut == false; 66} 67 68 69//---------------------------------------------------------------------------- 70 71U32 EarlyOutPolyList::addPoint(const Point3F& p) 72{ 73 if (mEarlyOut == true) 74 return 0; 75 76 mVertexList.increment(); 77 Vertex& v = mVertexList.last(); 78 v.point.x = p.x * mScale.x; 79 v.point.y = p.y * mScale.y; 80 v.point.z = p.z * mScale.z; 81 mMatrix.mulP(v.point); 82 83 // Build the plane mask 84 v.mask = 0; 85 for (U32 i = 0; i < mPlaneList.size(); i++) 86 if (mPlaneList[i].distToPlane(v.point) > 0) 87 v.mask |= 1 << i; 88 89 // If the point is inside all the planes, then we're done! 90 if (v.mask == 0) 91 mEarlyOut = true; 92 93 return mVertexList.size() - 1; 94} 95 96 97U32 EarlyOutPolyList::addPlane(const PlaneF& plane) 98{ 99 mPolyPlaneList.increment(); 100 mPlaneTransformer.transform(plane, mPolyPlaneList.last()); 101 102 return mPolyPlaneList.size() - 1; 103} 104 105 106//---------------------------------------------------------------------------- 107 108void EarlyOutPolyList::begin(BaseMatInstance* material,U32 surfaceKey) 109{ 110 if (mEarlyOut == true) 111 return; 112 113 mPolyList.increment(); 114 Poly& poly = mPolyList.last(); 115 poly.object = mCurrObject; 116 poly.material = material; 117 poly.vertexStart = mIndexList.size(); 118 poly.surfaceKey = surfaceKey; 119} 120 121 122//---------------------------------------------------------------------------- 123 124void EarlyOutPolyList::plane(U32 v1,U32 v2,U32 v3) 125{ 126 if (mEarlyOut == true) 127 return; 128 129 mPolyList.last().plane.set(mVertexList[v1].point, 130 mVertexList[v2].point,mVertexList[v3].point); 131} 132 133void EarlyOutPolyList::plane(const PlaneF& p) 134{ 135 if (mEarlyOut == true) 136 return; 137 138 mPlaneTransformer.transform(p, mPolyList.last().plane); 139} 140 141void EarlyOutPolyList::plane(const U32 index) 142{ 143 if (mEarlyOut == true) 144 return; 145 146 AssertFatal(index < mPolyPlaneList.size(), "Out of bounds index!"); 147 mPolyList.last().plane = mPolyPlaneList[index]; 148} 149 150const PlaneF& EarlyOutPolyList::getIndexedPlane(const U32 index) 151{ 152 AssertFatal(index < mPolyPlaneList.size(), "Out of bounds index!"); 153 return mPolyPlaneList[index]; 154} 155 156 157//---------------------------------------------------------------------------- 158 159void EarlyOutPolyList::vertex(U32 vi) 160{ 161 if (mEarlyOut == true) 162 return; 163 164 mIndexList.push_back(vi); 165} 166 167 168//---------------------------------------------------------------------------- 169 170void EarlyOutPolyList::end() 171{ 172 if (mEarlyOut == true) 173 return; 174 175 Poly& poly = mPolyList.last(); 176 177 // Anything facing away from the mNormal is rejected 178 if (mDot(poly.plane,mNormal) > 0) { 179 mIndexList.setSize(poly.vertexStart); 180 mPolyList.decrement(); 181 return; 182 } 183 184 // Build intial inside/outside plane masks 185 U32 indexStart = poly.vertexStart; 186 U32 vertexCount = mIndexList.size() - indexStart; 187 188 U32 frontMask = 0,backMask = 0; 189 U32 i; 190 for (i = indexStart; i < mIndexList.size(); i++) { 191 U32 mask = mVertexList[mIndexList[i]].mask; 192 frontMask |= mask; 193 backMask |= ~mask; 194 } 195 196 // Trivial accept if all the vertices are on the backsides of 197 // all the planes. 198 if (!frontMask) { 199 poly.vertexCount = vertexCount; 200 mEarlyOut = true; 201 return; 202 } 203 204 // Trivial reject if any plane not crossed has all it's points 205 // on the front. 206 U32 crossMask = frontMask & backMask; 207 if (~crossMask & frontMask) { 208 mIndexList.setSize(poly.vertexStart); 209 mPolyList.decrement(); 210 return; 211 } 212 213 // Need to do some clipping 214 for (U32 p = 0; p < mPlaneList.size(); p++) { 215 U32 pmask = 1 << p; 216 // Only test against this plane if we have something 217 // on both sides 218 if (crossMask & pmask) { 219 U32 indexEnd = mIndexList.size(); 220 U32 i1 = indexEnd - 1; 221 U32 mask1 = mVertexList[mIndexList[i1]].mask; 222 223 for (U32 i2 = indexStart; i2 < indexEnd; i2++) { 224 U32 mask2 = mVertexList[mIndexList[i2]].mask; 225 if ((mask1 ^ mask2) & pmask) { 226 // 227 mVertexList.increment(); 228 VectorF& v1 = mVertexList[mIndexList[i1]].point; 229 VectorF& v2 = mVertexList[mIndexList[i2]].point; 230 VectorF vv = v2 - v1; 231 F32 t = -mPlaneList[p].distToPlane(v1) / mDot(mPlaneList[p],vv); 232 233 mIndexList.push_back(mVertexList.size() - 1); 234 Vertex& iv = mVertexList.last(); 235 iv.point.x = v1.x + vv.x * t; 236 iv.point.y = v1.y + vv.y * t; 237 iv.point.z = v1.z + vv.z * t; 238 iv.mask = 0; 239 240 // Test against the remaining planes 241 for (i = p + 1; i < mPlaneList.size(); i++) 242 if (mPlaneList[i].distToPlane(iv.point) > 0) { 243 iv.mask = 1 << i; 244 break; 245 } 246 } 247 if (!(mask2 & pmask)) { 248 U32 index = mIndexList[i2]; 249 mIndexList.push_back(index); 250 } 251 mask1 = mask2; 252 i1 = i2; 253 } 254 255 // Check for degenerate 256 indexStart = indexEnd; 257 if (mIndexList.size() - indexStart < 3) { 258 mIndexList.setSize(poly.vertexStart); 259 mPolyList.decrement(); 260 return; 261 } 262 } 263 } 264 265 // If we reach here, then there's a poly! 266 mEarlyOut = true; 267 268 // Emit what's left and compress the index list. 269 poly.vertexCount = mIndexList.size() - indexStart; 270 memcpy(&mIndexList[poly.vertexStart], 271 &mIndexList[indexStart],poly.vertexCount); 272 mIndexList.setSize(poly.vertexStart + poly.vertexCount); 273} 274 275 276//---------------------------------------------------------------------------- 277 278void EarlyOutPolyList::memcpy(U32* dst, U32* src,U32 size) 279{ 280 U32* end = src + size; 281 while (src != end) 282 *dst++ = *src++; 283} 284 285