Player Controller - Convex Cast Normal Directions

[bmsq]

Hi,

I've been working on a custom player controller that is based on the same algorithm used by the quake games. It generally works quite well but it is not always smooth when pushing up against the edges of geometry which is at odd angles.

The algorithm relies heavily on convex cast to identify the normals of surfaces the player will bump into each frame update (I can explain the algorithm in more depth if required). I've noticed that the normal returned from Convex Cast points away from the controller when the strange behavior starts to occur.

What would be causing the odd normal direction and how is the best way to work around it?

I've tied using both the m_normal and m_normalOnPoint but both can suffer this issue (not always at the same time though). I've also tried autmatically flipping the normal by creating a plane from m_normal and m_point and the testing which side of the plane the player is on. However, this doesn't seem reliable when the origin of the body is close to the impact point.

Thanks,
Barry

[Julio Jerez]

I've been working on a custom player controller that is based on the same algorithm used by the quake games.

what algorithm is that? can I see a reference to it?

on the normal orientation,
In elrleir version of core 200 contact did not have a prefer orientation because for calculating reaction forces and impulse the orientation does not matter, only the direction in important.
Then I realised that in the contact callback the normal orientation is important for some effects, so in laters version I added the body parameter to the material callback so that teh user get teh proper normal orientation.
for example in earlier version of 200 one such function was like this

Code: Select all

void NewtonMaterialGetContactPositionAndNormal(const NewtonMaterial* const materialHandle, dFloat* const positPtr, dFloat* const normalPtr)
{
   TRACE_FUNTION(__FUNCTION__);
   dgContactMaterial* const material = (dgContactMaterial*) materialHandle;

   positPtr[0] = material->m_point.m_x;
   positPtr[1] = material->m_point.m_y;
   positPtr[2] = material->m_point.m_z;

   normalPtr[0] = material->m_normal.m_x;
   normalPtr[1] = material->m_normal.m_y;
   normalPtr[2] = material->m_normal.m_z;
}

and now it is like this

Code: Select all

void NewtonMaterialGetContactPositionAndNormal(const NewtonMaterial* const materialHandle, NewtonBody* const body, dFloat* const positPtr, dFloat* const normalPtr)
{
   TRACE_FUNTION(__FUNCTION__);
   dgContactMaterial* const material = (dgContactMaterial*) materialHandle;

   positPtr[0] = material->m_point.m_x;
   positPtr[1] = material->m_point.m_y;
   positPtr[2] = material->m_point.m_z;

   normalPtr[0] = material->m_normal.m_x;
   normalPtr[1] = material->m_normal.m_y;
   normalPtr[2] = material->m_normal.m_z;

   if ((dgBody*)body != material->m_body0) {
      normalPtr[0] *= dgFloat32 (-1.0f);
      normalPtr[1] *= dgFloat32 (-1.0f);
      normalPtr[2] *= dgFloat32 (-1.0f);
   }
}

However I do not remenber I ever adding the oriention information to the user contact function. It is either that or some bug, in convex cast.
can I see your code?
can I see a video or an image that shows the contacts at the moment that they flips?

I've noticed that the normal returned from Convex Cast points away from the controller when the strange behavior starts to occur.

that maybe be the reason too that teh joint Player controller some time fail, and I never found the reason.

[bmsq]

Hi Julio,

Thanks for the quick response! I'm currently using an older version of newton (2.13) which I don't think has the contact changes you described in your post. I'll try updating to the latest core 200 build and see if the problem still occurs. I'm not home this weekend so I may not be able to post back with results/screenshots/video/demo until next week.

As for the controller algorithm, I got it from looking at the quake 3 source code. I've also looked at q1 and q2 code and it's essentially the same thing. The algorithm is called SlideMove and it works by performing a convex cast from the current position to the expected position at the end of the frame. If a collision if found, the impact normal is checked against all previous impact normals and a new velocity direction is calculated. The new velocity is calculated so the player will "slide" along all existing normals, the last impact normal is saved and this process is repeated until the end of the frame or the player hits three intersecting normals and stops. Initially, the saved normal list contains just the ground normal and a "fake" normal to prevent backwards movement.

An example implementation always helps to understand an algorithm. Here is my current code which still includes some warts and debug code. I haven't wrapped this up as a generic joint yet, the "Tick" function is called each frame by my engine to perform the player movement.

I can send through links to the original source that I used to understand the algorithm if needed. Let me know if there is anything that you think could be improved or doesnt look right.

Cheers,
Barry

Code: Select all

/*================================================================================
   Title: CharacterController.cpp
   Author: Barry Squire
   Description:
================================================================================*/
#include <stdafx.h>
#include <Components/Entity.h>
#include <Components/TransformComponent.h>
#include "BodyComponent.h"
#include "CharacterController.h"


/*--------------------------------------------------------------------------------
   constructors / destructors:
--------------------------------------------------------------------------------*/
CharacterController::CharacterController()
{
   // default max slope to 45 degrees
   SetMaxSlope(45.001f * acosf(0.0f) / 90.0f);
   SetMaxStepHeight(0.501f);
   SetMaxAcceleration(16.0f);
   SetAirControl(0.125f);

   mUp = Vector::UNIT_Z;
   mGravity = Vector(0.0f, 0.0f, -9.8f);

   mSensor = NULL;
   mVelocity = Vector::ZERO;
   mState = STATE_AIRBORNE;
}

//--------------------------------------------------------------------------------
CharacterController::~CharacterController()
{
}


/*--------------------------------------------------------------------------------
   Public functions:
--------------------------------------------------------------------------------*/
float CharacterController::GetMaxSlope() const
{
   return acosf(mMaxSlope);
}

//--------------------------------------------------------------------------------
void CharacterController::SetMaxSlope(float angle)
{
   mMaxSlope = cosf(angle);
}

//--------------------------------------------------------------------------------
float CharacterController::GetMaxStepHeight() const
{
   return mStepHeight;
}

//--------------------------------------------------------------------------------
void CharacterController::SetMaxStepHeight(float height)
{
   mStepHeight = height;
}

//--------------------------------------------------------------------------------
float CharacterController::GetMaxAcceleration() const
{
   return mMaxAcceleration;
}

//--------------------------------------------------------------------------------
void CharacterController::SetMaxAcceleration(float acceleration)
{
   mMaxAcceleration = acceleration;
}

//--------------------------------------------------------------------------------
float CharacterController::GetAirControl() const
{
   return mAirControl;
}

//--------------------------------------------------------------------------------
void CharacterController::SetAirControl(float control)
{
   mAirControl = control;
}

//--------------------------------------------------------------------------------
void CharacterController::SetGravity(Vector &gravity)
{
   mGravity = gravity;

   Vector up(gravity);
   up.Normalise();
   up *= -1;

   // calculate the rotation quaternion which takes us from the current up vector to the new up vector
   float d = mUp.DotProduct(up);
   if (d < 1.0f)
   {
      Quaternion rotation;

      if (d < 1e-6f - 1.0f)
      {
         Vector axis = mUp.CrossProduct(Vector::UNIT_X);
         if (axis.IsZeroLength() == true)
            axis = mUp.CrossProduct(Vector::UNIT_Y);

         axis.Normalise();
         rotation.FromAngleAxis(acosf(0) *2.0f, axis);
      }
      else
      {
         float s = sqrtf((1 + d) * 2.0f);
         float inv = 1 / s;

         Vector c = mUp.CrossProduct(up);

         rotation.x = c.x * inv;
         rotation.y = c.y * inv;
         rotation.z = c.z * inv;
         rotation.w = s * 0.5f;

         rotation.Normalise();
      }

      mOrientation *= rotation;
      mOrientation.Normalise();
   }

   mUp = up;
}

//--------------------------------------------------------------------------------
void CharacterController::Jump()
{
   mMoveInput.z = 5.0f;
}

//--------------------------------------------------------------------------------
void CharacterController::Move(float forward, float side, float heading)
{
   mAngle = heading;
   mMoveInput.x = side;
   mMoveInput.y = forward;
}

//--------------------------------------------------------------------------------
void CharacterController::Reset()
{
   // body component configuration
   BodyComponent *body = GetOwner()->GetComponent<BodyComponent>();
   body->SetAutoSleep(false);
   body->SetSleeping(false);
   body->SetCollisionMode(BodyComponent::COLLIDE_NONE);  // disable collision with existing collision

   // newton body configuration
   mBody = body->GetNewtonBody();
   NewtonBodySetForceAndTorqueCallback(mBody, NULL);
   CreateSensor();

   // prevent the body from sleeping

   TransformComponent *transform = GetOwner()->GetComponent<TransformComponent>();
   mPosition = transform->GetPosition();
}

