Re: [Algorithms] Raycasting - how fast does it get?

[<ca...@gm...>]

A general BSP tree requires a plane and an index per node (~20 bytes).
That's quite more than a kd-tree that only needs an axis, a distance
and an index (~8 bytes). If you already have polygons or hull planes
in memory, you just need two indices per node, but you then have more
memory accesses.

If you have short rays grids work pretty well. Charles describes an
interesting data structure for that:
http://www.cbloom.com/3d/techdocs/grid_sort_raycasts.txt

I like what he did at OddWorld: output a polygon soup and a bunch of
ray queries from your game, and run a contest to see who in your team
can complete the queries faster. I think it was Dave who won the
raycasting contest, so he may be able to give you some hints.

Also, as Pierre points out, the fastest way of tracing a ray is not
tracing it :-)

--=20
Ignacio Casta=F1o
ca...@gm...



On 10/31/07, Alen Ladavac <ale...@cr...> wrote:
> Ignacio wrote:
> > there's plenty of research in that area. [...]
> Thanks for the pointers.
>
> Will have to take some time look into it in more details, but just one
> note after a quick look... if I understand correctly, Havran's thesis
> uses the term "BSP" to refer to what he calls "axis-aligned" BSP
> trees, which would be, if I'm not mistaken, more like regular-split
> kd-trees. He doesn't even bother measuring the "polygon-aligned" BSPs,
> because, as he says, it limits it to polygonal scenes, which would be
> exactly what I need here. Perhaps that's not to be overlooked?
>
> > How's your ray distribution? What hardware are you targeting? Is it
> > used in game? or in off-line tools?
>
> It's for ray casts against collision geometry, used in-game, mostly by
> bullets and AI visibility tests. Hw would be contemporary PCs and
> consoles.
>
> Thanks,
> Alen
>
>