Optimizing expensive calculation for calculating touch of side of cube

I have this code:

someMethod(){

for (int i = 0; i < numberOfCubes; i++) {
for (int f = 0; f < NUMBER_OF_SIDES; f++) { // Loop over all the
// faces
for (int t = 0; t < 2; t++) { // Loop over the triangles per
// face (2)
if (checkTriangleHit(mTriangleVerticesData[i],
NUMBER_OF_SIDES * 4 * f + NUMBER_OF_SIDES * 2 * t,
depth, i)
&& ((curFace == MINUS_ONE) || (depth[0] < curDepth))) {
curFace = f;
curDepth = depth[0];
}

}
}
}
}

public boolean checkTriangleHit(float[] vertexData, int vertexDataOffset,
float[] depth, int cubeNumber) {
// This function checks whether the passed x and y coordinates hit the
// triangle
// passed as argument. If so, it returns true and updates the depth of
// the hit.
// Else, it returns false
float[] fMVPVector = new float[12];

for (int v = 0; v < 3; v++) {
// Project the 3 vertices of the triangle using the Model, View and
// Projection matrix
Matrix.multiplyMV(fMVPVector, v * 4, mMVPMatrix[cubeNumber], 0,
vertexData, vertexDataOffset + v * 4);

// Perspective division
fMVPVector[4 * v + 0] /= fMVPVector[4 * v + 3];
fMVPVector[4 * v + 1] /= fMVPVector[4 * v + 3];
fMVPVector[4 * v + 2] /= fMVPVector[4 * v + 3];
fMVPVector[4 * v + 3] /= fMVPVector[4 * v + 3];

// Convert x, y to screen coordinates
fMVPVector[4 * v + 0] = (fMVPVector[4 * v + 0] + 1) * mWidth / 2;
fMVPVector[4 * v + 1] = (1 - fMVPVector[4 * v + 1]) * mHeight / 2;

}

// Now consider only x and y coordinates and figure out whether the
// click is in the projected view
// Transformation matrix for an affine coordinate system
float[] fTMatrix = new float[4];
fTMatrix[0] = fMVPVector[4] - fMVPVector[0]; // V1x - v0x
fTMatrix[2] = fMVPVector[5] - fMVPVector[1]; // V1y - v0y
fTMatrix[1] = fMVPVector[8] - fMVPVector[0]; // V2x - v0x
fTMatrix[3] = fMVPVector[9] - fMVPVector[1]; // V2y - v0y

float det = fTMatrix[0] * fTMatrix[3] - fTMatrix[1] * fTMatrix[2];
if (Math.abs(det) < SMALL_NUMBER) {
return false;
}

// Invert now the matrix
float[] fTInvMatrix = new float[4];
fTInvMatrix[0] = fTMatrix[3] / det;
fTInvMatrix[1] = -fTMatrix[1] / det;
fTInvMatrix[2] = -fTMatrix[2] / det;
fTInvMatrix[3] = fTMatrix[0] / det;

// Move the touch event fit in the new coordinate sytem
float[] touchVector = new float[2];
touchVector[0] = x - fMVPVector[0];
touchVector[1] = y - fMVPVector[1];

// Calculate the affine coordinates of the point
float[] touchAffVector = new float[2];
touchAffVector[0] = fTInvMatrix[0] * touchVector[0] + fTInvMatrix[1]
* touchVector[1];
touchAffVector[1] = fTInvMatrix[2] * touchVector[0] + fTInvMatrix[3]
* touchVector[1];

// The new x and y coordinates must be positive and less than 1.
if ((touchAffVector[0] < 0.0f) || (touchAffVector[0] > ONE)) {
return false;
}

if ((touchAffVector[1] < 0.0f) || (touchAffVector[1] > ONE)) {
return false;
}

// The vector v2-v1 is the diagonal of the spanning parallelogram
// Check that the point lies beneath the diagonal of the parallelogram
if (touchAffVector[0] + touchAffVector[1] - ONE > 0.0f) {
return false;
}

// Calculate now the depth of the touch event in the current triangle
depth[0] = touchAffVector[0] * (fMVPVector[6] - fMVPVector[2])
+ touchAffVector[1] * (fMVPVector[10] - fMVPVector[2])
+ fMVPVector[2];
return true;
}


Which calculates whether a tap (android) has been done on a side of a cube.

It works well for one cube, but as of 2 cubes it gets slow and for four it is human noticeable (and irritating).

I plan to use eight cubes in the future so it might be handy to optimize it.

My math skills are not that good so could it be possible to maybe at least give a few hints on how to optimize this?

Thanks a lot,

S.

• I think this requires more information. Does your camera position move? Are your cubes at different depths? Are your cubes next to eachother or are they floating around? The obvious issue is that you're doing huge amounts of matrix math. You need to turn this into a 3d space question first, then (if that's not fast enough) probably use some form of bounding box to cull the cubes you don't need to test against. – blurry May 17 '18 at 19:06
• the cubes are aligned (and the camera doesn't move) but the 8 cubes will have different depth – Bamboomy May 18 '18 at 5:41

It's been mentioned, but you probably need to exclude cubes based on a simple bounding box test first. Also, if you are testing a touch into the projected view space, would this not be just ray cast against projected space. If so, then I would advise the following.

1. Obtain the ray cast of the touch point into your view space.
2. Loop through every cube, test bounding sphere ray cast first, cheap test.
3. if point 2 successful, then , invert a copy of the ray cast so that is now in the local space of the cube. (invert the ray using the inverse of the cube matrix).
4. Test this copy ray cast against the untransformed cube (in its local space).
5. Do a dot product test on the normal of the face of the cube to make sure the face at the least is facing the ray cast. That should bring it down to 3 faces at most to test. meaning only 6 triangles to test from what I can see.
6. if you need to get the depth of the hit, you will have to take the ray cast start from the hitpoint and create a vector, then multiply it back out by the cubes transform.

There are plenty of ray cast code samples out there, hope this helps.

• I upvoted the answer but din't approve it yet because I would like to see it in action, I'll implement it asap and come back, thanks for the answer, it seems promising – Bamboomy May 18 '18 at 5:39
• Yeah. No problem. If you need any code samples around ray projection I can dig up my code. – ErnieDingo May 18 '18 at 8:03
• it depends on the digging you need to do, it will be something pleasant to write from the looks at it so if the digging would be to deep no need, if the digging is medium to low than it would be a nice starting point ;-) – Bamboomy May 18 '18 at 10:57
• It's not too hard. Will put the code for download – ErnieDingo May 18 '18 at 12:26
• Thanks a lot, apparently I will need to refactor quite a bit to get it clean, where can I find it? – Bamboomy May 18 '18 at 21:03