Experimental part snapping in LDCad 1.3

[Roland Melkert]

Hello all,

I've been working on part snapping for my LDCad editor. It's progressing nicely but I would love some feedback / opinions from people in order to fine tune things.

The current version works quite nicely with low connection point parts. The problem arises when you use parts with multiple valid snap points (e.g. the holes in 1xn tech beams). Currently it snaps based on z sorting, but there is room for improvement there.

I've uploaded short clip of the feature in action.

The used scene contains most of the parts with full snap information. Snapping is done 100% trough meta information on the existing part files. This is done using a shadow library, which acts like an auto include location. Content of identical named files in the shadow location are added to the official ones from the LDraw lib during loading. Information can also be inherited as a result all minifig torso/leg/hip/hand/arm parts have information by just creating 6 shadow files.

edit: second version, see below post.

Second version demo clip


All suggestions are welcome

[Michael Horvath]

Could you make it an optional feature? These calculations would bring LDCad to its knees when trying to load Datsville. I never was able to get Datsville to load successfully in SR 3D Builder for instance.

Also, it's too bad there is no official library of connection data. That way software makers could pool their efforts.

[Roland Melkert]

It's already an option, it will even be disabled by default.

My goal is/was never to go full snapping. I'm seeing it more as an aid for placing the awkward parts.

[Steffen]

> Also, it's too bad there is no official library of connection data

in the hinterlands of our minds there is the idea of adding this information to the library itself,
the same way as currently just the geometry.

in a way, it already is contained there implicitly, for example, stud.dat not only means
that there is something LOOKING like a stud but also SNAPPING like a stud.
and so on.

the only question is how to put this info into the library.

I strongly favor _not_ putting this into a special "connection table" as a separate file,
but instead use a per-part, i.e., de-central approach.

the connectivity information would be reviewed the same way as currently the geometry of a part.

to me, the ideal way to model that would simply be using primitives for that:

we already have stud.dat.
we can invent a new primitive which carries the meaning "fits onto a stud".

it will contain no visible geometry at all, just carry the information where a stud could snap.

a part file would place this wherever needed, for example, a 2x4 brick will have
2x4 usages of this suggested primitive on its underside.
we could even create stugs of it ,
so filesize is not really an issue.
and renderers would not be affected, as these files would not bring in _visible_ geometry.

however, for debugging/visualization purposes, they could.
a user then could _see_ where the snapping places are.

the same mechanism could be used not only for stud.dat, but also for others.
example: c-clip. it can snap for example on a long cylinder. so if a part has such a region,
it would place a "c clip snapper" primitive there, scaled properly to fully extend over the cylinder's length.

software then easily can detect that there a c-clip can snap.

the only information we need to store somewhere is which
2 primitive pairs match for snapping, e.g.
stud.dat snaps to snap-stud.dat.
c-clip.dat snaps to snap-c-clip.dat.
axle.dat snaps to axlehol.dat.
and so on.

i feel that our library is already very near to this. its logic and structure already BEG for a feature like this.



EDIT: I just found the old thread discussing ideas like this: http://forums.ldraw.org/showthread.php?t...97#pid8797

[Max Martin Richter]

Maybe we can use the connection information as Sergio did in his awesome SR3D-Builder.

We could use a meta command and add these connectivity information where it belongs to, so that we don't need extra files...


/Max

[Philippe Hurbain]

Maybe we can use the connection information as Sergio did in his awesome SR3D-Builder.

I totally agree! hopefully he should get an unification of connectivity information - and clearly Sergio does have the lead here... (*)

We could use a meta command and add these connectivity information where it belongs to, so that we don't need extra files...

...but here I dont agree that much. I think that keeping connectivity outside main files has much more chances to happen than making a major overhaul of the library - afterall it already happened! Lets be pragmatic...

