Selecting 3D surfaces with a selection box (in two different ways)

Question

I am creating a piece of modelling software. My models are all made up of flat polygons, which are simply an ordered set of vertices that I am displaying with OpenGL. I've done quite a bit of searching and to my surprise haven't found much information for the application I am looking for.

I am attempting to use a rectangular box to select surfaces. This sounds simple enough, but I want it to work in the same way that this method works in lots of programs. These are the requirements I am looking for:

1. I want a rectangle that starts at the left and goes right to only select those objects that are completely contained within the box.
2. Rectangles that start at the right and go left should select any surface that is touched (it does not have to be fully enclosed.
3. All objects in/touching the rectangle should be selected. In other words, I want to select objects whether they are visible or not. Everything that fits inside the box, even if covered by another surface, should still be selected.

Number 3 on the list is most important. Having both options 1 and 2 is preferred, but I can live with only one of them if it proves overly difficult to implement them.

I have looked at various other posts about 3D picking and it seems most suggest color picking or ray casting. I use color picking for normal click selection, but because I want the box selection to include surfaces that are not visible this is not an option. It also seems that ray casting only works with a single click point rather than a box. So are there any other methods that are fairly straightforward to accomplish my goal? I figured this would be a rather common task as it seems to be present in a lot of modelling software, but unfortunately I have not been able to find a method that suits my needs.

Pseudocode of an algorithm would be appreciated but is not required. At the very least I am looking for a method that I would be able to research and find some examples on my own; I simply do not know of the proper place to look.

Answer 1

Performing your own intersection calculations on the CPU is certainly one option. But based on how I understand your requirements, I think you can also let OpenGL do the job, which should be much easier and more efficient.

Method Overview

The mechanism that comes to mind are occlusion queries. They allow you to count pixels that have been rendered. If you combine this with using the scissor test, you can count pixels rendered inside your selection rectangle.

Application to Use Cases

Use case 2 is the simpler one for this approach. You set up the selection rectangle as the scissor rectangle, and render all surfaces with an occlusion query for each of them. Then you check the result of the queries, and all the surfaces where the query result is larger than 0 had pixels inside the selection rectangle.

Use case 1 is slightly trickier. To know if the surface is completely contained inside the rectangle, you need two passes. You go through the rendering with occlusion queries one time as above, with the scissor test enabled. Then you do the same thing a second time, with the scissor test disabled. If a surface has the same query result for both passes, it is completely inside the rectangle.

Implementation

I'm not going to provide full code for this. It should all be pretty straightforward. But here are a few pointers and code fragments. The calls are shown with C bindings. I hope it's obvious enough how the same thing would look with Python bindings.

First, since you want to include hidden surfaces in the selection, you need to disable the depth test:

glDisable(GL_DEPTH_TEST);

Since you don't really need to produce output, and probably don't want to disturb the visual rendering output, you may also want to disable color output:

glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE);

If you had back face culling enabled, you may want to disable that as well:

glDisable(GL_CULL_FACE);

Then, for the passes mentioned above where you only want to count pixels inside the selection rectangle, set up the scissor rectangle, and enable the scissor test:

glScissor(selectionLeft, selectionBottom, selectionWidth, selectionHeight);
glEnable(GL_SCISSOR_TEST);

For the rendering with the occlusion queries, you need a query object for each surface:

GLuint queryIds[surfaceCount];
glGenQueries(surfaceCount, queryIds);

Then for each surface, using k as the loop index:

glBeginQuery(GL_SAMPLES_PASSED, queryIds[k]);
// render surface k
glEndQuery(GL_SAMPLES_PASSED);

After all surfaces have been rendered, you can get the query results:

GLint pixelCounts[surfaceCount];
// for all surfaces k
glGetQueryObjectiv(queryIds[k], GL_QUERY_RESULT, &pixelCounts[k]);

Then evaluate the pixel counts to decide which surfaces should be selected as described in the previous section for each use case.

Don't forget to reset all the state after you're done to be ready for rendering again. Depth test, color mask, scissor test, etc.

Answer 2

I can tell you flat out that color picking will not work; you would have to do one pass per-object to satisfy requirement (3) since only one pixel ever makes it into the framebuffer.

As for ray casting, it is true that it only tests a single point, but you can actually create a test volume by unprojecting the four corners of your selection rectangle. You would find the coordinates in world-space at the near plane (Win_Z = 0) and at the far plane (Win_Z = 1) and use this to construct a 3D volume from your 2D selection area.

The volume you are going to get from doing this is called a frustum (assuming perspective projection), it looks like a pyramid with the top chopped off. Frustum intersection tests are very well documented, and anything that discusses "frustum culling" ought to provide you sufficient background to implement this. Your life will be a lot easier if you can approximate the bounds of these objects using axis-aligned bounding boxes and/or spheres.

The following diagram illustrates this test volume nicely: