User avatar
DavidS
Posts: 4193
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

A little Progress on my little OS Project:

Thu May 23, 2019 3:00 am

I have managed to get far enough to do some of the development self hosted. The spec largely is modeled after what is already posted at github, though I can not seem to make any updates or uploads there, sorry about that issue. I will be updating the github wiki for this project as soon as I can, and I will be plopping the version 0.0,1-pre-Alpha code and binaries up as soon as I can get github to cooperate.

Current status:
  • Kernel support for modules is doing quite well. Memory management is usable (albeit far from complete).
  • Console output to framebuffer working well.
  • Task management is working better than expected at this point, still some issues with VFP contexts.
  • USB is working acceptably, far from complete though good enough for HID and some Mass Storage devices.
  • Very basic disk and FS support for USB Mass Storage, has some issues though is working, this covers three modules plus the DWCUSB module at the moment..
  • RAMFS module fully functional.
  • GFXCore is working with 80% of all intended functionality implemented.
  • FontMan module for font handling is working for most purposes. Does pretty well for most bitmapped font applications (missing a few transformations), vector font support is still very minimal.
  • WinMan the window manager is somewhat usable. It is about as good as M$-Windows 2.0 or a bit better than 8-Bit GEOS in its current level of usability.
  • Filer, the Windowing graphical file manager is starting to come together, it can show files (with simple icons so far), launch applications, and sometimes copy files.
  • TCPIP the TCP/IP module is untested though present, still waiting on USB support to get far enough along, as well as a Ethernet stack..
And there are a few test applications including the beginnings of a BASIC Compiler/Interpreter just for something to test with. There are also; a WIMP/GUI based Calculator, a simple WIMP/GUI based text editor, the bare beginnings of a Paint application, some toy programs, a simple machine language monitor, and a few other small things.

The system works about the same on both the RPi 1B and RPi 3B/3B+. I am targeting version 0.0.2 pre-Alpha as the first version with enough function for people to toy around with. Though I thought I would through out a status update.

Also of note is that I am beginning to play with the OpenGL support of the GPU on bare metal, separately from this OS at this time. I am hoping to learn enough about the implementation to implement a usable OpenGL graphics system in my little toy OS, that is again temporarily without a name, as I was confronted by the company that already held the name I chose (and has for some time), oops.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

User avatar
Gavinmc42
Posts: 3148
Joined: Wed Aug 28, 2013 3:31 am

Re: A little Progress on my little OS Project:

Thu May 23, 2019 5:06 am

I like the simpler OpenVG, mainly because I don't understand OpenGL yet ;)
Getting the GUI working convinced me I need the rest of an real OS.
No one has told me they own Punk OS yet ;)

Sounds like you are much further along than most of us.
I've been distracted by seeing if I can have AI/NN built in, basically extending my PDA OS into a Robot OS.
I'm dancing on Rainbows.
Raspberries are not Apples or Oranges

User avatar
DavidS
Posts: 4193
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: A little Progress on my little OS Project:

Thu May 23, 2019 12:45 pm

Gavinmc42 wrote:
Thu May 23, 2019 5:06 am
I like the simpler OpenVG, mainly because I don't understand OpenGL yet ;)
Getting the GUI working convinced me I need the rest of an real OS.
No one has told me they own Punk OS yet ;)

Sounds like you are much further along than most of us.
I've been distracted by seeing if I can have AI/NN built in, basically extending my PDA OS into a Robot OS.
I have never looked at OpenVG. I began playing with OpenGL on other systems back in the mid 1990's (a stripped down version of OpenGL 1.2 on an Atari TT).

Also I just spent all night redoing the user level API for my OS, I am just going to push forward with the ARMTOS project, as it will likely be the best received version of my work. This decision was do to the need for a name in part, and in part do to the extremely large library of modern software for the Atari TOS compatible platforms.

I am also reluctantly getting to know gnu as (gas), as this is an assembler many use on a regular basis, and it allows me to use gcc until I get an ARM targeting C compiler that is syntax compatible with Pure C (ANSI versions) and the updated AHCC remake. Atari ST systems and developers embraced C from the beginning so I should do a good bit of my work in C.

GEM was almost entirely written in C, the same for GEMDOS (the DOS API like OS that sits under GEM). I have debated the multitasking API to implement, there are three major ones on the Atari TOS compatible platform (MultiTOS [MiNT], MagiX/MagiC, and Geneva). I am thinking that the Geneva API is the most sensible of the bunch, perhaps add a bit of the MiNT compatible UNIX style calls just for flavor.

Though I have not yet redone the API for the TCP/IP stack. As this is a ARM based OS so no software has been ported to it yet I am thinking of something closser to STiK/STiNG for the TCP/IP stack API. I do not much care for MiNT-NET (not realy very good implementation of sockets based API for networking).

Still having trouble with Github.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

Heater
Posts: 12629
Joined: Tue Jul 17, 2012 3:02 pm

Re: A little Progress on my little OS Project:

Thu May 23, 2019 1:48 pm

Sounds awesome.

What's the link to your repository on github?

User avatar
DavidS
Posts: 4193
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: A little Progress on my little OS Project:

Thu May 23, 2019 1:58 pm

Heater wrote:
Thu May 23, 2019 1:48 pm
Sounds awesome.

What's the link to your repository on github?
The link is:

https://github.com/ARMDavid/ArmTOS

NOTE: As I have not been able to update that, the info is wrong. I am not using a CPU emulator at all (yet), everything is ARMv7 native and the OS is a new TOS API compatible OS (Big Endian on most user mode code). It has been a fun project so far.

I hope I can upload the code soon, I do not know what the problem is with github, used to he easy to get stuff up.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

User avatar
DavidS
Posts: 4193
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: A little Progress on my little OS Project:

Thu May 23, 2019 2:49 pm

Another Update:
I am able to edit the readme.md and wiki pages now on github. Still having trouble uploading will let it be known when I manage to get that bit going.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

User avatar
DavidS
Posts: 4193
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: A little Progress on my little OS Project:

Thu May 23, 2019 9:35 pm

Mysterious blessings:
Maybe it is just a random blessing that I am having trouble uploading to GitHub today. I just tryed the updated code on the ARMv8 based RPi 3B and it failed do to not recognizing the SETEND instruction. I am not sure why this would not work in AARCH32 on the ARMv8 used in the Raspberry Pi 3B/3B+ though it means that all the SMP support I worked on is of no use to the project as the ARMv7 RPi 2B no longer is available, so much for compatibility I know many applications and libs still in development that still use SETEND.

So I will be posting this particular project as RPi 1 only (even though it would work on the original RPi 2B)
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

jahboater
Posts: 4427
Joined: Wed Feb 04, 2015 6:38 pm

Re: A little Progress on my little OS Project:

Fri May 24, 2019 1:37 am

Can you allow SETEND by setting bit 8 in the SCTLR register to zero?

Code: Select all

SED SETEND Disable. Disables SETEND instructions at EL0 using AArch32.
0 SETEND instructions are enabled.
1 The SETEND instruction is disabled.

User avatar
Paeryn
Posts: 2561
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: A little Progress on my little OS Project:

Fri May 24, 2019 2:10 am

<jahboater beat me to this, I got sidetracked before replying>
DavidS wrote:
Thu May 23, 2019 9:35 pm
Mysterious blessings:
Maybe it is just a random blessing that I am having trouble uploading to GitHub today. I just tryed the updated code on the ARMv8 based RPi 3B and it failed do to not recognizing the SETEND instruction. I am not sure why this would not work in AARCH32 on the ARMv8 used in the Raspberry Pi 3B/3B+ though it means that all the SMP support I worked on is of no use to the project as the ARMv7 RPi 2B no longer is available, so much for compatibility I know many applications and libs still in development that still use SETEND.

So I will be posting this particular project as RPi 1 only (even though it would work on the original RPi 2B)
SETEND is working on my RPi 3B (under Raspbian) though Arm deprecated its use. Bit 8 (SED - SetEnd Disable) of SCTLR (p15, 0, <Rt>, c1, c0, 0) defines whether it is disabled (0 = Enabled, 1 = Disabled), the docs say it defaults to 0. It's also in HSCTLR for controlling its use in the hypervisor.
She who travels light — forgot something.

User avatar
Gavinmc42
Posts: 3148
Joined: Wed Aug 28, 2013 3:31 am

Re: A little Progress on my little OS Project:

Fri May 24, 2019 5:29 am

I had a look at RISC OS and the Atari and Amiga OS's and many other OS's.
For most of my stuff multiuser is not a requirement, so these are fine.
But the look is so dated and they don't really make use of the hardware the Pi's come with

The Pi's are really in need of their own OS that is not as clunky as Linux.
I never would have even thought about making my own OS until recently as I did not expect to have the skills needed.
It turns out lots of the pieces are already out there, they just need gluing together.
It will be clunky but good practice for when I repeat it for a RISC-V version.

After the RISC-V OS, design my own CPU?
Should be enough to keep me busy for the next 10 years ;)
I might have to learn assembler just to figure out what you guys are talking about :oops:
I'm dancing on Rainbows.
Raspberries are not Apples or Oranges

zeoneo
Posts: 52
Joined: Sun Sep 30, 2018 6:54 am

Re: A little Progress on my little OS Project:

Fri May 24, 2019 9:56 am

Hi David,
DavidS wrote: FontMan module for font handling is working for most purposes. Does pretty well for most bitmapped font applications (missing a few transformations), vector font support is still very minimal.
Does it load true type font ? Have you tried FreeType library to load fonts and render it using OpenGL ?

Could you please explain the importance of "RAMFS"? Why do we need to implement it. Is it the similar concept as INITRD? I have read it online but did not understand the purpose why RAMFS needed.

Thanks,
ZEONEO
Let there be some light .../\...

LdB
Posts: 1142
Joined: Wed Dec 07, 2016 2:29 pm

Re: A little Progress on my little OS Project:

Fri May 24, 2019 1:36 pm

I have code that can I can release to public domain that can process a TTF format directly on the VC4 GL pipeline. I can't release the code to read the TFF file itself (it is commercial) but I have code that can process C vector glyph outlines produced from GetGlyphOutline on Windows and written as C format. Here let me put one up to look at.

So this is the standard Arial.ttf font at 400 grid height written out as a C structures
https://github.com/LdB-ECM/Exchange/blo ... ts/Arial.c

This is the format of the each vertex point in the vector record in the file ... so it can contain Quad & Cubic beziers and lines

Code: Select all

/*--------------------------------------------------------------------------}
{				  VECFONT VERTEX2D RECORD DEFINITION						}
{--------------------------------------------------------------------------*/
#pragma pack(1)                                 // Need uint16_t packing for structure
typedef struct {
	union {
		struct {
			uint16_t _unused : 2;				// @0-1		Unused bits
			uint16_t close : 1;					// @2		close contour
			uint16_t liftclose : 1;				// @3		Open contour ... close vertex in air
			uint16_t bezongrid : 1;				// @4		Bezier on grid point (Both quad and cubic)
			uint16_t quadbezoffgrid : 1;		// @5		Quad bezier off grid point 
			uint16_t cubicbezoffgrid : 1;		// @6		Cubic bezier off grid point
			uint16_t joinedcontour : 1;			// @7		This contour joins to another contour
			uint16_t criticalcorner : 1;		// @8		Critical corner flag
			uint16_t _reserved : 7;				// @9-15	Reserved bits
		};
		uint16_t RawFlags16;					//	Raw access to all 16 bits of flags
	};
	int16_t x;                                  // Vertex x co-ord
	int16_t y;                                  // Vertex y co-ord
} VECFONT_VERTEX2D;
#pragma pack()	
Each Letter has a character description record (search for const VECFONT_CDR Arial_CDT [256]) that is size, position etc data for each character. Finally at the very bottom is a FONT record which points to the above sections and provides basic font details.

When you process a character you get the outline as per the original TTF .. lets do "Arial" as text
Yellow x are line points, green x are on grid bez and blue x are off grid bez
Image

This is the code used to process the image above
https://github.com/LdB-ECM/Exchange/blo ... ssFont.txt
This is the code to process the bezier curves
https://github.com/LdB-ECM/Exchange/blo ... Bezier.txt

To run it into the VC4 pipeline you just need to scale it and do triangulation on the closed contour
https://developer.nvidia.com/gpugems/GP ... _ch25.html
CODE >>>>> Example 25-1. Quadratic Curve Pixel Shader