//--------------------------------------------------------------------------------
void CharacterController::Tick(float time, bool extraIterations)
{
   Quaternion direction;
   direction.FromAngleAxis(mAngle, Vector::UNIT_Z);
   direction = mOrientation * direction;

   // early exit if we are static
   //if (mMass == 0.0f)
   //   return;

   // find ground
   float hitParam;
   NewtonWorldConvexCastReturnInfo impactInfo;
   Vector movement = mUp * -0.1f;
   mOnGround = ConvexCast(mPosition, mSensor, movement, hitParam, impactInfo);
   mGroundNormal = impactInfo.m_normal;

   // perform movement based on current state
   switch (DetermineCurrentState())
   {
   case STATE_AIRBORNE:
      AirMove(direction, time);
      break;

   case STATE_WALKING:
      WalkMove(direction, time);
      break;
   };

   // calculate the controller transformation
   Matrix transform = Matrix::IDENTITY;
   direction.ToRotationMatrix(transform);
   transform(0, 3) = mPosition.x;
   transform(1, 3) = mPosition.y;
   transform(2, 3) = mPosition.z;
   NewtonBodySetMatrix(mBody, transform);
}

/*--------------------------------------------------------------------------------
   Protected functions:
--------------------------------------------------------------------------------*/
#include <Components/World.h>
#include "PhysicsManager.h"
void CharacterController::OnAdd()
{
   GetOwner()->GetWorld()->GetComponentManager<PhysicsManager>()->controller = this;
}

//--------------------------------------------------------------------------------
void CharacterController::OnRemove()
{
   // remove the joint...

   if (mSensor != NULL)
      NewtonReleaseCollision(NewtonBodyGetWorld(mBody), mSensor);
}

/*--------------------------------------------------------------------------------
   Protected functions:
--------------------------------------------------------------------------------*/
void CharacterController::CreateSensor()
{
   // free any existing sensor
   if (mSensor != NULL)
      NewtonReleaseCollision(NewtonBodyGetWorld(mBody), mSensor);

   // get the body's collision
   NewtonCollision *collision = NewtonBodyGetCollision(mBody);

   // calculate vertical dimensions
   Vector top;
   Vector up = Vector::UNIT_Z;
   NewtonCollisionSupportVertex(collision,  &up.x, top);

   Vector bottom;
   Vector down = -up;
   NewtonCollisionSupportVertex(collision, &down.x, bottom);

   // calculate the horizontal dimensions
   Vector radiusVector1;
   Vector right = Vector::UNIT_X;
   NewtonCollisionSupportVertex(collision, &right.x, &radiusVector1.x);

   Vector radiusVector2;
   Vector forward = Vector::UNIT_Y;
   NewtonCollisionSupportVertex(collision, &up.x, &radiusVector2.x);

   // calculate the radius
   float r1 = fabs(radiusVector1.DotProduct(right));
   float r2 = fabs(radiusVector2.DotProduct(forward));
   float radius = (r1 > r2 ? r1 : r2);

   // generate the convex hull sensor
   const int SENSOR_SEGMENTS = 32;

   Vector sensor[SENSOR_SEGMENTS * 2];
   for (int i = 0; i < SENSOR_SEGMENTS; ++i)
   {
      float x;
      float y;

      x = cosf(2.0f * 3.14159265f * float(i) / float(SENSOR_SEGMENTS));
      y = sinf(2.0f * 3.14159265f * float(i) / float(SENSOR_SEGMENTS));

      x *= radius;
      y *= radius;

      sensor[i].x = x;   
      sensor[i].y = y;
      sensor[i].z = top.z;

      sensor[i + SENSOR_SEGMENTS].x = x;   
      sensor[i + SENSOR_SEGMENTS].y = y;
      sensor[i + SENSOR_SEGMENTS].z = bottom.z;
   }

   // create the newton collisions
   mSensor = NewtonCreateConvexHull(NewtonBodyGetWorld(mBody), SENSOR_SEGMENTS * 2, &sensor[0].x, sizeof(Vector), 0.0f, 0, NULL);
}

