Jump to content


Member Since 20 Apr 2003
Offline Last Active May 21 2015 07:17 AM

Posts I've Made

In Topic: Algorithm for covering as much dots a as possible?

15 September 2014 - 12:10 AM

Wouldn't by any chance be a homework assignment? If so, that's greatly discouraged. If not, you may get better answers if you describe how the rectangle will be used.


I want to have thumbnails of screenshots from moments in the game. First I thought that I could just resize them but then it looks kinda ugly and a bit distorted.

So then I just crop it in the middle after that.

The problem is that I don't think it looks cool enough. So what I'm thinking is that I could mark the explosions, bullets and magic with "relevance" dots or run the image through a "Feature Detection" like a SURF or SIFT to mark the images with interesting stuff. I'm thinking of doing a collage/toplist of cool(= gives out most score) stuff when the level is complete. The problem is that it's really slow to do brute force and I want it the instant the level is complete. What I want is a function that basically given an width/height and an image gives me back the cropped version of the most intense place in the image.


Then rectangle A will be a rectangle that's inside A and also covers as many dots as possible.
Are you thinking about bounding boxes? In that case, it's easy:


Nope I want a specific size of the rectangle.

In Topic: Render queue ids/design?

09 November 2013 - 01:45 AM

Trying to cram everything into a 64-bit value solves nothing and creates problems. You are limited in your bits and comparisons are 3 times slower.

So perhaps you should explain why you feel the need to go this route and then perhaps we can give you a better alternative.


I totally see that it creates a lot of problems storing everything in a 64 bit value.

Woah I didn't know that it's 3 times slower to compare a 64 bit value. So I thought that it was as fast 32-bit compare on 64 bit computers.


The thing is that I don't feel I need to go this route cramming everything into 64-bit it was just that it was the first idea that came to me and I tried to stick to that idea. Im quiet open to any idea. Initially I wanted some input so that I could avoid the worst bottlenecks and design decisions.


I really like the idea that Hodgman gave me to just treat the sorting key as a binary blob that is only used for sorting. That's something I would never have thought of if it wasn't for this thread.



Coming up with a "perfect key" is impossible to do I know it now.

It's almost like an AI that needed to create these keys. Has someone tried building something like a neural network to create keys?

The inputs are shaders, uniforms, textures, vbos, ibos, z-depth, transparent and some other stuff. Output is a key. Training the network would be the draw calls or frame time.

I think it would be slow but will it be slower than the all the unnecessary render state changes?


Typically, my items will have state-groups such as per-camera (view/proj matrix), per-object (world matrix), per material (textures, shader), etc...


Wouldn't this create a bunch a of memory fragmentation? Or create a lot of dynamic dispatch?


I know writing branch free code is really hard so I guess that's ok.

In Topic: Render queue ids/design?

08 November 2013 - 01:37 AM

First-off, specifying diffuse, specular, normal, etc. textures specifically is a very good way to ensure you have to rewrite the whole thing at a later date.

Never hard-code the set of textures you have; you will always need to add one more new type. Besides you are wasting bits.

A better way would be to have a map-like class that takes an array of any number of texture ID’s and for each unique order and combination returns a single ID that need only consume 16 bits or so. Then only that single value needs to be tested to know if 2 objects have the same textures in the same orders (although once on the GPU order doen’t really matter, so it really could be just a unique ID based off the combination of textures, not the order).

So you mean like a hashcode?

Like murmurhash?

That sounds perfect. The problem I see is that then everything with the same diffuse but not the same normal map will be totally different. It's like the material ids.


I really don't like loosing that much control.

Let's say I have a 16 bit number to play around with:

1. The first texture id = 8 bit

2. The second texture id = 8 bit


Maybe then have something that keeps track of all the texture ids usage(the number of texture ids used and store them in a array).

When you call the "generate_material_id"/"generate_texture_id" then it checks all the current textures in the material and selects the two most used.

That would ensure that most texture switches is possibly mitigated. Or are you thinking of something else?


2) You treat the sorting key as just a binary lump of data that's only used for sorting and nothing else. You store render-state information elsewhere.



This is another solution I guess it's never black or white.


Both methods have their merits. To offer another point of view though, I personally chose #2. The objects in my render queue look kind-of like:

