J3D.ORG - Raw J3D: Picking

Picking

http://www.j3d.org/tutorials/raw_j3d/chapter6/picking.html

Apart from navigation, which is covered in the next chapter, manipulating an object would be the most common use of the mouse. At this point, the code that has been developed in this chapter still passes around raw AWT event information like the position of the cursor on the canvas. When picking objects, we need to map this 2D space onto the 3D objects in the scene. In 3D terms, this is referred to as picking.

Picking an object is the combination of two simple actions: handling a mouse click or movement and mapping a 2D screen coordinate into the 3D world. The last part is just the opposite of the 3D rendering process, but a lot more work needs to be done by the user rather than being automated.

One Click, Many Objects

Say you have the situation illustrated in 1. The user clicks on the screen at point A. The object that is picked is very easy to determine as there is only one along the projected vector indicated by the dashed line (note that the drawing does not indicate the effects of perspective). A simple casting of the vector into the scene graph will reveal what object has been selected and our pick system will return a reference to it.

Figure 1: Different forms of picking objects in a 3D world.

On the other hand, consider what happens when the user clicks at point B. Now there are three objects that could have been picked. What should the system return to the user when asked? It depends really on what your application requires. Sometimes you only want the closest object, other times you might require all of them. If you want all of them you may want it sorted by depth or not care too. All of these options are provided by the Java3D API, so you should not have any problems building the type of user interface that you need.

Nominating Pickable Objects

In a complex world there could be literally thousands of objects - most of them will never need to be picked. For example, in a virtual chat room based on a terrestrial metaphor, you may only want to select the door and one of the other users. The walls, windows and objects in the room may never need to be picked.

On the other side of the fence, the act of picking requires are reasonably large amount of calculation to be performed for every object. Worlds that have lots of objects could conceivably spend most of their time just calculating picking information. Obviously this isn’t a desirable outcome, so the Java3D API makes some large optimisations. Anything that is not pickable can be discarded. Although the Shape3D object is pickable by default, you should turn as many of these off as possible to allow greater optimisation potential.

Setting the pick state is through the use of the setPickable() method of the Node class. That allows any scene graph node to be pickable. Because picking is like other optimisable parts of the scene graph, it also requires the use of the capabilities:

ALLOW_PICKABLE_WRITE allows the user to change the pick state on the fly. You might use this if the object is only sometimes pickable. This only needs to be set if you are changing the pick state on the fly, not when first constructing a dead/uncompiled scene graph.
ALLOW_PICKABLE_READ allows the user to read what the current pick state of an object is. Less likely to be used than the write capability, but generally useful when dealing with large numbers of anonymous objects.
ENABLE_PICK_REPORTING is used only by grouping nodes. Because grouping nodes don’t define a visible object on the screen, normally they are tossed aside in the picking process. By enabling this option, when you get the path to the picked object, it will also include the enabled group (but not every group in the path) in that path.

The capabilities are only needed if you wish to change the pick state at run-time. If you don’t need to change or know what the state is, then all you need to do is call setPickable(true) on the object at creation time and then forget about it.

Describing Picked Objects

Because Java3D does a lot of internal optimisation of your scene graph when it gets compiled, your representation and the internal representation may not even look vaguely similar. This can cause a lot of hassles when trying to access the node of the scene graph that was picked. To overcome this problem, all path information is represented as a SceneGraphPath object. This abstract representation is used to hide the internal representation from the external code and make it easy to deal with picking.

When picking an object, typically we are not interested in the entire scene graph tree to that object, just the actual object that was picked. Since the object is a visible item, it has no children and the end of the path is the picked object. The picked item can never be an item in the middle of the path.

The SceneGraphPath class can be very useful for dealing with picked objects. As mentioned above, you usually don’t need to know anything more than the object that was actually picked. However, for those that do, there is quite a bit of useful information available through the following methods:

