perf(modeling): O(n²) array concatenation in scissionGeom3.js

[jbroll]

Summary

scissionGeom3.js uses Array.concat() inside nested loops, causing O(n²) memory operations.

Usage Frequency: LOW

Used only by scission() operation which splits a geometry into disconnected pieces. Most typical models don't use scission - it's a specialized operation for:

• Separating imported models that contain multiple parts
• Post-processing boolean results that created separate islands

Typical model usage: Rare - maybe 1% of models

Problem

File: packages/modeling/src/operations/booleans/scissionGeom3.js
Lines: 40-42

const indexesPerPolygon = polygons.map((polygon) => {
  let indexes = []
  polygon.vertices.forEach((point) => {
    indexes = indexes.concat(findMapping(indexesPerPoint, vec3.snap(temp, point, eps)))
  })
  return { e: 1, d: sortNb(indexes) }
})

For each vertex of each polygon, concat() creates a new array. With N polygons averaging V vertices, this is O(N*V) array allocations.

Suggested Fix

Use push() with spread:

const indexesPerPolygon = polygons.map((polygon) => {
  const indexes = []
  polygon.vertices.forEach((point) => {
    indexes.push(...findMapping(indexesPerPoint, vec3.snap(temp, point, eps)))
  })
  return { e: 1, d: sortNb(indexes) }
})

Impact

Low overall (rare operation), but when used on complex geometry it can be slow.

[hrgdavor]

Spread operator is dangerous to use in places where array could be large . This limit varies by browser and environment but often falls between 65,536 and 500,000 elements.

[jbroll]

Good point @hrgdavor! The spread operator does have stack limits (typically 65k-500k elements depending on environment).

For this particular case in scissionGeom3.js, findMapping() returns a small array (polygon indices sharing a vertex - typically 3-6 elements), so spread should be safe here. But you're right that a more defensive approach would be:

const indexes = []
polygon.vertices.forEach((point) => {
  const found = findMapping(indexesPerPoint, vec3.snap(temp, point, eps))
  for (let i = 0; i < found.length; i++) {
    indexes.push(found[i])
  }
})

Or use Array.prototype.push.apply() which has the same limit but makes the intent clearer:

indexes.push.apply(indexes, found)

For cases where the source array could be large (like in extrudeFromSlices.js issue #1419), a simple for-loop is definitely safer:

const walls = extrudeWalls(prevSlice, currentSlice)
for (let i = 0; i < walls.length; i++) {
  polygons.push(walls[i])
}

Thanks for the review!

[hrgdavor]

np, that is one particular issue I bumped into a while ago. So yes, here spread is just fine. I was not aware of number of expected elements in this particular case, thanks for clarification.