I'm working on a piece of legacy software, which has code that takes a mesh/3d point/radius/direction, and computes a list of vertices that are selected.
public static List<int> GetSelectedVertices(PointCloud model, Vec3 markPoint, Vec3 direction, float selectionRadius)
{
List<int> outputVertices = new List<int>();
Vec3 normal = GetNormal(direction);
foreach(int vertexId in model.VertexIds)
{
Vec3 facetPosition = model.GetFacetPosition(vertexId);
Vec3 vec3d = facetPosition - markPoint;
var computation = vec3d.X * vector3.X + vec3d.Y * vec3d.Y + vec3d.Z * vec3d.Z -
FloatSquare(vec3d.X * normal.X + vec3d.Y * normal.Y + vec3d.Z * normal.Z)
if(computation < selectionRadius)
{
outputVertices.Add(vertexId);
}
}
return outputVertices;
}
public static float FloatSquare(float input)
{
return input * input;
}
public static Vec3 GetNormal(Vec3 input)
{
double num = 1.0 / Math.Sqrt(input.X * input.X + input.Y * input.Y + input.Z * input.Z);
return new Vec3(num * input.X, num * input.Y, num * input.Z);
}
Given a list of vertices and their positions(highlighted in red in the image below, I want to compute a 3D point & radius that would allow GetSelectedVertices to encompass as many of the input vertices as possible, while minimizing inclusion of unnecessary vertices(i.e. any vertices that are not highlighted in red). Also, the ability to define a maximum radius would be extremely helpful.
Unfortunately I'm not allowed to change the GetSelectedVertices implementation, and minimizing the selection of unnecessary vertices is highly important.
I've currently tried two approaches, with lackluster results:
- Divide and conquer approach, where I split a bounding box into tiny segments and try each one(too slow, and suboptimal)
- Selecting the highest vertex, or the vertex closest to the bounding box center(too inaccurate)
Are there any well-known solutions to similar problems, or other approaches I could take?
Edits:
- Encompassing some unselected vertices is perfectly ok, but there is a cost to them. As a heuristic, something like 20% growth is acceptable. I.e. If you were to grow my selection by 20%, any newly selected facets are perfectly fine to encompass.
