Pixel-perfect 3D sprite-picking on cylidrical-billboarded sprites?

Question

Background Info

I have an OpenGL app where a player (just an AABB with an eye-height, look and move vectors), can walk along a 3D grid made of a square cells, essentially like a player walking along a Minecraft level. The cells can also have differing heights, which qualifies it as a 3D level, rather than 2D.

On each cell, there is potential to be a static sprite, which is centered on that cell. The sprite is rendered as a "cylindrical billboard" so that it's always facing the camera, but the base/bottom of the sprite is always rooted in the ground. Like this https://www.youtube.com/watch?v=2-queKkSVnw

(The point I'm making is that these cylindrical billboarded sprites render a bit differently than standard sprites which would be coplanar to the view plane on the vertical axis, as well)

Here's a simple representation, where the green stick is the player, and the pink squares are the billboarded sprites which are centered on their cells.

(Note: normally, the camera view would be from the player's eyes, and thus all the pink sprites should be aligned with the player's view plane)

I also have an "arm reach" vector which is a line segment that extends outward from the crosshair a certain distance, in other words a line segment. This line segment is slightly less than the width of one cell. So, worst case scenario, then, is that this line segment is intersecting with three cells at once, like this:

Question

My question is how should I detect that the user's arm reach ray/segment is intersecting with a vertically billboarded sprite, knowing that the sprites may have transparent pixels?

I know that the first step would be to find which cells the ray/segment is overlapping, as shown in the previous pic as the green-highlighted cells. The next step (in my case) shall be a 3D distance check from the player to the sprite location. If too far, can't click it, no matter how you rotate the camera view (and distort the sprite). After that, I'm unsure. I assume I need to somehow first check if the ray is intersecting the billboarded sprite's "rectangle" (the pink rectangle) (I say rectangle in quotes because it will be a distorted rectangle in first person view, due to perspective angle), and then pixel-pick on the sprite and look for the transparent color, but I'm not sure how to do either of those steps.

Daggerfall somehow accomplished this. Interacting with a billboarded sprite (i.e. a treasure pile) requires you to actually click on a non-transparent pixel of that sprite, or the click doesn't count.

Any sources on related techniques would be greatly appreciated. Thank you for your time!

Answer 1

I would recommend trying it Bálint's way first, because it is much easier to implement, but here is a CPU only solution. The reason you may want to go with this solution is if the extra rendering pass and CPU/GPU communication is giving you performance problems.

You know the position/orientation of the Billboard and Ray, so you can do a series of Ray/Geometry intersection to determine the position on the sprite.

1. Intersect the Ray with the AABB of the Billboard to quickly determine which sprites have a possibility of intersection.

2. Intersect the Ray with the Triangles that make up the chosen billboards to determine the location of intersection.

3. Compare the intersection location to the edges of the billboard using vector projection to determine where it intersects the billboard in pixel space.

4. Check the value of the pixel to determine if it is a hit or miss (no alpha or alpha)

If you need to improve performance, then you can divide the world into chunks, and check the AABB of the Chunk before proceeding with step #1.

Answer 2

When you need to do pixel perfect mouse picking with non geometric objects (e.g. sprites) it's usually better to simply let the GPU handle the pixel part.

Render your pickable objects into a framebuffer with a solid, distinct color based on an index (there are 2^24 different indexes you can have, you probably won't run out of them), then simply sample the color at the position of the crosshair.

A simple way to convert a 24 bit number to a 3 x 8 bit color is:

r = index >> 16 & 255
g = index >> 8 & 255
b = index & 255

Then to convert back you simply do

index = r << 16 | g << 8 | b