RRodgers
Level: Delver

Rank Points: 33
Registered: 09-12-2008
IP: Logged

Greetings.

Today, a particle of wild inspiration hit my brain and I created a shadow calculation algorithm from scratch. I did it in C, using a bit of assembly to speed things up. I have linked to the demo in the hopes that somebody would find in interesting. I am not sure what newer versions of DROD are capable of (I have played only the first demo), but I immediately thought of it when I wrote my test program.

Anyone who wants it can get it at:
http://rrodgers.110mb.com/light.zip (44KB)

Requirements:
Windows XP (Vista should work...)
A computer with MMX (almost every computer has it these days.)

The only third party product used was Ken Silverman's KPLIB. Ken is good friend of mine and it is highly recommended to view his website: http://www.advsys.net/ken
KPLIB is used for loading a wide variety of picture formats.

And to think I have actually intended that it would be used for a 3D engine of mine... now it ends up on a DROD forum. My bandwidth is too limited to download the other DROD demos on this site, so I would never know if it supports these kinds of shadows. If not, then I hope the developers find my test program interesting. It would be cool to see that in DROD.

---

[Last edited by RRodgers at 09-13-2008 09:42 AM]

vittro
Level: Smiter

Rank Points: 479
Registered: 04-17-2005
IP: Logged

Wow, looks really nice!

____________________________
http://vittorioromeo.info

Syntax
Level: Smitemaster
Rank Points: 1218
Registered: 05-12-2005
IP: Logged

That is excellent. I'd be very interested in your technique (even if vague). I wrote a few 3D asm "demo" presentations a while back and have been wondering whether this could be applied to 3D. It certainly looks brilliant.

My guess though is you're using palette shifting... would that be right?

RRodgers
Level: Delver

Rank Points: 33
Registered: 09-12-2008
IP: Logged

Ah, no. I do not use palettes. I will give a brief description of the algorithm, but bear in mind I am only 16 years old, and therefore it may not be as sophisticated as you think.

What I do is: I obtain the convex hull of the object that needs to cast a shadow, then I find the left/right point where the rays intersect the hull in only one place. Since I am working with squares, a few comparisons is all it takes. Then I project the two rays on to the screen border, so I am left with a convex polygon where the shadow will be. I use a bit array for keep track of lit pixels, then I use MMX multiplies to blend it with the colour and intensity of the light. For now, there is one multiply to blend the texture with the lightmap, and 1 for every lit pixel for every light. I could reduce those if I make the light have a constant intensity/distance, it would run much faster.

I think a 3D version could work as well, since you can compute the shaded area and store it as a bunch of planes. Any part of the scene not inside a "shading frustum", will be lit. The shading frustum is calculated in the same way as my normal 2D shading polygons. Of course, this is only an idea.

Any questions?

---

[Last edited by RRodgers at 09-13-2008 01:01 PM]

Tim
Level: Smitemaster

Rank Points: 1979
Registered: 08-07-2004
IP: Logged

Can I say that this looks very well?

I doubt the DROD developers will use the same code as you did, since I don't think MMX works multiplatform (DROD is). But it looks nice, and fast.

However, I do assume that DROD already use a similar method to create shadows, but a bit slower.

I think your 3D idea works well, but I'm wondering how that would work with "a bit array for keep track of lit pixels".

____________________________
The best way to lose customers is to let little kids running loose on a forum with too many mod points.

RRodgers
Level: Delver

Rank Points: 33
Registered: 09-12-2008
IP: Logged

The bit array refers to the 2D version. The 3D one might use scanline hybrid technique:

Right before you rasterise the scanline of a polygon, you form a triangle with the start/end and the light source. Then test where this triangle intersects geometry (trick needed here for speed...) you project this intersection line on the bit array for that scanline. It works on roughly the same principal, and the only bottleneck is how to make the triangle/geometry intersection fast enough to work. You will also require good hidden surface removal, so you don't render any more scanlines than necessary. Of course, I'm not saying this technique is foolproof, since I just came up with it. But it should be worth a try.

Just to clear confusion, I mean you take the 2D scanline's start/end, convert that to 3D (add z=hres/2 for 90 FOV), and combine with the light's 3D position. The intersection is converted back to 2D so it lies on the scanline.

I hope this is clear enough, I am not sure exactly how I should communicate this idea, since I usually speak C and occasionally Assembly.

I almost forgot to mention: The only reason I use MMX is for parallel colour multiplies. It is not essential to the algorithm, and the effect can be simulated (much faster) with the use of palettes. But that will restrict the number of different colours.

---

[Last edited by RRodgers at 09-15-2008 05:42 PM : Added last paragraph]

mrimer
Level: Legendary Smitemaster

Rank Points: 5056
Registered: 02-04-2003
IP: Logged

DROD's lighting algorithm uses 3D ray-traced shadow rays from pixel to light source, with room geometry built from primitives such as triangles, spheres, and planes, with various speed optimizations for occlusions. This seems to be pretty much what you're suggesting for 3D scanline rendering, am I right?

I built it this way so it would be simple to add more object geometry modeling in the future, and it should work with a minimum of tweaking. For instance, if we want to add shadow modeling for more game elements like potions, etc., you just plug in their geometry.

____________________________
Gandalf? Yes... That's what they used to call me.
Gandalf the Grey. That was my name.
I am Gandalf the White.
And I come back to you now at the turn of the tide.

---

[Last edited by mrimer at 09-15-2008 07:03 PM]

RRodgers
Level: Delver

Rank Points: 33
Registered: 09-12-2008
IP: Logged

Yes, that is about right. Except that doing per-pixel raytracing would be a lot slower. I don't think DROD really has to worry about speed, though. The main difference is that my algorithm would calculate the start/end point of the shadow a light would cast, instead of doing it for every pixel. This should also be easy to adapt to the primitives you specified.

I think it is a good idea to do lighting using 3D primitives, although you can also consider bit array voxels for more complex shapes, since triangles are a bit slow when it comes to things like characters with lots of curves. Voxels aren't too hard to bring into my algorithm either, since you only trace along the plane where the triangle cuts the voxel object's bounding cube, you can make a fast voxel tracing algorithm like that. Which brings me to add; perhaps DROD could make use of voxels instead of sprites, you would only need one object for all orientations. My friend, Ken Silverman, has done a lot of research on voxels and has given me a few good ideas regarding their rendering.

Hmmm... then you can add dynamic destructibility: The roach really splits in two when Beethro smites it. Feel free to ignore my suggestions, though. Being a programmer, I know it is a lot easier to say things than to actually implement them.

---

[Last edited by RRodgers at 09-15-2008 07:27 PM]