BSP Collision Detection

[WhatEver]

I have finaly implimented collision detection, and it works =D. I was very disapointed to find out that I had to use doubles to get the precision I needed so that a ray wouldn't leek through an edge of a polygon . Doubles are so big!

Now here's my question. In an average BSP tree for collision detection in Q3A, how many polygons are tested for collision? Q3A can draw 10,000 polygons on a scene and not slow down to a crawl; it doesn't test 10,000 polygons per frame too does it?

In my program I test to see if both origin and destination points are unequal before I clip the line to the plane and see if it's within the polygon. Are there other optimizations I should make to speed it up? Frankly, it's real slow.

Thanks

[jwatte]

The whole point of BSP trees is that they are hierarchical, and you only need about 15-20 tests to know where a point lies in the world (depending on tree balance etc). Testing a line as two points might help; if they're in different pieces of the world you know that the line spans volumes (which may or may not mean it's colliding).

You can also test a sphere with the line center as its center, and half the line length as its radius, and see which polygons collide with that sphere. Then run line intersect only against those polygons. Note that this will degrade as the line grows longer.

[WhatEver]

Ah, good. So it's normal that collision detection is slow, all you have to do is limit the times you use it.