LDCad script integration of LDInspector's collision detection

[Stefan Frenz]

Hi all,

inspired and motivated by this thread, I tried to port the collision detection algorithm of LDInspector to LDCad / Lua. Thanks to Roland and his massive support I have a first version running that seems to not crash immediately.

In the attached example TestMini there are three collisions:
   

Running the collision detection coloring macro, it marks all colliding parts correctly:
   

Having some parts in sub-models like in TextMiniSub, the macro marks the parts in the sub-models recursively which may lead to spurious false-collisions. I'm working on some kind of work-around by (a) adding collision indicators instead of coloring the parts or (b) creating a new flat file which then allows individual coloring of parts.
   

If you are interested in the still-very-beta-proof-of-concept-script, it is attached as txt file - just rename to lua and copy it do LDCad-1-7-Alpha-2/scripts/default/global/ directory. You will need LDCad 1.7 Alpha 2 or later - thanks again to Roland for providing all needed functions. Please do not run the collision detection with too many parts as the time will increase squared to the number of parts. Running this small example with 15 parts already requires 32ms on may machine and the default maximum macro runtime is 250 ms which leads to a maximum of about 40 parts without prolonging the macro execution time.

[Roland Melkert]

Very cool.

What kind of crashes do you mean though, as lua scripts shouldn't be able to crash LDCad in any way.

Some optimizations for you to consider:
- use bounding sphere tests
- avoid wrapper functions like your vsub and vcross etc, while being more readable it will cause more work for the scripting engine.
- use relative data (transform the test intersection line instead of the mesh data), this will avoid having to transform all mesh data and you only need to store information for unique meshes.

