Why is picking so slow and collisions so fast?
Blitz3D Forums/Blitz3D Programming/Why is picking so slow and collisions so fast?
| ||
| I have never come across a situation where I could even get Blitz collisions to slow down...well, maybe a few extreme cases. It's well-known that visiblities picks are probabaly the slowest step in a game loop. Why? Would a system that used collision to check visibility be any faster? |
| ||
| Hi, With collisions, the entity is unlikely to have moved far - therefore there is less to check. Most entities are outside the 'movement' bounding box and don't have to be checked. There is a bit of (unintentional) temporal coherence going here. But the bounding box for a pick is potentially very large, and many things need to be checked. Blitz picking is far from optimal - a BSP tree would speed things up massively, along the lines of Maplet's shadow casting - but to provide good picking with any arbitray scene means you can't really rely on it being 'BSP-able'. |
| ||
| Hey Mark, 1. I wrote a line pick function in the code archives which you should take a look at. It has more features than the built in line pick function. Of course a built in function would be faster, so it would be nice if the built in function did everything that my function did. :-) For example, it is useful in lightmapping to only have the line pick be sucessful if the pick goes through the front side of a face, so when you are inside an object picking the outside world it doesn't pick the object. Also, my function can cast a ray in one direction or both directions, and the line can be infinite or not. I don't think my function explicity supports it but it would also be nice to get the exact triangle which was picked, the XYZ coordinate that was picked in world OR model space, and the UV coordinate in the triangle that was picked. (presuming that point 1->2 = U 0..1 and point 2->3 = v 0..1 or something like that) 2. I presume that you attempt to pick bounding spheres for all the entities before you attempt to pick the entities themsevles. But it seems odd that linepicking would be slow picking a mere 200 spheres... Hm... 3. Why use a BSP tree? Why not an octree? Hm... Or... Maybe you could sort the spheres into quadrants around the pick start location and then you would onlly have to check the spheres in one quadrant? Hm... actually that wouldn't work cause some spheres could overlap more than one quadrant. Hm. Well you could always add such spheres to more than one quadrant. The question then is whether adding the spheres to the quadrants is more expensive than just attempting to line pick them right off the bat. I also presume you're using this sort of check for the line to sphere checks... Of course maybe you're using line to some other shape which is faster than sphere? Would line to axis aligned bounding box be faster? That would be surprising. ----------------------------------------------------- Finding the closest point on a line to another point. ----------------------------------------------------- (x1, y1, z1), (x2, y2, z2) = ends of line segment (x3, y3, y3) = point u = (x3 - x1)(x2 - x1) + (y3 - y1)(y2 - y1) + (z3 - z1)(z2 - z1) ----------------------------------------------------------- (x2 - x1)(x2 - x1) + (y2 - y1)(y2 - y1) + (z2 - z1)(z2 - z1) u = the location between the two end points of the line which is closest to the point. If u is not between 0 and 1 then the closest point is not between P1 and P2 ---------------------------- LINE-SPHERE-INTERSECTION ---------------------------- To find out if a line intersects a sphere, find the closest point on the line to the center of the sphere. Then calculate the location of that point using U. And finally, find out the if the distance from that point to the center of the sphere is less than the radius of the sphere. |
| ||
| I kind of thought linepicks were sphere to poly collision, done fast over distance. |
   |