Download Attachment: [url="http://vbgamer.strategon.com/msgboard/uploaded/cbx/200381021134_RayRect Intersect Method.zip"][img]icon_paperclip.gif[/img]RayRect Intersect Method.zip[/url]
18.05 KB">
Revisiting -> (Finding 2D Line intersections)
cbxRecently I have been tinkering with Quad BSP Trees. See my web site for a number of visual example apps. [url]www.createdbyx.com[/url] The Reason I have been playing around with Quad BSP Trees, is to better under stand how DOOM determined what walls it had to draw on screen. That and my interest in the Doom.NET project [url]http://www.gotdotnet.com/Community/Workspaces/Workspace.aspx?id=f1764f94-3389-4c69-8b2e-3d6e8b9df0f1[/url] I have just wrote a simple vb.net app that I would like people to try out and pick apart to determin if it really is working at the speed that it is. As far as I can tell it's un-testably fast. Which is why I am posting it for people to pick apard and find anything wrong with it. The source is written in vb.net and contains the *.exe. To operate the app ... Left mouse button sets ray start right mouse button sets ray end "T" starts the time recorder "D" displays the average calculation time info etc. Is this method the fasted possible? Is it 100% acurate? Am I missing something? Please let me know! Download Attachment: [url="http://vbgamer.strategon.com/msgboard/uploaded/cbx/200381021134_RayRect Intersect Method.zip"][img]icon_paperclip.gif[/img]RayRect Intersect Method.zip[/url]
18.05 KB
Eric ColemanI'm not sure that a recursive algorithm is the fastest for line-rectangle intersections. I'm no expert on the fastest method, but I would imagine that you could just do a line-line intersection test with the 2 diangonals of the rectangle, (after the RayOutOfBounds and RayPointsInsideBounds tests). The line intersection will either return 1 or 2 points, so you just check those two points to see if they are inside the box with the RayPointsInsideBounds function.
cbxActually I have tested it and I have only been able to get it up to 21 recursions. That's what the numbers are showing in the windows title bar. Also you only start getting large recursions at the very corners of the rect, because the ray is being split in two etc. I decided to try and take an "if" statement approach rather then a multiplication or division approach, to increase speed. I am betting that my method is much faster then the Line-line intersect method I posted eariler (Finding 2D Line intersections) [url]http://vbgamer.strategon.com/msgboard/topic.asp?TOPIC_ID=51[/url] Simply because there is like 10 multiplications and 2 to 4 divisions being made. Where as my methods only have 2 division statments. On the topic of speed I could also increase the speed in three ways.
  • First of all the app is running in debug mode with no optimizations. When I change it to release and enable optimizations it may execute slightly faster.
  • Second I could eliminate the recursive calls and replace it with a looping statment. This would also prevent any possible stack overflow errors.
  • Third I could try to resolve the issue of ray not even touching the rect. For example my method will start a recursive call even if the ray misses the rect .... View the picture to view an example. Download Attachment: [url="http://vbgamer.strategon.com/msgboard/uploaded/cbx/200381113755_Ray miss rect.gif"][img]icon_paperclip.gif[/img]Ray miss rect.gif[/url]
    2.58 KB
  • I could set the Resolution parameter of the CrossIntersectCheck method to a higher value but of cource the method would no longer be as acurate in finding collitions.
There was another way I could increase speed but I can't recall what i was ... (has to do with how a ray interacts with a quad BSP tree.)
Eric ColemanIf you're worried about the 3 divide operations from reducing a matrix to find the point of intersection of 2 lines, then your method is 2 divides per iteration. On the average, your current method will have more math operations than the one posted at gamedev.net. Of course, you shouldn't be trying to tweak such a small function. On the overall scale of things, having a really fast line intersection function is insignificant to actually programming the game. You should spend your time where its needed. I doubt this line intersection function would be the bottleneck for your game. Personally I would go with the method presented at gamedev.net. Its easier to understand (for me at least), and its smaller and thus easier to maintain. Use whichever function you're more comfortable with and then move on.
Rob LoachI'm not exactly sure what you're looking for, but I wrote a function a while ago to find the intersect among two given lines using Kramer's math rule. You can get it here: http://planetsourcecode.com/vb/scripts/ShowCode.asp?txtCodeId=41007&lngWId=1