Some api extensions that might be useful:
- query mesh bounding information (this is known data inside LDCad and contains all min/max coords you are gathering I think).
- line intersects mesh test function (there is tons of intersection test code inside LDCad, these will also do a sphere/box test before looping all poly's)

[Stefan Frenz]

Thanks for looking at it and thank you for your feedback. 

What kind of crashes do you mean though, as lua scripts shouldn't be able to crash LDCad in any way.

Oh, not LDCad crashes, only my script crashes. I'm used to typed programming in Java, and I made tons of really basic mistakes which are impossible in Java at runtime... Even a typo like "[string "colldet.lua"]:547: attempt to call a nil value (field 'sessio')", which feels like a crash to me after starting the script.  

Some optimizations for you to consider:

Thanks again. There are some other things on the todo-list for optimization, I will add your points. Your point "use relative data" I have to think about... Wouldn't this require doing much more matrix multiplications if the bounding boxed intersect often?

Some api extensions that might be useful:

Hmmmmm. This would be really useful. If the intersection tests were native LDCad functions, I would assume that they are a lot faster. And, hum, if the intersection tests are all there, there is not much left to do in Lua for the collision detection...   So how about integrating this completely?

There was this idea of N.W.Perry which is still on my todo-list. So if the code would migrate into native LDCad for speed reasons, it would be useful to have Lua functions gathering collision information about colliding parts.

[Jaco van der Molen]

Interesting.

If this would be native to LDCad, I asume one can overrule it and still make it possible to have collisions.
Ever so often it turns out one can build for real without colliding, but digitally a collision is not always unavoidable.

[Jaco van der Molen]

Hi all,

inspired and motivated by this thread, I tried to port the collision detection algorithm of LDInspector to LDCad / Lua. Thanks to Roland and his massive support I have a first version running that seems to not crash immediately.

In the attached example TestMini there are three collisions:


Running the collision detection coloring macro, it marks all colliding parts correctly:


Having some parts in sub-models like in TextMiniSub, the macro marks the parts in the sub-models recursively which may lead to spurious false-collisions. I'm working on some kind of work-around by (a) adding collision indicators instead of coloring the parts or (b) creating a new flat file which then allows individual coloring of parts.


If you are interested in the still-very-beta-proof-of-concept-script, it is attached as txt file - just rename to lua and copy it do LDCad-1-7-Alpha-2/scripts/default/global/ directory. You will need LDCad 1.7 Alpha 2 or later - thanks again to Roland for providing all needed functions. Please do not run the collision detection with too many parts as the time will increase squared to the number of parts. Running this small example with 15 parts already requires 32ms on may machine and the default maximum macro runtime is 250 ms which leads to a maximum of about 40 parts without prolonging the macro execution time.

I will try this...

[N. W. Perry]

Would this algorithm apply any transformation (i.e., scale factor) applied to the parts by their matrix, before calculating the collisions?

[Stefan Frenz]

Would this algorithm apply any transformation (i.e., scale factor) applied to the parts by their matrix, before calculating the collisions?

As far as I know: yes.   If you have an example file with known/expected result, I would like to test it.

[Stefan Frenz]

Interesting.

If this would be native to LDCad, I asume one can overrule it and still make it possible to have collisions.
Ever so often it turns out one can build for real without colliding, but digitally a collision is not always unavoidable.

The collision checks are very time intense. Even if it would be native, I would assume that they are not "always on" but rather "check these selected parts now" with some coffee break.

[N. W. Perry]

As far as I know: yes.   If you have an example file with known/expected result, I would like to test it.

Here's a simple use case from set 950. In this stack of seven bricks, four of them have been scaled down to be ~23 LDU tall. There should be no collisions reported if the scale factor is taken into account.

[Stefan Frenz]

Thanks for the example. All collision detections (LDCad-integrated, LDInspector command line, LDInspector gui) show 0 collisions as desired.

[N. W. Perry]

Thanks for the example. All collision detections (LDCad-integrated, LDInspector command line, LDInspector gui) show 0 collisions as desired.

Cool.  

If you want some more complicated ones to try, here are a couple of supercars that I know have some scaled parts:

  853 Auto Chassis.ldr (Size: 45.53 KB / Downloads: 2)
  8865 Test Car.ldr (Size: 1.76 MB / Downloads: 2)
  8880 Super Car.ldr (Size: 2.63 MB / Downloads: 2)

[Stefan Frenz]

Thanks - all three show collisions in LDInspector, the LDCad-integrated implementation (naturally) is much slower and for 8865 has an output indicating something different (assumably wrong). I will have a closer look.

[Roland Melkert]

The collision checks are very time intense. Even if it would be native, I would assume that they are not "always on" but rather "check these selected parts now" with some coffee break.

I have been thinking about a native collision detection feature, but I'm not sure how to put it into the existing GUI.

[Orion Pobursky]

I have been thinking about a native collision detection feature, but I'm not sure how to put it into the existing GUI.

I'd just have a toggle option like for snap data. Outline collisions in orange or something.

[Stefan Frenz]

I have been thinking about a native collision detection feature

This would be great! I would really love this feature to be integrated in LDCad!

but I'm not sure how to put it into the existing GUI.

About the modes: Maybe there could be another mode (like normal/animation) or in normal mode there could be an explicit list containing all collisions. Marking them could show an optical feedback of the selected parts like selecting a part in the source list. Thinking of N.W.Perry's interest in intended collisions, the normal mode with the option to move parts would also allow integration of the discussed functions "move/rotate in given direction while not colliding".

About the results: I have played around with different visualizations for my GUIs: outlining, solid coloring (one color for collisions, another one for non-colliding parts), color-changing (color changes per collision-group) and collision-only-remaining (not involved parts become invisible). Depending on the model, each has its advantages.

If there is anything I can do to help getting this feature into LDCad, please let me know.

[Stefan Frenz]

If you want some more complicated ones to try, here are a couple of supercars that I know have some scaled parts:

...still testing your version of 8865 but having rounding trouble in the LDCad-integrated version, working fine in LDInspector. This will take some more time, sorry...

[Stefan Frenz]

one step further: some of the collisions my collision detection reports are "really existing" in LDraw but do not exist in real world, like this collision of an axle with a technic brick shown by LDInspector:

  01_CollidingParts_LDInspector.gif (Size: 41.62 KB / Downloads: 64)

Zooming very close in LDCad gives this (with some markers done in  GIMP):

  02_CollidingDetails_LDCad_Marked.gif (Size: 10.16 KB / Downloads: 63)

So this is not a collision to avoid but is reported correctly by LDInspector. Those kind of collisions have to be checked manually, maybe even marked afterwards as "this is ok". I would suggest some internal line type like "0 !LDxx IGNORECOLLISION [whatever]" with [whatever] indicating the checked part. How this "whatever" should look like, I have some ideas but no final proposal.

Unfortunately, the above shown collision is not reported by my current version of the collision detection in LDCad but only shown by LDInspector - I'm still searching for the reason.  Bugs are found, see updated version of the script.

[Stefan Frenz]

Attached is a new version 0.2 of the LDInspector-Java-to-LDCad-Lua-port of the collision detection. It has at least three bugs less (thank you N.W.Perry for your example files) and should be a bit faster (thank you Roland for the hints).

[Stefan Frenz]

Thank you for your examples, now there are at least three bugs less in the Lua-port.   
The results seem to be mathematically correct, but I'm not sure if they are what is wanted. Setting tolerance to 0.0001, the 8865 model is marked like this:

   

Increasing the tolerance to 0.1 much less is marked:

   

As LDraw is by design somewhat angular (see my yesterday's post #17), setting the tolerance is a trade-off between false-positive and false-negative. I thought about calculating a ratio "overlapping" vs. "non-overlapping" volume, but this would (a) be hard to implement and (b) would not solve the underlying problem.