[WIP] Flash quake/descent style renderer.

[rachil0]

Had some time to work on this again over xmas/new years break so thought I would share a new demo :]

Added or revised features include:

* More robust shadowing - actually doing shadow volumes now instead of a flat projection. This makes some boundary cases render correctly that were failing before. The effect is still not perfect - there is a smoothing step that takes place in texture space that really should be done in world space (ie the code blurs/blends shadows using an 8 texels stencil, when it should blend using an 0.2 meter stencil). But most textures are at the same sampling density so you don't really notice that approximation. You can still only shadow by 1 light at a time - this will never change because shadowing is expensive enough already (note the drop in frame rate upon entering a new area). Screenie:



* Support for masked textures (like chain link fence). This is not really tough to do by itself, but it is tricky to get them to zbuffer correctly. It's not really a polygonal gradient fill anymore, it's a polygonal gradient fill with holes. The example fence is not very impressive, the real reason for adding this feature is to make thin doors.

* Underwater and under-lava graphical effects. Loved these in doom-a-like, just had to get them back. When viewed from above, water and lava are just standard animated textures that sorta ripple back and forth through a sequence of pngs. But when you jump underwater, a displacement map filter in screen space is applied to the entire framebuffer, so even the geometry looks like it's rippling too. A tint (blue or orange) is also applied. The displacement map filter was also used to generate the png sequence in the first place. Screenie:



* Sound effects for weapons, explosions and environmental events, courtesy of SFXR. I especially like the grenade tumbling sounds - 100% quake nostalgia. There are also stereo panning and distance fading effects. The fading is a little wonky - gets to quiet too soon - but the panning feels ok. Sound can't propagate beyond closed doors, and you can also tag sectors as soundproof. Eventually there will be gameplay consequences of sounds too, like player-triggered noises will alert nearby enemies.

* It's finally more than a camera in a box simulation - there is a player avatar with more interesting physical characteristics. The player can jump, slide down ramps, respond to friction and falls due to gravity. This screenie was made by toggling to 3rd person view and then walking your avatar around to face the static camera:



* There's a few interactive environment elements. There are timed laser traps, moving brushes for making elevators and bridges, and doors respond to player as they approach and retreat. Screenies of an interactive bridge and laser traps:




* Last but not least, there is a larger map to explore - 1K vertices, 1600 triangles, 32 sectors. I eventually expect real playable maps to be on the order of 3-4 times this size. There's also the first gameplay entities - find all 3 keys! However the locked (colored) doors are kinda on the honor system right now. You can walk through them without the keys, and you can't really pickup the keys anyway. Screenie in-editor:



Controls:
Left/Right/Page-Up/Page-Down to look around.
Up/Down to walk forwards and backwards.
Shift to jump, control to shoot, tab to cycle through weapons.
Home to toggle between 1st and 3rd person views.

Link to playable demo (1.5 MB, requires flash 10): here (Copy to your computer, unzip all contents to same directory).


EDIT: Glad you guys like it! Ideas for what gameplay features would be cool on a map would be greatly appreciated.

[renderhjs]

sooooooooooooo seeeeeeeeeeexy will have an in depth look at it

[.hooligan]

That's amazing

[UnknownGuy]

Just played through, was quite sweet. Nice job! (An actual usable 3d experience, quite rare!)

Mouse controlled view would be useful.

Runs real nice!

[ColbyCheeze]

Better than all of the PV3D etc demos if you ask me. This is more relevant to programming games than those painfully slow APIs. Well I say that from what I observe, I may be wrong...since I haven't tried to spend my time learning and using them.

I always enjoy seeing the updates you add to this project. Pretty cool stuff. Keep it up.

[mr_malee]

the best.

If you want something done, do it yourself.

[tomsamson]

I agree with the others, its a great achievment and i think with where the flash player is at right now something like this makes a way better impression and way more sense than all those pv3D etc demos which usually choke around at less than 15 fps without much interactivity.
This ran really great on my machine, i could even play it pretty smooth with anti aliasing turned on, really nice.


Since you asked for suggestions:
-mouselook aim and mouse button shoot option
yeah, not like in the classic games but man, i´d like it so much more with this
-not using shift key (pressing shift key several times triggers a windows message)
-show minimap (maybe gameplaywise only of already explored areas)
yeah, i get easily confused regarding where i´ve already been

[realMakc]

ah, you tricked me into thinking those beams actually do any damage, had to run like crazy through them my suggestion, make shadows stronger, they are barely visible here.

[dVyper]

Word can't describe just how blown away I am with this update so I'm not even going to try...

Just keep it up!

[Pazil]

...

WOW

I can't believe I have missed this for this long!!! First I must ask, is the whole engine a Z-Buffer? I've been working away at a Z-Buffer for a long time now (in theory), but I haven't gotten a lot of time, and only now am I starting to write my custom rasterization classes...but I read that the best way to go is with using GradientFill...my original plan, until I saw how slow BitmapData.draw() method is, or would be...And man have I ever imagined up millions of optimization techniques, but I've never had the guts to start something so big...in fact, I must admit, I don't even know exactly where to start...

I think that Render will recall me mentioning some weird secret 3d engine idea I had...well, this was pretty much it. I mean, I think I have a few tricks up my sleeve still, but of course, I need to actually show them and quit simply talking about them...
So yeah...this is the best 3d Engine yet! Delivers amazing FPS rate with very good graphical quality! I'm astounded when I see all those shadows and everything, and how you have a z-buffer!

A few details under the good: How exactly how are you doing everything? I mean, what are you doing in Vector, and what are you doing in Raster?
Second, what are the limitations of level design in it? Can you do absolutely anything, or are there some guidelines? (I think this was previously answered, but I'll have forgotten about it (*PHEW*...read through the whole thread in just about 40 minutes or so, to suck it in...) )...

Hell, this is my new favourite thread! And can you post the links to the demo's? Other people seem to be finding them, but I...well, you finish the sentence...

AMAZING
All my respect to you! Though I almost feel like giving up on Flash... Never knew someone else was thinking about doing a Z-buffer until know...

Keep up the work!

P.

[realMakc]

First I must ask, is the whole engine a Z-Buffer?

...both of my codes are portal renderers...

the link is mine.

[Pazil]

Ah ok...it just looked like there were some z-buffer screen shots...Post #77, second screeny. The way he combines the two and how he's using depth as the pixel shade is exactly like a z-buffer...

I never knew that a Portal engine can be the whole concept. From what I've read on Portals, is that they're just an optimization of sorts...to speed the rendering of things, and also solve fairly minor cases of visibility...
In the demo's (I'm sorry...I was too excited to really notice the links you HAD put up) you can throw objects like grenades.
How are they sorted with the other objects, like columns and stuff?

P.

[rachil0]

Thank you for all the interest I'll try to explain how it works in broad strokes:

It uses three different algorithms (portal rendering, binary space partitioning, Z-buffering) together to solve different aspects of the visible surface problem. The map is first and foremost a portal renderer like realMakc's link. The editor builds geometry from convex polyhedra ("sectors") where all the faces point into the roamable volume. If a map contained a single sector, it's easy to draw - because it's convex none of its faces can occlude any other. We just need to do a backface cull, project them to screen space, and draw them using the 400x300 screen rectangle as a clipping region. To support multple rooms, sector polygons can be tagged with hole ("portal") information. If a hole/portal subpolygon is present on a sector polygon, it the sector that is visible through the hole is drawn recursively. The holes projection in screen space is used as a clipping region - much like the 400x300 window was used before. Ultimately the renderer looks very much like a depth-first-search - the map structure builds a graph where nodes are the sectors to be drawn, and the arcs are the portals which connect them.

The renderer described thus far is basically the descent engine. With it you can model any geometry you like - just keep on carving out roamable regions with additional sectors. For greater geometric flexibility, you can partially fill a sector back in with outwardly oriented polyhedra ("brushes"). The reasoning is that sometimes it's easier to describe/discretize what is filled/unroamable rather than describing what is empty/roamable.
Consider the red door screenie: the laser trap emitters, ramp, and catwalk structures all all brushes, the green wall is the sector boundary. It's easy to say this room is "mostly empty with these specific areas solid", than to say "this area is made up on the following voids: ...". The catwalk in particular makes a weird 3 handle torus topology that would be tedious to describe in terms of the voids it leaves behind. Another way to put it, is that it's easy to build the catwalk structure out of blocks of marble, but hard to carve it out of a single piece of marble.