//--------------------------------------------------------------------------------
float CharacterController::ScaleInput(const Vector &moveInput)
{
   float max = fabs(moveInput.x);

   if (fabs(moveInput.y) > max)
      max = fabs(moveInput.y);

   //if (fabs(moveInput.z) > max)
   //   max = fabs(moveInput.z);

   if (max <= 0.0f)
      return 0;

   return max / moveInput.Length();
}

//--------------------------------------------------------------------------------
void CharacterController::SlideVelocity(Vector &velocity, const Vector &normal, float overBounce) const
{
   float backOff = velocity.DotProduct(normal);
   
   if (backOff < 0.0f)
      backOff *= overBounce;
   else
      backOff /= overBounce;

   velocity -= (normal * backOff);
}

//--------------------------------------------------------------------------------
void CharacterController::Accelerate(Vector &velocity, const Vector &desiredDir, float desiredSpeed, float acceleration, float time) const
{
   Vector accelerationVelocity(desiredDir);
   accelerationVelocity *= acceleration * desiredSpeed * time;

   Vector desiredVelocity(desiredDir);
   desiredVelocity *= desiredSpeed;

   for (int i = 0; i < 3; ++i)
   {
      if (accelerationVelocity[i] > 0)
      {
         // acceleration along axis in positive direction
         if (velocity[i] < desiredVelocity[i])
         {
            velocity[i] += accelerationVelocity[i];
            if (velocity[i] > desiredVelocity[i])
               velocity[i] = desiredVelocity[i];
         }
      }
      else
      {
         // acceleration along axis in negative direction
         if (velocity[i] > desiredVelocity[i])
         {
            velocity[i] += accelerationVelocity[i];
            if (velocity[i] < desiredVelocity[i])
               velocity[i] = desiredVelocity[i];
         }
      }
   }
}

//--------------------------------------------------------------------------------
void CharacterController::Friction(Vector &velocity, float friction, float time)
{
   Vector vector(velocity);

   // clear any vertical friction when walking along slopes
   if (mState == STATE_WALKING)
      vector -= mUp * vector.DotProduct(mUp);
   
   float speed = vector.Length();
   if (speed < (1.0f / 32.0f))
   {
      velocity.x = 0.0f;
      velocity.y = 0.0f;
      return;
   }

   float drop = 0.0f;

   // apply ground friction
   if (mState == STATE_WALKING)
   {
      float control = speed < (100.0f / 32.0f) ? (100.0f / 32.0f) : speed;
      drop += control * friction * time;
   }

   // scale the velocity
   float newSpeed = speed - drop;
   if (newSpeed < 0.0f)
      newSpeed = 0.0f;

   newSpeed /= speed;

   velocity *= newSpeed;
}

//--------------------------------------------------------------------------------
CharacterController::State CharacterController::DetermineCurrentState()
{
   // not on ground, we must be airbone
   if (mOnGround == false)
   {
      if (mState != STATE_AIRBORNE)
      {
         Log::Info("Falling");
         Log::Info("Position:\t%f, %f, %f", mPosition.x, mPosition.y, mPosition.z);
      }

      return STATE_AIRBORNE;
   }

   // check vertical velocity to check if we are kicking off from ground
   if ( (mVelocity.DotProduct(mUp) > 0.0f) && (mVelocity.DotProduct(mGroundNormal) > 3.2f) )
   {
      mOnGround = false; // TODO: this works, but not sure if it should be moved else where

      Log::Info("Kick off!");
      return STATE_AIRBORNE;
   }

   // force airborne state if slope is too steep
   if (mGroundNormal.DotProduct(mUp) < mMaxSlope)
   {
      if (mState != STATE_AIRBORNE)
      {
         Log::Info("Too steep");
         Log::Info("Normal:\t%f, %f, %f", mGroundNormal.x, mGroundNormal.y, mGroundNormal.z);
         Log::Info("Position:\t%f, %f, %f", mPosition.x, mPosition.y, mPosition.z);
      }

      return STATE_AIRBORNE;
   }

   // made it this far, controller must be walking
   if (mState == STATE_AIRBORNE)
   {
      Log::Info("Landed");
      Log::Info("Normal:\t%f, %f, %f", mGroundNormal.x, mGroundNormal.y, mGroundNormal.z);
      Log::Info("Position:\t%f, %f, %f", mPosition.x, mPosition.y, mPosition.z);
   }

   return STATE_WALKING;
}

