Is this a good algorithm for 2D collision, or will it allocate too much memory?

Question

I have a Rectangle class, of which I have 5-6 vectors for each instance. The main vectors are the center and color of the object, while the secondary vectors represent more or less the north, south, east, and west directions of the rectangle itself. These vectors are used to detect collision by "pointing" outside of the sides of the rectangle to detect collision. I may end up creating more fields of the NW, SW, NE, SE, equivalents as well, but I'd like to know if this is actually a good implementation before I do this. The only Vec2f I have allocated as a pointer is the mWidthHeight vector, which of course is just a representation of the width and the height (x = width, y = height) of the rectangle.

Will this allocate too much memory if there are thousands of these on the screen, or is this an OK (at least) implementation?

Rect.h

Note - I'm debating with the idea of making the N, S, E, W vectors pointers to memory. Is that a good idea, or no?

#pragma once

#include <QGLWidget>
#include <GL/glext.h>
#include <cmath>
#include <QDebug>
#include "Shape.h"
#include "Vec3f.h"
#include "rand.h"

const int DEFAULT_SQUARE_WIDTH = 5;
const int DEFAULT_SQUARE_HEIGHT = 5;

typedef enum {

  V2D_NORTH,
  V2D_SOUTH,
  V2D_EAST,
  V2D_WEST

} V2D_DIRECTION;

class Rectangle : public Shape
{
public:

    Rectangle(
        Vec2f center = Vec2f(),
        Vec2f widthheight = Vec2f(DEFAULT_SQUARE_WIDTH, DEFAULT_SQUARE_HEIGHT),
        float radius = 0,
        Vec3f color = Vec3f()
    );

    ~Rectangle();

    inline Vec2f* getWidthHeight() const {
        return mWidthHeight;
    }

    inline Vec2f getDirection(V2D_DIRECTION dir) const {
        switch(dir) {
        case V2D_NORTH:
            return mNorth;

        case V2D_SOUTH:
            return mSouth;

        case V2D_EAST:
            return mEast;

        case V2D_WEST:
            return mWest;

        }
    }
    virtual void Collide( Shape &s );

    virtual void Collide( Rectangle &r );

    virtual void Collide ( Circle &c );

    virtual bool Intersects( const Shape& s ) const;

    virtual bool Intersects( const Rectangle& s ) const;

    virtual bool IsAlive( void ) const;

    virtual float Mass( void ) const;

protected:

   virtual void Draw( void ) const;
   Vec2f* mWidthHeight;
   Vec3f mColor;

private:
   Vec2f mNorth;
   Vec2f mSouth;
   Vec2f mEast;
   Vec2f mWest;
   void InitDirections();

};

Paul Martel · Accepted Answer · 2012-01-13 00:01:22Z

Your constructor arguments and defaults are unusual. What does radius mean for a Rectangle? Should there be an argument for initializing mass? I suggest:

    static const Vec2f& defaultCenter();
    static const Vec2f& defaultSquareDimensions();
    static const Vec3f& defaultColor();

    Rectangle(
        const Vec2f& center = defaultCenter(),
        const Vec2f& widthheight = defaultSquareDimensions(),
        // Assuming rotation angles are supported...
        const Vec2f orientation = defaultOrientation(),
        const Vec3f& color = defaultColor()
    );

and/or maybe:

    Rectangle(
        const Vec3f& color,
        const Vec2f& center = defaultCenter(),
        const Vec2f& widthheight = defaultSquareDimensions(),
        // Assuming rotation angles are supported...
        const Vec2f orientation = defaultOrientation()
    );



    inline const Vec2f& getWidthHeight() const {
        return mWidthHeight;
    }

The static methods can return "static objects" that are constructed once each instead of always constructing new temps.

I can't tell what the return value of the following function represents. What is the north direction vector of a rectangle? Can you give examples for different rectangles? Can you explain how you would use the returned vector?

    inline Vec2f getDirection(V2D_DIRECTION dir) const {
        switch(dir) {
        case V2D_NORTH:
            return mNorth;

        case V2D_SOUTH:
            return mSouth;

        case V2D_EAST:
            return mEast;

        case V2D_WEST:
            return mWest;

        }
    }

This seemed missing?

    virtual bool Intersects( const Circle& s ) const;

There should be some good reason not to make these private:

   Vec2f mCenter;

There seems to be no reason to make this a pointer. There might be an argument for making it const.

   Vec2f mWidthHeight;
   Vec2f mOrientation;

If rectangles tend to come in a small selection of colors, you may be better off storing an index into a central pallette vector or possibly a pointer into a pool of shared colors.

There might be an argument for making this const if they don't change color.

   Vec3f mColor;

The following seem expensive to store and maintain and they also seem like they may be at least partly redundant? If they are redundant (derivable from a smaller set of parameters) you should probably run benchmarks on code that stores these values and code that calculates them on the fly as needed.

private:
   Vec2f mNorth;
   Vec2f mSouth;
   Vec2f mEast;
   Vec2f mWest;
   void InitDirections();

It may be that there is a better way to express orientation and/or these other values that is more useful in finding intersections. It seems strange to me to be considering even more of these vectors for NW, etc. but I'm not even sure yet what they mean.

To speed up intersection, I thought you MIGHT also want to store an additional widthheight representing the bounding box -- the smallest x/y aligned rectangle that contains this rectangle in its current orientation.

SO MUCH depends on how your actual intersect logic uses all of these values. Storing them all and more MIGHT be worthwhile.

CPU vs. memory trade-offs can be very tricky to predict.

An afterthought: A single mDirections[V2D_MAX-1] member indexed by V2D_DIRECTIONS would neatly replace mNorth, mSouth, etc.. — Paul Martel
– Paul Martel, Commented Jan 13, 2012 at 0:37
WRT using pointers, this will likely make the members a little slower to process, AND will more than double their memory footprint UNLESS you had some way of sharing the actual Vec2f objects among (typically 2 or more) rectangles -- attached rectangles moving in formation? -- OR if somehow most of the Vec2f pointers could typically be kept null. — Paul Martel
– Paul Martel, Commented Jan 17, 2012 at 12:42

Stack Exchange Network

Is this a good algorithm for 2D collision, or will it allocate too much memory?

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Is this a good algorithm for 2D collision, or will it allocate too much memory?

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions