A 3D Object Picking Technique that Uses OpenGL

Environment: VC++6, Win32

Overview

This article demonstrates a simple technique for capturing which 3D object the user clicked on with the mouse. Of course, it can be used to discover the object at any X,Y position on the screen. The most difficult thing about picking is telling OpenGL to send its output directly to an image; and that technique was covered on a previous CodeGuru article; it's available for viewing here. Once you are able to send graphics directly to an image (DIB Section) the rest is trivial.

Here is an outline of the basic approach:

  1. The user clicks the mouse (or some input device). Capture the X and Y position of the click.
  2. Now, set up a lookup table of colors: 1 color for each 3D object in the model.
  3. Re-draw the model, but instead of the normal colors, use the colors from the lookup table. And one more thing, don't display the output image on the screen.
  4. Find the color of the image pixel at the X-Y position of the click and use the color to find the corresponding 3D object in the lookup table.
  5. Re-build your model using original colors and textures.

This simple technique is called the Painter's Algorithm. It's nice because there is no complicated geometry. Its downfall is that it is not the most efficient approach because of the necessity of redrawing the entire model, at least the parts that may be picked. However, some steps can be taken to improve the efficiency of Step 3 by keeping in mind that the user will never see the intermediate model, so the resolution may be lower than the original model. For example, in the sample project the spheres are broken into triangles, but for the intermediate "pick" image you may use far fewer triangles to describe the sphere, thus making the drawing code much faster.

Sample Project

Use the left mouse button to rotate the solar system and the RIGHT mouse button to select a planet.

Enjoy.

Downloads

Download demo project - 405 Kb



About the Author

Andy McGovern

Andy McGovern - Software Developer/Engineer. Special interests: astronomy, image processing, orbital mechanics, mathematics. Currently work at the Johns Hopkins University Applied Physics Laboratory on the science operations team for the CRISM instrument on the Mars Reconnaissance Orbiter.

Comments

  • no code!!!

    Posted by nobody_wxf on 05/23/2006 11:19pm

    why?

    Reply
  • It helps!

    Posted by joeblackjoeblack21st on 12/26/2005 11:10am

    Though it is a little easy ,it enlightens me ,thanks!

    Reply
  • That technique is also described in the "red book" ...

    Posted by bob42 on 10/25/2005 02:33am

    ... Woo et al :-). They also contend that when you have more objects that colors you can iterate over the objects multiple times. The alternative is to use the unproject() methods of OpenGL (also described in the "red book").

    Reply
  • Easy algorithm with plenty of room for tweaks and improvements

    Posted by Legacy on 01/10/2004 12:00am

    Originally posted by: Colin Branch

    This algorithm is really good for scenes that lack a strong organization. Typically non-buffer based picking is done through 3d collision testing between objects and a line defined by the click of the mouse. These are not too expensive especially if you use a hierarchical data structure like octtree, bounding volumes etc. Of course to do this requires a bit of coding and linear algebra.
    The painters algorithm bipasses all this nastyness since it allows the videocard to find the closests pixels of triangles to a user defined plane (ie these are the visible pixels).

    For a modelling program frequently there are various elements that need to be selected (groups,objects,faces,edges and points). To do this requires that each element be rendered with a different id.

    With the development of programmable hardware it is now possible to render the ids without requiring additional passes. Using a simple frament shader it is possible to render the ideas directly to the framebuffer thus not requiring a second pass. One way is simply use the typically unused alpha component on 32bit displays to store the id (though this limits you to 256 ids). Another way is to compress the colors to 16bits and use the low-order bits to store the id (results is slight color shifts). Or with the newest hardware you can create much larger buffers such as 128bit floating point buffers which allow large id ranges. Another possibility is to allow multiple frames per id. For example is using only the alpha channel, have odd frames store the low order bits of the id and the even frames to store the hight order bits. And simply with the mouse click gather data for 2 frames before responding with the selection of the full 16bit id. Nowadays even extremely huge scenes are rendered at decent rates. While 10fps is horrible for gaming it is sufficient for 3d modelling, so hardware picking should be an option.

    Reply
  • How to build the diagrams with the help of Visual C++ .NET and OpenGL?

    Posted by Legacy on 09/30/2003 12:00am

    Originally posted by: Zharkov

    Hello. Inform, please, on what site it is possible to find materials on construction of the three-dimensional diagrams of functions with the help of Visual C++ .NET and OpenGL?

    Beforehand many thanks for your answer. Best regards, Dr. V.A. Zharkov. Address: Orekhovy bulvar,39-2, Moscow, 115573, Russia.

    Reply
  • Don't use this method, it's too slow ! ! !

    Posted by Legacy on 07/29/2003 12:00am

    Originally posted by: Taz

    The mothod described here is not very useable, it to slow compared to the build in method of selecting.

    Instead create a name stack, using glRenderMode( GL_SELECT ) and glPushName, glPopName etc...

    see the examples on nehe.gamedev.net

    Reply
  • Actually, this is a good method given current hardware

    Posted by Legacy on 04/07/2003 12:00am

    Originally posted by: David Stidolph

    Considering the speed of rendering cards, throwing a lot of triangles at a problem is fast - it is the textures that kill your frame rate.

    I would NOT suggest using lower resolution objects - will not speed things up a lot on modern (GeForce) cards but might introduce inaccuracies. Also, many of the triangles would already be in the cache if you did not change them.

    One thing to speed it up though, reset your clipping plane to several pixels around the mouse cursor. Clipping is blindingly fast on modern hardware.

    One thing I have learned in 3D, keep things simple. This is simple.

    As to speed cost - this is a user event (a mouse click) - losing a frame is fine for that.

    Good article - simple concept and deliver. Those intereasted in the code can dive in, but those just wanting basic ideas get them fast.

    David Stidolph
    Austin, TX

    Reply
  • There got to be better way!

    Posted by Legacy on 04/05/2003 12:00am

    Originally posted by: soichi hayashi

    I don't know much about OpenGL, but I would be very disappointed if this method is actually being used everywhere else.

    I like the sample program though. :)

    Reply
  • Why?

    Posted by Legacy on 04/04/2003 12:00am

    Originally posted by: John

    OpenGL provides a means for selecting (picking) rendered objects with the mouse by using the PushName and PopName mechanisms. I guess I don't quite understand why you would want to use your method and not the one provided for you via the OpenGL API. Please explain...

    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • On-demand Event Event Date: September 10, 2014 Modern mobile applications connect systems-of-engagement (mobile apps) with systems-of-record (traditional IT) to deliver new and innovative business value. But the lifecycle for development of mobile apps is also new and different. Emerging trends in mobile development call for faster delivery of incremental features, coupled with feedback from the users of the app "in the wild." This loop of continuous delivery and continuous feedback is how the best mobile …

  • On-demand Event Event Date: July 22, 2014 In this WhatWorks analysis, John Pescatore examines a use case where end users had local administrative rights on their PCs and it had gotten out of hand for this Fortune 500 Energy and Utilities company. The compelling event that prompted the company to reexamine this situation was the migration to Windows 7. In Windows XP, a custom tool that allowed users one of three levels of administrative rights to their workstations would need to be replaced during the Windows …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds