Sign in to follow this  
phb5000

2D Obstruction and Overlap

Recommended Posts

phb5000    122
Im working on a GUI system. Currently Im getting a quite low fps. I have to implement some kind of obstruction/overlap calculation to stop rendering of sprites that are completely invisible (due to overlap). Does anyone know of any good and fast techniques for doing this? My system is built using a control hierarchy. All controls are relative to each other (children / parent).

Share this post


Link to post
Share on other sites
Programmer16    2321
My system uses a visibility update. I'm not sure that it'll be faster than what you're using, but this is how it works:

bool Quad::UpdateVisible(RECT* pClippingRect)
{
RECT ClippingArea;
RECT QuadRect = { (long)m_Position.x, (long)m_Position.y, (long)(m_Position.x + m_fWidth), (long)(m_Position.y + m_fHeight) };
if(!pClippingRect)
SetRect(&ClippingArea, 0, 0, INT_MAX, INT_MAX);
else
memcpy(&ClippingArea, pClippingRect, sizeof(RECT));

D3DXVECTOR2 Position;
float fWidth, fHeight;
RECT SrcRect;

RECT VisibleRect;
IntersectRect(&VisibleRect, &ClippingArea, &QuadRect);

float fOffsetX = abs(QuadRect.left - VisibleRect.left);
float fOffsetY = abs(QuadRect.top - VisibleRect.top);

Position.x = m_Position.x + fOffsetX;
Position.y = m_Position.y + fOffsetY;
fWidth = VisibleRect.right - VisibleRect.left;
fHeight = VisibleRect.bottom - VisibleRect.top;

SrcRect.left = m_SrcRect.left + fOffsetX;
SrcRect.top = m_SrcRect.top + fOffsetY;
SrcRect.right = SrcRect.left + fWidth;
SrcRect.bottom = SrcRect.top + fHeight;

m_Vertices[0].SetPosition(Position.x, Position.y + fHeight);
m_Vertices[1].SetPosition(Position.x, Position.y);
m_Vertices[2].SetPosition(Position.x + fWidth, Position.y);

m_Vertices[3].SetPosition(Position.x, Position.y + fHeight);
m_Vertices[4].SetPosition(Position.x + fWidth, Position.y);
m_Vertices[5].SetPosition(Position.x + fWidth, Position.y + fHeight);

m_Vertices[0].SetColor(m_nTint);
m_Vertices[1].SetColor(m_nTint);
m_Vertices[2].SetColor(m_nTint);

m_Vertices[3].SetColor(m_nTint);
m_Vertices[4].SetColor(m_nTint);
m_Vertices[5].SetColor(m_nTint);

if(m_Texture)
{
m_Vertices[0].SetTexCoord0((float)SrcRect.left / m_Texture->GetWidth(), (float)SrcRect.bottom / m_Texture->GetHeight());
m_Vertices[1].SetTexCoord0((float)SrcRect.left / m_Texture->GetWidth(), (float)SrcRect.top / m_Texture->GetHeight());
m_Vertices[2].SetTexCoord0((float)SrcRect.right / m_Texture->GetWidth(), (float)SrcRect.top / m_Texture->GetHeight());

m_Vertices[3].SetTexCoord0((float)SrcRect.left / m_Texture->GetWidth(), (float)SrcRect.bottom / m_Texture->GetHeight());
m_Vertices[4].SetTexCoord0((float)SrcRect.right / m_Texture->GetWidth(), (float)SrcRect.top / m_Texture->GetHeight());
m_Vertices[5].SetTexCoord0((float)SrcRect.right / m_Texture->GetWidth(), (float)SrcRect.bottom / m_Texture->GetHeight());
}

if(!pClippingRect)
return true; // No clipping is wanted.

return VisibleRect.right - VisibleRect.left > 0 && VisibleRect.bottom - VisibleRect.top > 0;
}




This is called once per frame though, and I have recently redone the system. 2 things that should be done are adding dirty variables (so that the function will only change the vertices if the object has move/resized) and a z-value so that you know when one object is in front of another. This function also returns whether or not the object is within the clipping rect.

The last part is pretty advantageous. If you sort your lists by the z value, then you can pass the previous child's clipping rect to the current child's UpdateVisible() call (although, you want to test if its not visible in the clipping rect.)

HTH!

[Edited by - Programmer16 on April 20, 2006 2:19:34 AM]

Share this post


Link to post
Share on other sites
phb5000    122
Im thinking about adding one more feature to my current system which might make it faster:

Lets say I have two controls that are all children to the same control (in other words: they are all siblings). If I compare these controls to each other they can either be: Seperate, Intersecting, or Containing.

