Camera.getPickRay() With BoundingBox Using Intersector about libgdx HOT 14 CLOSED

From [email protected] on October 08, 2010 17:57:15

Further investigation indicates that the camera's distance from the bounding box makes a difference. Being farther away makes the touch go undetected. I haven't hunted around in the code for a root cause.

from libgdx.

From badlogicgames on October 08, 2010 18:31:40

The ray is probably handled as a segment, so the direction's length is actually playing a role. I'll have to dig into the inner workings of the intersection code. It's been a while (like 3 years :p) since i last looked at it. Thanks for reporting the issue.

As a quick fix you can artifically increase the length of the direction by a large factor

Status: Accepted

from libgdx.

From badlogicgames on October 08, 2010 18:37:30

After further inspection there seems to be something else going on. The hit test is completely inaccurate, something that i'd not expect. I'll report as soon as i find the issue.

from libgdx.

From [email protected] on October 08, 2010 18:43:44

Check that I'm using the Intersector class correctly first, obviously. I think I'm using it right, but it's worth double checking.

The hack of multiplying by 16384f does fix the core issue, so I agree it's probably at least partially related to the direction's length. This is a significant improvement over my old hack of making the BoundingBox much larger than it needed to be.

from libgdx.

From badlogicgames on October 08, 2010 18:56:48

Yes, it is indeed an issue with the rays direction lenght. Your code has another problem though:

public boolean applyRay(Ray ray) {
int tileCount = terrain.getDepth() * terrain.getWidth();
for (int i=0; i < tileCount; i++) {
if (Intersector.intersectRayBoundsFast(ray, boundingBoxes[i])) {
this.lastTileTouched = i;
return true;
}
}
this.lastTileTouched = -2;
return false;
}

This will return as soon as ANY intersection is found. This does not mean that it found the nearest intersection. So, assuming your direction length is scaled, you try to hit the upper area of the blue tile on the bottom left. The code will report that the red tile is hit. And indeed it is, but the intersection point with the blue tile's bounding box is closer to the camera so you should actually try to find the closest intersection point instead of using the first you find.

Intersector.intersectRayBoundsFast() does not return an intersection point. So either use change to Intersector.intersectRayBoundsFast() or you use a trick: each bounding box has a center. When you hit a bounding box you take the distance from its center to the camera and decide whether it is closer than the previous closest hit bounding box.

I'll fix the direction length problem asap.

Thanks for reporting!

from libgdx.

From badlogicgames on October 08, 2010 19:05:08

Issue 46 has been merged into this issue.

from libgdx.

From [email protected] on October 08, 2010 19:15:32

D'oh. The issue of finding only nearest is something I've fixed in the game I'm developing, where I found this bug, but I didn't port the fix to the BoundingBoxTest. Same for the infinitesimal width (experimentally, I found that the BoundingBox had to be at least 1f/33554430f thick). However, the latter (which is now a dupe of this bug) depends on if you check for passing through one of the BoundingBox planes (a flat box will be a single plane, the top and bottom being identical, while a non-flat box will have six planes) or check for being internal to the box somewhere.

You say "Intersector.intersectRayBoundsFast() does not return an intersection point. So either use change to Intersector.intersectRayBoundsFast()" Unless I'm more tired than I think I am, that's the same function. Anyway, this goes back to the Terrain stuff from this thread: http://www.apistudios.com/hosted/marzec/badlogic/forum/viewtopic.php?f=11&t=45&start=10 So when I find a candidate Bounding Box, I find the actual terrain tile's intersection (which does not seem to have issues with distance) and use that for further reference. The Bounding Box is only used for narrowing down the search space.

from libgdx.

From badlogicgames on October 08, 2010 19:41:34

Sorry about my incoherent ramblings, it's 4:30am over here :p

Intersector.intersectRayBoundsFast() has no alternative that gives you an exact intersection point. I'll add that to my todo list. One way to solve this temporarily would be to first make sure the ray intersects the bounds and then find the nearest ray/plane intersection for the bounds relative to the camera position. This is wasteful though so i suggest a different method.

