Author Topic: Light/Shadow Casting with rays for OpenXCom  (Read 6376 times)

Offline Skybuck

  • Colonel
  • ****
  • Posts: 223
    • View Profile
Light/Shadow Casting with rays for OpenXCom
« on: March 08, 2022, 09:35:32 am »
What is needed for this is X,Y,Z coordinates inside some title or so and bounding box detection of cells/tiles. Also some sun coordinates, and possibly other light source coordinates :)
 
Tomorrow or so and coming days, I will dive into the source code of OpenXcom and see if I can get something done.

Any help/pointers/hints where to look would be appreciated :)
« Last Edit: March 09, 2022, 01:58:13 am by Skybuck »

Offline Yankes

  • Commander
  • *****
  • Posts: 3207
    • View Profile
In OXCE there is already simple version of light "ray-tracing", it is done in tile space.

Offline Skybuck

  • Colonel
  • ****
  • Posts: 223
    • View Profile
LOL, You call that ray-tracing ? HAHA. I don't see any ray-tracing, I see some tiles slightly changing in brightness and sometimes some bullit shadows ? What are you talking about ? =D

Anyway yesterday I was a bit vague in my mind but today/"this morning" I am clear and on coke, yes coca cola lol, is that a violation btw ? Anyway.

I will describe an algorithm in case I don't come through with code, so that perhaps another programmer with  more OpenXCom development experience can try.

So let's first look at what is not necessary.

The interesting thing is that it's not necessary to cast rays from the camera to the scene, because of the painter algorithm. I assume the sprites/bitmaps/tiles are painted from back to front. So this painter algorithm already solves the visibility problem to a large degree, perhaps even 100% except if we would want transparency as well.

So basically all the pixels that are visible/draw on the screen are auto resolved by the painter's algorithm and that means we can draw a conceptually line from the pixel in voxel space towards an artificial sun or other light sources.

If this ray is obstructed by other objects/voxels/bounding boxes then the pixel is not lit, otherwise it is lit. If it is lit we can perform additional calculations, like distance to sun or angle towards sun and we can shade it's color, make it brighter/or full color as it was or make it dimmer as if it's slightly in shadow receiving less light. If it's not lit we can make it a lot darker up to a maximum of zero ofcourse we don't want to wrap it around or some ambient value or so.

So what is necessary is that per pixel information is stored:

1. The tile that was drawn on this pixel.
2. The x,y,z of this tile.
3. The bounding box of this tile.

If possible maybe a zbuffer could be usefull as well or maybe not, maybe it's to limited precision or it might be difficult to incorporate since tiles all have different coordinates.

So once we have the information of 1,2,3 then we must do a ray vs tile bounding box intersection test.

Where does the ray enter the tile ? And where does the ray exit the tile ?

For this there is already an algorithm which can be transformed into a 3D version. This algorithm is called "Fast Voxel Traversion". It works very simple by computing the intersection of a line with it's x-axis, y-axis, z-axis as T slides along the line. Since the distance from tile to tile in single dimension is always the same, all that is necessary is to determine which intersection with which axis is closest and increment T with that distance. This will cause the line to slide from intersection axis to intersection axis and could and probably is just what  we need to very simple compute entry and exit points for the tile.

Then once we know exactly where this line enters, we can then try and covert this coordinates into localized voxel coordinates for the tile, and then we can even use the same algorithm inside a voxelized tile to see if there are any collisions along the path of the line.

And thus the hit detection algorithm is complete and allows us to determine if a ray hits anything inside a tile or not.

Come to think of it, perhaps there is already an algorithm inside the source code, for lasers, and other weaponry that could be re-used. I am not sure if it's voxel/tile based, but probably/possibility. I am also not sure how efficient it is because I have not looked at it, perhaps it uses the exact same algorithm.

Whatever the case may be this algorithm needs to be fast, because a lot of rays have to be computed. Very maybe it might be possible to compute 2x2 in case there is not enough processing...

But the fun thing about x-com is that it is kinda static, except for the weapons... and thus there is plenty of time to do all kinds of computations, as the player as trying to make a move or waiting for the enemy movements and such, it's a turn based game, so some waiting until the graphics rendering is done, is somewhat acceptable.

That leaves the worry about dynamic/interactive/real-time/animation events. One possibility is that an algorithm tries to predict the player moves and shots and starts pre-computing the lightning path... for bullits and other dynamic events so that it is already computed and stored in memory.

