Wednesday 25 April 2012

Android: Allowing users to pick 3D objects


I have published some apps on android but up until now I have never done anything with OpenGL, so thought it was about high time I get started. Bring on my first 2d game, I read a book and followed the examples.. and let me tell you that was fun. Then I decided I wanted to do my first 3d game, bring on cube destroy!! (not yet released or finished).

I was not far in to programming my first 3d game before I wanted users to be able to click on objects in 3d space, I was not able to find a complete tutorial on how to do this. After some time I used any resources I could and managed to get it working.. hence this blog to save you time!

So the basic process is broken up as follows:

  1. Create a ray in 3d space based on a user click
  2. Transform any of your 3d objects using the Model view matrix.
  3. Check what objects are in the same space as the ray.
  4. Find the closest object that was clicked if any.


The first thing you need is the coordinates of the click on the screen (screen ordinates and not 3d space ordinates). For those who are unaware the following on method on your view class will get these.

    
    @Override
    public boolean onTouchEvent(MotionEvent e) {
        // MotionEvent reports input details from the touch screen
        // and other input controls. In this case, you are only
        // interested in events where the touch position changed.

        float x = e.getX();
        float y = e.getY();
        
        switch (e.getAction()) {
            case MotionEvent.ACTION_UP:
            // do something with them...
            break;
        }
   }


To use these new coordinates we need to convert them to space coordinates. Lucky for us there is a GLU method that will do this for us (http://developer.android.com/reference/android/opengl/GLU.html). Unlucky for us its not so easy to use, it requires the Model Matrix and View Matrix in order to do the conversions.

The hard part is getting hold of these Matrices, once again the developers at google have come to the party. If you open up the API demo's you will find a package com.example.android.apis.graphics.spritetext, open it and "borrow" the follow classes:
  • MatrixGrabber
  • MatrixStack
  • MatrixTrackingGL
To be able to use these classes you are going to have to set a GL Wrapper on your view. So do the following in your Activity:


    /** Called when the activity is first created. */
    @Override
    public void onCreate(Bundle savedInstanceState)
    {
        super.onCreate(savedInstanceState);
        view = new MyView(this);
        view.setGLWrapper(new GLSurfaceView.GLWrapper() {
            public GL wrap(GL gl) {
                return new MatrixTrackingGL(gl);
            }
        });
        setContentView(view);
    }


So now getting the Model and View Matricies respectivly is as easy as follows:

     MatrixGrabber matrixGrabber = new MatrixGrabber();
     matrixGrabber.getCurrentState(gl);
     matrixGrabber.mModelView;
     matrixGrabber.mProjection;

It will get the Matrix at the current state of OpenGL, so you need acquire them after doing your transformations.

Now we can almost use GLU.gluUnProject. The argument we do not have but will need is the viewport. You would have set your viewport in your Renderer:

     public void onSurfaceChanged(GL10 gl, int width, int height) {
          gl.glViewport(0, 0, width, height);
          //if you set your viewport as above then the argument for GLU.gluUnProject would be.
          int[] viewport = {0, 0, width, height};
          //rest of method

So now we can obtain our ray, all we need is to find the far and near points on the Z axis. I just created a Ray class to hold the near and far vector which had a constructor to create the points.
 

    public Ray(GL10 gl, int width, int height, float xTouch, float yTouch) {
        MatrixGrabber matrixGrabber = new MatrixGrabber();
        matrixGrabber.getCurrentState(gl);

        int[] viewport = {0, 0, width, height};

        float[] nearCoOrds = new float[3];
        float[] farCoOrds = new float[3];
        float[] temp = new float[4];
        float[] temp2 = new float[4];
        // get the near and far ords for the click

        float winx = xTouch, winy =(float)viewport[3] - yTouch;

//        Log.d(TAG, "modelView is =" + Arrays.toString(matrixGrabber.mModelView));
//        Log.d(TAG, "projection view is =" + Arrays.toString( matrixGrabber.mProjection ));

        int result = GLU.gluUnProject(winx, winy, 1.0f, matrixGrabber.mModelView, 0, matrixGrabber.mProjection, 0, viewport, 0, temp, 0);

        Matrix.multiplyMV(temp2, 0, matrixGrabber.mModelView, 0, temp, 0);
        if(result == GL10.GL_TRUE){
            nearCoOrds[0] = temp2[0] / temp2[3];
            nearCoOrds[1] = temp2[1] / temp2[3];
            nearCoOrds[2] = temp2[2] / temp2[3];

        }

        result = GLU.gluUnProject(winx, winy, 0, matrixGrabber.mModelView, 0, matrixGrabber.mProjection, 0, viewport, 0, temp, 0);
        Matrix.multiplyMV(temp2,0,matrixGrabber.mModelView, 0, temp, 0);
        if(result == GL10.GL_TRUE){
            farCoOrds[0] = temp2[0] / temp2[3];
            farCoOrds[1] = temp2[1] / temp2[3];
            farCoOrds[2] = temp2[2] / temp2[3];
        }
        this.P0 = farCoOrds;
        this.P1 = nearCoOrds;
    }   

Something to note here is that the result is homogeneous so x,z,y,w. Just divide the arguments by w to get the arguments.

Ok now we have our ray!! now could be different depending on what objects you are displaying. After doing any transformations to your object you will want to obtain the Model View matrix. Once you have this matrix you can take the vectors that make up your object and multiply them by the Model View matrix, this will transform them to where they are in space when rendered.

My game was made up of cubes, this is how I convert the coordinates:
 
        float[] convertedSquare = new float[Cube.CUBE_CO_ORDS.length];
        float[] resultVector = new float[4];
        float[] inputVector = new float[4];

        for(int i =0; i < Cube.CUBE_CO_ORDS.length;i = i+3){
            inputVector[0] = Cube.CUBE_CO_ORDS[i];
            inputVector[1] = Cube.CUBE_CO_ORDS[i+1];
            inputVector[2] = Cube.CUBE_CO_ORDS[i+2];
            inputVector[3] = 1;
            Matrix.multiplyMV(resultVector, 0, matrixGrabber.mModelView, 0, inputVector,0);
            convertedSquare[i] = resultVector[0]/resultVector[3];
            convertedSquare[i+1] = resultVector[1]/resultVector[3];
            convertedSquare[i+2] = resultVector[2]/resultVector[3];

        }
Now we have our converted square and our ray, we need to check if the exist anywhere in the same space. Its been a while since Linear math at uni so I looked it up on the net, I managed to find a C implementation. So I converted it to Java and hey presto we just call the method for the intersection. Here is a link to the page I got the implementation off: http://softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm#Segment-Plan

Here is the code for intersections:

 
public class Triangle {
    public float[] V0;
    public float[] V1;
    public float[] V2;

    public Triangle(float[] V0, float[] V1, float[] V2){
        this.V0 =V0;
        this.V1 = V1;
        this.V2 = V2;
    }

   
    private static final float SMALL_NUM =  0.00000001f; // anything that avoids division overflow


    // intersectRayAndTriangle(): intersect a ray with a 3D triangle
//    Input:  a ray R, and a triangle T
//    Output: *I = intersection point (when it exists)
//    Return: -1 = triangle is degenerate (a segment or point)
//             0 = disjoint (no intersect)
//             1 = intersect in unique point I1
//             2 = are in the same plane
    public static int intersectRayAndTriangle(Ray R, Triangle T, float[] I)
    {
        float[]    u, v, n;             // triangle vectors
        float[]    dir, w0, w;          // ray vectors
        float     r, a, b;             // params to calc ray-plane intersect

        // get triangle edge vectors and plane normal
        u =  Vector.minus(T.V1, T.V0);
        v =  Vector.minus(T.V2, T.V0);
        n =  Vector.crossProduct(u, v);             // cross product

        if (Arrays.equals(n, new float[]{0.0f,0.0f,0.0f})){           // triangle is degenerate
            return -1;                 // do not deal with this case
        }
        dir =  Vector.minus(R.P1, R.P0);             // ray direction vector
        w0 = Vector.minus( R.P0 , T.V0);
        a = - Vector.dot(n,w0);
        b =  Vector.dot(n,dir);
        if (Math.abs(b) < SMALL_NUM) {     // ray is parallel to triangle plane
            if (a == 0){                // ray lies in triangle plane
                return 2;
            }else{
                return 0;             // ray disjoint from plane
            }
        }

        // get intersect point of ray with triangle plane
        r = a / b;
        if (r < 0.0f){                   // ray goes away from triangle
            return 0;                  // => no intersect
        }
        // for a segment, also test if (r > 1.0) => no intersect

        float[] tempI =  Vector.addition(R.P0,  Vector.scalarProduct(r, dir));           // intersect point of ray and plane
        I[0] = tempI[0];
        I[1] = tempI[1];
        I[2] = tempI[2];

        // is I inside T?
        float    uu, uv, vv, wu, wv, D;
        uu =  Vector.dot(u,u);
        uv =  Vector.dot(u,v);
        vv =  Vector.dot(v,v);
        w =  Vector.minus(I, T.V0);
        wu =  Vector.dot(w,u);
        wv = Vector.dot(w,v);
        D = (uv * uv) - (uu * vv);

        // get and test parametric coords
        float s, t;
        s = ((uv * wv) - (vv * wu)) / D;
        if (s < 0.0f || s > 1.0f)        // I is outside T
            return 0;
        t = (uv * wu - uu * wv) / D;
        if (t < 0.0f || (s + t) > 1.0f)  // I is outside T
            return 0;

        return 1;                      // I is in T
    }


}

Here is a utility class for Vectors:
 
public class Vector {
    // dot product (3D) which allows vector operations in arguments
    public static float dot(float[] u,float[] v) {
        return ((u[X] * v[X]) + (u[Y] * v[Y]) + (u[Z] * v[Z]));
    }
    public static float[] minus(float[] u, float[] v){
        return new float[]{u[X]-v[X],u[Y]-v[Y],u[Z]-v[Z]};
    }
    public static float[] addition(float[] u, float[] v){
        return new float[]{u[X]+v[X],u[Y]+v[Y],u[Z]+v[Z]};
    }
    //scalar product
    public static float[] scalarProduct(float r, float[] u){
        return new float[]{u[X]*r,u[Y]*r,u[Z]*r};
    }
    // (cross product)
    public static float[] crossProduct(float[] u, float[] v){
        return new float[]{(u[Y]*v[Z]) - (u[Z]*v[Y]),(u[Z]*v[X]) - (u[X]*v[Z]),(u[X]*v[Y]) - (u[Y]*v[X])};
    }
    //mangnatude or length
    public static float length(float[] u){
        return (float) Math.abs(Math.sqrt((u[X] *u[X]) + (u[Y] *u[Y]) + (u[Z] *u[Z])));
    }

    public static final int X = 0;
    public static final int Y = 1;
    public static final int Z = 2;
}

Ok so now all we need to do is call the method above and store the intersection, the shortest intersection vector will be the object they clicked!

sorry this is a bit rushed, I will come back and brush it up soon. Hope it helps someone?