Collision detection

[dbc]

Is there a way to do collision detection between two csg objects without having to do an intersection and looking for an empty result?

My application for pyPolyCSG is simulation of CNC G-code for milling. The bug reported in issue #6 illustrates the basic idea.

1. Start with a csg constructed box or an imported mesh that represents stock to be cut
2. Create a csg shape that models a tool. My intention is to model the tool in two pieces, the 'cutter' and the 'arbor'.
3. Model 'fixture' with further csg objects.
4. Simulate milling by moving the tool through the toolpath, subtracting the cutter from the stock at each iteration.
5. Detect and report collisions of cutter/fixture, arbor/stock, arbor/fixture.

So in my application, collision detection happens at each iteration step along the tool path. It doesn't need full csg, so I suspect the simulation would run a lot faster if it could to collision detection without having to perform csg.

[jamesgregson]

There's nothing in there to handle this. Collision detection (CD) is often done with separate (highly optimized) code such as RAPID or OPCODE. There may be bindings for these that would allow for efficient collision detection, but CD is a research topic in itself.

Incidentally, I am also ultimately targeting CAD/CAM/CNC. That's actually how the pyPolyCSG project arose, although this library is more geared towards parametric modeling than to toolpath operations.

As I understand it, most CNC packages use a voxel representation (i.e. a regular 3D grid) for the workpiece/fixtures and a primitive representation for the cutter. This allows for a relatively limited set of intersection primitives (e.g. cylinder-grid, sphere-grid) for interference testing that can be reused for performing the CSG operations. The downside is that accuracy suffers: sharp edges are smoothed and the grid-size determines the smallest resolvable feature.

You could probably also take a pyPolyCSG mesh and make a spatial-partitioning structure in Python that would allow you to look up triangles that intersect a bounding-box or sphere, but again this isn't handled in the library as-is. This is probably best done in C++ and would be quite useful, but I doubt I'd get around to it before the new year as I have paper deadlines before then.

[dbc]

For collision detection, I would think you could do a CSG intersection and test for a non-empty result mesh. It seems like that should work fine, but also seems like it could be pretty expensive. Unless there is something in Carve that quickly short-circuits intersection of two non-intersecting meshes?

I was trying to avoid having to write a lot of 3D code just for a toolpath simulation, so I didn't want to take on writing a voxel muncher. CSG is more general anyway. Although I admit my use case is somewhat abusive of a general CSG package. My goal is a 2.5D CAM package that accepts .dxf as input, and outputs g-code.

[jamesgregson]

Sorry for the delay, I didn't seem to get an email about your reply.

I think you will have a difficult time getting a CSG library to work the way you've described. They seems to fall apart with coincident/degenerate geometry, which your use-case will generate lots of. Some libraries are better than others, e.g. CGAL seems to beat Carve for robustness, but I've yet to find one that hasn't crashed with valid (but hard) inputs. Since pyPolyCSG just wraps Carve, it can't really make the CSG libraries any more robust.

You may want to check out Slic3r (slicer.org). It's an open source 2.5D GCode generator for 3D printers like Makerbots, written in Python. It probably won't be exactly what you're looking for, but the source might give you some ideas for your project.