When you find a candidate bounding box via Intersector.intersectRayBoundsFast take the distance from the bounding box' center to the ray origin (== camera position). If that distance is smaller than the previously found distance (or an initial value of Float.MAX_VALUE) then you have your new closest intersection. Repeat for all bounding boxes and you'll get the bounding box that is nearest with two relatively cheap tests, the fast ray/bound intersection and the distance calculation between the bounding box center and the ray origin (== camera position). You don't need the exact intersection point as you are only interested in the tile that was hit. Thus a simple check to see which hit tile is closest to the camera suffices.

hth

from libgdx.

From [email protected] on October 08, 2010 19:50:14

I don't think you can narrow down first solely by which center point in which bounding box are closest, at least not with how Terrain can currently be created. I think it's necessary to determine which tile was hit as well (or at the very least, that a tile was hit, and at that point you're going to know anyway).

The reason is this: Imagine a camera pointing along the Z-axis, so there's a long row of chunks occluding others. The frontmost chunk has a really tall tile at its corner, while the backmost chunk has a really tall tile in the middle. The effect of this is that the bounding box of the nearest tile takes up the entire camera's view. Clicking on the spire in the middle, associated with the backmost chunk, will return a false positive indicating that the frontmost chunk was the one that was hit.

from libgdx.

From badlogicgames on October 09, 2010 05:59:43

As long as your tiles are flat as it is now the method would work. For arbitrary tile heights there would indeed be a problem.

After you determined a candidate bounding box you just need to intersect against its two triangles which will give you intersection point(s) you can meassure the distance to.

There's another method that's actually faster: think of the intersection of the ray with the terrain as a line drawing problem. View the terrain from above. Now trace the ray over this 2D view, only using its direction's x and z component. You can trace via the Bresenham algorithm or via DDA. For each tile you pass while tracing intersect the full 3D ray against its triangles. The first tile you itersect is your nearest tile (given that you start tracing from the origin of the ray).

You can end the trace as soon as the ray passes out of the terrain's x/z bounding box. If the ray starts outside of the x/z bounding clip the ray. If the ray has no x/z direction component only test the tile the origin is located in in x/z.

A bit more involved but blazingly fast.

from libgdx.

From [email protected] on December 18, 2010 17:08:18

I had exactly same issue as described up there, worked around by doing:

picker.direction.mul(100);

where picker is the ray returned by camer.getPickRay()

from libgdx.

From [email protected] on March 11, 2011 06:35:27

Based on the algorithm at http://ompf.org/ray/ray_box.html I've coded a replacement which works for me. Please free to use in libgdx if it helps.

static public boolean intersectRayBoundsFast(Ray ray, BoundingBox box) {
float a, b;
float min, max;
float divX = 1 / ray.direction.x;
float divY = 1 / ray.direction.y;
float divZ = 1 / ray.direction.z;

a = (box.min.x - ray.origin.x) * divX;
b = (box.max.x - ray.origin.x) * divX;
if(a < b) {
    min = a;
    max = b;
} else {
    min = b;
    max = a;            
}

a = (box.min.y - ray.origin.y) * divY;
b = (box.max.y - ray.origin.y) * divY;
if(a > b) {
    float t = a;
    a = b;
    b = t;
}

if(a > min)
    min = a;
if(b < max)
    max = b;

a = (box.min.z - ray.origin.z) * divZ;
b = (box.max.z - ray.origin.z) * divZ;
if(a > b) {
    float t = a;
    a = b;
    b = t;
}

if(a > min)
    min = a;
if(b < max)
    max = b;

return (max >= 0) && (max >= min);

}

from libgdx.

From badlogicgames on March 11, 2011 07:14:43

Great, I'll give this a try. Could you provide me with an author name i can put into the Intersector.java file?

from libgdx.

From badlogicgames on March 13, 2011 10:23:45

Great, that seems to work as expected. At long last i can fix this bug :)

Thanks!

Status: Fixed

from libgdx.