游戏中的刚体碰撞分析

2024-5-11 ~ 2024-7-23 Margoo (0)

前言

本文提供了一种方法（Impulse Method）来处理游戏中几何体间的碰撞处理。主要思路为利用 SDF 与梯度求出反弹法线并计算动量。思路来自 GAMES103。本文针对其进行了更详细的讲解以及提供一个可编译的代码实现。

具体实现效果如下所示：

具体效果

前置知识

SDF（Signed distance function），有符号距离函数。是一个多元函数（具体几元取决于研究对象所处的维度），本文记作。其返回一个值，该值为点到目标几何体的最短距离。不同的几何体有不同的 SDF 函数。例如圆的 SDF 为。其中为的阶范数（无需过多关注范数的概念，在我们所讨论的仿射空间内，范数就是模长），为圆的半径。若则说明点在圆内；若则说明点在圆上；若则说明点在园外。本文不提供任何几何体的 SDF 函数推导过程，读者若有兴趣可自行查找相关资料。

偏导（Partial Derivative），偏导是多变量微积分中的一个基本概念。在单变量微积分中，我们经常用表示函数关于的导数。但是当函数所接受的参数大于一个时，例如，原本的表示导数的方法就失效了。偏导解决这个问题的思路其实就是“固定其他不变，只变一个”，或者说的更简单一点，其实读者可以将偏导理解为：，本文不注重数学，因此只简单介绍。若读者有相关问题只能烦请自行理解了。

梯度（Gradient），一般用拉普拉斯算子（）加函数名表示，如。在我们所讨论的范围内，有梯度，其中为函数所接受的输入元素数。梯度其实不等于向量，但此处为了读者方便，可以将梯度理解为一个向量，向量的每一个元素都是关于函数的偏导。

梯度示意图

Ⅰ、利用 SDF 判断物体碰撞

利用 SDF 有两个方法，一个是对物体边缘上的每个点都进行一次 SDF 计算。这并在性能上并不划算，这里我将提供一种更好的方法，尽管这种方法可能会失去一些普适性，但是带来的性能证明这是值得的。

我们先考虑两个圆的碰撞如下图所示：

两个圆还未相撞

当两个圆还没相撞时，我们能观察到两个圆心之间的距离满足。而又如下图，当两个圆已经发生了碰撞甚至重叠在一起时，如图 1.1。

图 1.1：两个圆已经发生了碰撞并重叠

我们可以观察到两个圆心之间的距离则满足。对应成 SDF 即为。因此，当时，两个圆就发生了碰撞。

圆形搞定了，我们再来看圆和线之间的相撞，如图 1.2。

图 1.2：点与线之间的碰撞

其实点与线之间的碰撞更为简单。只要即可。

有了上述基础上，我们就可以描述了圆形与任意几何体（圆弧除外）之间的碰撞了，而线与线之间的碰撞由于篇幅原因，本文不再介绍，读者可自行介绍，我也并没有在代码中实现线线碰撞的代码。

Ⅱ、碰撞后位置的修正

当两个物体碰撞以后，我们并不能确保物体的位置一定是在我们预期之中的，例如图 1.1 就是一个意外情况。由于速度过快导致两个物体出现了重叠。此时我们就需要修正物体的位置。现在我们关注如图 2.1 的情况。

图 2.1：一种重叠的情况

不难发现，我们所需要的位置修复就是将圆形沿着法线方向（）移动两个圆之间的距离，也就是。即。

这里特地说一下 SDF 的梯度在代码中如何求。对于圆形，我们可以直接求，即对求偏导。而对于直线的 SDF，其 SDF 函数并不是很好写成数学表达式，就算写出来了其偏导产物也非常恐怖（我并没有尝试去这么做，如果尝试了然后发现其形式很优雅欢迎你在评论区指正）。所以我们直接采用偏导的定义，即对 SDF 函数取一个很小的增量然后相减：

