(50G) [HPGCC3] DRAW3DMATRIX replacement with grayscale surfaces, proof of concept

[3298]

It's time to release something I've been working on for ... longer than I'd want to admit.
It is a 3D renderer written using HPGCC3 with grayscale graphics and proper polygon sorting, originally intended to be used for a 50G version of a Casio AFX series game I enjoyed (a flight simulator with wireframe graphics called F-16 Falcon 2.0). At some point, my renderer was wireframe too, but when I started to use grayscale graphics, I noticed that without proper depth sorting some pixels could have the wrong color. To be precise, it happened when the 2D projections of two lines intersected; the point of intersection would get the color of the line that was defined earlier than the other one, which wasn't always the line that was closer to the viewer.
When reading up on ways to sort the lines, I decided to allow polygons as well. Modern graphics cards like to cut everything into triangles, but with CPU rendering I expected the renderer to be more efficient if I allow more corners per polygon - the renderer simply assumes all corners beyond the third one are in the plane defined by the first three. (If that's not the case, graphical glitches may happen.) This didn't solve the sorting problem yet, but the BSP (binary space partitioning) implementation I subsequently wrote did. I went with BSP because the only alternative I seriously considered was the Z-buffer, which has its own shortcomings, for example problems with transparent surfaces and a large memory footprint. (With 131x80 64-bit depth values, we have a Z-buffer weighing about 82KiB. That's a lot for our poor 50G.)
At some point my "render a single frame" and "render an endlessly rotating cube" test programs didn't cut it anymore, so I wrote something that allowed for multiple tests without constantly recompiling: a program that interprets a matrix as a heightmap and renders it, just like the built-in command DRAW3DMATRIX. What I'm releasing here is essentially this test program, but when the 50G has a command that does pretty much the same thing, it might actually be useful.
The performance was worse than I expected, so I tweaked some things: I replaced almost all floating point calculations with fixed point procedures. That helped a little bit, but not as much as increasing the clock speed from HPGCC3's default 12MHz to the OS's default 75MHz. Still, when feeding the output of {6. 6.} RANM 10. / \->NUM into the program, it takes between 300 and 400 milliseconds per frame. DRAW3DMATRIX performs better, and it can handle larger matrices than that just fine, but my renderer's performance drops off quickly due to the BSP calculations.

The renderer requires a matrix of real numbers on the stack (TYPE must report 3). Other types are not accepted; they only result in an Invalid Argument Type error. If you want to test it with RANM (which generates a symbolic matrix containing integers), use \->NUM to convert it. You might also want to scale it down yourself because unlike DRAW3DMATRIX my renderer does not take scaling parameters. Note: only scaling by a real number is not enough, because even though every number (except 0 apparently) will become a real one, the wrapping type will stay a symbolic matrix. The difference between a symbolic matrix and a numeric one is not visible directly, but TYPE reports 29 for the former and 3 for the latter.
When starting the renderer, you'll see a few letters followed by numbers at the bottom of the screen. They show how many polygons got past the backface culling step (i), how many were actually drawn (o), how many were added by cutting a polygon into two pieces (c) (cutting polygons is a part of how BSP works), and finally the time spent rendering the frame, in milliseconds (t). A 2x2 matrix is usually at 3 or 4 ms, a 4x4 one takes slightly less than 50 ms, and a 6x6 matrix takes between 300 and 400 ms, as I explained above.
As a demonstration of the renderer's capabilities, the surfaces are rendered with 75% alpha, that is, everything behind them is faintly shining through. The surfaces are dark or bright, depending on which side of them you see; the darker one is the underside. Removing this in favor of solid colors only has minimal impact on performance.
The keyboard controls are also different from DRAW3DMATRIX. Instead of rotating around the object's axes, the cursor keys rotate around the global X and Y axes. Rotation around the Z axis is done with leftshift and rightshift, the number keys 2, 4, 6 and 8 can be used for panning (which DRAW3DMATRIX cannot do at all). + and - move the object along the Z axis; this can be used as a substitute for zooming. 5 will reset the object to its original position and orientation, ON will get you out of the renderer.

Known glitches:
- Sometimes a few pixels of the black outlines are drawn below the surfaces instead of above them. I put in some hacks to keep them on top, but apparently they are not working quite right.
- The surfaces tend to flicker slightly, especially with larger matrices as the input. This shouldn't happen because I'm rendering to a hidden buffer which is then copied to the visible one with a single memcpy, but it's still there.
- When a surface covers large amounts of screen space, some slightly darker vertical lines appear with a horizontal distance of 4 pixels. I do not know what causes this.
- Rotating and moving the object can be slow or fast, depending on how fast the object is rendered. It's like that because the object is rotated/moved by a constant angle/distance every frame while the corresponding key is held down.
- On x49gp, only the leftshift, rightshift and ON controls are registered for some unknown reason. The remaining controls are apparently ignored, at least for me. The real calculator does not show this behavior.

A big THANK YOU to Claudio L. for HPGCC3 and some personal support when I had trouble. He showed me how to debug it with objdump, x49gp and gdb, and together we sorted out some issues which were mostly caused by me using a current version of arm-none-eabi-gcc instead of the one suggested on the HPGCC3 website (which is ridiculously hard to obtain, by the way; the current one was simply installed from my system's package manager). Only one issue was a real HPGCC3 bug, which I was able to work around (the romlib has some variables outside the .romglobals section, which makes them overlap with user variables; workaround: define an otherwise unused array covering the area these variables are put into).

I haven't decided on a license yet, so I'll hold on to the source for the moment. If I go for an open source one, it'll also need some cleanup and documentation.

As I mentioned, this program was designed as a test for the renderer code, so it should be considered a proof of concept. In that sense, my conclusion is that it works reasonably well, but it could use some performance improvement in the polygon sorting/cutting area. I do have some ideas, but they include major rewrites, so that will take a while.
Any questions, suggestions, bug reports?

[Han]

Have you tried looking at:

http://www.hpcalc.org/details.php?id=7128

The source is available for you to look at; it gets pretty good framerates (uses HPGCC2 though, I think).

[3298]

No, I haven't until just now. Interesting program, runs quite fast. But looking at its source, it simply sorts polygons by average Z value, which will glitch out with any situation where polygon A obscures polygon B, B obscures C, etc., and finally some polygon obscures A again (i.e. a cycle in the drawing order dependencies). This is especially important with just 2 polygons in this cycle; you get this situation when the polygons intersect. Binary space partitioning gets rid of that problem by separating at least one polygon in the cycle into two (or more) parts, such that there cannot be such a cycle anymore.
With PLOTXYZ's input scheme it should be possible to create self-intersecting shapes, which would show the problem. Ironically my input options don't allow for self-intersecting shapes, but I wrote my program in two parts, so I could simply keep the rendering engine and replace the rest with a parametric plotter like PLOTXYZ.

In other news, I have done significant improvements. In the first version I was concerned about memory and had the program recalculate the BSP tree during each frame. This allowed me to draw parts of the tree before it was fully built, so I could free the drawn polygons and keep the memory usage down. That was a major CPU hog (for obvious reasons), so the second version builds the tree once on startup and keeps it in memory.
Together with quite a few other improvements (some of which affect the structure of the BSP tree to keep the polygon count down) it renders a 10x10 random matrix in about 100 milliseconds. Unfortunately my tests with 16x16 matrices or larger failed with an "Out of memory" message. 15x15 matrices take about 330 milliseconds. Building the tree on startup takes several seconds, though, so be patient. When exiting, all the data structures are released again (I could skip this because they will be released on exit anyway, but while debugging with valgrind the messages about lost memory blocks got in my way), so that will take a moment as well.
Other changes:
- The cursor keys and RS/LS now rotate around the object's axes instead of the global axes. This is a byproduct of the changes, and it didn't bother me enough to change it back.
- Rotation and movement now scale to the amount of time spent rendering a frame, resulting in more predictable behavior.
- The information on the bottom of the screen now shows the polygon count in the BSP tree (p=...) and the frame time in milliseconds (t=...).

There are more changes behind the scenes, mostly in preparation for other uses; for example, the BSP merging functions are still under construction. They are commented out for this version because they are simply not needed - there is only a single object, nothing to merge with.
If you are paying attention to the number of polygons, you night notice that it has been reduced quite a bit. There are two reasons for that: The first one is a change to the way the black outlines are drawn. They were just ordinary polygons with two corners before, but now they are drawn as special effect after filling one of the gray surfaces. This required keeping track of which edges were produced by cutting polygons so you don't get black lines all over the place. The other change was to add invisible polygons in certain places. This sounds counterproductive, but by 'containing' each square with these invisible polygons, I can keep the BSP construction algorithm from clipping planes from different squares against each other, which was previously happening a lot, and each time this happened, the polygon count increased.
There is still a lot to be done: The BSP merging algorithm works, but it takes a while to finish - while reading up on it, I came across an approach using a linear programming feasibility test to detect useless branches; this needs to be implemented. I also want portal rendering, which basically just needs support for 2D clipping against non-rectangular regions; the rest of it can already be done through the same mechanism as the outlines.

[franz.b]

Hi,
I'm not able to use it... I don't know what the extension ".ex3" is.
is it a library to install? is il a compressed file that I do not know?
thanks

[3298]

Oof, someone dug this old topic up. Didn't expect that, but I'm glad to see that someone is interested.

ex3 is the standard extension for HPGCC3's binaries. They are not compressed or anything, so you just put them on your calculator like any other program, but you need to have an HPGCC3-modified ROM on the calculator to run it.
Unfortunately the modified ROM cannot be distributed because it's obviously derived from the (copyrighted) standard ROM, so you'll have to build it yourself...

The installation instructions on the HPGCC3 website are moderately up-to-date - the rant in the first post of this topic doesn't apply anymore, but I have some fixes you'll probably need. If you don't mind installing Linux for this (doesn't have to be directly on your hardware, a virtual machine is fine), and if you aren't afraid of typing a few commands in a Linux terminal, then I'll happily walk you through the process.

[franz.b]

Thanks for the reply! but I thought it was something simpler to use, I did not understand it was a program for an alternative rom. for the moment I do not want to modify my calculator, but in the future I am thinking of trying HPGCC3 on an emulator (EMU48) if this was possible. here we are offtopic so I think I will look for a thread on HPGCC3 or I will open one to ask for help from you.

[pier4r]

(12-12-2017 06:05 PM)3298 Wrote:  Oof, someone dug this old topic up. Didn't expect that, but I'm glad to see that someone is interested.

You did quite a work (documenting it plus the technical work). Thanks!

[3298]

It's pretty safe to put it on the calculator, I've had it on mine for what, five years now? (Can't believe how much time has passed already - the earliest timestamps I can find in my various HPGCC3-related files are from July 2012. That's about one year after I got the 50G itself, and a bit more than a year before pier4r's benchmark project...) Anyway, HPGCC3 doesn't interfere with the normal operation at all, and if something goes wrong while flashing or you somehow want to get rid of it, you can simply retry or flash the original ROM again. Literally the only downside is that it reduces the size of port 2 by 256 KiB (or was it just 128? I don't remember). I installed it and never looked back - I only flashed the calculator once more after that (again HPGCC3, this time built with a newer compiler; I hoped to squeeze a tiny bit of additional performance out of the libraries via the enhancements applied to the compiler's code optimization strategies).

As a bonus, building HPGCC3 sets you up with a development environment for HPGCC3, so you can start writing your own stuff in C or C++ right away (other languages might need some effort to interface with the HPGCC3 libraries, but it should be possible as long as the language can be compiled for ARMv4T).

Emu48 won't run HPGCC3 because HPGCC3 runs directly on the ARM hardware (that's its entire point) whereas Emu48 only emulates the Saturn layer. There's x49gp which does run HPGCC3 (I'm using that as my debugging platform), but it is a "build it for yourself on Linux" deal as well. Not a problem for me at all because I run Linux anyway, and I sometimes tinker with the software (i.e. building something myself happens all the time - for example, in the last 2-3 weeks I messed with the touchpad driver part of libinput, adding some features I wanted), but for Windows users who are not familiar with Linux or compilers that might be a bit uncomfortable. (Though to be fair, compilers shouldn't pose a problem to most of the members around here, considering the topic of this community.)

[Murray]

Hi,
I'd be really interested for some hints as to how to get HPGCC3 to work. I've built the HPGCCROM.bin on three different versions of Ubuntu ( and 4 different versions of GCC) - I can get it to build and the helloworld example, and the other examples to compile. While they run somewhat, they display distorted text on the screen and hang X49GP... But DRAW3D works, as far as I can see and exits cleanly, so there is something I'm missing. I would be grateful for any hints, or a walk-thru.

[Murray]

Hi,

I've looked a bit harder and I find the sat3_example1.ex3 runs successfully provided I enable ARMCODE_CONFIG_STACK_SLOW so that screen output is disabled - so it looks like my problem is somewhere with printing to the screen...

[3298]

You posted while I was typing this essay ... looks like the "band-aid solution" below is what will fix your problem. However, installing the other patch is probably a good idea too, at least if you plan to use 64-bit values in your programs. The rest is probably less relevant for you, but I wanted to keep this explanation as generic as possible.

Most of what I write is supposed to be changes to the procedure Claudio has described in his HPGCC3 installation tutorial. Note that even though he recommends Ubuntu, it'll work on many other distros as well. I'm using Manjaro, for instance.
The first change is about Eclipse. You don't need to install it because that'll just give you a version that doesn't like HPGCC3's plugin. (At least, that's what happened for me.) I downloaded and extracted Eclipse Indigo (select the C/C++ edition, and either Linux x86 or Linux x64 depending on what kind of Linux you installed) to my home folder. Starting works from the file browser (start the file "eclipse" within the extracted folder) instead of the system's menu, but whatever. You probably know those procedures from OSX or Windows already.

The second change is a source code patch for the tools. You need to apply it before building tools_workspace. It works like this: download the attached file tools_patch.txt (it appears this forum doesn't allow me to use the proper file extension, which would be .diff or .patch) to the tools_workspace folder, open a terminal and navigate to that folder, then run this command:

Code:

patch -p1 -i tools_patch.txt

What this patch does is some changes to the code that turns the compiler's output (in ELF format) into raw binary files. At some point there has been a change in GCC regarding alignment which the code couldn't handle. This caused the data section in my programs to sometimes be shifted by four bytes, which made all things go haywire. This patch repairs that by making the alignment code less picky. (I don't know if the change to elf2rom is necessary, but just in case... The elf2armc thing fixed my alignment problem though, so it is actually needed.)

My next note is more of an addendum regarding C program development instead of an extra build step. It's also not a proper fix but rather a band-aid solution.
Basically, I noticed that the ROM code is supposed to have only a few variables (which it sticks into a section called romglobals; this is then compiled into every HPGCC3 program you write). But it has a few more variables which overlap with your program's. When these variables are used, they may lead to bad stuff if the HPGCC3 libraries read them, or to other bad stuff later when they write to them, thereby trashing your own variables.
My workaround is to put this somewhere into my code (main.c seems like a nice enough place for it):

Code:

/* workaround for ROM globals placed at the start of the .data / .bss area; we need to shift out own variables past them */
__attribute__((section(".romglobals"))) int __ROMglobals__[20]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

Technically the comment is useless, but I like to keep it because it reminds me why this weird line is there. It also explains how this fixes things: it enlarges the romglobals section to cover these undeclared variables as well, so the linker stops putting our own stuff there.
For my ROM 80 bytes were clobbered by the undeclared variables, which is why this workaround is an array of 20 ints (with an additional compilation option disabling a certain optimization it increased to 84 bytes, see below at the mfctop description). If you want to check how many bytes are used by your own ROM, do an objdump of libs_workspace/romlib/__romlib.exe and look at the .data and .bss sections.
Some of these ROM variables are written before they are read, or they are supposed to be zero-initialized. Unfortunately that's not always the case. I didn't account for those variables because 1. I don't use the functions that need them (i.e. I don't care enough), and 2. the compiler someone else used for their ROM may have put the variables in a different order than my compiler (not really fixable).

These ROM library variables could be fixed properly, but I didn't do that because I wanted my program to be able to just work on other people's ROMs which weren't likely to be fixed, so I opted to use the workaround in the program this thread is about.
The variables I identified are:
- uarrone from libs_workspace/decnumber/common/decNumber.c, not zero-initialized; theoretically fixable by declaring it const, but the decNumber library is strictly not-HP-specific 3rd-party code, so I didn't want to tamper with it,
- mfctop from libs_workspace/decnumber/common/decCentext.c, not zero-initialized; also theoretically fixable by declaring it const (resulting in a weird "const * const" declaration), or by removing it and changing the only use (the LITEND macro on the next line) to refer directly to mfcone instead of dereferencing mfctop; this one apparently gets optimized away when compiling the ROM with normal options, but when Claudio instructed me to try adding -fno-toplevel-reorder while troubleshooting this issue it showed up,
- qcompar from libs_workspace/hplib/sys/qsort.c, written before first read; could be removed by rewriting qsort and its recursive helper function qsort1 to pass down qsort's parameter compar instead of relying on a global variable,
- indicator_hpg from libs_workspace/hpg/common/hpg_set_indicator.c, written before first read; should be fixable by turning it from a static local variable into an ordinary local variable, because the "static" semantics seem to be unnecessary in that place.
- gglorgaddr from libs_workspace/ggl/ggl/ggl_initscr.c, written before first read (at least if you use it as designed, i.e. ggl_initscr at startup and ggl_freescr at exit); this is the nastiest one not only because it's in an important function (if you plan to use GGL for your graphics at least, like I do - this is why I discovered this issue at all: this variable overwrote one of mine), but also because it's the hardest to get rid of the proper way. I think it should end up in the master globals or system globals table.

On another note, even though HPGCC3 appears to be designed for Eclipse, it's quite possible to build stuff without using that IDE. Once a project is generated using Eclipse, the code can be written in any editor, while using "make all" in a terminal for compilation. Adding, moving, or deleting files (or any similar changes to the project's structure) is probably still easier via Eclipse, but maintaining the project files (.project, .cproject, Debug/*.mk, Release/*.mk) manually is quite possible. The first two could even be dropped, and if one build configuration is enough the other one could be deleted as well. I use Kate, I edit the project files manually, and I've not yet had an issue due to that.

[Murray]

Thanks very much for you time and detailed explanation. I had to add the --binary switch to the patch command as in
patch -p1 -i tools_patch.txt --binary.
I altered the helloworld example to read
/*
* hellofix.c
*
* Created on: Dec 27, 2017
* Author: murray
*/
#include <hpgcc3.h>
/* workaround for ROM globals placed at the start of the .data / .bss area; we need to shift out own variables past them */
__attribute__((section(".romglobals"))) int __ROMglobals__[20]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

int main()
{

printf("Hello world!\n");
getchar();
return 0;
}
Unfortunately my setup is still showing the same behaviour - that is something almost recognizable as Hello World! on the screen followed by a hang. Graph3D still works though...
I don't know if it makes any difference but I've tried the build on Ubuntu 12.04, 14.04 and 16.04 (where the arm-none-eabi-gcc version is arm-none-eabi-gcc (15:4.9.3+svn231177-1) 4.9.3 20150529 (prerelease), with various other versions on the other two systems.
I don't want to be a pest, but if you can think of anything else to try, I'd be keen to hear. I've spent a few late nights on this so far - I started down this track because HPGCC SP2 has a problem with sscanf and I want to read flat files...
Best Regards and thanks again

[Murray]

In a spirit of adventure, I modified Claudio's helloWorld example to use WAIT_CANCEL instead if getchar():
/*
* helot.c
*
* Created on: Dec 28, 2017
* Author: murray
*/
#include <hpgcc3.h>
/* workaround for ROM globals placed at the start of the .data / .bss area; we need to shift out own variables past them */
__attribute__((section(".romglobals"))) int __ROMglobals__[20]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int main()
{
printf("Hello world!\n");
WAIT_CANCEL;
return 0;
}
This produces an improvement - the previous version hung in a tight loop, from the look of the cpu usage of x49gp, whereas now the program exits cleanly when I hit cancel. The characters of the displayed text are still distorted though.

[Murray]

And finally... A version of helloWorld that works.
/*
* helot.c
*
* Created on: Dec 28, 2017
* Author: murray
*/


#include <hpgcc3.h>
#include <hpgraphics.h>

/* workaround for ROM globals placed at the start of the .data / .bss area; we need to shift out own variables past them */
__attribute__((section(".romglobals"))) int __ROMglobals__[20]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

int main()
{
hpg_set_mode_mono(1);
hpg_set_font(HPG_STDSCREEN, hpg_get_minifont());
hpg_clear();
hpg_draw_text("Hello, world!", 0, 0);
hpg_flip(); //updates the screen with the new image (needed in double-buffered mode)
WAIT_CANCEL;
return 0;
}

A bit of a long way round, with a misleading example on the HPGCC3 web-site, but real signs of life.
Thanks a lot for your help.

Cheers

[3298]

Well, that's definitely weird. I copied your hellofix.c code into a new project, compiled it, loaded it into my x49gp instance, and it simply worked. I'm attaching the build output in case you want to test it on your installation.
The example you labeled as "working" is using the black-and-white mode - are you using the grayscale-enabled version of x49gp? If not, that would explain why the other examples don't look right. (They would look right on a real calculator.)
I patched x49gp a few years ago, and the patch has been accepted by x49gp's author pretty quickly. I recommend cloning your x49gp directory from that repository, or perhaps Claudio's fork if his command line switch for debugging looks appealing.

[Murray]

Thanks - that's great. Works a treat with the upgraded X49GP - didn't think of trying it on a real calculator when it was hanging the emulator :-(
Thanks for your help - hope this assists others to get things going.