Add triangle fill/draw methods to images

[riknoll]

We should really have an efficient implementation of this in the sim/c++. There's been a lot of interest in the forum but performance is a bottleneck right now when implemented in user code.

[riknoll]

@benvillalobos @eanders-ms FYI

[riknoll]

@AqeeAqee has expressed interest in implementing this, so i've pushed some starter code in pxt-common-packages that defines the shim:

https://github.com/microsoft/pxt-common-packages/tree/triangle-fill

In this branch I've added an Image.fillTriangle method that should be available on images

There are two places this has to be implemented, I've added comments in both places:

1. libs/screen/image.cpp - this is the C++ implementation that will run on hardware devices
2. libs/screen/sim/image.ts - this is the browser implementation that will run in the simulator

To set up a developer environment:

1. Install Node.js
2. Install the pxt cli:

npm install -g pxt

4. Clone and link the repos:

git clone https://github.com/microsoft/pxt-arcade.git
git clone https://github.com/microsoft/pxt-common-packages.git
cd pxt-common-packages
git checkout triangle-fill
npm install
cd ../pxt-arcade
npm install
npm link ../pxt-common-packages

5. Spin up a local server:

cd pxt-arcade
pxt serve

This will launch pxt-arcade on localhost in your browser. When you make changes in pxt-common-packages, pxt serve should automatically pick them up and you'll see them when you refresh.

[riknoll]

One thing to note: C++ changes take a long time to compile (it goes to our cloud compiler). I usually find that it's easiest to implement the function for the browser first and then port the code over to C++ to minimize the headache!

[riknoll]

ah whoops, there's a bug in the code i pushed. one moment!

[riknoll]

alright fixed! Also, @jwunderl has helpfully reminded me that @AqeeAqee can't actually test the sim implementation because it's a private repo. For that reason, don't worry about the sim! if you are still interested, implement the C++ and @jwunderl or I will port your code to the simulator.

Lastly, you can greatly speed up the C++ build by deleting the following entries in pxt-arcade/pxtarget.json:

        "libs/d5prj",
        "libs/esp32",
        "libs/hw---n3",
        "libs/hw---n4",
        "libs/hw---rpi",
        "libs/hw---samd51",
        "libs/hw---rp2040",
        "libs/hw---vm",
        "libs/rpiprj",

These define hardware targets for boards other than the meowbit! if you're just testing with the meowbit, then you can safely remove these and skip those compile steps

[AqeeAqee]

Got it!
Thanks for you & jwunderl's guide and tips. Will start up soon, and sync up with you when I have progress.

[AqeeAqee]

Hi Richard
I need some help on setup environment.

I followed the steps you provided. After excute "pxt serve", the web page showing this forever

output logs:

https://github.com/AqeeAqee/temp/blob/main/npm_install.log
https://github.com/AqeeAqee/temp/blob/main/pxt_serve.log

[jwunderl]

@AqeeAqee can you run node -v real quick and confirm which version you are running?

[AqeeAqee]

v10.15.1

[AqeeAqee]

I checked latest version is 18.15.0, v10 is too old LOL, installing...

[jwunderl]

Yeah, unfortunately v10.15.1 is exactly one version too old to run as I believe textencoder was added by default in v11 (/v12 lts) -- I'm running v16lts fwiw; we should probably update pxt-arcade's package.json engines field like we do in pxt https://github.com/microsoft/pxt/blob/master/package.json#L60, I'm actually a little surprised it didn't get mad because of pxt's engine requirement but maybe it only works for top level package.jsons and not deps

[AqeeAqee]

Web server starts, and the editor is worked too. Thanks!
But here is a new problem: there is no fillTriangle() under Image obj

[AqeeAqee]

I am sure all methods added by richard have been pulled in source files.

[riknoll]

@AqeeAqee possible your repos became unlinked! Sometimes running npm install after the initial linking will do that. Try running npm link ../pxt-common-packages in pxt-arcade again.

[eanders-ms]

Hey @AqeeAqee awesome you're taking a stab at this! I was thinking this approach might be a good one, given Arcade's low-end hardware spec: http://www.sunshine2k.de/coding/java/TriangleRasterization/TriangleRasterization.html#algo1 (Standard Algorithm section). Just a suggestion. Looking forward to seeing what you come up with.

[AqeeAqee]

@riknoll
Thanks, it fixed!

BTW, there's other errors in
https://github.com/AqeeAqee/temp/blob/main/npm_install.log
https://github.com/AqeeAqee/temp/blob/main/pxt_serve.log
These can be igore safely?

