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]
|Revisiting -> (Finding 2D Line intersections)|
|cbx||Recently 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]|
|Eric Coleman||I'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.|
|cbx||Actually 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.
|Eric Coleman||If 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 Loach||I'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|