getObject() returns the instance of the object that was picked.
getNode() method allows you to step through all of the objects in the path from the root locale to the clicked object. If you have not enabled pick reporting for any of the groups (like transforms) then you end up with a path that contains a single element - the picked object. You may want to use this in conjunction with the nodeCount() method that will return the number of objects in the path.
getTransform() returns the location of the object in world coordinates at the time the object was picked. This is not effected by the setting of the ALLOW_LOCAL_TO_VWORLD_READ capability of the picked node. Note that if the object is being animated that the transform may have changed by the time you get to actually process some of the data.
isSamePath() can be used to see if two paths represent the same object. For example, if you have picked the same object twice in a row during an animation, the path is the same, but a number of other parts like the transforms are different. A pure equals comparison would return false because the transforms are different, when really it is the same object that has been picked.

Pick Mouse behaviour

Assuming that your scene graph consists of a number of pickable objects, you now need to do something with them. The typical use (there are others as we’ll see later) is with the mouse by clicking on it. For this, we’ll extend on the basic mouse click behaviour from earlier in the chapter to provide a pick behaviour. When the mouse is clicked, we’ll return a SceneGraphPath to the selected object.

To start the code, we build a MouseClickedBehaviour derived from the base MouseBehaviour. This starts by telling the base class that it is only interested in click events. For this, there is no need to implement the processAWTEvent() so we’ll leave that to the pick behaviour.

The pick behaviour is derived from the mouse click behaviour. Depending on what you want for pick behaviour, a click may not be the appropriate input. For example, a drag to move object would really need to combine picking with the mouse drag behaviour. For this example the simple click on an object notification is all that we need to illustrate the basic principles are needed. As we noted in an earlier section, there are a number of ways of selecting when there are many objects in the scene. Because we don’t want to limit the caller too much, the implementation will allow them to select the type needed in the constructor using a constant.

When picking an object, all the code starts from the processAWTEvent() method internals. Obviously the first part of picking an object based on an AWT event is to get hold of the mouse position:

