Pages of trig

[+Andrew Davie]

I feel like I'm back in high school, struggling with math once again.

 

I'm working on a circular masking/wipe, in C.

 

The fundamentals are that I have a lookup table which gives me a "line" of pixels, starting at the "middle" of a scanline, with n pixels set ON (where n is a multiple of two, and goes from 0 to 40).. In other words, the mask gives me a scanline across a circle. I get the left/right ON bits of the circle for any given possibility (that is, 0 pixels ON, up to 40 pixels ON).  It's symmetrical on the screen, but due to odd PF mirroring, not symmetrical in data and so needs 6 bytes/line for this table. I have a maximum of 100 lines (same above the center point as below).  So that's the fundamental... this table has 21 rows; that is a 0-row (no PF bits on) up to the 20th row (20 PF bits on, left and right sides).  The on-pixels start in the middle and increase one pixel at a time towards the edge, as we go up the index.  Maybe easier to just show it...

 

const unsigned char mBit[][6] = {

    // index via # pixels on line

    { XXXX____, XXXXXXXX, XXXXXXXX, XXXX____, XXXXXXXX, XXXXXXXX },   //20
    { XXX_____, XXXXXXXX, XXXXXXXX, XXXX____, XXXXXXXX, _XXXXXXX },   //19
    { XX______, XXXXXXXX, XXXXXXXX, XXXX____, XXXXXXXX, __XXXXXX },   //18
    { X_______, XXXXXXXX, XXXXXXXX, XXXX____, XXXXXXXX, ___XXXXX },   //17
    { ________, XXXXXXXX, XXXXXXXX, XXXX____, XXXXXXXX, ____XXXX },   //16
    { ________, _XXXXXXX, XXXXXXXX, XXXX____, XXXXXXXX, _____XXX },   //15
    { ________, __XXXXXX, XXXXXXXX, XXXX____, XXXXXXXX, ______XX },   //14
    { ________, ___XXXXX, XXXXXXXX, XXXX____, XXXXXXXX, _______X },   //13
    { ________, ____XXXX, XXXXXXXX, XXXX____, XXXXXXXX, ________ },   //12
    { ________, _____XXX, XXXXXXXX, XXXX____, XXXXXXX_, ________ },   //11
    { ________, ______XX, XXXXXXXX, XXXX____, XXXXXX__, ________ },   //10
    { ________, _______X, XXXXXXXX, XXXX____, XXXXX___, ________ },   //9
    { ________, ________, XXXXXXXX, XXXX____, XXXX____, ________ },   //8
    { ________, ________, XXXXXXX_, XXXX____, XXX_____, ________ },   //7
    { ________, ________, XXXXXX__, XXXX____, XX______, ________ },   //6
    { ________, ________, XXXXX___, XXXX____, X_______, ________ },   //5
    { ________, ________, XXXX____, XXXX____, ________, ________ },   //4
    { ________, ________, XXX_____, _XXX____, ________, ________ },   //3
    { ________, ________, XX______, __XX____, ________, ________ },   //2
    { ________, ________, X_______, ___X____, ________, ________ },   //1
    { ________, ________, ________, ________, ________, ________ },   //0
};

I think I got that right.  Anyway, the problem is...  I want to be able to generate a mask for the whole screen which is a circle of radius n where n ranges from 0 to ... whatever.  If n = 20 then we get a circle full-width of the screen (radius 20 pixels = diameter 40 pixels).  Of course the corners of the screen would not be masked (the circle does not fully cover the screen) so we need to be able to allow the radius to go much bigger. But I'll get to that later.

 

So, the problem becomes -- for any scanline on the screen, lookup the 6 mask bytes from the above table.  Again, the table gives all "mask-line" possibilities for covering circle of radius 0 to 20.  But we want to be able to mask a circle of a requested radius.  Oh, and we can't use trig functions, or division. Just to make it more interesting.

 

Here's my thinking so far...

 

If we consider the center point of the screen C as our 0-scanline, and just look at lines above that (because below that will be just mirroring anyway)...  so for each scanline we have L which is the # scanlines from C.  and R is the radius of the circle. Given PF pixels are about 4x as wide as tall, we'll divide L by 4 so that we're in equivalent units and don't get an ellipse instead of a circle.  Let's call L/4 just l.

 

Now, back to my days of trig, if we consider the quadrant  formed with the vertical from C up the middle of the screen, and the horizontal from C to the right edge of screen.  For any given L and R we want to know the index into the mBit table.  That is, d where d varies from 0 to 20.  Effectively the width of pixels for that line.  Another way of thinking of this is that d is one side of the right-angled triangle formed by these x,y coordinates (with C at 0,0)....   [0,0], [0,L], [d,L]. In other words, calculate "d"

 

 

