What are you working on? v16

[knighty]

[QUOTE=Matte;28408013]The game, using the world in the picture, uses about 550 000 K. That's 750 chunks. If I increase the world to 3800 chunks, it uses 1 200 000 K. The chunks are memory killers, though, we are doing what we can to replace redundant integers with shorts and bytes as we go.

The world in the picture has 471380 faces (each have 4 vertices), an example 3800-chunk world renders 1426245 faces. Those are just example numbers. The face count varies with the seed of the map.

Here is a picture of a random 3800-chunk map. The radius is 9 chunks.

[img_thumb]http://i747.photobucket.com/albums/xx120/Azzi777/Untitled3.png[/img_thumb][/QUOTE]

I suspected it'd be huge. I imagine most of the cost is in the vertex buffers though. A 32x32x32 chunk is only 32kb (You ought to be using bytes for this). 8x8x8 of them adds up to 16mb. I don;t know how many chunks you have but I can't imagine they add up a lot themselves. However the vertex buffers are gonna be huge. 2 million vertices, where I assume you have positions, normals and uvs are going to add up to 64mb.

Some ideas for decreasing size: Smaller vertices. No idea what you're currently using, but since your world is quantized you can easily get away with 16bit positions. Normals are one of 3 directions, so can be packed into a single byte, and uvs should be easily compressable too.

Run length encoding for chunks too. Will make it hard to index into but since you probably only iterated over it for the VB, it should be doable.

edit: It just occured to me you probably don't have normals anyway. So ignore that.

edit2: Hadn't realised you'd posted exact counts. 750 * 32 * 32 * 32 = 24mb if each block is 8bits. How on earth have you managed to use 550mb? :P

[yakahughes]

[QUOTE=ThePuska;28408290]Well you could create a temporary array of all the pointers in the linked list and then iterate through the array in an inverse order.[/QUOTE]

That would be pretty horribly inefficient.

[Jallen]

[QUOTE=yakahughes;28408435]That would be pretty horribly inefficient I think.[/QUOTE]

I'll tell you what's horrible.
The irony in that you posted a recursive solution. It has the exact same memory usage :downs:

[yakahughes]

[QUOTE=Jallen;28408470]I'll tell you what's horrible.
The irony in that you posted a recursive solution. It has the exact same memory usage :downs:[/QUOTE]

Wouldn't it be better to go over every item once rather than twice? I wasn't referring to memory efficiency.

[Jallen]

[QUOTE=yakahughes;28408514]Wouldn't it be better to go over everything once rather than twice? I wasn't referring to memory efficiency.[/QUOTE]

If you count the actual number of instructions it's going to be almost exactly identical. The fact that there are two loops isn't relevant.
The only difference between having 2 loops in a row and doing 2 things in one loop is the latter will interlace the tasks.

So lern 2 computer science before you rate me dumb.

[yakahughes]

[QUOTE=Jallen;28408584]If you count the actual number of instructions it's going to be almost exactly identical. The fact that there are two loops isn't relevant.
The only difference between having 2 loops in a row and doing 2 things in one loop is the latter will interleave the tasks.

So lern 2 computer science before you rate me dumb.[/QUOTE]

The loop is a task in itself, so combining two tasks in one loop is better than performing one task each in two loops. You can rate me dumb too, it's a dumbfest.

[knighty]

I don't see any good reason to do anything other than what yakahughes originally posted.....

Jallen, I haven't used an std::stack before but I would assume it's going to be allocating a lot of memory dynamically just to create a stack to then delete stuff from.

[Jallen]

[QUOTE=yakahughes;28408633][B]The loop is a task in itself[/B]. You can rate me dumb too, it's a dumbfest.[/QUOTE]

You're looking at an extra n boolean comparisons here really. The effect is negligible and nowhere near as stupid as relying on the stack to not overflow with a list of arbitary size.

[editline]3rd March 2011[/editline]

[QUOTE=knighty;28408649]I don't see any good reason to do anything other than what yakahughes originally posted.....

Jallen, I haven't used an std::stack before but I would assume it's going to be allocating a lot of memory dynamically just to create a stack to then delete stuff from.[/QUOTE]

The difference is that if you have a massive list, an std::stack won't overflow.

[knighty]

[QUOTE=Jallen;28408667]You're looking at an extra n boolean comparisons here really. The effect is negligible and nowhere near as stupid as relying on the stack to not overflow with a list of arbitary size.[/QUOTE]

That's a good point. I suppose the question here is how arbitrary is the list size....

[ThePuska]

Would something like this reverse the linking direction of a linked list with minimal memory consumption?

[cpp]
void reverse(Node* list)
{
Node* _prev = 0, _next, current = list;
while (current)
{
_next = current->next;
current->next = _prev;
_prev = current;
current = _next;
}
}
[/cpp]

