Hi all.
I have made a picking demo but when I pick the delay is up to 50 ms (!!), that’s a long delay if we want a fast engine…
I have a terrain (which is pretty big), and that’s the problem…
Does the picking code pick behind objects, in my case, behind a hill?
How to make it faster?
Thanks in advance!
Emil Alonzo
Hi,
here my solution for terrainpicking:
I cast a ray from eye through intersection with a ground plane. Then i go step by step on this ray forward. If the y-coordinate on the ray at x,y is smaler than the y- coordinate on the terrain(x,y) i go back on the ray, in smaller steps. If the y-coordinate of the ray at x,y is close enough to the y-coordinate at terrain(x,y) i got the intersection point with the terrain.
You do not get the 100% right position with this solution, but you can fit the solution to your needs(performance,precision) by changing the variables precision and heightModifer
I think this solution could be pretty fast if you find the right values for the variables.
//Umwandlung von Screen- in Worldkoordinaten auf einem Terrain
public Vector3f getTerrainIntersection(Point mousePos, Point3f camPos, Point3f lookat)
{
double r=(mousePos.x - screenWidth/2.0f)/(screenWidth/2.0f)*0.935f;
double s=((screenHeight/2.0f - mousePos.y)/(screenHeight/2.0f)) * (screenHeight/screenWidth)*0.935f;
//Vector d from Camera to Lookat
Vector3f d=new Vector3f();
d.x=camPos.x-lookat.x;
d.y=Math.abs(camPos.y-lookat.y);
d.z=camPos.z-lookat.z;
//Vector v1 parallel to Ground and perpendicularly to Vector d
Vector3f v1=new Vector3f();
v1.x=d.z;
v1.y=0;
v1.z=-d.x;
v1.normalize();
// Crossproduct of d and v1
Vector3f v2= new Vector3f();
v2.cross(d,v1);
v2.normalize();
//Plane to project the pointer
Vector3f v=new Vector3f();
v.x=(float)(lookat.x+r*v1.x+s*v2.x); //rayDir=v.x
v.y=(float)(lookat.y+s*v2.y);
v.z=(float)(lookat.z+r*v1.z+s*v2.z);
/*Intersection with x,z-Plane
*Line: l=camPos+w(v-camPos)
*Plane: p=sx*(1;0;0)+sz*(0;0;1)
*l=p ....
*/
float w=(float)(-camPos.y/(v.y-camPos.y));
float sx=(float)(camPos.x+w*(v.x-camPos.x));
float sz=(float)(camPos.z+w*(v.z-camPos.z));
//Plane
Vector3f planeInter=new Vector3f();
planeInter.x=sx;
planeInter.y=0;
planeInter.z=sz;
/*Find Intersection with Terrain
Eine Gerade wird durch Auge und Planeintersection gezogen
Dann wird sich schrittweise vom Auge aus der planeintersection genährt
und dabei überprüft um die y-Koordinate der Geraden mit der y-koordinaten
des Terrains an diesem x,z punkt übereinstimmt.
Ist dies in etwa der Fall(Präzisionsgrad) dann ist der Schnittpuntk mit dem
Terrain gefunden.
Durch Einstellen der Werte von heightModifer und precision kann sowohl
Qualität als auch Rechenaufwand angepasst werden.
*/
Vector3f pointerPos=new Vector3f(camPos);
planeInter.x-=camPos.x;
planeInter.y=camPos.y;
planeInter.z-=camPos.z;
rayDir.x=v.x-camPos.x;
rayDir.y=v.y-camPos.y;
rayDir.z=v.z-camPos.z;
heightModifer=planeInter.length()/70;
rayDir.normalize();
precision=heightModifer/15; //Präzision der Berechnung
n=1;
runs=0;
if(rayDir.y<-0.01f)
{
while(Math.abs(pointerPos.y - Globals.terrain.getY(pointerPos.x,pointerPos.z))>precision
&& pointerPos.y > 0 && runs<200 && n< 15000)
{
if(pointerPos.y > Globals.terrain.getY(pointerPos.x,pointerPos.z))
n+=heightModifer;
else
n-=precision/3;
pointerPos.x=camPos.x+n*rayDir.x;
pointerPos.y=camPos.y+n*rayDir.y;
pointerPos.z=camPos.z+n*rayDir.z;
runs++;
}
}
else
{
pointerPos.x=camPos.x+5000*rayDir.x;
pointerPos.y=camPos.y+5000*rayDir.y;
pointerPos.z=camPos.z+5000*rayDir.z;
}
//System.out.println("Runs: "+runs);
/*if(runs>mostRuns)
mostRuns=runs;
stem.out.println("Most runs: "+mostRuns);
System.out.println("Heightmodifer: "+heightModifer);
System.out.println("Precision: "+precision);*/
return pointerPos;
}
Hope it helps
Jacke
Thanks for the help! 
Alonzo
can someone tell me what “rayDir” is and how do I get it?
It think it’s a vector (correct me if i’m wrong).
So add
Vector3f rayDir = new Vector3f();
above the
rayDir.x=v.x-camPos.x;
rayDir.y=v.y-camPos.y;
rayDir.z=v.z-camPos.z;
bit and it should work ok.
Have anybody a function to get :
A thread on picking:
http://www.java-gaming.org/cgi-bin/JGNetForums/YaBB.cgi?board=xith3d;action=display;num=1104393946
Have a look for the geometry directory in xithtk, there is some code.
Please report to me if some code is missing or buggy.
This is the picking code:
Point3f point= new Point3f();
Vector3f vec = new Vector3f();
getCanvas3D().createPickRay(x, y, point, vec);
Ray ray = new Ray(point, vec);
Point3f p = null;
Triangle triangle = null;
for (Triangle t : getTriangles(shape)) {
Point3f temp = t.intersects(ray);
if (temp != null) {
p = temp;
triangle = t;
System.out.println("Coordinate of intersection=" + p);
break;
}
}
getTriangles() :
public Triangle[] getTriangles(Shape3D poShape3D) {
Triangle[] aoTriangle = null;
Vector3f oVector3f = new Vector3f();
poShape3D.getLocalToVworld().getTranslation(oVector3f);
Geometry oGeometry = poShape3D.getGeometry();
if (oGeometry instanceof GeomIndexedContainer) {
GeomIndexedContainer oGeomIndexedContainer = (GeomIndexedContainer)oGeometry;
int[] aiIndices = oGeomIndexedContainer.getIndex();
aoTriangle = new Triangle[aiIndices.length / 3];
for (int i = 0, j = 0; i < aiIndices.length; i++, j++) {
Point3f oPoint3f1 = new Point3f();
Point3f oPoint3f2 = new Point3f();
Point3f oPoint3f3 = new Point3f();
oGeometry.getVertex(aiIndices[i], oPoint3f1);
oGeometry.getVertex(aiIndices[i + 1], oPoint3f2);
oGeometry.getVertex(aiIndices[i + 2], oPoint3f3);
oPoint3f1.add(oVector3f);
oPoint3f2.add(oVector3f);
oPoint3f3.add(oVector3f);
aoTriangle[j] = new Triangle(oPoint3f1, oPoint3f2, oPoint3f3);
i += 2;
}
} else {
aoTriangle = new Triangle[oGeometry.getVertexCount() / 3];
for (int i = 0, j = 0; i < oGeometry.getVertexCount(); i++, j++) {
Point3f oPoint3f1 = new Point3f();
Point3f oPoint3f2 = new Point3f();
Point3f oPoint3f3 = new Point3f();
oGeometry.getVertex(i, oPoint3f1);
oGeometry.getVertex(i + 1, oPoint3f2);
oGeometry.getVertex(i + 2, oPoint3f3);
oPoint3f1.add(oVector3f);
oPoint3f2.add(oVector3f);
oPoint3f3.add(oVector3f);
aoTriangle[j] = new Triangle(oPoint3f1, oPoint3f2, oPoint3f3);
i += 2;
}
}
return aoTriangle;
}
I don’t know how to optimize it but please somebody try.
I don’t even know how to pick the whole universe, I only know how to check if a shape is being picked, but triangle and point of intersection is in for the moment ;).
Good luck and please optimize and add code.
Alonzo
Thanks Macca, I’ve had some more time to look at this and realized Globals.terrain.getY is also undefined. Any ideas about that one?
Globals.terrain.getY(pointerPos.x, pointerPos.z)
I am getting so frustrated with this, I can’t get this to work. Most of this stuff I am not following. I either need a detailed tutorial to follow or some code I can plug in and run with.
I have my eye at (camX, camY, camZ) and I have it looking at (viewX, viewY, 0) I’m just trying to get the X,Y coords where the user clicked Z will always be 0 its a flat terrain… I’ve spent so much time on this and still have nothing 
please help!
Yeah i know, it can be really frustrating to do something so obvious i spent ages trying to understand this!
The terrain.getY() is getting the height of point x, z on your terrain. y is up, not z!
The Globals.terrain is your Terrain class (if you’re using the demo i think you can just delete the “Globals.” bit.) otherwise replace this with the name of your Terrain object. I’m not sure you need this if your terrain’s going to be flat because its always going to return 0, but i guess its best to leave it in incase you have mountains and stuff later.
Are you using Terrain or have you just got a flat shape? If so, this method won’t help you, check out DonCrudelis’ code above. You should be able to just plug it in, though you might have to change the getCanvas3D() bit for the name of your canvas object. ‘x’ and ‘y’ are your mouse points on the screen, ‘shape’ is your terrain shape. I think p will return the point you’re looking for.
Hope this helps!
I have got a flat shape… a quad. So I should try DonCrudelis’ code or is that just for terrain object? Here is what I’m doing now, I changed Global.terrain.getY to 0, and I pass in Z for Y and Y for Z since I have Y as up.
public void mouseClicked(MouseEvent e) {
Vector3f vect = new Vector3f();
vect = getTerrainIntersection(e.getPoint(), new Point3f(camX, camZ,
camY), new Point3f(viewX, 0, viewY));
System.out.println(vect.x); // x coord
System.out.println(vect.z); // y coord
isViewChangeScheduled = true;
}
What I get out of this are values very close to my viewX and viewY I put into it. My viewX=5 and viewY=5 i get output like:
X = 5.0227056
Y = 4.992122
X = 5.004961
Y = 5.0184546
X = 4.9696717
Y = 5.014441
clicking in various places - this is obviously not what I want =/
oh yeah, and this is with the camera overhead looking straight down, if I change the angle of it then it gives me different numbers, but still nothing close to what I want
Hi
As far as I got to know this stuff, we still have to enumerate through all Triangles in the world - this is for big worlds a really big problem. Has anybody got a solution for this? I think a good selection algorithm could very much increase the speed.
I don’t even know if something of this kind already exists in xith/jogl, because a good renderer should also use this kind of thingi, because a renderer that tries to render something behind the view is a lot slower than a renderer thet only renders stuff in front of the view.
I found another post mentioning Canvas3D.createPickRay(). I had to download the method from CVS but it was worth it, helped me a ton I think I got it figured out now. Thanks guys!
createPickRay() from CVS
public void createPickRay(int x, int y, Point3f o, Vector3f d) {
float w = (float) canvas.getWidth();
float h = (float) canvas.getHeight();
float a = h / w;
if (view.getProjectionPolicy() == View.PERSPECTIVE_PROJECTION) {
// normalize the pixel location to between -1.0 and 1.0 and modify the x
// coordinate to take aspect ratio into account.
float rx = (2.0f * (float) x / w - 1.0f) / a;
float ry = 2.0f - 2.0f * (float) y / h - 1.0f;
// calculate the distance between viewer and view plane.
float vpd = 1.0f / (float) Math.tan(view.getFieldOfView());
// originate the ray at the local origin of the viewer and direct it
// toward the local position of the click in the view plane.
o.set(0.0f, 0.0f, 0.0f);
d.set(rx, ry, -vpd);
d.normalize();
} else {
// normalize the pixel location to between -1.0 and 1.0 and modify the y
// coordinate to take aspect ratio into account.
float rx = 2.0f * (float) x / w - 1.0f;
float ry = a * (2.0f - 2.0f * (float) y / h - 1.0f);
// originate the ray at local position of the click in the view plane
// and direct it along the -Z axis.
float s = view.getScreenScale();
o.set(s * rx, s * ry, 0.0f);
d.set(0.0f, 0.0f, -1.0f);
}
// transform the ray into world space.
view.getTransform().transform(o);
view.getTransform().transform(d);
}
Hi
I’ve got two things to say:
1.
I’ve got a very good way of checking collisions with the whole scene, without calculating intersections with all Triangles. It works like this:
Vector toLookCloserAt = new Vector();
Stack s = new Stack();
s.push(root);
while(!s.empty()) {
Node n = (Node) s.pop();
if(n.getVworldBounds().intersect(origin, direction) { //Intersection with ray
if(n instanceof Group) {
s.addAll( ((Group) n).getChildren);
}
else toLookCloserAt.add(n);
}
}
//now you only have to test the Shape3D's in toLookCloserAt
DonCrudelis had some code for getting the triangles from a Shape3D. But it only seems to work for GeomIndexedContainer and not for any other kinds of Geometry, too.
Has anybody a better solution to get the Triangles than by testing for all kinds of Geometry. The major problem here for me is, that GeometryStripArray saves the stuff differently than a simple Trianglearray. At least I think so!
[quote]Hi
I’ve got two things to say:
1.
I’ve got a very good way of checking collisions with the whole scene, without calculating intersections with all Triangles. It works like this:
Vector toLookCloserAt = new Vector();
Stack s = new Stack();
s.push(root);
while(!s.empty()) {
Node n = (Node) s.pop();
if(n.getVworldBounds().intersect(origin, direction) { //Intersection with ray
if(n instanceof Group) {
s.addAll( ((Group) n).getChildren);
}
else toLookCloserAt.add(n);
}
}
//now you only have to test the Shape3D's in toLookCloserAt
DonCrudelis had some code for getting the triangles from a Shape3D. But it only seems to work for GeomIndexedContainer and not for any other kinds of Geometry, too.
Has anybody a better solution to get the Triangles than by testing for all kinds of Geometry. The major problem here for me is, that GeometryStripArray saves the stuff differently than a simple Trianglearray. At least I think so!
[/quote]
Okay, this advance the Picking discussion.
I’ll see if I can do a little function to get all Triangle in it ( even if there is TriangleStrip information, or Quad ).
I think there is a problem only if the Geom is composed of segments instead of faces ( triangles or quads ).
I think there really has to be a way, because the renderer has to do it in some way too - and testing for all kinds of classes would be no good object oriented programming.
Some things I found out 
:
GeomContainer has a Function called getVertexFormat() - it seems to return an integer - what the int means i think is saved in the static variables of GeomContainer. This might be the way to get an idea of how to interpret the VertexData without testing for all kinds of Geometry classes. We would still have to test for all the different types :-[ .
Actually I think there must be a better way, because the Geometry stuff wouldn’t be able to be extended then.
Something I also stepped across is GeometryTranslocator. Where does it fit in?
I’m having some trouble with picking. I’ve got my pickable objects arranged in a BranchGroup. When I add a node to the group its bounds get set to some default value which is totally wrong.
All the nodes also get set to this same value even if I manually set the bounds and turn off autocompute before hand. When I try and pick them they all intersect no matter where I click.
Anyone got any ideas what I’m doing wrong?
The Bounds should autocompute correctly.
Are you testing this, by showing the bounds with setShowBounds ? - It doesn’t work correctly.
Was using breakpoints but I’ve got this sorted now thanks, used the view.pick instead