Forum archive

Build - a raycaster?

Return to forum index

Grimasso at 2009-10-26 18:55
Hello everybody,

I'm currently trying to implement a small raycasting engine on my mobile phone. I read a lot of raycasting stuff during the last hours and read, that Build also was/is a raycaster.
I just wondered about this, because it can do a lot of things classic raycaster aren't capable of:
- Floors of different height
- Walls at any angle
- Slopes
- No gridlocking of walls
- ... even more

We can put this together to two main capabilities classic raycasters have not:
- "Complex walls" (Walls at any angle at any point of the map)
- Variable heights

@Ken and everybody who knows:
How do you determine if a wall is hit by a ray? In classic gridlocked-wall raycasters theres a trick to only check the ray in steps on the grid coordinates to keep it faster.
Whats the trick in build?
My second major question: With variable floor heights there can be multiple walls per column to render.
How do you keep this fast? If I got it right, the advantage of a raycaster is that theres only one check needed per screen column (because theres always just 1 wall).
Whats the trick behind this? Only solution coming to my mind is to implement a rayTRACER-like checking of each pixel, but it would be too slow I guess.

Greetings
Awesoken at 2009-10-27 07:32
Re: Build - a raycaster?
Build does NOT use raycasting. Here is an earlier thread where I write about that myth:
http://www.jonof.id.au/forum/index.php?topic=1584.msg10179#msg10179

If you want to know how Build really works, then I suggest you search these (JonoF's) forums. Try using "build visibility" or "build render" as search strings. Any posts written by me will be accurate, since I am the author of the engine.
Jinroh at 2009-10-28 12:03
Grimasso said at 2009-10-26 18:55
Hello everybody,

I'm currently trying to implement a small raycasting engine on my mobile phone. I read a lot of raycasting stuff during the last hours and read, that Build also was/is a raycaster.
If you want to write a 3D Engine for your mobile phone to render scenes comparable to BUILD I would suggest that you do not use Raycasting. Unless you write a raycaster in 100% ARM# Assembly (Or whatever your phone's processor may be) I would suggest that you use a BSP based system instead.

The problem here with raycasters/raytracers is the first hit.

The first hit is usually costly without some kind of optimization it's like On^2 or something but it's not very efficient because you may end up traversing the whole list of walls that you may hit.

BSPs or other PVS style algorithms allow you to know what walls are visible and which will be hit. Even if you use a raycaster/raytracer in the Sector style you'll still have at least 2 or more walls (for subsectors) that you may hit.

Depending on the complex nature of your level this could be a lot of walls. BSP (or others) will be able to give you a more efficient picture for walls to be rendered. Yeah, you won't be able to have (easily) dynamic worlds like BUILD, but it would be a whole lot faster for Mobile Phones (Assuming that the average mobile phone is comparable to the GBA).

Even if you are using a super phone like an iPhone you can use the native GPU hardware to push polygons which would be more efficient than pushing one column/span at a time.

Not trying to discourage you, but just letting you think about what you're getting into. Plus there are tons of BSP friendly formats and data you can use for testing like the FreeDoom levels.

Just my 2 cents but I feel it should be mentioned.

http://www.bspquakeeditor.com/images/bsp95gltrans2.gif
Edited by Jinroh at 2009-10-28 12:08
Grimasso at 2009-10-28 18:13
Thanks for your advice, I thought about poly rendering but most tutorials give the impression as if painting down a raycaster-wall is much faster (actually most say, its the fastest known way to "3d/2.5d" ) than rendering a "real" polygon. I have no clue, but I will try both if I got enough time :)
Jinroh at 2009-10-29 13:54
Grimasso said at 2009-10-28 18:13
Thanks for your advice, I thought about poly rendering but most tutorials give the impression as if painting down a raycaster-wall is much faster (actually most say, its the fastest known way to "3d/2.5d" ) than rendering a "real" polygon. I have no clue, but I will try both if I got enough time :)
Regardless of what approach you choose, this article by the popular Jacco Bikker may give you some insights on optimizations.
http://www.flipcode.com/archives/3D_Graphics_on_Mobile_Devices-Part_1_Voxel_Graphics.shtml

Could you give us some quotes from these tutorials to explain the logic of the authors? Not saying you're wrong, just from the way that video memory is set up you can optimize drawing Horizontally much more than drawing vertically.

Since video memory is contiguous drawing horizontally only requires you to increase the offset by one for each neighboring pixel to the right.

Drawing down usually requires you to increase video memory by screenWidth or screenPitch.

You can rasterize and draw polygons as a series of horizontal lines which can be filled using a simple Memset to fill the entire line. Since you're doing mobile phone dev you probably will be using Java? I can't remember too much of Java as I've not used it in several years, so I'm not sure if it has something like Memset but I'm sure it can do a similar optimization.

Not trying to be a pompous ass here, just in my logic it should be faster to rasterize a polygons than draw a bunch of vertical lines down a raycaster so I'm curious in hearing what the article authors say.
0xC0DE at 2009-10-29 20:41
Jinroh said at 2009-10-29 13:54
Grimasso said at 2009-10-28 18:13
Thanks for your advice, I thought about poly rendering but most tutorials give the impression as if painting down a raycaster-wall is much faster (actually most say, its the fastest known way to "3d/2.5d" ) than rendering a "real" polygon. I have no clue, but I will try both if I got enough time :)
Regardless of what approach you choose, this article by the popular Jacco Bikker may give you some insights on optimizations.
http://www.flipcode.com/archives/3D_Graphics_on_Mobile_Devices-Part_1_Voxel_Graphics.shtml

Could you give us some quotes from these tutorials to explain the logic of the authors? Not saying you're wrong, just from the way that video memory is set up you can optimize drawing Horizontally much more than drawing vertically.

Since video memory is contiguous drawing horizontally only requires you to increase the offset by one for each neighboring pixel to the right.

Drawing down usually requires you to increase video memory by screenWidth or screenPitch.

You can rasterize and draw polygons as a series of horizontal lines which can be filled using a simple Memset to fill the entire line. Since you're doing mobile phone dev you probably will be using Java? I can't remember too much of Java as I've not used it in several years, so I'm not sure if it has something like Memset but I'm sure it can do a similar optimization.

Not trying to be a pompous ass here, just in my logic it should be faster to rasterize a polygons than draw a bunch of vertical lines down a raycaster so I'm curious in hearing what the article authors say.
Well, it’s fairly simple approach; use the hardware to rotate your screen :)

At least that’s what all the fancy programmers do on (handheld) consoles. For example,
if you have a voxel-heightmap-engine (or even a wolf3D raycast engine) you want to
draw a lot of vertical lines.

For gba, the best approach is to go to mode 5 (which is 160x120, normal res is 240x160).
Draw all the lines horizontal, then rotate the screen and stretch it (120*2 = 240, and the
width which now becomes the height is already 160 pixels).

This is really fast because :
1.) Rotation of the screen is hardware accelerated
2.) Pointers to your data stay the same (heightmap and texture map) for the whole line
3.) Horizontal line drawing (which is indeed faster then vertical drawing)

Edited by Hugo Smits at 2009-10-29 20:43
Jinroh at 2009-10-30 01:43
Hugo Smits said at 2009-10-29 20:41
Well, it’s fairly simple approach; use the hardware to rotate your screen :)

At least that’s what all the fancy programmers do on (handheld) consoles. For example,
if you have a voxel-heightmap-engine (or even a wolf3D raycast engine) you want to
draw a lot of vertical lines.

For gba, the best approach is to go to mode 5 (which is 160x120, normal res is 240x160).
Draw all the lines horizontal, then rotate the screen and stretch it (120*2 = 240, and the
width which now becomes the height is already 160 pixels).

This is really fast because :
1.) Rotation of the screen is hardware accelerated
2.) Pointers to your data stay the same (heightmap and texture map) for the whole line
3.) Horizontal line drawing (which is indeed faster then vertical drawing)
Thanks for that enlightening optimization Hugo. ^_^ Had no idea handheld coders did that but it makes sense. Especially on the GBA where it's Rotation and Scaling Hardware is none to shabby. ^o^
Edited by Jinroh at 2009-10-30 01:46
CaimX86 at 2009-10-30 20:22
Hi everybody, It's my first time posting here!
For gba, the best approach is to go to mode 5 (which is 160x120, normal res is 240x160).
Draw all the lines horizontal, then rotate the screen and stretch it (120*2 = 240, and the
width which now becomes the height is already 160 pixels).
I liked this approach. But if I understand right, you said: go to mode 5 -> Draw -> Multiple and then... what? You need go back to "NORMAL MODE"?

I'm mean: You need change gba screen mode for rotation? But isn't this slow?
0xC0DE at 2009-10-30 22:59
CaimX86 said at 2009-10-30 20:22
Hi everybody, It's my first time posting here!
For gba, the best approach is to go to mode 5 (which is 160x120, normal res is 240x160).
Draw all the lines horizontal, then rotate the screen and stretch it (120*2 = 240, and the
width which now becomes the height is already 160 pixels).
I liked this approach. But if I understand right, you said: go to mode 5 -> Draw -> Multiple and then... what? You need go back to "NORMAL MODE"?

I'm mean: You need change gba screen mode for rotation? But isn't this slow?
no, you can't change mode’s in between (because then the screen gets scrambled, you need to
redraw your stuff for the new mode). I was merely pointing out that the normal resolution of a GBA screen
is 240x160 pixels, and that mode 5 has a resolution of 120x160 (so it’s a lot smaller).

Because of this you need to stretch the screen (so that the 120 pixels of mode 5 become 240 pixels) to get a full-screen effect.
CaimX86 at 2009-10-30 23:31
Hugo Smits said at 2009-10-30 22:59
CaimX86 said at 2009-10-30 20:22
Hi everybody, It's my first time posting here!
For gba, the best approach is to go to mode 5 (which is 160x120, normal res is 240x160).
Draw all the lines horizontal, then rotate the screen and stretch it (120*2 = 240, and the
width which now becomes the height is already 160 pixels).
I liked this approach. But if I understand right, you said: go to mode 5 -> Draw -> Multiple and then... what? You need go back to "NORMAL MODE"?

I'm mean: You need change gba screen mode for rotation? But isn't this slow?
no, you can't change mode’s in between (because then the screen gets scrambled, you need to
redraw your stuff for the new mode). I was merely pointing out that the normal resolution of a GBA screen
is 240x160 pixels, and that mode 5 has a resolution of 120x160 (so it’s a lot smaller).

Because of this you need to stretch the screen (so that the 120 pixels of mode 5 become 240 pixels) to get a full-screen effect.
Sorry If this appear like a dumb question, but I really want understanding your point.

So, I understand all the rotation thing, I just have a little doubt about Screen Mode.

You start at Mode 5 -> Rotate -> go to "Normal Mode" -> Draw? That's it?
0xC0DE at 2009-10-31 20:20
CaimX86 said at 2009-10-30 23:31
Hugo Smits said at 2009-10-30 22:59
CaimX86 said at 2009-10-30 20:22
Hi everybody, It's my first time posting here!
For gba, the best approach is to go to mode 5 (which is 160x120, normal res is 240x160).
Draw all the lines horizontal, then rotate the screen and stretch it (120*2 = 240, and the
width which now becomes the height is already 160 pixels).
I liked this approach. But if I understand right, you said: go to mode 5 -> Draw -> Multiple and then... what? You need go back to "NORMAL MODE"?

I'm mean: You need change gba screen mode for rotation? But isn't this slow?
no, you can't change mode’s in between (because then the screen gets scrambled, you need to
redraw your stuff for the new mode). I was merely pointing out that the normal resolution of a GBA screen
is 240x160 pixels, and that mode 5 has a resolution of 120x160 (so it’s a lot smaller).

Because of this you need to stretch the screen (so that the 120 pixels of mode 5 become 240 pixels) to get a full-screen effect.
Sorry If this appear like a dumb question, but I really want understanding your point.

So, I understand all the rotation thing, I just have a little doubt about Screen Mode.

You start at Mode 5 -> Rotate -> go to "Normal Mode" -> Draw? That's it?
You can draw whenever you like, if you rotate the screen that’s just for appearance,
it’s not like the VRAM bank actually rotates as well. And there is no ‘normal mode’ like
I said before; it’s just the resolution gap. A GBA screen is 240x160, mode5 resolution
is 120x160. So it’s (a lot) smaller and that doesn’t look nice, that’s why you need to stretch.
CaimX86 at 2009-10-31 23:01
Hugo Smits said at 2009-10-31 20:20
CaimX86 said at 2009-10-30 23:31
Hugo Smits said at 2009-10-30 22:59
CaimX86 said at 2009-10-30 20:22
Hi everybody, It's my first time posting here!
For gba, the best approach is to go to mode 5 (which is 160x120, normal res is 240x160).
Draw all the lines horizontal, then rotate the screen and stretch it (120*2 = 240, and the
width which now becomes the height is already 160 pixels).
I liked this approach. But if I understand right, you said: go to mode 5 -> Draw -> Multiple and then... what? You need go back to "NORMAL MODE"?

I'm mean: You need change gba screen mode for rotation? But isn't this slow?
no, you can't change mode’s in between (because then the screen gets scrambled, you need to
redraw your stuff for the new mode). I was merely pointing out that the normal resolution of a GBA screen
is 240x160 pixels, and that mode 5 has a resolution of 120x160 (so it’s a lot smaller).

Because of this you need to stretch the screen (so that the 120 pixels of mode 5 become 240 pixels) to get a full-screen effect.
Sorry If this appear like a dumb question, but I really want understanding your point.

So, I understand all the rotation thing, I just have a little doubt about Screen Mode.

You start at Mode 5 -> Rotate -> go to "Normal Mode" -> Draw? That's it?
You can draw whenever you like, if you rotate the screen that’s just for appearance,
it’s not like the VRAM bank actually rotates as well. And there is no ‘normal mode’ like
I said before; it’s just the resolution gap. A GBA screen is 240x160, mode5 resolution
is 120x160. So it’s (a lot) smaller and that doesn’t look nice, that’s why you need to stretch.
I can see clearly now. :D

Thanks a lot!
Jinroh at 2009-11-02 01:36
Yeah, basically he's saying:

1. "Use Mode 5's BG2"
2. "Adjust the 'BGAffineData' for the BG2 to Rotate and Scale the screen"

Just in case you were having any more trouble. Hugo's a busy guy so he doesn't always go into great detail. He does awesome work though. ^_^
Edited by Jinroh at 2009-11-02 01:38
CaimX86 at 2009-11-02 07:33
Jinroh said at 2009-11-02 01:36
Yeah, basically he's saying:

1. "Use Mode 5's BG2"
2. "Adjust the 'BGAffineData' for the BG2 to Rotate and Scale the screen"

Just in case you were having any more trouble. Hugo's a busy guy so he doesn't always go into great detail. He does awesome work though. ^_^
Alright!

Thanks again. ;)
Jinroh at 2009-11-02 13:02
CaimX86 said at 2009-11-02 07:33
Alright!

Thanks again. ;)
No problem, I guess I should add what exactly BGAffineData is just in case. If you don't know where to find it, it can be hard to find the exact structure that they're looking for.
```
typdef struct
{
   s16 PA;
   s16 PB;
   s16 PC;
   s16 PD;
   u32 center_x;
   u32 center_y;
}BGAffineData;
```
That's all the data you should need just feed it to the affine background register.
CaimX86 at 2009-11-02 22:06
Jinroh said at 2009-11-02 13:02
CaimX86 said at 2009-11-02 07:33
Alright!

Thanks again. ;)
No problem, I guess I should add what exactly BGAffineData is just in case. If you don't know where to find it, it can be hard to find the exact structure that they're looking for.
```
typdef struct
{
   s16 PA;
   s16 PB;
   s16 PC;
   s16 PD;
   u32 center_x;
   u32 center_y;
}BGAffineData;
```
That's all the data you should need just feed it to the affine background register.
This will be very helpful! :)

Forum archive

Build - a raycaster?

Re: Build - a raycaster?