//--------------------------------------------------------------------------------
void CharacterController::AirMove(Quaternion direction, float time)
{
   // ensure state matches movement
   mState = STATE_AIRBORNE;

   Vector forward;
   Vector right;
   Vector up;
   direction.ToAxes(forward, right, up);

   // calculate the desired velocity
   Vector desiredVelocity;
   desiredVelocity  = forward * mMoveInput.x;
   desiredVelocity += right   * mMoveInput.y;

   // clear any virtical movement
   mMoveInput.z = 0.0f;

   // calculate the direction and speed ensuring we don't exceed maximum input speed
   Vector desiredDirection(desiredVelocity);
   float desiredSpeed = desiredDirection.Normalise();
   desiredSpeed *= ScaleInput(mMoveInput);

   // apply friction and acceleration
   Accelerate(mVelocity, desiredDirection, desiredSpeed, mMaxAcceleration * mAirControl, time);

   // slide along any steep ground plane
   if (mOnGround == true)
      SlideVelocity(mVelocity, mGroundNormal);

   SlideMove(mPosition, mVelocity, true, time);
}

//--------------------------------------------------------------------------------
void CharacterController::WalkMove(Quaternion direction, float time)
{
   // check for jumping
   if (mMoveInput.z > 0.0f)
   {
      mOnGround = false;
      mVelocity += mUp * mMoveInput.z;// * time; // is this needed?

      Log::Info("Jumping");
      Log::Info("Normal:\t%f, %f, %f", mGroundNormal.x, mGroundNormal.y, mGroundNormal.z);
      Log::Info("Position:\t%f, %f, %f", mPosition.x, mPosition.y, mPosition.z);

      AirMove(direction, time);
      return;
   }

   // zero any vertical velocity if we have just landed
   if (mState == STATE_AIRBORNE)
      mVelocity -= mUp * mVelocity.DotProduct(mUp);

   // ensure state matches movement
   mState = STATE_WALKING;

   Vector forward;
   Vector right;
   Vector up;
   direction.ToAxes(forward, right, up);

   // project the forward and right directions onto the ground plane
   SlideVelocity(forward, mGroundNormal);
   SlideVelocity(right, mGroundNormal);
   
   forward.Normalise();
   right.Normalise();

   // calculate the desired velocity
   Vector desiredVelocity;
   desiredVelocity  = forward * mMoveInput.x;
   desiredVelocity += right   * mMoveInput.y;

   // calculate the direction and speed ensuring we don't exceed maximum input speed
   Vector desiredDirection(desiredVelocity);
   float desiredSpeed = desiredDirection.Normalise();
   desiredSpeed *= ScaleInput(mMoveInput);

   // apply friction and acceleration
   Friction(mVelocity, /*6.0f*/6.0f, time);  // TODO: adjust friction according to ground contact
   Accelerate(mVelocity, desiredDirection, desiredSpeed, mMaxAcceleration, time);

   // align velocity with ground ensuring we don't loose/gain speed
   float speed = mVelocity.Length();
   SlideVelocity(mVelocity, mGroundNormal);

   mVelocity.Normalise();
   mVelocity *= speed;

   // perform the actual move
   //SlideMove(mPosition, mVelocity, false, time);
   StepSlideMove(mPosition, mVelocity, false, time);
}

//--------------------------------------------------------------------------------
unsigned CharacterController::ConvexCastPrefilter(const NewtonBody* body, const NewtonCollision* collision, void* userData)
{
   const NewtonBody *ignore = static_cast<const NewtonBody *>(userData);

   // ignore controller
   if (body == ignore)
      return 0;

   // TODO: move this to a virtual function?
   BodyComponent *component = static_cast<BodyComponent*>(NewtonBodyGetUserData(body));
   if ( (component != NULL) && (component->GetCollisionMode() != BodyComponent::COLLIDE_SOLID) )
      return 0;

   return 1;
}

