GMLscripts.com

Discuss and collaborate on GML scripts
Invert

You are not logged in.

#1 2009-04-08 09:25:41

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Yet Another Idiotic Light And Shadow Engine

This is something I posted in a GMC moderator forum a few weeks ago, I thought I might as well spill the beans and post it here. I almost never finish games but I have a lot experiments I've done in Game Maker. I never really talk about them, partly because I don't like to toot my own horn and partly because I kind of hope that someone else will make the same discoveries on their own. It's more fun that way. But, after years of waiting sometimes, it seems silly not to talk about them. The quoted and slightly edited text begins below.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

For the last few days I've been in a deep YAILASE -- Yet Another Idiotic Light And Shadow Engine. For the last few years is more accurate but I've made some advances recently.

I've been wanting to do this action roguelike for a while, something in the spirit of Gateway to Apshai, which is sort of like a primitive Diablo. Light and visibility are a major visual component of roguelikes, and I want to explore those areas for gameplay. Things hidden in shadows, stealth, fear, that sort of thing. Like most everyone else who has worked on Game Maker shadow engines, I've at various times reached the conclusion that no matter what I try, it's never going to be fast enough.

In 2005, when I was creating and testing my range_finder script, I immediately saw its potential as a lighting system. I liked the idea of sprites casting shadows (as opposed to the currently popular vector-based approaches), but it was horribly slow.

wL1zuoi.pngfhCWKnM.jpg

A year later I had an epiphany for a novel way to cast shadows from point light sources using the GPU. NdMan had already done this with a single directional light but doing this with multiple dynamic point sources seemed impossible. The epiphany came when I was playing around in my 3D software visualizing a top-down 3D game. I realized that the lines of perspective are visually the same as the shadow lines cast by a light source at the same position.

VD4gs.pngeDUu4.gif

Once I understood that I could leverage the GPU's perspective camera to cast shadows, decent frame rates seemed in reach. Figuring out how to put multiple lights some place other than at the camera position took some doing. The other major trick was figuring out how to accumulate the light without using a surface or slow screen capture function calls. I flogged the z-buffer and d3d transforms mercilessly and three weeks later I had this.

mzQgdSs.jpgGnzJoYY.jpg0yfUMdq.jpg

As an incredible bonus, the shadow casters are d3d geometry and the scene can be fully navigated. The dynamic shadows still work like voodoo magic without any changes to the technique. It was quite staggering to discover this.

It was fast, simple, worked with d3d geometry, and was a neat hack ... but it was also extremely disappointing on one level. Being able to walk around in a 3D environment with lights and shadows was no fun if the shadows couldn't get onto the walls. There didn't seem to be any practical solution, so I basically shelved the idea. I'd pull it out from time to time to play with it, and I had some ideas about how to do the wall shadows, but even hardware accelerated it would be too slow because the technique requires the ability to clear the z-buffer for every light which is further multiplied by the number of planes that receive shadows. Facing the fact that the only known way to clear the z-buffer is calling the slowish screen_redraw function and the idea seemed hopeless.

But recently I had another idea for less realistic wall shadows by treating the floor shadows as a texture for the walls. The UV points at the floor are mapped exactly to their position in light/shadow map and the UV points at the top of the wall are the same. This causes the texture to stretch up the wall creating vertical shadows. The added benefit of this technique is that the walls are much more smoothly lit. Unfortunately, to do this with any speed requires surfaces, and surfaces aren't compatible with d3d mode. So I decided to build my own perspective camera and this is the result after several iterations.

jUh9psf.jpgGUm4mxs.jpgg8jQ5nM.jpg

The last two illustrate the idea of using shadows to obscure a "secret" passage. These pictures show only block shapes, but any geometry could be used to cast or receive shadows. The frame rate in these pictures is also not really accurate. All of the lights are dynamic right now, when most of them would normally be static. With that change and some further optimization the frame rate should hit around 120 fps. That should be plenty of clearance for the rest of the game to hit the 30 fps goal. 60 fps might even be possible.

UPDATE:

I posted a demonstration later in this thread which I'm adding here so people don't have to dig for it.