It'd finish with _prev holding the last (now first) node of the list. You could then iterate through it in a backwards order. And then revert the direction again, if you need to.

edit: Bad code

[Matte]

[QUOTE=knighty;28408354]I suspected it'd be huge. I imagine most of the cost is in the vertex buffers though. A 32x32x32 chunk is only 32kb (You ought to be using bytes for this). 8x8x8 of them adds up to 16mb. I don;t know how many chunks you have but I can't imagine they add up a lot themselves. However the vertex buffers are gonna be huge. 2 million vertices, where I assume you have positions, normals and uvs are going to add up to 64mb.

Some ideas for decreasing size: Smaller vertices. No idea what you're currently using, but since your world is quantized you can easily get away with 16bit positions. Normals are one of 3 directions, so can be packed into a single byte, and uvs should be easily compressable too.

Run length encoding for chunks too. Will make it hard to index into but since you probably only iterated over it for the VB, it should be doable.

edit: It just occured to me you probably don't have normals anyway. So ignore that.

edit2: Hadn't realised you'd posted exact counts. 750 * 32 * 32 * 32 = 24mb if each block is 8bits. How on earth have you managed to use 550mb? :P[/QUOTE]

Thanks for the input. Appreciate it a lot.

We are actually using shorts for the blocks (8 bit = type, 8 = data, states etc), we're discussing using bytes now, as the gains would probably be quite huge.

The vertices could probably be shortened a considerable amount, looking into that.

I will also look into run-length encoding, though indexing could probably be problem here.

I just went over the chunk class and discovered some arrays that weren't supposed to be there... Duh. Cleaning up the code now. It should probably use a lot less memory.

[Jallen]

[QUOTE=ThePuska;28408734]Would something like this reverse the linking direction of a linked list with minimal memory consumption?

[cpp]
void reverse(Node* list)
{
Node* _prev = null, _next, current = list;
while (current)
{
_next = current->next;
current->next = _prev;
_prev = current;
current = current->next;
}
}
[/cpp]

It'd finish with _prev holding the last (now first) node of the list. You could then iterate through it in a backwards order. And then revert the direction again, if you need to.[/QUOTE]

I see what you're doing but when I try to follow that...

:psyboom:

It's the sort of thing you need to draw a picture for I think, with arrows and circles n shit.

[ThePuska]

[QUOTE=Jallen;28408812]I see what you're doing but when I try to follow that...

:psyboom:

It's the sort of thing you need to draw a picture for I think, with arrows and circles n shit.[/QUOTE]

I noticed an error in it, see the edited version if you want to understand it

[knighty]

[QUOTE=Matte;28408742]Thanks for the input. Appreciate it a lot.

We are actually using shorts for the blocks (8 bit = type, 8 = data, states etc), we're discussing using bytes now, as the gains would probably be quite huge.

The vertices could probably be shortened a considerable amount, looking into that.

I will also look into run-length encoding, though indexing could probably be problem here.

I just went over the chunk class and discovered some arrays that weren't supposed to be there... Duh. Cleaning up the code now. It should probably use a lot less memory.[/QUOTE]

Have you considered instancing the faces? I really want to do a voxel engine like this of my own, and the way I've decided I'd do it in my head is like so:

Have a basic face which has coordinates 0,0; 0,1; 1,0; 1,1.
Instance that face like you usually would
The data buffer contains a packed variable that indicates the direction of the face (up,right,forward) and reorientates the face in the vertex shader.

I can't think of a particularly more memory/draw call efficient method than that.

[yakahughes]

[QUOTE=ThePuska;28408734]Would something like this reverse the linking direction of a linked list with minimal memory consumption?

[cpp]
void reverse(Node* list)
{
Node* _prev = 0, _next, current = list;
while (current)
{
_next = current->next;
current->next = _prev;
_prev = current;
current = _next;
}
}
[/cpp]

It'd finish with _prev holding the last (now first) node of the list. You could then iterate through it in a backwards order. And then revert the direction again, if you need to.

edit: Bad code[/QUOTE]
[cpp]
void reverse(Node*& list)
{
Node* _prev = 0, *_next, *current = list;
while (current)
{
_next = current->next;
current->next = _prev;
_prev = current;
current = _next;
}

list = _prev;
}
[/cpp]

There's the fixed and working code.

So we have three ways, recursion which can overflow if the list is big enough but is, in my opinion, the most elegant solution, then the copy everything to an array way, then the reverse the list and iterate it then reverse it again way, which is the most memory efficient.

Any other ways?

[Jallen]

Hmm. Well you're always going to need a way back, so if there are any others I can't imagine they would be very different or have any real performance benefits.

[DevBug]

[QUOTE=Jallen;28408295]

void delete_backwards(Node* List)
{
	std::stack<Node*> ptrStack;
	Node* current = List;
	while(current)
	{
		ptrStack.push(current);
		current = current->next;
	}

	while(ptrStack.size() != 0)
	{
		delete ptrStack.top();
		ptrStack.pop();
	}
}
		

[editline]3rd March 2011[/editline]

Ninjad while I was writing shit. Damn.[/QUOTE]

That defeats the purpose, he might as well use an external library if he is using C++.

[Jallen]

[QUOTE=DevBug;28409813]That defeats the purpose, he might as well use an external library if he is using C++.[/QUOTE]

I used std::stack because it's a known standard interface. Anybody can make a templated stack class in 15 minutes.

[DevBug]

[QUOTE=Jallen;28409836]I used std::stack because it's a known standard interface. Anybody can make a [b]templated[/b] stack class in 15 minutes.[/QUOTE]

Just use something like [url=http://www.boost.org/doc/libs/1_35_0/doc/html/intrusive/slist.html]Boost's slist[/url]

[TerabyteS]

Today I was bored so I took my game of life, tore it apart and made a maze generator out of it.

[img]http://dl.dropbox.com/u/2951174/c%2B%2B/zupe.png[/img]
Takes the guy around 40 seconds to generate this^

The fun part is when you make it do crazy shit
[img]http://dl.dropbox.com/u/2951174/c%2B%2B/gen.png[/img]

It's actually still working on that one.

I can explain the algorythm if anyone would like.

[Bang Train]

[QUOTE=Matte;28408742]Thanks for the input. Appreciate it a lot.

We are actually using shorts for the blocks (8 bit = type, 8 = data, states etc), we're discussing using bytes now, as the gains would probably be quite huge.

The vertices could probably be shortened a considerable amount, looking into that.

I will also look into run-length encoding, though indexing could probably be problem here.

I just went over the chunk class and discovered some arrays that weren't supposed to be there... Duh. Cleaning up the code now. It should probably use a lot less memory.[/QUOTE]

depending on compiler/architecture/OS, things will become byte aligned (typically 4)

so a byte byte int is same memory as int int , byte int byte is int int int....

so ordering does matter... keep that in mind

edit: applys for structs for sure...not sure how the compiler deals with class member vars and laying them out in memory

[Samperson123]

[QUOTE=TerabyteS;28410789]Today I was bored so I took my game of life, tore it apart and made a maze generator out of it.

[img_thumb]http://dl.dropbox.com/u/2951174/c%2B%2B/zupe.png[/img_thumb]
Takes the guy around 40 seconds to generate this^

The fun part is when you make it do crazy shit
[img_thumb]http://dl.dropbox.com/u/2951174/c%2B%2B/gen.png[/img_thumb]

It's actually still working on that one.

I can explain the algorythm if anyone would like.[/QUOTE]

If you want a challenge, you should try implementing Eller's algorithm. It is the craziest one.

[Overv]

I'm working on the structure of that OpenGL guide and I have this right now:

[img]http://gyazo.com/588ac3df01eea2cbdfbabdb7b6e26693.png[/img]

Am I missing anything important or is there something about the order that doesn't make any sense?

[dnt462]

[img]http://dl.dropbox.com/u/7801481/Progress.png[/img]

Progress, It may look like crap, but i work on that more tomorrow.
And I did a shit job cropping the photo.

[hypershadsy]

[QUOTE=redsoxrock;28412198][img_thumb]http://dl.dropbox.com/u/7801481/Progress.png[/img_thumb]

Progress, It may look like crap, but i work on that more tomorrow.
And I did a shit job cropping the photo.[/QUOTE]

Either your tiles or your window isn't a perfect square.

[DevBug]

[QUOTE=Overv;28411900]I'm working on the structure of that OpenGL guide and I have this right now:

[img_thumb]http://gyazo.com/588ac3df01eea2cbdfbabdb7b6e26693.png[/img_thumb]

Am I missing anything important or is there something about the order that doesn't make any sense?[/QUOTE]

I would put transformation before texture mapping. Also, you should add a section on shaders.

[editline]3rd March 2011[/editline]

Edit:

Or something under the advanced section like: Introduction to shaders

[Overv]

[QUOTE=DevBug;28412617]Or something under the advanced section like: Introduction to shaders[/QUOTE]

The problem is that in OpenGL 3.x shaders are essential for drawing anything on the screen at all, so they need to be part of the basic learning progress.

[dnt462]

No, i was resizing the the window

[Bang Train]

How long till these guides start coming out overv?

[Geel]

[QUOTE=Bang Train;28413138]How long till these guides start coming out overv?[/QUOTE]

He starts writing tomorrow.