Possible performance issues for model picking #11814
Description
While having a short look at the reasons for #11811 , I think that most of the time is spent in the model picking functionality. While some of this may be necessary for the new functionality and behavior of the Screen Space Camera Controller, it led me into a the rabbit hole that is the pickModel.js function.
There are, from a quick glance, at least two things that might be costly in terms of performance.
1. Re-creating the indices
When a given primitive does not have its indices stored in a typedArray, then this array is array is re-created and re-filled (from the buffer) here:
There are some unknowns for me. Some of that is related to WebGL1 vs. 2, and whether outlines or wireframes are enabled. Eventually, it might boil down to a trade-off between "memory requirements" and "performance". But this part may have to reviewed with some scrutiny.
2. Transforming the vertices, again and again...
The part that is the most expensive one is the one where vertices are fetched for each triangle, and the triangle is tested for intersections with the ray, at
Focussing on the approach with some pseudocode:
for (let i = 0; i < indicesLength; i += 3) {
const i0 = indices[i];
const i1 = indices[i + 1];
const i2 = indices[i + 2];
for (const instanceTransform of transforms) {
const v0 = getVertexPosition(..., instanceTransform, ...);
const v1 = getVertexPosition(..., instanceTransform, ...);
const v2 = getVertexPosition(..., instanceTransform, ...);
const t = IntersectionTests.rayTriangleParametric(ray, v0, v1, v2);
if (defined(t)) {
if (t < minT && t >= 0.0) {
minT = t;
}
}
}
}Verbally:
- For each triangle:
- Fetch the vertices
- Transform the vertices with the
instanceTransform(done ingetVertexPosition) - Check the transformed triangle for intersections with the ray
I think that it should be possible to write this in a different form:
// Store rays that are transformed with the inverse of the instance transform
const transformedRays = [];
for (const instanceTransform of transforms) {
const invTransform = Matrix4.inverse(instanceTransform, new Matrix4());
transformedRays.push(transformWith(ray, invTransform));
}
const indicesLength = indices.length;
for (let i = 0; i < indicesLength; i += 3) {
const i0 = indices[i];
const i1 = indices[i + 1];
const i2 = indices[i + 2];
// Do not transform the vertices
const v0 = getVertexPosition(...);
const v1 = getVertexPosition(...);
const v2 = getVertexPosition(...);
// But test them for intersections with the transformed ray
for (let r=0; r<transformedRays.length; r++) {
const transformedRay = transformedRays[r];
const t = IntersectionTests.rayTriangleParametric(transformedRay, v0, v1, v2);
if (defined(t)) {
if (t < minT && t >= 0.0) {
minT = t;
}
}
}
}- For each triangle:
- Fetch the vertices
- For each transformed ray:
- Check the triangle for intersection with the transformed ray
Mathematically (and from a quick test), I think that this might work and bring a noticable speedup, with further potential for optimizations, but also some care to make sure that things like the exaggeration can be taken into account properly.
The reason why I'm not just opening a PR with a suggestion is ... that there are currently far to many swear words in my local state, after I spent about 3 hours trying to set up a spec that intersects a ray with a unit sphere at the origin. Yes, this should be a no-brainer. But I failed miserably. So.... if someone could set up a test, at the end of pickModelSpec.js, that has the following form...
fit("picks, ANYTHING...", async function () {
const url = "./Data/Models/glTF-2.0/Spheres/sphere_V37500.glb";
const model = await loadAndZoomToModelAsync(
{
url: url,
enablePick: !scene.frameState.context.webgl2,
},
scene
);
const ray = new Ray();
ray.origin = new Cartesian3(0.0, 0.0, 10.0);
ray.direction = new Cartesian3(0, 0, -1);
const actual = pickModel(model, ray, scene.frameState);
const expected = new Cartesian3(0.0, 0.0, 0.0);
expect(actual).toEqualEpsilon(
expected,
CesiumMath.EPSILON12
);
});
and that actually picks anything, then I'd have another look. (And if someone would also like to summarize the coordinate transforms that are going on there under the hood and that make this so hard, this would be great).
Here is a ZIP with a glTF that is just a sphere with 37k vertices that I'd like to use for this test: