2D Polygon Collision Response and Rigid Body Motion

Question

So I am already aware that I am trying to tackle a huge gaming obstacle that I may or may not be able to do, but I have read up on 2D Collision Response everywhere that I can and this pdf file is the most benificial thing that I have found. I have the formulas down, I just lack the conceptual understanding of the math to know how this big nasty formula is supposed to look in code.

The Collision Detection is not the problem, I have already devised a system for that and it works fine. I am having trouble figuring out what parameters I would need for a handleCollision() method when a Polygon collides with a wall, in this case the side of the JFrame window.

I already set up my concave "spaceship" polygon as a combination of individual convex polygons, and I currently have made working methods to get the Area of each polygon (represented by the Module class), as well as the centroid. The combination of small convex polygons is represented by a Vessel class, from which I can also get the centroid by averaging the centroids of its Modules, and its Area.

The JPanel class :

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.event.KeyEvent;
import java.awt.event.MouseEvent;
import java.awt.event.MouseWheelEvent;
import java.awt.geom.Area;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import javax.swing.JPanel;

public class TPanel extends JPanel
{
    private static final long serialVersionUID = 1L;

    private int xBounds, yBounds;
    private Rectangle2D.Double cage;
    private Area bounds;
    private Vessel vessel;
    private ArrayList<Point2D.Double> stars;

    public TPanel(int x, int y, int res)
    {
        xBounds = x;
        yBounds = y;
        cage = new Rectangle2D.Double(xBounds / 3, yBounds / 3, xBounds / 3, yBounds / 3); //normally used as the boundaries for panning - not being used as of now
        vessel = new Vessel(new Point2D.Double(cage.x + cage.width / 2, cage.y + cage.height / 2));
        stars = new ArrayList<Point2D.Double>();

        bounds = new Area(new Rectangle2D.Double(-1, -1, xBounds + 2, yBounds + 2));
        bounds.subtract(new Area(new Rectangle2D.Double(0, 0, xBounds, yBounds))); // creates a thin border around the screen for collision checking

        for(int i = 0; i < 1000; i++) // random star locations to provide a background
        {
            stars.add(new Point2D.Double(Math.random() * xBounds, Math.random() * yBounds));
        }
    }

    public void paintComponent(Graphics arg0)
    {
        Graphics2D g = (Graphics2D) arg0;
        g.setColor(Color.black);
        g.fillRect(0, 0, xBounds, yBounds);
        g.setColor(Color.white);
        for(Point2D.Double l : stars)
        {
            g.drawLine((int)l.x, (int)l.y, (int)l.x, (int)l.y);
        }

        vessel.act(true, true, true);

        //I use area.intersect(Area a) to determine if the vessel is colliding with the boundaries
        Area i = vessel.getArea();
        i.intersect(bounds);
        if(!i.isEmpty())
        {
            /** What parameters do I need to use here to calulate the 
             * resulting velocity and angular velocity of the vessel
             * upon contact with one of the four boundary walls?
             * I know I need the normal vector perpendicular to the wall
             * that it is colliding with... How do I incorporate Chris Hecker's
             * formulas here?
             * 
             * for the Vessel:
             * 
             * Angular velocity :    vessel.aVelocity
             * Velocity         :    vessel.xVelocty; and vessel.yVelocity;
             * Centroid (Point2D.Double):    vessel.getCenter()
             * Moment of Inertia: vessel.getMOI()
             *     ****DO I NEED MOMENT OF INERTIA?*****
             * Mass             :    vessel.getMass()
             * 
             * how do I incorporate these variables to produce the realistic 
             * end-behavior of the spaceship after a collision with the wall
             * as illustrated in Chris Hecker's article?
             * 
             */







        }

        //THE AREA FOR PANNING HAS BEEN OMITTED - so I can try to get collisions working with the boundaries of the JFrame window
        /*
        boolean xMove = true;
        boolean yMove = true;
        if(p.x < cage.getMinX() || p.x > cage.getMaxX())
            xMove = false;
        if(p.y < cage.getMinY() || p.y > cage.getMaxY())
            yMove = false;
        Point2D.Double disp = vessel.act(xMove, yMove, true);
        for(Point2D.Double l : stars)
        {
            if(!xMove)
                l.x -= disp.x;
            if(!yMove)
                l.y -= disp.y;
        }
         */     

        for(Area a : vessel.getAreaModules())
        {
            g.setColor(Color.gray);
            g.fill(a);
            g.setColor(Color.lightGray);
            g.draw(a);
        }

        for(Module m : vessel.modules)
        {
            g.setColor(Color.cyan);
            g.fillOval((int)(m.getCenter().x * Tazzum.SCALE + vessel.loc.x) - 2, (int)(m.getCenter().y * Tazzum.SCALE + vessel.loc.y) - 2, 4, 4);
        }

        g.setColor(Color.yellow);
        g.fillOval((int)(vessel.getCenter().x * Tazzum.SCALE + vessel.loc.x) - 2, (int)(vessel.getCenter().y * Tazzum.SCALE + vessel.loc.y) - 2, 4, 4);

    }

