Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Rectangle problem

Reply
Thread Tools

Rectangle problem

 
 
stuartbrockman@gmail.com
Guest
Posts: n/a
 
      07-24-2008
Hi,
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
area.

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.
 
Reply With Quote
 
 
 
 
Juha Nieminen
Guest
Posts: n/a
 
      07-24-2008
http://www.velocityreviews.com/forums/(E-Mail Removed) 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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Can anyone implement the pseudocode for the maximal rectangle problem ? Dan C Programming 1 03-26-2011 06:26 PM
Can anyone implement the pseudocode for the maximal rectangle problem ? Dan C++ 1 03-26-2011 06:26 PM
scientific publications on the "Square-rectangle problem"? Leslaw Bieniasz C++ 27 02-03-2010 02:34 PM
Paint a rectangle Alberto ASP .Net 1 01-01-2005 04:47 PM
Rectangle object in asp.net? Kenneth ASP .Net 1 01-15-2004 08:53 AM



Advertisments