Here is a proof-of-concept prototype of the lighting system under discussion. Sorry it's taken so long to release. This is most definitely not an engine. It's as if three years of ad hoc development lead to a Frankencode monster that is as obtuse as it is unwieldy. No effort has been made to build proper systems, comment code, or even make it rational. Some stuff will not make sense. All I can say is, it did at one point. Other stuff never made sense.

This is the current generation, about eight iterations out of date (June 24, 2009). It is the first public release and is eight iterations more recent than the only private release (April 20, 2009). Only two people have seen that one. This version is much nicer.

This is almost identical to the version used to make the top-down video seen earlier in this thread. There are only a few small differences. The most significant is that this version has the older/faster/uglier shadow casting code for the dynamic geometry. This version has only mouse control and does not have recording ability.

There may be unused code still in there.
There are probably bugs.
You'll get over it.

Right-mouse-button to move
Shift key to change room speed
F1 for further Help.

http://www.host-a.net/u/xot/wm_ms_em_16-public.gmk

Normal Canted Top-Down View

Last edited by xot (2012-02-24 13:28:10)


Abusing forum power since 1986.

Offline

#2 2009-04-10 04:15:00

icuurd12b42
Member
Registered: 2008-12-11
Posts: 303

Re: Yet Another Idiotic Light And Shadow Engine

You could port your code to a dll now.

Offline

#3 2009-04-10 10:15:49

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Yet Another Idiotic Light And Shadow Engine

A DLL would completely defeat the purpose. Where's the challenge in that? laugh


Abusing forum power since 1986.

Offline

#4 2009-04-11 00:40:30

icuurd12b42
Member
Registered: 2008-12-11
Posts: 303

Re: Yet Another Idiotic Light And Shadow Engine

The chalange, using XtraFear's GM c++ lib, is to port a cool feature that is fast enough to use maybe? I started to convert many greatly optimized GM functions to dll functions. Application sepcific code too. I'm working on a map editor that morphs the terrain grid and remakes the terrain model. It's GML code that I optimised the heck in GML script. Then finally ported to a dll for the final optimization blow. It's a reasonable solution.

The GM3dPartSys.dll is an example of GM code accelerated to the max.

Your camera system could possibly just be a DLL function call to draw the world. All you need is add the world specific data (walls, textures) to a list. Without seeing your code, it's hard to tell how difficult it would be to set up though.

Offline

#5 2009-04-11 03:49:49

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Yet Another Idiotic Light And Shadow Engine

Wow! I have to say that the C++ lib thing is a bit mind blowing. This really seems to open things up. If there can be found a way to manipulate textures (sprites, surfaces, or backgrounds), I can think of some interesting applications. The way this light and shadow system works, I'm not sure there would be any substantial gains, but there could be for some other things. Particles is a good example.

