• Advertisement
Sign in to follow this  

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.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi

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

Thanks! Edited by SpectreNectar

Share this post


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

Share this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement