• FEATURED

View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Separating geometry based on closest points?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

2 replies to this topic

### #1SpectreNectar  Members

Posted 11 October 2012 - 04:06 PM

Hi

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

Thanks!

Edited by SpectreNectar, 11 October 2012 - 04:21 PM.

### #2Faelenor  Members

Posted 12 October 2012 - 05:23 AM

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

### #3SpectreNectar  Members

Posted 12 October 2012 - 02:40 PM

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()
{
// 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;
}


co_gjk_line()

{
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;
}


co_gjk_triangle()
{
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;
}


co_obb_furthest_point_along_vector_x()
{
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);
}


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

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.