Jump to content

[TOPIC: topicViewTemplate]
[GLOBAL: userSmallPhoto]
Photo

Shadows for polygons and rects
Started by XeduR @Spyric Aug 01 2018 09:03 AM

39 replies to this topic
shadows
[TOPIC CONTROLS]
Page 1 of 2 1 2
[/TOPIC CONTROLS]
[modOptionsDropdown]
[/modOptionsDropdown]
[reputationFilter]
[TOPIC: post.html]
#1

XeduR @Spyric

[GLOBAL: userInfoPane.html]
XeduR @Spyric
  • Enthusiast

  • 71 posts
  • Corona SDK

I just finished the last minor tweaks on a shadow function that I created for one of my Corona projects. The function is capable of creating shadows for all sorts of simple polygons.

In its current form, it takes about 0.03ms to 0.08ms to create shadows for convex shapes with relatively few vertices and about 0.2ms to 0.4ms to create shadows for more complex concave shapes.

Has anyone else in the community worked on something similar to this, and if so, what kind of performance did you achieve? Or, if you haven't worked on something like this, do you think that this level of performance is viable?

 

giphy.gif


  • Michael Flad, horacebury and sporkfin like this

[TOPIC: post.html]
#2

roaminggamer

[GLOBAL: userInfoPane.html]
roaminggamer
  • Corona Geek

  • 6,923 posts
  • Corona SDK

Yes another developer (René Aye) made a shadows module, but I think he is no longer developing w/ Corona.

Starting at ~40:00 in this video:


  • XeduR @Spyric likes this

[TOPIC: post.html]
#3

XeduR @Spyric

[GLOBAL: userInfoPane.html]
XeduR @Spyric
  • Enthusiast

  • 71 posts
  • Corona SDK

Thank you for the link, roaminggamer! I had completely forgotten about that Corona Geek episode. This is one of the things that I thoroughly enjoy about programming. You have a single task, but there are as many solutions as there are programmers. Rene and I have completely different ways of approaching this issue.

I just downloaded his module and tried it out. In terms of performance, my module seems to create the shadows roughly 10-12 times faster and doesn't have any issues with the shadows trying to catch up to the shapes, but my module doesn't work with circles like his does or have any cool lens glare effects.


  • horacebury likes this

[TOPIC: post.html]
#4

horacebury

[GLOBAL: userInfoPane.html]
horacebury
  • Corona Geek

  • 2,956 posts
  • Corona SDK

This is awesome!

 

Shadows are something I've tried to work out but completely failed at. Well done for getting such great performance.

 

Would love to see this as a code share or plugin.



[TOPIC: post.html]
#5

Michael Flad

[GLOBAL: userInfoPane.html]
Michael Flad
  • Contributor

  • 139 posts
  • Corona SDK

Yeah, releaseing this as a plugin would be really cool.



[TOPIC: post.html]
#6

XeduR @Spyric

[GLOBAL: userInfoPane.html]
XeduR @Spyric
  • Enthusiast

  • 71 posts
  • Corona SDK

I got an idea from the video. By inserting the shadows into a snapshot, I can also create accurate shadows for circles as seen in the attached image.

I hadn't thought about it, but if there is sufficient interest from the community, I could possibly turn this module into a plugin at some point.

Attached Files


  • horacebury, bgmadclown and Sheekore like this

[TOPIC: post.html]
#7

sporkfin

[GLOBAL: userInfoPane.html]
sporkfin
  • Contributor

  • 398 posts
  • Corona SDK

That would make an awesome plugin!  I'd buy it.  Is possible at this time to produce a gradient fill - fade the alpha of the shadow to 0 to soften the edges?  Can it work with multiple lights?

 

Great work!



[TOPIC: post.html]
#8

XeduR @Spyric

[GLOBAL: userInfoPane.html]
XeduR @Spyric
  • Enthusiast

  • 71 posts
  • Corona SDK

As it is now, the module supports using as many local light sources as needed. It also supports using a single global light source, i.e. a single angle that all objects use for their shadows, which is useful in cases where the light source is far away, e.g. the Sun.

The shadows as polygon display objects, so a gradient fill can be easily applied to them, as seen in the attached picture. If the shapes are complex or odd, then using gradient fills might not be as easy as just rotating them according to the angle between the light and the object. 

Attached Files


  • Michael Flad, horacebury and egruttner like this

[TOPIC: post.html]
#9

SGS

[GLOBAL: userInfoPane.html]
SGS
  • Corona Geek

  • 1,841 posts
  • Corona SDK

If you scale this you will run into major bottlenecks as polygons are not very performant in Corona.

 

I switched from polygons to deformed rects for my game and the performance boost was like 3x.

 

My games are isometric by design.



[TOPIC: post.html]
#10

XeduR @Spyric

[GLOBAL: userInfoPane.html]
XeduR @Spyric
  • Enthusiast

  • 71 posts
  • Corona SDK

While rects offer a better performance than polygons, they can't be used to create shadows for concave polygons or polygons that have 5 sides or more unless multiple rects are used to form the shadows, but doing so would most likely result in something more cumbersome than the current method. Calculating the vertices for the shadow is the most strenuous task. After the vertices have been calculated, creating the polygon itself seems to only take about 0.01ms to 0.03ms extra.

 

The shadow system does, of course, have a clear upper limit in terms of how many shadows it can create every frame. Trying to delete and create too many shadows every frame will certainly result in significant frame drops.

I will probably create some stress test build for android and post the link here. Then, if others are willing to try out the module's performance on their devices, I should be able to better figure out the potential limits of the module.



[TOPIC: post.html]
#11

SGS

[GLOBAL: userInfoPane.html]
SGS
  • Corona Geek

  • 1,841 posts
  • Corona SDK

Given I normally have 1k display objects on display at any one time I would love to simulate shadows for those... but I doubt this is doable in Corona.  Admittedly my objects are pngs but I could easily define a polygon for shadows.

 

its real easy when objects are discrete but z-ordering shadows would also be a real issue?



[TOPIC: post.html]
#12

XeduR @Spyric

[GLOBAL: userInfoPane.html]
XeduR @Spyric
  • Enthusiast

  • 71 posts
  • Corona SDK

If you create those 1k objects when the scene/level/etc. is loaded, then depending on the number and complexity of the polygons' vertices, it should be very doable. I just ran a test on my computer and creating shadows for 1000 very simple convex shapes took about 1.1 seconds. The duration seems very high, especially since creating only a few of such shapes takes less than tenth of a millisecond, so I'm going to double check my code tomorrow for possible leaks and other issues.

I'm not sure if z-ordering the shadows would be particularly difficult for isometric games. For instance, one of the ways that I am currently creating the shadows is via a loop like this:
 

for i = 1, #light do
	for j = 1, #object do
		shadow[i][j] = spyricShadows.cast( object[j], light[i], shadowSettings )
		shadow[i][j]:setFillColor(0)
		groupShadows:insert( shadow[i][j] )
	end
end

The function returns a polygon. If the object that the shadow is created for were to added to the group after the shadow, or if the shadow were to be placed in the object's group via other means, then it should work without any difficulties.



[TOPIC: post.html]
#13

sporkfin

[GLOBAL: userInfoPane.html]
sporkfin
  • Contributor

  • 398 posts
  • Corona SDK

@XeduR  Do you have a specific game you are designing this for.  I see so much potential for games of all genres.  I've been playing around with making a light Corona 3D engine (back burner project) and your work here masters some of the principles I've been wrestling with.  My concept centers around tricking the eye using 3 and 4-point perspective to give the illusion of depth which is essentially what your module does with shadow vertices.

 

Please keep us updated, I'd love to see how this progresses.



[TOPIC: post.html]
#14

XeduR @Spyric

[GLOBAL: userInfoPane.html]
XeduR @Spyric
  • Enthusiast

  • 71 posts
  • Corona SDK

I did indeed start working on this module for a specific game, but as the module kept getting better and better, I came to realise that several of my other projects would also greatly benefit from this. The game that I am working on at the very moment is a platformer that also utilises normal mapping and other polygon manipulation methods to complement the shadows.

Here's a very non-descriptive image of its alpha version (the normal mapping is turned off in the image).

 

Attached Files


  • StarCrunch and sporkfin like this

[TOPIC: post.html]
#15

XeduR @Spyric

[GLOBAL: userInfoPane.html]
XeduR @Spyric
  • Enthusiast

  • 71 posts
  • Corona SDK

Quick update.

I've been optimising the shadow module a bit further and I also found out the reason for why creating 1k shadows took over 1.1 seconds before. The answer is, it didn't. I was using a function for creating those 1k polygons and another 1k for their shadows, but I accidentally kept running the function 3 times, resulting in actually creating 3k objects and 3k shadows, i.e. a total of 6k polygons.

So yeah, creating up to 1k or more shadows will take a while depending on the complexity of the shadows (i.e. how many vertices and whether the shapes are concave or convex), but as long as those shadows aren't being created every frame, it should work just fine. Creating 1k simple convex shapes and shadows for them took 305.9ms on average and creating 1k relatively simple concave shapes and shadows for them took 575.4ms on average.

@roaminggamer, as I'm optimising the module, I became curious about the idea of caching some common results of various calculations that you talked about in the video. Do you, or anyone for that matter, know how big of a difference would it be to use tables containing sin, cos and tan values and retrieve the values from the tables instead of actually using the math.sin, math.cos and math.tan functions? The module can easily run hundreds of such calculations every frame, if asked, so if I could perform them more efficiently at the expense of some accuracy, I would be very interested in pursuing such a route.
 



[TOPIC: post.html]
#16

GrahamRanson

[GLOBAL: userInfoPane.html]
GrahamRanson
  • Enthusiast

  • 75 posts
  • Corona SDK

Just replying to state my strong interest in this being released as a paid plugin.


  • sporkfin likes this

[TOPIC: post.html]
#17

SGS

[GLOBAL: userInfoPane.html]
SGS
  • Corona Geek

  • 1,841 posts
  • Corona SDK

In my isometric worlds I do the following....

 

On world load I load the textures required into a cache. 

On each frame (and only if the screen dimensions have changed) I walk the world to work out visibility based on x, y and z values of the asset. 

If it should be visible but is not yet loaded I then instantiate the required objects otherwise I simply toggle visibility, start/stop animations and start/pause emitters.

 

...would your "plugin" handle such a system?



[TOPIC: post.html]
#18

XeduR @Spyric

[GLOBAL: userInfoPane.html]
XeduR @Spyric
  • Enthusiast

  • 71 posts
  • Corona SDK

@SGS, you could generate all of the shadows for all of the required objects as the world loads and then just toggle their visibility on and off as necessary, or you could write some check to see when a shadow would be on screen and then create it and delete it once it moves on or off screen.

When you are referring to your game, are you talking about Designer City? I've looked at a few screenshots of the game and there might be some problems with using this shadow module for it. In games like that, there are buildings of varying heights and shapes. Depending on the angle of the light, as well as its position on the z-axis and the buildings shape and height, the shadows for some buildings might not appear as intended.

For instance, if a tall building casts a long shadow then that shadow might overlap other buildings. You could choose to place the shadow underneath those buildings or on top of them, but neither of them would be technically correct. You'd need a 3D engine for that. My shadow module only casts the shadows on a 2D plane and does not take into account if there are other objects in the way. While my module works with isometric shapes, it cannot handle fancy 3D objects. Instead, it should be used to create a shadow based on the object's base.



[TOPIC: post.html]
#19

XeduR @Spyric

[GLOBAL: userInfoPane.html]
XeduR @Spyric
  • Enthusiast

  • 71 posts
  • Corona SDK

