Ray Picking

[Daslee]

Okay, this is what I've got:

Vector3 destination = getPickingRay(Display.getWidth() / 2, Display.getHeight() / 2);
				Vector3 p = new Vector3(control.position.x, control.position.y, control.position.y);
				Vector3 d = destination;
				float t = 10000;
				//As you said p+(10000*d)
				//So now I will multiply 10000 with d
				d.mul(t); //Multiply d vector by t, as you said: (10000*d)
				//And now p + d
				d.add(p);
				glDisable(GL_TEXTURE_2D);
					glBegin(GL_LINES);
						glColor3f(1f, 1f, 1f);
						glVertex3f(p.x(), p.y(), p.z());
						glColor3f(0f, 0f, 0f);
						glVertex3f(d.x(), d.y(), d.z()); 
					glEnd();
				glEnable(GL_TEXTURE_2D);

As you can see I colored line as gradient. White end of line moves as I move player, but black always stays almost in center of game x,y,z is around 0,0,0. Also when I move mouse, no one end of line moves. It's really hard to see if it intersects with any box, because that line looks weird, like 2d..

[OverBlob]

Hello, I found this link while I was looking for some ray picking stuff, but I didn't take the time to read it carefully yet, so I don't know if it will be very usefull for you.
However I hope it could help you

http://schabby.de/picking-opengl-ray-tracing/

[abcdef]

Daslee

Its hard to pin point your error, there are plenty of comments giving you lots of advice on what to do. I can't really help you any further at the moment.

Good luck in your debugging though, I suggest you break everything down to simple tests and test everything seperately.

[Daslee]

Hello, I found this link while I was looking for some ray picking stuff, but I didn't take the time to read it carefully yet, so I don't know if it will be very usefull for you.
However I hope it could help you

http://schabby.de/picking-opengl-ray-tracing/

Thanks for helping, but now I can't understand here:

// look direction
        view.subAndAssign(lookAt, position).normalize();
 
        // screenX
        screenHoritzontally.crossAndAssign(view, up).normalize();
 
        // screenY
        screenVertically.crossAndAssign(screenHoritzontally, view).normalize();
 
        final float radians = (float) (viewAngle*Math.PI / 180f);
        float halfHeight = (float) (Math.tan(radians/2)*nearClippingPlaneDistance);
        float halfScaledAspectRatio = halfHeight*getViewportAspectRatio();
 
        screenVertically.scale(halfHeight);
        screenHoritzontally.scale(halfScaledAspectRatio);

How does author gets lookAt vector? And what means that up vector, what position must be in it?

[quew8]

How does author gets lookAt vector? And what means that up vector, what position must be in it?

Firstly a vector is a direction, a vertex is a position.

Any viewing matrix can be defined by three vectors:
look at / forward, which is the direction you look in.
up, which is the upward direction of your view.
left, which is the sideways direction of your view.
All three must be at right angles to one another and normalized.
I find the best way to think of it is as a coordinate system, where lookAt is the z axis, up the y axis and left the x axis. 

In fact if you aren't already constructing your viewing matrix from these vectors (with a call to gluLookAt) the vectors can be directly extracted from the matrix (it must be solely the VIEWING matrix, not modelview). They are the first three elements of the first three rows (or columns depending on the handiness of your matrices) of your viewing matrix.

[Daslee]

So instead of lookAt I can write camera.position.z and instead of up camera.position.y? And one more question about view Vector. I actually do not know what to do with view vector, so I wrote it like this:

Vector3f view = new Vector3f(control.pitch, control.yaw, 0);

Is that's right?

[quew8]

That's not right. Please read this article: http://3dgep.com/?p=1700, it will explain it far better than I could here. Also I would like to apologize, instead of the "left" vector it would be more correct to say the "right" vector. I'm not quite sure what you meant by the view vector. Do you mean the forward/lookAt vector? It is better to get this from the viewing matrix. Presumably you make the viewing matrix with glRotate(yaw, 0, 1, 0) and glRotate(pitch, 1, 0, 0)? If so then the article will explain how the viewing matrix relates to these vectors.

[Daslee]

Im back 
So I think I found the problem. I think that problem is with ray-box intersection or maybe in for loop where checking for intersection, because when it checks for intersection and it found intersection then it continues searching for another (goes through intersected object). Here is short video about it: http://www.youtube.com/watch?v=8gsWnA6uRE4

And image with short explanation: http://img707.imageshack.us/img707/3368/60398683.png

