Rectangle problem

Discussion in 'C++' started by, Jul 24, 2008.

  1. Guest

    I am currently writing a simple 2D game in C++ and I need an algorithm
    to help me decide which areas of the screen need redrawing. Each of
    the entities on screen that have updated in a particular frame add
    themselves to a vector maintained by a "ScreenManager" class and I
    have their bounding rectangles. Unfortunately, many of these entities
    are overlapping and performance is an issue, so I am looking for an
    algorithm to simplify the job to be done.

    To simplify the problem, say I have a struct:

    struct Rect{
    Rect(int x, int y, int width, int height);
    int x, y, width, height;

    I would like to have a function that takes a std::vector<Rect> and
    returns another std::vector<Rect>, except that in the new vector, none
    of the Rect's are overlapping, but they still cover the same screen

    e.g Say I have a Rect(1,1,10,10) and a Rect(5,5,10,10), the function
    would return {Rect(1,1,10,10), Rect(5,11,10,4), Rect(11,5,4,4)} or
    something equivalent.

    Note that in the actual game, there would be more than two Rect's. And
    they may be overlapping (or not) in any way.

    Does anybody have any idea where I could start on this? The algorithm
    is easy to do in my head with a pen and paper, but I can't seem to
    work out how to do it in code.
    , Jul 24, 2008
    1. Advertisements

  2. wrote:
    > I am currently writing a simple 2D game in C++ and I need an algorithm
    > to help me decide which areas of the screen need redrawing.

    Not an answer to your question, but if you are using some kind of
    graphics library which takes advantage of hardware acceleration (which
    is more the rule than the exception in current computers), the need to
    refresh only the changed parts of the screen is mostly a thing of the
    past. Refreshing the entire screen (or application window) every time
    anything changes is usually so light with hardware acceleration
    (especially for 2D games) that it's a non-issue.
    From experience I can say that you can draw eg. 10 screen-sized
    alpha-channeled bitmaps on the screen, each over the previous ones, plus
    a couple dozens of smaller images, 50 times per second, and even a
    low-end (but modern) CPU won't even hit 30% of usage.

    Of course if you are drawing purely in software mode, without any
    hardware acceleration, that's a completely different issue.
    Juha Nieminen, Jul 24, 2008
    1. Advertisements

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Kenneth

    Rectangle object in

    Kenneth, Jan 15, 2004, in forum: ASP .Net
    Steve C. Orr [MVP, MCSD]
    Jan 15, 2004
  2. Alberto

    Paint a rectangle

    Alberto, Jan 1, 2005, in forum: ASP .Net
    Scott Mitchell [MVP]
    Jan 1, 2005
  3. Leslaw Bieniasz
    Feb 3, 2010
  4. Dan
    Öö Tiib
    Mar 26, 2011
  5. Dan
    Öö Tiib
    Mar 26, 2011

Share This Page