Image mapping : Peer review needed

The Oric video chip is not an easy beast to master, so any trick or method that allows to achieve nice visual results is welcome. Don't hesitate to comment (nicely) other people tricks and pictures
jbperin
Flight Lieutenant
Posts: 285
Joined: Wed Nov 06, 2019 11:00 am
Location: Valence, France

Re: Image mapping : Peer review needed

ThomH wrote:
Mon Sep 21, 2020 10:21 pm
the classic serial implementation for affine texturing a polygon is just two adds per pixel. In pseudo-C:

Code: Select all

``````for(x = start ... end) {
pixel[x][y] = pixel[texture_x][texture_y];
texture_x += offset_x;
texture_y += offset_y;
}
``````
... with appropriate modifications to fixed point. You can set up offset_x/y at the start of each scan line either by tracking them along each edge and doing a divide, or by plane or barycentric calculations.

For now I've managed to put the calculation under the following form:

Code: Select all

``````for(x = start ... end) {
pixel[x][y] = pixel[texture_x][texture_y];
texture_x = K * (y-y0) - R * (x-x0);
texture_y = S * (x-x0) - T * (y-y0);
}
with (x0, y0) screen coordinates of reference point of texture
and K, R, S and T being values computed with trigonometry``````

Which is similar to what you describe because:
• Along a given scanline, terms (y-y0) don't vary so they can be considered as constant and then it can be written like that:

Code: Select all

``````    texture_x = C_1 - R * (x-x0);
texture_y = S * (x-x0) - C_2;``````
• As for terms (x-x0), they only increment by one from one pixel to the following one.
So, considering the nth pixel in the scanline, its texture coordinates are:

Code: Select all

``````    texture_x[n] = C_1 - R * (x-x0);
texture_y[n] = S * (x-x0) - C_2;``````
and considering its immediate neighbour on its right

Code: Select all

``````    texture_x[n+1] = C_1 - R * ((x+1)-x0) = C_1 - R*(x-x0) -R = texture_x[n] - R
texture_y[n+1] = S * ((x+1)-x0) - C_2 = S*(x-x0) - C_2 + S = texture_y[n] + S
``````
So it lead to the algo you've given.

Code: Select all

``````    texture_x[n+1] =  texture_x[n] -R
texture_y[n+1] =  texture_y[n] + S
``````
The problem is that R and S are numbers like 2.6 or 3.4 (with non neglictable decimal part) that I can't just round after a division.
I have R and S under the shape Ra/Rb and Sa/Sb with Rb<Ra and Sb<Sa.

Either I do the division and work with Q8.8 fixed point values to keep precision and accuracy.

Code: Select all

``````R = Ra / Rb
S = Sa / Sb
for(x = start ... end) {
pixel[x][y] = pixel[texture_x][texture_y];
texture_x -= R;
texture_y += S;
}
``````
Or I use an algo as the following one to keep the fractionnal representation

Code: Select all

``````for(x = start ... end) {
pixel[x][y] = pixel[texture_x][texture_y];

texture_x 	+= -Rb;
ErrorX 		= Ra - texture_x;
If (|ErrorX*2| > Rb) Then
texture_x -= Ra

texture_y 	+= Sb;
ErrorY 		= Sa - texture_y;
If (|ErrorY*2| > Sb) Then
texture_y -= Sa

}``````
In first case, I have a 16 bits division (at the beginning of the scanline) followed by two 16 bits additions for each pixel.
In second case, I have no division and then 3 or 4 8-bits additions for each pixel.

So it's hard to figure out what's more efficient.

For now I only protyped in python the formulae given at the beginning of this post (i.e I haven't integrated the iterative formulation of the texture_x/y calculation)

I use this simple texture file:

When I do a projection on a plane 3D surface (it's not real perspective fill .. it's just image stretching ) by using floating point arithmetic it gives the following result: (I draw triangles to see the shape onto which I map the image)
And when i use 8 bits integer calculation (with lookup tables for euclidian norm, arctan, sin and cosine), it gives:
It doesn't look too dirty but last steps of calculation (the ones that compute R=Ra/Rb and S=Sa/Sb) are still done on floating point values and they are not incremental. So it might get a bit dirtier when I will deal with that.

What are plane or barycentric calculations ?

sam
Posts: 56
Joined: Sun Jul 09, 2017 3:28 pm
Location: Brest (France)
Contact:

Re: Image mapping : Peer review needed

It look like something is wrong with the rendering. The circle surrounding the A is not convex when projected (look at the upper right quadrant: it points inward when projected). Correct projection should preserve concavity of shapes & "straightness" of segments (look at the right side of the A-letter.. it isn't straight after projection). You should try to project a (possibly rotated) checkerboard to clearly view the perturbing geometrical aberrations this simplified projections creates.

And may be this: on the original source the image is centered, but it doesn't look centered wrt to the bounding box when projected. It looks to me a bit shifted to the left, that is closer to the viewer than it needs to be. One can further see this when comparing the space to the drawing from the left or right edge of the bounding box. They both look the same. However the right part of the projection being further away, the remaining space should look "smaller" than the space to the left. I'm not sure I explain this correctly.. but something looks weird considering the left/right space around the projected drawing and the bounding box.

my 2 cents.

sam.

jbperin
Flight Lieutenant
Posts: 285
Joined: Wed Nov 06, 2019 11:00 am
Location: Valence, France

Re: Image mapping : Peer review needed

sam wrote:
Tue Sep 22, 2020 6:15 pm
It look like something is wrong.
You should try to project a (possibly rotated) checkerboard
sam.
Oups indeed ..
It seems the algo need a fix .. Thank you for your remark

ThomH
Flying Officer
Posts: 233
Joined: Thu Oct 13, 2016 9:55 pm

Re: Image mapping : Peer review needed

No, it's not perspective correct — it's an affine rendering. So exactly what you'd see on an original Playstation. As per discussion above, the problem is that texture (x, y) aren't linear in screen space; (x/z, y/z, 1/z) are but then you need at least one divide per pixel to get back to regular (x, y).

Old DOS titles tend to divide only every e.g. 16 pixels, and then linearly interpolate in between. That's very obvious in Descent, slightly less so in Quake. Later, more enlightened Playstation titles subdivide entire polygons. Subdivision was Sony's answer to just about everything on the PS1, including clipping, so there was direct library support for that.

Alternatively, go the Wolfenstein/Doom way and avoid divides entirely by just drawing walls in vertical strips and floors in horizontal. In both cases you're stepping along a line where z is constant. So, again, no divides. As long as you do the work at the edges correctly.

Dbug
Posts: 3681
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Re: Image mapping : Peer review needed

What Thom wrote.

Basically, in the specific case of a labyrinth where the walls are always vertical, there are plenty of optimizations that can be done which solve the specific issue you have (which would not work at all in something like a 6DOF* game like Descent), and if you choose to have the eyes (camera) at the center of the walls, you just need to rasterize one slope (top or bottom), which gives you the other one by symetry, and also the total height of the vertical segment, and you can use a precomputed table of vertical increments to move in your source texture

* 6 degrees of freedom

jbperin
Flight Lieutenant
Posts: 285
Joined: Wed Nov 06, 2019 11:00 am
Location: Valence, France

Re: Image mapping : Peer review needed

Dbug wrote:
Wed Sep 23, 2020 3:10 pm

Basically, in the specific case of a labyrinth where the walls are always vertical, there are plenty of optimizations that can be done which solve the specific issue you have (which would not work at all in something like a 6DOF* game like Descent), and if you choose to have the eyes (camera) at the center of the walls, you just need to rasterize one slope (top or bottom), which gives you the other one by symetry, and also the total height of the vertical segment, and you can use a precomputed table of vertical increments to move in your source texture
I don't know why it's so slow ..
proto.zip
I haven't yet put the 3D stuff ..

I just tried to find a way to display a texture based on an array that could come from a raycasting system.

artwork by Rax

jbperin
Flight Lieutenant
Posts: 285
Joined: Wed Nov 06, 2019 11:00 am
Location: Valence, France

Re: Image mapping : Peer review needed

Two textured wall + a sprite

ibisum
Wing Commander
Posts: 1445
Joined: Fri Apr 03, 2009 8:56 am
Location: Vienna, Austria
Contact:

Re: Image mapping : Peer review needed

Wow. This looks amazing!

jbperin
Flight Lieutenant
Posts: 285
Joined: Wed Nov 06, 2019 11:00 am
Location: Valence, France

Re: Image mapping : Peer review needed

Thank you.

For now it is just amazingly slow ..

It takes almost 4 sec to compute and render this image

ibisum
Wing Commander
Posts: 1445
Joined: Fri Apr 03, 2009 8:56 am
Location: Vienna, Austria
Contact:

Re: Image mapping : Peer review needed

Its still a beautiful picture! I hope you get it optimised and playable, it sure looks tantalising ..

iss
Wing Commander
Posts: 1276
Joined: Sat Apr 03, 2010 5:43 pm
Location: Bulgaria
Contact:

Re: Image mapping : Peer review needed

jbperin wrote:
Tue Feb 09, 2021 10:59 pm
For now it is just amazingly slow ..
It takes almost 4 sec to compute and render this image
Congrats, it looks cool!!!
Maybe it's little slow because it renders also the enemy who's hiding behind the stone pillar .

Dbug
Posts: 3681
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Re: Image mapping : Peer review needed

jbperin wrote:
Tue Feb 09, 2021 10:59 pm
Thank you.

For now it is just amazingly slow ..

It takes almost 4 sec to compute and render this image
Starting to look good

Now, question for you: Do you think the same method could be used to draw some form of textured floor?

jbperin
Flight Lieutenant
Posts: 285
Joined: Wed Nov 06, 2019 11:00 am
Location: Valence, France

Re: Image mapping : Peer review needed

ibisum wrote:
Tue Feb 09, 2021 11:27 pm
Its still a beautiful picture! I hope you get it optimised and playable, it sure looks tantalising ..
Look at the picture below, it shows a record with 2x overclock to give an idea of what it could be if it was translated to assembly. Do you still think it's nice ?
iss wrote:
Wed Feb 10, 2021 1:34 am
Maybe it's little slow because it renders also the enemy who's hiding behind the stone pillar .
LOL .. if only there was an enemy that was consuming the whole cpu, i could optimize by removing it. But unfortunatly .. it's slow by nature.
Dbug wrote:
Wed Feb 10, 2021 12:32 pm
Now, question for you: Do you think the same method could be used to draw some form of textured floor?
I must admit I totally missed the textured floor topic. I have no idea on how to do that. Do you have any clue?

It is already very slow .. dunno if it is reasonnable to weigthen more the stuff ..

The following capture was recorded with x2 overclock.

Attachments

Dbug
Posts: 3681
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Re: Image mapping : Peer review needed

Look at the picture below, it shows a record with 2x overclock to give an idea of what it could be if it was translated to assembly. Do you still think it's nice ?
If it's still 100% in C, and using the OSDK, I'm pretty sure a proper assembler port would be much faster than 2x, I would not be surprised if a 8x is doable.

In the case of columns, it would almost make sense to do a first pass, before drawing the walls, to tag the sections of walls that will be hidden entirely by some of the sprites, and then, when you raster the world, you can just skip these columns.

If you implement that with a 2D zbuffer, with for example two entries (one for the depth, one for the id), you can eliminate probably 90% of the overdraw, and even have sprites over sprites, correctly drawn, monsters partially hidden by columns, etc...

As usual, the fastest code is the one that does not run.

Same thing for the erasing, in most cases, with this type of column based rendering, you don't need to clear the screen at all, just update what needs to be updated.

jbperin
Flight Lieutenant
Posts: 285
Joined: Wed Nov 06, 2019 11:00 am
Location: Valence, France

Re: Image mapping : Peer review needed

Dbug wrote:
Thu Feb 11, 2021 8:31 am
If it's still 100% in C, and using the OSDK, I'm pretty sure a proper assembler port would be much faster than 2x, I would not be surprised if a 8x is doable.
Yes it is 95% C for now.
And just like you I think it could be between 4 and 8 times faster by turning to assembly.
I long to discover what will be the final speed once it is coded in assembly language.
But for now I force myself to sharpen the C prototype the more it is possible so that I only port an optimal approach.
Dbug wrote:
Thu Feb 11, 2021 8:31 am
In the case of columns, it would almost make sense to do a first pass, before drawing the walls, to tag the sections of walls that will be hidden entirely by some of the sprites, and then, when you raster the world, you can just skip these columns.
That would be a seducing tips but I don't think it is possible here because sprites has a kind of alpha channel that make them transparent on some part of their texture.
So I need to draw the background to fill this transparent parts.

Dbug wrote:
Thu Feb 11, 2021 8:31 am
If you implement that with a 2D zbuffer, with for example two entries (one for the depth, one for the id), you can eliminate probably 90% of the overdraw, and even have sprites over sprites, correctly drawn, monsters partially hidden by columns, etc...
I have a 2D zbuffer with three entries (one for the depth, one for the wallId and one for texture coordinate).
I use it when I draw the sprite to determine which part of a sprite is visible so if a sprite is partially hidden by a wall, I should only draw the visible part of it .. based on the 2D zbuffer resulting from raycasting.
Since sprites can have transparent part, and that multiple sprite can simultaneously be visible on the same display column, I'm thinking of creating a loop to draw sprites in descending order of distance so that the closest ones overdraw the more distant ones.

I know it's the brute force way to proceed but I have no better idea on how to deal with :
iss wrote:
Wed Feb 10, 2021 1:34 am
the enemy who's hiding behind the stone pillar .
Perhaps I should consider working on a texel array in memory rather than displaying directly on screen.
The idea could be to draw various layers (walls, sprite in descending orders of distance) in a texel array in memory
And then writing into screen memory only once the texel array is prepared.
That way it could:
- save the time consumned by writing rgb components that are going to be overdrawn (because losing the time of rewriting a texel color in a cell is cheaper than rewriting three RGB components).
- have a faster screen update routine that transform the prefilled texel array into the rgb scanlines on sreen only at the end.

What do you think of this idea ?

The problem is that screen is 80*64 texel large .. so I would need 5kb buffer for such a texel buffer and it is totally unaffordable

The last compilation of the C proto gave me:

Code: Select all

``````Creating final program proto.TAP
File 'build\proto.tap' is 35919 bytes long (14 bytes header and 35905 bytes of data)``````
Dbug wrote:
Thu Feb 11, 2021 8:31 am
As usual, the fastest code is the one that does not run.
You're dawn right man !!
Dbug wrote:
Thu Feb 11, 2021 8:31 am
Same thing for the erasing, in most cases, with this type of column based rendering, you don't need to clear the screen at all, just update what needs to be updated.
I can't really figure how such a magic could be possible but I'm interested. Do you have suggestions ?