Cool Idea - Implementation?

The Partridge Family were neither partridges nor a family. Discuss.
MagicFlyingGoat
Posts: 20
Joined: April 17th, 2014, 4:13 am

Cool Idea - Implementation?

Post by MagicFlyingGoat » July 17th, 2014, 12:02 am

So i had a cool idea to make the loading of keyed sprites much more efficient, the idea is that you create a surface of structs, each with an x,y pos and color. And instead of checking through to see which pixels should be skipped each time you draw, you instead only load the required pixels into the surface in the first place, and then draw them according to their x,y and color values. My only problem with this is i can't pre calculate the size of the array required to hold the pixels. It's not a massive problem but i am trying to make the code nice and optimized and that overhead bothers me.

PixelData Struct

Code: Select all

struct PixelData {
		int x;
		int y;
		D3DCOLOR color;
	};
Some code i wrote to handle the loading onto the surface

Code: Select all

surface = new PixelData[height * width];

if(colorkey) {
	unsigned int index = 0;
	for( unsigned int y = 0; y < bitmap.GetHeight(); y++ )
	{
		for( unsigned int x = 0; x < bitmap.GetWidth(); x++ )
		{
			bitmap.GetPixel( x,y,&pixel );
			if(D3DCOLOR_ARGB( pixel.GetA(),pixel.GetR(),pixel.GetG(),pixel.GetB() ) != colorkey) {
				PixelData c;
				c.x = x;
				c.y = y;
				c.color = D3DCOLOR_ARGB( pixel.GetA(),pixel.GetR(),pixel.GetG(),pixel.GetB() );
				surface[index] = c;
			}
		}
	}
}


My only idea is that i can do another loop first to check how many pixels there will be but i think that there is probably a much better solution, so any ideas would be appreciated

cameron
Posts: 794
Joined: June 26th, 2012, 5:38 pm
Location: USA

Re: Cool Idea - Implementation?

Post by cameron » July 17th, 2014, 12:25 am

Can I get the whole surface.h?
Computer too slow? Consider running a VM on your toaster.

MagicFlyingGoat
Posts: 20
Joined: April 17th, 2014, 4:13 am

Re: Cool Idea - Implementation?

Post by MagicFlyingGoat » July 17th, 2014, 12:47 am

i don't think it will be very helpful, its more the concept im struggling with, not the code. but here it is anyway:

(ovbiously not quite finished)

Code: Select all

#pragma once

#include "D3DGraphics.h"
#include <string>
#include <GdiPlus.h>
#pragma comment( lib,"gdiplus.lib" )

class EmbedSprite {
private:
	struct PixelData {
		int x;
		int y;
		D3DCOLOR color;
		PixelData* pNextPixel;
	};
public: 
	EmbedSprite(const std::wstring filename, D3DCOLOR colorkey = NULL) {
		Gdiplus::GdiplusStartupInput gdiplusStartupInput;
		ULONG_PTR gdiplusToken;
		Gdiplus::GdiplusStartup( &gdiplusToken,&gdiplusStartupInput,NULL );

		Gdiplus::Bitmap bitmap( filename.c_str() );
		Gdiplus::Color pixel;

		height = bitmap.GetHeight();
		width = bitmap.GetWidth();

		surface = new PixelData[height * width];

		if(colorkey) {
			unsigned int index = 0;
			for( unsigned int y = 0; y < bitmap.GetHeight(); y++ )
			{
				for( unsigned int x = 0; x < bitmap.GetWidth(); x++ )
				{
					bitmap.GetPixel( x,y,&pixel );
					if(D3DCOLOR_ARGB( pixel.GetA(),pixel.GetR(),pixel.GetG(),pixel.GetB() ) != colorkey) {
						PixelData c;
						c.x = x;
						c.y = y;
						c.color = D3DCOLOR_ARGB( pixel.GetA(),pixel.GetR(),pixel.GetG(),pixel.GetB() );
						surface[index] = c;
					}
				}
			}
		}	
	}
private:
	int width;
	int height;
	PixelData* surface;
};

cameron
Posts: 794
Joined: June 26th, 2012, 5:38 pm
Location: USA

Re: Cool Idea - Implementation?

Post by cameron » July 17th, 2014, 2:17 am

My only problem with this is i can't pre calculate the size of the array required to hold the pixels.
so here is what I think:
1)create temp std::list
2)push back if color != key
3)delete surface and reallocate with Pixel Data number of elements = list.size()
5)iterate through list and copy data from list to array
6)list.clear();

There are several other ways to do it, but this is the easiest way I can think of.
Computer too slow? Consider running a VM on your toaster.

