mesh size approximation about manifold

[pca006132]

yes, by the size of the mesh I actually want to mean the number of vertices :)

perhaps reading too much complexity theory stuff recently

[elalish]

I take it this is memory footprint, rather than dimensions?

[kintel]

Basically, the use-case is that we cache Manifold results to allow subsequent evaluations to run faster if the underlying code of any sub-tree didn't change, or for repeated equivalent code (like a geometry version of common subexpression elimination).
To avoid runaway memory usage, we need some way of limiting the cache size, which is also settable by users in the UI. For CGAL, we compute the byte size of the underlying geometry, as that's something understandable to users. Getting vertex count may be a reasonable start, and we can use some heuristics to estimate memory usage from that.

[elalish]

Why do you need an estimate? Why not just run that sub-tree and measure its size? Is this to support the render() command, or something more automatic?

[kintel]

This is run for every intermediate CSG result in our CSG tree, and I was under the impression that evaluating the Manifold tree would be too expensive to run that often.

Note: We run this often because CGAL is really slow. With Manifold, we could potentially limitecache insertion to operations taking more than some threshold computation time.

[elalish]

Well, it sounds like both OpenSCAD and Manifold have an internal CSG tree. If you're doing fancy caching with your tree, then it probably has more benefit than ours, in which case you might want to circumvent our CSG tree (by forcing execution via e.g. NumVert()) and rely solely on yours. Then you'll have complete control over when things get re-evaluated.

[pca006132]

For now, OpenSCAD is not having a more powerful CSG tree rewriting, so they probably don't want complete control over this (yet).

[kintel]

Perhaps we’re using Manifold in a slightly awkward way. I need to learn something about how Manifold actually works :)

[kintel]

OK, reading some code, it looks like, when performing an operation on Manifold objects (objects of the Manifold class), it really just builds a CSG tree from the underlying CsgNodes.
..meaning that when OpenSCAD does stuff like union() {objA(); objB();}, it calls manifoldObjectA.Boolean(manifoldObjectB), which is really cheap as it's just a tree operation (as opposed to CGAL Nef polyhedrons which would perform the union at this point).

This kind of makes the concept of caching Manifold operations moot. ..until we actually hit some expensive operation (like minkowski which will perform a Nef3 minkowski operation inline). Since we may not want to rely on which operations are expensive or not, perhaps caching should really be done based on observed resource usage, not on a per-node basis.

I'll go back and think about this for a bit. If any of my observations above are grossly inaccurate, I'd appreciate some guidance :)

[elalish]

Yeah, Manifold is very lazy about evaluation, and also does some interesting reordering of the CSG tree to help optimize. I didn't realize OpenSCAD did any fancy caching - I thought it was all user-driven with the render() command, which I quite liked. That ability to re-run only part of the CSG tree when changes are local is nice - Manifold has no way to know about that.

[pca006132]

This kind of makes the concept of caching Manifold operations moot. ..until we actually hit some expensive operation (like minkowski which will perform a Nef3 minkowski operation inline). Since we may not want to rely on which operations are expensive or not, perhaps caching should really be done based on observed resource usage, not on a per-node basis.

Probably not. The main issue is that you will not know the resource usage of the operation until you eventually evaluate it. If nothing forces the evaluation, everything will look unbelievably fast, which is one common issue when users try to benchmark manifold's performance.

Consider the following:

union() {
  expensive_thing();
  simple_thing();
}

If openscad does not cache the expensive_thing module, changes to the simple_thing module will require re-evaluating expensive_thing, which can be expensive as the name suggests... The issue is that if we don't have a size approximation, openscad cannot know if the geometry in expensive_thing is expensive, unless it forces evaluation for that module alone. If openscad caches expensive_thing, manifold will try to reuse the previous result for expensive_thing, and changes to simple_thing can utilize the cache.

[kintel]

Right, but in that case, shouldn’t we cache manifold::Mesh objects, rather than manifold::Manifold objects as we do today?
..or am I missing something else?

[elalish]

No, but if you want to actually cache a manifold, just make sure to call NumVerts on it. That forces evaluation. If you don't do that, then all you're caching is a promise of a CSG tree, but you probably already have that outside of manifold. Although I probably shouldn't have much confidence without getting familiar with your code.

[pca006132]

caching the promise without forcing evaluation is fine, we do take that into consideration and make sure that there will not be double evaluation.

[kintel]

Let me know if this discussion is better suited elsewhere.

Reading more code, I think I get it: When the Manifold class is evaluated into a concrete object (Manifold::GetCsgLeafNode(), it will eventually replace its root node pointer with a pointer to the new concrete geometry (CsgLeafNode), and as a result dereference its entire subtree. In order to achieve this, it will first recursively flatten the tree by collapsing each non-leaf node into a leaf node in a depth-first fashion (..potentially applying some optimizations along the way).

Once the subtree is dereferenced, it's lost - unless someone else decides to hang onto a shared_ptr to interesting subtrees.

..so what OpenSCAD needs to do in the expensive_thing() case above, would be to cache the shared_ptr<Manifold> to that subtree. Even if it's not evaluated at the time, we'll get Manifold's caching for free when it eventually evaluates, due to the recursive flattening done by Manifold. The memory cost at the time of caching will be practically zero, as we're only storing a pointer to a subtree which is also stored elsewhere. After evaluation, we become the only reference to this subtree, and the cost will be the size of the concrete CsgLeafNode.

[pca006132]

Yes, your understanding is correct.

[kintel]

Thanks for the confirmation! I guess we're back to square one in terms of this ticket: We don't have any way of estimating the size of a ManifoldNode until it's evaluated. We could proactively evaluate every node we create (bottom-up), but it sounds like we may then kill any optimizations done by manifold.

[elalish]

Considering the point is to make it faster to evaluate when someone changes their script, another approach would be to choose cache points based on usage or code shape (modules without many parameters, or where parameters haven't been changed much), rather than execution time. Otherwise, the simplest approximation is probably just sum the number of verts of all the ancestor meshes, but it'll be very approximate.

[pca006132]

I think what manifold can do now is just give them the sum of the number of verts. Any more advanced cache system should be implemented on openscad side and tailored to their usecases.

[pca006132]

@kintel is this still needed if we don't cache manifold geometries and just cache polysets?

[kintel]

Let's pause this request for now, until we have a better sense of how to manage such caching.