How to convert floats to fixed point integers?

I’m working on a ray casting engine and would like to experiment with fixed point math. At the moment I’ve got a few thousand floats in pre-computed look-up tables. My thinking is that moving the engine over to fixed point math might help with:

  • memory (if these values can fit in 8:8 or some other 16-bit configuration, I’d cut my PROGMEM consumption by half!)
  • speed (even with LUTs precomputed, there’s a fair amount of floating point calculations that I might be able to get rid off)

I need help with:

  • what is the smallest fixed point type available, able to hold these values? Or more generally: how do I figure out if a floating point value will fit in a given fixed point type?
  • how do I convert these tables to use fixed point types? I’m generating these from a bit of C++ code so it’d be great if there’s a simple syntax to go from float to SFixed (or plain int_16t if possible?).

Thanks!

Below is a sample LUT from my app. The forum limits post-length so I put the full set up over on pastebin in case that helps.

constexpr float tan_table[769] PROGMEM {
0.000818,0.009000,0.017182,0.025367,0.033556,0.041749,0.049947,0.058152,0.066365,0.074587,0.082819,0.091062,0.099318,0.107586,0.115870,0.124169,0.132485,0.140819,0.149172,0.157546,0.165941,0.174359,0.182802,0.191269,0.199763,0.208285,0.216836,0.225417,0.234030,0.242676,0.251357,0.260073,0.268826,0.277618,0.286450,0.295324,0.304240,0.313201,0.322208,0.331263,0.340367,0.349522,0.358729,0.367990,0.377308,0.386683,0.396117,0.405613,0.415172,0.424797,0.434488,0.444249,0.454081,0.463986,0.473966,0.484025,0.494163,0.504384,0.514689,0.525081,0.535564,0.546138,0.556807,0.567574,0.578442,0.589412,0.600490,0.611676,0.622975,0.634390,0.645924,0.657580,0.669363,0.681275,0.693321,0.705504,0.717829,0.730299,0.742920,0.755694,0.768628,0.781725,0.794991,0.808430,0.822049,0.835852,0.849845,0.864034,0.878425,0.893024,0.907838,0.922875,0.938139,0.953640,0.969385,0.985381,1.001638,1.018163,1.034966,1.052055,1.069441,1.087135,1.105146,1.123485,1.142165,1.161198,1.180595,1.200370,1.220538,1.241113,1.262110,1.283545,1.305436,1.327798,1.350652,1.374017,1.397913,1.422361,1.447386,1.473010,1.499260,1.526161,1.553743,1.582035,1.611068,1.640878,1.671499,1.702969,1.735328,1.768619,1.802888,1.838183,1.874556,1.912062,1.950760,1.990713,2.031989,2.074660,2.118805,2.164509,2.211859,2.260955,2.311902,2.364813,2.419811,2.477031,2.536620,2.598733,2.663545,2.731244,2.802038,2.876154,2.953842,3.035379,3.121068,3.211248,3.306294,3.406625,3.512709,3.625071,3.744301,3.871069,4.006128,4.150340,4.304689,4.470307,4.648500,4.840782,5.048926,5.275003,5.521475,5.791267,6.087897,6.415625,6.779663,7.186462,7.644079,8.162753,8.755661,9.440068,10.239041,11.184112,12.319571,13.709556,15.450745,17.695831,20.701040,24.931747,31.330647,42.140896,64.327286,135.811066,-1222.229004,-111.115623,-58.199440,-39.420891,-29.801161,-23.952900,-20.021200,-17.196249,-15.068141,-13.407147,-12.074522,-10.981501,-10.068707,-9.294851,-8.630375,-8.053544,-7.548029,-7.101317,-6.703656,-6.347353,-6.026228,-5.735280,-5.470413,-5.228238,-5.005932,-4.801115,-4.611784,-4.436220,-4.272954,-4.120718,-3.978411,-3.845076,-3.719873,-3.602067,-3.491006,-3.386113,-3.286875,-3.192834,-3.103581,-3.018749,-2.938005,-2.861053,-2.787620,-2.717463,-2.650357,-2.586099,-2.524505,-2.465402,-2.408638,-2.354067,-2.301558,-2.250991,-2.202252,-2.155239,-2.109855,-2.066011,-2.023625,-1.982619,-1.942921,-1.904467,-1.867192,-1.831040,-1.795954,-1.761885,-1.728783,-1.696605,-1.665308,-1.634852,-1.605201,-1.576318,-1.548171,-1.520727,-1.493958,-1.467836,-1.442334,-1.417427,-1.393090,-1.369302,-1.346041,-1.323287,-1.301020,-1.279222,-1.257877,-1.236965,-1.216473,-1.196384,-1.176685,-1.157362,-1.138401,-1.119791,-1.101518,-1.083571,-1.065940,-1.048614,-1.031582,-1.014836,-0.998365,-0.982161,-0.966216,-0.950521,-0.935067,-0.919849,-0.904858,-0.890088,-0.875530,-0.861180,-0.847031,-0.833076,-0.819311,-0.805728,-0.792324,-0.779092,-0.766028,-0.753127,-0.740383,-0.727793,-0.715352,-0.703056,-0.690901,-0.678882,-0.666996,-0.655239,-0.643607,-0.632097,-0.620706,-0.609430,-0.598266,-0.587210,-0.576260,-0.565413,-0.554666,-0.544016,-0.533460,-0.522996,-0.512621,-0.502333,-0.492129,-0.482007,-0.471964,-0.461999,-0.452109,-0.442291,-0.432545,-0.422867,-0.413255,-0.403709,-0.394226,-0.384803,-0.375440,-0.366134,-0.356883,-0.347686,-0.338542,-0.329448,-0.320403,-0.311405,-0.302454,-0.293546,-0.284681,-0.275857,-0.267072,-0.258327,-0.249618,-0.240944,-0.232305,-0.223698,-0.215123,-0.206578,-0.198062,-0.189573,-0.181111,-0.172674,-0.164260,-0.155870,-0.147500,-0.139151,-0.130820,-0.122508,-0.114212,-0.105931,-0.097665,-0.089413,-0.081172,-0.072942,-0.064722,-0.056511,-0.048307,-0.040110,-0.031918,-0.023730,-0.015546,-0.007363,0.000818,0.009000,0.017182,0.025367,0.033556,0.041749,0.049947,0.058152,0.066365,0.074587,0.082819,0.091062,0.099318,0.107586,0.115870,0.124169,0.132485,0.140819,0.149172,0.157546,0.165941,0.174359,0.182802,0.191269,0.199763,0.208285,0.216836,0.225417,0.234030,0.242676,0.251357,0.260073,0.268826,0.277618,0.286450,0.295324,0.304240,0.313201,0.322208,0.331263,0.340367,0.349522,0.358729,0.367990,0.377308,0.386683,0.396117,0.405613,0.415172,0.424797,0.434488,0.444249,0.454081,0.463986,0.473966,0.484024,0.494163,0.504384,0.514689,0.525081,0.535563,0.546138,0.556807,0.567574,0.578442,0.589412,0.600490,0.611676,0.622975,0.634390,0.645924,0.657580,0.669363,0.681275,0.693321,0.705504,0.717829,0.730299,0.742919,0.755694,0.768628,0.781725,0.794991,0.808430,0.822049,0.835852,0.849845,0.864034,0.878425,0.893024,0.907838,0.922874,0.938139,0.953640,0.969385,0.985381,1.001638,1.018162,1.034965,1.052055,1.069441,1.087135,1.105146,1.123485,1.142165,1.161197,1.180596,1.200371,1.220539,1.241114,1.262111,1.283546,1.305435,1.327799,1.350653,1.374017,1.397914,1.422362,1.447386,1.473010,1.499261,1.526162,1.553743,1.582036,1.611070,1.640879,1.671499,1.702970,1.735329,1.768620,1.802890,1.838184,1.874557,1.912062,1.950761,1.990714,2.031989,2.074663,2.118807,2.164509,2.211859,2.260957,2.311903,2.364813,2.419814,2.477034,2.536620,2.598733,2.663547,2.731246,2.802039,2.876158,2.953846,3.035380,3.121068,3.211252,3.306297,3.406626,3.512715,3.625075,3.744304,3.871069,4.006133,4.150343,4.304691,4.470317,4.648508,4.840787,5.048925,5.275013,5.521481,5.791270,6.087914,6.415638,6.779672,7.186460,7.644099,8.162767,8.755669,9.440108,10.239076,11.184137,12.319566,13.709618,15.450793,17.695860,20.701231,24.931952,31.330849,42.140839,64.328629,135.814880,-1222.098511,-111.110130,-58.198334,-39.420570,-29.801189,-23.952713,-20.021118,-17.196224,-15.068040,-13.407088,-12.074492,-10.981504,-10.068673,-9.294833,-8.630368,-8.053514,-7.548010,-7.101306,-6.703658,-6.347339,-6.026220,-5.735277,-5.470399,-5.228229,-5.005926,-4.801116,-4.611776,-4.436216,-4.272952,-4.120709,-3.978405,-3.845073,-3.719874,-3.602063,-3.491003,-3.386112,-3.286870,-3.192831,-3.103579,-3.018748,-2.938002,-2.861051,-2.787619,-2.717459,-2.650354,-2.586098,-2.524504,-2.465400,-2.408636,-2.354066,-2.301556,-2.250989,-2.202251,-2.155238,-2.109852,-2.066009,-2.023623,-1.982616,-1.942920,-1.904466,-1.867192,-1.831038,-1.795953,-1.761883,-1.728783,-1.696603,-1.665307,-1.634852,-1.605199,-1.576317,-1.548170,-1.520727,-1.493957,-1.467835,-1.442333,-1.417425,-1.393089,-1.369301,-1.346041,-1.323286,-1.301019,-1.279222,-1.257875,-1.236964,-1.216472,-1.196384,-1.176684,-1.157362,-1.138401,-1.119789,-1.101517,-1.083571,-1.065940,-1.048613,-1.031582,-1.014835,-0.998364,-0.982161,-0.966216,-0.950521,-0.935067,-0.919849,-0.904858,-0.890087,-0.875530,-0.861180,-0.847031,-0.833076,-0.819310,-0.805728,-0.792323,-0.779092,-0.766028,-0.753127,-0.740383,-0.727793,-0.715352,-0.703056,-0.690900,-0.678882,-0.666996,-0.655238,-0.643607,-0.632097,-0.620705,-0.609429,-0.598265,-0.587210,-0.576259,-0.565412,-0.554665,-0.544015,-0.533459,-0.522995,-0.512621,-0.502332,-0.492128,-0.482006,-0.471963,-0.461998,-0.452108,-0.442291,-0.432544,-0.422866,-0.413255,-0.403708,-0.394225,-0.384803,-0.375440,-0.366133,-0.356883,-0.347686,-0.338542,-0.329448,-0.320403,-0.311405,-0.302453,-0.293545,-0.284680,-0.275856,-0.267072,-0.258326,-0.249618,-0.240944,-0.232305,-0.223698,-0.215123,-0.206578,-0.198062,-0.189573,-0.181111,-0.172674,-0.164260,-0.155869,-0.147500,-0.139150,-0.130820,-0.122507,-0.114212,-0.105931,-0.097665,-0.089412,-0.081172,-0.072942,-0.064721,-0.056510,-0.048307,-0.040109,-0.031917,-0.023730,-0.015545,-0.007363,0.000818};
1 Like

For float to SFixed there’s an implicit conversion:

// Implicit conversion
constexpr SFixed<7, 8> fixed = 0.5f;

For the reverse you need an explicit cast:

float floating = static_cast<float>(SFixed<7, 8>(0, 127));

(C-style casting works too, but C++-style is more self-documenting.)

It’s certainly possible, but I’m not sure why you’d want to.

You can retrieve the underlying representation with:

SFixed<7, 8> fixed = 0.5f;
int16_t integer = fixed.getInternal();

(Note that the type returned by getInternal() depends on the size and type of the fixed point.)

To figure this out you need some statistics about your data:

  • The number with the highest integer part
  • The number with the lowest integer part
  • The number with the most fractional digits

E.g. I can already see a -1222.229004, which implies you’d need at least 12 bits of integer part (11 for ‘1222’, 1 for the sign).

When you know that, you can think about how much precision you need and how much you can afford to loose.

One thing to remember is that a fixed point is essentially a mixed fraction where the denominator is a power of two.
1.5f as an SFixed<7, 8> is effectively 1 128256.

Unfortunately this varies on AVR due to the lack of a barrel shifter and limitations on multiplication and division.

Simple adding and subtracting is much cheaper with fixed points,
but multiplication tends to be slower.


I don’t know how much you already know about fixed points,
but I recommend reading A Fixed Point Primer as an introduction.

If you have any more questions don’t hesitate to ask.
(By the way, I’m the one who wrote that particular library.)

1 Like

Sorry for the double post but something just occurred to me…

You might also want to consider using ‘binary radians’ (a.k.a. brads) if possible.
Despite the name, brads are more similar to degrees than radians.
Essentially you say there are 28 (256) or 216 (65536) ‘brads’ in a circle,
then you no longer have to do any modulo operations because computer integers are implicitly modulo a power of two,
and determining the quadrant becomes a bitwise operation,
which allows you to store a single quadrant worth of sin/cos values,
and determine the operation by inspecting the quadrant.

Here’s an example I helped @Dreamer2345 write a while back :

Using 8-bit brads meant only a 64 entry look-up table was needed.

2 Likes

Thanks for taking the time! I’ll definetly read up on brads - I’ve never heard of the concept before but it sounds immediately useful!

Most of the math in my program is happening in the ray caster. Thankfully it’s only ~120 LOC. Looking at this, do you think I have anything to gain from going fixed point?

#pragma once
#include "Config.h"
#include "LevelData.h"
#include "Graphics.h"
#include "Utils.h"
#include "LUT.h"
class RayCaster {    
    struct RayStart {
        float intersection = 0.0f; //the first possible intersection point
        int boundary = 0; // the next intersection point   
        int delta = 0; // the amount needed to move to get to the next cell position
        int next_cell = 0; //cell delta, to move left / right or up / down
    };
    struct RayEnd {
        float distance = 0.0f; // the distance of intersection from the player
        int boundary = 0; // record intersections with cell boundaries        
        int intersection = 0; // used to save exact intersection point with a wall         
        bool operator <(const RayEnd& that) const noexcept { return distance < that.distance; };
    };    
    static constexpr auto WALL_BOUNDARY_COLOR = BLACK;
    static constexpr auto VERTICAL_WALL_COLOR = WHITE;
    static constexpr auto HORIZONTAL_WALL_COLOR = WHITE;      
    static constexpr auto K = 7000.0f;// think of K as a combination of view distance and aspect ratio. Pick a value that looks good. In my case: that makes the block on screen look square.
    //The MAGIC_CONSTANT must be an even power-of-two >= WORLD_SIZE. Used to quickly round our position to nearest cell wall using bitwise AND.
    static constexpr auto MAGIC_CONSTANT = (Utils::isPowerOfTwo(WORLD_SIZE) ? WORLD_SIZE : Utils::nextPowerOfTwo(WORLD_SIZE)) - Cfg::CELL_SIZE;  
      
    RayStart initHorizontalRay(const int x, const int y, const int view_angle) const noexcept {        
        const auto FACING_RIGHT = (view_angle < ANGLE_90 || view_angle >= ANGLE_270);        
        const int x_bound = FACING_RIGHT ? CELL_SIZE + (x & MAGIC_CONSTANT) : (x & MAGIC_CONSTANT); //round x to nearest CELL_WIDTH (power-of-2), this is the first possible intersection point. 
        const int x_delta = FACING_RIGHT ? CELL_SIZE : -CELL_SIZE; // the amount needed to move to get to the next vertical line (cell boundary)
        const int next_cell_direction = FACING_RIGHT ? 0 : -1;  //x coordinates increase to the left, and decrease to the right      
        const float yi = pgm_read_float(&tan_table[view_angle]) * (x_bound - x) + y; // based on first possible vertical intersection line, compute Y intercept, so that casting can begin                                
        return RayStart{ yi, x_bound, x_delta, next_cell_direction };
    }

    RayStart initVerticalRay(const int x, const int y, const int view_angle) const noexcept {
        const auto FACING_DOWN = (view_angle >= ANGLE_0 && view_angle < ANGLE_180);
        const int y_bound = FACING_DOWN ? CELL_SIZE  + (y & MAGIC_CONSTANT) : (y & MAGIC_CONSTANT); //Optimization: round y to nearest CELL_HEIGHT (power-of-2) 
        const int y_delta = FACING_DOWN ? CELL_SIZE : -CELL_SIZE; // the amount needed to move to get to the next horizontal line (cell boundary)
        const int next_cell_direction = FACING_DOWN ? 0 : -1; //remember: y coordinates increase as we move down (south) in the world, and decrease towards the top (north)               
        const float xi = pgm_read_float(&inv_tan_table[view_angle]) * (y_bound - y) + x; // based on first possible horizontal intersection line, compute X intercept, so that casting can begin              
        return RayStart{ xi, y_bound, y_delta, next_cell_direction };
    }

    RayEnd findVerticalWall(const int x, const int y, const int view_angle) const noexcept  {
        auto [yi,  x_bound, x_delta, next_x_cell] = initHorizontalRay(x, y, view_angle);//cast a ray horizontally, along the x-axis, to intersect with vertical walls
        RayEnd result;
        while (x_bound > -1 && x_bound < WORLD_SIZE) {
            const int cell_x = ((x_bound + next_x_cell) >> CELL_SIZE_FP);
            const int cell_y = static_cast<int>(yi) >> CELL_SIZE_FP;                   
            if (!isWall(cell_x, cell_y)) {
                yi += pgm_read_float(&y_step[view_angle]); //"calculate" y-intercept
                x_bound += x_delta;//move to next possible intersection points
                continue;
            }
            result.distance = (yi - y) * pgm_read_float(&inv_sin_table[view_angle]); //distance to hit
            result.boundary = x_bound; //record intersections with cell boundaries
            result.intersection = static_cast<int>(yi);
            return result;                        
        }        
        return result;          
    }  
  
    RayEnd findHorizontalWall(const int x, const int y, const int view_angle) const noexcept {
        auto [xi, y_bound, y_delta, next_y_cell] = initVerticalRay(x, y, view_angle);//cast a ray vertically, along the y-axis, to intersect with horizontal walls
        RayEnd result;
        while (y_bound > -1 && y_bound < WORLD_SIZE) {
            const int cell_x = static_cast<int>(xi) >> CELL_SIZE_FP; //the current cell that the ray is in             
            const int cell_y = ((y_bound + next_y_cell) >> CELL_SIZE_FP);
            if (!isWall(cell_x, cell_y)) {
                xi += pgm_read_float(&x_step[view_angle]); //compute next X intercept
                y_bound += y_delta;
                continue;
            }         
            result.distance = (xi - x) * pgm_read_float(&inv_cos_table[view_angle]);
            result.boundary = y_bound;
            result.intersection = static_cast<int>(xi);                                        
            return result;            
        }
        return result;
    }         
public:
    RayCaster() {} 
    void renderView(Graphics& g, const int x, const int y, int view_angle) const noexcept {
        // This function casts out RAY_COUNT rays from the viewer and builds up the display based on the intersections with the walls.
        // The distance to the first horizontal and vertical edge is recorded. The closest intersection is the one used to draw the display.
        // The inverse of that distance is used to compute the height of the "sliver" of wall that will be drawn on the screen                
        g.clearScreen();
        if ((view_angle -= HALF_FOV_ANGLE) < 0) { //compute starting angle from player. Field of view is FOV angles, subtract half of that from the current view angle
            view_angle = ANGLE_360 + view_angle;
        }
        for (int ray = 0; ray < RAY_COUNT; ray++) {
            RayEnd xray = findVerticalWall(x, y, view_angle);  //cast a ray along the x-axis to intersect with vertical walls
            RayEnd yray = findHorizontalWall(x, y, view_angle); //cast a ray along the y-axis to intersect with horizontal walls
            auto color = WALL_BOUNDARY_COLOR;
            const float min_dist = (xray < yray) ? xray.distance : yray.distance;
            if (xray < yray) { // there was a vertical wall closer than a horizontal wall                
                if (xray.intersection % CELL_SIZE > 1) {
                    color = VERTICAL_WALL_COLOR;
                }             
            }
            else { // must have hit a horizontal wall first                            
                if (yray.intersection % CELL_SIZE > 1) {
                    color = HORIZONTAL_WALL_COLOR;
                }              
            }
            // height of the sliver is based on the inverse distance to the intersection. Closer is bigger, so: height = 1/dist. However, 1 is too low a factor to look good. 
			// Thus the constant K, which has been pre-multiplied into the view-filter lookup-table (cos_table).
            const int height = static_cast<int>(pgm_read_float(&cos_table[ray]) / min_dist);
            const int clipped_height = (height > Cfg::VIEWPORT_HEIGHT) ? Cfg::VIEWPORT_HEIGHT : height;
            const int top = VIEWPORT_HORIZON - (clipped_height >> 1); //Optimization: height >> 1 == height / 2. slivers are drawn symmetrically around the viewport horizon.             
            const int bottom = (top + clipped_height)-1; //we're off by one, overdrawing 1px to the left and bottom of the viewport. 
            const int sliver_x = ray;       
            g.setColor(color);            
            g.drawVerticalLine(sliver_x, top, clipped_height - 1);    
            if (++view_angle >= ANGLE_360) {
                view_angle = 0;
            }
        }
    }
};

RAY_COUNT == 128 (arduboy screen width). So just counting the potentially costly stuff (ignoring shifts, adds or substractions) renderView will execute 128 * (4 multiplications, 1 division), per frame.

For completeness sake, here’s the code for generating the LUTs, including a bunch of the constants used throughout the ray caster.

static constexpr auto RAY_COUNT = Cfg::VIEWPORT_WIDTH; //one ray per column of screen space (horizontal resolution)
static constexpr auto FOV_DEGREES = 60; //Field of View, in degrees. We'll need to break these into RAY_COUNT sub-angles and cast a ray for each angle. We'll be using a lookup table for that        	
static constexpr auto TABLE_SIZE = static_cast<int>(VIEWPORT_WIDTH* (360.0f / FOV_DEGREES)); //how many elements we need to store the slope of every possible ray that can be projected.        
static constexpr auto ANGLE_360 = Cfg::TABLE_SIZE; //East (and total number of possible angles in a full rotation)
static constexpr auto ANGLE_90 = ANGLE_360 / 4; //South
static constexpr auto ANGLE_180 = ANGLE_360 / 2; //West
static constexpr auto ANGLE_270 = ANGLE_360 - ANGLE_90; //North
static constexpr auto ANGLE_0 = 0;  //back to East
static constexpr auto TWO_PI = 2.0f * 3.141592654f;
static constexpr auto ANGLE_TO_RADIANS = (TWO_PI / ANGLE_360);
static constexpr auto HALF_FOV_ANGLE = Cfg::VIEWPORT_WIDTH / 2; // FoV/2 in angles (for table lookup) instead of degrees.    
static constexpr auto K = 7000.0f;// think of K as a combination of view distance and aspect ratio. Pick a value that looks good. In my case: that makes the block on screen look square. (p.213)            

// tangent tables equivalent to slopes, used to compute initial intersections with ray
std::array<float, ANGLE_360 + 1> tan_table; 
std::array<float, ANGLE_360 + 1> inv_tan_table;

// step tables used to find next intersections, equivalent to slopes times width and height of cell    
std::array<float, ANGLE_360 + 1> y_step; //x and y steps, used to find intersections after initial one is found
std::array<float, ANGLE_360 + 1> x_step;

// 1/cos and 1/sin tables used to compute distance of intersection very quickly  
// Optimization: cos(X) == sin(X+90), so for cos lookups we can simply re-use the sin-table with an offset of ANGLE_90.    
std::array<float, ANGLE_360 + ANGLE_90> inv_sin_table; //+90 degrees to make room for the tail-end of the offset cos values.    
float* inv_cos_table = &inv_sin_table[ANGLE_90]; //cos(X) == sin(X+90).    

// cos table used to fix view distortion caused by radial projection (eg: cancel out fishbowl effect)
std::array<float, HALF_FOV_ANGLE * 2 + 1> cos_table;

void buildLookupTables() noexcept {
	constexpr auto TENTH_OF_A_RADIAN = ANGLE_TO_RADIANS * 0.1f;
	for (int ang = ANGLE_0; ang <= ANGLE_360; ang++) {            
		const auto rad_angle = TENTH_OF_A_RADIAN + (ang * ANGLE_TO_RADIANS); //adding a small offset to avoid edge cases with 0. 
		tan_table[ang] = std::tan(rad_angle);
		inv_tan_table[ang] = 1.0f / tan_table[ang];
		// tangent has the incorrect signs in all quadrants except 1, so manually fix the signs of each quadrant.
		if (ang >= ANGLE_0 && ang < ANGLE_180) { //upper half plane (eg. upper right & left quadrants)
			y_step[ang] = std::abs(tan_table[ang] * CELL_SIZE);
		} else {
			y_step[ang] = -std::abs(tan_table[ang] * CELL_SIZE);
		}
		if (ang >= ANGLE_90 && ang < ANGLE_270) { //left half plane (left up and down quads)
			x_step[ang] = -std::abs(inv_tan_table[ang] * CELL_SIZE);
		} else {
			x_step[ang] = std::abs(inv_tan_table[ang] * CELL_SIZE);
		}     		
		assert(std::fabs(y_step[ang]) != 0.0f && "Potential asymtotic ray on the y-axis produced while building lookup tables.");
		assert(std::fabs(x_step[ang]) != 0.0f && "Potential asymtotic ray on the x-axis produced while building lookup tables.");                     
		inv_sin_table[ang] = 1.0f / std::sin(rad_angle);         
	}
	
	//duplicate the first 90 sin values at the end of the array, to complete the joint sin & cos lookup table.
	auto end = std::end(inv_sin_table) - ANGLE_90;
	std::copy_n(std::begin(inv_sin_table), ANGLE_90, end); 
			
	// create view filter table. Without this we would see a fishbowl effect. There is a cosine wave modulated on top of the view distance as a side effect of casting from a fixed point.
	// to cancel this effect out, we multiple by the inverse of the cosine and the result is the proper scale. 
	// inverse cosine would be 1/cos(rad_angle), but 1 is too small to give us good sized slivers, hence the constant K which is arbitrarily chosen for what looks good. 
	for (int ang = -HALF_FOV_ANGLE; ang <= HALF_FOV_ANGLE; ang++) {
		const auto rad_angle = TENTH_OF_A_RADIAN + (ang * ANGLE_TO_RADIANS);
		const auto index = ang + HALF_FOV_ANGLE;
		cos_table[index] = (K / std::cos(rad_angle));
	}
}
1 Like

It’s hard to say really.

As I say, multiplication tends to be slower for fixed points,
but some things might work out cheaper, for example:

const int cell_x = static_cast<int>(xi) >> CELL_SIZE_FP;

xi is float, so converting to int is probably complicated,
(at the very least I’d guess it’s a function call, but I’m not sure,)
wheras with fixed points it would be a shift and a mask,
so there’s a possibility the compiler might be able to fuse the two shifts.

And similarly I would expect that the fixed point equivalent for:

yi += pgm_read_float(&y_step[view_angle]);

Would be cheaper because it would effectively use integer addition.

Fixed points also open up the possibility for manual optimisations.
E.g. if you know a certain SFixed will never be negative then you do a manual conversion without the sign extension step.

The main reason multiplication is expensive for fixed points (as far as I’m aware) is because you need a type twice as wide as the fixed point to avoid loss of information, and AVR CPUs don’t cope with that very well.
AVR only has a ‘mul’ instruction for smaller types,
so it has to resort to a manual algorithm for larger ones.

Ultimately I think the only way to know for sure is to try it.


Whether or not fixed points solve your problem,
I think using brads is worth considering.
Or at least finding a means to cut your table sizes to a power of two so you can use more bitwise operations when handling the indices.


Might I ask, are you using something other than the Arduino IDE to compile your code?

I notice you’re using a ‘structured binding declaration’ which are a C++17 feature,
but as far as I’m aware the Arduino IDE uses GNU++11 (C++11 with compiler extensions).

It probably doesn’t make much difference to the problem at hand,
I was just surprised to see that feature used in Arduboy code.

Ah, yeah. I’ve set the Arduino IDE up to compile with C++17. I’m actually playing around with cross platform development so this project is originally written in Visual Studio for Windows. I’m porting to Arduboy manually right now, to figure out the least common denominator might be. Eg. what my abstraction layers will need to support.

This thread is basically me getting excited and side-tracked with premature optimization. But also - more new things to learn. :smiley:

3 Likes

Is there any way for me to get an assembler listing from the Arduino IDE? Or perhaps a separate tool, to map the source code to compiler output? I’d love to figure out what really works on the Arduboy.

From a command line you can use objdump. You should be able to find the AVR version avr-objdump somewhere in the installed IDE directory tree. On my Ubuntu Linux system it’s:
.../arduino-1.8.12/hardware/tools/avr/bin/avr-objdump
I usually create a soft link to it in my local bin folder, named arduino-avr-objdump, so I can easily execute it from anywhere.

I believe you want to use the -S option but you can experiment with various switches.
https://sourceware.org/binutils/docs/binutils/objdump.html

You have to feed it the .elf file that the compiler outputs for your sketch, which should be found in a temporary build folder after compiling your sketch in the IDE (using Verify).
If you set the IDE preferences for:
Show verbose output during: ☑ compilation
the output should contain the location of this temporary folder. Search for arduino_build_xxxxxx where xxxxxx is a unique number.

On my system it appears in the system /tmp directory. I usually switch to this temporary directory and run the command from there. E.g.:
cd /tmp/arduino_build_242045
arduino-avr-objdump -S MyArduboySketch.ino.elf > MyArduboySketch.disasm

The output can be scrambled and a bit confusing, mostly due to the compiler optimisations.