How to select multiple 3D objects programatically

condeagustin · May 11, 2010, 6:02am

Hello everyone

Suppose that I have a FPS view and there are 50 spheres around me in different positions x,y,y and I want to select for example a set of those spheres and then move that set wherever I want. My question is: except for having to pick each one (with a ray coming from the camera position to camera direction) and then move them all, do you know any other selection technique or algorithm for more than 1 object that is faster than having to select each one of them? I mean is there some technique where, for example you fire a lot of rays forming a cone and every object within that cone is selected with just one click? I need information about any other selection technique different from having to select one by one. I would appreciate it a lot if you helped me. Thank you.

Agustin

sbook · May 11, 2010, 6:27am

Your question is a bit confusing as selecting a set of them kind of required you to select them individually

It sounds like you want to do something like dragging a box around the objects you want selected and then selecting them all, is this correct? You could implement this a few different way varying in complexity from testing for their location being inside or outside of this selection zone up to testing each object for collisions with the hypothetical box or cone

condeagustin · May 11, 2010, 3:14pm

Yes, I want something like that, but I don't really know how to implement it. For example, I could fire a lot of rays from the cam's location to the cam's direction and these rays could form a cone. Whatever is intersecting those rays is the set of objects that are going to be selected. Or the hypothetical cone you said could be a normal JMonkey Cone (with transparency) drawn from the cam's location to the cam's direction and check what objects are inside that cone, but again I don't know how to implement this. Can you give me tips? Thank you

sbook · May 11, 2010, 6:55pm

You'll want to start with something like:

myCylinder.hasCollision(objectToTest, true);

Now, with your hypothetical 50 spheres, just iterate through:

Iterator<Spatial> it = allSpheres.getChildren().iterator(); while(it.hasNext()){ Spatial sphere = it.next(); if(myCylinder.hasCollision(sphere, true)){ // Do something with the sphere } }

condeagustin · May 11, 2010, 11:37pm

Ok, the hasCollision method works perfect, but when the object is totally inside the cylinder the hasCollision method returns false! and I need to also know when the object is totally inside the cylinder. How can I do it?

sbook · May 12, 2010, 12:58am

condeagustin said:

Ok, the hasCollision method works perfect, but when the object is totally inside the cylinder the hasCollision method returns false! and I need to also know when the object is totally inside the cylinder. How can I do it?

Well collisions are only occurring when the cylinders are in contact with the geometry making up the cylinder (i.e: the walls). You'd likely need to do x,y,z testing on each of the objects to see if they're within the space that the cylinder takes up..

cylinder.getWorldBound().contains(someSphere.getLocalTranslation());

You'd of course have to do this a bit differently since you're testing to see if the entire sphere is within the cylinder rather than just a single point in the center..

nebelritter · May 12, 2010, 7:55am

Hello,

please correct me if i'm wrong.

If the x,y,z check returns value for point being inside, and collision says no collision, wouldn't than mean, that the sphere is fully coverd by the cylinder?

So combining both ways would lead to distinction of the 4 states, completely inside, inside with collision, outside with collision and completely outside.

As i said, am i wrong?

Nebelritter

normen · May 12, 2010, 9:40am

I have a little "pyramidcollider" class in scalaxy to check which entities are in a given pyramid in space (the broder selection of the user). So you give it the cam location and four points in space that make up the "bottom" four corners of the box (ray from the click position). Then I use this code so see if there are entities inside the pyramid:

t = cam position (pyramid "top")

b1-4 = pyramid "base" corners

public boolean isVectorInPyramid(Vector3f v){ int cnt = 0; Ray ray = new Ray(v, rndVec()); //seiten if ( ray.intersect(t, b1, b2) ) cnt++; //if (cnt>1) return false; if ( ray.intersect(t, b2, b3) ) cnt++; if (cnt>1) return false; if ( ray.intersect(t, b3, b4) ) cnt++; if (cnt>1) return false; if ( ray.intersect(t, b4, b1) ) cnt++; if (cnt>1) return false; //unterseite if ( ray.intersect(b1, b2, b3) ) cnt++; if (cnt>1) return false; if ( ray.intersect(b1, b3, b4) ) cnt++; if (cnt>1) return false; if (cnt==1) return true; else //->(cnt==0 || cnt>1) return false; }

If your random ray collides once with a side of the pyramid you are inside of it, if twice or no time then you are outside :)

sbook · May 12, 2010, 4:49pm

nebelritter said:

Hello,

please correct me if i'm wrong.

If the x,y,z check returns value for point being inside, and collision says no collision, wouldn't than mean, that the sphere is fully coverd by the cylinder?

So combining both ways would lead to distinction of the 4 states, completely inside, inside with collision, outside with collision and completely outside.

As i said, am i wrong?

Nebelritter

:-o Of course! That's much simpler to implement than checking if all of the corners are inside the cylinder..

normen said:

I have a little "pyramidcollider" class in scalaxy to check which entities are in a given pyramid in space (the broder selection of the user). So you give it the cam location and four points in space that make up the "bottom" four corners of the box (ray from the click position). Then I use this code so see if there are entities inside the pyramid:

Only problem with this is that a pyramid is relatively simple since its a square at the bottom.. A cone is a circle and thus has many more 'corners'

normen · May 12, 2010, 5:39pm

sbook said:

Only problem with this is that a pyramid is relatively simple since its a square at the bottom.. A cone is a circle and thus has many more 'corners'

Of course this only works with box selection but most games have box selection and not circle selection?

sbook · May 12, 2010, 8:08pm

normen said:

sbook said:

Only problem with this is that a pyramid is relatively simple since its a square at the bottom.. A cone is a circle and thus has many more 'corners'

Of course this only works with box selection but most games have box selection and not circle selection?

I'd agree, but:

condeagustin said:
I mean is there some technique where, for example you fire a lot of rays forming a cone and every object within that cone is selected with just one click?

Then again, the OP may not be married to the idea of a cone. Either way I've now bookmarked this thread as its presented 2-3 different ways of solving a problem :)

condeagustin · May 13, 2010, 2:37am

Thank you very much guys! It really helped a lot!

ostenning · September 28, 2013, 4:14am

Hi everyone, I spent a few hours attempting various methods to implement a solution to this problem.
This is the easiest, fastest solution I have come by that does not use Ray’s.

For the RTS GUI selection box:

Create a 2D quad and and add it to the guiNode, with a given position and size.
Once you are ready to scan to see if objects exist within this 2d Quad we do the folllowing:
2a. Loop through all the objects/geometry’s that could potentially be inside to box.
2b. Inside the loop, use the camera’s “To ScreenSpace” method: getCamera().getScreenCoordinates(spatialWorldTranslation);

This has then converted your objects 3d position into a 2d position relative to the camera.
Now, we can do a simple X-Y check:

Check if coordinate is inside quad:
if (screenCoord.x > rect.x && screenCoord.x < (rect.x + rect.width))… also for y-axis.

Then select!!

See code:
[java]
private void scanForIntersections() {
float x = rectangle.getWorldTranslation().x;
float y = rectangle.getWorldTranslation().y;
float w = quadShape.getWidth() + x;
float h = quadShape.getHeight() + y;

   ArrayList&lt;Geometry&gt; selectedGeos = new ArrayList&lt;Geometry&gt;(); 
   
    
    for (Geometry geo : scene.getChildren()) {
        
        Vector3f targetWorld = geo.getWorldTranslation();
        Vector3f targetScreen = scene.getCamera().getScreenCoordinates(targetWorld);
        
        if (targetScreen.x &gt; x &amp;&amp; targetScreen.x &lt; w){
            if (targetScreen.y &gt; y &amp;&amp; targetScreen.y &lt; h){
                selectedGeos.add(mol);
            }
        }
    }
}

[/java]

This solution is seems to be faster and more simple than the ray-casting solution.

Regards,
Ostenning

atomix · September 28, 2013, 4:46am

@ostenning:
You code is efficient and also simple, but still can not compare with @normen I suppose. In fact it also have some troubles but its not really obvious if you use it within an RTS, I tell you why:

The screenspace transformation can treat objects behind the camera eye with object in front of it the same!
So if you not selecting object topdown, but occasionally have objects behind you, you scew up.
When you use screenspace transformation in fact use matrix under the hood, and normen’s ray compare look complex but in fact use fewer math operation

Anyway for a RTS and for first try, you good to go.

ostenning · September 28, 2013, 4:55am

@atomix said: @ostenning: You code is efficient and also simple, but still can not compare with @normen I suppose. In fact it also have some troubles but its not really obvious if you use it within an RTS, I tell you why: 1) The screenspace transformation can treat objects behind the camera eye with object in front of it the same! So if you not selecting object topdown, but occasionally have objects behind you, you scew up. 2) When you use screenspace transformation in fact use matrix under the hood, and normen's ray compare look complex but in fact use fewer math operation :p
Anyway for a RTS and for first try, you good to go.

Ah yes, you are right, some objects behind the camera can sometimes be selected. But there could be an easy fix to this: Simply check if the object is infront of camera in its facing direction…

Edit: I tried using the cameras Frustrum.Inside enum to check if the object is inside the cameras vision, therefore removing the geometries selected behind the camera. It didnt work. Can someone elaborate?

Regards,
Ostenning

atomix · September 28, 2013, 5:17am

@ostenning
Revive the quesion a little bit.

@condeagustin said: Suppose that I have a <span style="text-decoration:underline;">FPS view </span>and there are 50 spheres around me in different positions x,y,y and I want to select for example a set of those spheres and then move that set wherever I want. My question is: except for having to pick each one (with a ray coming from the camera position to camera direction) and then move them all, do you know any other selection technique or algorithm for more than 1 object that is faster than having to select each one of them? I mean is there some technique where, for example you fire a lot of rays forming a cone and every object within that cone is selected with just one click?

If you going to check camera direction again, you redo all operation the that the fustum culling did, even if it can be fast; but it use a lot of resources. In normen way, in fact, my selecting framework also use that. You do what fustum culling do both coordinate and direction checking in one step. ( may awkward i know ..:p): - You method: All geometries in the rootNode get sceenspace transformation then camera's plane side checking+ near far checking or vice versa... - The other: All geometries in the rootNode, form a ray and check with a fustum piramid, this is very effecifient method which mentioned in a lot of graphics book.

For an FPS, I recommend doing piramid checking, you can also concerning near, far plane; it exactly what a fustum culling did!