C/C++教程

阅读记录How to Create a Custom 2D Physics Engine - Rangy Gaul(2)

本文主要是介绍阅读记录How to Create a Custom 2D Physics Engine - Rangy Gaul(2),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • Friction, Scene and Jump Table
    • Friction
    • Coulomb's Law库伦定律
    • 静摩擦和动摩擦
    • Scene
    • JumpTable 碰撞查询跳转表
  • Oriented Rigid Bodies
    • Orientation Math
    • Cross Product叉积
    • 转矩和角速度
    • Inertia惯性
    • 积分
    • Transforming to a Basis
    • Collision Detection and Manifold Generation
      • 支撑点
      • 寻找分离轴
    • 碰撞解决
  • 引用

github仓库:https://github.com/tutsplus/ImpulseEngine

可以结合代码看文章

Friction, Scene and Jump Table

Friction

摩擦力是碰撞解决的一部分。摩擦力总是作用在物体上,作用力的方向与物体所要运动的方向相反。

一般来说摩擦力是很复杂的,取决于接触的两个物体,我们为了对他进行建模,制造了许多假设和近似。

体现在数学上,通常类似于“摩擦可以用单个矢量近似”——类似于刚体动力学通过假设具有均匀密度的物体不能变形来模拟真实生活中的相互作用。

once the objects land on the solid platform, they just sort of all press away and drift off the edges of the screen. This is due to a lack of friction simulation.一旦物体落在光滑的平台上,它们就会被压走,并从屏幕边缘漂移。这是由于缺乏摩擦模拟。

冲量方法中,j表示了分离两个相互渗透的物体需要的冲量的大小。可以表示为jnormal 或者jN。

摩擦力的大小一般表示为jtangent或者jT。

摩擦力也会被当做冲量处理,直接改变速度,方向为碰撞的负切线的方向。

2d下,直接像处理普通冲量那样,然后把n换为t

\[j = \frac{-(1 + e)((V^B - V^A) \cdot t)}{\frac{1}{mass^A} + \frac{1}{mass^B}} \]

在这个方程中只有一个n的实例被替换为t,但是一旦引入旋转,除了方程的分子中的单个实例之外,还必须替换更多的实例。

切向量是一个垂直于碰撞法线的向量,指向相对速度方向(看似夹角小于90度)

Vectors of various types within the timeframe of a collision of rigid bodies.
Vectors of various types within the timeframe of a collision of rigid bodies.

摩擦将是一个与切向量相对的矢量。这意味着可以直接计算施加摩擦的方向,因为法向量是在碰撞检测中找到的。

那我们求一下切向量的

\[V^R = V^B-V^A \\ t = V^R- (V^R \cdot n)*n \]

然后我们就可以计算出jT

意识到摩擦矢量指向与切矢量相反的方向,因此,当我们点乘切矢量的相对速度时,我们必须加上一个负号来解出切矢量的相对速度。这个负号使切线速度翻转突然指向摩擦力应该近似为的方向。

// Re-calculate relative velocity after normal impulse
// is applied (impulse from first article, this code comes
// directly thereafter in the same resolve function)
Vec2 rv = VB - VA
 
// Solve for the tangent vector
Vec2 tangent = rv - Dot( rv, normal ) * normal
t = tangent.Normalize( )
 
// Solve for magnitude to apply along the friction vector
float jt = -Dot( rv, t ) //我认为t就是tangent标准化后的
jt = jt / (1 / MassA + 1 / MassB) //这里简化了,没有-(1+e)

( 这段推导看的很迷惑)

Coulomb's Law库伦定律

摩擦力定律,关键在于库仑定律是一个不等式。

\[F_f <= \mu F_n \]

摩擦力总是小于或等于法向力乘以某个常数μ(其值取决于物体的材料)。

法向力就是原来的j大小乘以碰撞法向力。

所以如果我们解出的jT小于μ乘以法向力,那么我们可以用jT大小作为摩擦力。如果不是,那么我们必须用法向力乘以μ。这种“其他”情况是一种将摩擦压在某个最大值以下的形式。

库仑定律的全部意义就在于完成这个夹紧过程。这种夹紧结果是摩擦模拟中最困难的部分,大部分程序都没做好这一步。

下一个代码块是前一个代码示例,完成了夹紧过程和摩擦脉冲应用:

// Re-calculate relative velocity after normal impulse
// is applied (impulse from first article, this code comes
// directly thereafter in the same resolve function)
Vec2 rv = VB - VA
 
// Solve for the tangent vector
Vec2 tangent = rv - Dot( rv, normal ) * normal
t = tangent.Normalize( )
 
// Solve for magnitude to apply along the friction vector
float jt = -Dot( rv, t )
jt = jt / (1 / MassA + 1 / MassB)
 
// PythagoreanSolve = A^2 + B^2 = C^2, solving for C given A and B
// Use to approximate mu given friction coefficients of each body
float mu = PythagoreanSolve( A->staticFriction, B->staticFriction )
 
// Clamp magnitude of friction and create impulse vector
Vec2 frictionImpulse
if(abs( jt ) < j * mu)
  frictionImpulse = jt * t
else
{
  dynamicFriction = PythagoreanSolve( A->dynamicFriction, B->dynamicFriction )
  frictionImpulse = -j * t * dynamicFriction
}
 
// Apply
A->velocity -= (1 / A->mass) * frictionImpulse
B->velocity += (1 / B->mass) * frictionImpulse

y有些摩擦系数的求解:

\[Friction = \sqrt{Friction_A^2+Friction_B^2} \]

但实际上这两个值的平均值完全可以避免使用平方根。实际上,任何形式的选取摩擦系数都是可行的;这正是我所喜欢的。另一种选择是使用查找表,其中每个主体的类型用作2D表的索引。

由于j总是正的,我们取摩擦矢量的时候,乘了切向量后要进行反向

静摩擦和动摩擦

在上面的代码段里,动静摩擦的概念直接被引入到库伦定律实现里了。

摩擦会发生一些有趣的事情:它需要一种“激活能量”,以便物体在完全静止时开始运动。在现实生活中,当两个物体相互依赖时,需要相当大的能量来推动其中一个物体并使其运动。然而,一旦你让某些东西滑动(产生了相对运动),那么从那以后保持它滑动通常就更容易了。

他说需要的能量激活是取决于摩擦力微表面模型。。

Microscopic view of what causes energy of activation due to friction.
Microscopic view of what causes energy of activation due to friction.

表面之间的微小变形是造成摩擦的原因。物体之间就会产生微小的变形,相互关联。这些需要被打破或分开,以便物体相互滑动。

我们需要在引擎中建立模型。一个简单的解决办法是为每种材料提供两个摩擦值:一个用于静态,一个用于动态。

静摩擦是用来固定我们的jt量级的。如果解出的jt大小足够低(低于我们的阈值),那么我们可以假设物体处于静止状态,或者几乎处于静止状态,并将整个jt作为脉冲。另一方面,如果我们解出的jt高于阈值,则可以假设该物体已经打破了“激活能”,在这种情况下使用较低的摩擦冲量,用较小的摩擦系数和略有不同的冲量计算来表示。

Scene

Scene类充当包含物理模拟场景的所有内容的容器。它调用并使用任何广义阶段的结果,包含所有刚体,运行碰撞检查并调用分辨率。它还集成了所有活动对象。场景还会与用户交互(就像程序员使用物理引擎一样)。

class Scene
{
public:
  Scene( Vec2 gravity, real dt );
  ~Scene( );
 
  void SetGravity( Vec2 gravity )
  void SetDT( real dt )
 
  Body *CreateBody( ShapeInterface *shape, BodyDef def )
 
  // Inserts a body into the scene and initializes the body (computes mass).
  //void InsertBody( Body *body )
 
