2 replies to this topic

[SpectreNectar]

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.

[Faelenor]

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

[SpectreNectar]

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.