• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
GuyWithBeard

Fastest way to get all distinct colors in a texture

6 posts in this topic

Hi,
 
I am baking occlusion culling data by rendering the scene from certain points into six textures (basically a cubemap). The scene is rendered with a special shader which takes the ID of each object and encodes that into an RGBA color which is then written to the texture. After the texture is rendered, I loop over each pixel in the texture and reconstruct the ID of the object from the pixel color. This way I get a list of all objects visible in the rendered image, without having to sort the objects based on distance to camera or anything, but the problem is that iterating over all pixels in the texture is fairly slow.
 
How would you speed up the process of getting a list of all distinct colors from the texture?
 
Cheers!
0

Share this post


Link to post
Share on other sites

That's an interesting question. What do you have at your disposal? Perhaps compute shaders and atomics could do - they are so fast they can be used for OIT transparency. Building the acceleration structure seems to be perhaps the most important thing.

You could have something like a matrix transpose on Local Data Share... if the API using it supports it (I'm not sure DirectCompute does).

Assuming you use DirectCompute or some Profile 5 target, you could use a write barrier to gather information from the various work-items in a workgroup, reduce the various lists and then spill them out to a global buffer.

This global buffer would still not be unique but it would likely be much smaller.

1

Share this post


Link to post
Share on other sites

No, if you are just given the texture then you are out of luck. There is no way to magically determine which colors are in a texture without examining at least N pixels (where you are looking for N colors corresponding to your object identifiers) and if the texture has no particular structure, i.e. is just a random frame with arbitrary geometry in it, then you are looking at a best case of N lookups (if all your colors are neatly tucked at the top left corner of the texture) and a worst case of checking every single pixel (if one color is at the bottom right of the texture, or if your colors are distributed randomly across the image, etc...)

 

So, you might be able to speed it up a bit with a clever parallel reduction method (assuming you don't have too many object ID's) but in general complexity will still be at least proportional to the number of pixels in the texture. But perhaps the approach can be changed to allow this to work efficiently. All you need to do is make it so your shader outputs the occlusion data in a way that the CPU can actually use efficiently, this could be as simple as a 1xN black and white texture which the pixels shaders write to whenever they get to render a particular object (one pixel for each object). There might be synchronization issues, though. I'm sure there is a lot of literature on fast occlusion query techniques. I think you are on the right track by rendering ID "colors" like this, but you need to output them differently because as you've seen scanning the texture to actually extract the occlusion info produced by the shaders out of it is way too expensive.

1

Share this post


Link to post
Share on other sites

I am working with Unity, so I don't have direct access to many interface. (Yes, I know that unity ships with Umbra, this is for procedural levels).

 

One thing I did, which provided a speedup of over 4x in certain cases, is simply to split the texture in four parts and hand off the parts to 4 threads. This is good enough for now since it brings down the bake time considerably.

 

I was originally thinking of writing a number to a lookup texture only when the pixel shader was fired, but that would have required me to sort the objects based on distance to camera. Also, more importantly, MRT support seems to not be very well supported in Unity.

0

Share this post


Link to post
Share on other sites

Out of curiosity can you make do with just 6 renders per cell, I was never sure how that would cover all viewing positions/angles the player might do?

0

Share this post


Link to post
Share on other sites

Basically, you want a histogram with two special conditions: 1) you don't care about the actual count, only need to know zero or not-zero and 2) you have a lot of bins.

 

Even without compute shaders, this is something that can conveniently run on the GPU. If you have shader storage buffer objects, use these, and nothing extra is needed. Just render a quad the same size of the texture (possibly with an empty FBO, too) and for each fragment read a texel, mash together the four 8-bit values to get the ID, and set the respective index in the shader storage object. You could do that with a simple loop too (rendering only one fragment total) but then of course you don't use the GPU's capablity of doing the task massively parallel and hiding memory/texture latencies by switching threads in and out.

 

Otherwise, if no shader storage is available, you must work around the fact that you only have a gather, but no scatter operation. The GPU Gems 3 article on histograms comes to mind, or you could just abuse the vertex shader for most of the heavy lifting.

 

As a quick-sketch idea, render width*height vertices (point mode) without inputs and let it read one texel per vertex from the texture according to gl_VertexID, then output a vertex with coordinates that correspond to that texel's value in the output texture (trivial fragment shader, writing out constant 1.0). This has quite some overdraw, but you could use the vertex ID as depth, so early Z will kill most of the overdraw.

Then, to find out wheter an object ID is present anywhere in those 6 textures, you simply need to look up its index in the output texture, that should be very fast.

 

Reading back the result probably takes longer than it takes the GPU to perform the calculation!

 

As for the huge number of bins, you probably don't have 4 billion objects (likely not even 16.7 million), therefore much of the 32 bits in a pixel will be unused. Support for 81922 textures is pretty much omnipresent, and looking at what GL_MAX_VIEWPORT_DIMS tells me, it's not trouble using that as rendertarget either. Now, 40962 can already encode 16,7 million object IDs (and 81922 is around 67 million), so either way it should be no issue.

Edited by samoth
1

Share this post


Link to post
Share on other sites

Out of curiosity can you make do with just 6 renders per cell, I was never sure how that would cover all viewing positions/angles the player might do?

 

The game is tile based, so I have to iterate over all the "walkable" tiles and render the cubemap to see which other tiles I need to render when the player is standing on the current tile.

0

Share this post


Link to post
Share on other sites

In the case of Rage and the feedback system that tells the engine what portions of the megatexture need to be streamed, they render a low-res color coded image, where the color signifies what coordinates of the virtual texture to load. I thought your current problem seemed related and could perhaps benefit from attempting to use smaller textures to minimize the time it takes to detect your colors on there ?

0

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  
Followers 0