We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.
IndexProgramming Questions & HelpOpenGL and 3D Libraries › Finding intersection point along path of mouse
Page Index Toggle Pages: 1
Finding intersection point along path of mouse (Read 1024 times)
Finding intersection point along path of mouse
Feb 27th, 2006, 5:22pm
 
Couldn't think of a snappier title unfortunately...

Right, I had a problem. Given a known camara position/direction, and the on screen x/y co-ordinates fo the mouse, find that 3d-world-coordinates tha the mouse is covering.

This turne dout to be significantly more complex than I had imagined, and unfortunately does require intersect testing world-polygons, as well as significant ammounts of vector calculations, and I'm sure there must be a better way to do it.

For reference, here is the current code I need to run to find out where abouts on the x/y (z=0) plane the mouse cursor is, from a given camera position:

Code:

camera(0,-50,50,0,0,0,0,0,-1); //setup camera
fill(128,200,128); // a small chunk of th eplane, so we can see object is "on" it.
beginShape(QUADS);
{
vertex(-50,-50,0);
vertex(50,-50,0);
vertex(50,50,0);
vertex(-50,50,0);
}
endShape();

Vector camPos=new Vector(0,-50,50);
Vector camDir=new Vector(0,1,-1);
Vector left=cross(new Vector(0,0,1),camDir); // use temporary "up" until we can calculate the actual version
Vector up=cross(camDir,left);

Vector tmp=rotate(camDir,up,-PI/6.0); // vector along the left side of the view frustrum
Vector tmp2=rotate(camDir,left,-PI/6.0); // vector along the top of the view frustrum

Vector[] camPlane=new Vector[3]; // a plane for us to map on-screen values to.
camPlane[0]=add(new Vector(0,0,0),add(mul(left,1000),mul(up,1000)));
camPlane[1]=add(new Vector(0,0,0),add(mul(left,1000),mul(up,-1000)));
camPlane[2]=add(new Vector(0,0,0),mul(left,-1000));

// find the co-ordinates where the middle/left/top vectors intersect this plane.
Vector mid=intersectPoint(camPlane[0],camPlane[1],camPlane[2],camPos,add(camPos,mul(camDir,300)));
Vector leftEdge=intersectPoint(camPlane[0],camPlane[1],camPlane[2],camPos,add(camPos,mul(tmp,300)));
Vector topEdge=intersectPoint(camPlane[0],camPlane[1],camPlane[2],camPos,add(camPos,mul(tmp2,300)));

//what change does one pixel make
Vector deltaX=div(dir(mid,leftEdge),(float)width/2.0);
Vector deltaY=div(dir(mid,topEdge),(float)height/2.0);

// convert mouse X and Y co-ordinates into vectors in the camPlane
Vector mouseVectorX=add(leftEdge,mul(deltaX,constrain(mouseX,0,width-1)));
Vector mouseVectorY=add(topEdge,mul(deltaY,constrain(mouseY,0,height-1)));

// the Vector in the camera plane of the mouse, from the top left corner
Vector mousePlaneVector=add(mouseVectorX,mouseVectorY);

// the vector from the camera to this point in the camPlane
Vector mouseCameraVector=mul(dir(camPos,mousePlaneVector),100);

// finally! the intersection of the mouse pointer with the "ground" plane.
Vector ip=intersectPoint(new Vector(-1000,-1000,0),new Vector(0,1000,0),new Vector(1000,-1000,0),camPos,add(camPos,mouseCameraVector));


As you can see this is huge, and doesn't even include the 40-odd lines of my VectorMaths library that does the intersect/rotation etc.

So.. is there a better way? There's got to be one, that cannot be the best way to get the correct answer.

It *is* possible to simplify it, but it will give a variably wrong answer, especially if I use larger FOV settings, since the screen is mapped to a flat plane, not a curved surface equidistant from the camera.
Re: Finding intersection point along path of mouse
Reply #1 - Feb 27th, 2006, 6:04pm
 
Yes, it really is a hard problem.  But one that's been solved - the solution just depends on your perspective settings, as you've found out.  

Regarding intersection tests, there are some things you can do to speed it up - testing bounding boxes etc on complex geometry, using frustrum culling and so on.  But it's only worth it for complex scenes.

My 2 attempts and previous forum discussion are here: http://processing.org/discourse/yabb_beta/YaBB.cgi?board=Contribution_3DOpenGL;action=display;num=1115906725;start=3#3 In particular cello linked to this article about doing the same things in OpenGL http://www.3dkingdoms.com/selection.html

One uses a back-buffer to draw colour coded versions of the objects with lighting off and inspects the pixel colour underneath the mouse.  The other projects all the polys into screen space and does 2D intersection testing - fine for depth sorted polys that don't intersect, but bad if there are any intersections.

I never got to the ray casting method (I think) you're using. Do you have a demo of this running?

If we can get this right, I'd encourage a write-up on Processing Hacks, since it's definitely a FAQ without a short answer!
Re: Finding intersection point along path of mouse
Reply #2 - Feb 27th, 2006, 6:05pm
 
As for a better title, some people call it 'picking', or just 'selecting objects in 3D'.
Re: Finding intersection point along path of mouse
Reply #3 - Feb 27th, 2006, 6:20pm
 
It's not quite picking or selecting, since I don't care what lies under the mouse (so the colour method isn't useful), just the world-coordinates of it, so I can draw other objects "on" the object underneath.

I've got a demo of this code at:
http://www.hardcorepawn.com/CoOrds/

The red/blue/green balls are just there to make sure I've got the left/top/mid points right.
Page Index Toggle Pages: 1