MagicFlyingGoat
Posts: 20
Joined: April 17th, 2014, 4:13 am

Re: Cool Idea - Implementation?

Post by MagicFlyingGoat » July 17th, 2014, 4:21 am

Not a bad idea, but I don't like the idea of deleting and creating the arrays especially if I'm doing this a lot of times, moving a lot of data around like can take awhile. However I have thought of adding a pointer to the structure and making a linked list, I think that would work very well. and is very helpful because then I don't need to precalc the size and I only need to access them in order anyway, I'm working on it now and i'll see how it goes

User avatar
LuisR14
Posts: 1248
Joined: May 23rd, 2013, 3:52 pm
Location: USA
Contact:

Re: Cool Idea - Implementation?

Post by LuisR14 » July 17th, 2014, 4:40 am

this is a pretty nice idea :)
well i have my own thoughts about doing this, which would involve using a pointer to pointer
here's what i came up with

Code: Select all

PixelData** pPxl = &surface;

if(colorkey) {
	for( unsigned int y = 0; y < bitmap.GetHeight(); y++ )
	{
		for( unsigned int x = 0; x < bitmap.GetWidth(); x++ )
		{
			bitmap.GetPixel( x,y,&pixel );
			if(D3DCOLOR_ARGB( pixel.GetA(),pixel.GetR(),pixel.GetG(),pixel.GetB() ) != colorkey) {
				PixelData*& p = *pPxl;
				p = new PixelData;
				p->x = x;
				p->y = y;
				p->color = D3DCOLOR_ARGB( pixel.GetA(),pixel.GetR(),pixel.GetG(),pixel.GetB() );
				p->pNextPixel = nullptr;
				pPxl = &p->pNextPixel;
			}
		}
	}
}
(i used reference to pointer in inner loop just to not have to do (*pPxl)-> for every line hehe :p)

cameron's idea would work too (tho he didn't really mean reallocate every time but just when whole image's pixel data has been retrieved xP)
always available, always on, about ~10 years c/c++, java[script], win32/directx api, [x]html/css/php/some asp/sql experience. (all self taught)
Knows English, Spanish and Japanese.
[url=irc://irc.freenode.net/#pchili]irc://irc.freenode.net/#pchili[/url] [url=irc://luisr14.no-ip.org/#pchili]alt[/url] -- join up if ever want real-time help or to just chat :mrgreen: --

MagicFlyingGoat
Posts: 20
Joined: April 17th, 2014, 4:13 am

Re: Cool Idea - Implementation?

Post by MagicFlyingGoat » July 17th, 2014, 6:29 am

thanks Luis, my final product looks a fair bit like yours ^^. Yeah i understood what Cameron meant and i meant to say that if i was making a lot of sprites, i'd have to do it a lot of times, not necessarily lots of times per sprite, that would be ridiculously inefficient haha. But thanks for the help, i appreciate it :D

The only slight problem i have with that code is that you use an array to access the linked list, which just seems a little redundant to me, i just stored the data of the last pixel and then changed the pointer and the overwrote the last pixel data with the current pixel. I personally like that better, but i can see why you did it your way ;)

User avatar
LuisR14
Posts: 1248
Joined: May 23rd, 2013, 3:52 pm
Location: USA
Contact:

Re: Cool Idea - Implementation?

Post by LuisR14 » July 17th, 2014, 7:08 am

MagicFlyingGoat wrote:The only slight problem i have with that code is that you use an array to access the linked list
umm, i never used an array there o.O, tis just pointers :p
always available, always on, about ~10 years c/c++, java[script], win32/directx api, [x]html/css/php/some asp/sql experience. (all self taught)
Knows English, Spanish and Japanese.
[url=irc://irc.freenode.net/#pchili]irc://irc.freenode.net/#pchili[/url] [url=irc://luisr14.no-ip.org/#pchili]alt[/url] -- join up if ever want real-time help or to just chat :mrgreen: --

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Cool Idea - Implementation?

Post by chili » July 17th, 2014, 12:50 pm

Interesting idea, it's always fun to think of ways to speed things up. Not sure if this will actually give you a boost though. Make sure you do some benchmarking to figure out the relative performance.
Chili

stagephrite
Posts: 5
Joined: June 20th, 2014, 1:53 pm

Re: Cool Idea - Implementation?

Post by stagephrite » July 17th, 2014, 3:54 pm

I'd use unsigned shorts(or signed shorts if you feel you need the negative values) to store the x and y in pixeldata, a range of 0 - 65,535(for unsigned) or –32,768 to 32,767(for signed) should be more than enough and you'll be saving 4 bytes of memory per pixel.

Post Reply