BVB Source Codes

CRYENGINE Show AICollision.cpp Source code

Return Download CRYENGINE: download AICollision.cpp Source code - Download CRYENGINE Source code - Type:.cpp
  1. // Copyright 2001-2016 Crytek GmbH / Crytek Group. All rights reserved.
  2.  
  3. #include "StdAfx.h"
  4. #include "AICollision.h"
  5. #include "CAISystem.h"
  6. #include "Walkability/WalkabilityCacheManager.h"
  7. #include "DebugDrawContext.h"
  8.  
  9. static EAICollisionEntities aiCollisionEntitiesTable[] =
  10. {
  11.         AICE_STATIC,
  12.         AICE_ALL,
  13.         AICE_ALL_SOFT,
  14.         AICE_DYNAMIC,
  15.         AICE_STATIC_EXCEPT_TERRAIN,
  16.         AICE_ALL_EXCEPT_TERRAIN,
  17.         AICE_ALL_INLUDING_LIVING
  18. };
  19.  
  20. #ifdef CRYAISYSTEM_DEBUG
  21. unsigned g_CheckWalkabilityCalls;
  22. #endif //CRYAISYSTEM_DEBUG
  23.  
  24. IPhysicalEntity* g_AIEntitiesInBoxPreAlloc[GetPhysicalEntitiesInBoxMaxResultCount];
  25.  
  26. // For automatic cleanup of memory allocated by physics
  27. // We could have a static buffer also, at the cost of a little complication - physics memory is still needed if static buffer too small
  28. void PhysicalEntityListAutoPtr::operator=(IPhysicalEntity** pList)
  29. {
  30.         if (m_pList)
  31.                 gEnv->pPhysicalWorld->GetPhysUtils()->DeletePointer(m_pList);
  32.         m_pList = pList;
  33. }
  34.  
  35. //====================================================================
  36. // IntersectSweptSphere
  37. // hitPos is optional - may be faster if 0
  38. //====================================================================
  39. bool IntersectSweptSphere(Vec3* hitPos, float& hitDist, const Lineseg& lineseg, float radius, EAICollisionEntities aiCollisionEntities, IPhysicalEntity** pSkipEnts, int nSkipEnts, int geomFlagsAny)
  40. {
  41.         primitives::sphere spherePrim;
  42.         spherePrim.center = lineseg.start;
  43.         spherePrim.r = radius;
  44.  
  45.         Vec3 dir = lineseg.end - lineseg.start;
  46.  
  47.         geom_contact* pContact = 0;
  48.         geom_contact** ppContact = hitPos ? &pContact : 0;
  49.         int geomFlagsAll = 0;
  50.  
  51.         float d = gEnv->pPhysicalWorld->PrimitiveWorldIntersection(spherePrim.type, &spherePrim, dir,
  52.                                                                    aiCollisionEntities, ppContact,
  53.                                                                    geomFlagsAll, geomFlagsAny, 0, 0, 0, pSkipEnts, nSkipEnts);
  54.  
  55.         if (d > 0.0f)
  56.         {
  57.                 hitDist = d;
  58.                 if (pContact && hitPos)
  59.                         *hitPos = pContact->pt;
  60.                 return true;
  61.         }
  62.         else
  63.         {
  64.                 return false;
  65.         }
  66. }
  67.  
  68. //====================================================================
  69. // IntersectSweptSphere
  70. //====================================================================
  71. bool IntersectSweptSphere(Vec3* hitPos, float& hitDist, const Lineseg& lineseg, float radius, const std::vector<IPhysicalEntity*>& entities)
  72. {
  73.         IPhysicalWorld* pPhysics = gEnv->pPhysicalWorld;
  74.         primitives::sphere spherePrim;
  75.         spherePrim.center = lineseg.start;
  76.         spherePrim.r = radius;
  77.  
  78.         Vec3 dir = lineseg.end - lineseg.start;
  79.  
  80.         ray_hit hit;
  81.         unsigned nEntities = entities.size();
  82.         hitDist = std::numeric_limits<float>::max();
  83.         for (unsigned iEntity = 0; iEntity < nEntities; ++iEntity)
  84.         {
  85.                 IPhysicalEntity* pEntity = entities[iEntity];
  86.                 if (pPhysics->CollideEntityWithBeam(pEntity, lineseg.start, dir, radius, &hit))
  87.                 {
  88.                         if (hit.dist < hitDist)
  89.                         {
  90.                                 if (hitPos)
  91.                                         *hitPos = hit.pt;
  92.                                 hitDist = hit.dist;
  93.                         }
  94.                 }
  95.         }
  96.         return hitDist < std::numeric_limits<float>::max();
  97. }
  98.  
  99. //====================================================================
  100. // OverlapCylinder
  101. //====================================================================
  102. bool OverlapCylinder(const Lineseg& lineseg, float radius, const std::vector<IPhysicalEntity*>& entities)
  103. {
  104.         intersection_params ip;
  105.         ip.bStopAtFirstTri = true;
  106.         ip.bNoAreaContacts = true;
  107.         ip.bNoIntersection = 1;
  108.         ip.bNoBorder = true;
  109.  
  110.         primitives::cylinder cylinderPrim;
  111.         cylinderPrim.center = 0.5f * (lineseg.start + lineseg.end);
  112.         cylinderPrim.axis = lineseg.end - lineseg.start;
  113.         cylinderPrim.hh = 0.5f * cylinderPrim.axis.NormalizeSafe(Vec3Constants<float>::fVec3_OneZ);
  114.         cylinderPrim.r = radius;
  115.  
  116.         ray_hit hit;
  117.         unsigned nEntities = entities.size();
  118.         IPhysicalWorld* pPhysics = gEnv->pPhysicalWorld;
  119.         const Vec3 vZero(ZERO);
  120.         for (unsigned iEntity = 0; iEntity < nEntities; ++iEntity)
  121.         {
  122.                 IPhysicalEntity* pEntity = entities[iEntity];
  123.                 if (pPhysics->CollideEntityWithPrimitive(pEntity, cylinderPrim.type, &cylinderPrim, vZero, &hit, &ip))
  124.                         return true;
  125.         }
  126.         return false;
  127. }
  128.  
  129. // for finding the start/end positions
  130. const float WalkabilityFloorUpDist = 0.25f;
  131. const float WalkabilityFloorDownDist = 2.0f;
  132. // assume character is this fat
  133. const float WalkabilityRadius = 0.25f;
  134. // radius of the swept sphere down to find the floor
  135. const float WalkabilityDownRadius = 0.06f;
  136. // assume character is this tall
  137. const float WalkabilityTotalHeight = 1.8f;
  138. const float WalkabilityCritterTotalHeight = 0.3f;
  139.  
  140. const float WalkabilityTorsoOffset = 0.65f;
  141. const float WalkabilityCritterTorsoOffset = 0.15f;
  142. // maximum allowed floor height change from one to the next
  143. const float WalkabilityMaxDeltaZ = 0.6f;
  144. // height of the torso capsule above foot
  145. const Vec3 WalkabilityTorsoBaseOffset(0.0f, 0.0f, WalkabilityMaxDeltaZ);
  146. // Separation between sample points (horizontal)
  147. const float WalkabilitySampleDist = 0.2f;
  148.  
  149. const Vec3 WalkabilityUp(0.0f, 0.0f, 1.0f);
  150.  
  151. //typedef std::vector<IPhysicalEntity*> PhysicalEntities;
  152.  
  153. bool CheckWalkability(const Vec3& origin, const Vec3& target, float radius, const ListPositions& boundary,
  154.                       Vec3* finalFloor, bool* flatFloor, const AABB* boundaryAABB)
  155. {
  156.         if (Overlap::Lineseg_Polygon2D(Lineseg(origin, target), boundary, boundaryAABB))
  157.                 return false;
  158.  
  159.         return CheckWalkability(origin, target, radius, finalFloor, flatFloor);
  160. }
  161.  
  162. //#include "Puppet.h"
  163.  
  164. bool OverlapTorsoSegment(const Vec3& startOBB, const Vec3& endOBB, float radius, StaticPhysEntityArray& overlapTorsoEntities)
  165. {
  166.         if (overlapTorsoEntities.empty())
  167.                 return false;
  168.  
  169.         // Marcio: HAX for Crysis2 ticks
  170.         bool isCritter = radius < 0.2f;
  171.         const Vec3 TorsoUp(0.0f, 0.0f, max(radius * 0.65f, isCritter ? WalkabilityCritterTorsoOffset : WalkabilityTorsoOffset));
  172.         const float TorsoTotalHeight = isCritter ? WalkabilityCritterTotalHeight : WalkabilityTotalHeight;
  173.  
  174.         const float height = (TorsoTotalHeight - TorsoUp.z);
  175.  
  176.         intersection_params ip;
  177.         ip.bStopAtFirstTri = true;
  178.         ip.bNoAreaContacts = true;
  179.         ip.bNoIntersection = 1;
  180.         ip.bNoBorder = true;
  181.         ip.bThreadSafe = true;
  182.  
  183.         ray_hit hit;
  184.  
  185.         IPhysicalWorld::SPWIParams params;
  186.         params.pSkipEnts = &overlapTorsoEntities[0];
  187.         params.nSkipEnts = -(int)overlapTorsoEntities.size();
  188.         params.sweepDir = Vec3(0.f, 0.f, 0.f);
  189.         params.pip = &ip;
  190.  
  191.         // short cut if start equals end
  192.         if (endOBB.IsEquivalent(startOBB))
  193.         {
  194.                 primitives::cylinder cylinder;
  195.                 cylinder.axis = WalkabilityUp;
  196.                 cylinder.center = Vec3(startOBB.x, startOBB.y, startOBB.z + height * 0.5f);
  197.                 cylinder.center += TorsoUp;
  198.                 cylinder.hh = height * 0.5f;
  199.                 cylinder.r = radius;
  200.  
  201.                 params.itype = primitives::cylinder::type;
  202.                 params.pprim = &cylinder;
  203.  
  204.                 bool result = gEnv->pPhysicalWorld->PrimitiveWorldIntersection(params) > 0.0f;
  205.  
  206.                 if (gAIEnv.CVars.DebugCheckWalkability)
  207.                 {
  208.                         CDebugDrawContext()->DrawCylinder(cylinder.center, cylinder.axis,
  209.                                                           cylinder.r, cylinder.hh * 2.0f, result ? Col_Red : Col_Green);
  210.                 }
  211.  
  212.                 return result;
  213.         }
  214.  
  215.         Vec3 forward = (endOBB - startOBB);
  216.         const float length = forward.NormalizeSafe(Vec3Constants<float>::fVec3_OneY);
  217.         Vec3 right = forward.Cross(Vec3Constants<float>::fVec3_OneZ).GetNormalizedSafe(Vec3Constants<float>::fVec3_OneX);
  218.         Vec3 up = right.Cross(forward);
  219.  
  220.         primitives::box physBox;
  221.         physBox.center = 0.5f * (startOBB + endOBB);
  222.         physBox.center += TorsoUp;
  223.         physBox.center.z += 0.5f * height;
  224.         physBox.size.Set(radius, (0.5f * length), 0.5f * height);
  225.         physBox.bOriented = 1;
  226.         physBox.Basis.SetFromVectors(right, forward, up);
  227.         physBox.Basis.Transpose();
  228.  
  229.         // test obb for plane path
  230.         params.itype = primitives::box::type;
  231.         params.pprim = &physBox;
  232.  
  233.         bool result = gEnv->pPhysicalWorld->PrimitiveWorldIntersection(params) > 0.0f;
  234.  
  235.         if (gAIEnv.CVars.DebugCheckWalkability)
  236.         {
  237.                 OBB obb(OBB::CreateOBB(physBox.Basis.GetTransposed(), physBox.size, ZERO));
  238.  
  239.                 CDebugDrawContext()->DrawOBB(obb, Matrix34::CreateTranslationMat(physBox.center), true, result ? Col_Red : Col_Green,
  240.                                              eBBD_Faceted);
  241.         }
  242.  
  243.         if (!result)
  244.         {
  245.                 primitives::cylinder cylinderStart;
  246.                 cylinderStart.axis = WalkabilityUp;
  247.                 cylinderStart.center = Vec3(startOBB.x, startOBB.y, startOBB.z + height * 0.5f);
  248.                 cylinderStart.center += TorsoUp;
  249.                 cylinderStart.hh = height * 0.5f;
  250.                 cylinderStart.r = radius;
  251.  
  252.                 params.itype = primitives::cylinder::type;
  253.                 params.pprim = &cylinderStart;
  254.                 result |= gEnv->pPhysicalWorld->PrimitiveWorldIntersection(params) > 0.0f;
  255.  
  256.                 if (gAIEnv.CVars.DebugCheckWalkability)
  257.                 {
  258.                         CDebugDrawContext()->DrawCylinder(cylinderStart.center, cylinderStart.axis,
  259.                                                           cylinderStart.r, cylinderStart.hh * 2.0f, result ? Col_Red : Col_Green);
  260.                 }
  261.         }
  262.  
  263.         if (!result)
  264.         {
  265.                 primitives::cylinder cylinderEnd;
  266.                 cylinderEnd.axis = WalkabilityUp;
  267.                 cylinderEnd.center = Vec3(endOBB.x, endOBB.y, endOBB.z + height * 0.5f);
  268.                 cylinderEnd.center += TorsoUp;
  269.                 cylinderEnd.hh = height * 0.5f;
  270.                 cylinderEnd.r = radius;
  271.  
  272.                 params.pprim = &cylinderEnd;
  273.                 result |= gEnv->pPhysicalWorld->PrimitiveWorldIntersection(params) > 0.0f;
  274.  
  275.                 if (gAIEnv.CVars.DebugCheckWalkability)
  276.                 {
  277.                         CDebugDrawContext()->DrawCylinder(cylinderEnd.center, cylinderEnd.axis,
  278.                                                           cylinderEnd.r, cylinderEnd.hh * 2.0f, result ? Col_Red : Col_Green);
  279.                 }
  280.         }
  281.  
  282.         return result;
  283. }
  284.  
  285. //====================================================================
  286. // CheckWalkability
  287. //====================================================================
  288. #pragma warning (push)
  289. #pragma warning (disable: 6262)
  290. bool CheckWalkability(const Vec3& origin, const Vec3& target, float radius, Vec3* finalFloor, bool* flatFloor)
  291. {
  292.         FUNCTION_PROFILER(GetISystem(), PROFILE_AI);
  293.  
  294.         bool floorHeightChanged = false;
  295.  
  296.         Vec3 direction2D(Vec2(target - origin));
  297.         float distanceSq = direction2D.GetLengthSquared2D();
  298.         if (distanceSq < sqr(0.125f))
  299.         {
  300.                 if (finalFloor)
  301.                         *finalFloor = origin;
  302.  
  303.                 if (flatFloor)
  304.                         *flatFloor = true;
  305.  
  306.                 return true;
  307.         }
  308.  
  309.         // Marcio: HAX for Crysis2 ticks
  310.         bool isCritter = radius < 0.2f;
  311.         const Vec3 TorsoUp(0.0f, 0.0f, max(radius * 0.65f, isCritter ? WalkabilityCritterTorsoOffset : WalkabilityTorsoOffset));
  312.         const float TorsoTotalHeight = isCritter ? WalkabilityCritterTotalHeight : WalkabilityTotalHeight;
  313.         const float NextFloorMaxZDiff = isCritter ? 0.25f : 0.75f;
  314.         const float NextFloorZOffset = isCritter ? 0.25f : max(radius, 0.5f);
  315.  
  316.         float distance = direction2D.NormalizeSafe() + radius;
  317.  
  318.         const float OptimalSampleOffset = max(0.225f, radius * 0.85f);
  319.         const float OptimalSegmentLength = gAIEnv.CVars.CheckWalkabilityOptimalSectionLength;
  320.         const size_t OptimalSegmentSampleCount = std::max<size_t>(1, (size_t)(OptimalSegmentLength / OptimalSampleOffset));
  321.  
  322.         size_t sampleCount = (size_t)(distance / OptimalSampleOffset);
  323.         const float sampleOffsetAmount = (sampleCount > 1) ? (distance / (float)sampleCount) : distance;
  324.         const Vec3 sampleOffset = direction2D * sampleOffsetAmount;
  325.  
  326.         const float segmentLength = OptimalSegmentSampleCount * sampleOffsetAmount;
  327.         const size_t segmentCount = 1 + (size_t)(distance / segmentLength);
  328.         const Vec3 segmentOffset = direction2D * segmentLength;
  329.         const size_t segmentSampleCount = OptimalSegmentSampleCount;
  330.  
  331.         float minZ = min(origin.z, target.z) - WalkabilityFloorDownDist;
  332.         float maxZ = max(origin.z, target.z) + TorsoTotalHeight;
  333.         float Zdiff = fabs_tpl(maxZ - minZ);
  334.  
  335.         Vec3 segmentStart = origin;
  336.         Vec3 segmentStartFloor;
  337.         Vec3 newFloor;
  338.  
  339.         Vec3 startOBB(ZERO);
  340.         Vec3 endOBB(ZERO);
  341.  
  342.         StaticAABBArray segmentAABBs;
  343.         StaticPhysEntityArray segmentEntities;
  344.         StaticPhysEntityArray overlapTorsoEntities;
  345.  
  346.         for (size_t i = 0; i < segmentCount; ++i)
  347.         {
  348.                 segmentAABBs.clear();
  349.                 segmentEntities.clear();
  350.  
  351.                 Vec3 segmentEnd = segmentStart + segmentOffset;
  352.  
  353.                 // find all entities for this segment
  354.                 AABB enclosingAABB(AABB::RESET);
  355.  
  356.                 enclosingAABB.Add(Vec3(segmentStart.x, segmentStart.y, minZ), radius);
  357.                 enclosingAABB.Add(Vec3(segmentEnd.x, segmentEnd.y, maxZ), radius);
  358.  
  359.                 size_t entityCount = GetPhysicalEntitiesInBox(enclosingAABB.min, enclosingAABB.max, segmentEntities, AICE_ALL);
  360.  
  361.                 if (!entityCount) // no floor
  362.                         return false;
  363.  
  364.                 segmentAABBs.resize(entityCount);
  365.  
  366.                 pe_status_pos status;
  367.  
  368.                 for (size_t j = 0; j < entityCount; ++j)
  369.                 {
  370.                         IPhysicalEntity* entity = segmentEntities[j];
  371.  
  372.                         if (entity->GetStatus(&status))
  373.                         {
  374.                                 const Vec3 aabbMin(status.BBox[0]);
  375.                                 const Vec3 aabbMax(status.BBox[1]);
  376.  
  377.                                 // terrain will have a zeroed bbox
  378.                                 if (!aabbMin.IsZero() || !aabbMax.IsZero())
  379.                                         segmentAABBs[j] = AABB(aabbMin + status.pos, aabbMax + status.pos);
  380.                                 else
  381.                                         segmentAABBs[j] = enclosingAABB;
  382.                         }
  383.                         else
  384.                                 segmentAABBs[j] = AABB(AABB::RESET);
  385.                 }
  386.  
  387.                 // first segment - get the floor
  388.                 if (i == 0)
  389.                 {
  390.                         if (!FindFloor(segmentStart, segmentEntities, segmentAABBs, segmentStartFloor))
  391.                                 return false;
  392.  
  393.                         newFloor = segmentStartFloor;
  394.                 }
  395.  
  396.                 Vec3 locationFloor = segmentStartFloor;
  397.                 Vec3 checkLocation;
  398.  
  399.                 for (size_t j = 0; (sampleCount > 1) && (j < segmentSampleCount); ++j, --sampleCount)
  400.                 {
  401.                         checkLocation = locationFloor + sampleOffset;
  402.                         checkLocation.z += NextFloorZOffset;
  403.  
  404.                         if (!FindFloor(checkLocation, segmentEntities, segmentAABBs, newFloor))
  405.                                 return false;
  406.  
  407.                         assert(newFloor.IsValid());
  408.  
  409.                         float deltaZ = locationFloor.z - newFloor.z;
  410.                         if (fabs_tpl(deltaZ) > NextFloorMaxZDiff)
  411.                                 return false;
  412.  
  413.                         locationFloor = newFloor;
  414.  
  415.                         // check if we need to do the overlap torso check
  416.                         if (!startOBB.IsZero())
  417.                         {
  418.                                 // find entities for this segment
  419.  
  420.                                 Vec3 base = locationFloor + TorsoUp;
  421.  
  422.                                 AABB cylinderAABB(Vec3(base.x - radius, base.y - radius, base.z),
  423.                                                   Vec3(base.x + radius, base.y + radius, base.z + TorsoTotalHeight - TorsoUp.z));
  424.  
  425.                                 for (size_t k = 0; k < (size_t)segmentAABBs.size(); ++k)
  426.                                 {
  427.                                         if (segmentAABBs[k].IsIntersectBox(cylinderAABB))
  428.                                                 overlapTorsoEntities.push_back(segmentEntities[k]);
  429.                                 }
  430.  
  431.                                 // remove duplicate entries
  432.                                 std::sort(overlapTorsoEntities.begin(), overlapTorsoEntities.end());
  433.                                 overlapTorsoEntities.erase(std::unique(overlapTorsoEntities.begin(), overlapTorsoEntities.end()),
  434.                                                            overlapTorsoEntities.end());
  435.  
  436.                                 // check for planar floor, TODO add code for ramps and a like
  437.                                 if (fabs_tpl(startOBB.z - locationFloor.z) > 0.005f)
  438.                                 {
  439.                                         floorHeightChanged = true;
  440.                                         if (OverlapTorsoSegment(startOBB, endOBB, radius, overlapTorsoEntities))
  441.                                                 return false;
  442.  
  443.                                         overlapTorsoEntities.clear();
  444.                                         startOBB = locationFloor;
  445.                                 }
  446.                         }
  447.                         else
  448.                                 startOBB = locationFloor;
  449.  
  450.                         endOBB = locationFloor;
  451.                 }
  452.  
  453.                 segmentStart = newFloor;
  454.                 segmentStartFloor = newFloor;
  455.         }
  456.  
  457.         if (fabs_tpl(target.z - newFloor.z) > WalkabilityFloorDownDist + WalkabilityFloorUpDist)
  458.                 return false;
  459.  
  460.         // check the last segment also
  461.         if (OverlapTorsoSegment(startOBB, endOBB, radius, overlapTorsoEntities))
  462.                 return false;
  463.  
  464.         if (finalFloor)
  465.                 *finalFloor = newFloor;
  466.  
  467.         if (flatFloor)
  468.                 *flatFloor = !floorHeightChanged;
  469.  
  470.         return true;
  471. }
  472. #pragma warning (pop)
  473.  
  474. //====================================================================
  475. // CheckWalkability
  476. //====================================================================
  477. #pragma warning (push)
  478. #pragma warning (disable: 6262)
  479. bool CheckWalkability(const Vec3& origin, const Vec3& target, float radius,
  480.                       const StaticPhysEntityArray& entities, const StaticAABBArray& aabbs, Vec3* finalFloor, bool* flatFloor)
  481. {
  482.         FUNCTION_PROFILER(GetISystem(), PROFILE_AI);
  483.  
  484.         bool floorHeightChanged = false;
  485.  
  486.         Vec3 direction2D(Vec2(target - origin));
  487.         float distanceSq = direction2D.GetLengthSquared2D();
  488.         if (distanceSq < sqr(0.125f))
  489.         {
  490.                 if (finalFloor)
  491.                         *finalFloor = origin;
  492.  
  493.                 if (flatFloor)
  494.                         *flatFloor = true;
  495.  
  496.                 return true;
  497.         }
  498.  
  499.         // Marcio: HAX for Crysis2 ticks
  500.         bool isCritter = radius < 0.2f;
  501.         const Vec3 TorsoUp(0.0f, 0.0f, max(radius * 0.65f, isCritter ? WalkabilityCritterTorsoOffset : WalkabilityTorsoOffset));
  502.         const float TorsoTotalHeight = isCritter ? WalkabilityCritterTotalHeight : WalkabilityTotalHeight;
  503.         const float NextFloorMaxZDiff = isCritter ? 0.25f : 0.75f;
  504.         const float NextFloorZOffset = isCritter ? 0.25f : max(radius, 0.5f);
  505.  
  506.         float distance = direction2D.NormalizeSafe() + radius;
  507.  
  508.         const float OptimalSampleOffset = max(0.225f, radius * 0.85f);
  509.         const float OptimalSegmentLength = gAIEnv.CVars.CheckWalkabilityOptimalSectionLength;
  510.         const size_t OptimalSegmentSampleCount = std::max<size_t>(1, (size_t)(OptimalSegmentLength / OptimalSampleOffset));
  511.  
  512.         size_t sampleCount = (size_t)(distance / OptimalSampleOffset);
  513.         const float sampleOffsetAmount = (sampleCount > 1) ? (distance / (float)sampleCount) : distance;
  514.         const Vec3 sampleOffset = direction2D * sampleOffsetAmount;
  515.  
  516.         const float segmentLength = OptimalSegmentSampleCount * sampleOffsetAmount;
  517.         const size_t segmentCount = 1 + (size_t)(distance / segmentLength);
  518.         const Vec3 segmentOffset = direction2D * segmentLength;
  519.         const size_t segmentSampleCount = OptimalSegmentSampleCount;
  520.  
  521.         float minZ = min(origin.z, target.z) - WalkabilityFloorDownDist;
  522.         float maxZ = max(origin.z, target.z) + TorsoTotalHeight;
  523.         float Zdiff = fabs_tpl(maxZ - minZ);
  524.  
  525.         Vec3 segmentStart = origin;
  526.         Vec3 segmentStartFloor;
  527.         Vec3 newFloor;
  528.  
  529.         Vec3 startOBB(ZERO);
  530.         Vec3 endOBB(ZERO);
  531.  
  532.         StaticAABBArray segmentAABBs;
  533.         StaticPhysEntityArray segmentEntities;
  534.         StaticPhysEntityArray overlapTorsoEntities;
  535.  
  536.         for (size_t i = 0; i < segmentCount; ++i)
  537.         {
  538.                 segmentAABBs.clear();
  539.                 segmentEntities.clear();
  540.  
  541.                 Vec3 segmentEnd = segmentStart + segmentOffset;
  542.  
  543.                 // find all entities for this segment
  544.                 AABB enclosingAABB(AABB::RESET);
  545.  
  546.                 enclosingAABB.Add(Vec3(segmentStart.x, segmentStart.y, minZ), radius);
  547.                 enclosingAABB.Add(Vec3(segmentEnd.x, segmentEnd.y, maxZ), radius);
  548.  
  549.                 for (size_t j = 0; j < (size_t)aabbs.size(); ++j)
  550.                 {
  551.                         if (enclosingAABB.IsIntersectBox(aabbs[j]))
  552.                         {
  553.                                 segmentAABBs.push_back(aabbs[j]);
  554.                                 segmentEntities.push_back(entities[j]);
  555.                         }
  556.                 }
  557.  
  558.                 if (segmentEntities.empty()) // no floor
  559.                         return false;
  560.  
  561.                 // first segment - get the floor
  562.                 if (i == 0)
  563.                 {
  564.                         if (!FindFloor(segmentStart, segmentEntities, segmentAABBs, segmentStartFloor))
  565.                                 return false;
  566.  
  567.                         newFloor = segmentStartFloor;
  568.                 }
  569.  
  570.                 Vec3 locationFloor = segmentStartFloor;
  571.                 Vec3 checkLocation;
  572.  
  573.                 for (size_t j = 0; (sampleCount > 1) && (j < segmentSampleCount); ++j, --sampleCount)
  574.                 {
  575.                         checkLocation = locationFloor + sampleOffset;
  576.                         checkLocation.z += NextFloorZOffset;
  577.  
  578.                         if (!FindFloor(checkLocation, segmentEntities, segmentAABBs, newFloor))
  579.                                 return false;
  580.  
  581.                         assert(newFloor.IsValid());
  582.  
  583.                         float deltaZ = locationFloor.z - newFloor.z;
  584.                         if (fabs_tpl(deltaZ) > NextFloorMaxZDiff)
  585.                                 return false;
  586.  
  587.                         locationFloor = newFloor;
  588.  
  589.                         // check if we need to do the overlap torso check
  590.                         if (!startOBB.IsZero())
  591.                         {
  592.                                 // find entities for this segment
  593.                                 Vec3 base = locationFloor + TorsoUp;
  594.  
  595.                                 AABB cylinderAABB(Vec3(base.x - radius, base.y - radius, base.z),
  596.                                                   Vec3(base.x + radius, base.y + radius, base.z + TorsoTotalHeight - TorsoUp.z));
  597.  
  598.                                 for (size_t k = 0; k < (size_t)segmentAABBs.size(); ++k)
  599.                                 {
  600.                                         if (segmentAABBs[k].IsIntersectBox(cylinderAABB))
  601.                                                 overlapTorsoEntities.push_back(segmentEntities[k]);
  602.                                 }
  603.  
  604.                                 // remove duplicate entries
  605.                                 std::sort(overlapTorsoEntities.begin(), overlapTorsoEntities.end());
  606.                                 overlapTorsoEntities.erase(std::unique(overlapTorsoEntities.begin(), overlapTorsoEntities.end()),
  607.                                                            overlapTorsoEntities.end());
  608.  
  609.                                 // check for planar floor, TODO add code for ramps and a like
  610.                                 if (fabs_tpl(startOBB.z - locationFloor.z) > 0.005f)
  611.                                 {
  612.                                         floorHeightChanged = true;
  613.                                         if (OverlapTorsoSegment(startOBB, endOBB, radius, overlapTorsoEntities))
  614.                                                 return false;
  615.  
  616.                                         overlapTorsoEntities.clear();
  617.                                         startOBB = locationFloor;
  618.                                 }
  619.                         }
  620.                         else
  621.                                 startOBB = locationFloor;
  622.  
  623.                         endOBB = locationFloor;
  624.                 }
  625.  
  626.                 segmentStart = newFloor;
  627.                 segmentStartFloor = newFloor;
  628.         }
  629.  
  630.         if (fabs_tpl(target.z - newFloor.z) > WalkabilityFloorDownDist + WalkabilityFloorUpDist)
  631.                 return false;
  632.  
  633.         // check the last segment also
  634.         if (OverlapTorsoSegment(startOBB, endOBB, radius, overlapTorsoEntities))
  635.                 return false;
  636.  
  637.         if (finalFloor)
  638.                 *finalFloor = newFloor;
  639.  
  640.         if (flatFloor)
  641.                 *flatFloor = !floorHeightChanged;
  642.  
  643.         return true;
  644. }
  645. #pragma warning (pop)
  646.  
  647. bool CheckWalkabilitySimple(/*Vec3 from, Vec3 to,*/ SWalkPosition fromPos, SWalkPosition toPos, float radius, EAICollisionEntities aiCollisionEntities)
  648. {
  649.         FUNCTION_PROFILER(GetISystem(), PROFILE_AI);
  650.  
  651.         const Vec3 from(fromPos.m_pos);
  652.         const Vec3 to(toPos.m_pos);
  653.  
  654.         Vec3 fromFloor;
  655.         Vec3 toFloor;
  656.  
  657.         if (fromPos.m_isFloor)
  658.                 fromFloor = from;
  659.         else if (!gAIEnv.pWalkabilityCacheManager->FindFloor(0, from, fromFloor))
  660.                 return false;
  661.  
  662.         if (toPos.m_isFloor)
  663.                 toFloor = to;
  664.         else if (!gAIEnv.pWalkabilityCacheManager->FindFloor(0, to, toFloor))
  665.                 return false;
  666.  
  667.         // Marcio: HAX for Crysis2 ticks
  668.         bool isCritter = radius < 0.2f;
  669.         const Vec3 TorsoUp(0.0f, 0.0f, max(radius * 0.65f, isCritter ? WalkabilityCritterTorsoOffset : WalkabilityTorsoOffset));
  670.         const float TorsoTotalHeight = isCritter ? WalkabilityCritterTotalHeight : WalkabilityTotalHeight;
  671.  
  672.         const float checkRadius = radius - 0.0001f;
  673.         const Vec3 horWalkDelta = toFloor - fromFloor;
  674.         const float horWalkDistSq = horWalkDelta.len2();
  675.  
  676.         if (horWalkDistSq > 0.001f)
  677.         {
  678.                 const float horWalkDist = sqrt_tpl(horWalkDistSq);
  679.                 const Vec3 horWalkDir = horWalkDelta / horWalkDist;
  680.                 const float boxHeight = TorsoTotalHeight - TorsoUp.z;
  681.  
  682.                 primitives::box boxPrim;
  683.                 boxPrim.center = 0.5f * (fromFloor + toFloor);
  684.                 boxPrim.center.z += TorsoUp.z + 0.5f * boxHeight;
  685.                 boxPrim.size.Set(checkRadius, 0.5f * horWalkDist, boxHeight * 0.5f);
  686.                 boxPrim.bOriented = 1;
  687.  
  688.                 const Vec3 right = horWalkDir.Cross(Vec3Constants<float>::fVec3_OneZ).GetNormalizedSafe(Vec3Constants<float>::fVec3_OneY);
  689.                 const Vec3 up = right.Cross(horWalkDir);
  690.  
  691.                 boxPrim.Basis.SetFromVectors(right, horWalkDir, up);
  692.                 boxPrim.Basis.Transpose();
  693.  
  694.                 //[Alexey] Because of return false between CreatePrimitive and Release we had leaks here!!!
  695.                 //_smart_ptr<IGeometry> box = gEnv->pPhysicalWorld->GetGeomManager()->CreatePrimitive(primitives::box::type,&boxPrim);
  696.                 //box->Release();
  697.                 // NOTE Sep 7, 2007: <pvl> made static after SetData() interface became
  698.                 // available, to avoid per-frame allocations
  699.                 //static IGeometry * box = gEnv->pPhysicalWorld->GetGeomManager()->CreatePrimitive(primitives::box::type,&boxPrim);
  700.                 // Changed to get it from the CAISytem so it can be released at levelUnload.
  701.                 IGeometry*& walkabilityGeometryBox = GetAISystem()->m_walkabilityGeometryBox;
  702.                 if (!walkabilityGeometryBox)
  703.                         walkabilityGeometryBox = gEnv->pPhysicalWorld->GetGeomManager()->CreatePrimitive(primitives::box::type, &boxPrim);
  704.                 walkabilityGeometryBox->SetData(&boxPrim);
  705.  
  706.                 pe_status_nparts snp;
  707.                 pe_status_pos sp;
  708.                 geom_world_data gwd;
  709.                 intersection_params ip;
  710.                 ip.bStopAtFirstTri = true;
  711.                 ip.bNoAreaContacts = true;
  712.                 ip.bNoBorder = true;
  713.                 ip.bNoIntersection = 1;
  714.                 ip.bThreadSafe = true;
  715.  
  716.                 bool result = (gEnv->pPhysicalWorld->PrimitiveWorldIntersection(primitives::box::type, &boxPrim, Vec3(ZERO), aiCollisionEntities,
  717.                                                                                 0, 0, geom_colltype0 | geom_colltype_player, &ip) <= 0.0f);
  718.  
  719. #ifdef DBG_WALK
  720.                 // debug
  721.                 OBB obb;
  722.                 obb.SetOBB(boxPrim.Basis.GetTransposed(), boxPrim.size, Vec3(ZERO));
  723.                 GetAISystem()->AddDebugBox(boxPrim.center, obb, 128, 0, 0, 5.0f);
  724. #endif
  725.                 return result;
  726.         }
  727.  
  728.         return true;
  729. }
  730.  
  731. //====================================================================
  732. // FindFloor
  733. //====================================================================
  734. bool FindFloor(const Vec3& position, Vec3& floor)
  735. {
  736.         const Vec3 dir = Vec3(0.0f, 0.0f, -(WalkabilityFloorDownDist + WalkabilityFloorUpDist));
  737.         const Vec3 start = position + Vec3(0, 0, WalkabilityFloorUpDist);
  738.  
  739.         const RayCastResult& result = gAIEnv.pRayCaster->Cast(RayCastRequest(start, dir, AICE_ALL,
  740.                                                                              rwi_stop_at_pierceable | rwi_colltype_any(geom_colltype_player)));
  741.  
  742.         if (!result || (result[0].dist < 0.0f))
  743.         {
  744.                 if (gAIEnv.CVars.DebugCheckWalkability)
  745.                 {
  746.                         CDebugDrawContext dc;
  747.  
  748.                         dc->DrawLine(start, Col_Red, start + dir, Col_Red);
  749.                         dc->DrawCone(start, Vec3(0.0f, 0.0f, -1.0f), 0.175f, 0.45f, Col_Red);
  750.                 }
  751.  
  752.                 return false;
  753.         }
  754.  
  755.         floor = Vec3(start.x, start.y, start.z - result[0].dist);
  756.  
  757.         if (gAIEnv.CVars.DebugCheckWalkability)
  758.         {
  759.                 CDebugDrawContext dc;
  760.  
  761.                 dc->DrawLine(start, Col_Green, start + dir, Col_Green);
  762.                 dc->DrawCone(start, Vec3(0.0f, 0.0f, -1.0f), 0.125f, 0.25f, Col_Green);
  763.                 dc->DrawCone(floor + Vec3(0.0f, 0.0f, 0.35f), Vec3(0.0f, 0.0f, -1.0f), 0.125f, 0.35f, Col_SteelBlue);
  764.         }
  765.  
  766.         return true;
  767. }
  768.  
  769. //====================================================================
  770. // FindFloor
  771. //====================================================================
  772. bool FindFloor(const Vec3& position, const StaticPhysEntityArray& entities, const StaticAABBArray& aabbs, Vec3& floor)
  773. {
  774.         Vec3 dir = Vec3(0.0f, 0.0f, -(WalkabilityFloorDownDist + WalkabilityFloorUpDist));
  775.         const Vec3 start = position + Vec3(0, 0, WalkabilityFloorUpDist);
  776.         const Lineseg line(start, start + dir);
  777.         IPhysicalWorld* const physicalWorld = gEnv->pPhysicalWorld;
  778.  
  779.         ray_hit hit;
  780.         float closest = FLT_MAX;
  781.  
  782.         size_t entityCount = (size_t)aabbs.size();
  783.         for (size_t i = 0; i < entityCount; ++i)
  784.         {
  785.                 const AABB& aabb = aabbs[i];
  786.  
  787.                 if ((aabb.min.x <= start.x) && (aabb.max.x >= start.x) &&
  788.                     (aabb.min.y <= start.y) && (aabb.max.y >= start.y) &&
  789.                     physicalWorld->RayTraceEntity(entities[i], start, dir, &hit, 0, geom_colltype_player))
  790.                 {
  791.                         if (hit.dist < closest)
  792.                                 closest = hit.dist;
  793.                 }
  794.         }
  795.  
  796.         if (closest < FLT_MAX)
  797.         {
  798.                 floor = Vec3(position.x, position.y, start.z - closest);
  799.  
  800.                 if (gAIEnv.CVars.DebugCheckWalkability)
  801.                 {
  802.                         CDebugDrawContext dc;
  803.  
  804.                         dc->DrawLine(line.start, Col_Green, line.end, Col_Green);
  805.                         dc->DrawCone(line.start, Vec3(0.0f, 0.0f, -1.0f), 0.125f, 0.25f, Col_Green);
  806.                         dc->DrawCone(floor + Vec3(0.0f, 0.0f, 0.35f), Vec3(0.0f, 0.0f, -1.0f), 0.125f, 0.35f, Col_SteelBlue);
  807.                 }
  808.  
  809.                 return true;
  810.         }
  811.  
  812.         if (gAIEnv.CVars.DebugCheckWalkability)
  813.         {
  814.                 CDebugDrawContext dc;
  815.  
  816.                 dc->DrawLine(line.start, Col_Red, line.end, Col_Red);
  817.                 dc->DrawCone(line.start, Vec3(0.0f, 0.0f, -1.0f), 0.175f, 0.45f, Col_Red);
  818.         }
  819.  
  820.         return false;
  821. }
  822.  
  823. //===================================================================
  824. // IsLeft: tests if a point is Left|On|Right of an infinite line.
  825. //    Input:  three points P0, P1, and P2
  826. //    Return: >0 for P2 left of the line through P0 and P1
  827. //            =0 for P2 on the line
  828. //            <0 for P2 right of the line
  829. //===================================================================
  830. inline float IsLeft(Vec3 P0, Vec3 P1, const Vec3& P2)
  831. {
  832.         bool swap = false;
  833.         if (P0.x < P1.x)
  834.                 swap = true;
  835.         else if (P0.x == P1.x && P0.y < P1.y)
  836.                 swap = true;
  837.  
  838.         if (swap)
  839.                 std::swap(P0, P1);
  840.  
  841.         float res = (P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y);
  842.         const float tol = 0.0000f;
  843.         if (res > tol || res < -tol)
  844.                 return swap ? -res : res;
  845.         else
  846.                 return 0.0f;
  847. }
  848.  
  849. inline bool ptEqual(const Vec3& lhs, const Vec3& rhs)
  850. {
  851.         const float tol = 0.01f;
  852.         return (fabs(lhs.x - rhs.x) < tol) && (fabs(lhs.y - rhs.y) < tol);
  853. }
  854.  
  855. #if 0
  856. struct SPointSorter
  857. {
  858.         SPointSorter(const Vec3& pt) : pt(pt) {}
  859.         bool operator()(const Vec3& lhs, const Vec3& rhs)
  860.         {
  861.                 float isLeft = IsLeft(pt, lhs, rhs);
  862.                 if (isLeft > 0.0f)
  863.                         return true;
  864.                 else if (isLeft < 0.0f)
  865.                         return false;
  866.                 else
  867.                         return (lhs - pt).GetLengthSquared2D() < (rhs - pt).GetLengthSquared2D();
  868.         }
  869.         const Vec3 pt;
  870. };
  871.  
  872. //===================================================================
  873. // ConvexHull2D
  874. // Implements Graham's scan
  875. //===================================================================
  876. void ConvexHull2DGraham(std::vector<Vec3>& ptsOut, const std::vector<Vec3>& ptsIn)
  877. {
  878.         FUNCTION_PROFILER(gEnv->pSystem, PROFILE_AI);
  879.         const unsigned nPtsIn = ptsIn.size();
  880.         if (nPtsIn < 3)
  881.         {
  882.                 ptsOut = ptsIn;
  883.                 return;
  884.         }
  885.         unsigned iBotRight = 0;
  886.         for (unsigned iPt = 1; iPt < nPtsIn; ++iPt)
  887.         {
  888.                 if (ptsIn[iPt].y < ptsIn[iBotRight].y)
  889.                         iBotRight = iPt;
  890.                 else if (ptsIn[iPt].y == ptsIn[iBotRight].y && ptsIn[iPt].x < ptsIn[iBotRight].x)
  891.                         iBotRight = iPt;
  892.         }
  893.  
  894.         static std::vector<Vec3> ptsSorted; // avoid memory allocation
  895.         ptsSorted.assign(ptsIn.begin(), ptsIn.end());
  896.  
  897.         std::swap(ptsSorted[0], ptsSorted[iBotRight]);
  898.         {
  899.                 FRAME_PROFILER("SORT Graham", gEnv->pSystem, PROFILE_AI)
  900.                 std::sort(ptsSorted.begin() + 1, ptsSorted.end(), SPointSorter(ptsSorted[0]));
  901.         }
  902.         ptsSorted.erase(std::unique(ptsSorted.begin(), ptsSorted.end(), ptEqual), ptsSorted.end());
  903.  
  904.         const unsigned nPtsSorted = ptsSorted.size();
  905.         if (nPtsSorted < 3)
  906.         {
  907.                 ptsOut = ptsSorted;
  908.                 return;
  909.         }
  910.  
  911.         ptsOut.resize(0);
  912.         ptsOut.push_back(ptsSorted[0]);
  913.         ptsOut.push_back(ptsSorted[1]);
  914.         unsigned int i = 2;
  915.         while (i < nPtsSorted)
  916.         {
  917.                 if (ptsOut.size() <= 1)
  918.                 {
  919.                         AIWarning("Badness in ConvexHull2D");
  920.                         AILogComment("i = %d ptsIn = ", i);
  921.                         for (unsigned j = 0; j < ptsIn.size(); ++j)
  922.                                 AILogComment("%6.3f, %6.3f, %6.3f", ptsIn[j].x, ptsIn[j].y, ptsIn[j].z);
  923.                         AILogComment("ptsSorted = ");
  924.                         for (unsigned j = 0; j < ptsSorted.size(); ++j)
  925.                                 AILogComment("%6.3f, %6.3f, %6.3f", ptsSorted[j].x, ptsSorted[j].y, ptsSorted[j].z);
  926.                         ptsOut.resize(0);
  927.                         return;
  928.                 }
  929.                 const Vec3& pt1 = ptsOut[ptsOut.size() - 1];
  930.                 const Vec3& pt2 = ptsOut[ptsOut.size() - 2];
  931.                 const Vec3& p = ptsSorted[i];
  932.                 float isLeft = IsLeft(pt2, pt1, p);
  933.                 if (isLeft > 0.0f)
  934.                 {
  935.                         ptsOut.push_back(p);
  936.                         ++i;
  937.                 }
  938.                 else if (isLeft < 0.0f)
  939.                 {
  940.                         ptsOut.pop_back();
  941.                 }
  942.                 else
  943.                 {
  944.                         ptsOut.pop_back();
  945.                         ptsOut.push_back(p);
  946.                         ++i;
  947.                 }
  948.         }
  949. }
  950. #endif
  951.  
  952. inline float IsLeftAndrew(const Vec3& p0, const Vec3& p1, const Vec3& p2)
  953. {
  954.         return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
  955. }
  956.  
  957. inline bool PointSorterAndrew(const Vec3& lhs, const Vec3& rhs)
  958. {
  959.         if (lhs.x < rhs.x) return true;
  960.         if (lhs.x > rhs.x) return false;
  961.         return lhs.y < rhs.y;
  962. }
  963.  
  964. //===================================================================
  965. // ConvexHull2D
  966. // Implements Andrew's algorithm
  967. //
  968. // Copyright 2001, softSurfer (www.softsurfer.com)
  969. // This code may be freely used and modified for any purpose
  970. // providing that this copyright notice is included with it.
  971. // SoftSurfer makes no warranty for this code, and cannot be held
  972. // liable for any real or imagined damage resulting from its use.
  973. // Users of this code must verify correctness for their application.
  974. //===================================================================
  975. static std::vector<Vec3> ConvexHull2DAndrewTemp;
  976.  
  977. void ConvexHull2DAndrew(std::vector<Vec3>& ptsOut, const std::vector<Vec3>& ptsIn)
  978. {
  979.         FUNCTION_PROFILER(gEnv->pSystem, PROFILE_AI);
  980.         const int n = (int)ptsIn.size();
  981.         if (n < 3)
  982.         {
  983.                 ptsOut = ptsIn;
  984.                 return;
  985.         }
  986.  
  987.         std::vector<Vec3>& P = ConvexHull2DAndrewTemp;
  988.         P = ptsIn;
  989.  
  990.         {
  991.                 FRAME_PROFILER("SORT Andrew", gEnv->pSystem, PROFILE_AI)
  992.                 std::sort(P.begin(), P.end(), PointSorterAndrew);
  993.         }
  994.  
  995.         // the output array ptsOut[] will be used as the stack
  996.         int i;
  997.  
  998.         ptsOut.clear();
  999.         ptsOut.reserve(P.size());
  1000.  
  1001.         // Get the indices of points with min x-coord and min|max y-coord
  1002.         int minmin = 0, minmax;
  1003.         float xmin = P[0].x;
  1004.         for (i = 1; i < n; i++)
  1005.                 if (P[i].x != xmin)
  1006.                         break;
  1007.  
  1008.         minmax = i - 1;
  1009.         if (minmax == n - 1)
  1010.         {
  1011.                 // degenerate case: all x-coords == xmin
  1012.                 ptsOut.push_back(P[minmin]);
  1013.                 if (P[minmax].y != P[minmin].y) // a nontrivial segment
  1014.                         ptsOut.push_back(P[minmax]);
  1015.                 ptsOut.push_back(P[minmin]);           // add polygon endpoint
  1016.                 return;
  1017.         }
  1018.  
  1019.         // Get the indices of points with max x-coord and min|max y-coord
  1020.         int maxmin, maxmax = n - 1;
  1021.         float xmax = P[n - 1].x;
  1022.         for (i = n - 2; i >= 0; i--)
  1023.                 if (P[i].x != xmax) break;
  1024.         maxmin = i + 1;
  1025.  
  1026.         // Compute the lower hull on the stack H
  1027.         ptsOut.push_back(P[minmin]);      // push minmin point onto stack
  1028.         i = minmax;
  1029.         while (++i <= maxmin)
  1030.         {
  1031.                 // the lower line joins P[minmin] with P[maxmin]
  1032.                 if (IsLeftAndrew(P[minmin], P[maxmin], P[i]) >= 0 && i < maxmin)
  1033.                         continue;          // ignore P[i] above or on the lower line
  1034.  
  1035.                 while ((int)ptsOut.size() > 1) // there are at least 2 points on the stack
  1036.                 {
  1037.                         // test if P[i] is left of the line at the stack top
  1038.                         if (IsLeftAndrew(ptsOut[ptsOut.size() - 2], ptsOut.back(), P[i]) > 0)
  1039.                                 break;         // P[i] is a new hull vertex
  1040.                         else
  1041.                                 ptsOut.pop_back(); // pop top point off stack
  1042.                 }
  1043.                 ptsOut.push_back(P[i]);       // push P[i] onto stack
  1044.         }
  1045.  
  1046.         // Next, compute the upper hull on the stack H above the bottom hull
  1047.         if (maxmax != maxmin)             // if distinct xmax points
  1048.                 ptsOut.push_back(P[maxmax]);    // push maxmax point onto stack
  1049.         int bot = (int)ptsOut.size() - 1; // the bottom point of the upper hull stack
  1050.         i = maxmin;
  1051.         while (--i >= minmax)
  1052.         {
  1053.                 // the upper line joins P[maxmax] with P[minmax]
  1054.                 if (IsLeftAndrew(P[maxmax], P[minmax], P[i]) >= 0 && i > minmax)
  1055.                         continue;          // ignore P[i] below or on the upper line
  1056.  
  1057.                 while ((int)ptsOut.size() > bot + 1)    // at least 2 points on the upper stack
  1058.                 {
  1059.                         // test if P[i] is left of the line at the stack top
  1060.                         if (IsLeftAndrew(ptsOut[ptsOut.size() - 2], ptsOut.back(), P[i]) > 0)
  1061.                                 break;         // P[i] is a new hull vertex
  1062.                         else
  1063.                                 ptsOut.pop_back();         // pop top po2int off stack
  1064.                 }
  1065.                 ptsOut.push_back(P[i]);       // push P[i] onto stack
  1066.         }
  1067.         if (minmax != minmin)
  1068.                 ptsOut.push_back(P[minmin]);  // push joining endpoint onto stack
  1069.         if (!ptsOut.empty() && ptEqual(ptsOut.front(), ptsOut.back()))
  1070.                 ptsOut.pop_back();
  1071. }
  1072.  
  1073. //===================================================================
  1074. // GetFloorRectangleFromOrientedBox
  1075. //===================================================================
  1076. void GetFloorRectangleFromOrientedBox(const Matrix34& tm, const AABB& box, SAIRect3& rect)
  1077. {
  1078.         Matrix33 tmRot(tm);
  1079.         tmRot.Transpose();
  1080.  
  1081.         Vec3 corners[8];
  1082.         SetAABBCornerPoints(box, corners);
  1083.  
  1084.         rect.center = tm.GetTranslation();
  1085.  
  1086.         rect.axisu = tm.GetColumn1();
  1087.         rect.axisu.z = 0;
  1088.         rect.axisu.Normalize();
  1089.         rect.axisv.Set(rect.axisu.y, -rect.axisu.x, 0);
  1090.  
  1091.         Vec3 tu = tmRot.TransformVector(rect.axisu);
  1092.         Vec3 tv = tmRot.TransformVector(rect.axisv);
  1093.  
  1094.         rect.min.x = FLT_MAX;
  1095.         rect.min.y = FLT_MAX;
  1096.         rect.max.x = -FLT_MAX;
  1097.         rect.max.y = -FLT_MAX;
  1098.  
  1099.         for (unsigned i = 0; i < 8; ++i)
  1100.         {
  1101.                 float du = tu.Dot(corners[i]);
  1102.                 float dv = tv.Dot(corners[i]);
  1103.                 rect.min.x = min(rect.min.x, du);
  1104.                 rect.max.x = max(rect.max.x, du);
  1105.                 rect.min.y = min(rect.min.y, dv);
  1106.                 rect.max.y = max(rect.max.y, dv);
  1107.         }
  1108. }
  1109.  
  1110. void CleanupAICollision()
  1111. {
  1112.         stl::free_container(ConvexHull2DAndrewTemp);
  1113. }
  1114.  
downloadAICollision.cpp Source code - Download CRYENGINE Source code
Related Source Codes/Software:
postal - 2017-06-11
reactide - Reactide is the first dedicated IDE for React web ... 2017-06-11
rkt - rkt is a pod-native container engine for Linux. It... 2017-06-11
uWebSockets - Tiny WebSockets https://for... 2017-06-11
realworld - TodoMVC for the RealWorld - Exemplary fullstack Me... 2017-06-11
CRYENGINE - CRYENGINE is a powerful real-time game development... 2017-06-11
goreplay - GoReplay is an open-source tool for capturing and ... 2017-06-10
pyenv - Simple Python version management 2017-06-10
redux-saga - An alternative side effect model for Redux apps ... 2017-06-10
angular-starter - 2017-06-10

 Back to top