Torque3D Documentation / _generateds / extrudedPolyList.cpp

extrudedPolyList.cpp

Engine/source/collision/extrudedPolyList.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/mMath.h"
 26#include "console/console.h"
 27#include "collision/extrudedPolyList.h"
 28#include "math/mPolyhedron.h"
 29#include "collision/collision.h"
 30
 31// Minimum distance from a face
 32F32 ExtrudedPolyList::FaceEpsilon = 0.01f;
 33
 34// Value used to compare collision times
 35F32 ExtrudedPolyList::EqualEpsilon = 0.0001f;
 36
 37ExtrudedPolyList::ExtrudedPolyList()
 38{
 39   VECTOR_SET_ASSOCIATION(mVertexList);
 40   VECTOR_SET_ASSOCIATION(mIndexList);
 41   VECTOR_SET_ASSOCIATION(mExtrudedList);
 42   VECTOR_SET_ASSOCIATION(mPlaneList);
 43   VECTOR_SET_ASSOCIATION(mPolyPlaneList);
 44
 45   mVelocity.set(0.0f,0.0f,0.0f);
 46   mIndexList.reserve(128);
 47   mVertexList.reserve(64);
 48   mPolyPlaneList.reserve(64);
 49   mPlaneList.reserve(64);
 50   mCollisionList = 0;
 51   dMemset(&mPoly, 0, sizeof(mPoly));
 52}
 53
 54ExtrudedPolyList::~ExtrudedPolyList()
 55{
 56}
 57
 58//----------------------------------------------------------------------------
 59
 60bool ExtrudedPolyList::isEmpty() const
 61{
 62   return mCollisionList->getCount() == 0;
 63}
 64
 65
 66//----------------------------------------------------------------------------
 67
 68void ExtrudedPolyList::extrude(const Polyhedron& pt, const VectorF& vector)
 69{
 70   // Clear state
 71   mIndexList.clear();
 72   mVertexList.clear();
 73   mPlaneList.clear();
 74   mPolyPlaneList.clear();
 75
 76   // Determine which faces will be extruded.
 77   mExtrudedList.setSize(pt.mPlaneList.size());
 78
 79   for (U32 f = 0; f < pt.mPlaneList.size(); f++)
 80   {
 81      const PlaneF& face = pt.mPlaneList[f];
 82      ExtrudedFace& eface = mExtrudedList[f];
 83      F32 dot = mDot(face,vector);
 84      eface.active = dot > EqualEpsilon;
 85      
 86      if (eface.active) 
 87      {
 88         eface.maxDistance = dot;
 89         eface.plane = face;
 90         eface.planeMask = BIT(mPlaneList.size());
 91
 92         // Add the face as a plane to clip against.
 93         mPlaneList.increment(2);
 94         PlaneF* plane = mPlaneList.end() - 2;
 95         plane[0] = plane[1] = face;
 96         plane[0].invert();
 97      }
 98   }
 99
100   // Produce extruded planes for bounding and internal edges
101   for (U32 e = 0; e < pt.mEdgeList.size(); e++) 
102   {
103      Polyhedron::Edge const& edge = pt.mEdgeList[e];
104      ExtrudedFace& ef1 = mExtrudedList[edge.face[0]];
105      ExtrudedFace& ef2 = mExtrudedList[edge.face[1]];
106      if (ef1.active || ef2.active) 
107      {
108
109         // Assumes that the edge points are clockwise
110         // for face[0].
111         const Point3F& p1 = pt.mPointList[edge.vertex[1]];
112         const Point3F &p2 = pt.mPointList[edge.vertex[0]];
113         Point3F p3 = p2 + vector;
114
115         mPlaneList.increment(2);
116         PlaneF* plane = mPlaneList.end() - 2;
117         plane[0].set(p3,p2,p1);
118         plane[1] = plane[0];
119         plane[1].invert();
120
121         U32 pmask = BIT(mPlaneList.size()-2);
122         ef1.planeMask |= pmask;
123         ef2.planeMask |= pmask << 1;
124      }
125   }
126}
127
128
129//----------------------------------------------------------------------------
130
131void ExtrudedPolyList::setCollisionList(CollisionList* info)
132{
133   mCollisionList = info;
134   mCollisionList->clear();
135   mCollisionList->setTime( 2.0f );
136}
137
138//----------------------------------------------------------------------------
139
140void ExtrudedPolyList::adjustCollisionTime()
141{
142   if( !mCollisionList->getCount() )
143      return;
144
145   mCollisionList->setTime( mClampF( mCollisionList->getTime(), 0.f, 1.f ) );
146}
147
148
149//----------------------------------------------------------------------------
150
151U32 ExtrudedPolyList::addPoint(const Point3F& p)
152{
153   mVertexList.increment();
154   Vertex& v = mVertexList.last();
155
156   v.point.x = p.x * mScale.x;
157   v.point.y = p.y * mScale.y;
158   v.point.z = p.z * mScale.z;
159   mMatrix.mulP(v.point);
160
161   // Build the plane mask, planes come in pairs
162   v.mask = 0;
163   for (U32 i = 0; i < mPlaneList.size(); i ++)
164      if (mPlaneList[i].distToPlane(v.point) >= 0.f)
165         v.mask |= BIT(i);
166
167   return mVertexList.size() - 1;
168}
169
170
171U32 ExtrudedPolyList::addPlane(const PlaneF& plane)
172{
173   mPolyPlaneList.increment();
174   mPlaneTransformer.transform(plane, mPolyPlaneList.last());
175
176   return mPolyPlaneList.size() - 1;
177}
178
179
180//----------------------------------------------------------------------------
181
182void ExtrudedPolyList::begin(BaseMatInstance* material, U32 /*surfaceKey*/)
183{
184   mPoly.object = mCurrObject;
185   mPoly.material = material;
186   mIndexList.clear();
187}
188
189void ExtrudedPolyList::plane(U32 v1, U32 v2, U32 v3)
190{
191   mPoly.plane.set(mVertexList[v1].point,
192                   mVertexList[v2].point,
193                   mVertexList[v3].point);
194                   
195   // We hope this isn't needed but we're leaving it in anyway -- BJG/EGH
196   mPoly.plane.normalizeSafe();
197}
198
199void ExtrudedPolyList::plane(const PlaneF& p)
200{
201   mPlaneTransformer.transform(p, mPoly.plane);
202}
203
204void ExtrudedPolyList::plane(const U32 index)
205{
206   AssertFatal(index < mPolyPlaneList.size(), "Out of bounds index!");
207   mPoly.plane = mPolyPlaneList[index];
208}
209
210const PlaneF& ExtrudedPolyList::getIndexedPlane(const U32 index)
211{
212   AssertFatal(index < mPolyPlaneList.size(), "Out of bounds index!");
213   return mPolyPlaneList[index];
214}
215
216
217void ExtrudedPolyList::vertex(U32 vi)
218{
219   mIndexList.push_back(vi);
220}
221
222void ExtrudedPolyList::end()
223{
224   // Anything facing away from the mVelocity is rejected  (and also
225   // cap to max collisions)
226   if (mDot(mPoly.plane, mNormalVelocity) > 0.f ||
227      mCollisionList->getCount() >= CollisionList::MaxCollisions)
228      return;
229
230   // Test the built up poly (stored in mPoly) against all our extruded
231   // faces.
232   U32           cFaceCount = 0;
233   ExtrudedFace* cFace[30];
234   bool          cEdgeColl[30];
235   ExtrudedFace* face = mExtrudedList.begin();
236   ExtrudedFace* end = mExtrudedList.end();
237
238   for (; face != end; face++)
239   {
240      // Skip inactive..
241      if (!face->active)
242         continue;
243
244      // Update the dot product.
245      face->faceDot = -mDot(face->plane,mPoly.plane);
246      
247      // Skip it if we're facing towards...
248      if(face->faceDot <= 0.f)
249         continue;
250
251      // Test, and skip if colliding.
252      if (!testPoly(*face))
253         continue;
254 
255      // Note collision.
256      cFace[cFaceCount]       = face;
257      cEdgeColl[cFaceCount++] = false;
258   }
259
260   if (!cFaceCount)
261   {
262      face = mExtrudedList.begin();
263      end  = mExtrudedList.end();
264      for (; face != end; face++)
265      {
266         // Don't need to do dot product second time, so just check if it's
267         // active (we already did the dot product in the previous loop).
268         if (!face->active)
269            continue;
270
271         // Skip it if we're facing away...
272         if(face->faceDot > 0.f)
273            continue;
274
275         // Do collision as above.
276         if (!testPoly(*face))
277            continue;
278
279         // Note the collision.
280         cFace[cFaceCount]       = face;
281         cEdgeColl[cFaceCount++] = true;
282      }
283   }
284
285   // If we STILL don't have any collisions, just skip out.
286   if (!cFaceCount)
287      return;
288
289   // Pick the best collision face based on best alignment with respective
290   // face.
291   face = cFace[0];
292   bool edge = cEdgeColl[0];
293   for (U32 f = 1; f < cFaceCount; f++)
294   {
295      if (cFace[f]->faceDot <= face->faceDot)
296         continue;
297
298      face = cFace[f];
299      edge = cEdgeColl[f];
300   }
301
302   // Add it to the collision list if it's better and/or equal
303   // to our current best.
304
305   // Don't add it to the collision list if it's too far away.
306   if (face->time > mCollisionList->getTime() + EqualEpsilon || face->time >= 1.0)
307      return;
308
309   if (face->time < mCollisionList->getTime() - EqualEpsilon) 
310   {
311      // If this is significantly closer than before, then clear out the
312      // list, as it's a better match than the old stuff.
313      mCollisionList->clear();
314      mCollisionList->setTime( face->time );
315      mCollisionList->setMaxHeight( face->height );
316   }
317   else 
318   {
319      // Otherwise, just update some book-keeping stuff.
320      if ( face->height > mCollisionList->getMaxHeight() )
321         mCollisionList->setMaxHeight( face->height );
322   }
323
324   // Note the collision in our collision list.
325   Collision& collision = mCollisionList->increment();
326   collision.point    = face->point;
327   collision.faceDot  = face->faceDot;
328   collision.face     = face - mExtrudedList.begin();
329   collision.object   = mPoly.object;
330   collision.normal   = mPoly.plane;
331   collision.material = mPoly.material;
332}
333
334
335//----------------------------------------------------------------------------
336
337bool ExtrudedPolyList::testPoly(ExtrudedFace& face)
338{
339   // Build intial inside/outside plane masks
340   U32 indexStart = 0;
341   U32 indexEnd = mIndexList.size();
342   U32 oVertexSize = mVertexList.size();
343   U32 oIndexSize = mIndexList.size();
344
345   U32 frontMask = 0,backMask = 0;
346   for (U32 i = indexStart; i < indexEnd; i++) 
347   {
348      U32 mask = mVertexList[mIndexList[i]].mask & face.planeMask;
349      frontMask |= mask;
350      backMask |= ~mask;
351   }
352
353   // Clip the mPoly against the planes that bound the face...
354   // Trivial accept if all the vertices are on the backsides of
355   // all the planes.
356   if (frontMask) 
357   {
358      // Trivial reject if any plane not crossed has all it's points
359      // on the front.
360      U32 crossMask = frontMask & backMask;
361      if (~crossMask & frontMask)
362         return false;
363
364      // Need to do some clipping
365      for (U32 p=0; p < mPlaneList.size(); p++) 
366      {
367         U32 pmask    = BIT(p);
368         U32 newStart = mIndexList.size();
369
370         // Only test against this plane if we have something
371         // on both sides - otherwise skip.
372         if (!(face.planeMask & crossMask & pmask))
373            continue;
374
375         U32 i1 = indexEnd - 1;
376         U32 mask1 = mVertexList[mIndexList[i1]].mask;
377
378         for (U32 i2 = indexStart; i2 < indexEnd; i2++) 
379         {
380            const U32 mask2 = mVertexList[mIndexList[i2]].mask;
381            if ((mask1 ^ mask2) & pmask)
382            {
383               // Clip the edge against the plane.
384               mVertexList.increment();
385               VectorF& v1 = mVertexList[mIndexList[i1]].point;
386               VectorF& v2 = mVertexList[mIndexList[i2]].point;
387               VectorF vv = v2 - v1;
388               F32 t = -mPlaneList[p].distToPlane(v1) / mDot(mPlaneList[p],vv);
389
390               mIndexList.push_back(mVertexList.size() - 1);
391               Vertex& iv = mVertexList.last();
392               iv.point.x = v1.x + vv.x * t;
393               iv.point.y = v1.y + vv.y * t;
394               iv.point.z = v1.z + vv.z * t;
395               iv.mask = 0;
396
397               // Test against the remaining planes
398               for (U32 i = p+1; i < mPlaneList.size(); i ++)
399               {
400                  if (mPlaneList[i].distToPlane(iv.point) > 0.f)
401                     iv.mask |= BIT(i);
402               }
403            }
404
405            if (!(mask2 & pmask)) 
406            {
407               U32 index = mIndexList[i2];
408               mIndexList.push_back(index);
409            }
410
411            mask1 = mask2;
412            i1 = i2;
413         }
414
415         // Check for degenerate
416         indexStart = newStart;
417         indexEnd = mIndexList.size();
418         if (mIndexList.size() - indexStart < 3) 
419         {
420            mVertexList.setSize(oVertexSize);
421            mIndexList.setSize(oIndexSize);
422            return false;
423         }
424      }
425   }
426
427   // Find closest point on the mPoly
428   Point3F bp(0.0f, 0.0f, 0.0f);
429   F32 bd = 1E30f;
430   F32 height = -1E30f;
431   for (U32 b = indexStart; b < indexEnd; b++) 
432   {
433      Vertex& vertex = mVertexList[mIndexList[b]];
434      F32 dist = face.plane.distToPlane(vertex.point);
435      if (dist <= bd) 
436      {
437         bd = (dist < 0)? 0: dist;
438         bp = vertex.point;
439      }
440      
441      // Since we don't clip against the back plane, we'll
442      // only include vertex heights that are within range.
443      if (vertex.point.z > height && dist < face.maxDistance)
444         height = vertex.point.z;
445   }
446   
447   // hack for not jetting up through the cieling
448   F32 fudge = 0.01f;
449   F32 fudgeB = 0.2f;
450   if(mNormalVelocity.z > 0.0)
451   {
452      fudge = 0.01f; //0.015;
453      fudgeB = 0.2f;
454   }
455   
456   // Do extruded points for back-off.
457   F32 oldBd=bd;
458   for (U32 b = indexStart; b < indexEnd; b++) 
459   {
460      Vertex& vertex = mVertexList[mIndexList[b]];
461      
462      // Extrude out just a tad to make sure we don't end up getting too close to the
463      // geometry and getting stuck - but cap it so we don't introduce error into long
464      // sweeps.
465      F32 dist = face.plane.distToPlane( vertex.point 
466                          + Point3F(mPoly.plane) * getMin(face.maxDistance * fudgeB, fudge));
467
468      if (dist <= bd)
469      {
470         bd = (dist < 0)? 0: dist;
471         bp = vertex.point;
472      }
473   }
474
475   // Remove temporary data
476   mVertexList.setSize(oVertexSize);
477   mIndexList.setSize(oIndexSize);
478
479   // Don't add it to the collision list if it's worse then our current best.
480   if (oldBd >= face.maxDistance)
481      return false;
482
483   // Update our info and indicate we should add to the model.
484   F32 oldT = oldBd / face.maxDistance;
485   F32 pushBackT = bd / face.maxDistance;
486   
487   if(oldT - pushBackT > 0.1)
488      face.time = oldT - fudge;
489   else
490      face.time = pushBackT;
491      
492   face.height = height;
493   face.point  = bp;
494   return true;
495}
496
497//--------------------------------------------------------------------------
498void ExtrudedPolyList::setVelocity(const VectorF& velocity)
499{
500   mVelocity = velocity;
501   if (velocity.isZero() == false)
502   {
503      mNormalVelocity = velocity;
504      mNormalVelocity.normalize();
505      setInterestNormal(mNormalVelocity);
506   }
507   else
508   {
509      mNormalVelocity.set(0.0f, 0.0f, 0.0f);
510      clearInterestNormal();
511   }
512}
513