If the algorithm predicts the users correctly then the animation happens fluently, otherwise there may be a short delay before the animation happens.

Multiple different events should be predictable and thus multiple animations pre-rendered/computed, once the player made it's move those that are no longer predicted by the algorithm can tbe thrown out, while others could be kept if they are independent from the other animations, or to keep it simple all could be thrown out as the player makes his next move.

Bye for now,
  Skybuck.
« Last Edit: March 09, 2022, 01:58:54 am by Skybuck »

Offline Skybuck

  • Colonel
  • ****
  • Posts: 223
    • View Profile
Re: Light/Shadow Casting with rays for OpenXCom
« Reply #3 on: March 09, 2022, 02:02:36 am »
Also so far I like OpenXCom best, the mods over there work the best, OpenXCom auto-deactives malfunctioning mods. So first implementation from me while be tried on OpenXCom code base, maybe later it can be integrated into OpenXCom extended.

Any help with pointers to code that I should check for maybe re-use or usefull or inspiration would be welcomed.

Now I go give it a try... with windows 7 home edition and visual studio 2019 and the openxcom dependables and that is all that is needed to build openxcom.exe and a microsoft account away and a valid license which is free for visual studio 2019 community edition.

Offline Yankes

  • Commander
  • *****
  • Posts: 3207
    • View Profile
LOL, You call that ray-tracing ? HAHA. I don't see any ray-tracing, I see some tiles slightly changing in brightness and sometimes some bullit shadows ? What are you talking about ? =D

Then look more closely, in OXCE object cast shadows based on where is light source and what objects are in path:
https://www.youtube.com/watch?v=9oNroA3feEw

beside I do not see that your algorithm is lot better than current OXC version, probably less accurate because current version is critical for proper handing of corner cases.
Any proves that is faster than current version? And result paths are comparable e.g. bullets will not go past though some walls because code skip checking some voxels.


btw do not create multiple forum topics on same "thread", all your post/questions about this should be in current topic.

Offline Skybuck

  • Colonel
  • ****
  • Posts: 223
    • View Profile
Re: Light/Shadow Casting with rays for OpenXCom
« Reply #5 on: March 12, 2022, 05:44:08 am »
That is per tile lightning. It's nothing new, the game had that since the ms-dos version in ufo enemy unknown.

What I want to do is per pixel lightning so it will look a lot better.

To be able to do per pixel/per ray lightning and so forth, it is necessary to be able to "shoot rays" into the "scene/engine" and to "detect hits" / "collisions" with any kind of object/hitbox/volume etc.

This is why I am looking into calculateLine function. Furthermore the math/function must be as perfect as possible, otherwise some pixels will remain dark and it will look ugly.

Furthermore the rays should be drawn from the scene towards the sun to reduce floating point errors. Floating point errors near the sun are not a big deal.

I think it may be the opposite the bresenham line 3d algorithm might be the one not to handle all corner cases.

I am looking into this right now to find a good voxel traversal algorith, but it's hard with the clipping and math and re-usability of code and testing.

I just found my light casting/shadow code, from 2013, I had that idea since 1995, so now I should be a lot easier to implement it. Even ported it to cuda c in 2013 ! Wow time flies ! ;)

This code should be a lot better than the even older code I initially found...
« Last Edit: March 12, 2022, 06:53:51 am by Skybuck »

Offline Skybuck

  • Colonel
  • ****
  • Posts: 223
    • View Profile
Re: Light/Shadow Casting with rays for OpenXCom
« Reply #6 on: March 12, 2022, 10:41:30 am »
I used somebody elses code, modified it slightly to perfect first/last voxel and also integrated into game, this creates possibilities ! Just a test to see if it would work and indeed it does, no clipping code yet, there were some little quickers inside the game, like not being able to handle negative z but coded around that:

The same code below could also be used for lighting of voxels/pixels so this going to be interesting.

Code has been integrated into game in this branch:

https://github.com/SkybuckFlying/OpenXcom/tree/FastVoxelTraversalAttempt2

Original/slightly modified/perfected fast voxel traversal code:

The one that worked for me in 3D for both positive and negative directions (in CUDA C):

#define SIGN(x) (x > 0 ? 1 : (x < 0 ? -1 : 0))
#define FRAC0(x) (x - floorf(x))
#define FRAC1(x) (1 - x + floorf(x))

float tMaxX, tMaxY, tMaxZ, tDeltaX, tDeltaY, tDeltaZ;
int3 voxel;

float x1, y1, z1; // start point   
float x2, y2, z2; // end point   

int dx = SIGN(x2 - x1);
if (dx != 0) tDeltaX = fmin(dx / (x2 - x1), 10000000.0f); else tDeltaX = 10000000.0f;
if (dx > 0) tMaxX = tDeltaX * FRAC1(x1); else tMaxX = tDeltaX * FRAC0(x1);
voxel.x = (int) x1;

int dy = SIGN(y2 - y1);
if (dy != 0) tDeltaY = fmin(dy / (y2 - y1), 10000000.0f); else tDeltaY = 10000000.0f;
if (dy > 0) tMaxY = tDeltaY * FRAC1(y1); else tMaxY = tDeltaY * FRAC0(y1);
voxel.y = (int) y1;

int dz = SIGN(z2 - z1);
if (dz != 0) tDeltaZ = fmin(dz / (z2 - z1), 10000000.0f); else tDeltaZ = 10000000.0f;
if (dz > 0) tMaxZ = tDeltaZ * FRAC1(z1); else tMaxZ = tDeltaZ * FRAC0(z1);
voxel.z = (int) z1;

while (true) {
    // process first and subsequent voxels here

    if (tMaxX < tMaxY) {
        if (tMaxX < tMaxZ) {
            voxel.x += dx;
            tMaxX += tDeltaX;
        } else {
            voxel.z += dz;
            tMaxZ += tDeltaZ;
        }
    } else {
        if (tMaxY < tMaxZ) {
            voxel.y += dy;
            tMaxY += tDeltaY;
        } else {
            voxel.z += dz;
            tMaxZ += tDeltaZ;
        }
    }
    if (tMaxX > 1 && tMaxY > 1 && tMaxZ > 1)
   {
    // process last voxel here
  break;
  }
}

Offline Skybuck

  • Colonel
  • ****
  • Posts: 223
    • View Profile
Re: Light/Shadow Casting with rays for OpenXCom
« Reply #7 on: March 12, 2022, 11:55:11 am »
Translated the OpenXCOM c/c++ bresenham line 3d algorithm to Delphi, tested it, examine and:

I CAN CONFIRM THE FAST VOXEL TRAVERSAL ALGORITHM IS A LOT MORE ACCURATE THEN THE BRESENHAM 3D LINE ALGORITHM, AT LEAST WHEN doVoxelCheck := false;

EVEN WITH doVoxelCheck := True; THE BRESENHAM 3D LINE ALGORITHM WILL STILL MISS SOME CELLS !

VERY INTERESTING DISCOVERY !

Offline Yankes

  • Commander
  • *****
  • Posts: 3207
    • View Profile
Re: Light/Shadow Casting with rays for OpenXCom
« Reply #8 on: March 12, 2022, 01:12:32 pm »
That is per tile lightning. It's nothing new, the game had that since the ms-dos version in ufo enemy unknown.

What I want to do is per pixel lightning so it will look a lot better.

To be able to do per pixel/per ray lightning and so forth, it is necessary to be able to "shoot rays" into the "scene/engine" and to "detect hits" / "collisions" with any kind of object/hitbox/volume etc.
First of all, original game do not have proper lightning, because light go troughs walls and only depend on distance and ignored levels.
My lighting obeys walls and floors. This is 10000 time more complex and compotation demanding than original.

And for your project.
Per pixel you say? Do you know that this game have 2d graphic? how you calculate normals for flat sprites?
Another thing how do you plan do it without GPU? My lightning is on edge of limits for CPU can do where I only shade whole tiles.
And you plan incense work up to by 32*40 times?

Offline Skybuck

  • Colonel
  • ****
  • Posts: 223
    • View Profile
Re: Light/Shadow Casting with rays for OpenXCom
« Reply #9 on: March 13, 2022, 01:19:46 pm »
"First of all, original game do not have proper lightning,"

Original game had some kind of tile lightning. I am looking to improve OpenXCom to the maximum possible of graphic fidelty it can have. There is a lot of untapped potential. The goal of re-creating x-com has been achieved. Now it is time to take it to the next level.

"| because light go troughs walls and only depend on distance and ignored levels."

Valid complaint here, with real lightning inside of houses might become dark. Perhaps extra lights need to be added to game data.

"My lighting obeys walls and floors."

I am not sure what you are referring to ? OpenXCom, OpenXCom Extended ? A certain mod ? A certain set of options ?

"This is 10000 time more complex and compotation demanding than original."

Original ran on 33 MHz, so 330.000, so your version would require 330 GHz.

"And for your project. Per pixel you say?"

Yes per pixel, is the original idea to see how it looks like. This is what the original in a weird way does. Thanks to sprite rendering.The sprite rendering can be taken to a next level.

If that fails or doesn't look good, next step would be to do it per voxel. But this may not be necessary.

"Do you know that this game have 2d graphic?"

Yes, this is the brilliant part about it. It's not just 2d graphics. It's 2d graphics combined with 3d graphics.

The original had 2 kinds of graphics per sprites, not all but the 3d's yes.

The 2 kinds of graphics are:

1. 2D graphics sprites to show what the voxel 3d sprite would look like from it's orientation. In principle these 2d sprites are pre-rendered 3d voxel sprites.

2. 3D voxel, scaled down, run length compressed, 1 bit hit boxes. These were used to do hit detection of rays.

Combine these two restores the 3D voxel sprite. It is not necessary to have 3D voxel color data, the 2D colored sprites are "layered/pulled" over these 3D hit box/voxel detections.

The same can be done for lighting, the 3d voxels are used to detect hit of light rays. The sprites are then used as a texture to get color data for what the light color should be.

"How you calculate normals for flat sprites?"

Normals are not required. The 2d sprite is layered over the 3d hitboxes. The 3d hitboxes are interpreted as voxels. Each voxel has a 3D box, the normals for such a 3D box are known.

Thus these flat surfaces can be used to approxiamete the lightning. More advanced computations could be done by interpolation the voxels to create half voxels if so required.

"Another thing how do you plan do it without GPU?"

A first implementation on CPU would be easiest to see how it looks, then to asses the runtime it takes. Since the game is turn based and usually slow there is plenty of time to render the scene, very few interactive computations needed, except when a soldier moves, a bullit flies, or an explosion happens. Some of that could be pre-computed and/or re-used. Parts of the scene could also be pre-rendered and re-used if it was not changed.

As a matter of fact the entire scene could be rendered in a gigant 3D voxel scene. Since computers now have gigabytes of ram. I am pretty sure the entire level of a typical xcom level may residue in memory completely on a voxel to voxel basis.

However such incredibly memory usage might not be necessary if it can be computed per title and so forth to save some memory, this stays in line with the original idea/architecture of the game and could be used to scale up the graphics of the game to proportions never seen before in any computer game.

Sprites could be scaled by 4x times the size and re-done by artist.

It seems sprites are 16x16x24 ? At high resolution still looks nice if battlescape is not scaled. However what if the sprites are doubled in size 32x32x64. Perhaps this allows 3D artists to create nicer looking sprites and re-do the entire game at more detail. Perhaps even 64x64x128 for insanely cool graphics. Or 128x128x256  or 128x128x128 or even 256x256x256.

My preference would more likely be something like 256x256x256 and if needed to be scale it down. So that initial graphics files are max quality. This also prepares the re-imagined game for high resolution monitors like 4K and 8K.

"My lightning is on edge of limits for CPU can do where I only shade whole tiles."

I am unaware of what lightning you are referring to. So far you have showed a link to a youtube video of Terror from the Deep. I am not so much interested in TFTD. It was a nice game, but my focus will be on X-COM UFO Enemy Unknown.

"And you plan incense work up to by 32*40 times?"

OpenXCom runs fine on my laptop. The existing lightning of soldiers in the dark and such can be kept. An extra layer of lightning can be added on top of it.

The current laptop resolution is 1600x900.

Which is 1.440.000 rays.

Each pixel on the screen can and should be shaded at least once.

Once this is achieved, then asses how it looks, and perhaps add additional lightning if enough cpu is left.

Another option is to switch to multi-threading and/or cuda.

However my laptop has broken 3D chip, so for now openl and/or cuda is out of the question.

Better to have CPU rendering anyway ;)

Offline Meridian

  • Global Moderator
  • Commander
  • *****
  • Posts: 8616
    • View Profile
Re: Light/Shadow Casting with rays for OpenXCom
« Reply #10 on: March 13, 2022, 01:49:54 pm »
> "My lighting obeys walls and floors."