{ u32:key, u32:drawCallData, u32:numStateGroups, StateGroup[]:states }

Each item contains the data that will be used to make the draw-call, and then it contains a variable-sized list of state-group pointers. A state-group then contains actual render-states, like commands to bind textures, buffers, shaders, etc...


Why store the draw call data in the queue when you have state groups?

Why not store the draw call data in the state groups?

Why have a list of state groups isn't one enough?

In Topic: Render queue ids/design?

07 November 2013 - 12:38 AM

I've been thinking I got some sleep.


I think I need 2 types of ids.

1 for opaque objects and 1 for transparent.

These lists just to clarify 1 = most significant bit.

So for opaque objects:

1. Type(like a tiny header in this case = 0(opaque 3D)) = 2 bit

2. layer = 4 bit

3. shader = 7 bit

4. diffuse = 7 bit

5. normals = 7 bit

6. specular = 7 bit

7. IBO = 7 bit

8. VBO = 7 bit

9. z-index = 8 bit


Ok, this has now 2+4+7*6+8 = 56 bit

Hmmm.. I think I could squeeze in another texture and that's a glow map that would mean: 2+4+7*7+8 = 63 bit

Pretty close to 64.


So for the transparent objects:

1. Type(like a tiny header in this case = 1(transparent 3D)) = 2 bit

2. layer = 4 bit

3. z-index = 12 bit

4. shader = 7 bit

5. diffuse = 7 bit

6. normals = 7 bit

7. specular = 7 bit

8. IBO = 7 bit

9. VBO = 7 bit


So for this it's 2+4+12+7*6 = 60 bit.

Also I could have 2 pools(1 for opaque and 1 for transparent) of shaders, diffuse textures, normals textures and specular textures. So I at least could get 256 IBO/VBO and texture combinations.


I think I need to think about this design a bit more so that I don't regret it in the future.

In Topic: Render queue ids/design?

06 November 2013 - 08:41 AM

The next most expensive is typically texture swaps. You have no information regarding the textures used, unless that information is part of the material.
Next are the VBO’s and then IBO’s. If texture information is not part of the material, discard the material—by this point it wouldn’t be of any help once everything else is sorted.

You have no depth information. Sorting by depth is a good idea for depth pre-pass (if you use it) and necessary for transparent objects.


At first I was thinking that material is a combination of all the textures like diffuse, normals and specular.

So let's say I have this structure:(I assume u mean that I need to have a single ID of 64-bit)

Then the structure would be more like this:

1. type(3D opaque, 3D transparent,fullscreen effects like SMAA/HDR, 2D/UI) = 2 bit

2. z-index = 8 bit

3. shader = 7 bit

4. diffuse = 6 bit

5. normals = 6 bit

6. specular = 6 bit

7. IBO = 6 bit

8. VBO = 6 bit


This is really conservative!

I get this to 2+8+7+5*6 = 47 bit


Is this a correct order? Should I maybe move z-index down a bit?

Hmmm.. Layering. Couldn't this be solved with z-index?

Now I got 17 bits to play around with.

I should probably increase some bits. What do u think would be best to increase?

Or Have I missed something that I need to have?

Maybe I shouldn't exactly specify diffuse,normals and specular but then I would need some kind of "material_id" like before. This feels more sustainable at least and I can easily sort them. Maybe just have 3 texture pools and u could store them in different slots for the shader?


Why should some manager assign ID’s, and why do you have a list of “free ID’s”? Are these ID’s that are available to be taken?

For shaders permutations this is most likely to be loaded when the game starts so then it's ok. Let's say we have 100 shader permutations and that would easily fit into 8 bit.

My concern is with with textures(needs most likely 3 textures per model) and IBO:s/VBO:s(a lot more per model) . They will change when the game progresses and then I need to reuse the id:s. Because I must be able to squeeze everything into  64-bit in order to sort the render queue efficiently.


The shader can assign its own ID. More robust because it eliminates the necessity that the shader be created by the shader manager—manual creation does not break the system.
The critical section isn’t really necessary though; it could just be an atomic.

I really like the idea I also like the idea of using atomics. The problem is that it feels it could create too many ID:s if you just add up.