UVM Wishlist #7
Comments
maximecb
added
help wanted
|
I'm a little embarrassed to show this is the state it's in, but I've been doodling since hearing about the project Saturday and I've got a start on some of the things on the list. I've got simple and crude text rendering with anti-aliasing / alpha blending and I am in the middle of implementing a Wu line drawing routine (but I have to go to sleep now, I'll finish it in the morning when my brain's working better.) Anyway, it's here: https://github.com/calroc/Thun/tree/master/implementations/uvm-ncc Like I said, it's embarrassing, but I wanted to be encouraging and I'm really excited about UVM! I'm going to use it to create a kind of IDE for a concatinative language called Joy. It's not BASIC but it will have a REPL and a simple text editor, so... there's that. :) Ciao! |
|
Hi @calroc! Very excited to see you doodling with UVM! :) I would definitely be interested in including some of your graphics code in the UVM examples if you're willing. The only thing that's a question mark in my mind is the compatibility of the inconsolata font with a CC0 license. Ideally I'd like the examples code and all its assets to be CC0 so that people can just do anything they want with it without worrying about licenses. I did some googling and it seems hard to find CC0 TTF monospaced fonts though. |
|
@maximecb I would love to pick couple of things like work on |
|
I've almost got the Wu anti-alias line algorithm licked. I'm doing something wrong though because I keep getting artifacts in the middle of the line (drawing from both ends at the same time.) In re: CC0 licensed fonts, I looked too and couldn't find any monospaced fonts that weren't pixel fonts, but some of those are pretty nice:
And I like "Tom Thumb" 4x6 pixel font: https://robey.lag.net/2010/01/23/tiny-monospace-font.html and https://github.com/gheja/tom-thumb-ttf |
That would be great. I think for string.h the C compiler is mature enough to implement everything. There are some tests in ncc/tests/string.c For stdio, I think we should be able to implement a minimalistic printf fairly easily. For the other file iO functions it's more tricky because we need to design system calls for files/streams and that hasn't been done yet. There's another open issue for that. |
Excited for line drawing. Once we have better float support we can use that to draw wireframe graphics.
Bitmap fonts can totally work. There are several more options on https://opengameart.org/ IIRC. You can directly search for game assets with a CC0 license which is pretty useful. |
|
Just looked at that monogram font and it looks quite gorgeous :) |
|
I've kind of got Wu lines working (at least for the "first octant"! That's the easy octant you know.) I gave up on the symmetrical version (where you draw the line from both ends simultaneously so you only have to do half as many iterations) because I couldn't get rid of artifacts at the center of the lines. I have some ideas how to fix that, but in the meantime just sweeping the whole major axis works fine (and we're not dealing with a 1980's microprocessor after all, eh?) I don't special-case the end points either, so it's not really the proper Wu algorithm. Still it looks nice! I tried a pixel font in the crude font machinery that I have so far, but (of course) Imagemagick draws the TTF scaled and with anti-aliasing, so it's not the actual bitmap, more like a screenshot of the bitmap, eh? (But if you want slightly blurry "pixel" fonts, that's good to go.) I'll write some code for actual bitmapped fonts... Interestingly the monogram bitmap is distributed as a JSON literal in it's own |
In re: float support, I'm a weirdo and an iconoclast, but my gut feeling is that you don't need floating point in a 64-bit world. However, as a matter of practicality (not to mention people taking your project seriously) there is all that sweet hardware that's already there and speaks float, eh? I'm not a graphics programmer, I look with awe on the folks who write shaders and deal with programming the GPU. What I'm getting at is, don't take my opinions on the matter seriously. On the one hand, it would be so cool if UVM could provide simple API for accelerated graphics, on the other hand that's a huge, deep rabbit hole that is made out of other rabbit holes in an ever-expanding fractal. That said, Chuck Moore used to have a wireframe 3D CAD system that fit on a deck of punch cards that he kept in his shirt pocket. I'm going to look into doing 3D math with integers (my dialect of Joy doesn't have floats), there's something called "rational trigonometry" which sounds promising. I wrote a 3D math system ages ago based on the code in "Physics For Game Developers", I got as far as a rotating cube. Hopefully I can come up with something. :) |
That's too bad. I hope you'll be able to make it work. At the moment we just have an interpreter and no JIT. The platform needs time to mature before effort is spent on building a JIT imo, so we do need to be able to squeeze as much performance as possible, especially for graphics.
It's probably because all the web kids can't be bothered to read a binary file 😅
I feel that way too. You can get really far with fixed point integer arithmetic, and with 32 or 64-bit integers, it seems like you basically shouldn't need floats at all for 2D or 3D video games. It's almost too bad that more engineering effort wasn't spent on accelerating fixed point computation... But like you said, there's just a lot of floating point hardware out there. It would feel wasteful not to have that capability. I also feel like people are going to expect FP support and would find it weird, would find UVM hard to target if it wasn't available 🤷♀️
The current interpreter should be fast enough that we'll be able to program something a Doom-like raycasted game. With a JIT compiler, we should be able to do decent 3D graphics with software rendering. Beyond that, I have more idea for maybe a SIMT execution model which could make use of multiple CPU cores, but that's much farther in the future. I also have some ideas for adding some simple "blitting" or alpha blending primitives that use SIMD on the host system. Kind of inspired by the Amiga. :)
Speaking of wireframe... Once we have line drawing working and I have structs working in NCC, I'd like to program an animation that's like a 3D fly through a wireframe city. Kind of like this, but in purple-ish synthwave colors :) |
|
Have you considered implementing bresenham until you can have anti-aliased lines? I couldn't find it in the examples folder |
|
That would work :) @neauoire is this your code? Would you be willing to share it under a CC0 license? |
|
It is my code, and yes please do use it under CC0. I don't want to change the license for moogle, but you may use this license whichever way you like :) |
|
Ok, I added a new header :) |
I'll take another whack at the symmetrical version tonight or tomorrow, but here's what I have so far for Wu lines: void carefree_wu_line(u32* dest, size_t dest_stride, u64 x, u64 y, u64 w, u64 h, u32 color)
{
// This isn't quite Wu's algorithm, although it uses the same
// fundamental trick of keeping track of both the intensity of
// the pixels to draw and the right time to increment the minor
// axis in a single error term.
//
// "An Efficient Antialiasing Technique", Xiaolin Wu
// Computer Graphics, Volume 25, Number 4, July 1991
// https://dl.acm.org/doi/pdf/10.1145/127719.122734
//
// "Graphics Programming Black Book" by Michael Abrash, chapter 42
// https://archive.org/details/gpbb20
// > Without loss of generality only lines in the first octant are considered.
assert(w > 0 && h > 0 && w > h);
// > We translate the point (x0, y0) to the origin,
// so y = kx where k = h/w with k <= 1
// (actually k < 1 because 45° lines are special-cased.)
u16 k = 0xFFFF * h / w;
u16 d = k >> 1;
while (w) {
w = w - 1;
u8 intensity = d >> 8;
carefree_alpha_blend_plot_pixel(dest, dest_stride, x, y + 1, color, intensity);
carefree_alpha_blend_plot_pixel(dest, dest_stride, x, y, color, 0xFF - intensity);
++x;
if (d + k >= 0xFFFF) {
d = k - (0xFFFF - d);
++y;
} else {
d = d + k;
}
}
}The I haven't written C in ages, so please forgive any goofs. Like, could |
|
Hmmm, well I've never seen this algorithm before but it seems like you may want to use |
|
I can't follow the intricacies of Wu's paper, but I gather that you don't need 64 bits for the error term since you're only interested in the N most significant bits anyway, so 16 is plenty. Would using |
|
Generally, using u32 or int will perform best, u64 almost the same. |
|
I got the symmetrical Wu algorithm working. (I tried to make it a little closer to your style.) // LIMIT is 16 bits of 0.999... in 0.16 format
#define LIMIT 0xffff
void draw_aa_line_first_octant(u32* fb, u32 fb_width, u32 fb_height, u32 x0, u32 y0, u32 x1, u32 y1, u32 color)
{
int dx = x1 - x0;
int dy = y1 - y0;
assert(dx > 0 && dy > 0 && dx > dy);
int error_adjust = LIMIT * dy / dx;
int error_accumulator = 0;
while (x1 >= x0)
{
u8 intensity = error_accumulator >> 8 & 0xff;
carefree_alpha_blend_plot_pixel(fb, fb_width, x0, y0, color, 0xFF - intensity);
carefree_alpha_blend_plot_pixel(fb, fb_width, x0, y0 + 1, color, intensity);
carefree_alpha_blend_plot_pixel(fb, fb_width, x1, y1, color, 0xFF - intensity);
carefree_alpha_blend_plot_pixel(fb, fb_width, x1, y1 - 1, color, intensity);
++x0;
x1 = x1 - 1; // bare --x1 compiles but doesn't decrement.
error_accumulator = error_accumulator + error_adjust;
if (error_accumulator > LIMIT)
{
error_accumulator = error_accumulator - LIMIT;
++y0;
y1 = y1 - 1;
}
}
}I'm just nailing down the various "reflections". I wrote a little demo program too that just draws lines from each corner of the window to the mouse position. |
|
Nice! Style looks good :) |
|
@calroc I just added syntax for global array initializers: https://github.com/maximecb/uvm/blob/main/ncc/tests/arrays.c#L6 This was motivated by the code you committed for the monogram font. This will make it a lot easier to embed data into code if we want to. |
|
Ah, that's awesome, I'll update the monogram font demo soon (no promises, but likely today.) I'm tempted to write some kind of simple run-length encoding... I made a start on (convex) polygon drawing last night, based on Abrash's Black Book ( https://archive.org/details/gpbb20/gpbb0/ ) Because |
|
BTW, Björn Höhrmann's "Flexible and Economical UTF-8 Decoder" ( http://bjoern.hoehrmann.de/utf-8/decoder/dfa/ ) works fine in NCC. It's not CC0 so it wouldn't be suitable for the |
For the purpose of UVM, I think a run-length encoding may just hurt performance or make the code harder to read. However, encoding everything into a global byte array would definitely be helpful. Another thing that would be really useful for the monogram font code is to have an integer scaling factor (e.g. 2x, 3x, 4x larger). Right now it's just too small to be legible. If we can polish up that code and add such missing features, we could potentially include it into a header to make it available to people.
Oh that's pretty cool :) Another thing I should add to the wishlist is something like SHA1 hashing. We might need that once we start to do networking and client-server stuff. Eventually I'd like to have a little UVM "app store" (or app catalog) with a GUI.
Nice. One thing I could do is add a syscall for something like That would make it pretty easy to fill pixels and could come in handy for other things. What do you think? |
Hey, that's great! I'll plug it in. It might take me a day or two to circle back to update the monogram font demo, but when I do I should be able to add a scale option (it's basically just stepping through the source bits at 1/2 or 1/3 or whatever of the destination scan rate, eh? Should be easy-peasy...) Just FYI, I spent most of yesterday writing NCC code "in anger" and had a lot of fun. (I'm porting Joy interpreter, I have parsing and printing working now, although it needs to be reworked to be less wasteful. I wrote a bunch of fun little bits of machinery like a simple hash table and a little heap to store strings, it sounds fancier than it is.) As part of that I cribbed this nice lil FNV hash function:
#define FNV_OFFSET 0xcbf29ce484222325
#define FNV_PRIME 0x100000001b3
u64
hash_key(char* key)
{
u64 hash = FNV_OFFSET;
for (char* p = key; *p; ++p) {
hash = hash ^ (u64)(unsigned char)(*p);
hash = hash * FNV_PRIME;
}
return hash;
} |
Nice. With global initializers and an unsigned int scale factor, it will be perfect 👌 . Good enough to implement a little text editor or a spreadsheet program or something (which I might play with for fun).
Would love to have a decently fast triangle rasterizer. Spinning cube will be an important milestone 😆 Would be fun to have a low-res spinning cube, then add a scanline effect on top, and use the font to draw the words "SOFTWARE, RENDERING, LIVES" in alternation. Currently working on slowly bringing up floating-point support in NCC. That will give us floating-point sine/cosine as well. It's totally possible to do perspective projection with fixed point math, but I think that code would be hard to parse for most people. Fixed point math is almost a lost dark art. That being said, if you want to have fun writing code to rotate a cube with
I'm glad you're having fun. I hope it's not the MacGyvered C compiler that made you angry in the first place 😆
There's the I try to keep everything under |
Cheers! I'm actually a little unhappy with the pixel-drawing, it's doing too much work. And I was thinking about adding a rainbow background. I managed to cobble together a crude HSV-to-RGB function: // Convert RGBA values in the range [0, 255] to a u32 encoding
u32 rgba32(u8 r, u8 g, u8 b, u8 a)
{
return ((u32)0x00_00_00_00 | ((u32)((a) << 24) | ((u32)(r) << 16) | ((u32)(g) << 8) | (u32)(b)));
}
// This is a function from hue (360° scaled to [0..0x100) aka u8)
// to the secondary color component (also u8). It's a triangle
// wave with three peaks.
u8 secondary_color_component[256] = {
0x00, 0x05, 0x0b, 0x11, 0x17, 0x1d, 0x23, 0x29,
0x2f, 0x35, 0x3b, 0x41, 0x47, 0x4d, 0x53, 0x58,
0x5e, 0x64, 0x6a, 0x70, 0x76, 0x7c, 0x82, 0x88,
0x8e, 0x94, 0x9a, 0xa0, 0xa6, 0xab, 0xb1, 0xb7,
0xbd, 0xc3, 0xc9, 0xcf, 0xd5, 0xdb, 0xe1, 0xe7,
0xed, 0xf3, 0xf9, 0xff, 0xf9, 0xf3, 0xed, 0xe7,
0xe1, 0xdb, 0xd5, 0xcf, 0xc9, 0xc3, 0xbd, 0xb7,
0xb1, 0xab, 0xa6, 0xa0, 0x9a, 0x94, 0x8e, 0x88,
0x82, 0x7c, 0x76, 0x70, 0x6a, 0x64, 0x5e, 0x58,
0x53, 0x4d, 0x47, 0x41, 0x3b, 0x35, 0x2f, 0x29,
0x23, 0x1d, 0x17, 0x11, 0x0b, 0x05, 0x00, 0x05,
0x0b, 0x11, 0x17, 0x1d, 0x23, 0x29, 0x2f, 0x35,
0x3b, 0x41, 0x47, 0x4d, 0x53, 0x58, 0x5e, 0x64,
0x6a, 0x70, 0x76, 0x7c, 0x82, 0x88, 0x8e, 0x94,
0x9a, 0xa0, 0xa6, 0xab, 0xb1, 0xb7, 0xbd, 0xc3,
0xc9, 0xcf, 0xd5, 0xdb, 0xe1, 0xe7, 0xed, 0xf3,
0xff, 0xf9, 0xf3, 0xed, 0xe7, 0xe1, 0xdb, 0xd5,
0xcf, 0xc9, 0xc3, 0xbd, 0xb7, 0xb1, 0xab, 0xa6,
0xa0, 0x9a, 0x94, 0x8e, 0x88, 0x82, 0x7c, 0x76,
0x70, 0x6a, 0x64, 0x5e, 0x58, 0x53, 0x4d, 0x47,
0x41, 0x3b, 0x35, 0x2f, 0x29, 0x23, 0x1d, 0x17,
0x11, 0x0b, 0x05, 0x00, 0x05, 0x0b, 0x11, 0x17,
0x1d, 0x23, 0x29, 0x2f, 0x35, 0x3b, 0x41, 0x47,
0x4d, 0x53, 0x58, 0x5e, 0x64, 0x6a, 0x70, 0x76,
0x7c, 0x82, 0x88, 0x8e, 0x94, 0x9a, 0xa0, 0xa6,
0xab, 0xb1, 0xb7, 0xbd, 0xc3, 0xc9, 0xcf, 0xd5,
0xdb, 0xe1, 0xe7, 0xed, 0xf3, 0xf9, 0xff, 0xf9,
0xf3, 0xed, 0xe7, 0xe1, 0xdb, 0xd5, 0xcf, 0xc9,
0xc3, 0xbd, 0xb7, 0xb1, 0xab, 0xa6, 0xa0, 0x9a,
0x94, 0x8e, 0x88, 0x82, 0x7c, 0x76, 0x70, 0x6a,
0x64, 0x5e, 0x58, 0x53, 0x4d, 0x47, 0x41, 0x3b,
0x35, 0x2f, 0x29, 0x23, 0x1d, 0x17, 0x11, 0x0b,
};
u32 HSVA_to_RGBA(u8 hue, u8 saturation, u8 value, u8 alpha)
{
u8 chroma = (u16)saturation * (u16)value / (u16)0xff;
u8 X = (u16)chroma * (u16)secondary_color_component[hue] / (u16)0xff;
u8 m = value - chroma;
// value >= chroma
// these are fractions between 0 <= n < 1
// s * v <= v (also <= s but we don't care here.)
chroma = chroma + m;
X = X + m;
return (
( 0 <= hue && hue < 43) ? rgba32(chroma, X, m, alpha) :
( 43 <= hue && hue < 86) ? rgba32(X, chroma, m, alpha) :
( 86 <= hue && hue < 128) ? rgba32(m, chroma, X, alpha) :
(128 <= hue && hue < 171) ? rgba32(m, X, chroma, alpha) :
(171 <= hue && hue < 214) ? rgba32(X, m, chroma, alpha) :
/*(214 <= hue && hue < 256)*/ rgba32(chroma, m, X, alpha)
);
}(I tried making BTW, ...
Not at all! The error messages are a bit rough, but 9/10 times I get what they're trying to tell me. It's a pretty sturdy compiler, at least I haven't broken it so far. (Just to be extra clear, when I say "in anger" I don't mean I'm actually angry, quite the opposite. I mean that I intend to use this code in , like, products: simple computers that I hope to actually sell to people to use daily. :) )
I don't see why not? AFAICT the limiting factor is pushing pixels from the CPU to the video RAM. On my desktop workstation (which has no GPU!) I can't run e.g. the paint demo at a usable framerate if I change the screen to, say, 1200x800. It's just too slow. But on smaller windows it's fine. I'm sure the bottleneck in the bandwidth between CPU and screen.
I saw that! Very cool. I only used the other one because I read about it a couple of weeks ago when I first ported Joy to C and liked it. I should mention that the HSV code above should be considered to be released under CC0. I can move it to the |
Sure, please do open an issue with the smallest repro you can find. I do my best to fix all the bugs I can find and I keep adding more tests. Because I know compiler bugs can discourage some people. I want people to have a good experience when trying out UVM, as much as possible.
On my mac M1 it runs smoothly no matter the size of the window. Could be something weird with graphics drivers or with SDL? Normally it should be plenty fast enough though. The amount of data it requires to transfer a few megapixels of data is trivial compared to the amount of memory or PCIE bandwidth a modern computer has, which is on the order of tens of gigabytes per second.
For Speaking of examples, I added |
|
Just added a macro for rgba32: d169448 |
|
This weekend so far I fixed several bugs in the C compiler, and worked on making line numbers accurate in error message, as well as adding some tests for that. Also added support for variadic functions and implemented a simple Generally just doing my best to fix all the obvious compiler bugs so people have a positive experience when they play with UVM. Tomorrow will look at fixing a bug with relative includes. Also starting to think about what are the pieces we need to implement a simple audio output API. By default SDL spawns a new thread and calls a callback to generate new audio samples. To make that work with UVM's event model, I need to implement a VM lock/mutex. The good news is that I think it should work, and it should be fast enough to program simple music software, or sound effects for games. |
That sounds like a wise policy. :)
Awesome! I'll whomp up a pretty demo or something.
Ah, that's cool! Forth systems typically have simple editors like that that work on a "screen" of text at a time (IIRC 512-byte "blocks" that were read/written to disk verbatim.) I've been busy but I had time to mess around with circle-drawing. Here's Wu's algorithm in Python: from math import floor, ceil, hypot
MAX_INTENSITY = 0xFF
def D(r, j):
h = hypot(r, j)
return floor(MAX_INTENSITY * (ceil(h) - h) + 0.5)
def draw_Wu_circle(radius):
x = radius
y = threshold = 0
while x > y:
y += 1
intensity = D(radius, y)
if intensity > threshold:
x -= 1
draw_points(x, y, intensity)
#draw_points(x - 1, y, MAX_INTENSITY - intensity)
threshold = intensity
def draw_points(x, y, alpha):
a = round((MAX_INTENSITY - alpha) / MAX_INTENSITY, 2)
b = round(alpha / MAX_INTENSITY, 2)
print(x * '.', f'[{a}][{b}]')
#put_pixels(x, y, alpha)
#put_pixels(y, x, alpha)
##def put_pixels(x, y, value):
## put_pixel(x, y, value)
## put_pixel(x, -y, value)
## put_pixel(-x, y, value)
## put_pixel(-x, -y, value)
if __name__ == '__main__':
draw_Wu_circle(50)It calculates 1/8th of the circle and you draw the rest by symmetry, but this version just prints out the octant with the (normalized) intensity values. If you look at it with a square-ish font you can see that the pie-slice is pretty precise. I used a really huge 1/4 sine LUT (it takes noticeable time to compile, but not to load at runtime) to draw a circle in UVM, but it's real purpose is that rotating cube. I also made a non-sine-table-using circle-drawing demo too, using the "midpoint" algorithm. (The hyphen is my word of the day.) But this does not do anti-aliasing (yet.) |
That was my thinking. We can have some sort of retro-style interpreter for something like BASIC or Forth.
The midpoint algorithm looks conceptually simpler? Would be cool to have something that can draw a filled-circle with anti-aliasing. In the last few days I've been working on getting an audio output API working with UVM. It's a bit complicated because threads are involved... And Rust threads + SDL don't mix super well, but I'm close to having it working. Simple sound effects and music apps should be possible soon :) Once it's working, will probably have a |
The Joy interpreter in NCC C is coming along. Joy syntax is so simple that the parser is uninteresting, so I don't think it would make a good example of parsing in general. Writing a Forth directly in UVM asm would be a lot of fun. A BASIC interpreter would be hella cool. Or Scheme?
Yeah, that sine table is kind of a joke. For one thing, it's I'm going to use it (or a less-silly version of it) to do simple fixed point 3D math, and of course it would be handy for audio too, eh? In re: circle drawing, yeah the midpoint algorithm is sort of the Wu algorithm with the math converted to simple integer ops, I'm pretty sure the error|intensity value is there but I haven't fully grokked the math yet. My brains are old and mushy. (And it's been a really hectic month so far! Whew!) At some point I'll circle back (pun intended, you get to a certain age and Dad Jokes just happen, I'm sorry) and figure it out (another terrible pun, I'm so soory!)
Ah that's so cool! (I'm even less of an audio geek than a graphics geek, but I appreciate what the techno-musicians do.) |
|
If anybody has time, an easy potential contribution would be to implement missing functions in https://github.com/maximecb/uvm/blob/main/ncc/include/string.h |
|
Hey, I just wanted to touch base. I've been doing other things (and these new talking computers have thrown me for a loop) but I'm still here, so to speak. :) |
|
Hi Simon! I've added support for floats, structs, and am currently working on some 3D matrix math code :) |
|
Hi Maxime, I've been busy with IRL stuff (we just bought some land!) but I intend to circle back to UVM + NCC soon. |
|
Glad to hear you'll be back soon! I've also been busy. I'm in the process of buying a new place and selling my current place. I managed to get this 3D rotating wireframe cube example working last weekend :D |
|
Ah! Congratulations, and congratulations! :) |
|
Ahoy! I'm circling back around. (I got some land and have been in the process of sort-of moving!) How are things going? What did I miss? :) |
|
Hello friends! I moved this summer and it ended up being very stressful, so I took a break, but now I am back 😎 I've fixed a couple of bugs, added a Next I will be looking at fixing/improving the situation with automatic promotion of integers and floats and type casting, which is a bit suboptimal at the moment (requires casts that normally shouldn't be needed in C). If you're still interested in contributing, help is very much welcome :) |
This is a list of potentially fun things to work on that would be useful for UVM and its software ecosystem. An easy way that you can contribute to UVM is to write example programs, or useful utility code to be shared with the community, and report any bugs or difficulties you run into along the way.
Some ideas:
printfimplementation inncc/include/stdio.h/ncc/include/uvm/graphics.h)My intent is to share all examples code under the CC0 1.0 license (a public domain dedication) so that people can get inspired from it and do with it as they please.
And generally speaking, if you write any kind of simple game for UVM, the code is readable, and you're willing to add it to this repo as part of the examples, that could be a useful contribution to the ecosystem :)
Smaller pull requests are easier to review and more likely to get merged quickly.
The text was updated successfully, but these errors were encountered: