Quantizing vertices?

[io7m]

Hello.

One issue with CSG as opposed to voxel-based geometry is that there's essentially no upper bound on the complexity of the geometry that can be created. For example, if you create a sphere and then subtract hundreds of tiny spheres from the surface of it, the result will be a very large number of polygons.

One way to get around this is to provide an optional quantization value that causes vertex coordinates to be snapped to the nearest multiple of the value. For example, specifying a quantization value of 1.0 would cause all created vertices to snap to integer coordinates. A value of 0.01 would snap vertex coordinates to the nearest 0.01 and so on. If coincident vertices are eliminated after snapping, this has the effect of putting an effective upper bound on the complexity of the geometry that can be created (at the obvious cost of making the system less able to express nice smooth geometry with high quantization values).

In real-time simulations where users can modify geometry in real-time, having that upper bound can be very important to keep performance to an acceptable level.

How much work do you think would be involved in adding this (optional, opt-in) feature to JCSG?

[madhephaestus]

This is a fantastic idea! My branch if for more experimental features that may break compatibility
https://github.com/NeuronRobotics/JCSG

I would be very interested in exploring this concept. I am using JCSG to build large complex assemblies that are simulated with a physics engine. Reducing the vertex count is of strong interest to me.

[miho]

Hi there,

in general I like the idea. For a stable solution there are several things to consider though:

• what about feature preservation? most users of this library love the fact that we preserve (almost)
  all features

• quantization can introduce unresolved intersections which need to be treated separately

• ...

These are just a few of the potential problems. But I don't want to discourage you from trying this. And you are welcome to contribute to JSCG.

IMPORTANT: if you want to contribute to this library, keep the PR's small and focused on one feature per PR. Otherwise it's rather unlikely that I will merge them since it takes too much time to review these PRs.

[miho]

For producing nicer meshes there's also an extension library. It's not well suited for real-time purposes but it is very good at producing high-quality meshes:

https://github.com/miho/JCSG-MeshExtensions

[Octogonapus]

I just played around with this for a bit here: https://gist.github.com/Octogonapus/221961cef019143deaf025f6611497a0

In the script you can see I make a cube-like CSG with dense geometry. After quantization and polygon deduplication, there was a decent reduction in the detail (8018 polygons down to 826 polygons with 0.1 quantization value). I haven't tested this script much but it might be useful on a case-by-case basis where you have a detailed object you want to simplify some.

I don't think a blanket approach like this belongs in JCSG. As Miho pointed out, people like that JCSG preserves features and this blanket approach does not do that. That said, I still think it shows some promise (at least for us at CommonWealthRobotics).

[miho]

Thanks for sharing this script! I will test it with...

[miho]

Oh, I just noticed you do a very dangerous floating point comparison which is likely to fail in non trivial cases (see L64). Always work with a tolerance (TOL, DELTA, EPSILON, ...) for floating point equality.

BTW: Vector3d implements equals() already.

[io7m]

I don't think a blanket approach like this belongs in JCSG. As Miho pointed out, people like that JCSG preserves features and this blanket approach does not do that. That said, I still think it shows some promise (at least for us at CommonWealthRobotics).

This is why I said the feature should be entirely opt-in. If you don't ask for it, you don't get it. If you want feature preservation in preference to very low density meshes, the available tools are already good enough. My requirement is that I don't create a massive number of intermediate polygons and vertices which then have to be simplified and removed, because I need strict bounds on memory usage. Creating 8018 polygons and then simplifying down to 826 isn't good enough in my case, because that obviously means that at some point during the algorithm, I was holding 8018 polygons in memory (and this number can obviously grow in an unbounded fashion as complexity increases).

I still haven't had a chance to work on this myself yet (I've been flooded with other work), but is it possible that JCSG could be extended to expose some sort of API that would let me quantize vertices and deduplicate vertices myself before JCSG turns them into polygons?

[miho]

In principle, yes. This is indeed possible. But it involves some work since most parts of JCSG don't make special assumptions about whether a vertex and/or polygon should be created. That's why it is relatively stable. We'd definitely have to discuss and carefully design an API that would allow such an extension before you or somebody else starts working on it. This is important to ensure that we can merge these changes hassle-free.

We are currently discussing an extended CSG approach that would allow us to delegate tasks to different CSG implementations. @sreiter and I already have plans about this.

[madhephaestus]

@miho and @sreiter I would like to be added to those discussions in order to mainline some of my features from: https://github.com/NeuronRobotics/JCSG I have added a lot of basic operations and primitives that would be useful to everyone. See this for a feature list: http://commonwealthrobotics.com/JavaCAD/Overview/http://commonwealthrobotics.com/JavaCAD/Overview/

Let me add a bit to the example code to the direct discussion here: https://github.com/madhephaestus/BowlerSlicer/blob/master/AnyliticalSolution.groovy

This is a script that quantizes vertexes, analyzes the remaining edges for degenerate edges (partial coincident and crossing lines), splitting them when it finds them. Then it stitches the edges back together as polygons, triangulates them, then prunes interior edges for mathematically pure boundary polygon generation. It is a compute HOG and i stopped work on it because it took so much compute. I am attempting to make a fast slicer for CSG objects, so this method was too complexity bounded to work for my needs.

NOTE the script uses some BowlerStudio API's to display the polygons for analysis of the algorithm

[Octogonapus]

@miho I know I use == for floating point comparisons, I cheated here because I was writing a quick proof of concept ;)

Anyway, I don't think vertex quantization is the way to go. I think we should go with something more like quadric mesh simplification, which will perform far better for sparse meshes and might preserve more features.

[miho]

@madhephaestus We are currently working on a resolution independent CSG API which is able to work on BREP as an alternative to tessellated geometries. The Java API is not done yet. But you can test an early version via a simple command-line application which already supports STEP/BREP files: https://github.com/miho/OCC-CSG