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

[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.