Page 1 of 9

Progress thread for original version (2006)

Posted: Mon 03 Apr, 2006 10:43 am
by benryves
Well, I gave raycasting a shot (and got nowhere with it!) and as Timendus is working on a raycaster himself I thought I'd go back to a vertex-based engine.
I already had some basic 8-bit 2D rotations going, so upped that to 16-bit and optimised them quite a bit:
Image
Having worked with DOOM recently, I think it's best to isolate the various parts of the world - the world's vertices are transformed in a batch. I'll then have a list of walls, linking vertices (by index).
Backface culling is trivial in this setup (if the second vertex's x is smaller than the first vertex's, it's invisible), the big problem I'm hitting upon is clipping the line to the view.
I'll use a triangle, where the valid points are in x<y && x>-y && y>0. Hopefully this would ease calculations.
I can't think of a sensible way to clip the line, though. Would a linear interpolation job be sensible? I'm trying to steer well away from any extra division/multiplication though... I'm already at 4 signed 16-bit multiplications per vertex. Then again, walking along the line using Bresenham until you hit a valid point sounds like an evil hack :P

Posted: Mon 03 Apr, 2006 1:52 pm
by coelurus
Just using Bresenham can still force you to clip (if the view sees only a middle segment of a line), or even worse, walk along a super-long line outside the screen due to perspective projection (which gives something like coord*-z behind the view). Still, if you can somehow make sure you got atleast one end-point in the screen, drawing the line until you hit a screen border should work pretty well.

It would be interesting to know a few more details:
What are your plans for rendering the walls?
Do you figure out what sectors in the map are relevant to some view and transform only those?
Windows?

Posted: Mon 03 Apr, 2006 2:16 pm
by benryves
coelurus wrote:Just using Bresenham can still force you to clip (if the view sees only a middle segment of a line), or even worse, walk along a super-long line outside the screen due to perspective projection (which gives something like coord*-z behind the view). Still, if you can somehow make sure you got atleast one end-point in the screen, drawing the line until you hit a screen border should work pretty well.
I think you're giving me too much credit - I meant using Bresenham to clip the line before it is transformed to the screen. As in, I know that one (or both) of the points are off-screen, so I walk along the line until I am on screen and use that point as the new end. I then transform to the screen as normal, safe in the knowledge that the line is safely on-screen (in fact, I'd now know that the X coordinate is right on the left or right edge of the viewing space, saving a division).

Seeing as I'll be using fixed-height "sectors" for the moment, I'll just use a LUT for the heights of walls.
What are your plans for rendering the walls?
In terms of technique or code; none whatsoever as such.
I will not be texturing the walls, though. If I feel especially creative (and have the clocks to waste), I might fill them a solid colour or dither them.
Of course, I'll need to sort back-to-front somehow. I don't know how good BSP would be for this sort of thing...
If I can get a basic, ugly, wireframe view up and running, that'll make me happy.
Do you figure out what sectors in the map are relevant to some view and transform only those?
All vertices are batch-transformed at the moment. Nothing clever is being done.
Windows?
Fixed-height sectors for the moment, so just walls, walls, walls. Of course, there's also the fun of trying to hide sprites behind walls and things like that which I haven't even dared think about yet.

I really wouldn't expect too much from me, as 99% of my 3D attempts have resulted in inglorious failure. ;)

Posted: Mon 03 Apr, 2006 9:32 pm
by coelurus
benryves wrote: I think you're giving me too much credit - I meant using Bresenham to clip the line before it is transformed to the screen. As in, I know that one (or both) of the points are off-screen, so I walk along the line until I am on screen and use that point as the new end. I then transform to the screen as normal, safe in the knowledge that the line is safely on-screen (in fact, I'd now know that the X coordinate is right on the left or right edge of the viewing space, saving a division).
Sounds really "dangerous", with what resolution will you step along the lines? How well will the lines align to the screen borders? Linear stepping in object space and then transforming into view space is generally a bad idea, you should consider clipping lines which have both ends outside the view and draw all lines with from the endpoint inside the view until you hit a screen border. Divisions aren't that bad really, you won't have hundreds of clipped lines anyway.
In terms of technique or code; none whatsoever as such.
I will not be texturing the walls, though. If I feel especially creative (and have the clocks to waste), I might fill them a solid colour or dither them.
Of course, I'll need to sort back-to-front somehow. I don't know how good BSP would be for this sort of thing...
If I can get a basic, ugly, wireframe view up and running, that'll make me happy.
Wireframe is really, really tricky to get working. I'd like to suggest you sort front-to-back instead and use a "virtual horizontal occlusion mask" (tricky words, but it's really simple :) ) to mark sections of the screen that have been covered with a wall section. If you got a screen with 96 pixels, you make a mask with 96 entries. When you render a vertical wall column, mark the proper entry in the mask as "filled". As long as the wall sections are fixed in height, it should work (you'll even get a perfect estimate on when the screen is filled and you can stop the rendering). Things get tricky when it's a full 2D screen problem, as the vertical edges in my doom code :P
All vertices are batch-transformed at the moment. Nothing clever is being done.
If you use the occlusion-mask-thingie, divide the map into sectors and incrementally walk through nearby sectors until the mask is filled.
Fixed-height sectors for the moment, so just walls, walls, walls. Of course, there's also the fun of trying to hide sprites behind walls and things like that which I haven't even dared think about yet.
Got nothing to add :wink:
I really wouldn't expect too much from me, as 99% of my 3D attempts have resulted in inglorious failure. ;)
I've seen quite a lot of 3D-stuff from you and I must say they looked rather nice. Have you been coding several hundred 3D engines that we regular mortals are not aware of? :)

Oh warm cuddly bed, what a nice place to spend a good night's sleep...

Posted: Tue 04 Apr, 2006 11:04 am
by benryves
Same map as before (a few points in a square with a ring of points around it), in a more "3D" view:
Image
It's a bit wasted; the entire "map" is 20480 units high/wide!
coelurus wrote:Sounds really "dangerous", with what resolution will you step along the lines? How well will the lines align to the screen borders? Linear stepping in object space and then transforming into view space is generally a bad idea, you should consider clipping lines which have both ends outside the view and draw all lines with from the endpoint inside the view until you hit a screen border. Divisions aren't that bad really, you won't have hundreds of clipped lines anyway.
True, divisions are a lot faster than I had imagined they would be.
It was more a concern that when lines stretch to odd positions (for example, if a line had one point a little way a front of you, and the other point quite a long way behind you) then the transformed points would end up wrapping or doing other strange things. I see your point for clipping lines that are entirely in front of you, though.
Wireframe is really, really tricky to get working.
When I said wireframe, I meant like you'd see in a 3D modelling package, and you can see through the mesh (the walls don't occlude eachother). I had thought of a few ways to occlude walls - keeping track of the upper/lower "points" for each screen column, and before drawing a wall checking that it doesn't write over an existing wall (drawn front-to-back). For example, a wall slice would be drawn from y=16 to y=48, the next wall slice (taller) would try to be drawn from y=8 to y=58, and because it is taller the points would be added (but would only be filled from 8->16 and 48->58 ). The next wall would be really far away, and only from 30 to 34, and because this is lower than the current wall it is completely ignored. That sort of idea.
If you use the occlusion-mask-thingie, divide the map into sectors and incrementally walk through nearby sectors until the mask is filled.
Nice idea. :)
Have you been coding several hundred 3D engines that we regular mortals are not aware of? :)
Something like that :D You've probably seen this:
Image
...which was Matt3D-powered (Glasscars, Coaster83).
I also did some horrible line-drawing hack on top of your raycaster #1 demo. Those were the only two that didn't end in total failure, just the usual "it's just not going to work!" failure.

Posted: Tue 04 Apr, 2006 5:01 pm
by kalan_vod
Thankyou both, I am learning a little from reading your posts. I wanted to add to the conversation, but I don't have anything to add :P...Btw Ben..WOW..all your SS look amazing! and coelurus you have done some outstanding work also!

Posted: Tue 04 Apr, 2006 6:15 pm
by coelurus
Ben does some really good work, glad to hear that I too contribute with something useful although I never touch any z80 :)

The flipping-of-vertices-behind, always fun to mess around with. You can optimize your line-scanning thingie with some crude binary refinement. Step using refined steps along the line on one of the X and Y axes until you get below a certain threshold just in front of the view plane. You could also try to clip transformed vertices to the near plane and then do the perspective projection.

The successive occlusion scheme is pretty much what was used in the little C-doom-demo and it works well for variable-height walls. I wonder about windows though, maybe it'll need a sort of vertical span buffer for every column. Or maybe windows are totally outrageous, but it would be a nice touch being able to look outside into courtyards. I hope atleast you'll try it Ben :)

Posted: Wed 05 Apr, 2006 10:16 am
by benryves
Image
Have some quicky hacked-on walls. No clipping, yet; if either vertex is off-screen the wall is ignored. The distortion when a wall is close is thanks my lazy wall height table;

