[LDCad] Concave collision detection

[K Johnson]

Mr. Melkert

Just for some background...

I am developing a LDraw game that uses JBrickable connection data to snap to location.

I have successfully implemented connector location data for the LDraw bricks and the parts connect at the locations I need. 

I am running into a problem where I would need to check for collisions between the meshes to see if the position is okay to place.

Obviously, the LDraw meshes are concave and I cannot find collision detection between two concave meshes.

For example:

This would be okay...

  Screen Shot 2020-04-18 at 6.19.44 PM.png (Size: 65.32 KB / Downloads: 63)

This wouldn't:

  Screen Shot 2020-04-18 at 6.20.12 PM.png (Size: 62.43 KB / Downloads: 65)

[Roland Melkert]

I am running into a problem where I would need to check for collisions between the meshes to see if the position is okay to place.

This needs what i like to call a multiple connection solver.

It's a feature I like to add to LDCad 2.0 but it's a very complicated one, and will need a lot of processing power. I think it's the main reason programs like LDD get very slow with larger models.

If you want to solve it by collision detection alone you would need to define simplified collision volumes for all parts which isn't a small task.

You might be able to (partly) generate it from the mesh data though.

[K Johnson]

This needs what i like to call a multiple connection solver.

It's a feature I like to add to LDCad 2.0 but it's a very complicated one, and will need a lot of processing power. I think it's the main reason programs like LDD get very slow with larger models.

If you want to solve it by collision detection alone you would need to define simplified collision volumes for all parts which isn't a small task.

You might be able to (partly) generate it from the mesh data though.

I was considering generating from mesh data, and I also considered ancompound convex pseudo-concave solution, but I think I'll just exclude the functionality for now, for I don't think it's a terribly common building technique (I could be wrong). 

I also wanted to ask you further about what you said on a different post regarding the license for commercial LDraw software.

I am planning on using the LDraw parts for a virtual reality building system, but I am unsure if this is a good idea because of the potential copywrite infringement on the LEGO Group. I want to decide early in the development process if I should use LDraw or model my own knockoff parts and possibly use the same part names for instruction manual/LDraw .ldr file export purposes. The library wouldn't be all-encompassing in either case, and I would make sure not to use any trademark material, but as far as I am aware the LEGO Group has failed in multiple lawsuits to secure intellectual ownership of most of their part designs (excluding some parts such as minifigs, Bionicle, etc.) after their patents expired. I was wondering what makes you so concerned, then, about monetizing LDCad if my facts are correct.

[Stefan Frenz]

by collision detection alone

I tried collision detection with the mesh triangles for LDInspector, and it's not too easy to have an appropriate tolerance band. If I just calculate intersections between triangles, it works in most cases, but as soon as rotating or not-rectangular-angles come into the game, the tolerance band has to be adjusted and some cases are "not solvable the easy way". Consider the attached example: two pieces with "round" shape, in green perfectly aligned and in orange rotated by 5° which produces three "false positive" intersections.
  Example.jpg (Size: 7.01 KB / Downloads: 37)

I also tried the quickhull algorithm. Maybe this would have been useful for checking multiple times, but as LDInspector checks all objects only once and not multiple times, it's not used anymore there.

[Roland Melkert]

I was wondering what makes you so concerned, then, about monetizing LDCad if my facts are correct.

LEGO group has a 'fair play' policy which basically means do what you want free time wise, but things get grey when you start monetizing.

I think the books Orion mentioned aren't a problem as they are still fair use and only need a disclaimer somewhere.

And on a more personal level I don't want to go the commercial side of things because that would imply more serious work while the LDCad project is pure hobby for me. I've got enough death lines etc in my daily work

[Roland Melkert]

I also tried the quickhull algorithm. Maybe this would have been useful for checking multiple times, but as LDInspector checks all objects only once and not multiple times, it's not used anymore there.

Doesn't a bigger margin of error solve that?

Or you could use the primitives to define cylinder shaped collision objects.

[Stefan Frenz]

Doesn't a bigger margin of error solve that? Or you could use the primitives to define cylinder shaped collision objects.

Yes, a bigger margin solves most of them, but it's a trade off between false-negative and false-positive. Redefining cylinder shape objects would solve many false-positives (as for studs), but not all (as for 30014 "Brick 1x2 with Arm"), and I don't have an idea to automatically detect shapes based on LDraw files. I assume this is the same reason to have LGEO objects in POVray and not using LDraw definitions there...

To me the collision detection in LDInspector is a reasonable compromise. I just wanted to express my thoughts about my considerations about collision detection in the hope that they would be useful for a game described by K Johnson...