With Seperate and Containing I can conclude whether to show or hide a control. But with Intersecting (meaning: two controls intersect but do not block out eachother) one of the controls may be overlapping one of the other controls children. So, if two controls just intersect should I test the control with all of the other controls children. That seems "expensive".

I hope my explaination is understandable. Its kind of hard to explain


Seperate:
- Both controls need rendering
- Neither is being overlapped

------------- -------------
| | | |
| Control 1 | | Control 2 |
| | | |
------------- -------------


Intersecting:
- Control 1 is intersecting Control 2
- Control 2 still needs rendering
- *** Control 1 MAY be overlapping a child control in Control 2 ***

-------------
| |
| Control 1 |---------
| | |
-------------ntrol 2 |
| |
-------------


Containing:
- Control 1 is completely overlapping Control 2
- Control 2 doesnt need rendering
-------------
| |
| Control 1 |
| |
-------------




Share this post


Link to post
Share on other sites
Antheus    2409
Quote:
Original post by phb5000
Im thinking about adding one more feature to my current system which might make it faster:

Lets say I have two controls that are all children to the same control (in other words: they are all siblings). If I compare these controls to each other they can either be: Seperate, Intersecting, or Containing.

With Seperate and Containing I can conclude whether to show or hide a control. But with Intersecting (meaning: two controls intersect but do not block out eachother) one of the controls may be overlapping one of the other controls children. So, if two controls just intersect should I test the control with all of the other controls children. That seems "expensive".

I hope my explaination is understandable. Its kind of hard to explain


Seperate:
- Both controls need rendering
- Neither is being overlapped

------------- -------------
| | | |
| Control 1 | | Control 2 |
| | | |
------------- -------------


Intersecting:
- Control 1 is intersecting Control 2
- Control 2 still needs rendering
- *** Control 1 MAY be overlapping a child control in Control 2 ***

-------------
| |
| Control 1 |---------
| | |
-------------ntrol 2 |
| |
-------------


Containing:
- Control 1 is completely overlapping Control 2
- Control 2 doesnt need rendering
-------------
| |
| Control 1 |
| |
-------------


I used code tag for monospaced font.

If you want to do complete window rendering management, then it's best to go all the way. When a window needs to be redrawn, submit its rectangle to render manager. This one keeps track of dirty rectangles, areas which need to be redrawn.

In a typical system, you will have a property (opaque), which determines if a given control fully fills its area, or whether it has transparent, semi-transparent areas.

After that, you recursively traverse control's children, and calculate the intersection of dirty rectangle, and child control's rectangle. You will end up with several different cases. Every such case can split the intersection of dirty rectangle and your control's area into two (or 4 in special case of dirty rectangle being contained with child control) rectangles.

Then you pass these rectangles to the control, and tell it to repaint these sections.

Edit: The different option is to create a union of two child control and dirty rectangle, which simplifies intersection checks, but can result in unnecessary areas to be redrawn. It all depends on the nature of your UI.

Is this "expensive"? Depends. Operations can be extremly simplified, they only involve integer arithmetic, and even at that they are for most part just decision code. So they execute rather fast. In most cases, performing occlusion checks will be offset the cost of rendering.

For a more detailed description, look up various "dirty rectangle" or "window manager rendering" topics. Unfortunately I don't have any good ones handy right now.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
What kind of artwork are you using and how big is it?

Also how complex is your UI?

And how low is your "low" fps?

For most widgets I couldn't see a need for any more than two small pieces of art(an end cap and a stretchable fill which are reusable for each instance of the widget, and maybe even in other widgets). Your total art count should be low. If you are using huge bitmaps to represent all sorts of things (ie: a bitmap for an entire button, or other widget) I'd consider thinking about using smaller pieces of reusable art.

I also don't see much of a way that you'd need to render all that many quads that would require a fancy occlusion and clipping algorithm. Having a huge bitmap background kinda sucks a bit of performance, but there isn't much you can do about that (unless you can get away with using a solid colour for a background).

I'd say to look at optimizations that aren't so much code based for gui problems, especially since having a frame rate of at least 20 is good enough for it to feel right (provided there aren't any huge complex animations).

Share this post


Link to post
Share on other sites
phb5000    122
Well, the thing is that the system requires a quite high fps for the cursor to move smoothly and realisticly. Unless I find a better way for handling mouse input I going to have to keep the FPS at round 120 or higher.

Even though my GUI components are currently quite simple, when i start implementing complex controls (consisting of the base controls) the amount of work is going to increase a lot, and with animations the system becomes highly dependent on the fps.

If any one has any good techniques for rendering custom cursors then please let me know!

Share this post


Link to post
Share on other sites
silverphyre673    454
One thing you might want to consider is using a new thread just for the mouse, so that even if the rest of the application lags, the mouse will still move smoothly. I know I hate it when I play games and the mouse lags. Grrrr.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this