auto GradientSDF(const Vec &Point) -> Vec override {
	auto origin = SDF(Vec({Point.x[0], Point.x[1]}));
	return Vec({SDF(Vec({Point.x[0] + 0.0000000001, Point.x[1]})) - origin,
				SDF(Vec({Point.x[0], Point.x[1] + 0.0000000001})) - origin});
}

Ⅲ、碰撞后的速度修正

在进行速度的修正之前，我们应该确保一件事情：速度是需要修正的。什么意思呢，就是这个物体的速度可能已经在前几个 Tick 内被修正了，这种情况下我们就不需要在进行修正了。判断速度是否需要被修正的一个方法就是看其是否指向碰撞目标物体内，即比较与的大小。若，则说明速度指向物体内部。

对于速度的修复，我们先将速度沿法相法相正交分解：。然后分别进行速度更新，对于竖直方向的速度，有。其中为法线方向上的弹性系数，需要手动设置；为切方向上的摩擦系数。而切方向则需要我们去算出来。

根据阿蒙顿-库仑摩擦定律（），即“摩擦力与法向载荷成正比、摩擦因数与接触面积无关、摩擦因数与滑动速度无关、静摩擦因数大于动摩擦因数”。我们可以得到式。其中为平面摩擦系数，需要自行设定。然后代入整理解得。在实际程序中，我们可以直接取该不等式等号。为了防止出现超出我们所预期的范围，我们应该对其进行限制，即。

有了以上理论推导就可以开始实现代码了。

Ⅳ、代码实现

本代码实现取消了摩擦因数，默认动量不衰减。读者若有需要可以根据本文内容自行修改。

/*
 * Program Name 	: Rigid Body Collision Demo
 * Last Modify Date	: 2024/5/11
 * Author			: Margoo(1683691371@qq.com)
 * CPP Version		: >=C20
 */

#define _UNICODE
#define UNICODE

#include <array>
#include <cmath>
#include <ctime>
#include <format>
#include <graphics.h>
#include <vector>

typedef struct tagRECTF {
	double left;
	double top;
	double right;
	double bottom;
} RECTF, *PRECTF, NEAR *NPRECTF, FAR *LPRECTF;

// 2D Vector
class Vec final {
public:
	Vec() : x({0, 0}) {
	}
	Vec(std::array<double, 2> Init) : x(Init) {
	}

public:
	auto Length() noexcept -> double {
		return sqrt(pow(x[0], 2) + pow(x[1], 2));
	}
	auto Normalize() noexcept -> Vec {
		return (*this) / Length();
	}
	auto DotProduct(const Vec &Vector) noexcept -> double {
		return Vector.x[0] * x[0] + Vector.x[1] * x[1];
	}

public:
	auto operator*=(const Vec &Value) -> Vec & {
		for (auto position = size_t(0); position < 2; ++position) {
			x[position] *= Value.x[position];
		}

		return (*this);
	}
	auto operator/=(const Vec &Value) -> Vec & {
		for (auto position = size_t(0); position < 2; ++position) {
			x[position] /= Value.x[position];
		}

		return (*this);
	}
	auto operator+=(const Vec &Value) -> Vec & {
		for (auto position = size_t(0); position < 2; ++position) {
			x[position] += Value.x[position];
		}

		return (*this);
	}
	auto operator-=(const Vec &Value) -> Vec & {
		for (auto position = size_t(0); position < 2; ++position) {
			x[position] -= Value.x[position];
		}

		return (*this);
	}
	auto operator*=(const double &Value) -> Vec & {
		for (auto position = size_t(0); position < 2; ++position) {
			x[position] * Value;
		}

		return (*this);
	}
	auto operator/=(const double &Value) -> Vec & {
		for (auto position = size_t(0); position < 2; ++position) {
			x[position] / Value;
		}

		return (*this);
	}
	auto operator+=(const double &Value) -> Vec & {
		for (auto position = size_t(0); position < 2; ++position) {
			x[position] + Value;
		}

		return (*this);
	}
	auto operator-=(const double &Value) -> Vec & {
		for (auto position = size_t(0); position < 2; ++position) {
			x[position] - Value;
		}

		return (*this);
	}

public:
	friend auto operator/(const Vec &Left, const Vec &Right) -> Vec;
	friend auto operator/(const Vec &Left, const double &Right) -> Vec;
	friend auto operator*(const Vec &Left, const Vec &Right) -> Vec;
	friend auto operator*(const Vec &Left, const double &Right) -> Vec;
	friend auto operator+(const Vec &Left, const Vec &Right) -> Vec;
	friend auto operator+(const Vec &Left, const double &Right) -> Vec;
	friend auto operator-(const Vec &Left, const Vec &Right) -> Vec;
	friend auto operator-(const Vec &Left, const double &Right) -> Vec;

public:
	std::array<double, 2> x;
};

auto operator/(const Vec &Left, const Vec &Right) -> Vec {
	Vec result;
	for (auto position = size_t(0); position < 2; ++position) {
		result.x[position] = Left.x[position] / Right.x[position];
	}

	return result;
}
auto operator/(const Vec &Left, const double &Right) -> Vec {
	Vec result;
	for (auto position = size_t(0); position < 2; ++position) {
		result.x[position] = Left.x[position] / Right;
	}

	return result;
}
auto operator*(const Vec &Left, const Vec &Right) -> Vec {
	Vec result;
	for (auto position = size_t(0); position < 2; ++position) {
		result.x[position] = Left.x[position] * Right.x[position];
	}

	return result;
}
auto operator*(const Vec &Left, const double &Right) -> Vec {
	Vec result;
	for (auto position = size_t(0); position < 2; ++position) {
		result.x[position] = Left.x[position] * Right;
	}

	return result;
}
auto operator+(const Vec &Left, const Vec &Right) -> Vec {
	Vec result;
	for (auto position = size_t(0); position < 2; ++position) {
		result.x[position] = Left.x[position] + Right.x[position];
	}

	return result;
}
auto operator+(const Vec &Left, const double &Right) -> Vec {
	Vec result;
	for (auto position = size_t(0); position < 2; ++position) {
		result.x[position] = Left.x[position] + Right;
	}

	return result;
}
auto operator-(const Vec &Left, const Vec &Right) -> Vec {
	Vec result;
	for (auto position = size_t(0); position < 2; ++position) {
		result.x[position] = Left.x[position] - Right.x[position];
	}

	return result;
}
auto operator-(const Vec &Left, const double &Right) -> Vec {
	Vec result;
	for (auto position = size_t(0); position < 2; ++position) {
		result.x[position] = Left.x[position] - Right;
	}

	return result;
}

auto operator/(const double &Right, const Vec &Left) -> Vec {
	Vec result;
	for (auto position = size_t(0); position < 2; ++position) {
		result.x[position] = Right / Left.x[position];
	}

	return result;
}
auto operator*(const double &Right, const Vec &Left) -> Vec {
	Vec result;
	for (auto position = size_t(0); position < 2; ++position) {
		result.x[position] = Left.x[position] * Right;
	}

	return result;
}
auto operator+(const double &Right, const Vec &Left) -> Vec {
	Vec result;
	for (auto position = size_t(0); position < 2; ++position) {
		result.x[position] = Left.x[position] + Right;
	}

	return result;
}
auto operator-(const double &Right, const Vec &Left) -> Vec {
	Vec result;
	for (auto position = size_t(0); position < 2; ++position) {
		result.x[position] = Right - Left.x[position];
	}

	return result;
}