//--------------------------------------------------------------------------------
bool CharacterController::ConvexCast(const Vector &origin, const NewtonCollision *collision, Vector &movement, float &hitParam, NewtonWorldConvexCastReturnInfo &impactInfo) const
{
   const int maxContacts = 16;
   NewtonWorldConvexCastReturnInfo info[maxContacts];

   // calculate the transformation matrix for the origin
   Matrix transform = Matrix::IDENTITY;
   mOrientation.ToRotationMatrix(transform);
   transform(0, 3) = origin.x;
   transform(1, 3) = origin.y;
   transform(2, 3) = origin.z;

   // calculate destination from origin and movement
   Vector destination = origin + movement;

   // perform the convex cast
   int contacts = NewtonWorldConvexCast(NewtonBodyGetWorld(mBody), transform, &destination.x, collision, &hitParam, mBody, &ConvexCastPrefilter, &info[0], maxContacts, 0);
   
   if (contacts > 0)
   {
      // calculate desired normal
      Vector desiredNormal = -movement;
      desiredNormal.Normalise();

      // calculate the actual movement and destination
      movement *= hitParam;
      destination = origin + movement;

      // ensure the first normal is directed towards the cast object
      Plane p(info[0].m_normal, info[0].m_point);
      if (p.WhichSide(destination) == Plane::BACK_SIDE)
      {
         info[0].m_normal[0] *= -1;
         info[0].m_normal[1] *= -1;
         info[0].m_normal[2] *= -1;
      }

      // calculate score for the first value
      int bestContact = 0;
      float bestValue = desiredNormal.DotProduct(info[0].m_normal);

      for (int i = 1; i < contacts; ++i)
      {
         // ensure normal is directed towards the cast object
         Plane p(info[i].m_normal, info[i].m_point);
         if (p.WhichSide(destination) == Plane::BACK_SIDE)
         {
            info[i].m_normal[0] *= -1;
            info[i].m_normal[1] *= -1;
            info[i].m_normal[2] *= -1;
         }

         // maximise the score based on normal closest to the disired normal
         float value = desiredNormal.DotProduct(info[i].m_normal);
         if (value > bestValue)
         {
            bestContact = i;
            bestValue = value;
         }
      }

      // return the bset normal
      impactInfo = info[bestContact];
      //impactNormal = info[bestContact].m_normal;
      //impactBody = info[bestContact].m_hitBody;

      return true;
   }
   
   hitParam = 1.0f;
   return false;
}

