5.07.2011

Writing a surface occlusion detector

As I expressed in my previous post, I want to write an alghorithm/system that renders only the parts that need to be rendered in a Flash-like display list with z order. My idea of only updated the changed areas is solved quickly by iterating through all upper and nested objects and listing them along with their yet-to-update area. Simple. But that's doesn't solve any other problem. Whatever you remove or add to the display list has it's own z value. So if you delete a picture from the lowest layer and it doesn't affect the visuals at all - how to detect that it is visible? Well, my first thoughts were that I have to make a trade-off. First of all, I defined some properties for each object marking their bounding box and the way they depend on the objects drawn behind them (called "occlusion mode" in my program). If, for example, an object gets drawn by ORing the pixel below it, it will require them to be drawn. If not, you can skip any objects below and continue drawing the non-draw areas. I had several ideas how one can do this, but they either results in slow drawing or enormous memory usage - though CPU time is more critical, so more used memory isn't that kind of a problem. But still, my first ideas used exponentially more memory for every new object hiding stuff below it. Z buffering was also no option, so I decided to use a custom system - once again based on the almighty set theory. In essence, it decides between front-to-back (opac) and back-to-front (using previously drawn colors) objects and interprets their surface area as a set of outlined pixels. To bring only the visible pixel parts to live, it uses basic set operations to draw areas step-by-step with the optimal (in case, =minimal) amount of pixels necessary. I don't want to say to much about it, as I'm paranoid about it... there aren't many actually different alghorithms for rendering graphical scenes, I'd like to not see my invention implemented without my name on it. I don't mind GPL-ing it, but first I need to implement it. If everything turns out well, I will have a very set-ish and geometry-based alghorithm useful for virtually every kind of shape. Though I can't afford the performance for other shapes than rectangles, I can think of it beeing seriously mltifunctional. I don't have many of these clear moments where all my previous ideas and experiences come together so well, but this time it's different and it shows (atleast to me).

Anyway, I'm not quite sure about the performance in detail. Depending on how detailed your shapes and overlaps are, the performance alternates. I can't really predict how good the actual performance will be, but definitely quite minimal - especially if you don't use back-to-front objects cause these require a typical "background first, top-most object last" rendering philosophy as you can find in almost every 2D game. However, it should work fine on the NXT I think. It shouldn't go wrong with some carefully designed classes for describing pixel sets optimized for performance.

So wish me good luck for that one, I finally want to say that I wrote a render system that kicks ass.

No comments: