I made a perspective-correct 3d engine (that works with only 1 camera angle), rendering 600+ tiles at a smooth fps! The only problem is I need help filling in those tiles - they are 4-sided polygons and I can get all 4 points of each on the screen. I just need help filling those polygons - and I don’t know any way to in either blocks or typescript. If someone knows how, that info (like either fillrectangle that supports angles that aren’t strictly 90 degrees or a fill command similar to the image editor fill tool99 or any other trick to fill shapes in code) would be much appreciated.
If any of the Makecode team (@richard, @jwunderl, @Donuts, @hassan, etc.) or a forum user who knows a lot about Arcade know if this is possible easily or not, a reply would be much appreciated.
I made a small update (which was sent on stream) but it still does not have filling of polygons
UnsignedArduino suggested some ways that could be feasible for filling, but I’m not sure (yet) exactly which route I’ll take in attempting this… I just wish sprite-utils had triangle fill… @jwunderl …
I have been working on a 3d renderer also, and I have code for filling in a triangle. I was thinking of making it into an extension. So far, you can fill in a triangle with whatever color you like. I also had a special version of it that textures the triangle, without transforming the texture. I used the Barycentric Algorithm, which is short makes a rectangle around the triangle, and for each pixel in that rectangle, if it lies inside of the triangle, to draw there. this, and this were very helpful.
single color triangle filling
what it looks like in the simulator
the rectangles it uses to calculate
textured triangles
an example of what I mean by “texture not being transformed”
Although this is really cool, it is one of the slower methods for filling triangles, especially if you have a long, skinny, diagonal triangle.
The blocks are in the functions. For the regular triangle, the inputs are x1, y1, x2, y2, x3, y3, color, and a true/false statement for if you want the rectangle to be shown.
I will probably make this into an extension very soon…
And some changes to make it all support loop from X left to right.
We need yeild Y at given X of 3 edges, intead of outputing all Y edge by edge. Typescript doesn’t support “yeild”, so I defined a Line class, with next() method.
For point position calculated by accumulation, keep state(via Line class instance) wait for next calling with next X.
Result
On my Meowbit :About 12ms each filling solid color, 17ms each filling with texture, with random points, running 100+ time continues without update screen. About 20+ms if update screen every time.
On my simulator: About 1~2ms
This is wrote in several hours, should have bug inside, LOL. Feel free to report bugs.
Well, I’ve been trying to make my own triangle generator, but it kinda makes Star Trek logos instead of triangles… That’s a problem…
Also, @AqeeAqee your triangle drawer isn’t SUPER fast (at least it works), but it is pretty much unplayable at this point…
This is my port of a gpu-optimized triangle drawer but using the CPU so its really slow…
I might try to make one (in the future) that calculates all the positions that it needs to draw lines, sticks them into an array, then loopes over that array to draw the lines at the end of the frame. I’m not sure if that’ll even be fast enough though… I might just resort to a wireframe art style like this if I can’t get a triangle-drawing algorithm that is fast enough…
I might as well just ask… @kwx do you know how to fill polygons efficiently? (like 300/frame)
After last post, I think it over again, cause I am not very satisfied with the speed of result somehow. Suddenly, I awared that function calls are a little slow in Typescript, and there’s many function calls( about (maxX-minX)*3+3) times. So the Targets should append one “Avoid function call as much as possible”
Then I remaked a new version:
In this version:
removed class and next method
all minY&maxY of X are cached into a array(len=160x2),
only one function for each edge, no embeded function, calculated and cached in one call
Result
On my Meowbit :About 5.5ms each filling solid color, 8.8ms each filling with texture, with random points, running 100+ time continues without update screen. About 9.6/13ms if update screen every time.
On my simulator: About 0.2~0.5 ms
About Fill Polygon
This algorithm can fill polygons too. 4 or more edges, are all fine as long as any vertical line(x) cross edges 2 times at most.
Fortunately, what ever perspective transfrom applied, a rectangle/trapezoid will be still met this condition.
That means you need not split polygon into triangles in advance.
So I add a FillPolygon4() method
Result
On my Meowbit :About 5.9ms each filling solid color, 10.6ms each filling with texture, with random points, running 100+ time continues without update screen. About 10/15ms if update screen every time.
@richard
I am glad to, if you feel I’m qualified.
BTW, my time zone is much early than west coast US, hope it’s not a big problem, if need communication frequently.
So that confirms you’re adding polygon support natively??? NEAT! I haven’t coded in c++ but Id assume it isn’t too difficult. I probably won’t contribute though because it probably wouldn’t be a super good 1st project… Especially to optimize math for a first project in a different programming language…
the most i have done with c++ was make a simple command line shell for the nintendo ds/dsi
sadly i couldn’t find any graphics libraries tho . but thats understandable the console is 18yrs old and most websites about homebrew dev for it are shutdown or offline
Take a look at the triangles.ts file in my renderer demo https://arcade.makecode.com/03733-23293-89994-81627. It’s all based on slicing polygons into trapezoids with vertical left and right edges, and then drawing them one vertical pixel strip at a time in a byte buffer, then copying that byte buffer to the screen with image.setRows(x, buf). It draws the 1-pixel-wide slices of all triangles that intersect this X position simultaneously, so each vertical pixel column only gets written to the screen once. Also, it exclusively uses fixed-point (integer) math for this part of the codesince floating point math is extremely slow on hardware.
At the low level, I’ve done some loop unrolling to speed things up, for example this function that draws two alternating colors for dithering:
export function drawTriLineAlternating(tri: ActiveTrapezoid, buf: Buffer, col0: number, col1: number) {
const y0 = Fx.toIntFloor(tri.a_y)
const y1 = Fx.toIntFloor(tri.b_y)
let y = y0
if (y & 1) {
// Swap the colors so that col0 is consistently on even Y
const tmp = col0
col0 = col1
col1 = tmp
}
let y1end = y1 - 7
while (y <= y1end) {
buf.setUint8(y, col0)
buf.setUint8(y + 1, col1)
buf.setUint8(y + 2, col0)
buf.setUint8(y + 3, col1)
buf.setUint8(y + 4, col0)
buf.setUint8(y + 5, col1)
buf.setUint8(y + 6, col0)
buf.setUint8(y + 7, col1)
y += 8
}
if (y <= y1 - 3) {
buf.setUint8(y, col0)
buf.setUint8(y + 1, col1)
buf.setUint8(y + 2, col0)
buf.setUint8(y + 3, col1)
y += 4
}
if (y <= y1 - 1) {
buf.setUint8(y, col0)
buf.setUint8(y + 1, col1)
y += 2
}
if (y <= y1) {
buf.setUint8(y, col0)
//++y
}
tri.a_y = Fx.add(tri.a_y, tri.a_dydx)
tri.b_y = Fx.add(tri.b_y, tri.b_dydx)
}
Of course, having native code to do triangle drawing would be way faster than trying to do so in TypeScript, so having that would make a lot of fancier graphics possible.
I made this triangle renderer but it has worse perf than yours @AqeeAqee :
It was based off of this algorithm. It does have some glitching though.
Also, @AqeeAqee , thanks for making your quadrilateral renderer work with my game! I had trouble because it kept crashing (I wasn’t rounding the numbers, as I later found out.) I will use the version that you made until the c++ triangle renderer is finished and ready for the game. Thank you!
It’s so cool bc now I can do stuff like this:
In case you are wondering:
This project started out as a quest to revamp my old project, which originally was supposed to be a remake of the engine of the flash (and now HTML5) game series “Run.” (run, run 3) That project was entirely hardcoded and used basically no math, with sprites (manually scaled bc no scaling), rotation that wasn’t proper, and bugs (not to mention the fact that the tunnel only had 4 sides, and wan’t perspective corrected.) This project resolves many (if not all) of those old issues, but I don’t think I’m going to be just ripping off the original Run games. I’ll try to make it unique, even though it will still be running through gravity changing tunnels, like it being first-person (probably) and maybe with some sort of collectible. It’ll be inspired by the look of the original games, but it won’t be a remake.
Neat! This is an excellent example! I may not take the effort on implementing this algorithm depending on how long it takes for the C++ to be written (as there already is one that runs), but if it takes a long time for the C++, I will definitely put this to use!
)