[AqeeAqee]

@eanders-ms
This is a wonderful experience for me, learning with Makecode experts helping, no reason to be missed.
Thanks very much for your reference ariticle! I will study it before writing code.

[riknoll]

@AqeeAqee yup, those errors can be ignored!

One day, we'll remove them. One day.

[AqeeAqee]

Hi all,
Just checked in the first version.
This version focus on implement filling in 2 mode, for comparing. We can discuss, and decide which mode will be keep, then I will clean up and optimize further.
You can test with this project : https://arcade.makecode.com/S67692-48468-11606-15245

Mode1: Cache

• Cache all Y in 2 arrays
• Upside: faster
• Downside: need occupy extra mem bytes (cache width x2), in this verison cache 160 px width.

Mode2: Yield

• Generate Y of each edge at X when we get there, in an other word, got Y of edges parallelly.
• Upside: less footprint in mem
• Downside: slower, cause need to call "next()" repeatly

Fill Triangle Test Result:
(Average of calling 1000 time, from Typescript project, with random points each time, with screenRange=(0,160,0,120), or over range=(-0.5W,-0.5H, 1.5W, 1.5H)

Cache: ScreenRange= 0.417ms , OverRange=0.543ms
Yield: ScreenRange= 0.480ms , OverRange=0.744ms

Polygon4:

• fill with 2 mode descript above.
• Note, as I metioned in this post, only polygons meet condition can be filled correctly. (any vertical line(x) cross edges 2 times at most)

Fill Polygon4 Test Result:
Cache: ScreenRange=0.526ms , OverRange=0.725ms
Yield: ScreenRange= 0.641ms , OverRange=1.062ms

[AqeeAqee]

[Note for others]
The test project works in local pxt environment with this branch. Can not run on public Arcade site before this branch be merged.

[AqeeAqee]

Sorry, check in failed, I will try later.
(the accessing Github issue of our network, you know)

[AqeeAqee]

Seems I have no right to commit to pxt-common-packages. Need I fork it to my repo?

[eanders-ms]

Yes you will need to fork. For local testing, I'm hopeful we'll be able to sync your fork and npm link it as we normally do.

[AqeeAqee]

Forked and checked in at
AqeeAqee/pxt-common-packages@e8a71f1

[riknoll]

awesome stuff @AqeeAqee! Playing around on my pygamer, it's even faster (as expected). As for the memory tradeoff, i say we go for checking in the non-cache strategy first and if speed becomes an issue try out the cache optimization. 640 bytes definitely isn't the worst thing in the world but it's not trivial either

you should open this as a PR on pxt-common-packages! it's easier to give specific feedback that way. you can mark it as a draft if you're still working on it. at a glance, the code looks great!

[AqeeAqee]

Great to hear you are satisfied the performence. Totally agree your choose, I think so, memory is criticle concern for Arcade devices.
I will clean the code, and create PR soon. And with the FillPolygon4() method?

[riknoll]

yeah, go ahead and include both the triangle and polygon4 in the PR!

[AqeeAqee]

Created PR: microsoft/pxt-common-packages#1439, to https://github.com/microsoft/pxt-common-packages/tree/triangle-fill, is it right?

[riknoll]

@AqeeAqee yup, thanks! We'll review and continue this conversation over in that PR!

[AqeeAqee]

Hey @AqeeAqee awesome you're taking a stab at this! I was thinking this approach might be a good one, given Arcade's low-end hardware spec: http://www.sunshine2k.de/coding/java/TriangleRasterization/TriangleRasterization.html#algo1 (Standard Algorithm section). Just a suggestion. Looking forward to seeing what you come up with.

Thanks for your reference again. The main structure of trigangle fill implement I checked in is just similar to the 2nd algorithm in this article.

• But after edge1(first short edge) finished, I didn't calculate the location of intersection point. With generator and states of edge0(longest edge), we can just go ahead without particular operation, from 2nd X of 2nd triangle with edge2 and edge0, as edge0 already get there. This saving some times.
• And to avoid "falt edge plotted twice", I add a dryrun at first X of 2nd triangle(generator go through 1st X, and ready to 2nd and followings, without drawing)

[AqeeAqee]

Hi @riknoll and @jwunderl
I am still trying to tune fill algorithm further.
After replaced drawRect() with new added drawVLineCore(), skipped repeatly calling "img->makeWritable()" and etc. Faster about 20%~30%, much faster than cache mode even.
I will create another PR to commit it after current one approved.

[AqeeAqee]

new PR microsoft/pxt-common-packages#1441
More faster.