for (int i=0; i<totalNumberOfVertices; i++)
{
vector = proxyposition - vertex[vert].position;
current = vector.length();
if (i==0)
{
closest=current;
vertexnumber=0;
}
else
if(current<closest)
{
closest=current;
vertexnumber=i;
}
}
Collision Detection Algorithms
Author
Hi. I am looking for a way to decide if and which vertex of a mesh my mouse position (or proxy) is in contact with. This happens in each interval. The 3D object that the vertices construct is deformable. Each vertex has been assigned an integer number so it can be identified. At the moment I run a loop that compares the proxy position with ALL the vertices' position every timstep, then it finds the shortest distance and returns the integer number assigned to that vertex (making it slow with many vertices). As shown below:
Is there a quicker algorithm for me to do this without resorting to complicated BSP or other huge algorithms? Something not too complex but will give me a bit of a boost with speed?
Thanks
[Edited by - chrome68 on May 5, 2009 3:30:45 AM]
How are you determining the position of the proxy? Assuming typical mouse picking, there is an infinite number of world-space points that correspond to the screen-space position of the mouse, so I'm wondering how you're settling on a depth for the query point.
In any case, some simple spatial partitioning should do the trick. I would probably use an octree in this case (octrees aren't too hard to implement).
Also, unless you really do have a meaningful way to determine a depth for the query point, I would recommend using a picking volume instead (I recommend a pyramidal volume rather than a ray because it will give you uniform picking behavior regardless of distance - that is, points that are far away from the camera won't be more difficult to pick than those close to the camera).
For what it's worth, I've implemented face picking for complex models using this method, and it was plenty fast. That your object is deformable will add some complications though (in that you'll have to update the octree as the vertices move). Whether this will be a problem or not really depends on how and to what extent the object deforms.
In any case, some simple spatial partitioning should do the trick. I would probably use an octree in this case (octrees aren't too hard to implement).
Also, unless you really do have a meaningful way to determine a depth for the query point, I would recommend using a picking volume instead (I recommend a pyramidal volume rather than a ray because it will give you uniform picking behavior regardless of distance - that is, points that are far away from the camera won't be more difficult to pick than those close to the camera).
For what it's worth, I've implemented face picking for complex models using this method, and it was plenty fast. That your object is deformable will add some complications though (in that you'll have to update the octree as the vertices move). Whether this will be a problem or not really depends on how and to what extent the object deforms.
Author
Hi. The collision is already handled by the software i'm using. However it doesn't provide me with which vertex. The proxy position is continually monitored by the software and i can extract it at any given point in time. I can also obtain the position of each vertex of the 'very' deformable object. Octrees sound very advanced and up the scale. Is there no alternative that is simpler?
So I gather the software you're using performs a ray intersection with the (deforming) object and returns the intersection point, and you're wanting to determine which vertex or vertices of the object are closest to this point?
Can you tell us what library or API you're using for this? It seems to me that whatever it is, it must be performing broad-phase culling of its own as part of the raytracing. As such, it seems like kind of a waste to have to do this yourself as well. Do you have any access to the internal workings of the library? Is it a .dll or external module of some kind, or do you have access to the source code? What functionality exactly does its interface expose? (I ask because the nature of your question is complex enough that the details of the tools that you're using matter somewhat.)
Anyway, it sounds like what you're looking for is a nearest neighbor search. I haven't had need to investigate this topic to any great extent, so I can't offer much in the way of specific advice, but the subject is fairly well documented online and elsewhere.
Honestly, octrees are pretty simple as far as spatial partitioning goes (although I'm not even sure that an octree would be the most appopriate solution here). Grids are a bit simpler yet, but you're not going to get much simpler than that. With either a grid or an octree, you could identify the node in which the query point resides and then perform a breadth-first search to find the nearest neighbor. The costliest aspect of this approach would probably be keeping the grid or octree updated as the object deformed.
Maybe someone else will chime in with some better suggestions as to how to approach the nearest-neighbor problem. Meanwhile though, I think at this point some more information about the problem would be helpful, including what APIs/libraries you're using, and what the context is (that is, what is the object, how is it deforming, and why do you need to be able to pick individual vertices using the mouse).
Can you tell us what library or API you're using for this? It seems to me that whatever it is, it must be performing broad-phase culling of its own as part of the raytracing. As such, it seems like kind of a waste to have to do this yourself as well. Do you have any access to the internal workings of the library? Is it a .dll or external module of some kind, or do you have access to the source code? What functionality exactly does its interface expose? (I ask because the nature of your question is complex enough that the details of the tools that you're using matter somewhat.)
Anyway, it sounds like what you're looking for is a nearest neighbor search. I haven't had need to investigate this topic to any great extent, so I can't offer much in the way of specific advice, but the subject is fairly well documented online and elsewhere.
Honestly, octrees are pretty simple as far as spatial partitioning goes (although I'm not even sure that an octree would be the most appopriate solution here). Grids are a bit simpler yet, but you're not going to get much simpler than that. With either a grid or an octree, you could identify the node in which the query point resides and then perform a breadth-first search to find the nearest neighbor. The costliest aspect of this approach would probably be keeping the grid or octree updated as the object deformed.
Maybe someone else will chime in with some better suggestions as to how to approach the nearest-neighbor problem. Meanwhile though, I think at this point some more information about the problem would be helpful, including what APIs/libraries you're using, and what the context is (that is, what is the object, how is it deforming, and why do you need to be able to pick individual vertices using the mouse).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