class Sprite {
public:
	Sprite() = default;

public:
	virtual auto Draw() -> void = 0;
	// Use SDF for collision judgement
	virtual auto SDF(const Vec &Point) -> double	  = 0;
	virtual auto GradientSDF(const Vec &Point) -> Vec = 0;
	virtual auto DealSDF(const double &SDF) -> double {
		return SDF;
	}
	virtual auto Particle() -> Vec						   = 0;
	virtual auto RelativeMove(const Vec &Position) -> void = 0;

public:
	auto Move(const double &X, const double &Y) -> void {
		auto width	= boundingBox.right - boundingBox.left;
		auto height = boundingBox.bottom - boundingBox.top;

		boundingBox = {X, Y, X + width, Y + height};
	}

public:
	bool  lock = true;
	RECTF boundingBox{};
	Vec	  velocity;
};
class RoundSprite : public Sprite {
public:
	explicit RoundSprite(const double &Radius) : radius(Radius), Sprite() {
		boundingBox = {0, 0, Radius * 2, Radius * 2};
	}

public:
	auto Draw() -> void override {
		setfillcolor(WHITE);
		solidcircle(boundingBox.left + radius, boundingBox.top + radius, radius);
	}
	auto SDF(const Vec &Point) -> double override {
		Vec centre({boundingBox.left + radius, boundingBox.top + radius});

		return (Point - centre).Length() - radius;
	}
	auto GradientSDF(const Vec &Point) -> Vec override {
		auto base = SDF(Point) + radius;
		Vec	 centre({boundingBox.left + radius, boundingBox.top + radius});
		return Vec({(Point.x[0] - centre.x[0]) / base, (Point.x[1] - centre.x[1]) / base});
	}
	auto DealSDF(const double &SDF) -> double override {
		return SDF - radius;
	}
	auto Particle() -> Vec override {
		return Vec({boundingBox.left + radius, boundingBox.top + radius});
	}
	auto RelativeMove(const Vec &Position) -> void override {
		Move(Position.x[0] - radius, Position.x[1] - radius);
	}

public:
	double radius;
};
class LineSprite : public Sprite {
public:
	explicit LineSprite(const Vec &Point1, const Vec &Point2) : point1(Point1), point2(Point2) {
		boundingBox = {Point1.x[0], Point1.x[1], Point2.x[0], Point2.x[1]};
	}

public:
	auto Draw() -> void override {
		setlinecolor(WHITE);
		setlinestyle(PS_SOLID, 1);
		line(point1.x[0], point1.x[1], point2.x[0], point2.x[1]);
	}
	auto SDF(const Vec &Point) -> double override {
		Vec	   ap = Point - point1;
		Vec	   ab = point2 - point1;
		double h  = ap.DotProduct(ab) / ab.DotProduct(ab);
		h		  = h >= 1.f ? 1.f : h;
		h		  = h <= 0.f ? 0.f : h;

		return (ap - h * ab).Length();
	}
	auto GradientSDF(const Vec &Point) -> Vec override {
		auto origin = SDF(Vec({Point.x[0], Point.x[1]}));
		return Vec({SDF(Vec({Point.x[0] + 0.0000000001, Point.x[1]})) - origin,
					SDF(Vec({Point.x[0], Point.x[1] + 0.0000000001})) - origin});
	}
	auto Particle() -> Vec override {
		return point1 + (point2 - point1) / 2;
	}
	auto RelativeMove(const Vec &Position) -> void override {
		auto width	= boundingBox.right - boundingBox.left;
		auto height = boundingBox.bottom - boundingBox.top;
		point1		= Position;
		point2		= point1 + Vec({width, height});
		Move(Position.x[0], Position.x[1]);
	}

public:
	Vec point1;
	Vec point2;
};

