OBB(Orientex Bounding Box)

2차원 obb

2차원 에서는 각각의 obb의 축(중심에서 각 변의 중점을 가리키는 단위벡터)를 기준으로 각각의 obb

백준 16135
https://www.acmicpc.net/problem/16135

#include <bits/stdc++.h>

using namespace std;

typedef struct Box {
	vector<pair<double, double>> box_point;
	vector<pair<int, int>> chk_point;
	pair<double, double> pos;
	pair<double, double> up;
	pair<double, double> right;
} Box;

vector<pair<double, double>> normals;

pair<double, double> normalized(pair<double, double> p) {
	double len = p.first * p.first + p.second * p.second;
	len = sqrt(len);
	return pair(p.first / len, p.second / len);
}

double dot(pair<double, double> &p1, pair<double, double> &p2) {
	return p1.first * p2.first + p1.second * p2.second;
}

int collision(Box &b1, Box &b2) {
	pair<double, double> b12 = pair(b1.pos.first - b2.pos.first, b1.pos.second - b2.pos.second);
	for (int i = 0; i < normals.size(); i++) {
		double target = abs(dot(b12, normals[i]));
		double total = abs(dot(b1.up, normals[i])) + abs(dot(b1.right, normals[i]));
		total += abs(dot(b2.up, normals[i])) + abs(dot(b2.right, normals[i]));
		if (target >= total)
			return 0;
	}
	return 1;
}

bool check(Box &b1, Box &b2) {
	pair<int, int> st;
	st = b1.chk_point[0];
	for (int i = 1; i < 4; i++) {
		if (st.first == b1.chk_point[i].first && st.second == b1.chk_point[i].second)
			return true;
		st = b1.chk_point[i];
	}
	st = b2.chk_point[0];
	for (int i = 1; i < 4; i++) {
		if (st.first == b2.chk_point[i].first && st.second == b2.chk_point[i].second)
			return true;
		st = b2.chk_point[i];
	}
	return false;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	Box box1, box2;
	for (int i = 0; i < 2; i++) {
		double x, y;
		for (int j = 0; j < 4; j++) {
			cin >> x >> y;
			if (i == 0) {
				box1.box_point.push_back(pair(x, y));
				box1.chk_point.push_back(pair(int(x), int(y)));
			}
			else {
				box2.box_point.push_back(pair(x, y));
				box2.chk_point.push_back(pair(int(x), int(y)));
			}
		}
		if (i == 0) {
			double upx = (box1.box_point[0].first + box1.box_point[1].first) / 2;
			double upy = (box1.box_point[0].second + box1.box_point[1].second) / 2;
			double rx = (box1.box_point[1].first + box1.box_point[2].first) / 2;
			double ry = (box1.box_point[1].second + box1.box_point[2].second) / 2;
			box1.pos = pair((box1.box_point[0].first + box1.box_point[2].first) / 2, (box1.box_point[0].second + box1.box_point[2].second) / 2);
			box1.up = pair(upx - box1.pos.first, upy - box1.pos.second);
			box1.right = pair(rx - box1.pos.first, ry - box1.pos.second);
		}
		else {
			double upx = (box2.box_point[0].first + box2.box_point[1].first) / 2;
			double upy = (box2.box_point[0].second + box2.box_point[1].second) / 2;
			double rx = (box2.box_point[1].first + box2.box_point[2].first) / 2;
			double ry = (box2.box_point[1].second + box2.box_point[2].second) / 2;
			box2.pos = pair((box2.box_point[0].first + box2.box_point[2].first) / 2, (box2.box_point[0].second + box2.box_point[2].second) / 2);
			box2.up = pair(upx - box2.pos.first, upy - box2.pos.second);
			box2.right = pair(rx - box2.pos.first, ry - box2.pos.second);
		}
	}
	if (check(box1, box2)) {
		cout << 0 << '\n';
		return 0;
	}
	normals.push_back(normalized(box1.up));
	normals.push_back(normalized(box1.right));
	normals.push_back(normalized(box2.up));
	normals.push_back(normalized(box2.right));
	int flag = collision(box1, box2);
	cout << flag << '\n';
}

3차원 obb

3차원에서의 충돌은 조금 복잡하다. 2차원에서는 각각의 obb의 축을 이용했지만 3차원 obb의 축만을 사용한다면
https://gamedev.stackexchange.com/questions/44500/how-many-and-which-axes-to-use-for-3d-obb-collision-with-sat/
아래 링크에서와 같은 경우 실제로 충돌하지 않았지만 충돌을 했다고 판별하는 결과가 나온다. 이를 해결하기 위해 각각의 obb 축을 조합으로 3 * 3 개의 분리 축을 추가하여 충돌여부를 검사해야 한다.

import { Mat4x4} from "../graphics/Mat4x4.js";

function subDir(dir1, dir2) {
    let ans = [];
    for (let i = 0; i < dir1.length; i++)
        ans.push(dir1[i] - dir2[i])
    return ans;
}

function dotDir(src, des) {
    let ans = 0;
    for (let i = 0; i < 3; i++)
        ans += src[i] * des[i];
    return ans;
}

function crossProduct(vec1, vec2) {
	let res = [0, 0, 0, 0];
	res[0] = vec1[1] * vec2[2] - vec1[2] * vec2[1];
	res[1] = vec1[2] * vec2[0] - vec1[0] * vec2[2];
	res[2] = vec1[0] * vec2[1] - vec1[1] * vec2[0];
	return res;
}

export class CollisionBox {
    constructor(width, height, depth) {
        this.pos = [0, 0, 0, 1]
        this.degree = 0
        this.width = width;
        this.height = height;
        this.depth = depth;
        this.up = [0, 1, 0, 0];
        this.right = [1, 0, 0, 0];
        this.forward = [0, 0, 1, 0];
        this.upPoint = [0, height / 2, 0, 1];
        this.foPoint = [0, 0, depth / 2, 1];
        this.riPoint = [width / 2, 0, 0, 1];
        this.points = [];
        this.points.push([0, height / 2, 0, 1]); // up
        this.points.push([0, 0, depth / 2, 1]); // foward
        this.points.push([width / 2, 0, 0, 1]); // right
        this.model = Mat4x4.identityMat();
        this.t_mat = Mat4x4.identityMat();
        this.r_mat = Mat4x4.identityMat();
        this.s_mat = Mat4x4.identityMat();
    }

    rotBox(degree) {
        this.r_mat = Mat4x4.rotMatAxisZ(degree);
        this.model = Mat4x4.multipleMat4(this.r_mat, this.s_mat);
        this.model = Mat4x4.multipleMat4(this.t_mat, this.model);
        this.up = Mat4x4.multipleMat4AndVec4(this.r_mat, [0, 1, 0, 0]);
        this.right = Mat4x4.multipleMat4AndVec4(this.r_mat, [1, 0, 0, 0]);
        this.forward = Mat4x4.multipleMat4AndVec4(this.r_mat, [0, 0, 1, 0]);
        this.points[0] = Mat4x4.multipleMat4AndVec4(this.model, this.upPoint);
        this.points[1] = Mat4x4.multipleMat4AndVec4(this.model, this.foPoint);
        this.points[2] = Mat4x4.multipleMat4AndVec4(this.model, this.riPoint);
    }

    moveBox(mvX, mvY, mvZ) {
        this.t_mat = Mat4x4.transportMat([mvX, mvY, mvZ, 1])
        this.model = Mat4x4.multipleMat4(this.r_mat, this.s_mat);
        this.model = Mat4x4.multipleMat4(this.t_mat, this.model);
        this.pos = Mat4x4.multipleMat4AndVec4(this.model, [0, 0, 0, 1]);
        this.points[0] = Mat4x4.multipleMat4AndVec4(this.model, this.upPoint);
        this.points[1] = Mat4x4.multipleMat4AndVec4(this.model, this.foPoint);
        this.points[2] = Mat4x4.multipleMat4AndVec4(this.model, this.riPoint);
    }

    scaleBox(w_scale, h_scale) {
        // TODO
    }

    collision(otherBox) {
        let ab = subDir(this.pos, otherBox.pos);
        let unique = [];
        for (let i = 0; i < 3; i++) {
            unique.push(subDir(this.points[i], this.pos));
            unique.push(subDir(otherBox.points[i], otherBox.pos));
        }
        let SAT = [this.up, this.right, this.forward, otherBox.up, otherBox.right, otherBox.forward];
        SAT.push(crossProduct(this.up, otherBox.up));
        SAT.push(crossProduct(this.up, otherBox.right));
        SAT.push(crossProduct(this.up, otherBox.forward));
        SAT.push(crossProduct(this.right, otherBox.up));
        SAT.push(crossProduct(this.right, otherBox.right));
        SAT.push(crossProduct(this.right, otherBox.forward));
        SAT.push(crossProduct(this.forward, otherBox.up));
        SAT.push(crossProduct(this.forward, otherBox.right));
        SAT.push(crossProduct(this.forward, otherBox.forward));
        for (let i = 0; i < SAT.length; i++) {
            let total = 0;
            for (let j = 0; j < 6; j++) {
                total += Math.abs(dotDir(SAT[i], unique[j]));
            }
            let dist = Math.abs(dotDir(ab, SAT[i]));
            if (dist > total)
                return false;
        }
        return true;
    }
};