Quick Hit-Testing
-
For a 2-dimensional plane, I've implemented a function for determining whether a circle intersects a ray. Suppose there is one ray and many, many circles. How would I reduce the number of tests by selecting the circles that are certain or likely to be hit?
ROFLOLMFAO
-
For a 2-dimensional plane, I've implemented a function for determining whether a circle intersects a ray. Suppose there is one ray and many, many circles. How would I reduce the number of tests by selecting the circles that are certain or likely to be hit?
ROFLOLMFAO
Hi, lots can be done depending on circumstances. SCHEME 1 Assuming you are only interested in a finite and rectangular part of the 2D plane, you could divide the area in a number of smaller rectangles. Say 16*16 rectangles. Now a ray would intersect only some of these rectangles, so we are only interested in those circles that partially cover those rectangles. Assuming your circles are static, that can be precalculated and stored: for each record, you can hold a list of crossing circles. So now it is a matter of finding the rectangles crossed, then scanning the circles listed for these rectangles. WARNING: things must be organized in such a way that the same circle is not tested again for different rectangles; a boolean flag might help. SCHEME 2 Assuming (most of) the circles are fairly small with respect to the entire area, if the ray does not cross the entire area, but is restricted to some X-range (for a steep ray) or some Y-range, one could easily eliminate all circles that lie fully outside said X or Y-range. Hope this helps.
Luc Pattyn [My Articles] [Forum Guidelines]
-
Hi, lots can be done depending on circumstances. SCHEME 1 Assuming you are only interested in a finite and rectangular part of the 2D plane, you could divide the area in a number of smaller rectangles. Say 16*16 rectangles. Now a ray would intersect only some of these rectangles, so we are only interested in those circles that partially cover those rectangles. Assuming your circles are static, that can be precalculated and stored: for each record, you can hold a list of crossing circles. So now it is a matter of finding the rectangles crossed, then scanning the circles listed for these rectangles. WARNING: things must be organized in such a way that the same circle is not tested again for different rectangles; a boolean flag might help. SCHEME 2 Assuming (most of) the circles are fairly small with respect to the entire area, if the ray does not cross the entire area, but is restricted to some X-range (for a steep ray) or some Y-range, one could easily eliminate all circles that lie fully outside said X or Y-range. Hope this helps.
Luc Pattyn [My Articles] [Forum Guidelines]
Thank you for your input. I have already thought about SCHEME 1. The problem is, the circles are not static. They move around. They represent players on a map, and the line represents the path that a bullet takes. After some more thought about the problem, I realized that while we can't elimenate unnecessary tests altogether, we can cut out a good portion of the tests in some circumstances. This might involve maintaining certain properties before the actual hit testing occurs (like how order is maintained for a balanced search tree before a search is performed). I will outline my approach below (and you can judge my methods):
- A rectangular plane (named: MAP) is created which everything else will be relative to.
- MAP is subdivided into regions. These regions are squares. They contain references to circles. The length and width of the region are set such that it is not smaller than the largest diameter of a circle. These regions are addressed by indices. The indices are directly related to the region's offset from the origin on MAP.
- A circle (named: CHAR1) is created on MAP with a radius no greater than half a region's length. (This is important later on when we try to determine what regions get tested.)
- CHAR1 is added to the region that it is in. (The circle's boundaries may cross into one or more other regions.) Its region will now have a reference to it.
- CHAR1 moves and it crosses its region's boundaries. It has crossed into another region, so the region's references to CHAR1 are deleted, and the current region CHAR1 resides in creates a reference to CHAR1. (Regions are synchronized with the circle's location.)
- Another circle (named: CHAR2) is created on MAP. It fires a projectile that follows a line (named: PATH).
- Now here is the tricky part (I don't even know if it works.):
- With PATH defined by y = mx + b, create 2 more lines that are parrallel to PATH and are separated by an a perpendicular distance that is equal to the greatest possible radius of a circle (a limit which is artificially imposed). The lines are created on with sides of PATH. The three lines intersect all the regions that should be tested. (Hit-testing with squares should be much more efficient than hit testing with circles.)
- So now that we have 3 lines, we just plugin values for X in increments of the width of the region starting from the position of CHAR2. We get coordinates that hit every region that needs to be tested. Suppose the indices of the r
-
Thank you for your input. I have already thought about SCHEME 1. The problem is, the circles are not static. They move around. They represent players on a map, and the line represents the path that a bullet takes. After some more thought about the problem, I realized that while we can't elimenate unnecessary tests altogether, we can cut out a good portion of the tests in some circumstances. This might involve maintaining certain properties before the actual hit testing occurs (like how order is maintained for a balanced search tree before a search is performed). I will outline my approach below (and you can judge my methods):
- A rectangular plane (named: MAP) is created which everything else will be relative to.
- MAP is subdivided into regions. These regions are squares. They contain references to circles. The length and width of the region are set such that it is not smaller than the largest diameter of a circle. These regions are addressed by indices. The indices are directly related to the region's offset from the origin on MAP.
- A circle (named: CHAR1) is created on MAP with a radius no greater than half a region's length. (This is important later on when we try to determine what regions get tested.)
- CHAR1 is added to the region that it is in. (The circle's boundaries may cross into one or more other regions.) Its region will now have a reference to it.
- CHAR1 moves and it crosses its region's boundaries. It has crossed into another region, so the region's references to CHAR1 are deleted, and the current region CHAR1 resides in creates a reference to CHAR1. (Regions are synchronized with the circle's location.)
- Another circle (named: CHAR2) is created on MAP. It fires a projectile that follows a line (named: PATH).
- Now here is the tricky part (I don't even know if it works.):
- With PATH defined by y = mx + b, create 2 more lines that are parrallel to PATH and are separated by an a perpendicular distance that is equal to the greatest possible radius of a circle (a limit which is artificially imposed). The lines are created on with sides of PATH. The three lines intersect all the regions that should be tested. (Hit-testing with squares should be much more efficient than hit testing with circles.)
- So now that we have 3 lines, we just plugin values for X in increments of the width of the region starting from the position of CHAR2. We get coordinates that hit every region that needs to be tested. Suppose the indices of the r
Hi, this sounds reasonable, provided: 1) there are many CHAR1 (otherwise it all does not matter) 2) the greatest possible radius of a circle is small with respect to MAP size I am not sure about your integer division stuff; the line y = mx + b seems to imply floating-point: m and b wont be integers. BTW: the general equation for a line is a*x + b*y + c = 0 which is symmetric in x and y, resulting in no trouble when the line is vertical (if you dont like having 3 coefficients, you can divide them all by c provided c is non-zero). Further thought: there is a useful method Region.IsVisible() you might apply it to a region that is a (non-orthogonal) rectangle starting at the shooter, pointing in the direction he is shooting, and having a width of twice "the greatest possible radius of a circle" and a length sufficient to cross the border of MAP. Using it you would mean you do not need your squares after all, simply test each circle's center against it (very simple, probably fast too). As a side effect you could shoot circles that are off-screen too (by making the rectangle length quite large) ! :)
Luc Pattyn [My Articles] [Forum Guidelines]
-
Hi, this sounds reasonable, provided: 1) there are many CHAR1 (otherwise it all does not matter) 2) the greatest possible radius of a circle is small with respect to MAP size I am not sure about your integer division stuff; the line y = mx + b seems to imply floating-point: m and b wont be integers. BTW: the general equation for a line is a*x + b*y + c = 0 which is symmetric in x and y, resulting in no trouble when the line is vertical (if you dont like having 3 coefficients, you can divide them all by c provided c is non-zero). Further thought: there is a useful method Region.IsVisible() you might apply it to a region that is a (non-orthogonal) rectangle starting at the shooter, pointing in the direction he is shooting, and having a width of twice "the greatest possible radius of a circle" and a length sufficient to cross the border of MAP. Using it you would mean you do not need your squares after all, simply test each circle's center against it (very simple, probably fast too). As a side effect you could shoot circles that are off-screen too (by making the rectangle length quite large) ! :)
Luc Pattyn [My Articles] [Forum Guidelines]
Thanks for your responses. I'll try to work with different approaches to fidn the best one. (It's a Windows Presentation Foundation application by the way. It's also network-oriented. The game engine runs on the server.) As for the integer division stuff, I'll probably cast the Double to an Int64, strip the fractional part, or round down after division — whichever is more efficient.
ROFLOLMFAO
-
Thank you for your input. I have already thought about SCHEME 1. The problem is, the circles are not static. They move around. They represent players on a map, and the line represents the path that a bullet takes. After some more thought about the problem, I realized that while we can't elimenate unnecessary tests altogether, we can cut out a good portion of the tests in some circumstances. This might involve maintaining certain properties before the actual hit testing occurs (like how order is maintained for a balanced search tree before a search is performed). I will outline my approach below (and you can judge my methods):
- A rectangular plane (named: MAP) is created which everything else will be relative to.
- MAP is subdivided into regions. These regions are squares. They contain references to circles. The length and width of the region are set such that it is not smaller than the largest diameter of a circle. These regions are addressed by indices. The indices are directly related to the region's offset from the origin on MAP.
- A circle (named: CHAR1) is created on MAP with a radius no greater than half a region's length. (This is important later on when we try to determine what regions get tested.)
- CHAR1 is added to the region that it is in. (The circle's boundaries may cross into one or more other regions.) Its region will now have a reference to it.
- CHAR1 moves and it crosses its region's boundaries. It has crossed into another region, so the region's references to CHAR1 are deleted, and the current region CHAR1 resides in creates a reference to CHAR1. (Regions are synchronized with the circle's location.)
- Another circle (named: CHAR2) is created on MAP. It fires a projectile that follows a line (named: PATH).
- Now here is the tricky part (I don't even know if it works.):
- With PATH defined by y = mx + b, create 2 more lines that are parrallel to PATH and are separated by an a perpendicular distance that is equal to the greatest possible radius of a circle (a limit which is artificially imposed). The lines are created on with sides of PATH. The three lines intersect all the regions that should be tested. (Hit-testing with squares should be much more efficient than hit testing with circles.)
- So now that we have 3 lines, we just plugin values for X in increments of the width of the region starting from the position of CHAR2. We get coordinates that hit every region that needs to be tested. Suppose the indices of the r
Just to ensure that you know that testing for intersection with circles is reasonably inexpensive: if floating point, normalise equation of line ax + by + c = 0 so that a^2+b^2=1 then the test for intersection with circle centre (x0,y0) radius r0 is abs(a*x0 + b*y0 + c) <= r0 If integers, then there are several ways, but (a*x0 + b*y0 +c)^2 < (a^2+b^2)*r0^2 is reasonably cheap (4 multiplications and 2 additions) assuming that r0^2 and (a^2+b^2) is precomputed. You may have to be careful about overflows. With modern GFLOP processors, you can test a lot of circles in real time. It all depends on how many circles you have and how they are organised.
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
-
Just to ensure that you know that testing for intersection with circles is reasonably inexpensive: if floating point, normalise equation of line ax + by + c = 0 so that a^2+b^2=1 then the test for intersection with circle centre (x0,y0) radius r0 is abs(a*x0 + b*y0 + c) <= r0 If integers, then there are several ways, but (a*x0 + b*y0 +c)^2 < (a^2+b^2)*r0^2 is reasonably cheap (4 multiplications and 2 additions) assuming that r0^2 and (a^2+b^2) is precomputed. You may have to be careful about overflows. With modern GFLOP processors, you can test a lot of circles in real time. It all depends on how many circles you have and how they are organised.
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
Hi, this is great, and mathematically correct. When all coordinates use no more than 14 bits (that is 16000 pixels), then everything can be calculated in 32-bit signed integer arithmetic without risking overflows. Seems much better than the sorted-squares stuff... :)
Luc Pattyn [My Articles] [Forum Guidelines]
-
Just to ensure that you know that testing for intersection with circles is reasonably inexpensive: if floating point, normalise equation of line ax + by + c = 0 so that a^2+b^2=1 then the test for intersection with circle centre (x0,y0) radius r0 is abs(a*x0 + b*y0 + c) <= r0 If integers, then there are several ways, but (a*x0 + b*y0 +c)^2 < (a^2+b^2)*r0^2 is reasonably cheap (4 multiplications and 2 additions) assuming that r0^2 and (a^2+b^2) is precomputed. You may have to be careful about overflows. With modern GFLOP processors, you can test a lot of circles in real time. It all depends on how many circles you have and how they are organised.
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
Thanks. I'm guessing this goes back to the "l × c"* approach — comparing every line with every circle. If that turns out to be faster, I'll implement that too (you gotta love interfaces and virtual methods!). By the way, everything is done using the Double type. (It's the type that Windows Presentation Foundation works with.) * Represents the number of comparisons that needs to be made based on the number of lines and circles. The number of lines never exceeds the number of circles, so a lower bound would be 0 tests for no activity, and Math.Pow(c, 2) for the upper bound (when everyone is firing their uzis at once).
ROFLOLMFAO
-
Hi, this is great, and mathematically correct. When all coordinates use no more than 14 bits (that is 16000 pixels), then everything can be calculated in 32-bit signed integer arithmetic without risking overflows. Seems much better than the sorted-squares stuff... :)
Luc Pattyn [My Articles] [Forum Guidelines]
Hmm… I'd have to agree that dividing MAP into regions would be horribly complex (I haven't even implemented the code yet), but then again, I'm restricted to floating-point math, so I can't take the integer math approach. I'm also quite skeptical about testing every circle. Maybe I should make it more scalable, and allow automatic selection of algorithms based on certain conditions. In the end, we converge towards an optimal solution, but we never reach it. :)
ROFLOLMFAO
-
Hmm… I'd have to agree that dividing MAP into regions would be horribly complex (I haven't even implemented the code yet), but then again, I'm restricted to floating-point math, so I can't take the integer math approach. I'm also quite skeptical about testing every circle. Maybe I should make it more scalable, and allow automatic selection of algorithms based on certain conditions. In the end, we converge towards an optimal solution, but we never reach it. :)
ROFLOLMFAO
Hi, some more thoughts: 1. Whatever was said about integers can be done in float as well. 2. how many circles are there ? thousands ? and how many times per second do you need the hit testing ? a modern CPU executes 1 billion instr/sec ! 3. in my experience, reflecting before implementing is good (it allows for wise initial choices), but optimizing things that dont exist yet is not; optimization must be based on observations and measurements. Good luck !
Luc Pattyn [My Articles] [Forum Guidelines]
-
For a 2-dimensional plane, I've implemented a function for determining whether a circle intersects a ray. Suppose there is one ray and many, many circles. How would I reduce the number of tests by selecting the circles that are certain or likely to be hit?
ROFLOLMFAO
If a line intersects a circle then it also intersects a square centered at the same location and with a side length equal to the diameter of the circle. That fact could be use as the first stage in your hit detection.
Steve
-
Hi, some more thoughts: 1. Whatever was said about integers can be done in float as well. 2. how many circles are there ? thousands ? and how many times per second do you need the hit testing ? a modern CPU executes 1 billion instr/sec ! 3. in my experience, reflecting before implementing is good (it allows for wise initial choices), but optimizing things that dont exist yet is not; optimization must be based on observations and measurements. Good luck !
Luc Pattyn [My Articles] [Forum Guidelines]
I'll take every idea into consideration. It is a testing platform for a bigger project after all, and a better idea can't be ignored! Thank you for all your input! :D
ROFLOLMFAO
-
If a line intersects a circle then it also intersects a square centered at the same location and with a side length equal to the diameter of the circle. That fact could be use as the first stage in your hit detection.
Steve
I can't see how to test for intersection with a square that is cheaper than testing for intersection with a circle. The best methods I can come up with are actually harder to test with a square than a circle.
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
-
I can't see how to test for intersection with a square that is cheaper than testing for intersection with a circle. The best methods I can come up with are actually harder to test with a square than a circle.
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
I haven't seen the algorithms being used but I don't find it hard to imagine that an algorithm based on the Cohen-Sutherland line clipping algorithm, for example, could speed things up. Also lines of code need not mean slower code.
Steve
-
I haven't seen the algorithms being used but I don't find it hard to imagine that an algorithm based on the Cohen-Sutherland line clipping algorithm, for example, could speed things up. Also lines of code need not mean slower code.
Steve
Thanks for the link Steve - now I see where you are coming from. Guess there is no right answer (particularly without knowing all the problem), for finite line segments algorithms like you propose may be the best (although the answer will depend on the level of hardware support available), for infinite line segments the simple testing earlier in the thread could be promising. This looks like a semi-infinite problem so maybe a combination will turn out to be the best.
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
-
For a 2-dimensional plane, I've implemented a function for determining whether a circle intersects a ray. Suppose there is one ray and many, many circles. How would I reduce the number of tests by selecting the circles that are certain or likely to be hit?
ROFLOLMFAO
I've never done any gaming programming, so my idea may be way off, but... I assume that the circles are objects that maintain data about themselves. Could you have the circle objects keep track of what ray would intersect them? That way all the calculations would be done at the time of movement, and at the time the gun is fired, all that needs to be done is to check each circle to see if the shot qualifies as a hit.
Roy.