//--------------------------------------------------------------------------------
bool CharacterController::SlideMove(Vector &position, Vector &velocity, bool gravity, float &time)
{
   const int MAX_SLIDE_NORMALS = 5;
   Vector slideNormal[MAX_SLIDE_NORMALS];
   int normalCount = 0;

   Vector endVelocity = Vector::ZERO;
   if (gravity == true)
   {
      // calculate the gravity
      endVelocity = velocity;
      endVelocity += mGravity * time;
      velocity = endVelocity;

      // not sure about this, why trace based on average z height?
      //velocity = (velocity + endVelocity) * 0.5f;

/*
      // calculate the gravity
      endVelocity = velocity;
      endVelocity.z += -9.8f * time;
      velocity.z = endVelocity.z;

      // not sure about this, why trace based on average z height?
      //velocity.z = (velocity.z + endVelocity.z) * 0.5f;
*/
      
      // slide along any ground plane
      if (mOnGround == true)
         SlideVelocity(velocity, mGroundNormal);
   }

   float remainingTime = time;

    // never turn against the ground plane
    if (mOnGround == true)
      slideNormal[normalCount++] = mGroundNormal;

   // never turn against the original velocity
   slideNormal[normalCount] = velocity;
   slideNormal[normalCount].Normalise();
   ++normalCount;

   int bump;
   for (bump = 0; bump < 4; ++bump)
   {
      // calculate the required movement
      Vector movement = velocity * remainingTime;

      // check if we impact anything based on velocity
      float hitParam;
      NewtonWorldConvexCastReturnInfo impactInfo;
      if (ConvexCast(position, mSensor, movement, hitParam, impactInfo) == false)
      {
         // moved the entire distance
         position += movement;
         break;
      }
      Vector impactNormal(impactInfo.m_normal);

      if (hitParam > 0.0f)
      {
         // calculate the remaining time
         position += movement;
         remainingTime -= remainingTime * hitParam;
      }

      // TODO: add contact event
      OnApplyContact(position, velocity, impactInfo);

      // too many impacts, shouldn't happend but stop the entity just in case
      if (normalCount >= MAX_SLIDE_NORMALS)
      {
         velocity = Vector::ZERO;
         return true;
      }

      // if this is the same normal we hit before, nudge velocity out along it.  This solves some epsilon issues with non-axial normals
      bool nudged = false;
      for (int n = 0; n < normalCount; ++n)
      {
         if (impactNormal.DotProduct(slideNormal[n]) > 0.99f) // > 0.99f
         {
            velocity += (impactNormal / 32.0f);
            nudged = true;
            Log::Info("Nudged!");
            break;
         }
      }

      // ignore this impact if we just nudged the velocity
      if (nudged == true)
         continue;

      slideNormal[normalCount++] = impactNormal;

      // modify velocity so it parallels all impacted normals
      for (int i = 0; i < normalCount; ++i)
      {
         float impact = velocity.DotProduct(slideNormal[i]);

         // check if movement interacts with normal
         if (impact >= 0.1f) // >= 0.1f
            continue;

         /* TODO: investigate if this is required or useful
         // see how hard we are hitting
         if (mImpactSpeed < -impact)
            mImpactSpeed = -into;
         */

         // slide along the plane
         Vector slideVelocity(velocity);
         SlideVelocity(slideVelocity, slideNormal[i]);

         Vector endSlideVelocity(endVelocity);
         SlideVelocity(endSlideVelocity, slideNormal[i]);

         for (int j = 0; j < normalCount; ++j)
         {
            // skip any already processed normals
            if (j == i) continue;

            // check if movement interacts with normal
            if (slideVelocity.DotProduct(slideNormal[j]) >= 0.1f) // >= 0.1f
               continue;

            // try to slide along the normal
            SlideVelocity(slideVelocity, slideNormal[j]);
            SlideVelocity(endSlideVelocity, slideNormal[j]);

            // ensure it doesn't intersect with the first normal
            if (slideVelocity.DotProduct(slideNormal[i]) >= 0.0f) // >= 0f
               continue;

            // slide the original velocity along the crease
            Vector direction = slideNormal[i].CrossProduct(slideNormal[j]);
            direction.Normalise();

            slideVelocity = direction;
            slideVelocity *= direction.DotProduct(velocity);

            endSlideVelocity = direction;
            endSlideVelocity *= direction.DotProduct(endVelocity);

            // see if there is a third intersecting normal
            for (int k = 0; k < normalCount; ++k)
            {
               // skip any already processed normals
               if ( (k == i) || (k == j) ) continue;

               // check if movement interacts with normal
               if (slideVelocity.DotProduct(slideNormal[k]) >= 0.1f) // >= 0.1f
                  continue;

               // stop dead at a tripple plane interaction
               velocity = Vector::ZERO;
               return true;
            }
         }

         // try another move
         velocity = slideVelocity;
         endVelocity = endSlideVelocity;
         break;
      }
   }

   if (gravity)
      velocity = endVelocity;

   return bump == 0;
}

//--------------------------------------------------------------------------------
void CharacterController::StepSlideMove(Vector &position, Vector &velocity, bool gravity, float time)
{
   // save the initial position and velocity
   Vector startPosition(position);
   Vector startVelocity(velocity);

   if (SlideMove(position, velocity, gravity, time) == true)
   {
      // travelled full distance
      return;
   }

   Vector movement;
   float hitParam;
   NewtonWorldConvexCastReturnInfo impactInfo;
   bool foundGround;
   
   // never step up when we have up velocity
   movement = mUp;
   movement *= -mStepHeight;

   foundGround = ConvexCast(startPosition, mSensor, movement, hitParam, impactInfo);
   Vector impactNormal(impactInfo.m_normal);
   if (velocity.DotProduct(mUp) > 0)
   {
      if ( (foundGround == false) || (impactNormal.DotProduct(mUp) < mMaxSlope) )
         return;
   }

   // test if we can move the controller a step higher
   movement = mUp;
   movement *= mStepHeight;
   foundGround = ConvexCast(startPosition, mSensor, movement, hitParam, impactInfo);
   
   // try to move from new position
   position = startPosition + movement;
   velocity = startVelocity;
   SlideMove(position, velocity, gravity, time);

   // push down the final amount
   movement *= -1;
   foundGround = ConvexCast(position, mSensor, movement, hitParam, impactInfo);
   impactNormal = impactInfo.m_normal;
   
   position += movement;
   if (foundGround == false)
      SlideVelocity(velocity, impactNormal);
}