So there's also solid bits of map ("brushes") that fill back in a void ("sector"). However, when we have multiple brushes all existing in the same sector, we have to establish a drawing order so that they occlude each other correctly. This is where the BSP comes in. Each sector it's own local BSP which is used to sort the brushes. With just a local handful of brushes to consider, the BSP is easier to build. The editor does it automatically at export-time. To prevent faraway sectors from occluding nearby brushes, the brushes are drawn on the "tail side" of the recursion. So sectors are drawn as the recursion goes down, brushes are drawn as the recusion winds back up.

Moving on, the monsters are also self-sorted using BSP's. This makes sure that the arms of the monster correctly occlude the feet (for example). Monsters are sorted against other monsters using basic sort-on-z-centroid. Particles and billboards are also thrown into that step and sorted by z. Billboards currently include explosions and the green fireball weapon - the only raster entities in the game.

The tricky part is sorting these moving entities into the static map. I use a z-buffer with very limited functionality. Basically, the routine will let you feed it two screens, each with a pixel buffer and zbuffer plane, and will composite the two together in one pass. So the renderer makes 1 scene with just the map, another scene with just the monsters, and then composites them into the result. The z-buffer can be filled efficiently on a polygon-by-polyogn basis using linear gradient fills, because 1/z is linear in screen space.

There is no support for setting or testing single pixels - this cannot IMO be done efficiently in flash. However an entire-pass composition can be done efficiently using blendmode subtract and a bitmapData.threshold. Because of the finicky way flash does gradient fills and channel subtract, the zbuffer only has about 9 bits of resolution. This is an area I would like to improve, but it's not that bad because we have robust sorting schemes for every possibility except monster vs. map.

That ought to cover most of the basics (regarding your specific question, grenades are treated monsters so they are zbuffered to occlude correctly against columns).

[Pazil]

Wow. A wow for the engine itself, and wow for how well you explained it!

I never understood what you meant by brushes before now. So the only rule is you always need a big polyhedra encompassing the camera? If that's so, then I really need to get down and learn your engine's API!

A question on the z-buffer then...So you first draw a monster by doing the centroid z-sort. How do you draw the gradient shapes of it? And last but not least, how do you draw the final image? I understand the z-buffer combination well enough (I think), but how do you then translate the buffer info into the actual pixel values?
A question on the blendMode option also...why subract, and not lighten/darken? And then what does bitmapData.threshold do (In regard to the engine)?

