D.I.Y. 2D LinePick

Hi

I wondered in another post how B3D does it's LinePick but I'd like to formalize that question here, now.

It seems to 'walk along' the pick line until it hits a pickable entity. I say this because the time taken to do the pick is shorter the nearer to the pick line origin an entity is encountered. Then there's the ability to give the pick line a radius. I'm struggling to visualize how LinePick's functionality is realized efficiently, TBH.

The reason I'm pondering this is because I want to do a LinePick function for my 2D vector entity lib.

Hopefully, because I'm only dealing with entities defined entirely of 2D vectors, things shouldn't be as complex as B3D's LinePick (*nervous giggle*). Basically, it's going to boil down to using a line intersection test between the pick line and all the vectors comprising an entity, I guess?!

However, it's not quite as simple as that for a couple of reason that spring immediately to mind:
- If an intersection is found between the pick line and an entity's vector, I still need to continue checking the rest of the entity's vectors in case an intersection is found that's closer to the pick line's origin (I need PickedX,PickedY functionality, too).
- I'll need to check every pickable entity to find the entity whose vector intersected with the pick line, nearest to the pick line's origin.

I think this basic approach will work but it occurs to me that there's going to potentially be a lot of distance checks (although, I may be able to avoid use of Sqr and just work using the squared distances involved), and secondly, this cant be the way B3D does things as my way takes the same amount of time to execute, regardless of the pick line length and how close to it's origin an entity is picked. Also, how to implement a pick line radius - or, line width, in my case - goodness knows!

Am I missing a better way to achieve this? Any help and/or insights into how B3D does LinePick, much appreciated.

Thanks.

(In the meantime, I think I'm going to try and implement the method I mentioned, and see how things work out...)

Hmm, OK.

Well, the method I outlined above actually works quite well i.e. it's faster than I thought it'd be.

I still can't think how to give the pick line a width, though. No big deal, really - don't think I've ever used pick radius in B3D, anyway. Wouldn't mind having the ability for completeness, though.

I'd also like to make my algo more intelligent instead of just testing against every single line of every pickable entity. I'll have to have a think...

I'd still like to know how B3D does it's picking, too!

big10p - if you don't want it to test against every single line then perhaps you can first test against the 'bounding box' of each object first and then only check against each line for those whose bounding box was intersected.

Even quicker would be to use bounding spheres. You should be able to build a simple function to auto create these based on the poly info.

Yeah - the bounding box/sphere idea didn't cross my mind but I was unsure of any benefits as most vector entities are comprised relatively few lines - unlike in 3D where entities can have 1000's of polies.

I'm not totally convinced the benefits will outweigh the overhead of implementing bounding box/sphere. I'll have to experiment as I could be wrong. :)

Cheers!

Stevie: I'm having trouble calculation a bounding circle (this is pure 2D) without a silly amount of work. I can easily calculate the mesh width/height based on the mesh's vertices but this basically just leaves me with a bounding box.

Any ideas?

I would just find the average of the vertice positions to get your origin. You'll obviously need to store this. The distance of the vertex which is furthest from this origin will then be the bounding radius.

Not perfect but good enough to be used during quick broadphase checks.

Stevie

Turns out bounding boxes are far easier to implement and probably quicker. :)

It's about time you demo'd this thing!! In the words of "PUKI", I'll wait here ....

Heh - I'm just adding bits to it when i feel like it. It's no major project, or anything. :)

It'll be done when it's done. Don't expect anything flashy tho - it's only vector GFX entirely drawn using Line. :/

I'd like to add a collision system similar to B3D's, where you can move an entity and collisions are detected between the old entity position and it's new one. No idea how to do this though, really. Any ideas? :P

[edit] And, I guess I'm gonna have to write a demo game (and mesh editor :/) when it's done, just to 'showcase' the thing. Asteroids again, anyone? :D