Messed with this some more today. Like I was thinking a while back, it's straightforward to rip the environment geometry out of the original shareware version of descent and reformat it for this clone platform.
Here's level 1 in-editor:
And in-game:
I ripped the textures out of the game as well, but it's not clear how to redo the texture mapping in a way that's faithful to the original game. Apparently, the original descent performed bilinear UV mapping across quadrilaterals. I think that means that even when the surface is viewed perfectly normal-on with no perspective distortion it is not mapped affinely between screen and texture space. This code assumes that the mapping between polygon coordinates and texture coordinates is affine and I hesitate to change that on a whim. I suspect that Flash 10 makes the same assumption.
Another quirk with descent is that some of its polygons (quads) aren't even self-coplanar (and it's not a precision problem, they're not even close). That causes more visual artifacts, because you cannot reliably decide whether you're looking at the polygon from the front or the back. I guess one thing to do is split the quad into two triangles and push them through individually, but it isn't clear to me that such a splitting is always possible. At least, not without making a cell nonconvex, which is major failure time (TM). I have no idea how this idiosyncrasy is handled in the original game.
There's also a lot of places where they've made lots of slices in space. The atomic unit of a descent map is a warped cube, so there's lots of places where open volumes have been tesselated into cubes even though the volume is convex already. That isn't necessary in the flash clone, because it supports arbitrary convex regions already. Beyond being unnecessary, splitting a convex volume into subvolumes leaves lots of phantom ink lines hanging in the air, and causes a real performance suck as visibility is tracked through all these portals which are completely see-through already. It appears that descent avoids this perfomance penalty by aggregating cubes into "groups" which are guaranteed not to self-occlude (ie grouping the cubes back up into the convex volume that we started with). The flash clone doesn't do that grouping (why would it, right? the convex shape were trying to build up is already supported as an atomic unit), and I don't feel like coding that in just to avoid a limitation of the original game.
Given these problems, (and copyright issues) I don't plan to chase through Descent's data anymore. But it's still pretty cool that it worked at all.
Those are Q3 Arena compatibles, right? Probably won't happen. I think Q3A is a BSP traverser, not a portal renderer - although it probably supports portals somehow for early rejection of large groups of polygons. I (sort of) get how BSP rendering works, but I have no clue how player movement is clipped with that kind of geometry representation.
Not easily. In a portal renderer, faces have to be collected into convex polyhedra which enclose player roamable space. There is no such thing as a polygon in isolation, it's always bound to exactly one polyhedron.
Descent maps can only be translated/loaded easily because it stores these polyhedral groupings inside the level file. In quake (and sequels), this representation is not made very explicit. Every leaf of the BSP tree defines a polyhedron, but to actually build that polyhedron requires a lot of clipping operations. For loading a quake map it would be more of a reconstruction process, not a translation process.
I'll go ahead and throw these out too, they're matlab .m files for ripping out the descent shareware assets. The descent developer network, www.descent2.com/ddn/, has some helpful documentation on it.
parse_hog.m - The file descent.hog is basically a tape archive of robot models, map geometry, palettes and mission briefings (and more). This script pulls it apart into individual files again.
parse_pig.m - The descent.pig file has all the source textures. They're all palettized to 256 colors, the palette map is inside the palette.256 file (which is archived inside descent.hog). Some are RLE compressed, some are just blitted. This code decodes both cases and uses the palette to promote them to 24bit pngs.
parse_sdl.m - This is the one file that deserves posting, because this format is not documented on the DDN. The shareware and retail versions of descent1 have significantly different map encoding schemes, only the latter is documented online. Figuring out the shareware encoding required digging through the source which was kind of a pain (but it's open sourced so I think its still kosher).
You could definitely translate these to C, and you can probably do it with actionscript too, if you use the ByteArray class and are careful about the conversions from fixed point integers into Numbers.
It's been updates galore lately - have had more free time than usual for the last couple of weeks. So hooray for a slow summer!
Worked on porting this code to Flash 10 to take advantage of its support for 3D texturing (via graphics.drawTriangles). At high resolution, it's a marginal improvement speedwise, but visually it's a lot prettier because you get free bilinear filtering and it completely eliminates all those nasty perspective errors come from approximating the perspective transform with affine slices. Here's some screenies:
Flash 9:
Flash 10:
There's one catch that is causing some headaches - the drawTriangles method doesn't support tiling UV coordinates, it just clamps them. (That is, it currently ignores the "repeat" option of graphics.beginBitmapFill). I think this is unfortunate, because it forces you to waste a lot of time (or space, take your pick) tiling the texture manually, if that's the effect you want. It should be practically free to do this within Adobe's code for drawTriangles, I posted a feature request on the F10 forum about it so maybe it will make the cut. I plan to code up a work around in the export routine anyway - tiling the texture into a bigger bitmap automatically and readjusting the uv coordinates so that the process is transparent to the user of the map editor.
Getting lighting effects back in there is going to take some creativity, have some ideas but it's a little too soon to implement them.
I'm trying not to get too far ahead of myself, but I think F10 will be a huge benefit for this project. I expect that the frame rate can be cranked up quite a bit with just a little bit of quality loss. Rendering into a 400x300 window makes it run at like 100 fps on my wimpy machine, with a little bit of bitmapData.draw magic and a 2X rescale through a regular, affine beginBitmapFill, I expect this code to run about twice as fast as the F9 implementation and still look better.
Still working on the map editor too - dialog boxes for uv mapping are complete, going to work next on improving the flexibility for inputting geometry (rotations, copy/paste submodels, etc).
imho 10th version looks far worse, it's like totally blurred, with only things that benefit from high resolution being edges. 9th version looks sharp and more pleasing to my eye... imho.
imho 10th version looks far worse, it's like totally blurred, with only things that benefit from high resolution being edges. 9th version looks sharp and more pleasing to my eye... imho.
thats because the textures are stretched right? if the textures were sized to the face it sits on then it would look really nice and crisp.
by the way, I'm in awe, this project rocks the pants down.
thats because the textures are stretched right? if the textures were sized to the face it sits on then it would look really nice and crisp.
I think this is exactly right. All the textures I have laying around are 64x64 and meant to be tiled, but tiling isn't supported by drawTriangles so they had to be stretched out to fill the polygons. With appropriately sized textures (256? 512? who knows) I think the F10 version will look much better.
All these updates have been tech related with ugly content, once the editor is in better shape I will try to do a nice content piece that has some interesting geometry and pretty texturing.
The map editor is finished (more or less) to the original specs. Here's the newest round of features:
* Quicksave / Quickload / Peek at a Quicksave
* Support for texture alignment, with 5 different ways to define UV coordinates: {orthogonal, skew axes, arbitrary 3-point match, match to a coplanar polygon, unfold texture across a shared edge}
* It was too hard to tell what you were doing while you defined textures, so now you can preview the texture mapping directly inside the editor. This is basically required a port of the Flash9 rasterizer into the editor. It's still not a true WYSIWYG because the editor doesn't implement occlusion/polygon ordering, and there's no lighting effects. It's pretty close though.
* Support for more geometry transforms (mirror/rotate/scale/translate). Some of these have new dialog boxes to help get you moving in the right direction.
* New dialog boxes for constructing vertices, regular polygons and rectangles. I feel these are useful for shaping up a level more quickly, which is typically lots of axis aligned shapes. The freehand vertex sketching, and creating polygons from vertex sets are still supported.
* You have more control over polyhedra - you can add/remove faces individually to build your own shapes from a collection of polygons, and change the orientation of all a polyhedrons faces simultaneously.
* In addition to creating polyhedra by extruding them, you can also create pyramids (whoopee). To help you make more interesting shapes, you can clip polyhedra against planes. You can no longer clip individual polygons.
Here's an example map with some (reasonably) complicated geometry that I made completely inside the editor:
There's also some big technical changes that were influenced by the migration to Flash10. Back in post #33, I described how the Flash9 texture mapper plays an important role in visibility/occlusion. That is, it was written to texture map a convex polygon which is hidden/occluded by a set of convex holes. The Flash10 texturer (graphics.drawTriangles) has no concept of holes/occluders. To take advantage of its great pixel fill rate, a lot of crap had to be redone. At this point, the code is both a portal renderer and a bsp-traverser. Cells are still traversed recursively like a portal renderer, but the draw order of brushes inside each cell is determined using a BSP (so now there's overdraw for brushes, they're drawn back to front). It's not an entire-map bsp the way quake works - it's a BSP that is only responsible for carving up the space inside a single cell (a much smaller region, with much fewer polygons). With so few polygons, it's possible to implement the BSP creator in flash, with just a brute force "try to use every polygon as a splitting plane" approach. The editor does this for you during the export process, but it's still up to the (intelligent) user to provide polyhedra that can be BSP'ed without needing any splits. If it's detected that a polyhedra needs to be split in order to proceed, the export halts and tells you what polyhedral subset needs to be resolved. The user can then split these polyhedra manually (the Polyhedra>Clip command is used for this). It takes some brains to get a map successfully out the door, but the extra performance of Flash10 is soooo worth it. Here's the above example, running in both codes (still ugly textures, but now you COULD make them pretty if you took the time to do so).
This a pretty complicated scene for this engine, Flash 9 chokes on it.
Flash 10 delivers the goods (as much as 3D in flash can be qualified as "goods").
Some features were added to the Flash10 renderer, so it now has all the capabilities of Flash9:
* Support for brushes (the last F10 screenshot didn't include them, because they flat out didn't work). This was described earlier, it's all that bsp stuff.
* Sector based lighting.
* Depth cueing / fogging. This is the one place where there is a noticeable difference in the output between the two engines. The Flash10 version is a lot darker at long distances (z), right? In F10, depth cueing/fogging is done by overlaying partially transparent black polygons on top of the texture layer. The alpha value is modulated across the polygon so that far portions are darker than near portions. Unfortunately, to do this quickly in one shot (with graphics.beginGradientFill), your alpha CAN ONLY vary as a function of Z according to alpha:=C1+C2/z, for some constants C1 and C2. The original F9 version had alpha:= C1+C2/(z+C3). In short, the shading in the F10 version can't represent the F9 shading exactly. It's not that big of a deal IMO, but C1 and C2 definitely need some tweaking because it's too dark. Actually, a bigger problem is the singularity at Z=0, because at some point the alpha just saturates to zero and you get full brightness right through the fogging polygon. The C3 constant in the F9 version was introduced to push this saturation point behind the camera so it wasn't visible.
[Don't get me started on how messed up graphics.beginGradientFill is, how its matrix argument works is completely indecipherable. IMO the method is unusable without its helper function, Matrix.createGradientBox.]
*Completely redone collision detection, it's much less "jittery". You can now properly "slide" along walls, intersections between walls, and even nestle stably at the point where 3 walls intersect.
Some new planned features for the editor that are yet to be implemented:
* Special "tagging" options where you can define attributes on any geometrical construct (vertex, polygon, polyhedron). A tag is just a piece of XML data that will be carried along throughout loading/saving/exporting. This will be an extensible way to define things like sector-based lighting, start positions for players, whatever. Tags will be meaningless to the editor, they're just satellite data that hangs around. It will be up to the consumer of the exported xml data to interpret tags as they will (this is intentionally vague).
* Support for defining flat-color values on a per-polygon basis. Flat color will be used when no texture is defined, or when the polygon is too far away to be worth texturing. Right now, flat color is initialized to hot-pink and there is no way to edit in the editor. This will be an option on the same page as UVmapping/texture definition.
And on the renderer side:
* Support for monsters (finally!), with correct or at least decent occlusion behavior. Self occlusion is no problem - monsters will be implemented with BSP's so they'll self sort correctly. Sorting them against the map is expensive to do at runtime, because you've got to split them across portal boundaries AND split them against brush BSP planes. This is a fearsome amount of code and runtime expense. ... But I've been tinkering into it already, and I think pixelbender/hydra might come to the rescue here, and enable the implementation of a zbuffer in software. Using gradientFill I've figured out a way to write an 11-bit z-buffer already, if I can get it to 16 bits I'll be more than happy. The pixelbender stuff will be used on the compositing side, where z-buffers and image buffers of both the monsters and the map have been created individually, and a final image needs to be constructed by z-sorting them together on a pixel-by-pixel basis. The code is already F10 only, so why not explore the options.
I do not plan to update the Flash9 renderer anymore, but exporting to its file format will still be supported by the editor in case anyone wants to play around with it. [As the Flash10 work progresses, I expect its featureset will get further out of sync with the Flash9 version and its too much work to keep them both current]. However, I think the editor will remain a Flash9 project for now - it throws a million errors when compiled with mxmlc10, because its Vector3D class collides flash.geom.Vector3D. Oddly, this collision doesn't happen when you compile the renderer, just the editor. It must be because the flex UI components import flash.geom.* (boooo).
PS: The good feature fairy has promised me texture tiling will be added to flash 10's drawTriangles method (even though I already coded up the workaround). The workaround will enabled some new features like splatting bulletholes and other "damage" features onto textures. (broken screens like in descent), so I'm not cutting it out yet.
EDIT: I'll post up the codes and whatnot later, I'd like to hear more performance quotes on F9 vs. F10. Unfortunately, my free time is running out (new job starting soon) so this project is yawning and preparing to hibernate for another month or two (at least).
This requires all 16 entries of gradientFills colors[] argument (why oh why is this capped..... it still won't get you beyond 11 bits, because you're capped to 16 colors[] arguments.
I dont see why one cant subdivide triangle in necessary number of parts and fill independently (especially in v9 where the math can be merged with perspective correction). Still faster than setting pixels.
Been trying to solve the problem of how to sort monsters/items and other dynamic entities into the map. When the map consists of just the convex sectors & the portals between them (like descent), this is easy to do. As every monster polygon is drawn, just clip it against the portal that exposed the sector where the monster resides. No other polygons of the sector can occlude the monster, so draw them first and then the (clipped) monster goes back on top.
But when you permit the sectors to contain solid brushes that fill back in the space (like pillars, floating platforms, and other interesting geometrical bits) you have a real mess because these things can occlude the monster in complicated (possibly cyclical) ways. The brushes themselves will properly sort amongst themselves when you carve them up with a BSP, but this is only tractable when you can do the splitting upfront and store the cuts. If you have a brush that moves (like a menacing, roaming tetrahedron), this cutting process must be done every frame. I did implement that approach first, but it's far too slow to do in realtime. Flash is more polygon limited than fillrate limited, and this approach does not play to that economy. The same number of pixels are drawn, but you're drawing lots of little triangles and dramatically inflating your number of polygons because you split one monster polygon into 5-10 fragments depending on the scence.
The other option I see is zbuffering the map scene, and then doing conditional pixel writes when you draw in all the monsters in a second pass. This is attractive because it plays to the fillrate/polycount economy. Filling the zbuffer doubles your polycount and pixel fill requirements, but you have plenty of the latter already and it's still lower polycount than the previous case. I hoped to use some kind of pixelbender routine to do the compositing, but (!) Pixelbender is not at all performant compared to existing bitmapData methods, at least not in its current implementation (!).
So if you want to zbuffer quickly, you have to implement this test & write using the existing methods on BitmapData. I haven't figured out how to do this on a pixel by pixel basis right as each monster pixel is being drawn, but I think a workable compromise is to draw all the monsters (and their z) back to front. Then you have four separate graphics contexts with (i) map-texture (ii) map-z (iii) monster-texture (iv) monster-z. Actually it's a 1/z buffer with 8 bits of resolution, which can be drawn very quickly using gradient fill because 1/z is linear in screen space and can be swept using the 8 blue bits. These four layers can be composited very quickly by:
[1] draw the monster texture layer into BMPD1
[2] draw the map texture layer into BMPD2
[3] draw the map 1/z-buffer into BMPD3
[4] draw the monster 1/z-buffer into BMPD3 using Blendmode.SUBTRACT // clever step #1
The effect? Wherever the monster 1/z-buffer is greater than the map 1/z-buffer, this clamps to a zero in the blue channel. That is, when the monster occludes the map, we get a zero. Otherwise, the map occludes the monster.
[5] do a threshold operation:
BMPD2.threshold( BMPD3, "==", 0x00000000, 0x00000000, 0x000000FF, false);
Threshold is a strange function, it took me a lot of time to figure this part out. What is happening here is we are searching for the zeros of the blue channel of BMPD3, and using it to blank out pixels in the map texture, by alphaing them to zero.
[6] do a draw operation (or copypixels, take your pick)
BMPD1.draw (BMPD2).
This overwrites the monster texture layer with map pixels, _except_ where they have alpha=0. So we've basically made cutouts in the map layer than now expose the monster pixels.
[7] BMPD2 contains the finished frame - blit it to screen however you like.
Other than the fact that it's only 8 bits, it works pretty nicely. It's way quicker than pixel bender and its quite a bit faster than any other bitmapData approach I tried. (compare, paletteMap, and copychannels are pretty sluggish compared to draw, beginBitmapFill and copyPixels). The 8 bit limitation comes from the Blendmode.SUBTRACT step, because it's clamping semantics won't work across channels. It might be possible to extend this scheme to slightly more precision, but probably it will cost more to composite.
Anyway, enough talk and on to the goods. Here's the first monster I ported in, he looks kinda familiar.
Here's what the zbuffers look like (monster zbuffer, map zbuffer, result of BlendMode.SUBTRACT, and final image).
And here's what the final image looks like, once you've blown it up by 2 to fill the screen (800x600).
To summarize the sorting properties of this code:
1. Maps sort flawlessly using a combination of portal rendering and local BSP's between the brushes that exist in a common cell.
2. Monsters self-occlude/sort against themselves flawlessly, because they're BSPs too. Even when monsters are articulated/moving, you can still accomplish this by storing each frame of the walkcycle as a separate mesh and store them as distinct models.
3. Monsters sort pretty well against the map, the only problem is a lack of zbuffer resolution but this can be managed somewhat through careful map design.
3. (The only negative) Interpenetrating monsters do not sort 100% correctly. This is because they don't get z-composited individually, they get drawn back-to-front into a single buffer and then the whole stacked mess gets z-composited against the map in that 7-pass scheme. In practice, this will not be noticed very often. (Pinball Racers did a similar back to front step and sorting errors are hard to spot when you have sparse and separated geometry).
Here's a demo to play with (finally, right?). Shooting for 20 frames per second, and I think my computer is weaker than some of the others around here, so it might be quite speedy on some platforms. This can become a game for sure - it looks pretty and plays decent.
You'll need the flash10 debug player (or maybe the plugin) to play it. I am gunshy about installing the newest plugin, so I just use the standalone debug player available at:
(...and super thanks if you try playing it and post a FPS quote! If you do post a quote, try to use the same spot where I screenied from, because scene complexity really matters and that's the worst case)
EDIT: Guess I should do more fact-checking before I post random links into adobe.opensource - that is clearly not the same version of the debug player as I have been testing on. (DrawTriangles used to ignore linestyle, now it heeds it :shrug: ) Normally I'd piss and moan, but I actually agree with the change. Will post a corrected demo later. (I would just host my version of the debug player on my website, but that seems rude / un-EULA-like).
Although the ability to tile textures is a planned feature for graphics.drawTriangles, it's not yet implemented in the beta AFAIK. Back in post #53, I had already coded up a workaround: with some uv fiddling and bitmapData.copypixels, the small 64x64 textures are tiled in an auxiliary bitmapData which is then fed into drawTriangles, pretiled. That's the reason these demos consume so much memory - every polygon is doing this individually, so there's a _lot_ of copies of that 64x64 texture floating around.
This might not be such a bad idea though, because it lets you composite other artwork (bulletholes, liquid splatters, damage) and make a more interactive environment. I'm finding that another good use for this surface is it's a handy place to pre-alpha-blend your textures with black in order to fake a lighting model.
After probing into that idea, I think it's a big winner. For each cell, the user will be able to tag one lighting origin. Right now just the centroid of the cell is used. When the surface bitmap is tiled up from atomic textures, the texture is mixed with black using a basic falloff with radial distance. What's nice is that one omnidirectional light source will yield a simple circular highlight on the surface. This can be rendered quickly into a sprite as a radial gradient fill, then use bitmapData.draw to composite that sprite onto the surface texture. A second pass, with a bit more math involved, models the deep shadows that should be cast on cell walls by brush surfaces. Raycast points onto the cell surface, starting from the light source and passing through the brush vertices. Compute the convex hull of these points in 2D (this is fast), and then soften with a blurfilter to make the shadow boundary more gradual.
Here's a scene without lighting:
Here's what it looks like with lighting and white paint everywhere:
Here's what the real lit scene looks like:
Has a lot more life to it, I think!
If the light origin doesn't move, the lights don't change, and there is zero runtime expense for doing this. Currently every surface is built when the map is instantiated, and hangs around forever. Even that initial step is very quick. Ultimately, there will be a need to dispose of these surface bitmaps when they are no longer in the scene, to reduce the memory usage from what it is now (which is too high IMO). Once this caching system is in place, there will be modest runtime expense, whenever a surface needs to be rebuilt for rendering but is currently in the disposed state. But when you amortize that cost over however many frames it continues to be used, it's effectively a very small penalty. All in all, this is very similar to how quake 1 did it's lighting ( http://www.bluesnews.com/abrash/chap68.shtml )
Other random changes:
* hitscan weapons are supported, you can put bulletholes in the walls
* redid collision detection (again!) for greater robustness
Up next:
* adding physics attributes, basic particle rendering & updating (thinking of the wall-sparks from doom-a-like)
* graduation (!)
Reply With Quote
You set the bar high.
Originally Posted by realMakc
I always say, competency is only rewarded with additional work.
