LDCad script integration of LDInspector's collision detection


LDCad script integration of LDInspector's collision detection
#1
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. Wink

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. Smile 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.


Attached Files
.ldr   TestMiniSub.ldr (Size: 686 bytes / Downloads: 4)
.ldr   TestMini.ldr (Size: 883 bytes / Downloads: 5)
.txt   colldet.txt (Size: 16.89 KB / Downloads: 11)
Reply
RE: LDCad script integration of LDInspector's collision detection
#2
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)
Reply
RE: LDCad script integration of LDInspector's collision detection
#3
Thanks for looking at it and thank you for your feedback.  Smile

(2022-07-09, 20:18)Roland Melkert Wrote: 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. Wink 

(2022-07-09, 20:18)Roland Melkert Wrote: 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?

(2022-07-09, 20:18)Roland Melkert Wrote: 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... Wink  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. Wink
Reply
RE: LDCad script integration of LDInspector's collision detection
#4
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
lpub.binarybricks.nl
Reply
RE: LDCad script integration of LDInspector's collision detection
#5
(2022-07-09, 7:33)Stefan Frenz Wrote: 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. Wink

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. Smile 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...
Jaco van der Molen
lpub.binarybricks.nl
Reply
RE: LDCad script integration of LDInspector's collision detection
#6
Would this algorithm apply any transformation (i.e., scale factor) applied to the parts by their matrix, before calculating the collisions?
Reply
RE: LDCad script integration of LDInspector's collision detection
#7
(2022-08-31, 14:38)N. W. Perry Wrote: 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. Smile  If you have an example file with known/expected result, I would like to test it.
Reply
RE: LDCad script integration of LDInspector's collision detection
#8
(2022-08-31, 13:15)Jaco van der Molen Wrote: 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. Wink
Reply
RE: LDCad script integration of LDInspector's collision detection
#9
(2022-08-31, 17:06)Stefan Frenz Wrote: As far as I know: yes. Smile  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.


Attached Files
.ldr   test.ldr (Size: 407 bytes / Downloads: 2)
Reply
RE: LDCad script integration of LDInspector's collision detection
#10
Thanks for the example. All collision detections (LDCad-integrated, LDInspector command line, LDInspector gui) show 0 collisions as desired. Smile
Reply
RE: LDCad script integration of LDInspector's collision detection
#11
(2022-08-31, 22:13)Stefan Frenz Wrote: Thanks for the example. All collision detections (LDCad-integrated, LDInspector command line, LDInspector gui) show 0 collisions as desired. Smile

Cool. Cool 

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

.ldr   853 Auto Chassis.ldr (Size: 45.53 KB / Downloads: 2)
.ldr   8865 Test Car.ldr (Size: 1.76 MB / Downloads: 2)
.ldr   8880 Super Car.ldr (Size: 2.63 MB / Downloads: 2)
Reply
RE: LDCad script integration of LDInspector's collision detection
#12
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.
Reply
RE: LDCad script integration of LDInspector's collision detection
#13
(2022-08-31, 17:08)Stefan Frenz Wrote: 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. Wink

I have been thinking about a native collision detection feature, but I'm not sure how to put it into the existing GUI.
Reply
RE: LDCad script integration of LDInspector's collision detection
#14
(2022-09-01, 17:30)Roland Melkert Wrote: 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.
Reply
RE: LDCad script integration of LDInspector's collision detection
#15
(2022-09-01, 17:30)Roland Melkert Wrote: I have been thinking about a native collision detection feature
This would be great! Smile I would really love this feature to be integrated in LDCad! Smile

(2022-09-01, 17:30)Roland Melkert Wrote: 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. Smile
Reply
RE: LDCad script integration of LDInspector's collision detection
#16
(2022-08-31, 23:18)N. W. Perry Wrote: 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. Huh This will take some more time, sorry...
Reply
RE: LDCad script integration of LDInspector's collision detection
#17
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:

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

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

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

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.
Reply
new version: LDCad script integration of LDInspector's collision detection
#18
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).


Attached Files
.txt   colldet.txt (Size: 19.5 KB / Downloads: 9)
Reply
RE: LDCad script integration of LDInspector's collision detection
#19
Thank you for your examples, now there are at least three bugs less in the Lua-port.  Big Grin 
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.
Reply
« Next Oldest | Next Newest »



Forum Jump:


Users browsing this thread: 1 Guest(s)