    public double dotProduct(double a, double b, double theta)
    {
        return Math.abs(a) * Math.abs(b) * Math.sin(theta);
    }

    public void mouseClicked(MouseEvent e) {}
    public void mouseEntered(MouseEvent e) {}
    public void mouseExited(MouseEvent e) {}
    public void mousePressed(MouseEvent e) {}
    public void mouseReleased(MouseEvent e) {}
    public void keyPressed(KeyEvent e)
    {
        if(e.getKeyCode() == KeyEvent.VK_W)
        {
            vessel.throttle = 1;
            vessel.ignition = true;
        }
        else if(e.getKeyCode() == KeyEvent.VK_A)
        {
            vessel.torque = -1;
        }
        else if(e.getKeyCode() == KeyEvent.VK_D)
        {
            vessel.torque = 1;
        }
        else if(e.getKeyCode() == KeyEvent.VK_S)
        {
            vessel.aVelocity = 0.0;
        }
    }
    public void keyReleased(KeyEvent e)
    {
        if(e.getKeyCode() == KeyEvent.VK_W || e.getKeyCode() == KeyEvent.VK_S)
        {
            vessel.throttle = 0;
            vessel.ignition = false;
        }
        else if(e.getKeyCode() == KeyEvent.VK_A || e.getKeyCode() == KeyEvent.VK_D)
        {
            vessel.torque = 0;
        }
    }
    public void keyTyped(KeyEvent e) {}
    public void mouseDragged(MouseEvent e) {}
    public void mouseMoved(MouseEvent e) {}
    public void mouseWheelMoved(MouseWheelEvent e) {}

}

The Vessel Class :

import java.awt.geom.AffineTransform;
import java.awt.geom.Area;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Arrays;

public class Vessel
{
    public ArrayList<Module> modules;
    public Point2D.Double loc;
    public String name;
    public double xVelocity, yVelocity, aVelocity;
    public double accel, aAccel;
    private double dir;
    public int throttle, torque;
    public boolean ignition, steering;


    public Vessel(Point2D.Double p)
    {
        loc = p;
        name = "Vessel";
        xVelocity = 0.0;
        yVelocity = 0.0;
        aVelocity = 0.0;
        accel = 16;
        aAccel = 8;
        dir = Math.PI * 3 / 2;
        throttle = 0;
        torque = 0;
        ignition = false;
        modules = new ArrayList<Module>(
                Arrays.asList(
                        new Module(Module.BLOCK, 0, 1, 0, 0),
                        new Module(Module.BLOCK, 0, 1, 0, -1),
                        new Module(Module.EDGE, 3, 0.5, -1, 0.5),
                        new Module(Module.EDGE, 1, 0.5, 1, 0.5),
                        new Module(Module.WEDGE, 3, 0.125, -1, -0.5),
                        new Module(Module.WEDGE, 0, 0.125, 1, -0.5),
                        new Module(Module.WEDGE, 0, 0.125, 0.5, -2),
                        new Module(Module.WEDGE, 3, 0.125, -0.5, -2)
                        /*    
                         * Constructs a Vessel with modules put together in this orientation (roughly)
                         *         _ _
                         *        /_|_\
                         *       |     |
                         *       |_____|
                         *      /|     |\
                         *     | |_____| |
                         *     |_|     |_|
                         *     
                         *         ^^^
                         *     notice concavity
                         */

                        ));

    }

    public Point2D.Double act(boolean xMove, boolean yMove, boolean aMove)
    {
        double d = 0.0;
        Point2D.Double disp = new Point2D.Double();
        xVelocity += (throttle * accel * Tazzum.TIME_INCREMENT) * Math.cos(dir);
        yVelocity += (throttle * accel * Tazzum.TIME_INCREMENT) * Math.sin(dir);
        aVelocity += torque * aAccel * Tazzum.TIME_INCREMENT;
        disp.x = xVelocity * Tazzum.TIME_INCREMENT + (ignition ? 0.5 * accel *  Math.pow(Tazzum.TIME_INCREMENT, 2) : 0);
        disp.y = yVelocity * Tazzum.TIME_INCREMENT + (ignition ? 0.5 * accel *  Math.pow(Tazzum.TIME_INCREMENT, 2) : 0);


        //boolean checks to see if the window is panning to keep the spaceship where it is on the screen - while other objects are moving, making it look like the vessel is.
        if(xMove)
            loc.x += disp.x;
        if(yMove)
            loc.y += disp.y;
        if(aMove)
            d += aVelocity * Tazzum.TIME_INCREMENT + (torque != 0 ? 0.5 * aAccel * Math.pow(Tazzum.TIME_INCREMENT, 2) : 0);
        rotate(d, getCenter());
        return disp;
    }

    public void rotate(double t, Point2D.Double l)
    {
        for(Module m : modules)
            m.rotate(t, l);
        dir += t;
    }

    public Point2D.Double getCenter()
    {
        double x = 0.0;
        double y = 0.0;
        for(Module m : modules)
        {
            x += m.getCenter().x * m.density;
            y += m.getCenter().y * m.density;

        }
        x /= modules.size();
        y /= modules.size();
        return new Point2D.Double(x, y);
    }

    public ArrayList<Area> getAreaModules()
    {
        ArrayList<Area> arr = new ArrayList<Area>();
        AffineTransform at = new AffineTransform();
        at.translate(loc.x,  loc.y);
        at.scale(Tazzum.SCALE, Tazzum.SCALE); //scales the Area to the resolution of the screen before being painted
        Area a;
        for(Module m : modules)
        {
            a = new Area(at.createTransformedShape(m.shape));
            arr.add(a);
        }
        return arr;
    }

    public Area getArea()
    {
        Area a = new Area();
        for(Area b : getAreaModules())
            a.add(b);
        return a;
    }

    public double getMass()
    {
        double mass = 0.0;
        for(Module m : modules)
        {
            mass += m.getMass();
        }
        return mass;
    }

    public Point2D.Double getMOI() //moment of inertia for the concave spacecraft
    {
        Point2D.Double MOI = new Point2D.Double();
        for(Module m : modules)
        {
            MOI.x += m.getMOI().x;
            MOI.y += m.getMOI().y;
        }
        return MOI;
    }

}

and the Module Class :

import java.awt.Shape;
import java.awt.geom.AffineTransform;
import java.awt.geom.Arc2D;
import java.awt.geom.PathIterator;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;


public class Module
{
    //structural polygon layouts
    public static final Rectangle2D.Double BLOCK = new Rectangle2D.Double(-0.5, -0.5, 1, 1);
    public static final Rectangle2D.Double EDGE = new Rectangle2D.Double(-0.5, 0, 1, 0.5);
    public static final Polygon2D WEDGE = new Polygon2D(new double[]{-0.5, 0, -0.5}, new double[]{0, 0.5, 0.5}, 3);
    public static final Arc2D.Double ARC = new Arc2D.Double(-0.5, -0.5, 1, 1, 90, -90, Arc2D.PIE);

