views:

25

answers:

0

I'm developing a game where I need to do collision detection between a mobile circle and a stationary point. I am using a continuous method. I detect if the circle will hit the point before moving it, get the time of intersection, move the circle, then give the circle a new velocity vector. In my case, the new vector pushes the circle along the tangent between the circle and point, creating a sliding motion.

Since I get a time of intersection, I treat each frame as a period of time, and keep moving the circle during the frame until no time is left.

point = Point(px, py)
circle = Circle(x, y, radius)

...

function circle.setVelocity(dx, dy)
    self.dx = dx
    self.dy = dy

    self.velocityMag = math.sqrt((dx * dx) + (dy * dy))

function circle.move(time)
    ntime = time or 1

    self.x = self.x + (self.dx * ntime)
    self.y = self.y + (self.dy * ntime)

...

function update()
    circle.setVelocity(myDX, myDY)

    frameTime = 1
    moving = true

    while moving
        // cData contains time of impact and new velocity for circle.
        // If cData is null, no collision occurred within current time
        // period.
        cData = circleVSPoint(point, circle, frameTime)

        if cData
            circle.move(cData.time)

            frameTime = frameTime - cData.time

            if frameTime > 0
                circle.setVelocity(cData.newDX, cData.newDY)
            else
                moving = false
        else
            // No collision during remaining frameTime
            circle.move(frameTime)
            moving = false

The problem is I'm still getting intersections between the circle and the point. This is causing the time of impact to sometimes be negative. This leads to infinite loops in my main update code if the circle has the right position or velocity. I am unsure whether this is a bug in my main collision algorithm or if it's being caused by floating-point round-off errors.

This what the actual collision detection and response code looks like. It is based on this article: http://www.gamasutra.com/view/feature/3015/pool_hall_lessons_fast_accurate_.php?page=2, with the addition of collision response by projecting the circle's velocity onto the tangent between it and the point.

function circleVSPoint(point, circle, remainingTime)
    cData = null

    radius = circle.radius // Convenience

    // Vector from circle to point
    cornDX = point.x - circle.x
    cornDY = point.y - circle.y

    pLenSqr = (cornDX * cornDX) + (cornDY * cornDY)

    len = squareRoot(pLenSqr) - radius

    if len < circle.velocityMag
        // Circle fast enough to cross point if headed the right way.
        // Project vector from circle to point onto circle's
        // velocity vector.  This will get the closest point the
        // circle will ever reach the point.

        // Velocity unit vector
        vnx = circle.dx / circle.velocityMag
        vny = circle.dy / circle.velocityMag

        // Length of the projection vector
        dotprod = dotProduct(vnx, vny, cornDX, cornDY)

        if dotprod > 0
            // circle-to-point vector and projection vector form a
            // right triangle (circle-to-point vector is the
            // hypotenuse)

            radiusSqr = radius * radius

            minDistSqr = pLenSqr - (dotprod * dotprod)

            if minDistSqr < radiusSqr
                // The min distance forms a right triangle with a
                // hypotenuse with length equal to the radius.
                // Find the length of the other side.

                travOffsetSqr = radiusSqr - minDistSqr

                // Distance circle travels before hitting point
                realDist = dotprod - squareRoot(travOffsetSqr)

                if realDist < circle.velocityMag
                    testTime = realDist / circle.velocityMag

                    if testTime < remainingTime
                        cData = CollisionData()

                        // Collision time
                        cData.time = testTime

                        // Collision response

                        // Vector from point to circle's final
                        // position

                        fx = circle.x + (circle.dx * testTime)
                        fy = circle.y + (circle.dy * testTime)

                        fdx = fx - point.x
                        fdy = fy - point.y

                        // Right hand normal
                        normalX = -fdy
                        normalY = fdx

                        // Project circle's velocity vector onto
                        // tangent of point

                        // The projection of U on V is
                        //         U . V
                        //        ------- * V
                        //         |V|^2

                        dotprod = dotProduct(
                          circle.dx, circle.dy, normalX, normalY)
                        m = dotprod / radiusSqr

                        cData.newDX = m * normalX
                        cData.newDY = m * normalY

    return cData

Is anyone able to see any errors in my pseudocode? If not, could my issue really be caused by round-off errors? If so, what would I do to mitigate those?