For the light and shadows, this is already 100% GPU accelerated. I just draw sprites for lights and d3d transformed models for shadows. Because it uses surfaces, I can't use the depth buffer. That puts some limitations on the geometry I can draw if I don't sort the polys (which I largely don't for performance reasons). With a properly constrained perspective this doesn't really matter. The other limitation is that the bulk of the geometry pretty much has to be static in any practical scenario, although generally this would be the case anyway. One place I could see this library being useful is for bones driven character animation.

The early version of this light and shadow system didn't use models. The main trick was using the ds_grid math functions to do all of the perspective calculations in parallel. But it wasn't as fast as I hoped, probably from the shear slowness of ds_grid_get which had to be called four times a quad. That's something the library could work around.

Right now, I use a specially distorted model and a few clever d3d transforms to handle the perspective and the shadows. There is very little math and GML involved. It's all smoke and mirrors. Speaking of which, that'll be the subject of a future topic.


Abusing forum power since 1986.

Offline

#6 2009-04-11 21:19:48

icuurd12b42
Member
Registered: 2008-12-11
Posts: 303

Re: Yet Another Idiotic Light And Shadow Engine

You can move the ds_grid manipulation to a dll... This accelerates it a lot because that is no longer interpreted. you can use your own grid straight in c++, that accelerates it even more.

You can manipulate the texture the same as in gml so you have the same limits there (implemetation limits, no speed)

You no longer need the d3d depth buffer since you can order the draw yourself like I do the particle system, everything is ordered by distance to camera plane. Though this implies the caller cannot use the d3d buffer either if you use surfaces right.

Anyway, It's an idea to make it fast while still being compatible with the GM 3d drawing world.

Offline

#7 2009-04-12 15:12:27

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Yet Another Idiotic Light And Shadow Engine

I doubt it can really accelerate one call to ds_grid_copy and one call to ds_grid_multiply. That's all that I needed for the perspective or shadow calculations. Now reading the grid to draw the primitives, that's were I could have used a boost. But, I don't use that code any more.

It's literally this complicated:

with (light) {
    surface_set_target(surfaceWork);
    draw_clear();
    draw_set_blend_mode();
    draw_sprite();
    d3d_transform_set_skew_z();
    d3d_model_draw();
    surface_set_target(surfaceAccumulator);
    draw_set_blend_mode();
    draw_surface();
}

07EkrbX.gif
That's off the top of my head but that's basically all there is to it. There's very little interpreted code which is why I'm doubtful for any major gains. Maybe I'll try it for some other things, it certainly is powerful. I'm also not really a C programmer, so that's some of the reason for the hesitation to dive right in.

A version of the function: d3d_transform_set_skew_z

My original call for help: http://gmc.yoyogames.com/index.php?showtopic=247578
I thanked Spirit of the Wolf, but it looks like it was brac37 who came up with the code I found.


Abusing forum power since 1986.

Offline

#8 2009-04-13 16:23:07

paul23
Member
Registered: 2007-10-17
Posts: 110

Re: Yet Another Idiotic Light And Shadow Engine

Well what you could do is write your own "grid-system" in C++ and then use the specific algorithms from C++..

That's also what I'm doing with my A* engine I wrote some years ago: it might actually make custom A* possible to be used inside bigger games! (funny thing for example there was that all papers about A* talk about "keeping a list sorted" being the most demanding operation: yet in GM it was simply the loop-code itself).

Only problem with my method is that you couldn't use ds_grids anymore, since I believe the library doesn't actually increase the speed of the GM functions and thus calling "ds_grid_get(x,y)" wouldn't be really fast..

It looks good btw, can't wait to see it being "released"!

Offline

#9 2009-05-30 03:03:35

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Yet Another Idiotic Light And Shadow Engine

I thought I'd post a little progress update. This is about six iterations since the last picture. I've added dynamic geometry that can cast and receive multiple shadows. Shadows are cast using basically the same technique as the wall shadows. Shadows are received by copying the area of the floor the object is over and using it as a light map for the object.

0RH7vop.jpgThe big limitation is that dynamic geometry cannot cast shadows on anything but the floor. They could in the beginning but that leads to some serious problems. The biggest one is that the objects self-shadow in a physically impossible way. Imagine a four-legged table casting a shadow onto the floor, only the shadow also appears on the tabletop. It is possible to get around this by dividing the model into layers* that receive different groups of shadows, but it's complex and leads to other problems, a speed hit being not the least of them. The other problem is that shadows cast onto walls would be stretched across the entire height of the wall, floor to ceiling. That's highly unrealistic if the objects are not taller than the height of the light source. Even if they are, because the shadows the walls receive are built from what is essentially a 1-dimensional texture map, the projected shadow edges are straight lines, not the shape of the object.

(* theoretical side note: if the entire system was divided into enough layers, you could get completely realistic shadows everywhere)

One other limitation is the shadows are only cast by dynamic light sources. This is actually a good thing. When every single light casts shadows, there are shadows all over the place and things become very chaotic and ugly.

Oh, yes, one other limitation is that shadows in one room can pass through walls and appear in the room on the other side. As with other aspects of this system, careful control of the view, shadow length, wall geometry, and object placement is the key.

I use a subtractive blend to draw the shadows onto the floor. That's why objects already in shadow can still cast shadows of their own (although this isn't apparent in the picture). You see this same problem in most professional games that have dynamic geometry that casts shadows. The melding of dynamic and static lighting is imperfect to say the least.

I'm still trying to decide if this system is truly practical. Actual frame rate is almost 120 fps on a 2GHz AMD Opteron with a GeForce 6800GS, which is about what I figured I'd get once I got the static lighting working.


Abusing forum power since 1986.

Offline

#10 2009-06-21 09:24:21

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Yet Another Idiotic Light And Shadow Engine

Tiny little update:

Recently icuurd12b42 proved to me that it is indeed possible to use a d3d perspective projection without first calling d3d_start(). I tried this quite some time back, but for some reason I've never seemed to have had success. Once I saw that this was actually possible, I got pretty excited.

One of the things that this generation of light and shadow engine has required up to this point is performing perspective calculations manually. This lead to some interesting code. The first breakthrough was parallelization of math through the ds_grid math functions. Later, it was the realization that perspective could be precomputed and embedding into the model itself which would then only require a very fast shear transform to correct the distortion for any particular top-down view. Ultimately, none of this effort was required. [ed: It seems it was not wasted effort, as explained in later posts]

There are a couple of drawbacks to not using a d3d perspective transform. The primary one is that perspective correct texture mapping is not available. This leads to seams or creases in the texture mapping of any quad that doesn't have a parallelogram shape when projected onto the screen.

Wuiy9fS.jpg

By subdividing the geometry, the total error can be evenly distributed across the entirety of the textured area which makes the artifacts less noticeable. There have been some linear interpolation and bilinear interpolation tricks posted at GMC that do precisely this. However, that also means a whole lot of extra polygons one normally wouldn't need.

EFN7gZk.gif

H8wmRMb.jpgNow that I can use the GPU for perspective, I also have perspective correct texture mapping. That means I can now use about 25% the number of quads I needed before which has obvious advantages.

Compare this to the previous image. Notice twice as many walls are displayed but only half as many triangles are required. Notice a ~25% higher the frame rate.

In general, this simplifies several things greatly. I no longer need dedicated models just for shadow casting [ed: wrong] which reduces the amount of geometry in memory by a third. It also means I have much, much greater freedom when it come to the camera angles. Theoretically, this system can now work even from a first person perspective (although polygon sorting becomes a major issue at that point). All in all, this is a pretty big development.


Abusing forum power since 1986.

Offline

#11 2009-06-21 11:50:51

flexaplex
Member
Registered: 2008-12-11
Posts: 72

Re: Yet Another Idiotic Light And Shadow Engine

This is looking great.

Are you nearly finished working on it? What do you plan on doing with it after you've finished?

Offline

#12 2009-06-21 14:45:00

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Yet Another Idiotic Light And Shadow Engine

Sorry, I just can't top this idiocy.
http://gmc.yoyogames.com/index.php?showtopic=436877
If that teaches anything, it teaches what not to do.

Anyway ... lots of work to still do with this engine. In fact, I hesitate to call it an engine yet -- it may never be worthy of that name since it is so tricky to use.

The next thing I plan on doing is removing the dedicated shadow models and letting the d3d perspective projection do all the work. This will be going back to almost the same method I was using two years ago. It's funny how this project is starting to come full circle.

When I've got that working, I'm going to play with some different perspective projections including first-person. That's going to mean full-time dynamic polygon sorting. I don't expect it to be very practical. I have no plans for a first-person-anything, so it'll be more of a proof-of-concept. Who knows, there might be something simple that could be done with it.

Once I've had my fun with that, I'm going to focus on some major lighting changes.

The first thing that needs to be addressed is adding the ability to change to resolution of the light maps. That should be pretty simple and will allow for much larger environments and hopefully much faster rendering. This relies on multipass techniques, so the more I can reduce the number of affected pixels, the better.

Next, I want to add a luminous pass to the shader so that I can have textures with self-illuminated areas (like a glowing magical pool, or a control panel, or video screen). I may also add support for animated textures at this point.

2bfnzgj.jpgIf all goes well, the next experiment will be adding bump mapping. I'm pretty sure I can do the floor, no problem. I've already got something built that works well. The wall geometry will be a little trickier. If I can't do the walls, I may leave out bump mapping for the floors as well. What I've built is pretty fast but it may not be fast enough for multiple lights.

