PDA

View Full Version : Mesh-ray intersection test issues



alexDelchev
08-30-2016, 03:03 PM
Hi,

I'm working on my own little 3D engine and I have some problems with mouse picking implementation.

The problem is that I have used the Möller–Trumbore intersection algorithm because I want to test each mesh at the polygon level, but the results I'm getting are not at all accurate. The test returns positive even when I have not clicked on the mesh itself, but rather next to it. I don't know if I'm explaining this properly, please see the pictures at the bottom.

The main idea of my approach to picking is as follows:

1. Construct the ray using the camera position as the origin and obtaining the direction by unprojecting the cursor coordinates into world-space. I'm certain the issue is not here because when I click on the terrain the models accurately move to the cursor position.

2. Test with each selectable model in the scene whether the ray intersects with the model's axis aligned bounding box. The min and max values of the AABB are precomputed upon loading the mesh and when needed are transformed with the respective model's model-to-world matrix. I'm also certain the problem isn't here because I have run tests with "box" models and the results are accurate.

3. Upon detection of intersection with a bounding box, start testing with the triangles of the model:

- I go through the mesh polygons using the mesh indices and test for each triangle.
- If the model is animated I transform each vertex with it's corresponding skinning matrix for the current frame. The problem shouldn't be here as well because I get the same inaccuracies when testing with static(obj format) models and I transform the vertices the same way I do in the shader.
- I have already transformed the ray origin and direction with the model's inverse model-to-world matrix and then normalize the direction. The matrices shouldn't be a problem because I use a third party maths library(JOML) and use the same methods to construct the matrices when rendering without any issues.
- Then I test the triangle using the Möller–Trumbore algorithm, upon detecting an intersection I break out of the main loop and return the ID of the selected model.

As you can see from the pictures, something isn't right here, but I can't see what is actually causing the issue. It could be some big mess, it could be something small, but I can't see it, so that's why I decided to ask here.

Here my code to detect if a model is clicked:


public void handleEvent(double x, double y, List<GameItem> items, int key){
viewMatrix = transformation.updateViewMatrix(camera);

Vector3f origin = new Vector3f(camera.getPosition());
currentRay = calculateMouseRay((float) x, height - (float) y);
Vector3f ray = new Vector3f(currentRay);
boolean itemhit = false;
mainLoop:
for(int i=0; i<items.size(); i++){

ray = new Vector3f(currentRay);

GameItem item = items.get(i);

Matrix4f m = transformation.buildModelWorldMatrix(item);

List<List<Vector3f>> boxes = item.getBoundingBox();

Vector3f min = new Vector3f(Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE);
Vector3f max = new Vector3f(Float.MIN_VALUE, Float.MIN_VALUE, Float.MIN_VALUE);

for(List<Vector3f> box: boxes){
for(Vector3f currentVertex: box){
Vector3f vertex = new Vector3f(currentVertex.x, currentVertex.y, currentVertex.z);
vertex = m.transformPosition(vertex);

min.x = Math.min(min.x, vertex.x);
min.y = Math.min(min.y, vertex.y);
min.z = Math.min(min.z, vertex.z);

max.x = Math.max(max.x, vertex.x);
max.y = Math.max(max.y, vertex.y);
max.z = Math.max(max.z, vertex.z);
}
}


if(traceBoundingBox(ray, origin, min, max)){

float[] positions = item.getMesh().getPositions();
int[] indices = item.getMesh().getIndices();

boolean intersectsPolygon = false;
int weightIndex = 0;
int jointIndex = 0;

m = new Matrix4f(transformation.buildModelWorldMatrix(item ));
ray = new Vector3f(currentRay);
origin = new Vector3f(camera.getPosition());

m.invert();
m.transformPosition(origin);
m.transformDirection(ray);
ray.normalize();
for(int index=0; index<indices.length/3; index++){

float weight = 0;

Vector3f a = new Vector3f();
a.x = positions[indices[index*3]];
a.y = positions[indices[index*3] + 1];
a.z = positions[indices[index*3] + 2];

Vector3f b = new Vector3f();
b.x = positions[indices[index*3 + 1]];
b.y = positions[indices[index*3 + 1] + 1];
b.z = positions[indices[index*3 + 1] + 2];

Vector3f c = new Vector3f();
c.x = positions[indices[index*3 + 2]];
c.y = positions[indices[index*3 + 2] + 1];
c.z = positions[indices[index*3 + 2] + 2];

if(item instanceof AnimatedGameItem){
float[] weights = item.getMesh().getWeights();
int[] jointIndices = item.getMesh().getJointIndices();

Matrix4f[] animationMatrices = ((AnimatedGameItem) item).getLastFrame().getJointMatrices();
Matrix4f jointMat = new Matrix4f();

if(weights.length == (positions.length/3)*4){
Vector3f vert = new Vector3f();
for(int wi=0; wi<4; wi++){
if(weights[weightIndex*4 + wi] > 0){
jointMat = animationMatrices[jointIndices[jointIndex*4 + wi]];
Vector3f temp = new Vector3f(a);
jointMat.transformPosition(temp);
weight = weights[weightIndex*4 + wi];
temp.mul(weight);
vert.add(temp);
}
}
a = new Vector3f(vert);
weightIndex++;
jointIndex++;

vert = new Vector3f();
for(int wi=0; wi<4; wi++){
if(weights[weightIndex*4 + wi] > 0){
jointMat = animationMatrices[jointIndices[jointIndex*4 + wi]];
Vector3f temp = new Vector3f(b);
jointMat.transformPosition(temp);
weight = weights[weightIndex*4 + wi];
temp.mul(weight);
vert.add(temp);
}
}
b = new Vector3f(vert);
weightIndex++;
jointIndex++;

vert = new Vector3f();
for(int wi=0; wi<4; wi++){
if(weights[weightIndex*4 + wi] > 0){
jointMat = animationMatrices[jointIndices[jointIndex*4 + wi]];
Vector3f temp = new Vector3f(c);
jointMat.transformPosition(temp);
weight = weights[weightIndex*4 + wi];
temp.mul(weight);
vert.add(temp);
}
}
c = new Vector3f(vert);
weightIndex++;
jointIndex++;
}
}

intersectsPolygon = intersectTriangle(a, b, c, origin, ray);

if(intersectsPolygon){

if(selectedItem != i && key == LEFT_MOUSE_BUTTON){

itemhit = true;
itemSelected = true;
selectedItem = i;

break mainLoop;
}
}
}
}
}
}
}


Code for to test for bounding box intersection:

public boolean traceBoundingBox(Vector3f ray, Vector3f origin, Vector3f min, Vector3f max){

float dx = 1.0f/ray.x;
float dy = 1.0f/ray.y;
float dz = 1.0f/ray.z;

float tx1 = (min.x - origin.x)*dx;
float tx2 = (max.x - origin.x)*dx;

float minValue = tx1 < tx2 ? tx1 : tx2;
float maxValue = tx1 > tx2 ? tx1 : tx2;

float tmin = minValue;
float tmax = maxValue;

float ty1 = (min.y - origin.y)*dy;
float ty2 = (max.y - origin.y)*dy;

minValue = ty1 < ty2 ? ty1 : ty2;
maxValue = ty1 > ty2 ? ty1 : ty2;

tmin = tmin > minValue ? tmin : minValue;
tmax = tmax < maxValue ? tmax : maxValue;

float tz1 = (min.z - origin.z)*dz;
float tz2 = (max.z - origin.z)*dz;

minValue = tz1 < tz2 ? tz1 : tz2;
maxValue = tz1 > tz2 ? tz1 : tz2;

tmin = tmin > minValue ? tmin : minValue;
tmax = tmax < maxValue ? tmax : maxValue;

return tmax >= Math.max(0, tmin) && tmin < 1000;
}

Code for the Möller–Trumbore intersection algorithm:

private boolean intersectTriangle(Vector3f a, Vector3f b, Vector3f c, Vector3f origin, Vector3f ray){

Vector3f ab = new Vector3f();
b.sub(a, ab);
Vector3f ac = new Vector3f();
c.sub(a, ac);
Vector3f pvec = new Vector3f();
ray.cross(ac, pvec);

float det = ab.dot(pvec);

if(det < 1e-6 && det > -1e-6) {return false;}

float invDet = 1.0f/det;

Vector3f tvec = new Vector3f();
origin.sub(a, tvec);
float u = tvec.dot(pvec) * invDet;

if(u < 0 || u > 1) {return false;};

Vector3f qvec = new Vector3f();
tvec.cross(ab, qvec);
float v = ray.dot(qvec) * invDet;

if(v < 0 || u + v > 1) {return false;}

//float t = ac.dot(qvec)/det;

if(ac.dot(qvec) * invDet > 1e-6) {return true;}

return false;
}

Sorry for the long post, I tried to give only the relevant code. Also sorry for giving direct links to the pictures, but resizing them in order to upload them as attachments lowers the quality too much and it's hard too see.

Any suggestions how to fix this are more than welcome.

https://s21.postimg.io/nz01rvhx3/intersects.jpg

https://s15.postimg.io/anw0syg9n/also_intersects.jpg

https://s13.postimg.io/coylocp53/accurate_ray.jpg