Fastest way to do point search?
Blitz3D Forums/Blitz3D Programming/Fastest way to do point search?
| ||
| Allrighty, if anyone has really fast & clever way to do following math stuff, please post. Here's my case: I have a "pointcloud" - random bunch of points in 3D space, typically 100 or so but can be few hundred and sometimes less than 100. Points are static after generation, so they can be put in types / banks or whatever to make the search faster. What I need is the ability to find the two closest points to the "camera" in each frame and their relative distances (both distances together = 100%). And what would be fastest way to do small (maybe 16*16) bitmap color value blend (two bitmaps indexed with the pointcloud) using above percentages... What I have in mind is sort of pointcloud that marks the spots for these 16*16 "particles". |
| ||
| The fastest way would probably be extremely copmplicated. But a very fast simple way would be to use some method which divides the world into a grid, or several grids of varying size. You can then dtermine which grid square a point is in simply by dividing it's position by the grid resolution and discarding the remainder. Ie, divide by 64, and use Floor(). Then you can examine only those points which are in the same region of the grid as the camera. Granted, this will require three divides per point minimum, and three calls to Floor() but it avoids an IF statement to dtermine if a point's distance is less than that of the last point checked. I'm not sure if it will in fact be faster though. I dunno if you realise it, but you don't need to do a square root to find the two closest points to the camera. All you need to do is this. This should be more than fast enough for even 100,000 points. ; Set these values as appropriate given the scale of your world. They should be larger than whatever the greatest distance you think a point will ever be from your camera. Pd1# = 65536 Pd2# = 65536 For Point = 0 to Total_Points-1 ; Get Point's xyz here. D# = Px#*Px# + Py#*Py# + Pz#*Pz# If D# < Pd1# If D# < Pd2# Pd2# = D# P2 = Point else Pd1# = D# P1 = Point endif endif next Now, you can just compute the distance of P1 and P2 from the camera normally if you need it. And this loop goes through all the points only once, so it's linear in speed which means it's pretty fast. And there's no square root. Ps: When I say Px#*Px#, what I was assuming was the camera is centered at 0,0,0. If it is not then you need to do (Cx#-Px#)*(Cx#-Px#) for X Y and Z. |
| ||
| Yes, the "camera" will be moving... so, fastest (practical) way would be to just go through all the points without using any Überclever math? I'm pretty sure that my pointcloud max won't be more than 1000... should I use arrays, types or banks? Is there any noticeable speed difference? Can you explain this part bit more, why are you multiplying the values? D# = Px#*Px# + Py#*Py# + Pz#*Pz# And what's the fastest way to check the true distance between x1,y1,z1 and x2,y2,z2? |
| ||
| But what if the camera is in a gridcell not containing any points? What about dividing the cloud into equally sized partitions ,as sswift suggested, and then find the nearest partition (containing points) and then do the distance check on the points inside. Hmm, this sounds like an octtree. |
| ||
| "And what's the fastest way to check the true distance between x1,y1,z1 and x2,y2,z2? " The ONLY way to check the TRUE distance is with a square root. There's no faster way. You can use approximations of course. The worse the approximation the faster it will be. I would not bother concerining myself with it though unless you're doing it hundreds, perhaps thousands, or even tens of thousands of times a loop. I use squared distances when I can to compare two distances, but when I need a true distance I use a square root, and I don't worry about it unless I actually detect that my game is running too slowly and then I look for places I can make big optimizations. So if I had a loop running 100,000 times a frame with a square root in it I might look at using an approximate distance function, but more likely I'd try to find a way not to run that loop 100,000 times instead. |
| ||
| Approximation is often slower than throwing a Sqr() at it (depending on age of hardware). |
| ||
| squared distances Ah, so "D# = Px#*Px# + Py#*Py# + Pz#*Pz#" means that... :) And yes, you're right about square root - and I only need to do that twice during a loop after I have found the two points that are the nearest ones in the point cloud. Thanks, as always! |
| ||
| Approximation is often slower than throwing a Sqr() at it (depending on age of hardware). Really? Gheez... now I think that I need to do some sort of benchmark app to measure what would be the fastest way... maybe using 5000 random points as max poincloud points (I don't think that I'll ever use that much). |
| ||
You can also do a Bounding box + Squared distance search. It's the lower one of these two:Type point Field x#,y#,z# End Type width# = 100.0 height# = 100.0 depth# = 100.0 For i = 0 To 4999 point.point = New point point\x = Rnd(width) point\y = Rnd(height) point\z = Rnd(depth) Next camx# = 50 camy# = 50 camz# = 50 ms = MilliSecs() For loop = 1 To 1000 d0# = 100000000.0 np.point = Null For point.point = Each point dx# = point\x - camx dy# = point\y - camy dz# = point\z - camz d# = dx*dx + dy*dy + dz*dz If d<d0 d0 = d np = point End If Next Next Print "Squared search : "+(MilliSecs()-ms) Print "Nearest point : "+Str(np) Print ms = MilliSecs() For loop = 1 To 1000 d0# = 100000000.0 np.point = Null For point.point = Each point d# = (point\x - camx) * (point\x - camx) If d<d0 d# = d + ((point\y - camy) * (point\y - camy)) If d<d0 d# = d + ((point\z - camz) * (point\z - camz)) If d<d0 d0 = d np = point End If End If End If Next Next Print "Bound + Squared search : "+(MilliSecs()-ms) Print "Nearest point : "+Str(np) Print WaitKey() EndThat seems to be at least marginally faster than doing a squared distance search. To get it much faster than that you will probably need to build a search tree :) [edit] Ohh, I didn't really read your post :) So this one only finds the nearest point. |
| ||
Here is the modified code, that will find the two nearest points. As you can see it get's a bit more complex with the second method, but none the less it is a good deal faster.Type point Field x#,y#,z# End Type width# = 100.0 height# = 100.0 depth# = 100.0 pts = 5000 lps = 1000 For i = 1 To pts point.point = New point point\x = Rnd(width) point\y = Rnd(height) point\z = Rnd(depth) Next camx# = 50 camy# = 50 camz# = 50 Print "Search through "+pts+" points "+lps+" times" Print ms = MilliSecs() For loop = 1 To lps d0# = 100000000.0 d1# = 100000000.0 np0.point = Null np1.point = Null For point.point = Each point dx# = point\x - camx dy# = point\y - camy dz# = point\z - camz d# = dx*dx + dy*dy + dz*dz If d<d0 d0 = d np0 = point ElseIf d<d1 d1 = d np1 = point End If Next Next Print "Squared search : "+(MilliSecs()-ms)+" ms" Print "Nearest point A : "+Str(np0) Print "Nearest point B : "+Str(np1) Print ms = MilliSecs() For loop = 1 To lps d0# = 100000000.0 d1# = 100000000.0 np0.point = Null np1.point = Null For point.point = Each point d# = (point\x - camx) * (point\x - camx) If d<d0 d# = d + ((point\y - camy) * (point\y - camy)) If d<d0 d# = d + ((point\z - camz) * (point\z - camz)) If d<d0 d0 = d np0 = point ElseIf d<d1 d1 = d np1 = point End If ElseIf d<d1 d# = d + ((point\z - camz) * (point\z - camz)) If d<d1 d1 = d np1 = point End If End If ElseIf d<d1 d# = d + ((point\y - camy) * (point\y - camy)) If d<d1 d# = d + ((point\z - camz) * (point\z - camz)) If d<d1 d1 = d np1 = point End If End If End If Next Next Print "Bound + Squared search : "+(MilliSecs()-ms)+" ms" Print "Nearest point A : "+Str(np0) Print "Nearest point B : "+Str(np1) Print WaitKey() End |
| ||
| Cool! Some speed results: 99 points: 9 9 999 points: 90 73 4999 points: 457 338 ...So the second method gets faster when the pointcount increases. But it never gets slower! :) I guess that if you would sort the point positions (while retaining the index of the original point someway) spatially before searching you could develop even faster method as the sorting is one time only operation (that can be done "during loading"), and does not slow down anything during runtime. |
| ||
| A 'Balanced Kd Tree' would probably be the fastest solution, try doing a search for it :) |
| ||
| I would make a an array and for each element in the array, create an empty bank: pointres = 100 Dim PointMap(pointres,pointres,pointres) For x=0 to pointres for y=0 to pointres for z=0 to pointres PointMap(x,y,z)=CreateBank() next next next Then I would be able to place the camera coordinates into this position with relative ease: x=Entityx(camera)/pointres y=Entityy(camera)/pointres z=Entityz(camera)/pointres Then this returns a bank handle... the bank is a linear list of points in that zone. These could be entityhandles if you are using pivots, or just coordinates. then what we do is search -1 to 1 from the camera. For x-1 to x+1 for y-1 to y+1 for z-1 to z+1 compare points next next next This would probably mean you only ever need to compare 3 or 4 points at a time. It's stupidy fast no matter how many points you have in your clouds. The only thing that will slow it down is the density. You speed it up easily by using only a little more ram by increasing your pointres value. I did this back when I was doing occlusion. Not highly mathematical because I seriously doubt maths is needed here as they don't move: an elegent lookup table is the answer. |
| ||
| Hmm, a kind of hashtable with buckets. Clever! I've been playing around with hashtables and I think they are awesome. |
| ||
| Not a bad idea, robster! |
| ||
| Mustang, are you saying the the code I posted took 500 milliseconds to find the two closest points out of 5000 points? I find that hard to beleive. But if not milliseconds, then what do those scores represent? Perhaps a more pertinent question would be, are you running this on a 486? :-) Please post the test code. It's possible you did something to cause it to slow down. At the very least I'd then have something to play with and see if I can optimize it further. :-) |
| ||
| "Hmm, a kind of hashtable with buckets. Clever!" Hash table? I don't know where people came up with that term. It doesn't seem to fit. It's a 3D array, which contains pointers to a set of linked lists, or to banks of ram. A hash on the other hand is something where you take a set of data and squeeze it into a smaller space in such a way that you lose some accuracy but you can't reverse the process to get the original data back. While that is similar, I think that explaining this 3D array concept to someone as being a "hash table" where hashes are always explained in complicated difficult to understand ways with a lot of mathematics (as far as I've seen when looking them up), is a mistake. And heck, if you're gonna have banks of ram all of the same size (wasting memory), you might as well just use a 4D array instead of a 3D array. |
| ||
| Mustang, are you saying the the code I posted took 500 milliseconds to find the two closest points out of 5000 points? I find that hard to beleive. But if not milliseconds, then what do those scores represent? No, that was fredborgs code: Print "Bound + Squared search : "+(MilliSecs()-ms)+" ms" We had company "little xmas party" last evening which really started noon, so I copypasted just quicly Fredborgs readymade code and run it through for quick testing - I had no time to do comparable code from your version to test it too. And the PC was my work PC, AthlonXP2200. I guess I have to test yours and Rob's idea too but that means coding - and drinking and driving karts whole evening (karting first!) + Sauna was bit weary, and I can't think straight right now (10.45 pm next day) :P Luckily there's no hangover to speak of... |
| ||
| such luxury :D |
| ||
| Well, I've learned that hashing a value can be both a simple operation or a complex operation. It all depends on how good results you want. Hashing values in a basic hashtable means converting a keyvalue, be it a string or integer, to an integer value that fits inside a specific range(or a one dimensional array in this case). However, what I said was, "a KIND of hashtable". And by that I meant it was very similar to the hashtable solutions I've found on the web. The part where Rob divides the coordinates by the pointres value is a very simple BUT working way to hash the coordinate values. A more complex hashing method would try to spread the values over the whole array more efficient. I would also like to mention that .NET has a collection class called Hashtable that works this way. Maybe calling this operation "Hashing" is wrong, but it seems to me that most people do call it that, even on academic levels. |
   |