I am not sure what you are referring to ? OpenXCom, OpenXCom Extended ? A certain mod ? A certain set of options ?

He's referring to OpenXcom Extended with directional lighting engine turned on.
(by default it is turned off to keep the vanilla experience)

Anyway, we're looking forward to your great new engine... if it delivers what you describe, I'll be the first one to merge it into OpenXcom.
Good luck.

Offline Skybuck

  • Colonel
  • ****
  • Posts: 223
    • View Profile
Re: Light/Shadow Casting with rays for OpenXCom
« Reply #11 on: March 13, 2022, 01:52:37 pm »
Anyway back to the original idea for the algorithm to not confuse with what I wrote above.

Theoretically there would be indeed 1600x900 rays. However these do not need to be traversed because the end points and therefore the hit boxes/detections/intersect points are already known.

The painters algorithm, possibly incombination with voxel hit boxes can be used to compute the final points of the rays. This is what makes this algorithm incredibly fast. No rays need to be traversed. Even though with this new algorith the traversing is incredibly fast. However the traversing only has to be done for bullits, and also only for titles. So that saves already major computation.

So this will not be the typical raytracer. This is something different.

Instead of computating the intersection points of rays, this algorithm idea uses painter algorithm to decide the outcome of where the rays should end up. There is also no perspective so that also changes it a bit. Once the painter algorithm is complete the scene is basically done and we are directly looking at the final results of the rays.

Thus ray intersection/traversal computations are simply replaced by the computation necessary to perform the painther algorithm.

Here it becomes an interesting question: How much does it actually save, apperently a lot... I am not exactly sure how this works in the game, I do see some event driving handlers that react to mouses or other events.

It may be computationally cheaper to perform the painter algorithm and fill in a bunch of voxels and/or sprite colors to get the end of the ray.

So this solves the visibility problem already.

What is left is the shading problem. For this rays will need to be pulled from the location of the pixels/sprites/voxels towards a imaginery sun, or even lights inside the game itself.

One interesting candidate to try this out on are the actual lights on some terror maps, that could be an interesting start to try this idea out.

From there light traversal is done with fast voxel traversal algorithm. However I see a possibility to speed this algorithm up considerably.

It's a two phase algorithm:

1. Because of the usage of tiles, enormous ammounts of traverse time can be saved. If if the tile is an "air" title, the ray passes completely through it and thus these pixels/voxels inside this title do not need to be processed, and thus the ray travels/traverses to the next tile and so forth, until the ray traversal actually enters a title that has content/hit boxes.

and thus then phase 2 of the algorithm happens:

2. In the second phase, the ray is traverse inside the title to see which voxels inside the tile are passed through and finally hit. Once a hit is detected the algorithm can stop, unless it is transparent. This is where Terror of the Deep could also benefit from it by doing so perhaps wonky cos/sin shifting of pixels to mimic water breaking of light.
Once it returns with a hit, the x,y,z is known, the sprite pixel corresponding to the x,y,z should be known as well, and now distance to light is in a matter of fact already known, it is one of tMaxX, tMaxY, tMaxZ, possibly the maximum or the minimum, not sure yet, probably maximum. Thus this also saves on expensive square root computations, which is pretty cool.

Offline Skybuck

  • Colonel
  • ****
  • Posts: 223
    • View Profile
Re: Light/Shadow Casting with rays for OpenXCom
« Reply #12 on: March 13, 2022, 01:57:57 pm »
"
He's referring to OpenXcom Extended with directional lighting engine turned on.
(by default it is turned off to keep the vanilla experience)
"

How does one turn it on ? Does it require a re-compile ? Changing a setting in some config file ? Or a build in option in menu ?

Does it use opengl/direct/shaders ? Or does it run on CPU ?

Offline Yankes

  • Commander
  • *****
  • Posts: 3207
    • View Profile
Re: Light/Shadow Casting with rays for OpenXCom
« Reply #13 on: March 13, 2022, 02:13:19 pm »
"First of all, original game do not have proper lightning,"

Original game had some kind of tile lightning. I am looking to improve OpenXCom to the maximum possible of graphic fidelty it can have. There is a lot of untapped potential. The goal of re-creating x-com has been achieved. Now it is time to take it to the next level.

"| because light go troughs walls and only depend on distance and ignored levels."

