Raycasting performance?
Author
Hello everybody!
I'm currently coding a simple raycasting engine (raycasting != raytracing, remember wolfenstein 3D?) and I was wondering how power hungry such an algorithm is.
Does anybody else got into raycasting? Actually, on a P4, it runs at 30fps in 1280x1024 and 60fps on a C2D. It's a high resolution raycaster (there's a ray for each width pixel) and I think it quite too much power hungry since wolf3D was running on a 33mhz in 320x240 (my engine runs at 1500fps in 320). What do you think?
I didn't calculated the complexity, but it should be O(n²) with n being the width resolution. My algorithm has some room for optimisation, like using look-up tables for sqrt & cos (should be able to get a 25% increase) but I still find it quite slow.
If anybody of you already tried coding a raycasting demo, it would be nice to share your experience. Any advice is already welcome.
Thx :).
Hmm, are you doing the shadowing via ray casting, or the whole rendering?
never minding, I'd suggest you to use the Kd-Tree for superiour intersection kalkulus on static scenes, or the Bounding Interval Hierarchy (Wächter, Keller) if you have animated stuff, or a combo of them both. Plus: Think about the Mutli Level Ray Tracing Algorithm, or in short, MLRTA (Reshetov and company).
For discussions on those topics, why not visit ompf (in my signature)?
never minding, I'd suggest you to use the Kd-Tree for superiour intersection kalkulus on static scenes, or the Bounding Interval Hierarchy (Wächter, Keller) if you have animated stuff, or a combo of them both. Plus: Think about the Mutli Level Ray Tracing Algorithm, or in short, MLRTA (Reshetov and company).
For discussions on those topics, why not visit ompf (in my signature)?
Author
Thank you for your reply, but, it's about raycasting, not raytracing. Even if it's a much simplier type of raytracing, I don't think dk-tree and other structure would help me since I'm just trying to render a 2d array into an orthogonal world with wall of the same length. Nothing really advanced as you could notice.
Thanks anyway.
Thanks anyway.
hmm, but on the other hand, you can use kd-trees/bih's in two dimensions, too.
As long as your looking for intersections between some rays and some objects (let's say 20 objects and more), spatial ordering would increase performance. And instead of creating 1024x1024 texels once at startup, you could recreate them on the fly and on demand.
Hmm, but I guess I got confused over the properly overused term "ray-casting". That's not your fault, it's simply that some say ray-casting for tracing only primo-rays, some say ray-casting for 2d-shadow-map-generators (where you "shoot" a ray for each texel, forward in one step, look if it intersects with your landscape or whatsoever) and so forth.
Sorry, I think I can't help you at the moment :(
As long as your looking for intersections between some rays and some objects (let's say 20 objects and more), spatial ordering would increase performance. And instead of creating 1024x1024 texels once at startup, you could recreate them on the fly and on demand.
Hmm, but I guess I got confused over the properly overused term "ray-casting". That's not your fault, it's simply that some say ray-casting for tracing only primo-rays, some say ray-casting for 2d-shadow-map-generators (where you "shoot" a ray for each texel, forward in one step, look if it intersects with your landscape or whatsoever) and so forth.
Sorry, I think I can't help you at the moment :(
Quote:Original post by MrHelmut
...like using look-up tables for sqrt & cos (should be able to get a 25% increase)...
I'm pretty certain raycasting doesn't need sqrt or cos at all.
Anyway, are you sure these are resposible for 25% CPU time? Also, lookup tables might not be the right way to optimize them. But first of all check whether you can eliminate sqrt and cos altogether.
Finally, why do you even worry about 30 FPS at 1280x1024? That's very smooth so don't waste time optimizing while you could be doing more interesting things.
If you're looking for the oldschool tricks used to optimize raycasting, I can suggest several books when I get home.
Consider things like fixed point vs floating point, using crude approximations of any calculations(a 2-3 pixel error isn't a big deal when you're one of the first psuedo3d games), and using inline assembly to get the maximum work per cycle. Also, the wolfenstein 3d source code is available from 'id software' if you want to try to take it apart.
Consider things like fixed point vs floating point, using crude approximations of any calculations(a 2-3 pixel error isn't a big deal when you're one of the first psuedo3d games), and using inline assembly to get the maximum work per cycle. Also, the wolfenstein 3d source code is available from 'id software' if you want to try to take it apart.
Keep in mind that the Wolfenstein engine had several major restrictions with regard to what it could render. You could only have walls at 90° angles, and all the floor and ceiling heights were the same. So essentially the levels were arranged on a regular 2D grid. This allows for all sorts of optimized calculations. It becomes more like "scanning" than raycasting.
I believe Andre Lamothe talks about and includes such a raycaster/scanner with similar restrictions in his old book Tricks of the Game Programming Gurus. It's actually pretty neat.
I believe Andre Lamothe talks about and includes such a raycaster/scanner with similar restrictions in his old book Tricks of the Game Programming Gurus. It's actually pretty neat.
Quote:Original post by Extrarius
... optimize ... things like fixed point vs floating point
nowadays CPU's are faster in fp-math than integer math, at least for maths related things (think of sse) ;)
[Edited by - greenhybrid on June 11, 2007 12:23:23 PM]
Quote:Original post by greenhybridIs SSE floating point faster than SSSE3 fixed point? Could be, but I somehow doubt it. Either way, architecture-specific optimizations always run the risk of no longer being optimizations when the architecture changes.Quote:Original post by Extrarius
... optimize ... things like fixed point vs floating point
nowadays CPU's are faster in fp-math than integer math, at least for maths related things (think of sse) ;)
I d/l the wolf3d source just for fun and noticed that Carmack himself says that these days (being when they released the source) raycasting was not the fastest way to draw a 3d environment but it was simpler to implement.
If I remeber correctly, "Michael Abrash's Graphics Programming Black Book"(ISBN 1576101746) gets a textured triangle render down to 9 cycles per pixel on a pentium. It might be possible to get even lower than that on today's hardware using SIMD instruction sets.
If you haven't seen it already Permadi Raycasting tutorial might be of interest.
It was many years ago that I used it for my own wolf3D/raycasting demo, but I see to remember once i'd implemented the basic algorithm plenty of oppertunities for optimsations became apparent. I'm pretty sure it was possible to remove nearly all the trig etc, but sadly it was too long ago to remember.
Perhaps you should post some code, it would give poeple the oppertunity to make specific recommendations for optimsations.
It was many years ago that I used it for my own wolf3D/raycasting demo, but I see to remember once i'd implemented the basic algorithm plenty of oppertunities for optimsations became apparent. I'm pretty sure it was possible to remove nearly all the trig etc, but sadly it was too long ago to remember.
Perhaps you should post some code, it would give poeple the oppertunity to make specific recommendations for optimsations.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