class SpriteManager {
public:
	SpriteManager() = default;

public:
	auto UpdateSprite() -> void {
		for (auto &sprite : spriteList) {
			if (!sprite->lock) {
				for (auto &other : spriteList) {
					if (&other == &sprite) {
						continue;
					}
					auto spritePoint = sprite->Particle();
					auto sdf		 = sprite->DealSDF(other->SDF(spritePoint));
					if (sdf <= 0.001) {
						// Normal vector
						auto normal		 = other->GradientSDF(spritePoint).Normalize();
						auto newPosition = spritePoint + normal * abs(sdf);
						// Fix the position
						sprite->RelativeMove(newPosition);

						// Fix the speed
						if (sprite->velocity.DotProduct(normal) < 0) {
							Vec NVelocity	 = sprite->velocity.DotProduct(normal) * normal;
							Vec TVelocity	 = sprite->velocity - NVelocity;
							Vec newNVelocity = (0.f - NVelocity);
							Vec newTVelocity = max(1.f - (NVelocity.Length() / TVelocity.Length()), 1.f) * TVelocity;
							sprite->velocity = newNVelocity + newTVelocity;
						}
					}
				}
			}
		}
		for (auto &sprite : spriteList) {
			auto newPosition =
				Vec({static_cast<double>(sprite->boundingBox.left), static_cast<double>(sprite->boundingBox.top)}) +
				sprite->velocity * timingTick;
			sprite->Move(newPosition.x[0], newPosition.x[1]);
		}

		cleardevice();

		for (auto &sprite : spriteList) {
			sprite->Draw();
		}
	}

public:
	double				  timingTick = 1.f;
	std::vector<Sprite *> spriteList;
};

int main() {
	initgraph(640, 480);

	SpriteManager manager;
	auto		  roundSprite1 = new RoundSprite(20.f);
	auto		  roundSprite2 = new RoundSprite(60.f);
	auto		  roundSprite3 = new RoundSprite(70.f);
	auto		  roundSprite4 = new RoundSprite(20.f);
	auto		  roundSprite5 = new RoundSprite(20.f);
	auto		  roundSprite6 = new RoundSprite(20.f);
	auto		  border1	   = new LineSprite(Vec({0, 0}), Vec({static_cast<double>(getwidth()), 0}));
	auto		  border2	   = new LineSprite(Vec({0, 0}), Vec({0, static_cast<double>(getheight())}));
	auto		  border3	   = new LineSprite(Vec({static_cast<double>(getwidth()), 0}),
												Vec({static_cast<double>(getwidth()), static_cast<double>(getheight())}));
	auto		  border4	   = new LineSprite(Vec({0, static_cast<double>(getheight())}),
												Vec({static_cast<double>(getwidth()), static_cast<double>(getheight())}));
	auto		  lineSprite   = new LineSprite(Vec({70, 390}), Vec({100, 190}));
	manager.spriteList.push_back(roundSprite1);
	manager.spriteList.push_back(lineSprite);
	manager.spriteList.push_back(border1);
	manager.spriteList.push_back(border2);
	manager.spriteList.push_back(border3);
	manager.spriteList.push_back(border4);
	manager.spriteList.push_back(roundSprite2);
	manager.spriteList.push_back(roundSprite3);
	manager.spriteList.push_back(roundSprite4);
	manager.spriteList.push_back(roundSprite5);
	manager.spriteList.push_back(roundSprite6);
	roundSprite2->Move(180.f, 80.f);
	roundSprite3->Move(380.f, 180.f);
	roundSprite4->Move(300.f, 120.f);
	roundSprite5->Move(400.f, 320.f);
	roundSprite1->Move(20.f, 20.f);
	roundSprite1->velocity.x = {1.5f, 0.6f};
	roundSprite4->velocity.x = {-1.7f, 1.3f};
	roundSprite5->velocity.x = {-1.5f, -2.3f};
	roundSprite6->velocity.x = {3.f, -2.3f};
	roundSprite4->lock		 = false;
	roundSprite1->lock		 = false;
	roundSprite5->lock		 = false;
	roundSprite6->lock		 = false;

	BeginBatchDraw();

	settextcolor(GREEN);

	auto fpsCount = int(0);
	auto fps	  = int(0);
	auto time	  = clock();
	while (true) {
		manager.UpdateSprite();

		outtextxy(0.f, 0.f, std::format(L"FPS : {}", fpsCount).c_str());

		if (clock() - time >= 1000) {
			fpsCount = fps;
			fps		 = 0;
			time	 = clock();
		}

		++fps;

		FlushBatchDraw();

		Sleep(2);
	}

	return 0;
}

前言

前置知识

Ⅰ、利用 SDF 判断物体碰撞

Ⅱ、碰撞后位置的修正

Ⅲ、碰撞后的速度修正

Ⅳ、代码实现

添加评论