The level of detail portrayed in graphics environments is steadily increasing, and so does the challenge to enable users to accurately select 3D objects from a graphics scene in real time. Thousands of players may compete against one another in a multi-player game for instance, and they frequently select objects by pointing to them with the mouse cursor or other pointing devices. Selection in a 3D scene is addressed by picking algorithms. Picking algorithms must be fast in order to provide users with minimum delay responses. With such importance placed on picking, several algorithms have been proposed, with the most common being ray casting and color picking. We propose to explore these two algorithms by computationally analyzing and comparing them across several levels of scene complexity and object velocity. Our comparison metrics are accuracy and speed (selection time). Our ultimate goal is to determine the conditions under which one picking algorithm outperforms the other.
Our focus in this project is on theoretical analysis and implementation, rather than development of new picking algorithms. Our work is motivated by the lack of literature on general implementation of picking algorithms not tied to the graphics pipeline of a particular application programming interface (API), such as OpenGL and DirectX. These APIs provide CPU methods for 3D picking, but the efficiency of these methods decreases dramatically as the complexity of the graphics scene increases. Since they execute on the CPU, these methods do not take advantage of the powerful capabilities of modern programmable graphics processing units (GPU), which have a lot of cores for parallel processing. Furthermore, these methods seem to have become obsolete.
Modern GPU hardware supports the development of highly parallel programs, known as shaders. A thorough understanding of the graphics pipeline is extremely important when designing a GPU shader. How fast are these GPU cores? We will answer this question by implementing the ray picking algorithm as a CPU program and a GPU shader, and comparing their running times. We will also evaluate the performance of these algorithms against the color picking algorithm, in terms of both accuracy and speed. Finally, we will use spatial decomposition techniques to accelerate our picking methods.