protected void processAWTEvent(AWTEvent e) {
  MouseEvent evt = (MouseEvent)e;
  int x = evt.getX();
  int y = evt.getY();

With the mouse point available, we now need to cast that into the scene as a 3D ray from the user’s position. Note that we say a ray, not a vector. By definition, a vector is infinitely long that has no beginning and no end. Thus, if we used a vector in the scene, clicking on the screen would also select objects behind us as well. Even though the matrix maths is exactly the same, we stick to the more precise mathematical description of a ray, which is a starting point and an infinitely long line in one direction only. In this case "outwards" from the viewer’s position in the direction they are looking. Transforming a mouse position to a ray is not exactly obvious with Java3D so we’ll give everything to you here. To avoid boring you, we’ll avoid a complex explanation of the vector maths needed to actually do most of the work. To start with, here is the code that we need to use to turn a mouse position to a ray:

private PickRay createPickRay(Canvas3D canvas, int x, int y)
{
  Point3d eye_pos = new Point3d();
  Point3d mouse_pos = new Point3d();

  canvas.getCenterEyeInImagePlate(eye_pos);
  canvas.getPixelLocationInImagePlate(x, y, mouse_pos);

  Transform3D motion = new Transform3D();
  canvas.getImagePlateToVworld(motion);
  motion.transform(eye_pos);
  motion.transform(mouse_pos);

  Vector3d direction = new Vector3d(mouse_pos);
  direction.sub(eye_pos);

  return new PickRay(eye_pos, direction);
}

After establishing a couple of points for eye and mouse positions, the first thing that must be done is to establish where our mouse is 3D space and where the user is in 2D space. In both of these queries, the Point3d object is passed in and the values placed in them. Note that we go through this third party object called an image plate. This object is used as the interface between the 3D render and the 3D code.

Having established the basic renderer specific information the next task is to convert both the mouse and eye position into real virtual world coordinates (forming the next 4 lines of code). The two transform lines are used to modify the image plate coordinate systems into the virtual world coordinate system.

Finally, we need to establish a direction based on the user’s eye position and the position of the mouse. By subtracting the eye position from the mouse position, we end up with the direction of the pick ray. The last line is the final point of constructing the PickRay object from the eye position and direction.

Once the pick ray is established we need to find what this ray intersects with in the scene. There are two places you can do this - Locale and BranchGroup. What this requires is two difference constructors and some extra handling code, if we want to retain the generic flavour of this class. Both of these objects contain the same method signatures that allow us to pick objects in any one of the four styles. With a small switch statement, we can process any of the requests. For example, to pick any of the objects, you would use the following code:

PickRay ray = createPickRay(canvas, x, y);

SceneGraphPath[] path = null;

switch(select_mode)
{
  case SELECT_ALL:
    path = (group == null) ?
           locale.pickAll(ray) : group.pickAll(ray);
    break;
    ...

where SELECT_ALL is one of the constants that get passed in through the constructor that we mentioned a while back.

That is all there is to it. You now have a behaviour that can pick objects in the scene graph. You might want to spruce this up by telling the outside world that you have actually selected an object. Listeners or derived classes are the two standard ways of achieving that.

Different Pick Styles

In the previous section we only defined picking using a ray. In fact, Java3D is much more flexible than that. The various pick methods actually take a PickShape instance, from which PickRay is just one of the derived classes. There are three other variations: PickBounds, PickPoint and PickSegment. From these basic variations, there are different shapes that can be used: vector, cone and cylinder

PickBounds allows you to specify a volume of space to pick an object in. For example, you could use this to create a spherical bounding area, or drag area selection techniques that drawing applications are fond of.

PickPoint is based on a 3D point only. That is, anything touching that point as a surface will be returned. If the point lies inside an object, it won’t be included in the picked values. As you can imagine, for mouse based applications it is not very useful simply because you have no way of defining the depth portion of the point’s coordinate. However, it comes into its own if you have a 3D input device such as those used by modelling and animation companies.

PickSegment is a limited form of the PickRay object where instead of an infinite line, it is limited in length between two points. As you will see shortly, this is useful in 3D object interactions within the scene graph, and maybe for limited range searching from the UI perspective.

Other uses of Picking

A popular misconception is that picking is only any good for user input handling with the mouse. While mouse handling is by far the biggest use of picking, that is not its only use. You will remember that in the code built for the behaviour the 2DS mouse coordinate first needed to be translated to the virtual world coordinates before picking could begin. This should suggest to you that you can use picking inside your virtual world without needing user input.

Where might this be useful? Consider a first person shooter style game. For quite some time now these games have contained AI driven lifeform objects that respond to the user (usually by trying to shoot them!). Using picking, we can automate much of that behaviour. If you consider that an object in the scene graph knows as much about the virtual world as you the user does, the use of picking by that object to search for you makes sense. How would you construct this?

Let’s consider a very basic creature. If it can see you, it will chase you. Firstly, the object needs to know the instant when it can see you. Construct a behaviour that wakes up every frame. It has a known orientation. From this orientation it casts a PickRay from its position in the direction it is facing and gets the closest pickable object. If that object is you, then it moves towards you. If not, it waits for the next frame and checks again - it may even move a fraction. A line is very narrow field of view, so instead you might want to use bounds with a conical shape (PickConeRay class) to make it fractionally more realistic.

Another use of picking is for collision detection. Construct a bounds around your object describing the collidable area. Then, on each frame check to see if you can pick anything within that area. If yes, then you have collided with something and need to react. If there are no picked objects then keep going as you were before. In reality, you wouldn’t use picking for this because Java3D includes a separate collision system that does all of this for you.

As you can see, picking can be used in many different forms. Since most of your ability to interact with the scene graph is limited to behaviours, it may be worth examining what you need to achieve and if it can be accomplished with behaviours.

Picking Limitations

Despite all the good points about the use of picking, there are a number of limitations. The first limitation is: if you can’t see it, you can’t pick it. Back faces or transparent objects cannot be picked. If you have a completely transparent object, such as a window, attempting to pick it will result in nothing being returned. The same applies if you are picking the back face of a polygon mesh. If you need to pick a transparent object you will need to make sure that it is not 100% transparent, but is slightly opaque.

The second, and most difficult limitation is that, by default you cannot get the point information about where on an object you picked it. That is, you only get the whole object and no further information. Several attempts have been made to implement further refinement by various members of the Java3D community, but all have turned out to be very resource intensive to date.