Digging up my trig, consider the angle in the lower right triangle as ang

Then sin(ang) = opp/hyp = L/R

cos(ang) = adj/hyp = d/R

tan(ang) = opp/adj = L/d

 

Now if we want d, we can get it by   d= L/tan(ang) or d = R.cos(ang).

we know sin(ang) = L/R and we have L and R as given, and since L is <=R, then sin(ang) will be in range 0-1

And reducing this to a "sensible" binary value, let's make that 0-255.  But we can't do division (a given), so let's create a table of reciprocals and then we can multiply by reciprocal.  Since we know that the maximum line count is 100 that will be a 100 entry reciprocal table. Given a number n, then reciprocal[n] will give us a 16-bit fixed-point representation of 1/n (with entry 0 invalid).  Thus, to do L/R, we can now go.  L * reciprocal[r].  So that gives us the value of sin(ang).

 

Now given any sin(ang) we can also have a table to lookup cos(ang).  That is, a 256 byte cos[] table where the sin value is the index.  Another way of saying this; for any given sin(ang), the cos(ang) will be constant, and so the sin(ang) can effectively give us cos(ang) just by direct lookup in the table, without having to go cos(sin-1(L/R)).  We just go cos(L*reciprocal[r]) and note that the cos table is not a table of cosines of angles. It's a table of cosines, given the sin of the angle as an index.

 

If we have the cosine of the angle, then we know cos(ang) = d/R, from above. So, d = R.cos(ang) -- which comes down to d = R. cos[L*reciprocal[R]].  That will give us the value we want, which is an index into the original mBit table.  If d > R, then we're off the table and use a full-pixel line.

 

That's the basic concept.  I'd need a reciprocal table, a cos table, and use fixed-point multiply (two per scanline).  It seems workable.

 

 

recip = reciprocal[R]

for each scanline on screen {

    L = abs(scanline-centerY)/4

    sin = L * recip

    cos = cosinegivensin[sin]

    d = R * cos

    maskPF0Left = mBit[d][0]

    maskPF1Left = mBit[d][1]

    maskPF2Left = mBit[d][2]

    maskPF0Right = mBit[d][3]

    maskPF1Right = mBit[d][4]

    maskPF2Right = mBit[d][5]

}

 

So the basic usage is pass in R (radius of circle) and scanline, and we get out 6 mask bytes for that scanline that will remove pixels outside the circle of radius R playfield pixels, for any scanline on the screen. I've bypassed the check where scanline is outside the circle, which should be trivial.

 

I just thought I'd share in case anyone has a much more sensible method of doing this and besides it helped to write it out.

 

 

[Thomas Jentzsch]

Have you thought about using Bresenham for a circle/ellipse?

[Omegamatrix]

Andrew, I'm trying to understand what you are trying to do, separarte of the implementation.

 

Are you actually drawing a circle, or just having a circular boundary of which you want to do some detection of objects being inside or outside of that boundary? Can you describe it a little more?

[+Andrew Davie]

44 minutes ago, Omegamatrix said:

Andrew, I'm trying to understand what you are trying to do, separarte of the implementation.

 

Are you actually drawing a circle, or just having a circular boundary of which you want to do some detection of objects being inside or outside of that boundary? Can you describe it a little more?

 

Sorry!

 

I'm trying to create a circular mask so that I can have some parts of the screen visible and some not visible.

The mask is applied to a screen buffer after the contents are "drawn" but before being displayed.

The mask is variable in radius (=size), so that I can animate that visible/non-visible experience.

I'll use it for a circular "screen wipe", pretty much like an iris-type shutter.

 

So, it's a SOLID circle, but formed on a per-line basis.  I'm not really looking for a "plot pixel at x,y" thing, more something that on a per-line basis will give me the 6 bytes of PF0 PF1 PF2/PF0 PF1 PF2 with appropriate bits set/clear in those bytes representing a scanline slice across a (potential) circle.

 

I'm pretty much there with a buggy implementation that actually looks a bit better than a pure circle, so I may keep that

 

 

 

 

[+MarcoJ]

I went through a bit of this for drawing circular crosshairs on Modern Battle. It takes too long to calculate sin in real time, so hard coded it with precalculated lookup tables. Used mspaint to draw circles of various sizes and then worked out the x and y plot for each given angle. Ended up with a 16 byte table (for 16 angles) for every given circle size of fixed values which mapped x and y for a circular quadrant. 

Edited May 27, 2021 by MarcoJ

[Dionoid]

Not sure if it helps, but for the PF iris in/out effect in my game, I basically divide the screen into tiles of 1x6 playfield pixels, which represent small squares on the screen.

Then every frame, I'm calculating the distance from each of the tiles to the center of the screen, using dx²+dy² (without bothering to take the square root of it).

Then when dx²+dy² < r² (where r is the increasing circle radius), I mark the tile as 'dirty', but only if it wasn't marked dirty in the previous frame, by adding the clause: AND dx²+dy² >= (r-1)². Note that for the opposite direction (i.e. a shrinking circle), I use dx²+dy² >= r² AND dx²+dy² < (r+1)² to mark tiles as 'dirty'.

 

After that, for each row of tiles, I check which of the 6 PF bytes in the line's display buffer should be drawn/updated, using the 'dirty' tiles. When *all* the bits of a PF byte are caused by 'dirty' tiles, I clean all the dirty bits of these tiles, indicating that the specific PF byte doesn't need to be updated anymore in the display buffer.

There are lots of little optimizations along the way, but this is the gist of it.

 

Edited May 27, 2021 by Dionoid

[+Andrew Davie]

18 minutes ago, Dionoid said:

Not sure if it helps, but for the PF iris in/out effect in my game, I basically divide the screen into tiles of 1x6 playfield pixels, which represent small squares on the screen.

 

Thanks for sharing. I was amazed when I first saw that effect in your game, and it was definitely inspiration for me to do something similar. I have grander plans... maybe... like a star-shaped in/out wipe. But I'm not really sure how best to do things yet. I have a functional version of a wipe that's quite buggy - but actually so visually pleasing I'm considering keeping it!

[Hakogame 箱亀]

Didn't read closely enough, please ignore.

Edited May 27, 2021 by Raccoon Lad

[+Andrew Davie]

I'm a bit supposed-to-be-doing-schoolwork, but I've been thinking about the above suggestions, and I think I now have a pretty good working concept/solution. Haven't coded, but I'm sure it will work.

 

It does work on the basic principle mentioned above that a "pixel" on the screen is either in the circle, or outside, as defined by (x^2 + y ^2) compared to r^2.   If x^2 + y^2 is larger, then the pixel is outside the circle, and so the mask bits should be zero.  I've used this basic principle to simplify the calculations for each pixel, and it goes something like this.

 

Choose an arbitrary point on (or off!) the 40 x n screen as our center-point.  Let's make square pixels, so n = scanline/4.  So, something like a 40x40 screen then.  And our Center is Cx, Cy.  And our radius is R2.  To simplify explanation, let's have a 40-bit array representing the PF pixels. Won't worry about the mirroring in this explanation;  just number the bits from 0-39 corresponding to X column on screen. Doesn't matter, just 40 bits side by side.

 

Pre-set the 40 bits to 0.

Init two variables, left_edge and right_edge to Cx.

These represent the "boundary edge" of the circle on any particular scanline. We start with them being right on the center-point's X position.

 

Now we iterate the scanlines.

But first calculate the squared distance to the center point from this scanline (Cx,0) to (Cx, Cy).  That's stored in "distance_left" and "distance_right".

When iterating, if distance > R2, then pixel is outside circle, otherwise inside.

 

Here's the basic stuff... but just one more addition after this...

 

For each scanline {

 (left edge check....)

    while (distance_left < R2 && left_edge > 0) {

      set_bit(left-edge)

      left_edge- = increment

      calculate new distance

    }

 

(right edge check...)

    while (distance_right < R2 && right_edge < 40) {

      set_bit(right_edge)

      right_edge+ = increment

      calculate new distance

    }

 

   if scanline = midpoint of circle, flip increments

}

 

So the above is marching the left and right edges based on the distance from the center point.

the distance_x values are the (x^2 + y^2) which is basically the (x position of an edge) ^2 + (scanline - Cy)^2)

 

 

 

Example:  center at 10, 10 and we're drawing scanline 0, with start left_edge = 10 (=Cx)..

we are looking at the left edge only here. The right edge proceeds in the same fasion...

 

x^2 + y^2 = (10-10)^2 + (10-0)^2 

 = 100

 

Let's say our desired radius is 11.  So R2 = 121.  This pixel is within the circle

set bit[x=10], then.

 

Now move left one...

center 10, 10, and drawing line 0 with left_edge = 9 (we've moved left one because last point was inside circle)...

x^2 + y^2 = (10-9)^2 + (10-0)^2

 = 1^2 + 100

 = 101

Still in the circle. set bit[9]

 

Move left again

left edge = 8

x^2 + y^2 = (10-8)^2 + 100

 = 104

still in circle. set bit[8]

 

Move left again

left edge = 7

x^2 + y^2 = (10-7)^2 + 100

 = 109

still in circle. set bit[7]

 

MOve left again.

left edge = 6

x^2 + y^2 = (10-6)^2 + 100

 = 116

still in circle. set bit[6]

 

Move left again...

left edge = 5

x^2 + y^2 = (10-5)^2 + 100

 = 125

 

Now that's outside the circle, and we stop iterating.

We're left with our x value being 5, and proceed to the next scanline.

We've set bits 10,9,8,7,6

 

We KEEP the mask array (40 bits) as we proceed....

 

Let's look at the next scanline...  y+1, and x=5

so distance is 

x^2 + y^2 = (10-5)^2 + (10-1)^2

 = 25 + 81

 = 106

That's inside the circle (R2=121) so we set bit[5]

 

Move left...

left edge = 4

x^2 + y^2 = (10-4)^2 + 81

 = 36 + 81

 = 117

that's inside again, so set bit [4]

 

move left...

left edge = 3

x^2 + y^2 = (10-3)^2 + 81

 = 49 + 81

 = 130

outside circle, so next scanline(2)

 

scanline 2...

x^2 + y^2 = (10-3)^2 + 64

 = 49 + 64

 = 113

inside circle, set bit[3]

 

move left.. left edge = 2

x^2 + y^2 = (10-2)^2 + 64

 = 128

outside, so next scanline(3)

we have bits 10,9,8,7,6,5,4,3 set in the mask.  The right-edge calculation would have set 11,12,13,14,15,16,17

 

scanline 3...

x^2 + y^2 = (10-2)^2 + 49

 = 64 + 49

 = 113

inside, so set bit[2]

 

move left. left edge = 1

x^2 + y^2 = 81 + 49

 = 130

outside, so next scanline[4]

 

scanline 4...

x^2 + y^2 = 81 + 36

 = 117

inside, so set bit[1]

 

move left.. left edge = 0

x^2 + y^2 = 100 + 36

 = 136

outside, so next scanline[5]

 

x^2 + y^2 = 100 + 25

outside, so next scanline [6]

 

x^2 + y^2 = 100 + 16

inside, so set bit[0]

 

... and since we're at 0 (left edge) we will just be getting "outside" until we're on the scanline of the center point.

When we reach the center point, we flip the edge's increment direction... instead of left_edge-- it becomes left_edge++, and mirror for the right edge.

 

Essentially we do a small number of checks on each scanline, shifting the edges outwards (for the top half of the circle) and inwards (for the lower half) by one pixel at a time, and determining if we are outside/inside the radius^2.  The lower half will be CLEARING mask bits, and the upper half SETTING the bits.  The left edge is bounded from 0..Cx and the right from Cx..39 inclusive.

 

Each scanline has a few operations, but mostly the mask is correct from the previous scanline. Just need to "trim the edges".

Instead of calculating the full X^2 + Y^2 on each line, we know that Y^2 only changes when you change to a new line, and X^2 can be done with a delta.  That is,   X^2 - (X-1)^2 = X^2 - (X^2 - 2X + 1) = 2X + 1 difference in each iteration, so no multiply required, just a shift and add. Same for Y delta, done once on each line. Pls ignore basic error in the maths, it's the principle I'm describing that's important  
 

This algorithm should allow any size circle with a center point anywhere on or off the screen.  I'll try implementing it when I have some free procrastination time.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

[+Andrew Davie]

Well, that worked nicely...

 

 

circleFadeDemo.bin

[+Karl G]

11 minutes ago, Andrew Davie said:

Well, that worked nicely...

It does indeed. I would also be curious to see the one that you say is buggy, but looked cool anyway. ?

[+Andrew Davie]

1 hour ago, Karl G said:

It does indeed. I would also be curious to see the one that you say is buggy, but looked cool anyway. ?

I didn't have a demo version but have re-implemented the buggy one... just for you....

 

 

[+Karl G]

That is indeed also a pretty cool effect  

[+fdr4prez]

Yeah, the buggy one is a nice transition for cut-scenes 

[Omegamatrix]

I love the circle demo Andrew. Well done!

[stepho]

Both look good.

 

I suspect the buggy version is due to round off errors due to the trig functions not being evenly spaced.
Eg, sin(1)-sin(0) is a lot larger than sin(90)-sin(89)                   where 90 degrees is a right angle, not radians.

 

I worked through the original algorithm and the maths is fine - assuming infinite precision.

 

I tried to think of other variations but none were as fast (theoretically) as yours.