Ok…. I wrote it myself… as usual.
Sharing code here, in case anyone needs:
I don’t know if it very efficient, but on my computer it runs with frequency of 53000 per second, or 830 per 1 frame (60 fps). At least it is mathematically correct and is based on solving the following problem for each face: (a1*x1+a2*x2+a3*x3-x0)^2+(a1*y1+a2*y2+a3*y3-y0)^2+(a1*z1+a2*z2+a3*z3-z0)^2 -> MIN
subject to constraints:
a1 >= 0,a2 >= 0,a3 >= 0
a1+a2+a3 = 1
You can use it to stick some character or any object to some surface (but remember that calculations will become tough with number of faces increasing. In my case I have 12 face mesh)
//returns a point in 3D space on the surface of mesh, which is the closest (in terms of Euclidean distance) to the specified point
//out - is output vector (if specified - will write there and no new Vector3D object created)
private static var _gnp_v:Vector.<Number> = new Vector.<Number>(9, true);//vector with 3 vertices (here for speedup)
public static function getNearestPoint(point:Vector3D, mesh:Mesh, out:Vector3D=null):Vector3D {
if (mesh == null || point == null) return null;//don't play with me
var vertexOffset:uint = mesh.subMeshes[0].vertexOffset;
var vertexStride:uint = mesh.subMeshes[0].vertexStride;
var indexData:Vector.<uint> = mesh.subMeshes[0].indexData;
var vertexData:Vector.<Number> = mesh.subMeshes[0].vertexData;
var ind1:uint, ind2:uint, ind3:uint;//indices of face vertexes in vertexData
var x0:Number=point.x, y0:Number=point.y, z0:Number=point.z;//point coordinates
var x1:Number, y1:Number, z1:Number, x2:Number, y2:Number, z2:Number, x3:Number, y3:Number, z3:Number;//coordinates of face verteces
var x03:Number, x13:Number, x23:Number, x21:Number;
var y03:Number, y13:Number, y23:Number, y21:Number;
var z03:Number, z13:Number, z23:Number, z21:Number;
var v21_23:Number, v13_23:Number, v03_13:Number, v13_sq:Number;
var a1:Number, a2:Number, a3:Number;//optimal weights for vertex1,vertex2,vertex3 (need to find them in solution)
var mode:uint, dist:Number, distBest:Number, faceBest:uint;
var rx:Number, ry:Number, rz:Number, rxBest:Number, ryBest:Number, rzBest:Number;//point we are searching for
distBest = Number.MAX_VALUE;
var faceIndex:int=indexData.length-1;//points to last vertex of the last face
while (faceIndex > -1) {//faces iteration;
//get coordinates of the triangle's 3 vertices (v1,v2,v3)
ind3 = vertexOffset + indexData[faceIndex--] * vertexStride;
ind2 = vertexOffset + indexData[faceIndex--] * vertexStride;
ind1 = vertexOffset + indexData[faceIndex--] * vertexStride;//faceIndex point to last vertex of previous face
//and apply transformation matrix
_gnp_v[0] = vertexData[ind1]; _gnp_v[1] = vertexData[uint(ind1 + 1)]; _gnp_v[2] = vertexData[uint(ind1 + 2)];
_gnp_v[3] = vertexData[ind2]; _gnp_v[4] = vertexData[uint(ind2 + 1)]; _gnp_v[5] = vertexData[uint(ind2 + 2)];
_gnp_v[6] = vertexData[ind3]; _gnp_v[7] = vertexData[uint(ind3 + 1)]; _gnp_v[8] = vertexData[uint(ind3 + 2)];
mesh.sceneTransform.transformVectors(_gnp_v,_gnp_v);
x1 = _gnp_v[0]; y1 = _gnp_v[1]; z1 = _gnp_v[2];
x2 = _gnp_v[3]; y2 = _gnp_v[4]; z2 = _gnp_v[5];
x3 = _gnp_v[6]; y3 = _gnp_v[7]; z3 = _gnp_v[8];
//calculate required differences
x03 = x0 - x3; x13 = x1 - x3; x23 = x2 - x3; x21 = x2 - x1;
y03 = y0 - y3; y13 = y1 - y3; y23 = y2 - y3; y21 = y2 - y1;
z03 = z0 - z3; z13 = z1 - z3; z23 = z2 - z3; z21 = z2 - z1;
v21_23 = x21*x23 + y21*y23 + z21*z23;
v13_23 = x13*x23 + y13*y23 + z13*z23;
v03_13 = x03*x13 + y03*y13 + z03*z13;
v13_sq = x13*x13 + y13*y13 + z13*z13;
//calculate the solution (a1, a2, a3) of minimization without conditions a1>=0 a2>=0 a3>=0 but with condition that a1+a2+a3==1
a1 = (v03_13*v21_23 - (x03*x21 + y03*y21 + z03*z21)*v13_23 );
a1 = a1 / (v13_sq*v21_23 - (x13*x21 + y13*y21 + z13*z21)*v13_23);
a2 = (v03_13 - v13_sq*a1)/v13_23;
a3 = 1 - a1 - a2;
//cool now adjust a1,a2,a3 for condition a1>=0 a2>=0 a3>=0
mode = 0;//means all conditions correct - optimal point is inside the triangle
if (a1 < 0) { a1 = 0; mode++; }
if (a2 < 0) { a2 = 0; mode++; }
if (a3 < 0) { a3 = 0; mode++; }
if (mode > 1) {//means will get exactly on some vertex of triangle
if (a1) a1 = 1
else if (a2) a2 = 1;
else a3 = 1;
} else if (mode == 1) {//means will be on the edge (same problem but with condition that one a = 0)
if (!a1) {//edge between v2 and v3
a2 = (x03*x23 + y03*y23 + z03*z23)/(x23*x23 + y23*y23 + z23*z23);
if(a2<0)a2=0 else if(a2>1)a2=1
a3 = 1 - a2;
} else if (!a2) {//edge between v1 and v3
a1 = v03_13 / v13_sq;
if(a1<0)a1=0 else if(a1>1)a1=1
a3 = 1 - a1;
} else {//edge between v1 and v2
a2 = ((x0 - x1)*x21 + (y0 - y1)*y21 + (z0 - z1)*z21)/(x21*x21 + x21*x21 + x21*x21);
if(a2<0)a2=0 else if(a2>1)a2=1
a1 = 1 - a2;
}
}
//solution found - now based on it calculate point and distance
rx = x1*a1 + x2*a2 + x3*a3;
ry = y1*a1 + y2*a2 + y3*a3;
rz = z1*a1 + z2*a2 + z3*a3;
dist = Math.pow(rx - x0, 2) + Math.pow(ry - y0, 2) + Math.pow(rz - z0, 2);
//if it is shorter than previous distance this point is considered best now
if (dist < distBest) {
distBest = dist
rxBest = rx; ryBest = ry; rzBest = rz;
faceBest = faceIndex + 1;//write here just for fun
}
}
//after all faces were checked - return best result
if (out != null) { out.x = rxBest; out.y = ryBest; out.z = rzBest; return out; }
return new Vector3D(rxBest, ryBest, rzBest);
}
