AutoCAD/Sketchup Style Hover Algorithms

Here’s a fun one for the algorithmists amongst you.

Drawing/drafting/vector graphics software let you manage vast amounts of “objects” in some creation environment. Users are constantly adding and removing objects.

When users hover over “key points” on an object (eg the end or midpoint of a line, or the corner of a rectangle) that point is instantly highlighted so the user knows they can click on it to do something.

The user can also instantly filter by layers which means not every point is highlightable at any point in time.

Does anyone have any ideas as to what data structures/algorithms are in use here? I’m building 3d modelling software and am stuck with this problem.

What I’m doing at the moment is getting all my points and specifying some fixed size bounding box around them. I then add them to an octree (a JME octree in fact). When the mouse is moved I cast a ray through the octree and get the closest point.

This isn’t flexible enough, however. Whenever I add or remove an object, I have to reconstruct the whole octree, which takes a second or two (significantly slower than should be needed given how fast other software does this). I am also unable to easily filter (sometime you might only be able to click on some objects for example).

The problem feels like it should be sub log(n) complexity (with some octree like bucketting algorithm) but I haven’t had any A-ha! moments yet.

Surely this problem has been solved a million times. Any thoughts?

Never did something like that, but one idea came to my mind:

First: Get the cursor position in world space. Then iterate over all vertices that are in the view frustum and check wether the projection ( simply ignore the depth value :wink: ) is in scope of a circle with a specific radius you chose as threshold.
After that check every hit on visibility and the other parameters you want… In the end you can return a list of vertices.

If you got your vertices stored in an octree you could check them even faster since you could banish all leaves that arent close to your cursor location…

Dunno if its clever or even right that way, but thats at least what I would try. :smiley:

@KuroSei’s suggestion would work but can be optimised. First check the bounds of objects and then only check the vertices once you have eliminated them all using the bounding boxes.

There are a bunch of collision/intersection/etc facilities available within the engine. You may well have to do the vertex identification yourself but certainly you can drill down to the geometry level using the tools provided.

1 Like

That makes sense… I’ll have a play around with the tools in the engine.

How do you think they manage object counts? Admittedly a lot of objects in those packages look like they use similar materials, but I’d wager that’s for visual clarity, not optimization.

I would think that I could have an AutoCAD file with hundreds of thousands of objects on unique layers (and therefore materials) and not see a loss in framerate…

I don’t know how they would do any object batching. In AutoCAD, the user can instantly delete everything, add everything back in again and change materials essentially instantly… very impressive!