# Separating geometry based on closest points?

This topic is 1924 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi

What is a good way to separate a sphere or a capsule inside a polyhedron?

Thanks! Edited by SpectreNectar

##### Share on other sites
Can you give more details please? An example would be nice, I don't understand what you're asking...

##### Share on other sites
Yes that was quite vague, I wasn't sure what I was asking at the time.

I've been looking into the GJK algorithm, but I have some trouble implementing it. Here's what I've tried for the 2D case (GML):

co_gjk()
[CODE]
{
// Arguments for first OBB
var a_cx, a_cy, a_ax1, a_ay1, a_ax2, a_ay2, a_sx, a_sy;
a_cx = argument0;
a_cy = argument1;
a_ax1 = argument2;
a_ay1 = argument3;
a_ax2 = argument4;
a_ay2 = argument5;
a_sx = argument6;
a_sy = argument7;

// Arguments for second OBB
var b_cx, b_cy, b_ax1, b_ay1, b_ax2, b_ay2, b_sx, b_sy;
b_cx = argument8;
b_cy = argument9;
b_ax1 = argument10;
b_ay1 = argument11;
b_ax2 = argument12;
b_ay2 = argument13;
b_sx = argument14;
b_sy = argument15;

// Vectors
co_gjk_direction_vector_x = -1;
co_gjk_direction_vector_y = -1;

var posx, posy, negx, negy;
posx = co_obb_furthest_point_along_vector_x(a_cx, a_cy, a_ax1, a_ay1, a_ax2, a_ay2, a_sx, a_sy);
posy = co_obb_furthest_point_along_vector_y(a_cx, a_cy, a_ax1, a_ay1, a_ax2, a_ay2, a_sx, a_sy);
negx = co_obb_furthest_point_along_vector_x(b_cx, b_cy, b_ax1, b_ay1, b_ax2, b_ay2, b_sx, b_sy);
negy = co_obb_furthest_point_along_vector_y(b_cx, b_cy, b_ax1, b_ay1, b_ax2, b_ay2, b_sx, b_sy);

var ax, ay;
ax = (posx-negx);
ay = (posy-negy);

co_gjk_direction_vector_x = -ax;
co_gjk_direction_vector_y = -ay;

co_gjk_point_list_x[0] = ax;
co_gjk_point_list_x[0] = ay;
var n;
n = 1;
do {

// Along direction vector
posx = co_obb_furthest_point_along_vector_x(a_cx, a_cy, a_ax1, a_ay1, a_ax2, a_ay2, a_sx, a_sy);
posy = co_obb_furthest_point_along_vector_y(a_cx, a_cy, a_ax1, a_ay1, a_ax2, a_ay2, a_sx, a_sy);
negx = co_obb_furthest_point_along_vector_x(b_cx, b_cy, b_ax1, b_ay1, b_ax2, b_ay2, b_sx, b_sy);
negy = co_obb_furthest_point_along_vector_y(b_cx, b_cy, b_ax1, b_ay1, b_ax2, b_ay2, b_sx, b_sy);

ax = (posx-negx);
ay = (posy-negy);

if(ax*co_gjk_direction_vector_x+ay*co_gjk_direction_vector_y < 0) return false;

co_gjk_point_list_x[n] = ax;
co_gjk_point_list_y[n] = ay;

if(n+1==2) n = co_gjk_line(co_gjk_point_list_x[0], co_gjk_point_list_y[0], co_gjk_point_list_x[1], co_gjk_point_list_y[1]);
else n = co_gjk_triangle(co_gjk_point_list_x[0], co_gjk_point_list_y[0], co_gjk_point_list_x[1], co_gjk_point_list_y[1], co_gjk_point_list_x[2], co_gjk_point_list_y[2]);

} until(n>=3);

return true;
}
[/CODE]

co_gjk_line()
[CODE]

{
var ax, ay, bx, by;
ax = argument2; //A is last!
ay = argument3;
bx = argument0;
by = argument1;
var aox, aoy, abx, aby;
aox = -ax;
aoy = -ay
abx = bx-ax;
aby = by-ay;

co_gjk_direction_vector_x = -aby;
co_gjk_direction_vector_y = abx;
// Not towards origin?
if(co_gjk_direction_vector_x*aox+co_gjk_direction_vector_y*aoy<0) {
co_gjk_direction_vector_x = -co_gjk_direction_vector_x;
co_gjk_direction_vector_y = -co_gjk_direction_vector_y;
}
return 2;
}
[/CODE]

co_gjk_triangle()
[CODE]
{
var ax, ay, bx, by, cx, cy;
ax = argument4; //A is last!
ay = argument5;
bx = argument2;
by = argument3;
cx = argument0;
cy = argument1;
var aox, aoy, abx, aby, acx, acy;
aox = -ax;
aoy = -ay
abx = bx-ax;
aby = by-ay;
acx = cx-ax;
acy = cy-ay;

co_gjk_direction_vector_x = -aby;
co_gjk_direction_vector_y = abx;
// "2D cross product"
if(abx*acy-aby*acx>0.0) {
co_gjk_direction_vector_x = -co_gjk_direction_vector_x;
co_gjk_direction_vector_y = -co_gjk_direction_vector_y;
}

// Towards origin?
if(co_gjk_direction_vector_x*aox+co_gjk_direction_vector_y*aoy>0.0) {
// Remove C from simplex
co_gjk_point_list_x[0] = ax;
co_gjk_point_list_x[0] = ay;
return 2;
}

co_gjk_direction_vector_x = -acy;
co_gjk_direction_vector_y = acx;
// "2D cross product"
if(acx*aby-acy*abx>0.0) {
co_gjk_direction_vector_x = -co_gjk_direction_vector_x;
co_gjk_direction_vector_y = -co_gjk_direction_vector_y;
}

// Towards origin?
if(co_gjk_direction_vector_x*aox+co_gjk_direction_vector_y*aoy<0) {
// Remove B from simplex
co_gjk_point_list_x[1] = ax;
co_gjk_point_list_x[1] = ay;
return 2;
}

// Done
return 3;
}
[/CODE]

co_obb_furthest_point_along_vector_x()
[CODE]
{
var cx, cy, ax1, ay1, ax2, ay2, sx, sy;
cx = argument0;
cy = argument1;
ax1 = argument2;
ay1 = argument3;
ax2 = argument4;
ay2 = argument5;
sx = argument6;
sy = argument7;

return sx*abs(co_gjk_direction_vector_x*ax1+co_gjk_direction_vector_y*ay1);
}
[/CODE]

It's supposed to return true if the OBBs intersect but nothing happens.