## Re: [Algorithms] Finding a free spot for circles in a triangle mesh.

 Re: [Algorithms] Finding a free spot for circles in a triangle mesh. From: Paul Du Bois - 2004-11-29 04:27:20 I have a similar problem, but in 3D, and it is a pain in the butt. I do a sphere vs sea-of-triangles intersection test and find the nearest feature, then travel (penetration distance + slop) outwards along the face normal (not the feature normal; that ended up not working so well). Repeat up to N times until the sphere is not intersecting any more, increasing slop as you go. Perform a sweep test from the final position to the original position. This works OK in practice, but I don't generally have to handle difficult cases; for those, it is likely to fail after N iterations. For your problem, it might help to think about it as something like Given a set of closed polygons S, a point P, and a radius r, determine whether P is in the volume minkowski_sum(S, circle of radius r). If it is, return the closest feature. This is a pretty easy collision problem. The minkowski sum can be precomputed for a few sample radii. You could simply the sum by only expanding edges and not verts; bevel the acute corners and make a bsp; etc etc.