Hardware accelerated polygon fill using LMMM

Ascended (10768)

29-12-2022, 02:10

I give you this little demonstration:

100 COLOR 15,0,0:SCREEN 5
110 COLOR=(4,7,0,0):COLOR=(8,0,7,0):COLOR=(12,7,7,0)
120 P=0:SETPAGE P,1-P:CLS
130 FOR I=-31 TO 32
140 SETPAGE P,1-P
150 J=ABS(I)-16
160 LINE (64,74)-(191,137),0,BF
170 LINE (80+J,74)-(80-J,137),4,,XOR
180 LINE (159+J,74)-(159-J,137),4,,XOR
190 LINE (96-J,74)-(96+J,137),8,,XOR
200 LINE (175-J,74)-(175+J,137),8,,XOR
210 COPY (64,74)-(191,137) TO (65,74),,XOR
220 P=1-P:NEXT I
230 GOTO 130

It just draws the edges of the polygon, and then fills them by executing an LMMM with XOR with a 1-pixel overlapping offset. The limitation being that you can have as many colours as there are bits, or more if the polygons don’t overlap. It can be used to great effect to implement a Glenz Vector effect.

Obviously in assembly this could be optimised to let the VDP do back-to-back polygon fills while the CPU clears the VRAM and draws the lines. The CPU should do the line drawing anyway since for lines angled more than 45 degrees horizontally only the first pixel should be drawn (with a modified Bresenham algorithm).

By Parn

Paladin (837)

29-12-2022, 14:40

Sweet! I like this a lot!

I hope you don't mind, I created an MSXPen with it. It's here:

https://msxpen.com/codes/-NKT63cW9LB2RD5chqg8

By aoineko

Paladin (1002)

29-12-2022, 21:52

The V9938 had very advanced functions like these logical operators, but it is not easy to find concrete use case in a game. In my Screen 8 car racing game, I used this feature to create a shadow under the car by drawing a circle that sets the high order bits of each RGB component to 0 to darken the background color. This is the only use case I have found so far.

If there had been a bit shifting operation, we could have done all the mathematical operators!

By NYYRIKKI

Enlighted (6067)

29-12-2022, 21:59

Well... This is nice looking trick for BASIC because BASIC is slow, but if you write modified Bresenham algorithm in assembler then it is definitely better just to execute LINE commands on VDP because that should be a lot faster and still gives the same end result.

Here is a bit similar trick that I used to create "fast" movement on MSX-BASIC

By NYYRIKKI

Enlighted (6067)

29-12-2022, 22:32

aoineko wrote:

The V9938 had very advanced functions like these logical operators, but it is not easy to find concrete use case in a game.

True... but with vectors they can be quite handy. Here and here are few practical BASIC examples.

By pizzapower

Master (165)

29-12-2022, 23:11

Hm... using this trick with a palette rotation could result in some nifty animations pre-calculated by a Python script to detect intersections (including concave polygons) by drawing some more lines to turn painting on and off. 🤔

By Grauw

Ascended (10768)

30-12-2022, 02:57

In principle, let’s say you have your polygons rendered in a span buffer (a list of a list of spans per scanline). Then to blit the span buffer on screen, first clear the screen to all zeroes, then for each scanline, loop through the spans (X, C) keeping a running variable CC (0 initially), then on the start X of each span put a pixel with CC=CC XOR C. Finish up with an LMMM XOR covering the draw area with a 1-pixel offset to fill the polygons.

By Bengalack

Paladin (747)

30-12-2022, 10:50

aoineko wrote:

The V9938 had very advanced functions like these logical operators, but it is not easy to find concrete use case in a game.

Not polygon fill though, but I sometimes use the operators on copy in Lilly -- There are a couple of screen 5 screens (like this, and the options-screen) where I have the source font in one color, and depending on the underlying color index (and not the color itself), the resulting font color becomes different. You just have to set up your palette properly. (There is a cost of course, so performance is always evaluated).

By NYYRIKKI

Enlighted (6067)

31-12-2022, 15:17

Grauw wrote:

I can see your point here. Doing 4 points + copy vs 2 lines or 3 lines with CPU sorting... There might be some use case for it, but it has to be very special especially if you take in to count the time that it takes to clear the row.

By pizzapower

Master (165)

17-03-2023, 17:29

I wrote a little Python script to explore this idea.

Encoded image:

LMMM-restored image:

By Grauw

Ascended (10768)

18-03-2023, 03:21

Nice demonstration!