Hi, I'm trying to implement picking in my engine. I got it working with this algorithm:

for (int i = 0; i < meshes.size(); i++) {
		intersect = AABBIntersect(rayOrigin, rayDir, meshes[i]);
		if (intersect) {
			selected = meshes[i];
			break;

		}
}

As you can see, it is quite naive and the main problem is that it is dependent on the order of the meshes in a list, so a mesh behind a wall might be picked by clicking on the wall because the mesh comes first in the list.

My idea to fix this was to calculate the distance between the camera and the AABB of the mesh for every object that is hit and the mesh with the lowest distance is the one that is picked

float minDist = 0.0f;_
for (int i = 0; i < hitMeshes.size(); i++) {
	D3DXVECTOR3 aabbPos = D3DXVECTOR3(meshes[i]->m_cellX, meshes[i]->m_cellY, meshes[i]->m_cellZ);
	D3DXVECTOR3 camPos = m_Camera->GetPosition();
	D3DXMATRIX worldMatrix;

	m_D3D->GetWorldMatrix(worldMatrix);
	D3DXVec3TransformCoord(&aabbPos, &aabbPos, &worldMatrix);

	float distance = dist(camPos, aabbPos);

	if (i == 0) {
		minDist = distance;
		selected = hitMeshes[i];
	} else if (distance < minDist) {
		minDist = distance;
		selected = hitMeshes[i];
	}
}

This partially fixes the issue, but the problem is that this algorithm only works from two directions, otherwise the mesh first in the list is picked anyway, Also it is possible to pick meshes that are partially obstructed by another mesh because the algorithm only considers distance to the AABB.

Is it possible to improve this algorithm so that it works ‘as expected’ while sticking purely with AABB's for collision detection? Thanks.

If I understand correctly, the first method does not work because you stop at the first collision. So you just need to add the if-else-if block that you added in the second method.

float minDist = 0.0f;
for (int i = 0; i < meshes.size(); i++) {
		intersect = AABBIntersect(rayOrigin, rayDir, meshes[i]);
		if (intersect) {
			// selected = meshes[i];			
			// break;
			if (i == 0) {
				minDist = distance;
				selected = meshes[i];
			} else if (distance < minDist) {
				minDist = distance;
				selected = meshes[i];
			}
		}
}

About the second code, if I have correctly understood it…, I only see the camera position but not where it is looking at. So you have a sphere with the center in the camera that intersect with the closest mesh, even if it is behind it.

float minDist = FLT_MAX;
int selected=-1;

for (int i = 0; i < meshes.size(); i++) 
{
		if ( AABBIntersect(rayOrigin, rayDir, meshes[i])) 
		{
			if (distance < minDist)
			 {
				minDist = distance;
				selected = i;
			}
		}
}

when the function ends, you will have the nearest mesh in the ‘selected’ index, else selected will be set to -1

Probably you want to set distance from the closest hit on the box, not just from the box center. Otherwise proposed methods can still fail if multiple boxes overlap.

thanks your responses everyone

@joej is something like that still possible with a simple ray-AABB collision algorithm or does it require something more advanced?

adam7 said:
is something like that still possible with a simple ray-AABB collision algorithm or does it require something more advanced?

It should be very minor changes and probably no extra cost.
Here some code i'm using for the same purpose…

	struct AABox 
	{
		vec minmax[2]; // minimum and maximum corers of the axis aligned box
	
		void DistanceRayFrontAndBackface (float &ffd, float& bfd, const vec& rayOrigin, const vec& rayInvDirection) const
		{
			vec t0 = vec(minmax[0] - rayOrigin).MulPerElem (rayInvDirection); // MulPerElem returns vec3(x*input.x, y*input.y, z*input.z);
			vec t1 = vec(minmax[1] - rayOrigin).MulPerElem (rayInvDirection);
			vec tMin = t0.MinPerElem (t1); // MinPerElem returns smaller value of both input vectors, individually for each dimension
			vec tMax = t0.MaxPerElem (t1);
			ffd = tMin.MaxElem(); // front face distance (behind origin if inside box) // MaxElem returns largest value of all dimensions 
			bfd = tMax.MinElem(); // back face distance	
		}
	};

That's some standard slab test, and we could use it like this:

vec rD(1,0,0); // ray direction
vec rO(0); // ray origin

vec rID (1 / rD[0], 1 / rD[1], 1 / rD[2]); // we can replace zero with a small epsilon 
float ffd, bfd;
aaBox.DistanceRayFrontAndBackface (ffd, bfd, rO, rID);
float t = (ffd > 0) ? ffd : bfd; // always the first intersection with a face
vec intersection = rO + rD * t;
float distance = t * rD.Length();

Here's some example where i use it to get a list of hovered editor nodes sorted by distance:

		std::vector<Link> TraceNodes (Configuration &config, const AABox clippingBox, 
			const vec rO, const vec rD, const float rLength = FLT_MAX)
		{
			bool visContent = config.GetParamB("vis> content");
			bool visNodes = config.GetParamB("vis> nodes");
			bool visBoth = config.GetParamB("vis> both");
			bool skipNonLayerNodes = config.GetParamB("vis> skipNonLayerNodes");
			bool visMesh = config.GetParamB("vis> content meshes");


			vec rID (1 / rD[0], 1 / rD[1], 1 / rD[2]); // todo: jitter required?

			std::vector< std::pair<float, Link> > hits;

			SceneTraversal traversal (this, Link(0, 0));
			while (!traversal.Done())
			{
				Link nodeLink = traversal.CurrentNode();
				const SceneNode* node = GetNode(nodeLink);
				bool descend = node && clippingBox.TestBox(node->branchAABB);
				if (descend)
				{
					float ffd, bfd;
					node->branchAABB.DistanceRayFrontAndBackface (ffd, bfd, rO, rID);
					descend = (ffd <= bfd);
				}
				if (descend)
				{
					float ffd, bfd;
					AABox box = node->nodeAABB;

					bool skip = (skipNonLayerNodes && node->voxelizationSettings.layer.Empty());
					if (!skip)
					{
						bool hasContent = 
								(visMesh && node->contentType == ContentType::MESH_BRUSH) ||
								(node->contentType == ContentType::ANALYTICAL_PRIMITIVE);

						skip = true;
						if ((visContent || visBoth) && hasContent)							
							skip = false;
							
						if ((visBoth && !hasContent) || visNodes) 
							skip = false;
					}

					if (!skip)
					{
						box.DistanceRayFrontAndBackface (ffd, bfd, rO, rID);
						if ((ffd <= bfd) & (ffd >= 0.0f) & (ffd <= rLength))
						{
//ImGui::Text("trace %i %i: %i", nodeLink.index, nodeLink.storageID, descend);
							box = GetLocalBB(nodeLink);
							const matrix& m = GetMatrixFromWorld(nodeLink);
							vec rOl = m.Transform(rO);
							vec rDl = m.Rotate(rD);
							float invLen = 1 / rDl.Length();
							rDl *= invLen;
							vec rIDl (1 / rDl[0], 1 / rDl[1], 1 / rDl[2]);


							box.DistanceRayFrontAndBackface (ffd, bfd, rOl, rIDl);
							if ((ffd <= bfd) & (ffd >= 0.0f) & (ffd <= rLength * invLen))
							{
								float t = (ffd > 0) ? ffd : bfd; // always the first intersection with a face
								float dist = t * invLen;

								//vec worldHit = rO + rD * dist;
								//RenderPoint (worldHit, 0,1,0);
								//RenderPoint (GetMatrixToWorld(nodeLink)[3], 1,0,0);
								

								hits.push_back(std::make_pair(dist, nodeLink));
							}
						}
					}
				}
				traversal.Traverse(descend);
			}

			struct Comparator {
				bool operator() (const std::pair<float, Link>& left, const std::pair<float, Link>& right)
				{
					return left.first < right.first;
				}
			};

			std::sort(hits.begin(), hits.end(), Comparator());
			std::vector<Link> result (hits.size());
			for (int i = 0; i < hits.size(); i++)
				result[i] = hits[i].second;
			return result;
		}
	};

Later i use mouse wheel to scroll forth and back in the list, so i can select a single object out of many intersections with some comfort.

EDIT:
There's a common pitfall when working with front/backface distance. The special case of having the ray origin inside the box often requires some rethinking.