Progress thread for original version (2006)

A DOOM-style 3D engine for TI-83 and TI-83+ series calculators.

Moderator: benryves

Post Reply
coelurus
Calc Wizard
Posts: 585
Joined: Sun 19 Dec, 2004 9:02 pm
Location: Sweden
Contact:

Post by coelurus »

Prismas + PVS. Maps are created from vertical prismas with a variable number of sides as walls which can be connected (the prisma-bit). For each prisma, create a list of all other prismas visible from the current (the PVS-bit). Sorting convex areas (no poly-level sorting due to the convexity!) seems to me to be faster than doing BSP vector-dots, but I guess one will have to do some approx. to determine that properly.

What are your plans on removing lines? Filling?

How do you define windows and cut-out doors?

And no progress on the doom-thingie, I haven't touched z80 for ages by now and I won't pick it up again I think.
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Post by benryves »

Each wall has four bits controlling whether the upper, lower, left or right edges have lines drawn over them. I can use this to draw windows and doors.

How could you tell which prisma ('prism'?) you were in to start drawing? In any case, writing the tool to cut up levels into convex geometry is not something I'd be able to do. :(

Current plans for removing lines are filling (hooray overdraw). I can't think of anything reliable in the meanwhile.
coelurus
Calc Wizard
Posts: 585
Joined: Sun 19 Dec, 2004 9:02 pm
Location: Sweden
Contact:

Post by coelurus »

If you got a window, meaning a poly in a poly, how do you decide what pixels to fill inbetween? What if you got many windows at different heights in the same wall?

It's "prism", I got a little caught up in my typing :P Anyway, if you make a custom level editor, you can have only prisms as building blocks for the world. As for deciding which prism the player is in, uh... Try progressive updates. For each prism, store all directly connected prisms. When a player gets outside the prism he/she/it is in, try all connected prisms (should only be a few) and see where he/she/it wants to go.

The overdraw thing was what kept me away from true 3D altogether. A couple of hundred bytes to write to every frame with some bit-nudging for poly-edges, urgh.
Forget about that :)
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Post by benryves »

I don't quite see what you're getting at with windows. A wall with a window in it would be made up of 4 walls - a tall one to the left and right, and then two short ones at the top and bottom - a bit like this:

Code: Select all

    +------+------+------+
    |      |  3   |      |
    |      +------+      |
    |      |      |      |
    |  1   |      |  2   |
    |      |      |      |
    |      +------+      |    
    |      |  4   |      |
    +------+------+------+
When collision detection is implemented, it should be easy enough to work out which prism you have wandered into I guess (as you'd notice you'd been allowed to step over a particular boundary line).

When you spoke of level editors - are you referring to what were/are known as 'brushes', then, by 'prisms'?

Image

My filling code is ugly and pretty broken, but in a test it seems fastish, provided I could keep overdraw to a minimum. Some clever front-back sorting and filling could be in order, but I'm not sure how to implement that. :|
User avatar
tr1p1ea
Maxcoderz Staff
Posts: 4141
Joined: Thu 16 Dec, 2004 10:06 pm
Location: I cant seem to get out of this cryogenic chamber!
Contact:

Post by tr1p1ea »

Borked or not teh borked ... manual sort or not ... thats just plain cool :). Speed is pretty decent for an implementation that is broken :).

I like the bg too.
"My world is Black & White. But if I blink fast enough, I see it in Grayscale."
Image
Image
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Post by benryves »

Thanks :) The background is from DOOM (and would look a lot nicer when I've got the scrolling code in. It is sufficient for testing though).

The filling routine works by scanning along the top and bottom edges of the wall and storing the Y coordinates in a buffer, then walking going through from left to right filling each column as it goes.

One (more obvious) way to optimise this is to group columns into aligned 8-pixel wide columns, then find the lowest Y for the top edge and highest Y for the bottom edge and only fill up to those using the per-pixel fill (assuming no overlap). Then I could fill the rest of the column in a nice, speedy, per-byte fill.

The dancing black pixels are places where the shoddy tracing code isn't quite aligned and so you get pixels from the sky showing through.
coelurus
Calc Wizard
Posts: 585
Joined: Sun 19 Dec, 2004 9:02 pm
Location: Sweden
Contact:

Post by coelurus »

Aha, silly me, I thought less on your windows than I do when I eat.

Prisms ~= brushes.

Aren't you sorting and filling already? Or did you emphasize the word "clever" just before?
Front-to-back is only useful if one has a sort of early rejection mechanism (I don't like these words either, but they explain things well :P ) ala S-buffer, AEL etc and ways to not draw where something has already been drawn. Back-to-front lets you skip all that crap and instead use overdraw, which IIRC Doom did?

Oh right, nice demo :)
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Post by benryves »

Heh :)

No, there is no sorting at all, and there needs to be cleverer filling. If you move too far around the 'building' you can see the front face + door through the back wall. Pictures are more fun to look at than text, though, so I posted it in any case.

Extending walls to have upper, lower, and middle sections (ala DOOM) would help to reduce the number of transformations and clippings on walls that form borders (eg around a window).

I don't recall exactly how DOOM filled walls, but it was in a front-to-back order. According to the DOOM wiki:
As the segs are drawn, they are stored in a linked list. This is used to clip other segs rendered later on, reducing overdraw. The list is also used later to clip the edges of sprites.
One other concern is the need to fill floors, and how I'd go about that, to hide the edges of walls that fall below the floor.
User avatar
Madskillz
Calc Wizard
Posts: 745
Joined: Fri 17 Dec, 2004 10:22 pm
Location: Wandering around in the Jungle...
Contact:

Post by Madskillz »

wow ben that is cool! You always seem to wow me. Cant wait to see more! :)
The Revolution is here...
User avatar
Shadow Phoenix
Calc Guru
Posts: 835
Joined: Mon 03 Jan, 2005 7:54 pm
Location: out there. seriosly.

Post by Shadow Phoenix »

Now thats cool! :D
Life is getting better.
coelurus
Calc Wizard
Posts: 585
Joined: Sun 19 Dec, 2004 9:02 pm
Location: Sweden
Contact:

Post by coelurus »

Aha, mean little trick you got there with the sorting :)

Sounds rather obvious that Doom had some sort of screen-space occlusion scheme going on, even Wolfenstein had it :p

Do u plan on making a "general FPS 3D engine" with view rolling and the lot or a "Doom-esque-limited" variant?
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Post by benryves »

Yes, I know I'm mean. :P It was more a test on my behalf to see that filling the polygons doesn't cripple the speed of the engine. If I wanted to show off sorting, I'd walk around the 'room'.

Ultimately (in terms of speed) I'll use a custom interrupt (set timers to one of the lowest speeds) that counts up and use that 'clock' to time movement and events, so that (for example) an SE user can have more complex scenes at smoother framerates, but the 83+ user won't feel he's walking through treacle (just be a bit choppy).

View rolling? Is that as in the DOOM3 engine feature where the camera wobbles around like a bad steadycam operator? (As you can tell, I don't like it) ;) The engine can't cope with that (relies on walls to be vertically aligned) unless I added a post-processing effect (shifting pixel rows). Head bobbing is easy to implement, though ;)

I plan on building a DOOM-limited engine. If this runs nice and fast, I could extend this with more features to have a less limiting engine. That's all up in the air, though.
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Post by benryves »

Image

Still no true occlusion, but I have added multicoloured walls (currently limited to black, white or 50% dither). By swapping the initial dither pattern on alternate frames, you get a rather poor greyscale (a lot less flickery on hardware!)

As you can also see, the sky now scrolls with the camera. It's 128x64, so it does repeat (angles are 0..255), but is good enough for the moment.

Dithered walls are going to be a big problem, thanks to the attributes of the physical LCD (as you probably already know, if you have alternating pixels in rows, the contrast drops in that area). Having vertical bars for a dither fixes this, but looks rather ugly.
User avatar
Timendus
Calc King
Posts: 1729
Joined: Sun 23 Jan, 2005 12:37 am
Location: Netherlands
Contact:

Post by Timendus »

OMG, that looks amazing, Ben! Are the colours predefined in the map, or in any way calculated to simulate illumination?
http://clap.timendus.com/ - The Calculator Link Alternative Protocol
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
threefingeredguy
Calc King
Posts: 2195
Joined: Sun 27 Mar, 2005 4:06 am
Location: sleeping
Contact:

Post by threefingeredguy »

Oh wow.
Image
Post Reply