If you got thru all that actually reading the TTF file will then make sense anyhow when you come to writing it well my structures should help you work out how to hold it in memory :-)

If you need me to throw up a running tutorial example let me know.
I can release the Windows code that creates the C vector files as well if required.

zeoneo
Posts: 52
Joined: Sun Sep 30, 2018 6:54 am

Re: A little Progress on my little OS Project:

Sat May 25, 2019 7:37 am

@Ldb it is interesting. I will go through it and see if I can make it work. I need to do lot of reading on TTF formats, how to create font texture from ttf and finally how to render it using VC4. I was searching for FreeType bare metal port but I guess I need to have basic user land support to cross compile it.

Thanks for the pointers in that direction. I might try your code after enough understanding of necessary concepts.
Let there be some light .../\...

User avatar
Gavinmc42
Posts: 3148
Joined: Wed Aug 28, 2013 3:31 am

Re: A little Progress on my little OS Project:

Sat May 25, 2019 10:23 am

Also look at AJ Starks Code for OpenVG, his code supports 3 fonts.
https://github.com/ajstarks/openvg

I have used the Ultibo Pascal port and the Go version but not the original C++.
I think it is using freetype not truetype according to the fontutil code?

Not sure how to go from OpenVG to OpenGLES re fonts.
I'm dancing on Rainbows.
Raspberries are not Apples or Oranges

User avatar
Paeryn
Posts: 2561
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: A little Progress on my little OS Project:

Sat May 25, 2019 12:22 pm

Gavinmc42 wrote:
Sat May 25, 2019 10:23 am
Also look at AJ Starks Code for OpenVG, his code supports 3 fonts.
https://github.com/ajstarks/openvg

I have used the Ultibo Pascal port and the Go version but not the original C++.
I think it is using freetype not truetype according to the fontutil code?

Not sure how to go from OpenVG to OpenGLES re fonts.
Yes, ajstarks' library uses freetype to parse the ttf files, for OpenVG it is simple as it gives you a list of moves, lines and curves which are all directly supported by OpenVG paths. For OpenGL you need to convert the list into triangles that cover the inside of the paths.
I'm sure freetype can render bitmaps of each glyph for you if you prefer (unless I'm remembering another lib).
She who travels light — forgot something.

LdB
Posts: 1142
Joined: Wed Dec 07, 2016 2:29 pm

Re: A little Progress on my little OS Project:

Sat May 25, 2019 2:28 pm

Personally from a baremetal persepective there is a lot of overhead in getting opengl up just to render a few character glyphs simply not worth the effort.

User avatar
Gavinmc42
Posts: 3148
Joined: Wed Aug 28, 2013 3:31 am

Re: A little Progress on my little OS Project:

Sun May 26, 2019 5:29 am

For OpenGL you need to convert the list into triangles that cover the inside of the paths.
Makes you wonder why people want to use OpenGL for Desktops GUIs when OpenVG is easier.
I am quite happy to stay with 2D until I reach it's limits for the simple stuff I do.

I do want to get to 3D visualization of data one day
Should be able to do that in a dispmanx window?
Once I get that going, I expect I will say "Hey this will make a cool 3Ddesktop". :lol:
But much to learn before then. ;)
I'm dancing on Rainbows.
Raspberries are not Apples or Oranges

bzt
Posts: 373
Joined: Sat Oct 14, 2017 9:57 pm

Re: A little Progress on my little OS Project:

Thu Jun 13, 2019 4:42 pm

Hi,

@DavidS: sounds really interesting what you have accomplished! Would it be possible to take look at your source? Your github repo only contains a README.md, that's all.
Gavinmc42 wrote:
Sun May 26, 2019 5:29 am
Makes you wonder why people want to use OpenGL for Desktops GUIs when OpenVG is easier.
For portability, I guess. At least I can't see any other reason.

@LdB: nice job! Although if I may add a suggestion, your Bezier curve calculation is not the best, it does a lot of unnecessary multiplications and it only supports quadratic curves.

There's another approach by recursively calculating the mid-points. I've used that algorithm in my font renderer, and it supports both quadratic and cubic Bezier curves (the latter important if you want to use the recent standard OpenType fonts too, not just the outdated TrueType ones).

