A Flash Developer Resource Site

Page 2 of 7 FirstFirst 123456 ... LastLast
Results 21 to 40 of 131

Thread: [WIP] Flash quake/descent style renderer.

  1. #21
    Senior Member realMakc's Avatar
    Join Date
    Oct 2002
    Posts
    927
    Quote Originally Posted by rachil0
    From the very 1st post... Judging from the screen shot, this is exactly what you did.
    I thought that was about 2nd swf.

    Quote Originally Posted by rachil0
    Another idea... Do either PV or Away3D already do this?
    Don't think I have heared of this anywhere.
    who is this? a word of friendly advice: FFS stop using AS2

  2. #22
    Senior Member rachil0's Avatar
    Join Date
    Jul 2007
    Location
    Columbus, OH.
    Posts
    465
    Time for another update. Did a significant overhaul of the rasterization alg. and I am pretty pleased with the results. Before, the frame was being built using 1 byte palette indices which placed into a byteArray one pixel at a time. The byteArray was then pushed into a bitmapData and promoted to a 32-bit image using paletteMap. The real problem with that is you can never reach high resolution images, because the pixel fill rate is just too slow.

    I had played around with beginBitmapFill in the past and found it to be really speedy. So I redid the engine to use beginBitmapFill to write long spans of pixels, instead of all that byteArray business. The result is that you can now push out an 800x600 32bpp frame in _less_ time than it was taking to do a 320x200 8bpp frame. I look at this demo and it doesn't even look like flash to me anymore, almost like an N64 or PS2.

    Naturally it's not perfect. There are still noticeable perspective errors if you look for them, especially when you roll the camera (which I will leave in the engine, but I think games should not permit this particular degree of freedom).
    And the "inking" that is applied around all the polygons is not just aesthetic - it's essentially covering up nasty jaggies/dropouts that occur at gaps between bitmapFill calls (when not controlling the rendering at a pixel by pixel level, it's tough to get complete fill-in without leaving a gap here and there)Personally, I think the ink looks attractive and would probably turn it on even if it was non-essential.

    One thing I noticed, that I think is worth sharing with the community at large, is a quirk with beginBitmapFill. It is dramatically faster at drawing large-x/small-y shapes than drawing small-x/large-y shapes. (For example, a 200x20 rectangle will be filled much faster than a 20x200 rectangle). This makes some sense from a cache-coherency point of view, because on some level a Graphics handle is just a linear framebuffer, and that framebuffer is probably x-major if it's like any other framebuffer on earth, so x-major shapes will have more cache hits. So the fact that one direction renders faster is not surprising to me - but the magnitude of the speed difference is astounding. When doing a full-screen fill, I've found that using 800 vertical strips is about 10(!) times slower than using 600 horizontal strips.

    This difference is so pronounced that I think rendering in vertical strips is performance suicide. But if you look at the quake code in debug mode, there is clearly some vertical strip rendering going on. But in fact, all the vertical strips are actually being drawn horizontally to a hidden off-screen graphics context, then captured into a bitmapData using draw(), then transposed back into vertical strips using a beginBitmapFill with an appropriate matrix. This is actually faster than drawing the strips vertically in the first place (which I find unbelieveable). That's another reason there are ugly drop-outs - rotating parts of the frame around makes it very difficult to establish a correct scanline fill convention - I didn't even bother, just covered up the errors instead.

    [This process is pretty interesting to see in action, you can watch it by editing Viewport.as, lines 44-46. "v_scanlines" holds the hidden offscreen graphics context which is transposed, and "v_finished" holds the finished product. You can change which one you get to look at by commenting in&out those lines.]

    Enough yammering, the full source is zipped at:

    http://esl.eng.ohio-state.edu/~rac/quakehighres.zip

    There's a pre-compiled .swf in there as well.

    Controls: d-pad changes yaw/pitch, shift/ctrl changes roll angle, space scoots forward, enter turns on debug mode.
    Last edited by rachil0; 01-09-2008 at 01:44 PM.

  3. #23
    Senior Member rachil0's Avatar
    Join Date
    Jul 2007
    Location
    Columbus, OH.
    Posts
    465
    EDIT: One last thing - for a real sense of what got improved, compare the image quality and speed difference between this demo, and the demo from post#8.

  4. #24
    Script kiddie VENGEANCE MX's Avatar
    Join Date
    Jun 2004
    Location
    England
    Posts
    2,590
    Wow... just... wow.

    60 FPS.

    SIXTY FPS!!

    And I wouldn't worry about the strokes; I actually didn't even notice everything was outlined until you pointed it out,
    http://www.birchlabs.co.uk/
    You know you want to.

  5. #25
    Student
    Join Date
    Apr 2001
    Location
    -
    Posts
    4,756
    very impressive indeed,- keep it up

  6. #26
    Senior Member realMakc's Avatar
    Join Date
    Oct 2002
    Posts
    927
    Hey Ryan, interesting find with fill. I think you need to re-package it (and for this purpose, give it a name) and put on svn somewhere. Hey, Max did, so why don't you?
    who is this? a word of friendly advice: FFS stop using AS2

  7. #27
    ism BlinkOk's Avatar
    Join Date
    Aug 2001
    Location
    , location, location
    Posts
    5,002
    very nice dude. super quick
    Graphics Attract, Motion Engages, Gameplay Addicts
    XP Pro | P4 2.8Ghz | 2Gb | 80Gb,40Gb | 128Mb DDR ATI Radeon 9800 Pro

  8. #28
    Junior Member
    Join Date
    Jan 2004
    Location
    Bordeaux, France
    Posts
    17
    Hello.

    Amazing demo and piece of code !! Wonderful work that you've done. Congratulations.

    If I may, I'd like to ask you few questions

    - From what I see in your code, there's no advanced sorting algorithm used. It seems like a classic painter algorithm. But I also see an SAT algorithm there. Is it used, how does it improve a way you sort polygons?

    - Is the collision's done with a ray approach, or the SAT?

    - I'm amazed by the quality you obtain here. There's no use of the Palette in that exemple I'm right.

    As Makc said, this kind of prototype is extremly helpful. Why don't you consider to join an existing group (as Sandy ) or create your own project? I'm sure some extremly interessting things can come out from this.

    And I totally agree with your comments and inlined code. Flash doesn't like at all functions call in expensive routines.

    Keep continue.

    Thomas
    Sandy3D, open source Flash 3D engine.
    http://www.fashsandy.org

  9. #29
    M.D. mr_malee's Avatar
    Join Date
    Dec 2002
    Location
    Shelter
    Posts
    4,139
    great stuff
    lather yourself up with soap - soap arcade

  10. #30
    FK founder & general loiterer Flashkit's Avatar
    Join Date
    Feb 2000
    Location
    Sydney
    Posts
    1,149
    yeah I'm pretty gobsmacked by it, well done. Now bring on the games with it... does flash quake = flake? or do we get floom instead?
    Regards Mark Fennell - Flash Kit Founder, general loiterer
    -------------------------------
    I Hate Zombies - iPhone Game | markfennell.com

  11. #31
    Senior Member realMakc's Avatar
    Join Date
    Oct 2002
    Posts
    927
    Quote Originally Posted by Flashkit
    Now bring on the games with it.
    Somehow this bit is the most underdeveloped in flash world. Not saying that there is no games, but where are their engines? All kept private at best, or do not reall exist as such.
    who is this? a word of friendly advice: FFS stop using AS2

  12. #32
    Student
    Join Date
    Apr 2001
    Location
    -
    Posts
    4,756
    with experimentation comes expierence,- not everyone aims for a complete game at the end

  13. #33
    Senior Member rachil0's Avatar
    Join Date
    Jul 2007
    Location
    Columbus, OH.
    Posts
    465
    Thanks for all the encouragement everyone! Makes it easier to justify spending more time on it.


    Quote Originally Posted by kiroukou
    Hello.
    - From what I see in your code, there's no advanced sorting algorithm used. It seems like a classic painter algorithm. But I also see an SAT algorithm there. Is it used, how does it improve a way you sort polygons?
    The fundamental drawing operation of the algorithm is texture mapping a convex region of the screen, with respect to a set of convex "holes" (regions of the screen which should not be touched). [This operation is performed by TextureMapper.textureVertical and TextureMapper.textureHorizontal, they are two functions with identical signatures, and could be used interchangeably.]

    There's no dedicated visibility data structure like a BSP tree, instead the algorithm is a portal renderer, much closer to descent than quake in terms of how visibility is established. The easiest way to visualize how a portal renderer works is to imagine you are trapped inside a cube and look out. Since the camera (you) is inside a convex polyhedra (the cube), it is impossible for any one of it's faces to occlude any other. Each face of a convex polyhedra is also convex. So they are all passed into the texture mapper, with no holes and the frame is completed. [MapPolyhedron.render performs this algorithm.]


    Of course a single cube is a boring map. Imagine on one of its faces, we cut a triangular (convex) hole, which leads to an neighboring cube. The portal renderer first draws the contents the original cube, when it hits the triangle hole in the wall, the texturemapper is instructed not to draw inside of it. Once that chamber is done, it uses the screen projection of the triangular hole as the clipping region for the next cube. [By restricting yourself to convex portals, these clip operations are straightforward to implement - ClipPolygon.as handles all the clipping]. This is the classic portal renderer, it draws one convex chamber at a time, recursing deeper into the map structure (and possibly branching) everytime a portal is encountered. The algorithm terminates when none of the portals that exit a chamber lie inside the portal that exposed that chamber. (If that makes sense).

    I extended this approach. The original portal renderer lets you build up complicated geometry as a union of chambers (like you're tunneling your map out of solid rock). I added "brushes", which are also convex polyhedra, which allow you to add material back into the volume carved out by a chamber. (A brush must lie entirely inside one chamber). The SAT is used to determine occlusion relationships between all the brushes that lie inside a chamber. So each chamber has it's own table of brushes, and it's own table of separating planes between the brushes. This table is static because brushes don't move. [This table is built by MapSector.generateAxisTable and the SeparatingAxis class].

    So now, instead of the renderer drawing a vacuum chamber, it first draws all the brushes in. Since each brush is a convex polyhedra, it's projection in screen space is a convex polygon, and we can compute this polygon by taking the convex hull of it's vertices. [clipPolygon.createConvexUnion does this operation in screen space]. Because of how the textureMapper works, we can draw brushes in arbitrary order - whenever a brush is being textured, we just need to pass in a list of hole regions, where each hole is the 2D projection of an occluding brush. No particular front-to-back or back-to-front painting order is required. [MapSector.render implements this algorithm].

    Once all the brushes have been drawn, now we can draw the chamber just like we did before. To prevent the walls from painting over the brushes we just painted, each chamber wall is passed the entire list of brush projections -so wall doesn't get drawn in those regions. When we recurse deeper through wall portals, the brush projections still get passed along as holes, so that deeper chambers and brushes will respect them and not draw back over them.

    The advantage of this whole scheme is that each pixel is filled once, but the disadvantages are that the texture mapping routine gets pretty complicated. When there's a lot of brushes choking off regions of the screen, I think a lot of CPU is being used to determine where a scanline starts, stops or has holes.

    Quote Originally Posted by kiroukou
    - Is the collision's done with a ray approach, or the SAT?
    The collision is done with a ray approach. This algorithm is implemented in MapSector.move and MapSector.addEncroachingSurfaces. The basic idea is that whenever you try to move, you have to make sure you didn't walk outside of the convex chamber (this is easy) or inside a convex brush (also easy). The hardish part is detecting when you are moving through a hole to another chamber.

    Quote Originally Posted by kiroukou
    - I'm amazed by the quality you obtain here. There's no use of the Palette in that exemple I'm right.
    It's 32 bit color from coast to coast (input texture to output image). The lighting is done by making a table out of each texture, which stores the texture at 32 different light levels. The texture mapper then picks which lighting level to use for each span.

    Quote Originally Posted by kiroukou
    As Makc said, this kind of prototype is extremly helpful. Why don't you consider to join an existing group (as Sandy ) or create your own project? I'm sure some extremly interessting things can come out from this.

    And I totally agree with your comments and inlined code. Flash doesn't like at all functions call in expensive routines.
    Maybe I'll look into that in the future. For now, the source code will be available at that same URL. I'm a total noob when it comes to setting up SVN or CSV tools.

    Quote Originally Posted by realMakc
    Hey, Max did, so why don't you?
    Funny you should mention him. I showed it to him and he was like aww crap, now I gotta make mine better. There is some good natured one-upsmanship going on there. It's one of the rare times I've met someone on the internet and then gone on to get to know him out here in flesh-space. (He goes to OSU just like I do).

  14. #34
    Senior Member rachil0's Avatar
    Join Date
    Jul 2007
    Location
    Columbus, OH.
    Posts
    465
    Quote Originally Posted by Flashkit
    yeah I'm pretty gobsmacked by it, well done. Now bring on the games with it... does flash quake = flake? or do we get floom instead?
    Of the two I'm partial to floom

    But I think the ultimate exercise in bad obscure puns would be to make a clone of HL2:Portal, since this a portal renderer to begin with.

  15. #35
    doItLikeThis
    Join Date
    Jan 2004
    Location
    :noitacoL
    Posts
    1,080
    Amazing stuff rachil0, keep it up mate
    -Aditya

  16. #36
    Senior Member realMakc's Avatar
    Join Date
    Oct 2002
    Posts
    927
    Quote Originally Posted by rachil0
    And the "inking" that is applied around all the polygons is not just aesthetic - it's essentially covering up nasty jaggies/dropouts that occur at gaps between bitmapFill calls (when not controlling the rendering at a pixel by pixel level, it's tough to get complete fill-in without leaving a gap here and there)
    Ah, but with K = 0.5 this is no problem, right (except that you should perhaps add few pixels to compensate for rounding errors and ensure that walls overlap (better than occasional 1px gaps))... so why dont you treat 1st and last items in hciStartQueue (?, I mean first and last pixel spans in a row) as if there was K = 0.5 set for them, and subdivide them in thin strips? frame rate will drop, but not that much as if K was always 0.5

    Quote Originally Posted by rachil0
    I'm a total noob when it comes to setting up SVN or CSV tools.
    I could help you set up google code stuff if you are that technology-friendly
    Last edited by realMakc; 01-11-2008 at 04:44 AM.
    who is this? a word of friendly advice: FFS stop using AS2

  17. #37
    Senior Member rachil0's Avatar
    Join Date
    Jul 2007
    Location
    Columbus, OH.
    Posts
    465
    Quote Originally Posted by realMakc
    Ah, but with K = 0.5 this is no problem, right (except that you should perhaps add few pixels to compensate for rounding errors and ensure that walls overlap (better than occasional 1px gaps))... so why dont you treat 1st and last items in hciStartQueue (?, I mean first and last pixel spans in a row) as if there was K = 0.5 set for them, and subdivide them in thin strips? frame rate will drop, but not that much as if K was always 0.5
    Hehe someone has been digging in the code. Yes, the rasterization is essentially perfect for K=0.5. (You could actually simplify the code quite a bit if you used K=0.5 all the time, but picking bigger K is what makes the code faster). The thickness of the ink was controlled by K, so at small K you got thinner lines. But I think that got clobbered in a refactor (the inking functionality was moved out of the TextureMapper and into a new "Inker" module, and I forgot to make inkwidth depend on K).

    I did try something like you are suggesting. Instead of refining K near the edges, I drew the first & last spans as little trapezoids that aligned correctly with the edge of the polygon. It was buggy, but it looked good and the bugs could've been fixed. However it also exposed another problem that would take another pile of code to fix. When you're drawing a strip of wall that's supposed to be occluded by tip of a brush, you need to chip a little bite out of the middle of a span, otherwise you will overwrite this tip, and sort of chamfer it off. You could always try painters algorithm, draw the wall first and the brush later so that you don't overwrite its corners, but that's a significant change and might have performance penalities.

    Both of these problems could be fixed, no doubt, but I did not want to throw so much code at the problem. Even getting the ends drawn correctly was a significant change to TextureMapper and the ClippingItem classes, I expect coding around that overwrite/chamfer case would require even more substantial changes. The strips that you are drawing can end up with funky shapes. I can pm the code that I have for it if you'd like to take a stab at it, but me=lazy and thicker ink=easy fix.


    Quote Originally Posted by realMakc
    I could help you set up google code stuff if you are that technology-friendly
    I have another project in the fire, maybe I can take you up on that offer once I get back around to this code again (estimate mid-march).

  18. #38
    Senior Member realMakc's Avatar
    Join Date
    Oct 2002
    Posts
    927
    hmm. commenting inker out was the 1st thing I did, actually, even before I went to replace CS3-incompatible textures. IMHO, getting brush tips chopped off would not be that visible when you are trying to run away from two guys with BFG. once upon a time I used video editor to cut some frames out of matrix 2 scene with agent smith and ravens, and to my surprize, I have found that most of birds were half-transparent and otherwise inaccurate. fx team cheated, but noone notices because that's not what people are looking for in the scene.
    who is this? a word of friendly advice: FFS stop using AS2

  19. #39
    Senior Member rachil0's Avatar
    Join Date
    Jul 2007
    Location
    Columbus, OH.
    Posts
    465
    Had a chance this week to revisit this project and thought I would share the progress - a quasi-functional solid modeler for editing levels! You can now fly around a map and carve up interesting structures in an interactive manner. Originally I planned to make this editor just for monsters/game entities, but the more I thought about it, I wanted to reuse it for the environment/map too. I decided to implement a map export routine first, because it has more immediate impact on the project.

    The internal representations for geometry used by the editor and the maps in-game are totally different, because the editor makes no effort to solve the visibility problem (i.e. what fragments of polygons are visible from what areas of the map). This is deliberate. It's too hard for the user to bookkeep / construct this information as they go. More than that, I want the editor to be agnostic to the final use of itsgeometrical data so I can reuse it to build monsters later. An unfortunate side effect is that the editor will probably never be integrated ingame. It's still very rough and the user interface is minimal, but it does have the bare essentials to start making maps:

    Current features:
    * Loading and saving of geometry to XML strings.
    * Exporting geometry to a quake-a-like compatible format. This includes the steps of classifying polyhedra into cells and brushes, and carving portals into polyhedra where they have some overlap between coplanar facets.
    * Interactive creation of vertices and polygons to help shape a level free hand.
    * Extrusion of polygons into roamable cells or solid brushes.
    * Clipping polygons and polyhedra against cutting planes. This will be a key algorithm for making monster-y models that self-occlude correctly, wanted to get it right early.
    * Reversing polygons handedness - useful for turning brushes inside out, transforming them into cells.

    Some features that are planned:
    * Dialogs for assigning textures / UV coordinates to each polygon. This is the next task, it has heavy GUI requirements that will take a while to slug out.
    * More "construction" dialogs, like creating reference vertices or reference axes for landmarks for later processes.
    * More geometry transforms: mirroring across an arbitrary plane, rotation about an arbitrary axis, translation, scaling relative to a base point. With the editor framework pretty established, this will be straightforward to add.
    * More procedures for generating polyhedra - the only way to make them now is via extrusions or cutting an existing polyhedra against a plane.
    * Quick-load and quick-save to an internal stack, so a user has a history of their model easily accessible without constantly copy/pasting the xml text.
    * Insert pre-existing geometry into the map directly. So you can make one "door" or "stairway" feature and copy/paste/transform it into other spots. This is very easy to implement.
    * Export to a new format suitable for avatars/monsters/other. I have a pretty good idea of how to do this interactively with a user using a BSP tree.

    There's some example maps that you can load in the editor that test various aspects of the rendering engine or export algorithm. Each map was done completely inside the editor, so it's definitely possible to make something playable.
    * fourroom.xml - first map I made that tests the simple cases of the export algorithm
    * portaltest.xml - tests various cases of portal extraction
    * freehand.xml - tests the most degenerate case of portal extraction
    * nesting_test.xml - tests some of the CSG aspects of the pipeline, making cavities, backfilling them with brushes, then cutting back into the brushes to make a crude prison cell shape
    * nesting_brush.xml - a slight mod of nesting_test that probes one final path in the export algorithm (where a solid brush is geometrically contained within more than one cell, and a decision must be made as to where it goes)
    * klein.xml - an example of the quirks of portal rendering, making a weird kleinbottle-esque (sp?) shape. This is a perfectly well formed map despite being physical impossible. Causes some funny visual glitches in-game.

    To view these different maps in-game, clobber input.xml with the contents of the one you want to see. To see them in the editor, use File>Load and type them in. Don't mix and match the xml files in /quake and /editor, they are formatted very differently.

    Since I've got more test data to run the renderer on, I've also discovered some bugs that need investigating. Freehand.xml seems particularly bad about polygons dropping out. There's also random times when clipPolygon.createConvexHull barfs unexpectedly. I will be searching through and fixing these problems in the future. I suspect they are both related to tolerance settings when testing geometrical predicates.

    Here's some screenshots of fourroom.xml in the editor, and in-game. Sorry they're so big.




    Full source for both codes (editor&renderer) available here.

    It's a lot to digest but I know some of you 3D-heads around here will enjoy poking the program around and seeing some results. I can elaborate as to how the example maps were created in a future post. Vaguely, it all boils down to (i) creating vertices in a specific plane to (ii) building polygons freehand (iii) extruding that polygon to either an offset plane or a preexisting plane on another polyhedra.
    Last edited by rachil0; 05-30-2008 at 10:58 PM.

  20. #40
    Student
    Join Date
    Apr 2001
    Location
    -
    Posts
    4,756
    that´s sick and neat at the same time

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  




Click Here to Expand Forum to Full Width

HTML5 Development Center