VO/RVO

VO和RVO的原理本身理解起来比较简单的，就是根据两个圆形的相对半径，相对速度，相对位置，求出碰撞区域，然后将速度移出碰撞区域。VO是双方都是当作对方速度不变的情况下，各自都将速度完整的移出了会碰撞的速度域，因此会抖动，RVO则是双方都默认对方速度也会移一半，因此自身也只移一半。

VO的原理

RVO的原理与VO类似，VO通过求出一个速度向量u，让物体的速度加上向量u，来移出会碰撞的速度域，RVO只移一半就行，即物体的速度加上向量u/2

数学相关的判断

代码实现主要是解一些数学题

求碰撞速度域

比如，即是求点到一个圆的两个切线。

<code>//求point 到 以circleCenter为圆心半径radius的圆的切线

pair<Vec2, Vec2> GeometryMath::calculateTangetLines(Vec2 point, Vec2 circleCenter, float radius) {

//点到圆心的长度，上图红线

float distSq = circleCenter.getDistanceSq(point);

//len是点到切点的长度

float len = sqrt(distSq - radius * radius);

//上图盖住部分红线的绿线

Vec2 temp = circleCenter - point;

temp.normalize();

temp *= len;

//左右各旋转夹角，即为切线点

float cosA = len / sqrt(distSq);

float sinA = radius / sqrt(distSq);

//顺时针

float x1 = temp.x * cosA - temp.y * sinA;

float y1 = temp.x * sinA + temp.y * cosA;

//逆时针

float x2 = temp.x * cosA - temp.y * (-sinA);

float y2 = temp.x * (-sinA) + temp.y * cosA;

return make_pair(Vec2(x1, y1), Vec2(x2, y2));

}

判定是否碰撞

判定速度是否在碰撞域内，即判定速度点与在左切线的右边，并且在右切线的左边

// 点 c 在a到b向量的左边, 即∠abc 小于180°

bool GeometryMath::isInLeft(Vec2 a, Vec2 b, Vec2 c) {

float e = getVectorCross(a, b, c);

return getVectorCross(a, b, c) < 0;

}

// 点 c 在a到b向量的右边, 即∠abc 大于180°

bool GeometryMath::isInRight(Vec2 a, Vec2 b, Vec2 c) {

return getVectorCross(a, b, c) > 0;

}

// 点 c 与a到b向量共线, 即∠abc 等于180°

bool GeometryMath::isCollineation(Vec2 a, Vec2 b, Vec2 c) {

return getVectorCross(a, b, c) < 0.00001;

}

float GeometryMath::getVectorCross(Vec2 a, Vec2 b, Vec2 c) {

Vec2 vectorBA = a - b;

Vec2 vectorBC = c - b;

return vectorBA.cross(vectorBC);

}

bool isCollision;

bool isFirstLeft = GeometryMath::isInLeft(Vec2::ZERO, verts.second, verts.first);

if (isFirstLeft) {

isCollision = GeometryMath::isInLeft(Vec2::ZERO, verts.second, relativeVelocity) && GeometryMath::isInRight(Vec2::ZERO, verts.first, relativeVelocity);

}

else {

isCollision = GeometryMath::isInLeft(Vec2::ZERO, verts.first, relativeVelocity) && GeometryMath::isInRight(Vec2::ZERO, verts.second, relativeVelocity);

}

求速度转移向量u

选择更近的一条切线边，求出速度到切线上的垂直点，作为新的速度，两者相减即为u

向量a与单位向量n的点积，即为a在n方向的投影长度

Vec2 vert = relativeVelocity.getDistance(verts.first) < relativeVelocity.getDistance(verts.second) ? verts.first : verts.second;

//求切线的单位向量

Vec2 v2 = vert.getNormalized();

//速度在切线上的投影长度

float n = relativeVelocity.dot(v2);

Vec2 v = v2 * n;

Vec2 u = v - relativeVelocity;

VO的效果：

RVO的效果:

实际写代码中VO其实还有个问题，就是在当前帧求出了新的速度的话，如果在这一帧立刻更新位置的话，在非常近的情况下。是极有可能产生碰撞的。

因为VO抖动的问题就是，在第一帧，双方可能碰撞于是计算了新的速度相互错开(此时的新速度在下一帧计算VO是不会碰撞的)如果当前帧根据新速度更新位置不会产生碰撞。而到了第二帧，双方根据此时的速度计算不会碰撞，于是新速度调整回了最佳速度(调整回的新速度在下一帧计算VO是会产生碰撞的，所以之后会产生抖动)，而此时如果根据当前帧调整的最佳速度立刻更新位置，在非常近的情况下，是会直接产生碰撞的