Code: Select all

void reentrantBezierTo(int x0,int y0, int x1,int y1, int x2,int y2, int x3,int y3, int l)
{
    int m0x, m0y, m1x, m1y, m2x, m2y, m3x, m3y, m4x, m4y,m5x, m5y;
    // check if we have reached the limit or if we can't split coordinates any further
    if(l<256 && (x0!=x3 || y0!=y3)) {
        // calculate mid-way coordinates
        m0x = ((x1-x0)/2) + x0;     m0y = ((y1-y0)/2) + y0;
        m1x = ((x2-x1)/2) + x1;     m1y = ((y2-y1)/2) + y1;
        m2x = ((x3-x2)/2) + x2;     m2y = ((y3-y2)/2) + y2;
        m3x = ((m1x-m0x)/2) + m0x;  m3y = ((m1y-m0y)/2) + m0y;
        m4x = ((m2x-m1x)/2) + m1x;  m4y = ((m2y-m1y)/2) + m1y;
        m5x = ((m4x-m3x)/2) + m3x;  m5y = ((m4y-m3y)/2) + m3y;
        // split the curve into half and repeat
        reentrantBezierTo(x0,y0, m0x,m0y, m3x,m3y, m5x,m5y, l+1);
        reentrantBezierTo(m5x,m5y, m4x,m4y, m2x,m2y, x3,y3, l+1);
    }
    lineTo(x0,y0, x3,y3);
}
As you can see, this is totally multiplication free. The algorithm stops after N recursions or when the resolution cannot handle the subpixel divisions any more (usually hit much sooner than recursion limit, it does only 2 or 3 recursions tops, so it's very fast). To speed it up even further, you can replace division by 2 with a shift operation, and you can convert the recursion into an iteration (I didn't felt the necessity of that, in such a low number of recursions the difference is negligable).

Now using this code with cubic Bezier curves is trivial, as it requires 4 points: start point, two control points, and an end point.

Code: Select all

void cubicBezierTo(int x0,int y0, int x1,int y1, int x2,int y2, int x3,int y3) {
    reentrantBezierTo(x0,y0, x1,y1, x2,y2, x3,y3, 0);
}
For quadratic Bezier curves you can calculate the two control points from the three points quite easily, using exactly the same mid-way equation used above in the reentrant function:

Code: Select all

void quadBezierTo(int x0,int y0, int x1,int y1, int x2,int y2) {
    reentrantBezierTo(x0,y0, x0+(x1-x0)/2, y0+(y1-y0)/2, x1+(x2-x1)/2, y1+(y2-y1)/2, x2,y2, 0);
}
For higher precision you can replace "int" with "float", or you can upscale the coordinates.
Hope this is useful!

Cheers,
bzt

LdB
Posts: 1142
Joined: Wed Dec 07, 2016 2:29 pm

Re: A little Progress on my little OS Project:

Thu Jun 13, 2019 5:07 pm

Cheers I like that a lot let me do some testing.

If you are into you maths I have another one for you to have a crack at :-)

As you know what you really want to do is fill the outline glyph not draw it. The fastest way to do that is to run a scanline on the y integer values from the top of the scaled glyph to the bottom y value.
https://www.geeksforgeeks.org/scan-line ... -opengl-c/

The reason I didn't add cubic beziers is I have always been unable to write the scanline code for a cubic because technically you can get up to 4 points. This is the quadratic bezier scanline code can you see any way to simplify and ideally remove the doubles?

VERTEX_TYPE is usually an int16_t or int32_t depending on CPU

Code: Select all

/*-ScanlineQuadBezier2D-----------------------------------------------------
 Scanline (sy) intersect and the quad bezier between the 3 control points.
 The return will be 0 for no intersect, 1 and px1 will contain x intersect 
 value or 2 and px1 and px2 will contain the x interect values.
 ---------------------------------------------------------------------------*/
short ScanlineQuadBezier2D(VERTEX_TYPE x1, VERTEX_TYPE y1,	// Vertex 1 (x1,y1) = On grid start pt
			VERTEX_TYPE x2, VERTEX_TYPE y2,			// Vertex 2 (x2,y2) = Control Pt
			VERTEX_TYPE x3, VERTEX_TYPE y3,			// Vertex 3 (x1,y1) = On grid End point
               	   VERTEX_TYPE sy, 							// Scan line y value
                     	VERTEX_TYPE* px1, VERTEX_TYPE* px2){		// Interection pt(s)
    short rslt;
    VERTEX_TYPE dx0, dy0, dx1, dy1, dx2, dy2, xf;
    VERTEX_TYPE* px;
    double tmf, tdf, tf, ymf;

    dx0 = x2 - x1;											// X diff between x2 and x1
    dy0 = y2 - y1;											// Y diff between y2 and y1
    dx1 = x3 - x2;											// X diff between x3 and x2
    dy1 = y3 - y2;											// Y diff between y3 and y2
    if ((dx0 == 0) && (dy0 == 0) && (dx1 == 0) && (dy1 == 0))	// All 3 points are one and same
	return (0);											// Drop point even if coincides with sy	
    if ((dx0 == 0) && (dy0 == 0))							       // First 2 points are one and same
	return (ScanlineLine2D(x2, y2, x3, y3, sy, px1));			// Scanline as a line from (x2,y2)<->(x3,y3)
    if((dx1 == 0) && (dy1 == 0))								// Last two points are one and same	
	return (ScanlineLine2D(x1, y1, x2, y2, sy, px1));			// Scanline as a line from (x1,y1)<->(x2,y2)
   dx2 = (dx1-dx0);										// Differnece between dx1 and dx0
   dy2 = (dy1-dy0);										// Differnece between dy1 and dy0
    if (dy2 != 0){											// y(t) = a*t*t + b*t + c
	// Calculate apex
	tmf = -(double)dy0/(double)dy2;						// 't' at apex point
	ymf = (double)y1 + DBL_EPSILON + tmf*(double)dy0;		// y at apex point
	tdf = ((double)sy - ymf)/(double)dy2;					// ''t' value at scanline
	if (tdf < 0.0) {										// If t value is invalid
		return (0);										// No intersect
	} else if (tdf > DBL_EPSILON) tdf = sqrt(tdf);				// Take sqrt of t value
	rslt = 0;												// Preset intersect return count to zero
	px = px1;											// Preset intersect x ptr to px1
	tf = tmf - tdf;											// Calculate first test t value
	if ((tf >= 0.0) && (tf <= 1.0)){							// Valid 't'  0.0 <= t <= 1.0
		xf = (VERTEX_TYPE)(((double)dx2*tf + (double)(dx0*2))*tf) + x1;// Calculate x point of intersec
		(*px) = xf;										// Transfer that result to *px
		rslt++;											// Increment intersect count
       	px = px2;										// Advance point to px2
	}
	tf = tmf + tdf;										// Calculate second test t value
	if ((tf >= 0.0) && (tf <= 1.0)){							// Valid 't'  0.0 <= t <= 1.0
		xf = (VERTEX_TYPE)(((double)dx2*tf + (double)(dx0*2))*tf) + x1;// Calculate x point of intersect
		(*px) = xf;										// Transfer that result to *px
		rslt++;											// Increment intersect count
		px = px2;										// Advance ptr to px2
	}		
	return (rslt);										// We can have one or two points returned
    } else if (dy0 != 0) {										// y(t) = b*t + c
	tf = ((double)(sy - y1) - DBL_EPSILON)/(double)(dy0*2);	// Calculate t of intersect
	if  ((tf >= 0.0) && (tf <= 1.0)){							// Valid 't'  0.0 <= t <= 1.0
		xf = (VERTEX_TYPE)(((double)dx2*tf + (double)(dx0*2))*tf) + x1;// Calculate x point of intersect		
		(*px1) = xf;										// Transfer that result to px1
		return (1);										// Return 1 as intersect count
	} else return (0);										// Intersect is outside line segment
   } else return (0);										// Drop horizontal line even if coincides with sy
}

bzt
Posts: 373
Joined: Sat Oct 14, 2017 9:57 pm

Re: A little Progress on my little OS Project:

Fri Jun 14, 2019 1:09 pm

LdB wrote:
Thu Jun 13, 2019 5:07 pm
Cheers I like that a lot let me do some testing.

If you are into you maths I have another one for you to have a crack at :-)
Yeah, at the university I've learned to be a software oriented mathematician, so we can say that :-)
LdB wrote:
Thu Jun 13, 2019 5:07 pm
As you know what you really want to do is fill the outline glyph not draw it. The fastest way to do that is to run a scanline on the y integer values from the top of the scaled glyph to the bottom y value.
https://www.geeksforgeeks.org/scan-line ... -opengl-c/

The reason I didn't add cubic beziers is I have always been unable to write the scanline code for a cubic because technically you can get up to 4 points. This is the quadratic bezier scanline code can you see any way to simplify and ideally remove the doubles?
In theory you can write a rasterizer that would calculate each point for cubic and quadratic Bezier curves as well as for lines to decide if a given point is inside or not. Good explanation here.

But that's a bit complex and yes, it needs high precision with doubles. So instead I convert the outline into a polygon which is surrounded by lines only, then I use a plain simple polygon fill. Polygon fill, odd-even rule and non-zero winding rule. I do this by simply replacing lineTo() in the above algorithm to a function which collects the lines (see _ssfn_l() in my code). Then the rasterizer (see _ssfn_r()) converts that list of lines into an ordered list of X coordinates for each Y scanlines (and scales them in the meantime, more on this later).

From here, there's two path you can follow, because a glyph can be made up out of more polygons. The simplest but slower way is to rasterize every polygon using XOR. For example, the glyph of letter 'A' consist of two polygons, the big outline and a small triangle inside (which looks like a square in this low res example):

Code: Select all

........   ........   ........
........   ...XX...   ...XX...
........   ..XXXX..   ..XXXX..
........   ..XXXX..   ..X..X..
........   .XXXXXX.   .XX..XX.
........   .XXXXXX.   .XXXXXX.
........   .XX..XX.   .XX..XX.
........   ........   ........
At first the canvas is empty, so when you rasterize the first polygon of 'A', XOR will make it appear (because 0 ^ 1 = 1). Then you rasterize the second polygon (the small triangle inside which looks like a square), it will clear the canvas at the polygon's intersections (because 1 ^ 1 = 0). Note that XOR does not care about the ordering of the polygons, it could been the triangle rasterized first, same result. (And it doesn't care if the outlines are listed in clockwise or counter-clockwise order, because you can't rely on that. Font makers are lazy, and they don't care about recommendations. As a matter of fact, FontForge has an option to set all polygon outlines in the same clockwise order.)

The other way, which I've used relies on odd-even rule. I merge the outlines of the polygons into the same set of X per Y scanlines, and I only rasterize the final set. This considerably speeds up things. For example, in the 'A' example above, at line 3 and 4, this algorithm will draw two horizontal lines without the need of XORing. This only works if the polygons have no overlapping outlines, which stands for TTF glyphs. In theory OTF format allows overlaping, but requires a special flag to be set if this happens:
Microsoft wrote:A non-zero-fill algorithm is needed to avoid dropouts when contours overlap. The OVERLAP_SIMPLE flag is used by some rasterizer implementations to ensure that a non-zero-fill algorithm is used rather than an even-odd-fill algorithm.
if a glyph has overlapping contours in the given instance, then the tool should either set this flag in the derived glyph data, or else should merge contours to remove overlap of separate contours.
In practice I haven't seen that flag set, either because the letters that I mostly use (Latin, Cyrillic, Greek) do not have overlapping outlines in the first place, or because the tool generated the font already merged the outlines into non-overlapping ones.

With OpenGL, I'd suggest to forget about scanlines, rather focus on merged polygons defined by lines only, and triangulate that. Let the GPU do the hard work for you :-)

Hope this helps,
bzt

LdB
Posts: 1142
Joined: Wed Dec 07, 2016 2:29 pm

Re: A little Progress on my little OS Project:

Fri Jun 14, 2019 3:21 pm

Been thru all that and things like paint floodfills the scanline method is 100 times faster than any of the options as actually measured on the PI because the VC4 is so dam good at it. Basically it's quicker at doing the manual solve of the equations than actually testing each point and along with the winding method. That winding method is also inconsistent and buggy because of the issues I am sure you already know like convex shapes, inclusion points and spin errors and you get no help form the VC4 you have to do all that on the ARM.

