kzhsw
August 15, 2025, 8:28am
1
ShadowGenerator.Parse called scene.getMeshesById, which is O(n) in time, for each mesh id in parsedShadowGenerator.renderList, makes the loop O(m*n) in time, where n is the count of meshes in scene, m is the count of items in renderList.
* @param constr A function that builds a shadow generator or undefined to create an instance of the default shadow generator
* @returns The parsed shadow generator
*/
public static Parse(parsedShadowGenerator: any, scene: Scene, constr?: (mapSize: number, light: IShadowLight, camera: Nullable<Camera>) => ShadowGenerator): ShadowGenerator {
const light = <IShadowLight>scene.getLightById(parsedShadowGenerator.lightId);
const camera: Nullable<Camera> = parsedShadowGenerator.cameraId !== undefined ? scene.getCameraById(parsedShadowGenerator.cameraId) : null;
const shadowGenerator = constr ? constr(parsedShadowGenerator.mapSize, light, camera) : new ShadowGenerator(parsedShadowGenerator.mapSize, light, undefined, camera);
const shadowMap = shadowGenerator.getShadowMap();
for (let meshIndex = 0; meshIndex < parsedShadowGenerator.renderList.length; meshIndex++) {
const meshes = scene.getMeshesById(parsedShadowGenerator.renderList[meshIndex]);
for (const mesh of meshes) {
if (!shadowMap) {
continue;
}
if (!shadowMap.renderList) {
shadowMap.renderList = [];
}
shadowMap.renderList.push(mesh);
}
}
And profiler shows there is a perf bottleneck in call to getMeshesById
Use a set of id for efficient matching, should be O(m) in space, and O(n) in time.
diff --git a/packages/dev/core/src/Lights/Shadows/shadowGenerator.ts b/packages/dev/core/src/Lights/Shadows/shadowGenerator.ts
index 34eb5b4c65..7ad0124070 100644
--- a/packages/dev/core/src/Lights/Shadows/shadowGenerator.ts
+++ b/packages/dev/core/src/Lights/Shadows/shadowGenerator.ts
@@ -2155,16 +2155,17 @@ export class ShadowGenerator implements IShadowGenerator {
const shadowGenerator = constr ? constr(parsedShadowGenerator.mapSize, light, camera) : new ShadowGenerator(parsedShadowGenerator.mapSize, light, undefined, camera);
const shadowMap = shadowGenerator.getShadowMap();
- for (let meshIndex = 0; meshIndex < parsedShadowGenerator.renderList.length; meshIndex++) {
- const meshes = scene.getMeshesById(parsedShadowGenerator.renderList[meshIndex]);
+ if (parsedShadowGenerator.renderList.length && shadowMap) {
+ const renderSet = new Set<string>(parsedShadowGenerator.renderList);
+ let renderList = shadowMap.renderList;
+ if (!renderList) {
+ renderList = shadowMap.renderList = [];
+ }
+ const meshes = scene.meshes;
for (const mesh of meshes) {
- if (!shadowMap) {
- continue;
- }
- if (!shadowMap.renderList) {
- shadowMap.renderList = [];
+ if (renderSet.has(mesh.id)) {
+ renderList.push(mesh);
}
- shadowMap.renderList.push(mesh);
}
}
3 Likes
I’m game!
Thanks a lot btw for all these tidbits of optimization! This is great
kzhsw
August 16, 2025, 12:41am
3
And a PR here:
master ← kzhsw:patch-2
opened 12:41AM - 16 Aug 25 UTC
The `ShadowGenerator.Parse` method exhibited a performance bottleneck due to its… inefficient handling of the `renderList`. Previously, it iterated through the `parsedShadowGenerator.renderList` and for each mesh ID, it called `scene.getMeshesById`. This resulted in an O(m*n) time complexity, where 'n' is the total number of meshes in the scene and 'm' is the number of meshes in the `renderList`. Profiling indicated that `getMeshesById` was a significant performance drain.
This commit refactors the parsing logic to improve efficiency. Instead of repeatedly querying meshes by ID, it now creates a `Set` of mesh IDs from the `renderList` (O(m) time and space). It then iterates through all meshes in the scene once (O(n) time) and checks for membership in the `Set` using an O(1) average time complexity lookup. Any mesh whose ID is found in the set is added to the `shadowMap.renderList`.
This change reduces the overall time complexity of parsing the `renderList` to O(n + m), which is a substantial performance improvement, especially for scenes with a large number of meshes or a large `renderList`.
Forum post: <https://forum.babylonjs.com/t/optimize-performance-of-shadowgenerator-parse/60086>
And seems something wrong with CI, without detailed error again
@ryantrem and @AlitarSemiramis can you check if we could display the error somehow ?
Can you run npm run format:fix ?
Not sure how but you did the same:
fixed in your PR
1 Like
kzhsw
August 25, 2025, 3:38am
7
Oh, never noticed that, my local copy works fine, but after pasting to github “Edit”, it added a new line. Thank you for that.
1 Like
Thank YOU for your appreciated help!
nw I feel like I helped lol