How often are you using BitmapData.draw()? I'm sorry if some of these questions are quite obvious, since I'm used to using the as2.0 BitmapData, so I don't know how they've changed the operations (in fact, I'll look at it now).

Sorry for overloading with questions...I still only half believe this!

P.

[rachil0]

Yes the camera must always lie inside of a polyhedra - a home sector from which the recursive rendering begins.

Just like you compure u,v coordinates for polygon vertices, you compute a camera z-depth for each vertex too. If you look at the function 1/z (or K/z for any constant K) across a flat polygon, it's actually linear in screen space after the perspective transform. So instead of rolling your own rasterization where you compute and poke z into a bitmapdata one pixel at a time, you can write 1/z for a whole polygon at once with a linear gradient fill (graphics.beginGradientFill). It's been a while since I touched this part of the code, but I think the actual mapping from z to color is:

      function zbuffer_value(z : Number) : color
      arg = 256/z;
      if (arg > 765)
       return 0xFFFFFF;
      if (arg > 510)
        return 0x00FFFF + ( (arg-510) << 16 );
      if (arg > 255)
        return 0x0000FF + ( (arg-255) << 8 );
      return arg;

Basically this takes a z value and maps it into a fill value between 0 and 765 (=255*3), and that gets mapped into a real color between (0x01,0xFF) or (0x01FF,0xFFFF) or (0x01FFFF, 0xFFFFFF). That is a continuous spectrum of 765 unique colors that can be filled with a gradient fill without introducing any gaps that could confuse the linear interpolation routine internal to graphics.beginGradientFill.

The blendmode subtract and thresholding operators are how the z-buffer write/test pass is implemented. Subtract ... erm subtracts the two zbuffers pixelwise, then threshold is used to find where the monster zbuffer was further than the map zbuffer. Where that happens, threshold writes a transparent pixel. Then this masked monster layer is composited above the map layer using bitmapData.draw.

It's obscure and the resolution sucks but I spent a lot of time trying to figure out a good way to fill and composite z-buffers and this is the best solution I could come up with. I would eventually like to rewrite those routines...perhaps in C++. I tried pixelbender but was not pleased with the speed.

All in all there are 3 draw calls. The map layer is rendered into an offscreen sprite using graphics.beginBitmapFills and graphics.drawTriangles, and ditto for the monster layer. Two draw calls are used to drop those graphics contexts into honest-to-god bitmapdatas. The third draw call is used during z-composition (as described above).

[Pazil]

Awesome!

I'm still not quite sure why you don't just merge the monster and map using BlendMode.LIGHTEN though. Also, you mention it filling in transparent pixels. Is this process done by looping through each pixel? Ah...waaait a second. I might have had a click right here. You do the subtract and threshold, because that's where you draw on the actual bitmaps of the projections instead of the z-buffer projection?
But then is the actual drawing done face by face basis, or the whole monster at once? Because if you do monster at once, then you must be doing 2 projections of it at first, no? One for the z-buffer with gradients, and one of the actual image? And same with the map?

I hope I don't seem to be nagging at you with questions or anything...This is all so fascinating! Also, how are you doing the gradients through drawTriangles? Do you need to give it a matrix, or can it interpolate values?

Thanks for being so open! And you seem to respond very quickly, but don't let me keep you from doing more! Keep it up!

P.

[rachil0]

You might be able to get it working with lighten - replaces with minimum z right? But then it wouldn't be obvious to me which layer that minimum z came from. With blendmode subtract, you get a zero where the map pixel should be used and a nonzero where the monster pixel should be used.

The transparent filling is done with threshold. It is a totally bizarre method if you peruse the livedocs, it edits the contents of the map pixelbuffer, but with a conditional check in the map z-buffer.

The drawing for monsters is done face by face, into two seperate graphics contents (a pixel buffer and a zbuffer). The map is the same - so ultimately there's 4 bitmapdatas in play (mapz, monsterz, mappixel, monsterpixel). This burns up fill rate but I have found that to be a plentiful resource compared to polycount.

The gradient fill is done with drawTriangles. There is some math magic behind the scenes to setup the beginGradientFill arguments. (bGF has very strange semantics too - internal units are 20'ths of pixels). The helper function, matrix.createGradientBox, is invaluable for getting this calc correct. But it doesn't do the whole job for you, because it only works for axis aligned gradients. You have to rotate and translate it around after you set it up, to get the gradient aligned with the proper screen direction and get the zero-z point in the right spot. Not a ton of math, but you have to be pretty careful with over/underflow when your z value is not inside (0,765).

Just happy to help Been working on 4k games so I've been trolling flashkit to see what the other guys are up to.

[realMakc]

if you do drawTriangles you could use UV(T)s as well and replace beginGradientFill with beginBitmapFill. but that may be slower too.

[Pazil]

That's a good idea! It could be slower, but if the GradientFill is really using 20'ths of pixels...then it wouldn't hurt to try it out!

P.

[Pazil]

Actually, nevermind. It seems that rastering lines may be faster, but it seems as though rastering triangles can't compare with drawTriangles()...

I was wondering about the FPS your engine's giving right now...How much of it is the overhead, and how much is the amount of poly's you want to render? Meaning, I notice that in the other 3d engines out there start out with quite low frame rate, but after you get over that, you can add quite a few triangles and poly's in there without worrying too much about the frame rate really shaking down...

P.