Hi Zach,
On Sun Aug 29 04:00:53 2010, zpmorgan@gmail.com wrote:
Show quoted text> I'm sorry Steffen, I somehow missed this message earlier.
No worries.
Show quoted text> It seems that you have the wrong idea about continuous collision
> detection.
Indeed, I originally had the wrong idea.
Show quoted text> If you'd like explanations for how I handled the various types of
> collisions, I'd be happy to explain it. I mostly just worked it out
> with basic geometrical equations.
That's fine. I think I could do the math, too. And I always have the
code to look at.
Show quoted text> Also, about the constructor, wouldn't an xsub constructor with named
> arguments still use a hash? Do you think it would boost performance
> much? I think that converting some of the point collision routines
> would be a much bigger gain. (some collision tests are broken down
> into multiple point collision tests)
Hmm. The constructor could still use a hash. Or it could walk the
arguments doign flip/flop with the expected key/value pairs. The big win
would be eliminating the extra entersub call of the Perl function
wrapper. Furthermore, calling XSUBs is faster than ordinary subs, so you
win some more. Below is the code (from Class::XSAccessor) that
implements a plain dumb constructor a la "return bless {@_}=>$class" for
a Perl-hash based object. You'd want to either create a hash (without
blessing it) and then hv_fetch from there to get the values for the C
object or, as I wrote above, just walk the argument list doing strEQ in
an if or even using a static hash map/switch for the keyname => struct
member conversion.
Naturally, these constructors could be generated from a list of valid
keys and struct member names using macros.
void
constructor(class, ...)
SV* class;
PREINIT:
int iStack;
HV* hash;
SV* obj;
const char* classname;
PPCODE:
if (sv_isobject(class)) {
classname = sv_reftype(SvRV(class), 1);
}
else {
if (!SvPOK(class))
croak("Need an object or class name as first argument to the
constructor.");
classname = SvPV_nolen(class);
}
hash = (HV *)sv_2mortal((SV *)newHV());
obj = sv_bless( newRV_inc((SV*)hash), gv_stashpv(classname, 1) );
if (items > 1) {
if (!(items % 2))
croak("Uneven number of arguments to constructor.");
for (iStack = 1; iStack < items; iStack += 2) {
HE *he;
he = hv_store_ent(hash, ST(iStack), newSVsv(ST(iStack+1)), 0);
if (!he) {
croak("Failed to write value to hash.");
}
}
}
PUSHs(sv_2mortal(obj));
Back to the original topic. I believe I figured out an algorithm that'll
detect polygon-polygon collision (yes, the dynamic type). I haven't
really done the math with pencil and paper, but it should be around
O(n*m) where n/m are the number of vertexes in the two polygons that are
involved.
First, we boost the scene so that one of the polygons is at rest
(O(n+m)). To determine whether the polygons will collide at all, we
orthogonally project the vertexes of both polygons on the line that is
orthogonal to the direction of movement of the moving polygon (O(n+m)
again). For each polygon, we find the outermost points on the line.
Then, if the two line segments intersect, the polygons will collide
(unless the direction of movement is going away from the second
polygon). So this should be O(n) overall.
Then, do get the actual collision, we use that one of the polygons isn't
moving. The collision must happen between one of the vertexes of either
of the polygons with an edge of the respective other polygon. So we use
the line trajectory of each vertex in the moving polygon and calculate
the intersection point with each edge (or the line it's in) of the
static polygon. We verify that the point is within the edge. If so, we
get the collision time. Repeat with switched roles. Then we calculate
the minimum of the collision times. This part should be O(n*m).
Of course, the difficult bit is always handling all the edge cases such
as head-on vertex-vertex collision.
It doesn't seem like I'll get the time to implement this any time soon,
but I thought I'd put this out there regardless.
Cheers,
Steffen
