Been poking around with this idea for a week or two and I finally came up with something that works OK. It's a first-person-style renderer than can handle arbitrary geometry and spit out a perspective correct scene regardless of view orientation. Well, almost perspective correct: correction is done every 32 pixels. The previous doom-a-like faked the elevation rotation, but this code handles that case and you can even roll the whole viewport about the camera line-of-sight. This is pretty disorienting ... makes me remember why I sucked so bad at descent.
The scene is pretty simple and the camera just moves along a fixed track, but I expect this code will scale much more attractively with scene complexity than the doom-a-like. Although no lighting model is in place yet, adding doom-style sector lighting will be essentially free. The lighting buffer is already being filled, but it is being filled with uniform brightness (for sector-based lighting, filling the lightbuffer is much more expensive than computing what goes in it). I intend to experiment with more complicated lighting models too, like directional lights and maybe bumpmapping too.
Just like in the doom clone, rasterization is done by pushing one pixel into a bitmap at a time. I really wanted to get a papervision style subdivision scheme to work. But to get a decent approximation to perspective correct, surfaces had to be subdivided really deeply, and the end result was a huge number of tiny triangles being rendered each frame. It was ultimately slower than just doing the rasterization pixel by pixel. However, I think that affine texture mapping via graphics.beginBitmapFill will work _great_ for rendering 3D polygonal enemies, because they will far enough from the viewpoint that there is little variation in z over their entire extends. As I recall, both descent and quake used affine texture mapped enemies, and you can hardly notice. In short, I don't think displaying enemies on the screen will load the engine very heavily at all. on the other hand, clipping them against the view portal might be somewhat costly.
I will post source code after I clean it up a bit, the design is very disorganized at the moment. In the demo, you can use the arrow keys to rotate the viewpoint around. You can also use shift/control to roll the whole viewport around (don't get dizzy!). This is the easiest way to see how perspective is approximated... just roll the view 45 degrees and you'll see these artifacts where the texture sort of ripples on the surface. This is a worst-case viewing situation - ugly but tolerable. Hitting the spacebar toggles debug lines in and out.
Bug reports and performance quotes are welcome feedback.
Guess there's not a lot of interest in something that's still so primitive, but here is source code anyway.
The key algorithms are:
Viewport.redraw
ClipPolygon.clipToWindow
MapPolygon.refreshClipPolygon
TextureMapper.textureHorizontal (which relies heavily on HorizontalClipItem)
TextureMapper.textureVertical (which relies heavily on VerticalClipItem)
Implemented a new feature while I cleaned - surfaces can now have subholes in them. Should make it easier to make complicated rooms / windows / doors with fewer total polygons/brushes.
I think it´s very intersting,- but it´s not that much more different as the previous thread of yours.
The last source of your demo had loooots of classes and was almost impossible to digg into for someone else.
Any plans on restructuring your code?
might have a look at the source in my little freetime sometime.
but a question that interests me more,- can your work with existing editors for doom and use those map data with your engine right now?- or how do you for example build the levels- rather code wise? or with a simplified editor?
* Cells of the map can now support solid "Brushes" which add matter back into the Cell (the Cell itself can only model a vacuum). The list of Brushes contained in each Cell is built up into a SceneGraph, which is sorted with respect to camera viewpoint every frame (using the separating axis theorem as the sort comparison). I think that for a little bit of extra processing, Brushes could be allowed to move within a cell to make moving bits of map (quake did this in a few spots, as I recall). Brushes will eventually move to make things like elevators and doors.
Just like the surfaces of a Cell, the surfaces of a Brush can support holes which lead to other Cells (which can then have their own Brushes, ad infinitum). It makes for a very neat system like constructive solid geometry, where you cut out vacuums add back in solids in a heirarchical fashion to define the map geometry. I think it will be much easier to use than the old approach (which was stricly a union of vacuums, you were always cutting away and could never add back in). The example map is 2 Cells and 1 Brush - in the previous version of the code, modeling it would have required about 25 (or more!) Cells. There is still _zero_ overdraw. Each pixel is drawn exactly once. (Well almost - I think because of rounding errors I sometimes get two writes at the shared edge between polygons with opposing rasterization directions... but that's the only possibility and it will be fixed eventually).
* Added lighting features like uniform lighting everywhere in a Cell, depth cuing (fogging distant surfaces) and directional lights which you can place and point at a wall. Example swf has two directional lights - one that points up at the ceiling like a wall sconce/torch and one that points at the wall like a flashlight that a player might hold. Positioning and orientation is arbitrary and can change at runtime with no extra cost.
Still no effort to implement monsters - I have ideas on how to do it, but its going to take a while to figure it all out. Maybe that's next, who knows.
EDIT: Eventually I would like to do map editors for both the doom-a-like and the quake-a-like. I don't see me writing any converters to import old doom/quake maps into either code - I have no idea how to do that. Despite their graphical similarities, neither of these engines works very much at all like quake or doom (which are BSP-traversers - both of my codes are portal renderers). The only retro game that it would be practical to implement a map converter for, would be descent. It was a portal renderer, dealt strictly with distorted cubes, and had no CSG semantics like brushes. It would be a straightforward 1:1 mapping between descent cubical volumes and "Cells" in this engine.
can't believe i missed this! soooo very cool... it's nice to see a comparison-based example of some of the stuff you're achieving. i usually write off 3D stuff as hopeless stabs at something flash player can't support quite yet, but this (and especially the Doom-a-like you link to) run amazingly. VERY impressive.
Originally Posted by renderhjs
The last source of your demo had loooots of classes and was almost impossible to digg into for someone else.
could not disagree more. although your preemptively tabbed curly braces look a bit awkward...
to rachil:
You´ve achieved something quite nice so far. I think there are a few reasons why you´re not getting more feedback and support:
-This is complex matter not every newby can easily jump into to understand right away.
-The more experienced developers are often busy with other things so they often aren´t into delving through tons of classes to make a sense out of it either
I think you´d get much more feedback and people jumping in on the project if you created an online documentation of the classes and a quick start tutorial on how to get going with the source.
Personally i think from just having a look at the swf you´re up to something really cool there, i just don´t have the time to dig through all the classes to appreciate, extend or even just use the code base.
also: if you´d really like to have more and more developers jumping on board you should also think about putting the project on osflash.org and code.google.com.
And yup,in next steps you should also restructure the classes to form an easy to use api, have them logically sorted into packages etc, have method setups which are easy to understand and as close in usage to other known apis as possible etc, all that typical "how to set up an api nicely" mumbo jumbo.
could not disagree more. although your preemptively tabbed curly braces look a bit awkward...
Haha, that's a quirk I picked up. I like it when every scoped pair of braces lines up on the same column. Helps me match em up, but I think I am the only person on the planet with that habit. I'm also terrible about switching between mixedCase names and underscored_names - influence from multiple conflicting environments has clobbered my brain on that point. Even in the same function, I use both conventions all the time.
Originally Posted by tomsamson
restructure the classes to form an easy to use api, have them logically sorted into packages etc
I'm still wrapping my brain around the package directive, it strikes me as sorta like namespaces. I never really got into that habit. The code is pretty amorphous, I am currently looking for ways to cut it into cleaner parts.
Thanks for the feedback, and here's a new update.
* Code for ordering Brushes within a Cell was totally redone - the old code was broken. The separating axis theorem works great to establish drawing order between two things, but it's conservative and can sometimes say 2things occlude which really don't. When a sector had >2 Brushes, it was possible (likely) to have a cyclical list of occluders which would deadlock the drawing process (Brush A needs to be drawn before Brush B, B needs to precede A, but wait oh C needs to go before A.. barf). Since this was the first time I really did anything serious in 3D, I didn't even realize this was a possibility. Now brushes are drawn in the same order regardless of who occludes whom. To get z-sorting right, every brush gets a list of every other brush, and using the SAT it can cut holes out of itself for all the other brushes that are infront of it. So it doesn't overwrite an already drawn brush or needlessly write into a spot that will be later overwritten by an occluding brush. Still zero overdraw - the same drawing calls are being made, they're just happening in a different order.
* You can move the camera now, instead of it just wandering on a boring fixed path. It's a no-brainer to move the camera according to keyboard input, the real challenges are (1) clipping your movement against the map so you can't walk through walls and (2) making the handoff as you migrate from one Cell to another. I think it's worked out but bugs may persist. It's a little wonky when you a riding a wall and then switch Cells - can have a little jump/hiccup. I still never solved this probably correctly in 2D/doom, so who knows what happens in 3D/quake!. Still far from a game, but one problem at a time.
Controls : up/down/left/write pans the camera, space scoots you forward (fixed speed for now), enter turns on debug lines.
Good lord thats brilliant...there's so many games you could make with that. With the free roaming capabilities of the camera the first game idea that came into my head was not a FPS but a dogfighting game. Hmm...
I really wanted to get a papervision style subdivision scheme to work. But to get a decent approximation to perspective correct, surfaces had to be subdivided really deeply, and the end result was a huge number of tiny triangles being rendered each frame.
the number will be only big for triangles viewed from edge. those viewed from above (perpendicular to line of sight) will not require any subdivision at all. sandy has recently ported away3d PreciseBitmapMaterial - what makes me mention this is that Thomas (sandy developer) tried to adapt Andre Michelle's cubicvr setPixel-based approach and ended up with lesser fps.
Not sure I agree with that. You are correct in saying that you can get away with no subdivision when the camera direction is normal to the surface. But in a FPS, it seems to me like viewing things edge-on is the rule, not the exception. If I am sitting in the center of a cubic room and looking directly at one of the faces, sure there's one face that requires no subdivision, but there's four faces that do. As soon as you look at some arbitrary angle, you need subdivision on all the faces again. Even in a doom or wolfenstein restricted world you still only have one affine direction, the other direction needs perspective correction. (So instead of approximating perspective correction by drawing little equilateral triangles, you can get exact perspective correction by drawing long strips of pixels).
There was one other thing that I wanted to try but never got around to. In a game like doom, the walls have constant z along the vertical axis and the floors have constant z along the horizontal axis, so affine rasterization can be done along those axes. But even on an arbitrarily oriented 3D surface, you can always find lines of pixels which share the same z-depth from the camera. The catch is that these lines can be arbitrarily oriented on the screen (they don't line up with a horz or vert scanline anymore). There was a trick called free-direction texture mapping which combined bresenhams line algorithm and this constant-z property to write arbitrary lines of pixels in a fast affine inner-loop. I've never implemented it, it sounds pretty tough.
But I think you could use a similar idea with the flash beginBitmapDraw routine. You only need to subdivide triangles deeply along the gradient of z (the direction orthogonal to the line of constant-z). Along the other direction, I think your triangles could have extremely long edges before you started noticing perspective error. Ultimately you could fill the screen with fewer long&skinny triangles instead of lots of equilaterial triangles (which is what this demo does).
I wanted to implement this for comparison but never got around to it. It wouldn't be a huge number of changes from the pvquake demo, but my gut feelings make me not want to do it, for two reasons. The first is that I have no idea how to integrate directional lighting into that approach. I think you could cajole the flash renderer into doing gouraud (sp?) shading over the screen triangles (by rendering black, partially transparent "mask" triangles over the texture layer, and filling them with beginGradientFill with a linearly varying alpha). The catch is that if you're drawing huge triangles, your lighting function is undersampled and then linearly interpolated. So any fine details in lighting, like a circular hotspot from a nearby directional light, are going to be ignored. Unless you subdivide based on lighting too... but then you're back to square 1 with lots of equilateral triangles.
The second reason is that fast rasterization is only half of the problem, the other half is handing occlusion efficiently. If your map volume is a union of convex cells, then all of your drawing regions are also convex even when they are occluded by other walls. It would be easy to program the long&skinny subdivision algorithm for this case. However, if you want to do CSG-style solids ("brushes" in the prior post), your drawing regions are now non-convex polygons, possibly with holes (yuck!). I think it would be really tricky to program subdivision for this case - the pvquake demo I gave does not even touch this problem. The easier to program alternative is to do just overdraw things, by drawing the cell and then painting the brushes back over top the cell walls. I think that would be slow. But when you're doing pixel by pixel rasterization, all this is a non-issue. You handle the funky polygon scanline by scanline in a 1D fashion, instead of trying to tesselate it into some union of triangles in 2D.
Ultimately, pixel by pixel rasterization (or scanline by scanline) seemed to gel so nicely with the map data structures (cells+brushes) that it made itself pretty appealing. The big reason you might want to pursue subdivision further is if you are unhappy with the low resolution of the pixel-drawer (which is currently 320x200 just like quake). Subdivision will scale nicely to high-res, pixel-by-pixel does not.
Not sure I agree with that. You are correct in saying that you can get away with no subdivision when the camera direction is normal to the surface. But in a FPS, it seems to me like viewing things edge-on is the rule, not the exception. If I am sitting in the center of a cubic room and looking directly at one of the faces, sure there's one face that requires no subdivision, but there's four faces that do.
I'm not sure if there is an option to disagree, take a look at this early test (generates random position every time). I will go through the rest of your post later today.
...right. so, what it was supposed to show is that even in close views with maximum precision you dont need that much triangles. maybe you could also look at original away3d demo (namely, the scene with some geometry). the most important bit is that these small triangles are generated "online", and projection matrix only needs to be adjusted rather than re-calculated, as it would be necessary in case of some LOD approach. any way, hopefully this will be no longer an issue with v10 player.
But I think you could use a similar idea with the flash beginBitmapDraw routine. You only need to subdivide triangles deeply along the gradient of z (the direction orthogonal to the line of constant-z). Along the other direction, I think your triangles could have extremely long edges before you started noticing perspective error.
Unfortunately, this will not work, AFAIK. Someone have put a tight cap on PreciseBitmapMaterial recursion limit once (about 5 iterations or so), and it resulted in very similar behavior to your idea; my overall impression was that texture zigzags became very visible in that case.
The first is that I have no idea how to integrate directional lighting into that approach. I think you could cajole the flash renderer into doing gouraud (sp?) shading over the screen triangles (by rendering black, partially transparent "mask" triangles over the texture layer, and filling them with beginGradientFill with a linearly varying alpha). The catch is that if you're drawing huge triangles, your lighting function is undersampled and then linearly interpolated. So any fine details in lighting, like a circular hotspot from a nearby directional light, are going to be ignored. Unless you subdivide based on lighting too...
Again, sandy has just ported Gouraud code from flash3d. Results are just like you describe it, but that's totally expected (check sphere graphics at wiki page). This is accuracy-versus-performance trade-off.
However, if you want to do CSG-style solids ("brushes" in the prior post), your drawing regions are now non-convex polygons, possibly with holes (yuck!). I think it would be really tricky to program subdivision for this case - the pvquake demo I gave does not even touch this problem. The easier to program alternative is to do just overdraw things, by drawing the cell and then painting the brushes back over top the cell walls. I think that would be slow. But when you're doing pixel by pixel rasterization, all this is a non-issue.
Yeah but in case 1 you do more math once, and in case 2 you do less math per every pixel. It is not that obvious what is faster.
Hi Rachil0,
very interessting source, thanks for sharing.
I did some experiments with rasterization while ago too, and I muse say (as Makc wrote) I was disapointed with performance.
Not that I'm not my implementation was the fastest ever, but screen resolution will always be a big problem in such approach.
Rasterization allows a decent perspective mapping, plus ZBuffer use.
But in that case, we can't expect to have more than a 300x200 viewport, which is really low to have a good game experience.
My idea is that, having the benefits of rasterization and the advantages of native drawing routines may result in something interessting. For example, in a room, having walls and floor rasterized and other objects using flash graphical routines.
But the problem will move to depth sorting problem...
I don't see, for now, a really good way to create a correct FPS style game (even if attempts so far are really amazing).
The first demo is rippled because perspective correction is not done at every pixel, but at set intervals along the scanline (24 pixels). Quake had the same artifacts (it was corrected at 8 or 16 pixel intervals iirc) and descent was especially bad (32 pixel subspans). You can cut this interval down to a smaller value but that error will always be present to some extent. From the very 1st post:
... the easiest way to see how perspective is approximated [is to] roll the view 45 degrees and you'll see these artifacts where the texture sort of ripples on the surface.
Judging from the screen shot, this is exactly what you did. In quake, this error was managed by map and camera design. Despite its 3D nature, most of quakes surfaces are still perfectly vertical walls and perfectly flat floors. Any sloped surface is placed such that it's unlikely that a players sight can be right up next to the surface like that. Furthermore, the camera was not permitted to roll around the view axis. Even when you're killed and the camera rolls to +90 degrees like your ear is on the ground, it's not a smooth motion! It just jumps 90 degrees - essentially swapping floors and walls around and avoiding the ugly 45 degree case altogether). If you try to find perspective error without rolling the camera and I think you'll find it's pretty tough to spot (especially in the most recent demo, which prevents you from placing the camera directly onto a surface, the collision routine keeps a small ball of empty space around the camera at all times).
Unfortunately I can't get the first link to work - which I suspect was the thrust of your post. The second link I checked out (neat!). I also looked at another demo on PreciseBitmapMaterial ( http://away.kiev.ua/away3d/techdemos/persptex/ ). They are very neat demos I think the real problem with the pvquake demo is that its subdivision isn't very smart. Thinking about it again, the one case that you really have to avoid is a permitting triangle edge that points in the same direction as the z-gradient direction. Maybe a good subdivision strategy is to first cut the polygon into thinnish slices along constant-z lines and then tesselate each slice with a triangle strip. If I get time, maybe I'll give that a try sometime.
There's still a few other things that I think would be worth trying. The first is using the same scanline algorithm, use graphics.beginBitmapFill to do the 24 pixel spans instead of pushing them in pixel by pixel. That might let you scale back up to high resolutions nicely, and still let you keep all the neat spotlighting effects.
Another idea, which is tougher to implement, is to reuse scene coherency to avoid subdividing polygons at other frames. Once you draw a quad onto the screen, capture/grab it's screen area (by splitting into 2 triangles) and stuff both triangular shapes into bitmaps. Then reuse these already-distorted textures on the next frame, affinely warping them onto the new screen triangles. Every handful of frames, redo a highly detailed version to make a new source texture. I think this could work pretty well, and could even let you fake some of the directional lighting effects, by baking it into the intermediate/cached texture. Do either PV or Away3D already do this? It strikes me as pretty clever, do you think it would work?
I think your demo is really neat! I agree strongly that a combination of perspective correct rasterization and (built-in) affine rendering will have the best results. The idea of perspective correct walls and affine objects is spot-on, in my opinion. Keep up the good work
Ultimately, it seems flash 10 might make these discussions obselete, when it allows arbitrary 3D orientation of all display objects. Then 1 wall = 1 bitmapFill call. That will be nice, hope that feature makes the cut.
Reply With Quote
Originally Posted by renderhjs
The code is pretty amorphous, I am currently looking for ways to cut it into cleaner parts.
