grafx is an open source Java library for drawing lines and filling polygons using floating-point endpoint coordinates. It is distributed under the terms of a BSD-style license. This library is compatible with Java 1.0 (yes, 1996 era) and newer. The code strives for simplicity and for not having dependencies on libraries in order that it be easily translatable to other programming languages.
There are two variants of this library: there is a 2D rendering library which is extremely optimized for performance and which has been available since the year 2001, and there is a newer 3D rendering library which was finally released on November 1st, 2023. The 2D rendering library has reached a level of maturity, while the 3D rendering library is still in active development, as it currently lacks the capability of rendering in perspective projection mode. It is expected that major refinements to the 3D library will be released shortly after Christmas 2023.
Below are some screenshots taken of the demo which comes included with the 3D rendering library release. The time taken to "rasterize" each of the images below at a 800x600 pixel resolution on a seven year old Lenovo T570 laptop running OpenJDK 11 is in the vicinity of one to three milliseconds, z buffer computations included. Needless to say this library performs very well and is definitely a suitable backend for the implementation of a lightweight video game.
The reason for developing my own strategies in line-drawing algorithms is that the Bresenham line-drawing algorithm does not suit my needs because it uses integer endpoint coordinates. I'm still interested in a strategy that will turn pixels on or leave them off; I do not want to employ concepts such as "stoke width" or antialiasing in my video game; I want to preserve a "retro 1980s" look. Lastly, it is crucial for my video game that a subsegment of a larger line segment is able to align perfectly pixel by pixel, when drawn on top with a different color. For example in a game of 3D Blockout, when the playing block is hugging the corner of the pit/well, its corner line should overlap perfectly with the corner line of the well.
Zoomed in to the image above at three sections we see the following pixels being turned on where the orangle lines of the well should be perfectly "behind" the white lines of the playing block:
And so, seeing how the Bresenham line-drawing algorithm, which most of the world was still using at the time, was not able to achieve such perfect results as depicted above due to its usage of integer endpoint coordinates, in the year 2001 I embarked upon a mission to invent a new strategy for turning on discrete pixels for a line having floating-point endpoint coordinates. I had just graduated from U.C. Berkeley in Mathematics at the time, where I excelled in my Computer Graphics course taught by Professor Carlo Sequin (whose teaching assistant was Jordan Smith); even during that class I realized the shortcomings of the Bresenham line-drawing algorithm. The Bresenham strategy is inherently flawed because it aliases the endpoints of a line segment, instead of aliasing the line at a pixel level. This leads to very "jaggy" approximations for curved lines, and it certainly makes it impossible to draw subsegments on top of longer segments where a complete pixel-wise overlap is desired, at least in the majority of cases.
The grafx project is hosted on sourceforge.net and has been since the year 2001. If it weren't for their service my source code would probably be lost by now.
The 3D version of this library is in active development, with a major release expected shortly after Christmas 2023. An effort is being made to study existing techniques of z-computation and clipping with respect to perspective projections. The possibility of discovering a slightly revised perspective projection function which simplifies computations is being evaluated. This is very involving work which takes time and takes careful consideration for details.
It would be interesting to implement something similar to the existing 3D graphics library using only integer math (i.e. fixed point arithmetic); while this could be achieved with decent results by employing only 32 bit integers, it would in fact be possible to achieve results that are extremely accurate by employing both 32 bit and 64 bit integers, in tandem. However, modern CPU architecture is such that floating point math and integer math are not much different in time taken to perform computations, and so it seems reasonable to follow a trend in the opposite direction, which is to move away from code that tries to implement everything with integer math, by utilizing various tricks, and move towards code that computes simply and by using floating point math where it is natural to do so. This also makes the code more understandable, simple, and maintainable.
Another trend in computer architecture recently has been the addition of CPU "cores" to computers, and not so much the increase in actual CPU speed. For that reason it seems reasonable that this 3D graphics pipeline be able to utilize all/most CPU cores on a given computer by modularizing subtasks of the entire rendering process. Significant efforts are being made to tackle that department as well.
There are very similar accuracy and threading puzzles that need to be solved in the area of computational geometry, in particular with CSG libraries which do unions, subtractions, and intersections between 3D solids. A mistake that is often made is that coordinates are converted to a finalized format before all of the computations finish taking place, leading to situations where "slightly off" boolean operations are performed due to the introduction of premature inaccuracies. Because I am aspiring to tackle some serious open source computational geometry issues in the near future, I figured that re-aquainting myself with this similar pixel-level puzzle will get my thoughts rolling in the right direction.
I have to confess that of all software projects I've worked on, this sort of nitty-gritty accumulation error-handling code is the most difficult of all; it's on par with or even more difficult than multi-threaded code. While I lack the vocabulary to fully describe what makes these sorts of problems so difficult, I can sort of explain it by stating that in the case of these line-drawing and polygon-filling algorithms there seems to be the need to have numbers exist in four different spaces: (1) the integer space for pixel aliasing, (2) the 64 bit space for specifying input coodinates, (3) a [semi-temporary] 32 bit space which chops accumulation errors, and (4) an additional space, which I have not yet been able to employ explicitly, which is finer than the 64 bit space and where all underlying computations take place. An analogy to better understand the idea would be the study of real numbers in Mathematics and the comparison of those to rational numbers, where between every two infinitesimally close rational numbers there lie a countably infinite number of other rational numbers, and there lie an uncountably infinte amount of real numbers in that same interval.
Figuring out the intricate implementation details with regards to accumulation error-handling is extremely taxing on the human brain; while I was deep in the cavernous abyss of the finite set of floating-point numbers, I began to see multi-dimensional spaces unfolding. I saw how a many-dimensional space was apparently being collapsed onto a one-dimensional space, and I began to see hierarchies/groupings of errors being handled by the cast from dimension to dimension, the first of which is the cast from 64 bit floating-point to 32 bit floating-point, and the second of which is the cast from a quasi-32 bit floating-point space (where the integer value is allowed to attain very large magnitudes) to the integer space. As I was beginning to understand these multi-dimensional aspects of error-handling within a single number line, I also began to comprehend how the introduction of a third dimension in a game of Tetris would allow the player to flip the L-piece or the S-piece to be oriented the other way, where the piece would become the Γ-piece and the Z-piece, respectively. I began to see the analogous problem of reflecting certain pieces in Blockout, which is essentially 3D Tetris; the 3D playing pieces each fit into exactly one of two categories: either the mirror image of the 3D piece is the same as the piece itself (modulo rotation in 3D), or the mirror image is distinct from the piece being reflected. In other words one realizes that a block which is reflected about an arbitrary plane will or won't pass a test: either that reflected block can be rotated in 3D to align perfectly with the original block or it can't.
I began to see the introduction of a fourth dimension, and I began to imagine the 3D Blockout piece being rotated in much the same way that a Tetris piece could be rotated in 3D to flip the S-shape to a Z-shape [for example]. Continuing on with my intense imagining I realized that this flipping of the 3D Blockout piece by reflecting it about an arbitrary plane was similar to turning the piece "inside out", only that the confusing aspect of this idea is that there seem to be two ways to realize this turning; one way where the 2-manifold sphere about which we're reflecting is "external" to the block and the other where the reflective 2-manifold sphere is "inside" the block, perhaps even being degenerate to a single point. I then remembered that a spherical 2-manifold can be turned inside out smoothly, without temporary kinks, while embedded in 4-space. Things in this world began to make sense to me but I became frightened at the same time. Perhaps the notion of "inside" and "outside" are false constructs, as are "before" and "after" as time proximity notions. It seems that humans have been able to categorize all 2-manifolds with the study of Topology in Mathematics, and that they're still struggling with a categorization theorem for 3-manifolds.
All downloads for grafx are available at https://sourceforge.net/projects/grafx/files/. The current version of grafx for 2D rendering is 2.3.2. The current version for 3D rendering is 1.1. These are named grafx-2.3.2 and grafx_3d-1.1, respectively.
The best way to communicate with me regarding questions, bugs, or concerns is by using the bug tracker on my SourceForge project page.