AABB Snapping in 3D

[jacquesr]

Hi guys,

I am currently in search of an algorithm to solve a problem that is very common in 2D: Snapping. I want to do this in 3D. I couldn't yet find any real information on how to efficiently approach this with 3 dimensions. I want to have the snapping as intuitive and fast as possible, so in my first implementation, I made for the following assumptions for my result:

1) I try to snap only while colliding. That avoids me having to cache a lot of possible snappoints or struggle with any datatrees. Drawback: I cannot snap when I'm close to an object, only while I collide with it.

2) The original position 'where the mesh would be if no snapping occured' is my starting point. With every mouse move I get while dragging a mesh around, I start the procedure again to evaluate possible snap points.

3) I have a threshold about how far 2 vertices can be apart from each other to cause a snap.

4) I only snap against 8 points (for now). The lower and upper corners of the bounding box. No center points yet.

5) If multiple snap points are within the threshold, the closest wins

6) The same vertex indices cannot snap with each other (would cause the object to sit inside the other one, which is no useful snap)

So far, this procedure works quiet well, as long as it stays in 2D. But there is one feature I want to add: Automatic raising of the mesh when it is inside another mesh and could stand on top of it. That changes the snap points that are compatible to each other since the mesh being dragged should be inside the area of the snap partner mesh. This is not a problem.

The things I am struggling with is that I can currently not really find a ruleset that works well in terms of how to decide if I can stand on top or need to stand next to a mesh. I can have a lot of differently sized meshes. I can probably not disallow the snapping on top if the mesh is bigger in area size than the one it will be on top of.

 

I may have to add more info but for now, any ideas on how this can work well are highly appreciated...

I also started thinking if the fully automatic raising of the mesh is generally not a good idea. Instead, one could use the mousewheel to switch Y position layers. During the dragging, layers would automatically be generated for every possible floor Y position I can identify from the currently colliding meshes (that collide on X and Z, of course)

Regards

Jacques

 

 

[jacquesr]

btw I will add a babylon playground with my current approach, I just have to port the code from my project...

[RaananW]

Hi!

Snapping... That's a wonderful subject ☺

I built snapping in an old project of mine, but that was based on a button, that when pressed, snapped one object to the ground. That requires a bit of math and that's about it.

I believe you mean snapping while the object is moving? Or dragged with a pointing device? 

 

[jacquesr]

Hi Raanan,

exactly. The point at which is becomes interesting (from my point of view / experience made so far) is when the 3rd dimension is involved. Snapping only e. g. objects that are on the same floor height (same minimum y bounding box position) is quiet easy. Yet automatically raising an object when it should sit on top of another one is something I could not yet solve to an extend I really like. I ended up being never able to snap to the ground as soon as multiple objects where involved, due to the fact that the thresholds sometimes eliminated the "better" choice (from the user perspective).

Also, when automatically raising the object, it is of course no longer behind the pointer. I will try to make a babylon example that I can work on ASAP. I want to solve the "staircase" case. So that I can move down a staircase with an object just by dragging it and being able to snap to each corner and also side...

 

Regards

Jacques

[RaananW]

looking forward to your playground  

[Wingnut]

Hi guys!

   Snaps are cool.  I'm glad you are trying this, J.  I also look forward to it. 

Thresholds, yeah boy.  Sometimes I think that the ONLY way to accomplish this... is to use buckies.  (buckies/bucky is an old Stanford Univ. term that I'm trying to raise from the dead.  Buckies are keys like control, alt, shift, etc.  Holding control and alt at the same time... is called a 'double bucky'.  Kind of fun).

Annnnnnnyway (continuing right along), maybe 3D snapping will require them.  For example:

- no bucky during drag, no snaps.
- shift key down during drag, X-axis snaps.
- alt key... Y-axis snaps.
- control key... Z-axis snaps.

Maybe some of the modelers (Maya, Max, Blender, etc) use this same method.

There's another user-interface for snaps, too.  Auto-snap or "smart-snap"... a list of snapping locations.  This would be where the user might repeatedly press control-s, and the snap object keeps snapping to different locations... until the user finds one they like  (probably only useful for building structures with boxes).

Jacques, maybe a front-sided box... inside of a double-sided box... is a decent starter playground for snap-meisters such as yourself?

http://www.babylonjs-playground.com/#15LYCI

Just you (camera), a decorative refrigerator magnet (inner box), 6 refrigerator doors (outer box), and a dream.   Good luck!

[jacquesr]

Hi Wingnut,

thanks for joining this discussion. I am currently developing a prototype in visual studio which I try to keep in a state that is easy to copy back into the playground.

I am going to use different mechanics, a mixture of those you listed above. Might still take a week since I am very busy at this time.

 

Regards

Jacques

[jacquesr]

Hey Guys,

I made it. First prototype that can be shown is ready. Please read my introduction first:

The prototype now only works with pre defined snapping points. The mesh information is extended for every created mesh. I want to add further interaction later (so that e. g. you can also freely move the mesh and snap on X and Z to other meshes) 

You can select a mesh with your mouse. When it's selected, you need to hold down Q to show the snap edge points. With Q held at least until you grab a point, you can now drag your mouse onto another mesh.

There is a (hopefully bug free) smart timeout so that when you hold still your mouse over the other mesh for 300ms, it becomes "locked". Then, you can see possible target points and lock on to them. If you let go the mouse, your mesh moves according to the source and end snap point selected. There is also a preview ghost mesh that shows you what will happen.

 

Please provide feedback guys.

 

Link:

http://www.babylonjs-playground.com/#12LLHA#0

EDIT:

Please be aware of the fact that I inject another 2D canvas into the playground to draw the 2D line between the points. I don't know if that works fine in every situation. With chrome on my desktop machine it works fine.

[Wingnut]

Hi J!  Hey, that works REALLY quite nicely!  Well done!  Works very well in my Firefox.  Boy, you've put lots of work into this. Congrats on proof-of-concept and demo #1!  Sweet!

[jacquesr]

Thanks. Going to improve on features so that we get multiple ways to snap. Also, it might need some UX improvements since it could be hard for a dummy user to grasp how to position things or see where in 3D space a point really is. It must meet the stupid user test

[jacquesr]

Hi guys,

I worked a lot in improving the usability of the prototype.

I made the following changes:

- snapping now works against sides of meshes

- the source mesh can be grabbed anywhere instead of only on specific points

- when moving over the side of a mesh, the closest of the already existing edge vectors (which I used in the first prototype) is evaluated and according to the one that is closest to the mouse, the selected mesh is positioned so it is aligned with the vector

- the mesh can now snap to itself (offset by its own dimension)

CONTROLS:

Click on a mesh to select it. You need to click once to select it, since I currently do that on mouseup.

Then, drag around the mesh (it wont follow your mouse currently, you will get a ghost mesh as soon as you hit the side of another mesh

 

 

The system now feels a lot more natural, at least from my point of view. There are still things that can be improved but it generally works really well.

Be aware that the code includes a fix for mesh.getChildren by injecting the method of 2.3 since it seems to be broken in the playground babylon version at this time.

http://www.babylonjs-playground.com/#28EVFY#0

 

 

 

 

[jacquesr]

Hi guys, another quick addition.

When snapping to sides others than top or bottom, you can use the arrow keys to force a specific list of points to be active only.

left arrow = all left vectors are active only

right arrow = all right vectors are active only

up arrow = all upper vectors are active only

down arrow = all lower vectors are active only

 

you can combine up or down with left or right

that improves the snap point selection

Please be aware that the key presses dont retrigger the selection so you need to move the mouse after changing the modifiers

 

http://www.babylonjs-playground.com/#28EVFY#1

[Wingnut]

That is working just great, J!  I need coffee before doing more tests, but... I was thinking about how/where to use this.  Certainly Luaacro's new editor could benefit from this, AND a rotation snap as well.  I guess that depends on the save/load abilities of the new editor, too.  Now where's that darned scene graph to playground editor button?    (that was a lame reference to another thread - ignore that comment at will) 

The drags and keypresses needed for your snap... are sure to collide with other clicks, drags, and keypresses that are in some user scenes. 

This is made for an editor, right?  Or maybe... for... when a scene is in "edit mode".  There will be times when... umm... user might want to "remember" all the snaps they did to a scene... by generating JS that they can paste into their scene code.  After an hour of playing in Snapperville, they might want to see a dump of actions.

box1.position = blah;
sphere3.position = foo;
etc.

They could paste this dump... into their scene, and then the snaps would be permanent... and re-done programmatically... at RUN time.  Naturally, if a user snapped a box to 10 different locations before they were satisfied, we would want ONLY the LAST snap position to be in the dump list.

My dream... is to easily assemble space craft and other 'compound models'... using all BJS primitive shapes. Then, somehow save the space craft assembly (save/dump all the .position changes that caused the space craft to assemble into that shape).

I don't know.  I'm just bubbling, here... thinkin' and inkin'.    Thoughts?  Anyone?  I really like what you've done here, J!  Nice job!
 

[jacquesr]

Well, we are using that for a logistics component that shows a truckload which allows interactive load editing. There are customers demanding highly interactive capabilities for such a component and I'm faced with getting this to work. We already have an undo/redo mechanism for position and rotation changes and it just works great. Combined with a port of my prototype into our project, I think there might be users that can optimize their load for their needs faster than an algorithm could. That is - of course - only for specific cases and demands.

With the undo/redo, we also only save the state that is achieved when the user lets go the mouse. The mesh/3D scene stuff acts as a slave component that listens to events on a nodetree, which can be edited with a command system (that stores the actions for undo/redo). The only special case where it is the other way around is the interactive editing that is done with the mouse, since here, the mesh positions lead the node tree. When the mouse is let go, we get the cached overall offset from the last permanent position and create a command with that ("move the node by x/y/z" command). We then redraw the node (which causes multile mesh disposals/recreates).

Also, for rotation, we do an animation and when we are done, do a redraw (dispose/recreate) to ensure that transformations don't become irritating when working with positions.

But back to the snapping: I might write a class that contains all things that extend the mesh so it can work with the snapping system. And then the modifiers can be freely bound to keys by only publishing certain editable states.

[Wingnut]

Excellent!!!  Wow, thanks for sharing that with me/us.  What a great application.  Yum!

[Vousk-prod.]

Woaw, that's a great piece of code! Congrats!

[jacquesr]

Code Ninja

 

Thank you for the feedback guys.

Going to give you a typescript class for easier integration... Have to port that first. Might take another week, maybe.

[Wingnut]

btw, you don't "give" a typescript.  The community actually comes to you, and wraps itself around you and all your code and ideas.  No toss'n'run.  You will be safely and gently ensconced in the gooey goodness of the BJS community/framework.  You will become "one" with us.  Resistance is futile.  hehe.  (yikes)

[jacquesr]

Hey everyone,

I just wanted to let you know that I am still working on the class... It has become quiet specific since I needed some extensions due to the fact that we have a very specific mesh cascading (e. g. where the mesh moved is not the mesh picked and there are some rules)

I might still release a real reuse class but it can take some time...