The Magic Touch Part 1
The issue:
You are on your way to making a 3d android app and you want to be able to select an object by touching it. But wait, that’s not all, you’d actually like to have the selected object follow your finger as you drag it across the screen.
This was a battle for a couple days, first in just getting selection working, and then blowing up into a tripple dot problem* where I all of a sudden had to deal with thread synchronizing for the rendering thread (something I was hoping future me would have to deal with).
If you are also looking at how to select something and move it around, you are at the right spot. Since I’m building a desktop editor for PandaDroid, these examples will be using my own matrix 3d class and keep the low level opengl calls just that.
First problem: How do you select an object given only an x and y coordinate?
Some graphics api’s have a way to do this. Unfortunatly, opengl es 1.0 does not, thus you are left with couple options. One can be to render two images and color coding objects so that you can test which object was selected. Unfortunately overlapping cannot be handled in a custom way . Another way is to send out a ray and see where it intersects. This article will be covering the ray cast selection method.
The basic principle here is that you draw a line from a camera’s view to the x y coordinate and then you see if that line ever intersects an object. The simplest way to represent a line in 3d is by representing it as a ray. A ray is 2 3d vectors: one being a point that the line intersects, and another vector that is a unit vector describing the slope.
So here’s our ray:
public class Ray {
public Vector3d position;
public Vector3d direction;
public Ray() {
this.position = new Vector3d();
this.direction = new Vector3d();
//My Vector3d's have a 4th component that can be 1 or 0.
//if it is 0, the vector won't be transformed by the translation, thus this
//vector will only be rotated or scaled. If you do not have a 4th component
//you will have to do 3x3 matrix transformations on the mDirection vector
//or recompute the direction by subtracting the position and normalizing
//the direction after the transformation.
this.direction.makeDirectional();
}
}
And we need to create a ray when given an x and y coordinate. To do this, I’d suggest making a camera class and it would be able to create a ray. The reason for this is that in order to create a ray you will need the near plane, the near height, the aspect ratio, and the inverse transform matrix.
Creating a ray is pretty simple, you just find the actual x y coordinates of the point on the screen based on scaling the points by finding the ratio of the positions and multiplying them by the near height and the near width (near height x aspect ratio). Then you set that as the direction and normalize that vector. The position is set as 0, 0, 0 and then you transform the ray by the inverse camera matrix so that the ray is now in the world space.
public class Camera {
private Matrix3d mTransformation;
private float mNear;
private float mNearHeight;
private float mAspectRatio;
public Ray createRay(float x, float y){
//first, convert x and y to a coordinate system where
//(0, 0) is at the center of the screen
float halfHeight = (float)this.mHeight/2;
float halfWidth = (float)this.mWidth/2;
float xUnit = (halfWidth - x)/halfWidth;
float yUnit = (y - halfHeight)/halfHeight; //Flip the y for android.
//now create the ray!
Ray ray = new Ray();
ray.direction.set(xUnit*this.mNearHeight*this.mAspectRatio, //x
yUnit*this.mNearHeight, //y
this.mNear); //z
ray.direction.normalize(); //make it a unit vector
ray.postion.set(0.0f, 0.0f, 0.0f);
//invert the position of the camera so that we can transform the ray
//into world space location.
Matrix3d inverse = this.mTransformation.clone();
inverse.invert();
inverse.transform(ray.position);
inverse.transform(ray.direction);
return ray;
}
}
Now that we can get a ray, we can find an object in the scene. This part gets a bit more difficult as there are many paths to pick depending on how you want to select things and what is considered selectable. Both of these issues depend on the application and the performance you need.
One thing that is probably the same with all the paths is that you need some type of list of selectable objects, and each object needs to have an accesible world space matrix and some way to test for ray intersection. A question that you must answer is how do you deal with overlapping objects. For me, I just sort the objects by how close they are to the camera so that the closest object is selected.
Once you have that part figured out, you need to figure out how you want to test for intersection. I’ll show a way to test intersection with an axis aligned box. An aab is simple to create. Basically its just the minimum and maximum values for x, y, z of a mesh’s vetices in the mesh’s local space. The creation of the aab can be done while importing a mesh. An aab is nice for testing because it runs constant time in respect to the mesh triangle count.
So before going onto the aab intersection, here’s an example of how the picking will be done.
public class Renderer {
private List<Node> mSelectableNodes;
private Camera mCamera;
...
//Update the scene, sort the selectable items by some method, and
//rendering code here
...
public Node select(float x, float y) {
Ray ray = mCamera.createRay(x, y);
Ray objectRay = ray.clone(); //so we don't need to recreate the ray each loop
for(Node node : this.mSelectableNodes){
if(node instanceof Model){
Matrix3d inverse = node.mTransform.clone();
inverse.invert();
inverse.transform(objectRay.position);
inverse.transform(objectRay.direction);
if(node.intersectsRay(objectRay)){ //test the intersection!
return (Model)node;
}
}
}
return null;
}
}
Now the hard part, the intersection. The method being used is by trimming the line represented by the ray by all the sides of the box and seeing if the line still exists.
public class Node {
private Vector3d mMin;
private Vector3d mMax;
...
//code about how to render and update this node.
...
public boolean intersectsRay(Ray ray){
float distanceNear = Float.NEGATIVE_INFINITY;
float distanceFar = Float.POSITIVE_INFINITY;
//Reduce the problem to 2d by testing the box's sides for x, y, and z.
for(int i = 0; i < 3; i++){
float boxMin = mMin.get(i); //make Vector3d's iterable is helpful here
float boxMax = mMax.get(i);
float slope = ray.direction.get(i);
float offset = ray.position.get(i);
if(!Util.floatEquals(slope,0)){
float distanceMin;
float distanceMax;
if(slope > 0) {
distanceMin = (boxMin-offset)/slope;
distanceMax = (boxMax-offset)/slope;
} else {
distanceMin = (boxMax-offset)/slope;
distanceMax = (boxMin-offset)/slope;
}
//see if this is closer
if(distanceMin > distanceNear){
distanceNear = distanceMin;
}
if(distanceMax < distanceFar){
distanceFar = distanceMax;
}
if(distanceNear > distanceFar){
return false;
}
} else if(offset < boxMin || offset > boxMax){
return false;
}
}
//if we make it here, all is good!
return true;
}
}
And there you go. With all those components, you should be able to call the Renderer.select(x, y) method and get the selected node.
Stay tuned for Part 2! That’s where you’ll be able to have the object follow your finger’s position. so it’s like the reverse of selection.
Notes:
* Tripple dot problem: My college physics book would rank the difficulty of a problem by placing dots by them and the hardest problems had 3 dots by them.
