Picking makes 3D applications interactive. It allows users to select and interact with objects in the 3D scene. In applications built with Point Break, common uses of picking include double clicking on an object to zoom to it and right clicking on an object to bring up a context menu with operations that act on the object.
In this blog, I will describe the algorithm Point Break uses to implement picking. The depth buffer, in combination with multipass rendering, is used to identify picked objects. The algorithm works in many cases when others do not, is almost trivial to implement, and provides good performance for scenes with moderate object depth complexity given its use of culling and scissoring.
Goals
Before describing the algorithm, first consider the goals for picking in Point Break.
- Picking should actually work. Seriously. Some picking algorithms do not consider per fragment operations such as the alpha test. If a model has a hole in it because the alpha test failed, picking on the hole should not return the model.
- It should be trivial for developers implementing primitives to make their primitives pick-able. In addition, individual parts of a primitive should be pick-able. For example, it should be possible to return the exact mesh of a picked model primitive. Although, this is actually more of an architecture issue than an algorithm issue.
- Picking should be fast enough to allow roll-over picking, that is, continuously executing a pick as the mouse moves across the screen. This is useful for reporting the current latitude/longitude/altitude or highlighting primitives as the mouse rolls over them.
- Drill picking should be possible. That is, the first pick returns the top object, then successive picks at the same screen location return the next object beneath the last one picked.
Many of the well known picking algorithms do not meet these goals or do not meet them cleanly. OpenGL selection and feedback ignores per fragment operations, is a pain to use, and I believe is not hardware accelerated. Furthermore, it is not part of OpenGL 3.0 or OpenGL ES. A attractive alternative is to use the Color Buffer for picking. This can be difficult for primitives that use shaders or textures with alpha channels. The stencil buffer can also be used for picking but this prevents using it for rendering. Finally, casting a ray thru the picked pixel and finding the intersected objects is widely used. Besides requiring a copy of objects in CPU memory, this approach does not consider per fragment operations.
Algorithm
In designing an algorithm to meet our picking goals, the first observation to make is:
We are going to read the depth value of the picked pixel to compute the world space position of the pick.
Furthermore, we should observe:
For most picks, the depth complexity of the picked pixel is relatively low.
To be precise, we don't care so much about the exact depth complexity; we care about the number of objects behind the pixel, which is likely to be far less than the actual depth complexity. Sometimes, only a single model is behind a pixel, e.g. when a satellite is picked. Other times, a model and the earth are behind a pixel. Although a scene with the viewer on the ground looking toward the horizon may have a high object depth complexity.
Since we need to read the depth buffer at least once, we ask:
If we only render the objects behind the picked pixel, can we afford to read the depth buffer after rendering each object? If we clear the depth buffer before each object, an object is picked if it wrote to the depth buffer.
"No, of course not." the naysayers exclaim. glReadPixels forces a pipeline flush and moving data from GPU to CPU memory is slow on all but PCIe buses. How slow? Too slow when 3 reads are required per pick? 10 reads? 1,000?
I didn't know; so I implemented it to find out. The algorithm works as following.
RenderSceneForPick()
{
modify the view frustum to just cover the picked pixel;
scissor out everything except the picked pixel;
for each visible object
{
clear depth buffer;
render object;
read depth buffer at pick location;
if (depth value != clear value)
{
add object to list of picked objects;
}
}
sort list of picked objects near to far;
}
Similar to picking with the color buffer, the scene is rendered into the back buffer, which is never swapped to the front. In addition, it assumes that all primitives write to the depth buffer, even translucent objects (which are rendered back to front without depth buffering for normal scenes). Its hard to come up with a case when an object could not write to the depth buffer. Perhaps, a post-process, per-pixel effect such as fog. Even, then it could write depth just when rendered for a pick. Who wants to pick fog anyway?
The first line of the algorithm need some explanation.
modify the view frustum to just cover the picked pixel;
This is crucial for performance. A view frustum is created that still starts at the viewer position and intersects the normal near and far planes but the frustum only intersects the near plane thru the picked pixel. This is used for culling so only objects behind the picked pixel are rendered. A 2D view is shown below. The original frustum is in black and the modified frustum is in red.
When this frustum is used for culling in a scene when the entire earth would be rendered, only a fraction of the earth is rendered for picking as shown below.
This actually shows a bad case; the bounding spheres of three tiles intersect the frustum since the picked pixel is approximately in the center of the image. To reduce the fill rate on both the depth buffer clear and object rendering, the second line of the algorithm scissors everything out except the picked pixel. This means, although all the vertices are processed in the image above, fragments are only processed for the picked pixel.
Odds and Ends
There's still a few more details to consider.
First, objects that write the same depth as the clear value are not picked. In most sane cases, this means objects rendered onto the far plane can be missed. Thankfully, this is almost never an issue and can be fixed by also reading the color buffer.
Second, if the viewer is far away, its possible for a large amount of the scene to be behind a single pixel. For example, the entire earth and everything on it could be behind a single pixel. What does the user think they are picking on anyway? Regardless, view frustum culling is not effective so we turn to a simple solution. Objects that are farther from the viewer then a user defined threshold or do not meet a user defined pixel size are not rendered.
Finally, we've ignored the problem of rubberband picking, where the user drags a box in screen space and wants to pick every object in it. Since the frustum may be large, culling is now less effective. The good news is this doesn't have to execute at highly interactive rates like a single pick used for roll-over picking.
Summary and Future Work
In summary, the depth buffer, in combination with multipass rendering, is used to identify picked objects. This algorithm considers per fragment operations, is straightforward to implement, and provides good performance for most scenes. In a future entry, I may post some performance numbers.
This algorithm is still ripe with potential optimizations. For example, when drill picking doesn't matter and only the front object needs to be picked, can hardware occlusion queries help? Can PBOs improve the performance of reading the depth buffer? If the object depth complexity is high, can each object be written to a different pixel and read back all at once?
In my eyes, the ideal picking algorithm has the ease of use of this algorithm and the speed of traditional color buffer picking with a single read back.
this seems to work well especially if you’re able to effectively cull your objects before running the algorithm…
in case performance is an issue… it sounds like you might be able to get away w/ a 1×1 size z-buffer… how about this… have a pool of 1×1 z-buffers, and for each object, render it to its own z-buffer. after rendering all objects, do all the read-backs in one shot. would this be faster? I dunno, cuz u might have to stall the pipeline each time you switch z-buffers, anyway. but it’s an interesting idea to consider. If anything, maybe using a 1×1 size buffer is faster than the full frame buffer.
one problem w/ “picking” algorithms is that they always assume the ray is coming from the camera, which can be inconvenient =/ it’d be particularly annoying if u have to do tens (or hundreds) of them per frame, because each one would require up to a full scene redraw… I guess if you have that problem, you can think about processing multiple picking requests in the same pass…
Yes, hierarchical culling is a must for this algorithm to be efficient. In addition, this algorithm benefits from tight bounding volumes.
I agree with using a single read-back for performance improvements. I don’t know if a separate z-buffer for each object is the way to go; switching FBOs might be a killer, as you suggest.
In terms of raw rendering, using a 1×1 z-buffer is probably faster since the scissor test, used in the current algorithm, executes after the fragment program. How much faster? Who knows? When objects are rendered for a pick, their fragment programs are almost always very simple.
I’m considering just rendering each object to a different pixel by changing the viewport then reading back the depth buffer once. I’m pretty sure it will work. It has little overhead and still only a single read-back (assuming there are enough pixels for each object).
What use cases do you have in mind for a ray that doesn’t come from the camera? Perhaps an orthogonal projection?
Looks like I was wrong. The scissor test can happen before a fragment program, even though the Direct3D documentation may lead you to think otherwise. Given this, I can’t see using 1×1 z-buffers being faster then rendering to different pixels in the same buffer.
ya, ur idea of using a different pixel per object sounds good.
a ray that doesn’t come from camera… actually not a big deal unless you’re writing a game on pointbreak
Excellent read, I just passed this onto a colleague who was doing a little research on that. And he actually bought me lunch because I found it for him smile So let me rephrase that: Thanks for lunch!
Just thought i would comment and say neat design, did you code it yourself? Looks great.
I was wondering how you set up glViewport for this? I tried setting it to be the same coordinates as glScissor, but that’s not working for me. glScissor seems to work as expected. Without calling glViewport, picking works great, but I’d like that optimization.
Robert,
I actually don’t change the viewport at all. Changing the view frustum for culling and scissor region is all that is needed to get the optimization.
Patrick
I tried using gluPickMatrix which seemed to work, is that what you mean by changing the view frustum?
By view frustum, I mean the view frustum that you are using for culling in your application code. If you’re not doing any culling, this optimization will not be as effective (although the scissor test will still help). When you render only a single pixel or small square of pixels for picking, there’s a good chance that fewer objects need to be rendered. Read up on view frustum culling and you’ll see what I mean.
Woah! I’m really loving the template/theme of this website. It’s simple, yet effective. A lot of times it’s tough to get that “perfect balance” between user friendliness and visual appeal. I must say you have done a awesome job with this. Additionally, the blog loads extremely quick for me on Chrome. Superb Blog!
I am unable to access this website adequately within Firefox, Hopefully you’ll fix this problem!?
Superbe billet. Puissez vous continuer à partager ce type de billets !
Thanks for sharing! nowadays There is so much confusion surrounding this topic and there’s a lot of different advice about good practices. Thanks for helping to make sense of it. Your opinions are appreciated.
Keep Rockin!
Best,
Oh my goodness! an amazing article dude. Thanks Nonetheless I’m experiencing problem with ur rss . Don’t know why Unable to subscribe to it. Is there anyone getting similar rss problem? Anyone who is aware of kindly respond. Thnkx
Great content material and great layout. Your blog deserves every one of the positive feedback it has been getting.
Spot lets start on this write-up, I seriously believe this remarkable site requirements a lot far more consideration. I’ll far more likely once once more to read a great deal far more, several thanks that information.
very good \o/
would love to incessantly get updated great site ! .
so much good info on here, : D.
I simply desired to appreciate you again. I do not know what I might have implemented without the tricks revealed by you about such a area of interest. It was a very horrifying condition for me personally, however , being able to see a new specialized tactic you dealt with the issue took me to weep with happiness. Now i’m happier for the help as well as hope you know what a great job you have been getting into teaching most people using a web site. Probably you’ve never got to know all of us.
I respect your piece of work, appreciate it for all the interesting blog posts.
woh I am pleased to find this website through google.
I like this web site very much so much great info .
Just desire to say your article is as astounding. The clearness to your publish is simply great and i can think you’re an expert on this subject. Fine with your permission let me to clutch your feed to keep updated with coming near near post. Thanks a million and please carry on the rewarding work.
yay google is my world beater helped me to find this outstanding web site ! .
Can I simply say what a relief to find someone who truly knows what they’re talking about on the internet.
I dugg some of you post as I cogitated they were extremely helpful invaluable
Perfect piece of work you have done, this website is really cool with great info .
Aw, this was a very nice post. In thought I wish to write like this – taking time and precise effort to make a very good article is very rare…
I like your blog, but could not find how to subscribe to get the updates by email.
My partner and i oftentimes look at your blog and always realize it’s worth it to read. Considered it was eventually about time document show you…Always maintain up the superb do the job
It’s seriously a quality doc. A particular standard on those wrinkles shows how drastically the taste is normally appreciated by the person dependable.
Good day, Document take a look at your complete documents, bear them getting.
Understand. Sunlit place! Put in writing even more. It appears as though Document ever common visitor to your site
Enjoying social city is usually way quite as good as writing comments about shitty sites professionals who log in benefit from yoville secrets-and-cheats.
I am glad to be one of several visitants on this outstanding web site (:, appreciate it for posting .
very interesting subject , great post.
It is best to participate in a contest for probably the greatest blogs on the web. I will suggest this web site!
I am attempting to read your blog site on my iphone, but its not doing the job for some reason. Can you let me and other followers know what we have to do to examine it via this type of device.
I gotta favorite this internet website it seems handy .
many dias! a good la madre, sigues minus dialup?
Well… for being entirely truthful, My partner and i don’t be prepared to locate such a info unintentionally, as Used to do, simply because I recently discovered this website although I became actually doing research online in the search engines, trying to find a thing extremely close however, not very the identical… Even so at this time I’m greater than very happy to be below along with I’d like to incorporate that your perspective can be remarcable even though any trifle debatable for you to our taste… I would instead declare it ought to be up to argument… nevertheless I’m scared to make you an opponent, haya, ha, ‘… Anyhow, for those who like to speak in detail about this, make sure you reply to my own remark along with I am going to ensure that you register so that I’ll be advised and also come back here for a lot more…
Useful page as I my remarks usually are not spammy ::)
read. |Thanks for good news!|Thanks for best news!|thank! for this news it’s a good infomation !|Nice post…Thank you for sharing some good things!! |Thans
Perfect piece of work you have done, this website is really cool with fantastic information.
you are my aspiration , I possess few web logs and occasionally run out from to brand : (.
[Software] FaceDominator Cracked, Dominate Facebook Marketing Today Download Here
Wonderful write-up ! I must discover while you update your site, can anyone help me register for your site?.The software served to us a tremendous amount. I am nominal amount aware measurements but your post set it up crystal clear idea
Thank you for all of the effort on this blog
It’s laborious to search out educated folks on this topic, however you sound like you know what you’re talking about! Thanks
Very first of all, permit my family recognize a person?s command during this make a difference. Despite the reality this really is undoubtedly brand new , by no meanstheless rapidly soon following registering your web site, this intellect has exploded extensively. Permit all of us to consider preserve of 1?s rss to assistance maintain in touch with whatsoever probable messages Sincere realize but will pass it on to aid admirers and my individualized are living members
Hands down, Apple’s app store wins by a mile. It’s a huge selection of all sorts of apps vs a rather sad selection of a handful for Zune. Microsoft has plans, especially in the realm of games, but I’m not sure I’d want to bet on the future if this aspect is important to you. The iPod is a much better choice in that case.
Extremely good post! I’m in the beginning stages during city management/marketing storage aiming to assist you to discover how to undertake it efficiently , methods enjoy this post are usually exceptionally beneficial. Like our organization is dependent in the us, them?verts virtually all a few things a newcomer to all of us. The occasion previously can be something that i keep worrying about to boot, how to indicate your own private real passion along with portion the fact your main solution is helpful if so.
Fantastic weblog! I truly absolutely adore just how it is rather simple for great view plus the specifics might be well crafted. My group is wanting to know earn money is perhaps acquainted if a cutting edge put up has been given. May possibly fell to your feed of which ought to do bring about! Possess a wonderful morning!
Extremely good document! Now i am only starting within area management/marketing marketing seeking to make sure you find out how to practice it good ( space ) options such as this publish are usually very practical. When our organization would depend the united states, the following?azines almost all somewhat fresh to united states. The ?nstance above is one challenge which bother about besides, ways to display your personal genuine enthusiasm and additionally publish the point that your merchandise is helpful in that case.
I’d been honored to receive a call from my friend as soon as he discovered the critical recommendations shared on your website. Going through your weblog posting can be a real fantastic experience. Thank you for taking into account readers like me, and I desire for you the very best of achievements for a skilled surface area.
We never know about you folks but also for myself the design of a web site is extremely important… I might say practically up to the post itself. Additionally I’m crazy regarding video clips… as well as, ought to be reality, Any press content in any way. Therefore, anytime I discover a write-up coupled these kind of wrinkles We just wish the specific OP embeds a few online movie a place. These days, a new numerous weblog owners typically do not… I am unable to think about precisely why?… My spouse and i otherwise this could happen may differ dependant upon this article… Nevertheless My partner and i still imagine that it would be suited to virtually any sort of articles, because it would often be nice to determine the comfortable and also helpful deal with or simply pick up any voice while very first landing. Anyway, lokks like I’m a bit away from matter using this type of?.. Correct… It appears to be this! Hehe… Many thanks a whole lot for loving the world wide web using this blog post!
I am glad to be one of numerous visitors on this outstanding internet site (:, thanks for posting .
I simply found your blog publish although I became the truth is owning a explore Yahoo and google, looking to find such like but not pretty a similar… However I’m more than pleased to see this, since you really seem to have the topical standpoint. I would instead say it’s up to debate… yet Now i’m reluctant not to allow you to my opposing forces, haya, ha, haya… In any case, if you wanna discuss a lot more about it, you should reply to my own comment and I’m going to make sure to subscribe in order that I’ll be informed and come back again here for a lot more… Your current wannabe close friend
you’ve got a fantastic weblog right here! would you like to make some invite posts on my weblog?
Outstanding post, I think men and women need to learn a great deal from this web site its rattling user genial .
The information mentioned in the article are some of the best available ……