Code: Select all

.for _dist, 0, 255
>   _height = 512 / (_dist+1)
    .db _height > 64 ? 64 : _height
.loop
Any thoughts on sorting the walls? The sorting algorithms I'm aware of rely on sorting a block of data after it has been created; I'm not sure if there's a clever way I can speed this up by adding the walls in sequence before sorting to optimise things.
coelurus wrote:The flipping-of-vertices-behind, always fun to mess around with.
"Fun" isn't exactly the word I'd use... ;) The technique you mentioned seems sensible enough.
I wonder about windows though, maybe it'll need a sort of vertical span buffer for every column. Or maybe windows are totally outrageous, but it would be a nice touch being able to look outside into courtyards.
Yes, thinking about it the method I was considering depends on all walls overlapping to some extent - so you couldn't have two walls, for example, at the same depth but one floating some distance above the other.
I certainly would like to have variable height floors/ceilings and so allow windows. I'll take it slowly though, one thing at a time.

Posted: Wed 05 Apr, 2006 1:54 pm
by coelurus
Sorting: splitting up your maps into convex sectors will help a lot, I see in your GD journal that you have been messing about with a similar issue so you should be able to do this with ease :)
As long as sectors are convex, you will get perfectly sorted sets of polygons if you walk through sectors one by one. You will also get a nice way of only processing parts of maps that are relevant for free.

Posted: Wed 05 Apr, 2006 2:17 pm
by benryves
Do you mean that each sector is linked to every other sector somehow, and so all I have to do is follow the sectors along? So, for example,

Code: Select all

+--------+--------+--------+
|        |        |        |
|   1        2        3    |
|        |        |        |
+--------+--------+--------+
I'm standing in sector 2, so I render sector 2, then sector 1, then sector 3? Or, if I was standing in sector 3, sector 3, then 2, then 1? I can see this getting very horrible when a sector has, for example, 4 adjacent sectors! As for cutting out the sectors...

Posted: Wed 05 Apr, 2006 10:44 pm
by Timendus
Damn, that's looking pretty cool already, Ben! :)
PTI with networking, 3D challenges... It's really tempting to get back to z80 for a while :mrgreen:

But I can't, I have lots of exams to learn for, family to visit, webdesign to do for other people... I shouldn't even be here now, I need to sleep! :)

Posted: Thu 06 Apr, 2006 7:08 am
by coelurus
Hum, another way of sorting is of course BSP trees. Those too should be used in small parts of the maps or else there will be lots of primitive-level splits (more potential clipping!).
Going back to sectors once again; sorting small lists is pretty fast, so maybe you could split your map into convex sectors, merge maybe 2-3 of them and then sort each one at the primitive level as they are requested for rendering.

Sounds like something you will have to try out, a perfect opportunity for some experimenting (or "prototyping") on the computer :)

Posted: Thu 06 Apr, 2006 3:31 pm
by benryves
coelurus wrote:Hum, another way of sorting is of course BSP trees. Those too should be used in small parts of the maps or else there will be lots of primitive-level splits (more potential clipping!).
Not to mention my incredibly awesome and heavily optimised BSP node generator, that has in the past generated > 5MB trees for a simple 30-line level. I've never been too hot on BSP. ;)
I have a nice little QuickBasic BSP engine somebody wrote which comes with a level editor, so I might have a look at that and try and puzzle out how that works.
Sounds like something you will have to try out, a perfect opportunity for some experimenting (or "prototyping") on the computer :)
Hehe :P

For the time being, I think I'll concentrate on trying to get wall clipping working (and reliably). I've got backface culling up and running (walls can be flagged as double-sided as well), but still no occlusion.

Posted: Thu 06 Apr, 2006 10:40 pm
by Fr0stbyte124
benryves wrote:Not to mention my incredibly awesome and heavily optimised BSP node generator, that has in the past generated > 5MB trees for a simple 30-line level. I've never been too hot on BSP. ;)
:o I didn't think that was possible...

Posted: Fri 07 Apr, 2006 9:54 am
by benryves
Fr0stbyte124 wrote:
benryves wrote:Not to mention my incredibly awesome and heavily optimised BSP node generator, that has in the past generated > 5MB trees for a simple 30-line level. I've never been too hot on BSP. ;)
:o I didn't think that was possible...
I think it liked the idea of splitting down the levels into infintessimally short lines. I believe it was floating point innaccuracy that saved it from going on for ever ;)