retessellate performance improvement suggestion

[achirita]

retessellate is meant to group together coplanar polygons.

In it's current format, it goes through each polygon and checks if it belongs to an existing group. If it doesn't, it creates a new group with that polygon.

This approach performs best when there is a high number of coplanar polygons, because there's a low number of groups to check against. On the other hand if there's a low number of coplanar polygons it has an O(n^2) execution time, because we have tons of groups with only 1 polygon inside.

My assumption is that in most cases we end up with a low number of coplanar polygons and this function could be optimized using the following logic:

• Sort all polygons based on their plane's distance to the origin.
• Go through the sorted array and cluster together polygons with the same distance to origin within a certain threshold (i.e. 0.00000015). If the difference in distance is higher than that the polygons are not coplanar.
• Go through each cluster. If it only has one element we don't need to do anything more. If it has multiple elements we could use the existing logic to create groups of coplanar polygons.

As opposed to the existing implementation this one performs best when there's a low number of coplanar polygons.

I've tested this implementation with a few different geometries (around 15k polygons each) and noticed a 4-5x improvement in execution time.

One thing to note - although both implementations function the same, my version returns the polygons in a different order than the existing implementation. It doesn't seem to have any negative effect, but it will definitely affect some of the existing tests.

I would love to hear your thoughts on this.

[hrgdavor]

Nice to see ppl tackling some of the internals. I am all for improving perf. Looks like it will be hard to test compared to current alg.
Maybe if you could just in the tests mark polygons order, and try to restore after new retesselate to compare. Or some other aproach taht could validate with existing tests ?

[z3dev]

@achirita nice idea. i suspect that the new algorithm prevents unnecessary allocations, which is a major cause of performance issues.

first, i really hate reTesselateCoplanarPolygons(). the logic is difficult to understand, and worse yet NEW vertices are created sometimes, which means that the polygons can mutate.

second, i spent time to write mergeCoplanarPolygons(). it never injects points, or mutate polygons. it just combines polygons.

i think that your new algorithm could be combined with mergeCoplanarPolygons() to improve performance as well as improve the results of the booleans.

third, the final results need to be verified by the test suites. sometimes, complete verification of polygons need to be performed, but in general just validate() and measurementVolume() are enough. @platypii has improved the geom3.validate() function, and this should can be improved further if necessary. FYI, you can see the failing boolean tests by grepping for 'validate'.

i'd like to see V3 using some form of mergeCoplanarPolygons(). and if you submit changes for retessellate() then lets focus on V3.

[achirita]

Thanks for the suggestions. I just realized one thing: reTesselateCoplanarPolygons() is meant to be called with an array of coplanar polygons. In the current V2 implementation all non coplanar polygons get pushed in an 1 element array and reTesselateCoplanarPolygons() is called for each. We could avoid this and push all non coplanar polygons to destpolygons array, right?

[z3dev]

I think that reTesselateCoplanarPolygons() returns the original array if length < 2

Sure. Anything is possible... eliminating allocations of any kind is key.

[platypii]

I'd be very interested to see your changes to retessellate @achirita!

It's not hard to find cases where 85%+ of the time spent in boolean operations is actually in retessellate. Here's an example:

const jscad = require('@jscad/modeling')
const { cylinder } = jscad.primitives
const { union } = jscad.booleans

const main = () => {
  const segments = 200
  const c1 = cylinder({ radius: 5, segments })
  const c2 = cylinder({ height: 10, segments })
  const startTime = performance.now()
  const obj = union(c1, c2)
  console.log(`Union ${Math.floor(performance.now() - startTime)} ms, retesselated ${obj.isRetesselated}, polygons ${obj.polygons.length}`)
  return obj
}

module.exports = { main }

I wonder if I should backport the volume tests from #1197 to V2 branch. It's really nice for testing exactly these kinds of changes.

[achirita]

This is exactly why I started looking into it.

I was hoping I would do a PR yesterday, but I ran into some issues. My implementation sorts the polygons, so the result is in a different order.

This doesn't seem to be a problem for geom3, but it breaks for geom2. Internally boolean operations turn geom2 into geom3 and then back again. If the polygon order is wrong the resulting geom2 is also wrong.

[achirita]

I have created a new PR #1250