The last potential shader change will be much more drastic. Right now, the lighting is all environmental (the floor being the environment). It's effective, but it could look so much better with some Lambertian shading added into the mix. The way the lighting works now there is no diffuse reflectance fall off as the incident angle increases. That causes the walls to "pop" into full brightness when moving around a dark corner, rather than gradually brightening with regard to the lighting angle. That can be GPU accelerated, and I think I can fit it into the existing system, but I'm not sure what it will do to speed.

Meanwhile, to really get much further I need to build some tools to create, import, and optimize geometry. I'm getting tired of this simple, blocky layout. I want to build some more elaborate walls in particular, along with trying to create some natural forms for a more cave-like environment. I'd also like to add support for moving doors. Of course, a proper rougelike requires random dungeons. I've been working on this too. I hastily tried to meld that project into this one with fairly disastrous results. The dungeon generator still needs a lot of work.

Finally, another area that needs attention are the "monsters" and player character. I need to add support for animated geometry (probably simple model swapping) ... and then create said animated geometry. That's going to be a bear to produce, I don't have any real experience as a character animator. I also don't know how to build UV maps in LightWave yet. I keep flirting with the idea of importing Quake 1 models. It's tempting to leave this work for the actual game, but it really needs to be tested for practicality.


Abusing forum power since 1986.

Offline

#13 2009-06-21 15:59:27

flexaplex
Member
Registered: 2008-12-11
Posts: 72

Re: Yet Another Idiotic Light And Shadow Engine

xot wrote:

Anyway ... lots of work to still do with this engine. In fact, I hesitate to call it an engine yet -- it may never be worthy of that name since it is so tricky to use.

The next thing I plan on doing is ...

...
...

Finally, another area that needs attention are the "monsters" and player character. I need to add support for animated geometry (probably simple model swapping) ... and then create said animated geometry. That's going to be a bear to produce, I don't have any real experience as a character animator. I also don't know how to build UV maps in LightWave yet. I keep flirting with the idea of importing Quake I models. It's tempting to leave this work for the actual game, but it really needs to be tested for practicality.

Oh.

OK, I'll check back in 4 years when you've finished wink

It's tempting to leave this work for the actual game

Does this mean you are actually writing this for a game and you're not really planning to release it as an engine? Will there be no release before it is fully completed?

I just wanted to test how fast and pretty it was smile

Sorry, I just can't top this idiocy.
http://gmc.yoyogames.com/index.php?showtopic=436877
If that teaches anything, it teaches what not to do.

lol. I just looked at that. Hilarious.

Last edited by flexaplex (2009-06-22 12:53:22)

Offline

#14 2009-06-21 16:27:05

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Yet Another Idiotic Light And Shadow Engine

I hope it doesn't take four more years to reach the end. I'm curious if GM8 will add anything that can improve this. I don't anticipate any formal release before GM8 comes out.

I don't know for sure what I'm going to do with it. I have several game ideas that can take advantage of it. One is the action roguelike I've been talking about here. I didn't initially plan on releasing this as an "engine" because it is so difficult to use. The thinking was, if you are capable of using it, you are capable of creating it yourself. That's part of the reason for this topic. As it evolves, it's starting to look a little more user friendly, so who knows. When I clean it up some more, and before I get too deep into changes, I'll probably post something that you can check out.

Sorry, I just can't top this idiocy.
http://gmc.yoyogames.com/index.php?showtopic=436877
If that teaches anything, it teaches what not to do.

lol. I just looked at that. Hilarious.

It killed me to approve that topic.


Abusing forum power since 1986.

Offline

#15 2009-06-21 17:01:49

flexaplex
Member
Registered: 2008-12-11
Posts: 72

Re: Yet Another Idiotic Light And Shadow Engine

xot wrote:

I hope it doesn't take four more years to reach the end. I'm curious if GM8 will add anything that can improve this. I don't anticipate any formal release before GM8 comes out.

I was going to say if your lucky GM8 might be able to improve some things. GM9 will probably be out by the time you finish though... no I am only joking that it will take so long smile

