Thread: GetPixel, HDC, and heartattacks

  1. #1
    Registered User
    Join Date
    Jun 2003
    Posts
    361

    GetPixel, HDC, and heartattacks

    For those of you that've read some of my most recent posts, you'll know the little project I'm working on. Basically, I'm trying to get as many little Dudes (4x4 Blue Square) flying randomly across my screen. So far, with no collision detection, I've been able to display 300 Dudes at 75FPS, 500 at 50FPS, and 1000 at about 30FPS.

    My first collision detection method consisted of starting with the first Dude in my array, and seeing if he was within colliding distance with ALL Dudes above him in the array. The I'd check #2 with all Dudes above him, and so on. With 100 dudes, it was pretty much 100! checks. That method resulted in being able to have 100 Dudes at 75FPS, 200 Dudes at 45FPS, 1000 Dudes at 3FPS, and I gave up after about 3 minutes while waiting for the first frame of 80000 Dudes.

    These rates just don't cut it, so, my better idea is to check the 8 Pixels surrounding a Dude...

    - Each Dude travels in the X Direction at a maximum speed of 3 Pixels Per Frame.
    - Each Dude travels in the Y Direction at a maximum speed of 3 PPF.

    By checking the colour of merely 8 Pixels, I can reduce the number of checks from (for 100 Dudes):
    9.3 x (10^157) <-- Rounded down hugely
    to
    8.0 x (10^2)

    There is a problem with this new method that the two can still miss eachother, but just by looking at those two numbers, I'm willing to throw in a bit of extra code to fix that and get the performance improvement. (Incase you don't quite get what I'm saying, I drew a picture down below).

    Now, for the actual check, here's what I have:
    Code:
    My "Organism" Class:
    class cORGANISM
    {
    public:
    	cORGANISM(void)
    	{
    		hDC = CreateDC("DISPLAY", NULL, NULL, NULL);
    		m_pD3DDevice = NULL;
    		m_pTexture = NULL;
    		m_pSprite = NULL;
    	}
    
    	virtual ~cORGANISM(void)
    	{
    		DeleteDC(hDC);
    
    		if(m_pSprite != NULL)
    		{
    			m_pSprite->Release();
    			m_pSprite = NULL;
    		}
    
    		if(m_pTexture != NULL)
    		{
    			m_pTexture->Release();
    			m_pTexture = NULL;
    		}
    		
    		if(m_pD3DDevice != NULL)
    			m_pD3DDevice = NULL;
    	}
    	
    	HRESULT Initialise(IDirect3DDevice9 *pD3DDevice);
    	void StringActiveDudes(char *NumDudes);
    	void Render(void);
    private:
    	IDirect3DDevice9 *m_pD3DDevice;
    	IDirect3DTexture9 *m_pTexture;
    	ID3DXSprite *m_pSprite;
    
    	std::vector<cDUDE> Dude;
    	HDC hDC;
    };
    
    Each Dude gets the hDC passed to it inside the cDude::Collision() method:
    bool cDUDE::Collision(float X, float Y, HDC *hDC)
    {
    	unsigned long Colour;
    
    	if(*hDC == NULL)
    		return false;
    
    	for(int I = -4; I <= 4; I = I + 4)
    	{
    		for(int J = -4; J <= 4; J = J + 4)
    		{
    			if((I != 0)||(J != 0))
    			{
    				Colour = GetPixel(*hDC, (int)X+I, (int)Y+J);
    				if(Colour != CLR_INVALID)
    				{
    					if(Colour != 0xFF000000)
    					{
    						return true;
    					}
    				}
    				else
    				{
    					return false;
    				}
    			}
    		}
    	}
    	return false;
    }
    The problem is that Colour, in the Collision Detection method is always CLR_INVALID. Is there some mistake that I'm making with my code above that's spottable?

    Also, GetPixel doesn't seem to be the quickest of calls. My FrameRate actually seems to have suffered more since changing collision methods. But I'm hoping it has something to do with the actual hDC and I'm making an error somewhere along the way that's just muddling things up.

    (And incase it makes a difference, my window was created with the "CS_OWNDC" style, way back when registering the WNDCLASS object).

    If you've managed to make it all the way down here, wow As always, any advice or comments are appreciated.
    Last edited by Epo; 12-18-2004 at 06:17 PM.

  2. #2
    Linguistic Engineer... doubleanti's Avatar
    Join Date
    Aug 2001
    Location
    CA
    Posts
    2,459
    For the get-pixel routine, you may try the following speed up:

    If you have direct memory access to the video buffer (which I assume you don't, but windows GFX is not my platform, DOS is, and we do have it), you can write your own get-pixel routine. Actually it may not be a routine so much as a define macro for a pointer reference (which is what makes it fast, you don't have to put stuff on the stack, it is inlined as the code works).

    Otherwise, I don't see any ways your particles could pass 'through' eachother within the +3 border you have described.

    Nice pictures, very solid post. I just hope mine is the same...

    Also, again I'm no windows or DX buff, but is it absolutely necessary to check for CLR_INVALID?
    hasafraggin shizigishin oppashigger...

  3. #3
    Registered User
    Join Date
    Jun 2003
    Posts
    361
    Otherwise, I don't see any ways your particles could pass 'through' eachother within the +3 border you have described.
    On second thought, right you are . I was thinking that if the two Dudes were travellling head-on, both at 3 Pixels Per Frame, then they could technically be positioned (as in the picture) such that in the next frame, they would actually be inside of eachothers' collision boundaries. But, there is no possible way for them to get in AND out without being detected, so that is actually a little more comforting; though I may throw in a few more pixel checks after just to be able to catch each one the first time around.

    but is it absolutely necessary to check for CLR_INVALID?
    It isn't absolutely necessary, it's more of my debugging strategy at the moment. GetPixel returns CLR_INVALID if the attempt was made outside the clipping region. So apparently all of my calls are being made outside of the clipping region, which doesn't make much sense.

    If the check uses this instead:
    Code:
    Colour = GetPixel(*hDC, (int)X+I, (int)Y+J);
    
    if(Colour != 0xFF000000)
    {
    	return true;
    }
    Then all my Dudes just stay still, even if nobody is around them, because apparently they are not on a black backround (which they most definitely are)

    If you have direct memory access to the video buffer (which I assume you don't, but windows GFX is not my platform, DOS is, and we do have it), you can write your own get-pixel routine. Actually it may not be a routine so much as a define macro for a pointer reference (which is what makes it fast, you don't have to put stuff on the stack, it is inlined as the code works).
    This one I'm not sure if I do or don't. Never really had to think about this until this very moment . I would assume so (well, I hope so anyways), but perhaps somebody with a bit more experience could tell me if I do? I would drop GetPixel in a heartbeat if this was the case. The key thing I need is speed, and I'm willing to try most anything to improve it.

    In the meantime I'll Goggle around a bit and see if anything comes up on the direct memory access idea.

    Thanks for the suggestions and thoughts doubleanti.

  4. #4
    Registered User
    Join Date
    Apr 2002
    Posts
    1,571
    GetPixel/SetPixel are some of the slowest calls out there. What you want to do is create a bitmap the size of your screen and then write/read to this bitmap. Also, this should be stored in a memory dc as an offscreen/back buffer surface. Then once all your rendering is done you blt it to your primary DC. To create the memory dc use CreateCompatibleDC. If you have any other questions about the methods let me know. Maybe if you want I can just write a sample program if you get too stuck.
    "...the results are undefined, and we all know what "undefined" means: it means it works during development, it works during testing, and it blows up in your most important customers' faces." --Scott Meyers

  5. #5
    Registered User
    Join Date
    Jun 2003
    Posts
    361
    Hm, that does sound a bit beyond me at the moment. But I'll give it a go (Google and MSDN are usually fairly kind) and when I have something to show for, I'll post it here for improvements. I appreciate the offer though MrWizard, I might take you up on it if I find that I'm in over my head right from the get go and can't figure out where to even start. But I'll give it a shot first. Thanks for the leads MrWizard, hopefully I'll have something worthwhile to show off here in the next couple of days.

  6. #6
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Actually the best way to go about doing collision detection like that is to use a quad tree algo or a BSP algo. However for pure 2D grids quad trees work much better.

    Essentially generate all of your dudes. Now build your starting quadtree from that.

    Here is the idea of a quadtree. Start with a large area or large square. Split into 4 smaller squares. Split until desired resolution is reached or no more splitting can be done. This is the leaf. Place all objects that are inside of this square or bounding area in the leaf. Do this for the entire scene or world.

    Now when you search do this:

    Start at the root of the tree.
    Move down into the tree until you reach a leaf. Check all those objects against each other for collision. Repeat for each bounding area in your scene or world.

    To illustrate I'll show some code that will draw boxes on the screen in a quad tree fashion. DrawBox() is simply a function that draws a solid colored square to the screen.


    Code:
    void QuadTreeDemo(int depth,int left,int top,int right,int bottom,RGBA color)
    {
      if (depth<1) return;
     
      //For actual tree code would look like this
      //if (depth<desired_depth) { AddObjectsToLeaf();return; }
     
     
      mid_horiz=(left+right)>>1;
      mid_vert=(top+bottom)>>1;
     
      //Draw square for this recursion
      DrawBox(left,top,right,bottom,color);
     
      //Recurse into upper left
      QuadTreeDemo(depth-1,left,top,mid_horiz,mid_vert,color);
      
      //Recurse into upper right
      QuadTreeDemo(depth-1,mid_horiz,top,right,mid_vert,color);
     
      //Recurse into lower left
      QuadTreeDemo(depth-1,left,mid_vert,mid_horiz,bottom,color);
     
      //Recurse into lower right
      QuadTreeDemo(depth-1,mid_horiz,mid_vert,right,bottom,color);
    }
    This is a log(n) algorithm and is very fast at VSD and collision detection.

  7. #7
    Linguistic Engineer... doubleanti's Avatar
    Join Date
    Aug 2001
    Location
    CA
    Posts
    2,459
    So, then, with Mr. Wizard's suggestion about using back buffers, and Bubba's log(n) algorithm for collision detection, you should be up and running (or your dudes at least) in no time.

    A couple of finer points.

    First, if you are using a back buffer, an option for you would be to use a base data type where the alignment is the size of a word on your computer, ie 32-bits. If doing this, for example, with a 5:6:5 16-bit format, you gather a lot of overhead in the conversion, which you can avoid (and probably already do) given the gfx mode.

    Secondly, for the quad trees, it should be noted that it works best for width and height (not necessarily equal) which are powers of 2, ie 2, 4, 8, 16, 32, and so forth. You may figure that this limits the size of your world to this discrete set of values. It does, however if you wish to implement a wrap-around world, you may back-buffer grids of your world on this alignment without having to worry about your dudes 'falling off the edge', meaning you save on bounds checking. However, logically it would incur that if your wrapped world is not of a power of 2 in height and length, you would have a sort of duplication of effort, which I would think would be hard to recognize and eliminate.

    We await your questions... =)
    hasafraggin shizigishin oppashigger...

  8. #8
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    There are also some more advanced things you can do as well.

    You can really narrow down which organisms need to be checked using several techniques.

    Dot product of velocity vectors
    If you take the dot product of the two velocity vectors and they are less than zero then you know that those objects are NOT approaching each other since the angle between the vectors is obtuse.

    Range
    You can find the distance between two organisms and work in terms of the square of the distance. There is no need to take the square root. If the organism does not fall within the range...don't check it.

    I would suggest the following program flow for collision detection.

    1. Recurse into Quad tree till you find correct leaf for nearest objects.
    2. Iterate through nearest objects and do range check, store in list.
    3. Iterate through list created in step 2 and do dot product check, store in a list.
    4. Iterate through list created in step 3 and do the expensive collision test.

    This method will guarantee that only objects that could possibly be in danger of colliding will be checked. It will eliminate all other objects from the expensive testing. Your range check can also be incorporated into the quad tree.

    Code:
     
    void HitCheck(COrganism &pSourceOrganism,QuadTree *pTree,DWORD dwSize,DWORD dwRange)
    {
    CVector2 vVel;
    CVector2 vPos;
     
    std::vector<COrganisms *> pOrganismList;
    std::vector<COrganisms *>::iterator iterOrganism;
     
    FindLeafObjects(pTree,dwSize,pOrganismList);
     
    iterOrganism=pOrganismList.begin();
     
    DWORD dwX,dwY;
     
    while (iterOrganism!=pOrganismList.end())
    {
    	Pos=iterOrganism->vPosition-pSourceOrganism.vPos;
    	dwX=(DWORD)(vPos.x*vPos.x);
    	dwY=(DWORD)(vPos.y*vPos.y);
     
    	//Range check
    	DWORD length=dwX+dwY;
    	if (length>dwRange) pOrganismList.erase(iterOrganism);
     
    	//Dot product check
    	vVel=iterOrganism->vVelVector;
    	vVel.x*=pSourceOrganism.vPos.x;
    	vVel.y*=pSourceOrganism.vPos.y;
    	float fDot=vVel.x+vVel.y;
     
    	if (fDot<0) pOrganismList.erase(iterOrganism);
    }
     
    //Now list has been culled correctly - check collisions
    CheckCollisions(pOrganismList);
    }

    Something like that. I wrote this while sitting here so it prob has errors, but I hope it illustrates the concept.
    Last edited by VirtualAce; 12-19-2004 at 03:09 PM.

  9. #9
    Registered User
    Join Date
    Jun 2003
    Posts
    361
    Alrights, after making a half-working bitmap version that MrWizard suggested, I realized that with that method, I can't really tell which Dude is colliding with which Dude.

    While there would be ways around this, I think it'll complicate things a lot less if I revert to checking Dudes against eachother and implement this Quadtree.

    I just want to make sure I understand this Quadtree fully, because it sounds a lot like a method I attempted before, but there were some issues that arose.

    So, pretty much, I just divide the screen into a number of smaller regions, and each region keeps track of which Dudes are contained in it. (In the picture below, it would be a 1x1 region). And each of those would be one Leaf, so 64 Leaves in my example there.

    Then, each turn (before optimization), if I had 50 guys, instead of having to do 49! checks, each Leaf only checks the Dudes within it. So Leaf(1, 1) has two guys, so it would check only those two. Leaf(5, 8) has 5 Dudes, so it would check 4! times. And so on?



    Secondly, for the quad trees, it should be noted that it works best for width and height (not necessarily equal) which are powers of 2, ie 2, 4, 8, 16, 32, and so forth.
    I'm wondering if there's a certain limit to the depth that the screen should be divided into though. I would assume that breaking up the screen into too many pieces would hinder the process eventually...

    EDIT
    Oh shoot, I misread that statment. The question above is what I'm wondering still though.

    There are also some more advanced things you can do as well.
    Thanks for the tips Bubba.

    The Dot Product will be tricky since the Dudes can technically be approaching eachother at any time though, given that the world wraps around. Discarding checks based on that could result in Dudes at the edge of the screen miss a collision with a Dude coming in from the other side of the screen at the same time. A bit of an additional check could be done to avoid this though, because I see how this could remove lots of potentially useless checks.

    Thanks for all of the feedback everyone. It's been plenty helpful. I guess, right now, my biggest question is if I'm understanding the Quadtree properly?




    BIG EDIT
    I think my math's been way off. If there are 50 Dudes, it isn't 49! checks is it? It would be 49+48+...+3+2+1 checks.
    Last edited by Epo; 12-20-2004 at 10:28 PM.

  10. #10
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    If you have 50 dudes and you are doing a linear check the actual amount of checks is 50*49 since checking the same dude against himself is ludicrous

    Code:
    for (int i=0;i<numDudes;i++)
    {
    for (int j=0;j<numDudes;j++)
    {
    //Dont check if we hit ourself
    if (i==j) break;
    bool Hit=CheckHit(Dude[i],Dude[j]);
    }
    }
    Your understanding of the quadtree is correct. I will show you why it's so fast.

    Given your picture, let's say that the dude we are wanting to check is in cell 1,1. Now the only dude's we need to really check for collision are those that satisfy the following:

    1. They must be in our cell.
    2. They must be moving towards us.
    3. They must be within range.

    Ok so we do our quadtree recursion. Our first recursion would split the playing field into 4 pieces - the vertical line at 4 and the horizontal line at 4. Now we have 4 quadrants. So we label these 0,1,2,3 from left to right, top to bottom. Ok our dude does fall within the boundaries of quadrant 0 or the upper left quadrant. So we can automatically discard 1,2 and 3. Notice on the map how many 'dude' checks we just eliminated. A whole bunch.

    Now our map looks like this - I've grayed out the quadrants that will not be checked and I've circle the dude we are using as our guy to check against.

  11. #11
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    That is what the map looks like after 1 recursion. Okay now for recursion 2. Again we split the white part into 4 equal quadrants again and check. We will label them 0,1,2,3 again. Well we know of course that our dude is still in quadrant 0, so we can discard 1,2 and 3 again. Now here is what it looks like.

    The darker areas are what we discarded in recursion level 1 or in step 1 above.
    The lighter shaded areas are what we are discarding now.
    The white areas are still valid areas that we need to check.

  12. #12
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Ok now we do the same thing. Split our white area into 4 quadrants and check where our dude is. Label them 0,1,2,3 and we find he is on quadrant 0. So we discard 1,2,3 again. Here is what it looks like now.

  13. #13
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Okay we have probably reached a good depth now. Notice that you have already done the splitting and such when you created the quadtree. But I'm illustrating what is happening as you move down into the tree based on your dude's position. You are discarding a whole lot of dudes and therefore a whole lot of checks.

    So we started with checking 1 dude against 49 other dudes. But since we are using a quadtree algo you can see that after just 3 recursions or 3 levels into the tree we have reduced our checks from 49 to 1. There is only 1 other guy in our quadrant.

    Now we need to check if that guy is moving towards us. If he isn't - he isn't going to hit us and so we don't need to check. We increment the dude we need to check against which would now be dude 2. But if dude2 just happens to be the guy we checked when we were dude1 (the circle would be around the other guy in our quadrant) then we know from our check with dude1 that dude2 and dude1 are not colliding. So we skip dude2 because he isn't going to hit anybody. So we have checked 2 guys now and never even performed the expensive test, yet we have deduced that they are not colliding. Do this for all dudes on the map and your framerates should increase dramatically.

    An easy way to 'track' which guys have been tested against each other is to use a vector or an STL map or you can use a stack.
    Last edited by VirtualAce; 12-21-2004 at 12:55 AM.

  14. #14
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    The hard part of the algo is when you have dudes:

    1. Partially inside of 2 quadrants or on a border between quadrants.
    2. Dudes that collide across quadrant boundaries.

    These checks really hurt the algo a lot because you must move back up in the tree or even start at the root again to correctly check the 2 dudes.

  15. #15
    Registered User
    Join Date
    Jun 2003
    Posts
    361
    Bubba...you're the man.

    That definitely clears up everything I was wondering when it comes to the Quadtree.

    For your collision check code though...
    Code:
    for (int i=0;i<numDudes;i++)
    {
    	for (int j=0;j<numDudes;j++)
    	{
    	//Dont check if we hit ourself
    	if (i==j) break;
    	bool Hit=CheckHit(Dude[i],Dude[j]);
    	}
    }
    Which requires the 10x9 checks for 10 Dudes...
    Could that be optimized to something like:
    Code:
    for (int i = 0; i < numDudes - 1; i++)
    {
    	//If Dude[0] checks with Dude[1]
    	//Then Dude[1] Shouldn't have to check with Dude[0]
    	for (int j = i + 1; j < numDudes; j++)
    	{
    	bool Hit=CheckHit(Dude[i],Dude[j]);
    	//Make sure to update both Dude[i] and Dude[j]
    	//if there is a collision
    	}
    }
    This is where my 10+9+8+...+3+2+1 number came from. Which would cut the number of checks in half.

    The problems you mentioned with the Quadtree:
    1. Partially inside of 2 quadrants or on a border between quadrants.
    2. Dudes that collide across quadrant boundaries.
    Were the very ones that turned me away from it in the first place. I've been drawing out some pictures recently, and I'm wondering what the thoughts are out there on a Nontree.

    Note: 3 more posts to follow with pictures

    Essentially, it's the same as the Quadtree, but with a few more divisions. I would think that it would be a touch slower, but now the distance/dot product checks can be implemented whenever, without fear of having to check for special cases such as two Dudes crossing a boundary at the same time or about to wrap around the world and hit eachother. Given that, I think the loss of speed would be minimal though, but, well, you tell me your thoughts.

    Say you start off with a screen of Dudes such as this. (The circled Dude is the one that will be checked).

Popular pages Recent additions subscribe to a feed