    public Shape shape;
    public double density;

    public Module(Shape s, int orientation, double d, double x, double y)
    {
        shape = s;
        density = d;
        AffineTransform at = new AffineTransform();
        at.translate(x, y);
        at.rotate(Math.PI / 2 * orientation);
        shape = at.createTransformedShape(shape);
    }

    public void rotate(double t, Point2D.Double l) // rotates the module by radians 'theta' about point 'l' with respect to the polygon's structural layout ^^^
    {
        AffineTransform at = new AffineTransform();
        at.rotate(t, l.x, l.y);
        shape = at.createTransformedShape(shape);
    }

    public Point2D.Double getCenter() // accurately goes through the PathIterator and averages points from the path to calculate the centroid of the shape
    {
        ArrayList<Point2D.Double> points = new ArrayList<Point2D.Double>();
        double[] arr = new double[6];
        for(PathIterator pi = shape.getPathIterator(null); !pi.isDone(); pi.next())
        {
            switch(pi.currentSegment(arr))
            {

            case PathIterator.SEG_LINETO :
                points.add(new Point2D.Double(arr[0], arr[1]));
                break;
            case PathIterator.SEG_CUBICTO :
                points.add(new Point2D.Double(arr[0], arr[1]));
                points.add(new Point2D.Double(arr[2], arr[3]));
                break;
            }
        }
        double cX = 0;
        double cY = 0;
        for(Point2D.Double p : points)
        {
            cX += p.x;
            cY += p.y;
        }
        return new Point2D.Double(cX / points.size() , cY / points.size());
    }

    public double getMass()
    {
        return density * Tazzum.SCALE;
    }

    public Point2D.Double getMOI() //calculate the moment of inertia for the polygon/Module
    {
        double height = shape.getBounds2D().getHeight() * Tazzum.SCALE;
        double width = shape.getBounds2D().getWidth() * Tazzum.SCALE;
        double xMOI = 0.0;
        double yMOI = 0.0;
        if(shape instanceof Rectangle2D) // moment of inertia for rectangular polygon
        {
            xMOI = width * Math.pow(height, 3) / 12;
            yMOI = Math.pow(width, 3) * height / 12;
        }
        else if(shape instanceof Polygon2D) //moment of inertia for a triangle (all Polygon2D objects instantiated are triangles as of now)
        {
            xMOI = width * Math.pow(height, 3) / 36;
            yMOI = width * Math.pow(height, 3) / 36;
        }
        else if(shape instanceof Arc2D) //moment of inertia for a quarter-circle
        {
            xMOI = (Math.PI / 16 - 4 / (9 * Math.PI)) * Math.pow(width, 3);
            yMOI = (Math.PI / 16 - 4 / (9 * Math.PI)) * Math.pow(width, 3);
        }

        return new Point2D.Double(xMOI, yMOI); //I'm using a Point2D.Double to unconventionally pass in two MOIs in case there's a Y-component
    }
}

If you have taken the time to analyze my situation - thank you! Hopefully you have a way of solving this dilemma.

Answer 1

I know that this is a collision detection specific question, but I suggest that you check out the JBox2D rigid body physics library (Which you can find here: http://www.jbox2d.org/)

I personally use this library and I like it a lot. I don't know if you're intending to write your library from scratch, but if you aren't, then JBox2D is a great solution. It's a port of the C++ Box2D library, which is well known and well documented - examples of C++ code using it (which shouldn't be too hard to port to Java) can be found in many places. A great resource is iForce2D: http://www.iforce2d.net/b2dtut/

Of course these tutorials are for C++ but the general idea is there.

Also, I'd like to suggest (this is not in any way related to the question you were asking, but since I know people who've had huge performance problems with Java2D in the past) that you look into LWJGL and its Java OpenGL bindings. I love it, and it makes for far more beautiful as well as (in comparison) blindingly fast code. It does have a bit of a steep learning curve, though. LWJGL also contains a great keyboard/mouse interface as well as OpenAL bindings for audio. Here's LWJGL's homepage: http://lwjgl.org/

I hope this helps!