From the Khronos forum It seems to be fairly universal that on most OpenGL hardware setting up scanline method is the fastest but I am no expert and just following the conversations. I couldn't work out why it was so fast until you see how the VC4 pipeline works with it visually

Image

Anyhow as is it is so much faster than the alternatives I will live with the doubles :-)

bzt
Posts: 373
Joined: Sat Oct 14, 2017 9:57 pm

Re: A little Progress on my little OS Project:

Fri Jun 14, 2019 5:38 pm

Hi,

I think there's nothing wrong with doubles, the GPU is using float point numbers after all. I see no point in struggling with integers if you want to render the glyph on the GPU at the end. My font library uses a CPU only rasterizer, therefore it made sense for me to use integer arithmetic only.

Not sure about that scanline thing, I'm no expert on OpenGL either, but I know that triangulating (even with hardware acceleration) can be a very time consuming task, so it is possible scanline approach beats that in performance.

On the other hand I don't agree with your animation. It is not a scanline algorithm, and it uses an arbitrary point as zerus to draw the triangles. This won't work for all the glyphs. You were lucky that it worked for that 'e', because it had even number of outlines from that zerus point's perspective. It most certainly won't work with glyphs like 'M', at '@' or when there are more disjunct polygons, like in double quotes '"'. You must use triangles that do not reach out the boundary of the current polygon to avoid artifacts, or you should find an appropriate zerus point which could be a more complex problem than the whole rasterization (there's no problem with 'M' or '"' if you use the same animated algorithm choosing the zerus at the middle bottom, but that could not work other glyphs).

EDIT: if you take a really close look, you can see those artifacts I was talking about on the 'e' too. They are small black and white pixels in wrong positions (blacks on the left, right to the zerus point, and white ones on the left side of 'e', to the right of the outter contour and to the left of the half-circle). Depending on the glyph, those could be bigger areas.

Cheers,
bzt
Attachments
aaa.gif
aaa.gif (2.23 KiB) Viewed 926 times

LdB
Posts: 1142
Joined: Wed Dec 07, 2016 2:29 pm

Re: A little Progress on my little OS Project:

Sat Jun 15, 2019 3:14 am

The animation is slightly fudged ... if you actually did the real algorithm visually it would not work for us humans :-)
It might still have those small glitches, I cant say you can see any on screen.

It's not traditional scan lining in doing each y line in turn but the real thing does an exact normal scanline calculation it is just used differently.
On the real deal you pivot the glyph using a view matrix so the triangle line is flat along the x axis and solve for the normal scanline, so in that respect it is a stock standard scanline except y is always zero (which doesn't simplify the maths). The alternative would be to solve that 2D projected line to the bezier curve a much more intensive process from my understanding and sort of what the animation represents.

So on the animation where you see an angle lined to a point, you would instead see the line always horizontal, and the character translated and rotated to a new position. For us as humans it just doesn't work it looks like a lot of effort to continually move the character but obviously in maths it is just a simple matrix operation on the glyph control points which the VC4 pumps thru on it's vertex shader.

I am not the OpenGL expert there may be better ways to do this but this technique is killing everything else on the VC4 that I have tried.

PS: I am struggling thru the cubic curve solution for a given y scanline. Done as the parametric euler solution it is just two sets of eulers rather than the single for quadratic so at this stage not looking to bad. I note worse case you can get 3 points not 4 as I originally thought.

bzt
Posts: 373
Joined: Sat Oct 14, 2017 9:57 pm

Re: A little Progress on my little OS Project:

Sat Jun 15, 2019 1:05 pm

Hi,

I'm afraid we have hijacked the topic, sorry DavidS. I'm still very curious about your source code if you don't mind.

@LdB: Okay, if you say so, I believe you. You have more experience with VC and OpenGL than I have.

As for the curves, do not calculate them. Convert them into series of lines with that recursive function :-) Replace all ints with doubles in the code (except for "l"), that's it. That's much much faster than any computation or classic mathematical solving approach, and I'm sure you already have a way to rasterize simple (defined by lines only) polygons with the GPU. It will require a little bit more memory, true, but optimization is always a choice between code size, speed and memory consumption, isn't it? I think this one worth that extra memory.

Cheers,
bzt

Return to “Bare metal, Assembly language”