(*edit... but there is room for improvement. Eg. there is no automatic orientation of axles placed into axleholes.

[Philippe Hurbain]

Results look pretty good already! I guess that you didn't yet address the rotation of parts around connexions?

[Roland Melkert]

Not yet but most parts have a logical center, so setting the grid to the parts orientation make rotating e.g. a minifig's arm relatively easy after the initial placement.

[Roland Melkert]

Also the needed information can differ a lot depending on what you want to do with it. In my approach I've choosen to describe shapes instead of connection types. So the software doesn't know anything about studs/pegs etc, it's only matching shapes against other shapes.

For example this is info I'm using for the 5.5 axle.

0 !LDCAD SNAP_CYL [gender=M] [caps=none] [secs=A 6 18 R 8 2 R 6 8 A 6 80] [center=true] [pos=-1 0 0] [ori=0 -1 0 1 0 0 0 0 1] [slide=true]

The engine will test this against other shapes, and if it fits it will snap to it along it's y axis. The above will go (partly) into a peghole because it's shape is simular (they share a radius 6 section, and the other sections are larger):

0 !LDCAD SNAP_CYL [gender=F] [caps=none] [secs=R 8 2 R 6 16 R 8 2] [center=true] [slide=true] [pos=0 0 0] [ori=1 0 0 0 1 0 0 0 1]


I've tried using as many primitive's possible for defining the info but I'm somewhat disappointed on that subject. It seems many primitives are 'misused' somewhat degrading their snap information on the higher level. For example the axle.dat primitive seems to be used for internals alot (Isn't is mend to be used open ended only?). Also some primitives are used mirrored (messing up orientation) although I managed to compensate for that somewhat. And finally there are a lot of parts that don't use primitives where they should, for example most tehcnic beams are missing the last peghole if only inherited info is used.

[Philippe Hurbain]

Interesting approach. The good point is that it could allow some non-standard assemblies, but it seems a daunting task (for software and for defining connectivity)...