//--------------------------------------------------------------------------------
void CharacterController::OnApplyContact(Vector &position, Vector &velocity, NewtonWorldConvexCastReturnInfo &impactInfo)
{
   BodyComponent *component = static_cast<BodyComponent*>(NewtonBodyGetUserData(impactInfo.m_hitBody));
   if (component != NULL)
   {
      Vector impactNormal(impactInfo.m_normalOnHitPoint);
      Vector impactPoint(impactInfo.m_point);

      Vector force = velocity * 80.0f * 0.001f; // f = mass * velocity * time
   
      Vector relative = impactPoint - component->GetOwner()->GetComponent<TransformComponent>()->GetPosition();
      Vector torque = impactPoint.CrossProduct(force);

      component->AddForce(force * 10000.0f);
      component->AddTorque(torque * 10.0f);
   }
}


[Julio Jerez]

Hi Julio,
As for the controller algorithm, I got it from looking at the quake 3 source code. I've also looked at q1 and q2 code and it's essentially the same thing. The algorithm is called SlideMove and it works by performing a convex cast from the current position to the expected position at the end of the frame. If a collision if found, the impact normal is checked against all previous impact normals and a new velocity direction is calculated. The new velocity is calculated so the player will "slide" along all existing normals, the last impact normal is saved and this process is repeated until the end of the frame or the player hits three intersecting normals and stops. Initially, the saved normal list contains just the ground normal and a "fake" normal to prevent backwards movement.
[/code]

oh I see, that is an standard iterative solution, basically in calculates the the preject velocuty and move to the position canceling the reflection velocity and then try again.
That method works for the most part as long as the player only collide with coner that do not form obtuse angles.
if the player hits a corner with an optuse angle then it it fail with terrible jiter because you afte the secund bounce the legal velocity is negative with respect to teh firt normal.
so so the player moves legally backward even the restition is zero.

The Newton player controller uses a complementary solver to solve the problem. Basically the first move calculate the reflection velocity. andt it saves the normal.
the secund move get the new normal and solve the new relfextion velocity for both normals directions using a complemtary system of equation.
since the condition of that complementary solver states that the prejection of reflected velocity can not be negative for all directions.
then the solution is ether positive velocity when the corner angles is 90% or larger or zero whne corners from 90 degree angle or less.

when you say this:

The new velocity is calculated so the player will "slide" along all existing normals, the last impact normal is saved and this process is repeated until the end of the frame or the player hits three intersecting normals and stops

if the algorithm is not using a complementari system or equations then it fail. but maybe they are using one.
It is funny because for almost 15 years I have being making controller using that principle for comercial games, and I never new that games like quake migh be using that.

[bmsq]

I haven't fully tested Obtuse angles in my game or Quake, but they shouldn't be a problem as the second bounce velocity will be calculated from the second normal AND the first. This should result in the player sliding along the seem (see second last function: "SlideMove", the section is commented with "slide original velocity along the crease).

I'll have to take another look at your controller Julio. I tried to understand it previously but couldn't visualize it without and basic concept of how it's works. This was the only reason I didn't use yours as a base and modify for my own purpose.

[Julio Jerez]

in teh newton player controller teh funtion that does what I mention is
dVector CustomPlayerController::CalculateVelocity (const dVector& veloc, dFloat timestep, const dVector& upDir, dFloat elevation, int threadIndex) const

I when over your code, and for what I can see it does no really solve the system as a complementaty system of equation,
I does mention find the velocity tangent to all normal, but that is not possible with obtuses angles, I am afraid you will see it failing in those cases.

if in the future face that problem, then you know what the secrect to teh solution is,

I beleive that weakness does not show in those contraoller because it si very rare that a level has a obtuse corners when the are made of flat walls,
but as lever geomtery becomes more detail those issuse show very frequenlly.

[bmsq]

I've updated my code to use Newton 2.33 and can confirm that the flipped normal problem is no longer occurring

Last time I looked at your player controller (possibly a v2.0 beta), I found it quite confusing and couldn't understand how it worked. I'm not sure if you have improved the design or whether I've just learnt a lot from writing my own, but I think I understand how this latest version works (I'm still trying to understand the complementary solver algorithm though). I really like how "Quake like" my current controller feels, but I'm very tempted to see if I can use your calculate velocity algorithm to get the best of both worlds.

Thanks for you help!