Now as you can see in image for example yellow line (where I'm looking at) intersects with first cube, but also if it continue searching for intersection it will intersects with second cube and second cube will be set as selected. And black line, it intersects with first, second, third and fourth cube, but fourth cube is last intersected, so this one will be selected. But I can't understand why this problem doesn't appears when yaw rotation is between 90 and 180.

So there is the problem, I think, but as in code:

for(Object obj : world.visibleCollidingObjects) obj.selected = false;
				Vector3 destination = getPickingRay(Display.getWidth() / 2, Display.getHeight() / 2);
				Ray rayPick = new Ray(new Vector3(control.position.x, control.position.y, control.position.z), destination);				
				
				//if(control.yaw >= 270 && control.yaw <= 360) rayPick.begin.xyz[1] -= 8;
				//if(control.yaw >= 0 && control.yaw <= 90) rayPick.begin.xyz[1] -= 8;
				for(Object obj : world.visibleCollidingObjects){
					if(rayIntersection(rayPick, obj)){
						obj.selected = true;
						selectedObjectIndex = world.objects.indexOf(obj);
						break;
					}
				}

It will set all objects selected = false, and then searches for intersection with ray, and as you can see if it found intersection it stops for loop with break;, but as I explained it'll searches for intersection with ray-cube till ray end. And what would be solution for this problem? 

[quew8]

You need to check the screen z-coordinate of each cube that intersects and if it less than all the previous intersections then record it and the index of the cube it corresponds to. At the end of the loop, whichever index remains is the closest cube being selected:

for(Object obj : world.visibleCollidingObjects) obj.selected = false;
				Vector3 destination = getPickingRay(Display.getWidth() / 2, Display.getHeight() / 2);
				Ray rayPick = new Ray(new Vector3(control.position.x, control.position.y, control.position.z), destination);				
				
				int index = -1;
                                float minDepth = Float.MAX_VALUE;
				for(int i = 0; i < world.visibleCollidingObjects.length; i++) {
                                        //Change this method to return the depth (z value) of the intersection or Float.MAX_VALUE if there is no
                                        //intersection.
                                        float depth = getDepthOfRayIntersection(rayPick, world.visibleCollidingObjects[i])
                                        if(depth < minDepth ) {
                                                minDepth = depth;
                                                index = i;
                                        }
				}
                                world.visibleCollidingObjects[index].selected = true;
                                selectedObjectIndex = index;

[Daslee]

So now I got this code:

int index = -1;
		float tmin = Float.MAX_VALUE;
		t=tmin;
		float minDepth = Float.MAX_VALUE;
		for(int i=0; i<world.visibleCollidingObjects.size(); i++){
			float depth = 0;
			if(rayIntersection(rayPick, world.visibleCollidingObjects.get(i))){
				t = (world.visibleCollidingObjects.get(i).min.z() - rayPick.begin.z()) / rayPick.dest.z();
				if(t < tmin){
					tmin = t;
				}
				depth = rayPick.begin.add(rayPick.dest.mul(tmin)).z();
			}else{
				depth = Float.MAX_VALUE;
			}
			if(depth < minDepth){
				minDepth = depth;
				index = i;
				break;
			}
		}
		if(index != -1) world.visibleCollidingObjects.get(index).selected = true;
		selectedObjectIndex = index;

Where you commented:

//Change this method to return the depth (z value) of the intersection or Float.MAX_VALUE if there is no
                                        //intersection.

Here I wrote code to get ray intersection point and then get z coordinate, so now if there is intersection with ray and cube, then depth is set as ray intersection point, Z coordinate:

depth = rayPick.begin.add(rayPick.dest.mul(tmin)).z();

But anyway, it's same as before. I even tried to use rayPick.tmin as intersection point which is set in rayIntersection method, but everything's same as before...

EDIT: I done simple test with new lwjgl project, added one line of cubes and tried picking by mouse position. So picking worked good with objects which x position was > 0 and picking worked bad (checked for intersection through objects) with objects which x position was < 0. So maybe this could be another problem, that picking works bad, when looking to objects which positions going to negative numbers?

[quew8]

t = (world.visibleCollidingObjects.get(i).min.z() - rayPick.begin.z()) / rayPick.dest.z();

In the Ray class, is dest the position vector of the end of the ray or is it the direction the ray goes in from the start point?
ie, with a ray AB, is dest B or AB?

If it is the destination as the name would suggest, you shouldn't be dividing by it. You should be dividing by the direction (dest - begin)

Another thing, surely you need to test every single cube now to make sure there isn't one closer, so you shouldn't have the break statement.

Also your code is rather messy; you seem to do more conditional clauses than you need to.
With the correction and a little optimization:

int index = -1;
		float tmin = Float.MAX_VALUE;
		t = tmin; //You don't actually need to work out the depth as it is proportional to t. If t is smaller then the depth would be too
		for(int i = 0; i < world.visibleCollidingObjects.size(); i++) {
			if(rayIntersection(rayPick, world.visibleCollidingObjects.get(i))) {
				t = (world.visibleCollidingObjects.get(i).min.z() - rayPick.begin.z()) / (rayPick.dest.z() - rayPick.begin.z());
				if(t < tmin) { 
					tmin = t;
                                        index = i; //No break statement
				}
			}
		}
		if(index != -1) world.visibleCollidingObjects.get(index).selected = true; //Sorry I didn't include this if in my original. Slipped my 
                                                                                                               //mind
		selectedObjectIndex = index;

[Daslee]

Yes, in Ray class dest is defined as direction. But whatever I try to do, nothing changes. Maybe problem in ray-box intersection method?

EDIT: No, ray-box intersection is good. I tried with another codes from google, so I got same results.

[quew8]

You have got rid of the break statement though? Have you tried testing with just 2 or 3 objects and printing out the intermediate results such as t, tmin and the result of the conditionals. The only other thing I can think of is your rayIntersection() method is slightly wrong. Maybe we could see that.

[Daslee]

Yes, I removed break; in for loop, but still nothing. Tried to print results, so they looks good. And here is two rayIntersection methods, which give same results:

public boolean rayIntersect(Ray r, Object obj){
		float tx1 = (obj.min.x() - r.begin.x()) * r.n_inv.x();
		float tx2 = (obj.max.x() - r.begin.x()) * r.n_inv.x();
		 
		float tmin = Math.min(tx1, tx2);
		float tmax = Math.max(tx1, tx2);
		 
		float ty1 = (obj.min.y() - r.begin.y())*r.n_inv.y();
		float ty2 = (obj.max.y() - r.begin.y())*r.n_inv.y();

		tmin = Math.max(tmin, Math.min(ty1, ty2));
		tmax = Math.min(tmax, Math.max(ty1, ty2));
		
		float tz1 = (obj.min.z() - r.begin.z()) * r.n_inv.z();
		float tz2 = (obj.max.z() - r.begin.z()) * r.n_inv.z();
		tmin = Math.max(tmin, Math.min(tz1, tz2));
		tmax = Math.min(tmax, Math.max(tz1, tz2));
		
		return tmax >= tmin;
	}
	
	public boolean rayIntersection(Ray r, Object obj){
		float tmin = (obj.min.x() - r.begin.x()) / r.dest.x();
		float tmax = (obj.max.x() - r.begin.x()) / r.dest.x();
		if(tmin > tmax){
			float temp = tmin;
			tmin = tmax;
			tmax = temp;
		}
		float tymin = (obj.min.y() - r.begin.y()) / r.dest.y();
		float tymax = (obj.max.y() - r.begin.y()) / r.dest.y();
		if(tymin > tymax){
			float temp = tymin;
			tymin = tymax;
			tymax = temp;
		}
		if((tmin > tymax) || (tymin > tmax))
			return false;
		if(tymin > tmin)
			tmin = tymin;
		if(tymax < tmax)
			tmax = tymax;
		float tzmin = (obj.min.z() - r.begin.z()) / r.dest.z();
		float tzmax = (obj.max.z() - r.begin.z()) / r.dest.z();
		if(tzmin > tzmax){
			float temp = tzmin;
			tzmin = tzmax;
			tzmax = temp;
		}
		if((tmin > tzmax) || (tzmin > tmax))
			return false;
		if(tzmin > tmin)
			tmin = tzmin;
		if(tzmax < tmax)
			tmax = tzmax;
		
		if((tmin > r.tmax) || (tmax < r.tmin)) return false;
		if(r.tmin < tmin) r.tmin = tmin;
		if(r.tmax > tmax) r.tmax = tmax;
		return true;
	}

Ray class:

package utility;

public class Ray {
	public Vector3 begin; //origin
	public Vector3 dest; //direction
	public Vector3 n_inv;
	
	public float tmin, tmax;
	
	public Ray(Vector3 p, Vector3 dest){
		this.begin = p;
		this.dest = dest;
		
		Vector3 temp = dest;
		temp.inverse();
		this.n_inv = temp;
		
		tmin = 0;
		tmax = Float.MAX_VALUE;
	}
}

UPDATE: I found one more bad thing with ray casting. There is a little space between ray and mouse position, here is image example (sorry for bad cursor, lwjgl taking screenshot couldn't save cursor, so I downloaded random from google): http://img189.imageshack.us/img189/5562/screenshot20130312.png

So... As you can see I casted ray from sphere center, to mouse position, but there is little space between mouse and ray. And I think that this is the problem why it picks objects inaccurate, not like I want. For example with mouse I'm on second cube, but by this image, ray would be on first cube, soo... Just need to find solution how to fix it. I could add some float values to ray direction x and y position, but I think that would not be efficient way to fix this problem.

[quew8]

I'm not sure what you mean by

add some float values to ray direction

. But this is most likely a problem with the way you create the ray. Could I see that code?