Valid complaint here, with real lightning inside of houses might become dark. Perhaps extra lights need to be added to game data.

"My lighting obeys walls and floors."

I am not sure what you are referring to ? OpenXCom, OpenXCom Extended ? A certain mod ? A certain set of options ?


OpenXCom Extended, I started this fork. Youtube video I posted previously show exactly this change, you can see "shadows" cast by objects in game.
This maximin that is possible using original game data.





"This is 10000 time more complex and compotation demanding than original."

Original ran on 33 MHz, so 330.000, so your version would require 330 GHz.



How much of this 33MHz was used for light? I would say 1MHz, this will mean 10GHz and on my CPU its 3s. On some maps literality that much take to make update of light. This mean I was not far from mark with my estimation.





"And for your project. Per pixel you say?"

Yes per pixel, is the original idea to see how it looks like. This is what the original in a weird way does. Thanks to sprite rendering.The sprite rendering can be taken to a next level.

If that fails or doesn't look good, next step would be to do it per voxel. But this may not be necessary.

"Do you know that this game have 2d graphic?"

Yes, this is the brilliant part about it. It's not just 2d graphics. It's 2d graphics combined with 3d graphics.

The original had 2 kinds of graphics per sprites, not all but the 3d's yes.

The 2 kinds of graphics are:

1. 2D graphics sprites to show what the voxel 3d sprite would look like from it's orientation. In principle these 2d sprites are pre-rendered 3d voxel sprites.

2. 3D voxel, scaled down, run length compressed, 1 bit hit boxes. These were used to do hit detection of rays.

Combine these two restores the 3D voxel sprite. It is not necessary to have 3D voxel color data, the 2D colored sprites are "layered/pulled" over these 3D hit box/voxel detections.



You can't combine them, Xcom 2d graphic data and hit boxes were only superfluous connected. You can see it yourself, I attach debug view form OXC where you can see Voxel space. You can recognize shapes and what is what but if you look closely nothing match exactly. Probably only flat walls relay match.






The same can be done for lighting, the 3d voxels are used to detect hit of light rays. The sprites are then used as a texture to get color data for what the light color should be.

"How you calculate normals for flat sprites?"

Normals are not required. The 2d sprite is layered over the 3d hitboxes. The 3d hitboxes are interpreted as voxels. Each voxel has a 3D box, the normals for such a 3D box are known.


But 3d hit boxes do not match graphic.



Thus these flat surfaces can be used to approxiamete the lightning. More advanced computations could be done by interpolation the voxels to create half voxels if so required.

"Another thing how do you plan do it without GPU?"

A first implementation on CPU would be easiest to see how it looks, then to asses the runtime it takes. Since the game is turn based and usually slow there is plenty of time to render the scene, very few interactive computations needed, except when a soldier moves, a bullit flies, or an explosion happens. Some of that could be pre-computed and/or re-used. Parts of the scene could also be pre-rendered and re-used if it was not changed.

As a matter of fact the entire scene could be rendered in a gigant 3D voxel scene. Since computers now have gigabytes of ram. I am pretty sure the entire level of a typical xcom level may residue in memory completely on a voxel to voxel basis.

Yes, there are voxel engines that could show spaces with accuracy like Xcom voxel space but you should be ready to spend years to make some thing like this for OpenXcom.





However such incredibly memory usage might not be necessary if it can be computed per title and so forth to save some memory, this stays in line with the original idea/architecture of the game and could be used to scale up the graphics of the game to proportions never seen before in any computer game.

Sprites could be scaled by 4x times the size and re-done by artist.

It seems sprites are 16x16x24 ? At high resolution still looks nice if battlescape is not scaled. However what if the sprites are doubled in size 32x32x64. Perhaps this allows 3D artists to create nicer looking sprites and re-do the entire game at more detail. Perhaps even 64x64x128 for insanely cool graphics. Or 128x128x256  or 128x128x128 or even 256x256x256.

My preference would more likely be something like 256x256x256 and if needed to be scale it down. So that initial graphics files are max quality. This also prepares the re-imagined game for high resolution monitors like 4K and 8K.

"My lightning is on edge of limits for CPU can do where I only shade whole tiles."

I am unaware of what lightning you are referring to. So far you have showed a link to a youtube video of Terror from the Deep. I am not so much interested in TFTD. It was a nice game, but my focus will be on X-COM UFO Enemy Unknown.
TFTD and UFO is SAME game, especially for OXC where you can switch between them on fly.


