Render Graphic Functions with Minimal Integer Math, Able to Drive CNC

• Download source code - 383.8 KB

Introduction

This article describes an algorithm to render both 2D and 3D mathematical functions, using only integer arithmetic and a very low number of operations.

The description of the algorithm begins with the 2D version, which being simpler is easier to understand, and then extended to 3D.

The code provided is oriented both to CNC machines and 3D printers, as well as to the representation of 2D primitives on the screen.

A demonstrator is included that will actively explain the operation of the algorithm.

The Algorithm

What we're going to exploit is something really simple. In a pixelated world, apart from the fact that the pixels are represented with integers, the next point to be drawn for a continuous function can only be one of the adjacent pixels. This limits the number to 8. If we add to this the orientation of the curve, which is given by the previous point drawn, the quantity is reduced to 5. What is done here is to calculate the value of the function for these 5 possible candidates, choose the best one and repeat the process until the end of the curve to be represented is reached.

What we are going to exploit here is that contrary to conventional mathematics, in which exact values are sought, this algorithm is only interested in fuzzy errors, which simplifies the formulas, avoids the use of floats, and dispenses with complex operations.

As an example, to get the next point in a circle, we must calculate in each of the possible candidate points:

error ~= x*x + y*y - r*r

Where x and y are the coordinates of the candidate, and r the radius of the circle.

Which implies three multiplications and two integer additions per candidate, and most importantly, it avoids square roots and divisions.

By using codlets, we make supporting a new feature a matter of a few lines of code. The header of the octant.c file shows this:

Classic vs. Pixelated Math

I understand that math developed over centuries has been used to render primitives on grainy (or pixelated) Cartesian systems, but there are subtle differences.

In conventional mathematics, a function such as a circle or a line consists of an infinite set of points that satisfy certain restrictions, that is, they are a subset of the Cartesian plane, and may even be made up of several entities.

By contrast, a rasterized function is something radically different. It is a FINITE set of points that are related to each other, the most important being ORDER.

I think that the fact that they visually look the same may have led to confusion. Going from the continuous to the discrete world requires something similar to the analog-digital conversion of an audio system.

The Demonstrator

It is a code::blocks project, but since there are no dependencies, I include executables for 64bit.
It has the ability to draw lines and circles, its extension to other primitives is simple. Only three files, so porting to another IDE may be an easy task.

demo.exe is the executable.

It is used via the keyboard. There is a little help. In the lower left part, the 9 pixels relevant to the algorithm appear, in a 3x3 grid, for each of the calculated pixels (5 are calculated in each iteration) the error of the function appears. The system will choose the lowest error one as the next point.

To use it, we must press 'x', which will restart the system.
To start a circle, press 'c'. For a line 'l'. The system places the primitives one after the other. Remember that this system is GCODE oriented.
With the 'n' key, the system will calculate and draw the next point, based on the values at the bottom left of the screen. This is the main learning key.
The 's' key changes the indication on the screen between the draw order and the direction in which the CNC spindle is directed.

Using a Primitive

This is the primitive for a circle, which center is relative to the current point:

int circleGuess( int * center, int x, int y )  /* x^2 + y^2 - r^2  ~= 0 */
{ x -= center[ 0 ];
  y -= center[ 1 ];

  return( x*x + y*y
        -  ( center[ 0 ] * center[ 0 ] ) 
        -  ( center[ 1 ] * center[ 1 ] ) );
}

ptCur will be updated with the every call to nextPoint:

int params[ 2 ]= { x, y };  // x and y passed as parameters to the function

ptCur= nextPoint( circleGuess, params
                , ptCur.heading
                , ptCur.x, ptCur.y );

Is that simple? This is event oriented programming, so readability is poor. Nevetheless, to add a new primitive is easy. The first parameter is a pointer that contains the parameters needed for the function (a quadratic Bezier needs more than a circle) and the two remaining parameters are the point under test. ptCur holds the current pointer, as well as the curve heading.

As promised, only integer adds and multiplications used.

And Now, 3D

In the 3D version, things get complicated. The simple 3x3 pixel square used in the 2D version becomes a 3x3x3 "rubik's cube" and navigation to get the next point has to contemplate more options. However, I leave the functional code so that it can be included. Suffice it to say that it is an extension of the 2D code and use a lookup table to simplify the calculations.

Route3d.exe demonstrates the rendering of 3D segments.
gcode.exe uses this algorithm to render a hardcoded object (wheel.c) from gcode to step motor movements.

Did It Ever Work

The response is Yes:

stm32 nucleo not present.

The Future

There are two typical problems that this algorithm could simplify. The most important is the use of a rotary tool on a CNC router.

This algorithm can greatly simplify the "counting" of the radius of the cutting tool in the CNC router when cutting the part, as well as the path to travel. I will release code for this, if enough interest.

The other is "cheap" anti-aliasing for screen rendering. By having the error values for different pixels, a proportional distribution of the color can be made based on the error rate.

History

• 30^th June, 2023: Initial version