Hi,
I need to create a "picking"/"selection" algorithm in order to select/pick my objects/faces/vertices/edges/wires/... in my 3D view.
But, I can't use any low-level API like OpenGL/DirectX !
I have think to use a BVH but it request a lot of time to create !!
So, I would like to know how you do in general and which algorithms are the best ?
Thanks for your advices
Picking/Selection algorithm - without OpenGL ... ?
Two relatively easy solutions:
1) The easiest and fastest way to do it is keeping a buffer of identifiers, which has the same dimensions as your projection buffer.
This buffer would be filled with 'identifiers' (pointers (i.e. addresses), for example) by your rendering algorithm, depending on the 'selection mode' (vertex, edge, face, etc).
Now you can simply read out the 'identifier' under the mouse cursor to know which 'object' was selected/picked.
2) Another option is to cast a ray from your viewpoint through a 'pixel' on screen and use some intersection math (again, depending on the 'selection mode') to determine what (if any) was selected/picked.
I implemented both solutions several times thoughout the years in my software rasterizers. They are really quite simple to get working.
1) The easiest and fastest way to do it is keeping a buffer of identifiers, which has the same dimensions as your projection buffer.
This buffer would be filled with 'identifiers' (pointers (i.e. addresses), for example) by your rendering algorithm, depending on the 'selection mode' (vertex, edge, face, etc).
Now you can simply read out the 'identifier' under the mouse cursor to know which 'object' was selected/picked.
2) Another option is to cast a ray from your viewpoint through a 'pixel' on screen and use some intersection math (again, depending on the 'selection mode') to determine what (if any) was selected/picked.
I implemented both solutions several times thoughout the years in my software rasterizers. They are really quite simple to get working.
Well, I'm against world space ray picking. The problem with ray picking: in perspective projection, the accuracy will make selecting distant objects impossible. So you have to compensate that somehow, which isn't very elegant IMHO. So instead, I use screen space selection. Window selection becomes easier to handle, and the selection accuracy will be independent from the distance by default.
Author
Thanks for your answer,
Currently I simply cast a ray in space and check for intersection with every triangle... it is very slow :-P
My goal is to simply increase the performances !
Also, my current "rendering engine" has no depth-buffer or something like that.
So, I don't know how to do :-P
Currently I simply cast a ray in space and check for intersection with every triangle... it is very slow :-P
My goal is to simply increase the performances !
Also, my current "rendering engine" has no depth-buffer or something like that.
So, I don't know how to do :-P
Just to clarify (I think we might have a slight misunderstanding due to terminology; which is my fault I'm pretty sure):
In the second solution I proposed, I'm talking about casting a 3D ray. When I wrote screen pixel I actually meant a point on the Z==0 plane which relates to a screen pixel.
When you have your calculations right and, more important, consistent, inaccuracy shouldn't be a problem, not even for objects that are far away.
I never had trouble with it, as far as I can remember.
The first solution is definitely the most straight forward and easiest to implement solution if you're only interested in picking top-most objects/entities.
That is, if you don't mind having an extra buffer eating up some memory and losing some cycles during rendering (since this would be for an editor-type of application, I guess that shouldn't be an issue).
In the second solution I proposed, I'm talking about casting a 3D ray. When I wrote screen pixel I actually meant a point on the Z==0 plane which relates to a screen pixel.
When you have your calculations right and, more important, consistent, inaccuracy shouldn't be a problem, not even for objects that are far away.
I never had trouble with it, as far as I can remember.
The first solution is definitely the most straight forward and easiest to implement solution if you're only interested in picking top-most objects/entities.
That is, if you don't mind having an extra buffer eating up some memory and losing some cycles during rendering (since this would be for an editor-type of application, I guess that shouldn't be an issue).
polar01, you were just a little to fast for me with your reply :)
What kind of rendering are you doing? Are you implementing a software renderer?
Some extra information might help to determine what could be the quickest solution for you.
What kind of rendering are you doing? Are you implementing a software renderer?
Some extra information might help to determine what could be the quickest solution for you.
Quote:Original post by szecsIt shouldn't be that much of a problem. One fairly straightforward solution is to pick using a frustum rather than a ray (which isn't in any way inelegant, IMO).
Well, I'm against world space ray picking. The problem with ray picking: in perspective projection, the accuracy will make selecting distant objects impossible. So you have to compensate that somehow, which isn't very elegant IMHO.
Quote:Original post by polar01Typically you would use some sort of spatial subdivision scheme (such as an octree) to accelerate the query.
Currently I simply cast a ray in space and check for intersection with every triangle... it is very slow :-P
Author
Yes, it is my questions :-)
Which space subdivision should I use ?
BVH
KDTree
Grid
BSP
Octree
By example BVH or KDTree are very fast (with improved versions like SBVH etc....). But the problem is that I have to create the tree and it has a cost (time) ! and whta happen if I change my geometry, each time I have to rebuild the BVH !
Also, what happend if I have models with millions of triangles !
So, my question is to check if there are better alternatives ?
Which space subdivision should I use ?
BVH
KDTree
Grid
BSP
Octree
By example BVH or KDTree are very fast (with improved versions like SBVH etc....). But the problem is that I have to create the tree and it has a cost (time) ! and whta happen if I change my geometry, each time I have to rebuild the BVH !
Also, what happend if I have models with millions of triangles !
So, my question is to check if there are better alternatives ?
polar01, an octree is one of the most useful spatial subdivison method that I ever implemented. Even/especially with millions of polygons you get good results, depending on your configuration. (disclaimer: I'm not an expert on spatial subdivision algorithms!)
Also moving entities are rather easily moved between nodes in an octree.
There's are lot of information available all around the net about octrees. I'd suggest you have a look at that.
You may even come up with a hybrid solution, mixing several methods. Don't restrict yourself to a single point of view! (that's the good thing being a programmer; you've got all the freedom :) )
Also moving entities are rather easily moved between nodes in an octree.
There's are lot of information available all around the net about octrees. I'd suggest you have a look at that.
You may even come up with a hybrid solution, mixing several methods. Don't restrict yourself to a single point of view! (that's the good thing being a programmer; you've got all the freedom :) )
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