  // Deletes a body from the scene
  void RemoveBody( Body *body )
 
  // Updates the scene with a single timestep
  void Step( void )
 
  float GetDT( void )
  LinkedList *GetBodyList( void )
  Vec2 GetGravity( void )
  void QueryAABB( CallBackQuery cb, const AABB& aabb )
  void QueryPoint( CallBackQuery cb, const Point2& point )
 
private:
  float dt     // Timestep in seconds
  float inv_dt // Inverse timestep in sceonds
  LinkedList body_list
  uint32 body_count
  Vec2 gravity
  bool debug_draw
  BroadPhase broadphase
};

Scene类没有什么特别复杂的地方。这样做的目的是让用户能够轻松地添加和移除刚体。BodyDef是一种包含刚体所有信息的结构(类似UE4的bodySetup),可用于允许用户将值作为一种配置结构插入。

另一个重要的函数是Step()。这个函数执行单轮的碰撞检查、分辨率和集成。应该在本系列第二篇文章中概述的时间步进循环中调用它。

查询点或AABB涉及检查哪些对象实际与场景中的指针或AABB发生碰撞。这让游戏玩法相关逻辑更容易看到事物在世界中的位置。

JumpTable 碰撞查询跳转表

查询点或AABB涉及检查哪些对象实际与场景中的指针或AABB发生碰撞。这让游戏玩法相关逻辑更容易看到事物在世界中的位置。比如box和box之间判断碰撞显然可以调用简单的函数,多边形之间调用就复杂的多。

c++中,我知道有两种主要的方法:双重分派和2D跳转表。在我自己的测试中,我发现了2D跳转表更好用,所以我将详细介绍如何实现它。如果你计划使用C或c++以外的其他语言我相信可以构造一个函数或函子对象数组类似于一个函数指针表(这是另一个原因我选择了谈论跳表而不是其他选项更特定于c++)。

在C或c++中,跳转表是函数指针表。表示任意名称或常数的索引用于在表中建立索引并调用特定的函数。1D跳转表的用法如下:

enum Animal
{
  Rabbit
  Duck
  Lion
};
 
const void (*talk)( void )[] = {
  RabbitTalk,
  DuckTalk,
  LionTalk,
};
 
// Call a function from the table with 1D virtual dispatch
talk[Rabbit]( ) // calls the RabbitTalk function

这里的C++函数指针没看懂,大体上是传入枚举得到函数指针的意思。

下面是一些用于调用碰撞例程的2D跳转表的伪代码:

collisionCallbackArray = {
  AABBvsAABB
  AABBvsCircle
  CirclevsAABB
  CirclevsCircle
}
 
// Call a collsion routine for collision detection between A and B
// two colliders without knowing their exact collider type
// type can be of either AABB or Circle
collisionCallbackArray[A->type][B->type]( A, B )

每个碰撞器的实际类型可以用来索引到一个2D数组中,并选择一个sovler来解决碰撞。

然而,请注意,aabbvcircle和CirclevsAABB几乎是重复的。这是必要的!对于这两个函数中的一个,法线需要翻转,这是它们之间唯一的区别。这允许一致的冲突解决,不管要解决的对象组合是什么。

Oriented Rigid Bodies

Orientation Math

旋向有关的数学

把转矩和角加速度联系起来。一个二维的叉积的快速描述是必需的。

Cross Product叉积

与3D的叉乘不同,2D的叉乘返回的不是矢量,而是标量。

这个标量值实际上代表了沿着z轴的正交向量的大小,如果叉乘是在3D中进行的话。二维叉积只是三维叉积的简化版。

叉乘的顺序很重要本文将大量使用叉乘来将角速度转化为线速度。

// Two crossed vectors return a scalar
float CrossProduct( const Vec2& a, const Vec2& b )
{
  return a.x * b.y - a.y * b.x;
}
 
// More exotic (but necessary) forms of the cross product
// with a vector a and scalar s, both returning a vector
Vec2 CrossProduct( const Vec2& a, float s )
{
  return Vec2( s * a.y, -s * a.x );
}
 
Vec2 CrossProduct( float s, const Vec2& a )
{
  return Vec2( -s * a.y, s * a.x );
}

转矩和角速度

从前面的文章中我们都应该知道,这个方程表示作用在物体上的力与该物体的质量和加速度之间的关系。这里有一个关于旋转的类比:

这里看的数学好有问题,晚点查证一下

线速度是刚体的重心的速度。在之前的文章中,所有的物体都没有转动分量,所以COM的线速度对于物体上所有点的速度是相同的。

核心是 力矩让物体转动,力矩产生角加速度,L是角动量,I是转动惯量,a是角加速度,t是合力力矩

Inertia惯性

转动惯量,影响转动难易程度的因子,和质量在线速度计算的地位类似。越大越难转动起来

我们就可以将物体的惯性以质量的格式存储在体内。明智的做法是存储这个惯性值的倒数,注意不要进行除零运算。

积分

每个刚体需要更多的场来存储旋转信息。下面是一个用于保存额外数据的结构的快速示例:

struct RigidBody
{
  Shape *shape
 
  // Linear components
  Vec2 position
  Vec2 velocity
  float acceleration
 
  // Angular components
  float orientation // radians
  float angularVelocity
  float torque
};

物体的角速度和方向的积分与速度和加速度的积分非常相似。

const Vec2 gravity( 0, -10.0f )
velocity += (force * 1.0f / mass) + gravity * dt
angularVelocity += torque * (1.0f / momentOfInertia) * dt
position += velocity * dt
orient += angularVelocity * dt

方向应该存储为一个单一的弧度值,如上所示,尽管对于某些形状,使用一个小的旋转矩阵可能是更好的选择

一个很好的例子就是定向包围盒(OBB)。OBB由宽度范围和高度范围组成,两者都可以用向量表示。这两个扩展向量可以用一个2乘2的旋转矩阵来表示OBB的轴。

struct Mat22
{
  union
  {
    struct
    {
      float m00, m01
      float m10, m11;
    };
 
    struct
    {
      Vec2 xCol;
      Vec2 yCol;
    };
  };
};

2x2的矩阵类

些有用的运算包括:从角度构造,从列向量构造,转置,与Vec2相乘,与另一个Mat22相乘,绝对值。最后一个有用的函数是能够从向量中检索x或y列。列函数看起来像这样:

Mat22 m( PI / 2.0f );
Vec2 r = m.ColX( ); // retrieve the x axis column

可以快速获得旋转矩阵的旋转轴

把两个正交的向量作为旋转矩阵的两列可以得到一个旋转后的坐标空间,构成旋转矩阵

构造函数:

Mat22::Mat22( const Vec2& x, const Vec2& y )
{
  m00 = x.x;
  m01 = x.y;
  m01 = y.x;
  m11 = y.y;
}
 
// or
 
Mat22::Mat22( const Vec2& x, const Vec2& y )
{
  xCol = x;
  yCol = y;
}

从一个向量和一个角度构建旋转矩阵:

Mat2( real radians )
{
  real c = std::cos( radians );
  real s = std::sin( radians );
 
  m00 = c; m01 = -s;
  m10 = s; m11 =  c;
}
 
// Rotate a vector
const Vec2 operator*( const Vec2& rhs ) const
{
  return Vec2( m00 * rhs.x + m01 * rhs.y, m10 * rhs.x + m11 * rhs.y );
}

后面给了一个旋转矩阵推导

Transforming to a Basis

理解模型和世界空间之间的区别是很重要的。模型空间是物理形状的局部坐标系。原点在质点处,坐标系统的方向与形状本身的轴对齐。

为了将一个形状从模型空间转换到世界空间,它必须旋转和平移。

我们定义旋转必须首先发生,因为旋转总是围绕原点进行的。由于对象在模型空间(原点在COM),旋转将围绕形状的COM旋转。旋转矩阵的名称为u。

一旦一个物体进入世界空间,它就可以通过反变换转换到一个完全不同的物体的模型空间。逆旋转和逆平移是这样做的。这就是在碰撞检测过程中简化了多少数学运算!

Inverse transformation from world space to model space of the red polygon.Inverse transformation (left to right) from world space to model space of the red polygon.

图看不太懂,大体上想表达把物体转换为一个物体的模型空间进行碰撞检测会更为简单,转换完之后就变成AABB和OBB的碰撞检测了

在大多数示例源代码中,顶点由于各种原因不断地从模型转换到世界,再转换回模型。为了理解示例碰撞检测代码,您应该清楚地理解这意味着什么。

Collision Detection and Manifold Generation

多边形和多边形

让我们从本系列文章中最复杂的碰撞检测例程开始。在我看来,检查两个多边形之间的碰撞最好使用分离轴定理(SAT)。

However, instead of projecting each polygon's extents onto each other, there is a slightly newer and more efficient method, as outlined by Dirk Gregorius in his 2013 GDC Lecture (slides available here for free).

然而,与将每个多边形的范围投影到彼此上不同,还有一种稍微更新和更有效的方法,正如Dirk Gregorius在2013年GDC演讲中所概述的。

支撑点

Support Point 支撑点的概念很重要

多边形的支撑点是沿着给定方向最远的顶点。如果两个顶点在给定的方向上有相等的距离,选哪个都可以。

为了计算支撑点,必须用点积来找出沿给定方向的有符号距离。因为这非常简单,所以我将在本文中展示一个快速示例:

// The extreme point along a direction within a polygon
Vec2 GetSupport( const Vec2& dir )
{
  real bestProjection = -FLT_MAX;
  Vec2 bestVertex;
 
  for(uint32 i = 0; i < m_vertexCount; ++i)
  {
    Vec2 v = m_vertices[i];
    real projection = Dot( v, dir );
 
    if(projection > bestProjection)
    {
      bestVertex = v;
      bestProjection = projection;
    }
  }
 
  return bestVertex;
}

点积用于每个顶点。点积表示给定方向上的有符号距离,所以投影距离最大的顶点就是支撑点。该操作在示例引擎中给定多边形的模型空间中执行。

寻找分离轴

通过使用支持点的概念,分离轴的寻找在两个多边形之间进行(多边形A,多边形B)。这个搜索的想法是沿着多边形A的所有面进行循环,并在这个面的负法线方向上找到支撑点(在多边形B上找支撑点)

SupportPoints

在上面的图像中,显示了两个支撑点:每个物体上有一个支撑点。

大正方形的蓝色法线将对应于另一个矩形上的支撑点(右下角),作为沿着蓝色法线相反方向最远的顶点。

红色法线将用于寻找位于红色箭头末端的支撑点。

从每个支撑点到当前面的距离被记录成有符号数,把这些距离从大到小排序,渗透值的计算为:该面法线 点乘 顶点到支撑点的向量 ,我们要求得最大渗透值,若最大的渗透值还是正的就说明两物体不想交,反之则有相交

下面是来自示例源代码的一个示例函数,它使用GetSupport函数找到可能的最小渗透轴:

real FindAxisLeastPenetration( uint32 *faceIndex, PolygonShape *A, PolygonShape *B )
{
  real bestDistance = -FLT_MAX;
  uint32 bestIndex;
 
  for(uint32 i = 0; i < A->m_vertexCount; ++i)
  {
    // Retrieve a face normal from A
    Vec2 n = A->m_normals[i];
 
    // Retrieve support point from B along -n
    Vec2 s = B->GetSupport( -n );
 
    // Retrieve vertex on face from A, transform into
    // B's model space
    Vec2 v = A->m_vertices[i];
 
    // Compute penetration distance (in B's model space)
    real d = Dot( n, s - v );
 
    // Store greatest distance
    if(d > bestDistance)
    {
      bestDistance = d;
      bestIndex = i;
    }
  }
 
  *faceIndex = bestIndex;
  return bestDistance;
}

由于这个函数返回最大的穿透值,如果这个穿透是正的,这意味着两个形状没有重叠(负的穿透将意味着没有分离轴)。

计算d的点乘部分使用的是面的向量

这个函数需要被调用两次,AB交换调用。

需要识别事件面和参考面,并且需要将事件面裁剪到参考面的边平面上。这是一个相当重要的操作,Erin Catto (Box2D和暴雪目前使用的所有物理的创造者)制作了 some great slides covering this topic in detail.

这个剪切将产生两个潜在的接触点。参考面后面的所有接触点都可以视为接触点。

圆与多边形的碰撞程序比多边形与多边形的碰撞检测简单得多。首先,在多边形上最接近圆心的面以类似于使用前一节的支撑点的方式计算:通过在多边形的每个面法线上循环,并找到圆心到圆心的距离。

如果圆心在面的法线反方向,则可以生成接触信息并结束程序

在识别出最近的面之后,测试就变成了线段与圆的测试。线段有三个有趣的区域,叫做Voronoi区域。查看以下图表:

Voronoi regions of a line segment.

这图两边的黄色区域,线段没有延伸过来在黄色区域作为顶点触发碰撞,在蓝色区域则判定为边触发碰撞

直观上,根据圆心的位置可以得到不同的接触信息。假设圆心位于任意一个顶点区域。这意味着离圆心最近的点将是一个边顶点,碰撞法线将是从这个顶点到圆心的向量。

如果圆在面区域内,那么线段到圆心的最近点将是圆的中心投影到线段上点。碰撞法线就是面法线。

为了计算圆所在的Voronoi区域,我们使用两个顶点之间的点积。这个想法是创建一个假想的三角形,并测试由线段顶点构成的角的角度是否大于或小于90度。为线段的每个顶点创建一个三角形。

Projecting vector from edge vertex to circle center onto the edge.

边顶点到圆心进行一个在边方向上的投影

如果值大于90度,则表示已识别出边缘区域。如果两个三角形的边顶点的角都不大于90度,则圆的圆心需要投影到线段上以产生流形信息。如上图所示,如果从边顶点到圆心与边向量本身点乘的矢量为负,则圆所在的Voronoi区域为已知(处于上图的EdgeRegion)。

碰撞解决

把之前处理的摩擦力冲量公式中j计算调节旋转量得到

A more in-depth derivation of this equation can be found on Chris Hecker's site.关于这个方程的更深入的推导可以在Chris Hecker的网站上找到。

r是一个从物体的质点到接触点的向量

重要的是要认识到物体上一个给定点的速度是线速度+旋转线速度:

\[V' = V + \omega \cross r \]

添加了旋转项,冲量的Apply略有变化:

void Body::ApplyImpulse( const Vec2& impulse, const Vec2& contactVector )
{
  velocity += 1.0f / mass * impulse;
  angularVelocity += 1.0f / inertia * Cross( contactVector, impulse );
}

contactVector是什么方向的,质点到接触点的向量

本系列的最后一篇文章到此结束。到目前为止,已经涵盖了相当多的主题,包括基于冲量的碰撞处理、流形生成、摩擦和旋转,所有这些都是二维的。

引用

https://gamedevelopment.tutsplus.com/tutorials/how-to-create-a-custom-2d-physics-engine-friction-scene-and-jump-table--gamedev-7756

https://gamedevelopment.tutsplus.com/tutorials/how-to-create-a-custom-2d-physics-engine-oriented-rigid-bodies--gamedev-8032

这篇关于阅读记录How to Create a Custom 2D Physics Engine - Rangy Gaul(2)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!