To answer my own question, if someone else is interested in speeding up certain parts of their projects, I recommend looking into calculating the answers in advance and storing them in tables. Here's the code from one of my tests:
 

local mathRad = math.rad
local getTimer = system.getTimer
local deg2rad = {}

for i = 1, 3600 do
	deg2rad[i] = mathRad(i*0.1)
end

local t1, t2 = {}, {}

local startTimeT1 = getTimer()
for i = 1, 10 do
	for j = 1, 3600 do
		t1[#t1+1] = mathRad(j)
	end
end
local endTimeT1 = getTimer()-startTimeT1

local startTimeT2 = getTimer()
for i = 1, 10 do
	for j = 1, 3600 do
		t2[#t2+1] = deg2rad[j]
	end
end
local endTimeT2 = getTimer()-startTimeT2

print("Duration by using math.rad: "..endTimeT1)
print("Duration by checking table: "..endTimeT2)

I tried the following code on my computer, as well as on two mobile devices. On my computer, the results varied greatly, but checking the table was faster every time. The results varied from checking the table being 1.1 times faster to 1.9 times faster. On my mobile devices, the were instances were checking the table was even 4 to 5 times faster.

So, it would seem that calculating the answers in advance can provide a great boost in performance, but it comes at the expense of accuracy and increased size on the disk.



[TOPIC: post.html]
#20

SGS

[GLOBAL: userInfoPane.html]
SGS
  • Corona Geek

  • 1,841 posts
  • Corona SDK

pre-calculation is always faster - especially if in tight loops.  for my games I have to pre-calculate most things to get it to perform.



[TOPIC: post.html]
#21

Michael Flad

[GLOBAL: userInfoPane.html]
Michael Flad
  • Contributor

  • 139 posts
  • Corona SDK

It highly depends on what you precalc and how expensive the calculation is. Also micro benchmarks may give a very different result compared to the same lines in a much more complex usage with bigger amounts of accessed memory etc. (but it's typically not that often the case when using interpreted Lua).
 
It also depends on what you precalc and if you can't do it in another way, f.i. I added a third option which simply does the deg2rad conversion inline and that's much faster than the table lookups.
 
I moved the memory allocation out of the loop as this probably was the most time consuming part (of course the same for both tests) - you created arrays of 36000 entries within the actual benchmark loops, I guess that's not what you intended?
 
And last but not least, your table lookup has a very different range of valid input. That of course depends on the code - if you know for sure all your angles are within f.i. 1-3600 (i.e. 360 degrees in 0.1 steps as used in your test) everything is fine.
But if you want to replace trig functions for angles you can't guarantee this (because they're the result of other calculations) you'll have to scale and floor your angles before you do the table lookup. At this point you need a function call already and you lost all your lookup gains, because I'd expect that in most cases, the primary reason for the overhead is the function call and not the actual calculation.
 
 
local mathRad = math.rad
local getTimer = system.getTimer
local deg2rad = {}
 
for i = 1, 3600 do
deg2rad[i] = mathRad(i*0.1)
end
 
local t1, t2, t3 = {}, {}, {}
for i = 1, 3600 do
    t1[i] = 0
    t2[i] = 0
    t3[i] = 0
end
 
local numIterations = 50
 
local startTimeT1 = getTimer()
for i = 1, numIterations do
for j = 1, 3600 do
t1[j] = mathRad(j)
end
end
local endTimeT1 = getTimer()-startTimeT1
 
 
local startTimeT2 = getTimer()
for i = 1, numIterations do
for j = 1, 3600 do
t2[j] = deg2rad[j]
end
end
local endTimeT2 = getTimer()-startTimeT2
 
 
local DEG2RAD = math.pi/1800
 
local startTimeT3 = getTimer()
for i = 1, numIterations do
for j = 1, 3600 do
        t3[j] = j * DEG2RAD
end
end
local endTimeT3 = getTimer()-startTimeT3
 
 
print("Duration by using math.rad: "..endTimeT1)
print("Duration by checking table: "..endTimeT2)
print("Duration by code: "..endTimeT3)

  • sporkfin and XeduR @Spyric like this

[TOPIC: post.html]
#22

StarCrunch

[GLOBAL: userInfoPane.html]
StarCrunch
  • Contributor

  • 744 posts
  • Corona SDK

@Xedur The libtess2-binding plugin I recently released might be relevant to you, say if you want to relax the simple polygon limit. I have some other stuff coming up in a similar vein, too. For bulk math I've also got the makings of an Eigen binding, but haven't been able to give it much attention lately.

 

Also belatedly joining in to say this looks very nice.  :)

 

Performance-wise, there might be identities to exploit or alternative formulations. Can you post any snippets, maybe with a mock-up of the geometry involved?



[TOPIC: post.html]
#23

XeduR @Spyric

[GLOBAL: userInfoPane.html]
XeduR @Spyric
  • Enthusiast

  • 71 posts
  • Corona SDK

@Michael Flad, calculating things inline is a great point. Thanks! I actually intended to run those tests 10 times (i.e. create 36 000 entries) in order to have larger sample for measuring the performances, but I guess rewriting those 3600 entries over and over again would have done the trick as well.

Your point about the function calls may also be spot on. While performing the degrees to radian and vise versa calculations is simple to perform inline, now I need to read up on sin, cos and tan functions and see if about approximate them through inline calculations.

@StarCrunch, the way that I've written my module is centered entirely around the use of simple polygons. An alternative approach is certainly doable, but would require a complete overhaul of the module (or writing a new one altogether).

For the most part, there isn't really anything special about the module. Each object's vertices are on the xy-plane and the module calculates the angle between the light and each vertex. The length of each side is then calculated by using the light's z coordinate and the object's height. This results in numerous math.sqrt, math.sin, math.cos, math.atan2, etc. calculations. By being able eliminate most of these functions and performing them inline, the performance should improve greatly.

 

Attached Files


  • sporkfin likes this

[TOPIC: post.html]
#24

Michael Flad

[GLOBAL: userInfoPane.html]
Michael Flad
  • Contributor

  • 139 posts
  • Corona SDK

I don't think you'll get any benefit from inlining the code for manual trig calculations - given the relatively small difference for the very simple deg2rad sample. But it's more a general idea to keep in mind for stuff that's in an inner loop and might be done using a function call just because it's convenient (like, basic vector maths etc.).

 

Also about the 36000 entries, that's fine as you need high iteration counts to benchmark innerloops (I've actually upped it to 180.000 in my pasted version), but what's bad is to create the array up to a dimension of 36000 within the benchmarked code as this requires a lot of work besides what you actually want to benchmark. Lua creates the inital tiny array with let's assume 4 entries (too lazy to search for the code but that's not relevant anyway) then you outgrow it and Lua reallocates the buffer to 8 entries, this may include a copy of the existing 4 entires. Then the same from 8 to 16, to 32 to 64 and so on until it's big enough for your 36000 iterations.

 

The reason this is bad is, you now have additonal work that's exactly the same for both version you want to benchmark and that's included in your measured timings so the actual difference of the code you want to find out will appear smaller than it really is.

F.i. if all the array allocs and resizes consume 1 second and you measure your two implementations at 1.2 and 1.4 seconds it seems to be a relatively small difference but the faster one is actually twice as fast.


  • XeduR @Spyric likes this

[TOPIC: post.html]
#25

sporkfin

[GLOBAL: userInfoPane.html]
sporkfin
  • Contributor

  • 398 posts
  • Corona SDK

Great topic!  Has anyone developed or seen a speed benchmark for corona math functions.  For example, if I'm running thousands of math calls per second, would it be better to minimize sin, cos, atan (that's my impulse) or minimize math.ceil or math.round?

 

I thought I'd ask before I engage in this analysis myself.




[topic_controls]
Page 1 of 2 1 2
 
[/topic_controls]

Also tagged with one or more of these keywords: shadows