"And you plan incense work up to by 32*40 times?"

OpenXCom runs fine on my laptop. The existing lightning of soldiers in the dark and such can be kept. An extra layer of lightning can be added on top of it.

The current laptop resolution is 1600x900.

Which is 1.440.000 rays.

Each pixel on the screen can and should be shaded at least once.
And how many light sources you plan to support? 1? 3? or maybe 1000+ that is standard for my light engine in OXCE.


Once this is achieved, then asses how it looks, and perhaps add additional lightning if enough cpu is left.

Another option is to switch to multi-threading and/or cuda.

However my laptop has broken 3D chip, so for now openl and/or cuda is out of the question.

Better to have CPU rendering anyway ;)

You can look screens I post there, to create voxel view engine do it in 1-2s on my CPU, changing line algorithm will not fix it, to make it work you need full blown voxel engine that allow fast querying ray hits (in log(n) time or even better const time).

Offline Skybuck

  • Colonel
  • ****
  • Posts: 223
    • View Profile
Re: Light/Shadow Casting with rays for OpenXCom
« Reply #14 on: March 13, 2022, 02:19:21 pm »
Anyway, so this new light/shadow casting/rendering idea. Let's examine how it might run.

https://www.ufopaedia.org/index.php/Battlescape_Map_Generation

Most common map size is 50x50x4

Tiles size documentation not found but it seems to be 16x16x24, which is probably width, depth, height or something ? not sure which is which. but I think 24 is probably height and not depth.

So now compute how many tiles will fit on my laptop screen 1600x900 :):

1600 / 16 = 100
900 / 24 =  37,5 so say 38.

100x38 = 3800 tiles, perhaps multiplied by a height of 4 tile levels = 15200

Anyway the tile grid for a screen is roughly 100x38x4 so this can be consider space paitioning grid.

The worst case diagonal is something like
100x2 + 38x2 + 4x2 = 284 traversals per ray max, this is over estimated.

Once a "filled" title is detected, it then needs to perform an additional traversal of the tile itself.

Worst case diagonal is 16x2 + 16x2 + 24x2 = 112 inner traversals.

Thus worst case traversal scenerio is: 284 + 112 = 396 traversals.

So for a screen of 1600x900 = 1440000

1440000 x 396 traversals = 570.240.000

One possible problem that is over looked with this approach is when the sun is very low, buildings from far away might block the sun which would make it necessary to do much larger traversals. One possible solution would be to keep the sun high up for now. Or perform low sun computations if computer allows it.

Keep it mind that this traversal algorithm could potentially be made in parallel, by computing all integers between x0,y0,z0 and x1,y1,z1 with 3 single dimension loops. Where T is computed for each integer. Producing three already sorted lists, which can be stored in arrays or cuda arrays for parallel access/computing without locking.

Once computed, arrays can be merged. One possible idea to find collision inside these arrays is to use gather approach to find which entry is closest hit. Processing it in parallel may waste some computational resources. Another possibility is to have warps compute the most likely directions to find collisions first and the preemptively kill/end the warp/kernel once found, this may require some global variable which each warps inspect to see if it's to be terminated.

Anyway back to CPU figures:

570.240.000 is a bit much for a CPU to handle. At least main RAM has a latency of about 400 nano seconds. Processing this ammount of traversal lookups would require:

570240000 * 400 nanoseconds = 228096000000 nanoseconds

228096000000 / (1000 x 1000 x 1000) = 228,096 seconds worst case scenerio which is somewhat exaggarated.

Perhaps real world scenerio is closer to 100 seconds, still a lot !

So relief will come from L2 and L3 cache hits, how much is hard to predict.

Part of the algorithm could be multi-threaded to benefit from more cache hits in L1, L2, L3 data caches.

Perhaps on a 16 core machine: 100 x 16 = 6,25 seconds rendering time.

Now it's starting to come near something usable.

However this outcome is unstatisfactory for todays hard so a better solution must be found.

One possibility which comes to mind is computing bounding boxes for empty space and using that to traverse the rays faster and to save on tile traversal computation time.

Seeing the fast ammount of empty space in x-com maps, this should offer quite some speed up, how much exactly is unknown and hard to predict but it's worth a try.

Bye for now,
  Skybuck.