axle.dat primitive seems to be used for internals alot (Isn't is mend to be used open ended only?)

Purpose of primitives was originally to simplify parts authoring, and had nothing to do with connectivity. Axles and axleholes have the same shape, so share the same primitive! Maybe you could discriminate with bfc invertnext prefix...???

most tehcnic beams are missing the last peghole if only inherited info is used.

??? afaik all holes of beam use either beamhole or connhole or peghole primitive...

[Travis Cobbs]

If you look at some random one (I looked at 32524), you'll see that one of the holes is made up of 4-4cyli.dat (1), 4-4ring8.dat (2), peghole.dat (2), and the other holes use beamhole.dat. If you look at beamhole.dat, you will see that it contains all the geometry for the hole, plus everything up to the adjoining hole. Since you appear to be the author, I'm guessing you forgot how you authored them.

[Philippe Hurbain]

I meant that there was at least the peghole primitive... Indeed, beamhole and connhole are relatively recent additions to primitives. But peghole was created by James.

[Roland Melkert]

Interesting approach. The good point is that it could allow some non-standard assemblies, but it seems a daunting task (for software and for defining connectivity)...

I was planning to add editing of snap info to the editor it self, but so far most parts are quite easily done in notepad using some copy paste of rotation numbers.

Purpose of primitives was originally to simplify parts authoring, and had nothing to do with connectivity. Axles and axleholes have the same shape, so share the same primitive! Maybe you could discriminate with bfc invertnext prefix...???

Yes but isn't using the axle.dat in situations where you will never see one side of it's outer triangles somewhat misusing. Like e.g. the 57585.dat part. Now bushes etc go through it because the axle is open ended, it's no big deal I can just flush the inherited info and redefine something else for the loose part.

??? afaik all holes of beam use either beamhole or connhole or peghole primitive...

Most use two peghole.dat refs for the last hole, I somehow (maybe wrongly) expected them to use a single connhole.dat I can't add snap info to peghole.dat cause you don't know what that single 'flat' shape is used for at the part level.

[Philippe Hurbain]

Yes but isn't using the axle.dat in situations where you will never see one side of it's outer triangles somewhat misusing. Like e.g. the 57585.dat part.

I don't see the problem when part is not transparent...

I somehow (maybe wrongly) expected them to use a single connhole.dat

History...
Peghole is there from the beginning, Beamhole was put on PT on 2004-11-07, Connhole was put on PT on 2007-12-02. Most beams were created before 2007, so they couldn't use connhole (except if they were updated).

I can't add snap info to peghole.dat cause you don't know what that single 'flat' shape is used for at the part level.

Mmhhh... indeed it doesn't describe length of hole - I guess that's what you mean - but it is not flat. And AFAIK was only used as Technic hole entry (that's not the case for stud.dat that has been used a lot as a capped cylinder, but hopefully we got rid of this).

[Michael Heidemann]

For most of this questions LDStructure should be your friend

My personal feeling is that we should use for connectivity the -already working- implementation from SR3D. I did not looked deep into this matter, but that connection information should be stored in a separate file with the same naming except the extension.
By doing it this way we can keep and work on the library as usual and create the connection data in a separate step (parallel or afterwards). I liked the way I could create the connectivity with LD4DStudio, but it was a too mighty tools in my stupid hands .

[Max Martin Richter]

AFAIK the file extension of the connectivity files of SR3D-Builder is also .dat, but stored in a "Conns" folder in the LDraw base path.

/Max

[Michael Heidemann]

Thanks for mention that. I feel that using the complete same filename can create confusion - at least in part creation process. Which file contain the visual part and which file contain the connection information. Just by copy and past you can simply detroy your work!
I would suggest the extension .LCI for LDraw Connectivity Information.
A quick search on the internet leads me to this solution as it is not widely use.

As a side note - this kind of functionality would enable us to add another feature I am thinking of for a while.
We can also use this scheme for electrical information.
I would suggest for this kind of extension the extension .LEI for LDraw Electricity Information.

[Roland Melkert]

For most of this questions LDStructure should be your friend

My personal feeling is that we should use for connectivity the -already working- implementation from SR3D. I did not looked deep into this matter, but that connection information should be stored in a separate file with the same naming except the extension.
By doing it this way we can keep and work on the library as usual and create the connection data in a separate step (parallel or afterwards).

I'm not going to bluntly copy Sergio's snap info. We can also not just trow it into the library imho, because first we need permission for that and second I'm not sure a single definition will suit all software needs.

I liked the way I could create the connectivity with LD4DStudio, but it was a too mighty tools in my stupid hands .

LDCad will offer simplified animation based upon LD4DStudio's scripting approach at some point, it's the reason I stopped working on LD4D

[Michael Heidemann]

If I remember right we have somewhere in this forum information from Sergio about this, but could not yet find it.

[Max Martin Richter]

I like this idea with the extensions. But we should bring it into a special folder for each purpose in my eyes. So our library can be well structured...

/Max

[Michael Heidemann]

No complains from my side for special folders. But we should keep an eye on the extension.

[Michael Horvath]

Since we're at it already, how about a new file format for LDR and MPD files? Something XML-based maybe?

I've been digging through Datsville and there's a lot of inconsistency in metadata tags and so forth. XML would be a lot less ambiguous.

[Ben Supnik]

Hi Guys,

I implemented "insert related" in Ldraw to solve the 'awkward parts' problem - it lets you do things like put the glass door in a frame where the origins of the two parts are off by a goofy number of LDUs 9 so that the door can rotate around its axis. I've been pretty happy with the results in that it was quick to code the feature, quick to add to the 'related parts' dictionary, and it's quick to model with it. (I've been meaning to post notes on the final format in the bricksmith tree for the wiki but it took a while to get a wiki login and then I got distracted.)

But awkward parts is a really really limited problem...general connectivity (and general connectivity with animation or movement) is significantly more complicated!

With that in mind, I really would like to see a general-purpose connectivity scheme in LDraw someday - there are some editing and analysis functions you just can't write without it.

Sergio explained quite a bit about his connectivity system; I thought his model was a pretty good prototype for what LDraw needs -- there are a few cases where I might suggest elaboration, but his tech would be a great starting point. And he seemed (to me) amenable to us using a similar idea in LDraw and/or even seeding some connectivity data from an sr3d export.

Here are his sets of posts from a while back.

http://forums.ldraw.org/showthread.php?t...84#pid8184
http://forums.ldraw.org/showthread.php?t...15#pid8215
http://forums.ldraw.org/showthread.php?t...55#pid8255
http://forums.ldraw.org/showthread.php?t...32#pid8332

Re: in the library or out of the library, I suggest we hedge:
- Design a conceptual data model for connectivity that is agnostic of how the data is stored (side table or in-part).
- If we have to start with side tables, so be it.
- Maybe we move the data into the parts later once the tech is proven.

In particular, I think that it's important that meta-data for connectivity be "compose-able" - in other words, if you put meta-data on stud.dat (saying that stud.dat connects in such-and-such way) then that meta-data is implicitly spread to every stud in every part everywhere.

If we don't do this, then it will be hard to move the data into the parts themselves in the long term because parts have the semantics of fully including sub-parts.

Finally in terms of performance, I don't think we'll have a scalability problem with an LDraw part set that has tons of connections. Connections exist at small locations in space (e.g. they are typically points or lines). Therefore when you bring a 1x1 brick into Datsville, while there might be a million or more _total_ connections, there are going to be a very small number of nearby connections. Dump the connections in a spatial index (e.g. an R-tree or something) and you can have a very fast search even in a huge model.

(By comparison, _drawing_ parts is a real scalability problem because the user can always put more parts on screen and we must draw them all. This is why I would like to have low-vertex-count alternates, so that parts can be 'dumbed down' when they are small in total pixel size.)

Roland, if you have any interest in moving toward general connectivity and a shared file standard, please let me know -- I can send you my notes from when I last looked at this and/or review prototype connectivity data if you have built it.

Cheers
Ben

[Michael Heidemann]

That idea is not new
The base of all our work are plain text files.
If we are going to use a xml file format then -all- existing application will not work anymore.
So this idea should be thrown away very fast - I had the same idea some years ago

[Roland Melkert]

But awkward parts is a really really limited problem...general connectivity (and general connectivity with animation or movement) is significantly more complicated!

This is why I've started out with basic one on one point matching/snapping, which as you can see in my above youtube clip actually works quite well on the smaller parts.

With that in mind, I really would like to see a general-purpose connectivity scheme in LDraw someday - there are some editing and analysis functions you just can't write without it.

Sergio explained quite a bit about his connectivity system; I thought his model was a pretty good prototype for what LDraw needs -- there are a few cases where I might suggest elaboration, but his tech would be a great starting point. And he seemed (to me) amenable to us using a similar idea in LDraw and/or even seeding some connectivity data from an sr3d export.

This is also how I see it, if we we're to add info to the library it has to be generic. Otherwise software developers still need to add stuff to it if they want to do something a bit different.

Here are his sets of posts from a while back.

http://forums.ldraw.org/showthread.php?t...84#pid8184
http://forums.ldraw.org/showthread.php?t...15#pid8215
http://forums.ldraw.org/showthread.php?t...55#pid8255
http://forums.ldraw.org/showthread.php?t...32#pid8332

Re: in the library or out of the library, I suggest we hedge:
- Design a conceptual data model for connectivity that is agnostic of how the data is stored (side table or in-part).
- If we have to start with side tables, so be it.
- Maybe we move the data into the parts later once the tech is proven.

In particular, I think that it's important that meta-data for connectivity be "compose-able" - in other words, if you put meta-data on stud.dat (saying that stud.dat connects in such-and-such way) then that meta-data is implicitly spread to every stud in every part everywhere.

I basically started implementing my thoughts as described here:

http://forums.ldraw.org/showthread.php?t...73#pid8173

It's using 4 different shape describing meta's at the moment, and some additional support ones (like include and reset). I'll probably have to add one or two more for the very exclusive part shapes.

Finally in terms of performance, I don't think we'll have a scalability problem with an LDraw part set that has tons of connections. Connections exist at small locations in space (e.g. they are typically points or lines). Therefore when you bring a 1x1 brick into Datsville, while there might be a million or more _total_ connections, there are going to be a very small number of nearby connections. Dump the connections in a spatial index (e.g. an R-tree or something) and you can have a very fast search even in a huge model.

This is exactly what I'm experiencing in my current setup, even unoptimized it's almost a non issue for modern processors to do a couple of thousand (far/near) ray intersection tests. And on top of this it's a very good candidate for multithreading.

Roland, if you have any interest in moving toward general connectivity and a shared file standard, please let me know -- I can send you my notes from when I last looked at this and/or review prototype connectivity data if you have built it.

I'm always interested, my current setup is evolving almost daily tough, but basically it works with extendable parameters on a one meta per shape basis.

The cylinder one for example basically lists the varying radius's along a line like so:

0 !LDCAD SNAP_CYL [ gender=M ] [ caps=one ] [ secs=R 6 10 A 6 5 ] [ pos=0 0 0 ] [ ori = 1 0 0 0 1 0 0 0 1 ] [ center=true ]

This says: There is a one open ended male cylindercal shape existing out of a radius 6 round section of length 10 and a radius 6 axle shaped section of length 5 at 0,0,0 using identity rotation and the position is it's center.

There are more optional parameters (sliding behavior, friction, rotation limits, what do when scaled/mirrored by type 1 references etc) but those are far from set in stone.

These meta's are currently read from a mirror library tree which acts like an auto include location. The information will be inherited by higher referencing parts so currently all studs have info like you described. The real problem with inheritance are shapes like the 'anti studs' because those live in empty space and thus don't share a primitive reference.

I have been thinking about adding the info indirectly e.g by adding 4 anti studs to the commonly used middle under stud of bricks. But this introduces a whole new set of problems (e.g unwanted ones, duplicates, etc).

[Ben Supnik]

I basically started implementing my thoughts as described here:

http://forums.ldraw.org/showthread.php?t...73#pid8173

It's using 4 different shape describing meta's at the moment, and some additional support ones (like include and reset). I'll probably have to add one or two more for the very exclusive part shapes.

I think I understand what your direction and design goal is, but let me ask a few questions to see if I fully get it.

- Sergio's system is based on "type matching" - a bunch of connection types are defined (strictly via data) and a much smaller number of geometries. Geometry matches must also match type to connect.

- In your system, it's all geometry, and the matches are strictly geometric. In other words, ALL cylinders of the same radius are going to fit equally well into a hole of the same radius.

Is that correct?

And if I understand: every geometric type that we find in the LDraw world will have to be supported by some geometry primitive that is built into the spec. In other words, the fact that your example is part cylinder, part axle works because both cylinders and axles are native to your code. If we ever have a part with a new, different cross section (where the axle's cross section is not a + shape) we'll possibly need a new geometry primitive and spec extensions.

Also, how would you handle pins? A pin is a cylinder with a wide rim - it only fits into the technic brick hole (a cylinder hole with a wider hole at the edge) because it can be compressed. It effectively provides one degree of rotational freedom once it is snapped in, although it has longitudinal movement freedom (and a lot of friction) while it is being inserted into the hole.

Cheers
Ben

[Roland Melkert]

- In your system, it's all geometry, and the matches are strictly geometric. In other words, ALL cylinders of the same radius are going to fit equally well into a hole of the same radius.

Is that correct?

Yes in a perfect world this is what I really want. But I've had to make some compensations for the time being. Like anti studs, I would really like them to snap into large rectangles when such a shape would enclose them, but I decided to keep it one on one for the time being by defining them as a grid of radius 6 F-cylinders.

And if I understand: every geometric type that we find in the LDraw world will have to be supported by some geometry primitive that is built into the spec. In other words, the fact that your example is part cylinder, part axle works because both cylinders and axles are native to your code. If we ever have a part with a new, different cross section (where the axle's cross section is not a + shape) we'll possibly need a new geometry primitive and spec extensions.

Yes, at the moment the CYL meta supports round, axle, square and 'lock' (see below). I'll add more if I find parts needing it. Only hard coded about these shapes at the moment is a bool matrix that determines what shape fits another when using the same radius, I could move that to some config / include file if it must be user extendable.

Also, how would you handle pins? A pin is a cylinder with a wide rim - it only fits into the technic brick hole (a cylinder hole with a wider hole at the edge) because it can be compressed. It effectively provides one degree of rotational freedom once it is snapped in, although it has longitudinal movement freedom (and a lot of friction) while it is being inserted into the hole.

This is a single pin half definition (e.g. connect3.dat):

0 !LDCAD SNAP_CYL [ gender=M ] [ caps=one ] [ secs=R 8 2 R 6 16 _L 6.25 2 ] [ pos=0 0 0 ] [ ori=1 0 0 0 1 0 0 0 1 ]

It will fit in any cylindrical hole that matches the radius's pattern, the _L part indicates the 6.25 radius can be ignored while fitting (it uses the preceding radius for the core tests instead, hence the '_' in front). When something fits based on those conditions, things are reexamined to see if the '_L' portion still fits while using it's true radius.

This works in the current build. only downside is a full pin will inherit two definitions and therefore snaps depending on your view on the scene (you can see that in the clip). I've solved this recently by redefining the shape as a whole inside 3673.dat (no code changes just the def), like so:

0 !LDCAD SNAP_RESET
0 !LDCAD SNAP_CYL [ gender=M ] [ caps=none ] [ secs=L_ 6.25 2 R 6 16 R 8 4 R 6 16 _L 6.25 2 ] [ center=true ] [ ori=0 -1 0 1 0 0 0 0 1 ]
0 !LDCAD SNAP_CYL [ gender=F ] [ caps=none ] [ secs=R 4 40 ] [ center=true ] [ ori=0 -1 0 1 0 0 0 0 1 ]

In this case reset drops all inherited stuff, but the meta supports dropping only a certain (user named) group.

For example the axle4.dat has info, which is fine for stacks of parts. But some parts use that primitive as part of a larger cylindrical shape, you can then drop that specific info meta inside that parts definition to redefine a more precise (round/axle mixed) shape. But the 'simple' one will do just fine for the parts not having full information yet.

I've created about 180 definition files up to now, and I must say overall I'm very pleased by it's behavior, there are some issues I have to figure out some more but that's nothing new when trying to set up a new feature.

[Roland Melkert]

Just wanted to show the latest version:

Version 2 demo clip.

I'm quite happy with this version, it now snaps to stuff based on the actual part shape and not the cursor location.

I also added information for all parts in the normal brick and plate groups (or so I thought, thanks for the lib update )

I'm still open to suggestions on general behavior etc though. Things I'm wondering about myself is how to apply the grid to the sliding parts, cause it's way to exact now. Maybe add a forth 'axis' to the stepping table, if anyone has a better idea please let me know.

[Michael Horvath]

Wow, that looks very ambitious! How will that affect performance? LDCad is a pretty quick program.

[Philippe Hurbain]

Wow indeed

[Arthur Sigg]

It rocks me to the floor ! Sorry, want to say: I'm very impressed, I take my hat off !
I hope for a final solution on snapping informations as part of the Library, independent from applications.
I'm so happy to see a silver lining and one day to no longer have to use the "historical program".

[Roland Melkert]

Thanks all,

Current performance is ok but it could be better (it gets slowish with around 2000 info-ed parts in the scene on my pc). There is still room for optimization though (current version is single threaded, does stuff multiple times etc).

Also the version in the clips is a debug version so it's stacked with assertion tests etc.

But it will probably never be fast enough for something like datsville (as a whole). But you can always turn the feature off anyway. Something that's essential anyway in order to prevent fighting the system when some part just doesn't want to go where you want it to go.

[John]

Wow. This is excellent! Adding snapping combined with everything else LDCad already does and I think you might have the best LDraw editor out there. I find a lot of the others much more cumbersome that yours. It's approaching the ease of use that comes with LDD I think.

Can hardly wait to try this version!

[Roland Melkert]

Thanks,

But please keep in mind I intended the part snapping as an additional tool, grids will always be the main placement system. This because there will always be parts without snap info or situations when the snap system just doesn't do what you want it to do.

[John]

Understood. I think that's even better. Having the flexibility to turn snapping on and off would be huge. There are certainly times where LDD just doesn't want to snap the way I want it to. Being able to choose when to snap and when to place manually will be fantastic.