When I clean it up some more, and before I get too deep into changes, I'll probably post something that you can check out.

Well I always like to try and release things. You never know what good ideas you might get from people.

Offline

#16 2009-06-21 18:45:24

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Yet Another Idiotic Light And Shadow Engine

Looks like I was wrong/right about not being able to use the d3d perspective transforms, at least during a crucial step. When the rendering target is a surface, they don't seem to work. All I can manage is ortho. I came to same conclusion back in October 2006. It really has come full circle. laugh


Abusing forum power since 1986.

Offline

#17 2009-06-21 19:18:28

flexaplex
Member
Registered: 2008-12-11
Posts: 72

Re: Yet Another Idiotic Light And Shadow Engine

Yes surfaces get destroyed when you turn on 3D mode so it's not going to be easy using them.

Last edited by flexaplex (2009-06-22 19:54:34)

Offline

#18 2009-06-22 05:21:20

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Yet Another Idiotic Light And Shadow Engine

I never turn on 3D mode but something about switching the rendering target seems to override the perspective projection. I may be wrong about that but that's what I think I'm seeing.

Lambertian reflectance shouldn't be too demanding, it's the reflectance model that the GPU uses. It does mean an extra pass with hardware lighting, but there are so many passes going on already that the increased GPU load should only be a small percentage of the overall usage.  All of the static lights can be precomputed, so that leaves only one or two dynamic lights to shade with in real-time. My main concern is ugly shading glitches when the dynamic lights are moving around. That's generally due to the limitations of Gouraud shading with large polygons and point light sources. Hmmmm, now I'm starting to wonder if this is actually practical because aren't hardware lights normally directional? I don't know, it's been a while since I messed with hardware lighting, I need to refresh myself as to what works. The first GPU experiment from two years ago managed point sources somehow.

Disclaimer: I keep referencing Wikipedia but a lot of what I'm reading there is misleading or incorrect.


Abusing forum power since 1986.

Offline

#19 2009-06-22 07:17:10

icuurd12b42
Member
Registered: 2008-12-11
Posts: 303

Re: Yet Another Idiotic Light And Shadow Engine

I've perused though the topic again and notice your d3d_start reference... And I think I remember you taking about texture fiddling which would help you somewhere...

If you dont use d3d_start, you can use surfaces for your textures!! And modify them live. you dont even need to refetch the texture once you have it...


Information about object: object0

Sprite: <no sprite>
Solid: false
Visible: true
Depth: 0
Persistent: false
Parent: <no parent>
Mask: <same as sprite>

Create Event:
execute code:

m = d3d_model_create();

d3d_model_ellipsoid(m,-10,-10,-10,10,10,10,1,1,16)
//tex = sprite_get_texture(sprite0,0)

s = surface_create(128,128)
surface_set_target(s);
draw_clear(c_black);
draw_sprite(sprite0,0,0,0);
surface_reset_target();
tex = surface_get_texture(s);


Keyboard Event for <Space> Key:
execute code:

surface_set_target(s);
draw_point_color(random(128),random(128), random(c_white));
surface_reset_target();

Draw Event:
execute code:

draw_set_color(image_blend);
d3d_model_draw(m,x,y,0,tex)


[edit]
I'm pretty tired, so, maybe that is what you are doing now!??

Last edited by icuurd12b422 (2009-06-22 07:24:02)

Offline

#20 2009-06-22 08:50:16

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Yet Another Idiotic Light And Shadow Engine

Yes, this is what I'm doing, i.e. using surfaces for textures. The light maps are surfaces and are used to texture the walls during the lighting pass. What I can't seem to do is render onto a surface using a d3d perspective projection. That's been the stumbling point for the last couple years. I eventually did figure out a way around that by using my own perspective system. It would simplify things if I didn't need to do it manually. Speed's not really a problem at this point, but I'd like to reduce the memory footprint and increase the ease of use as much as possible. Being able to set a d3d perspective projection onto a targeted surface would be a big help. I can't seem to manage it, but it isn't strictly required. The system I have works pretty good, it's just cumbersome to prepare the geometry for it.


Abusing forum power since 1986.

Offline

Board footer

Powered by FluxBB