diff options
Diffstat (limited to 'src/raycastlib.h')
| -rw-r--r-- | src/raycastlib.h | 504 |
1 files changed, 504 insertions, 0 deletions
diff --git a/src/raycastlib.h b/src/raycastlib.h new file mode 100644 index 0000000..c882bfd --- /dev/null +++ b/src/raycastlib.h @@ -0,0 +1,504 @@ +#ifndef RAYCASTLIB_H +#define RAYCASTLIB_H + +/** + raycastlib (RCL) - Small C header-only raycasting library for embedded and + low performance computers, such as Arduino. Only uses integer math and stdint + standard library. + + Check the defines below to fine-tune accuracy vs performance! Don't forget + to compile with optimizations. + + Before including the library define RCL_PIXEL_FUNCTION to the name of the + function (with RCL_PixelFunction signature) that will render your pixels! + + - All public (and most private) library identifiers start with RCL_. + - Game field's bottom left corner is at [0,0]. + - X axis goes right in the ground plane. + - Y axis goes up in the ground plane. + - Height means the Z (vertical) coordinate. + - Each game square is RCL_UNITS_PER_SQUARE * RCL_UNITS_PER_SQUARE points. + - Angles are in RCL_Units, 0 means pointing right (x+) and positively rotates + clockwise. A full angle has RCL_UNITS_PER_SQUARE RCL_Units. + - Most things are normalized with RCL_UNITS_PER_SQUARE (sin, cos, vector + unit length, texture coordinates etc.). + - Screen coordinates are normal: [0,0] = top left, x goes right, y goes down. + + author: Miloslav "drummyfish" Ciz + license: CC0 1.0 + version: 0.908d + + Version numbering: major.minor[d], id 'd' is appended, this is a + in-development version based on the previous stable major.minor version. Two + 'd' versions with the same version number, .e.g. 1.0d, may be different. +*/ + +#include <stdint.h> + +#ifndef RCL_RAYCAST_TINY /** Turns on super efficient version of this library. + Only use if neccesarry, looks ugly. Also not done + yet. */ + #define RCL_UNITS_PER_SQUARE 1024 /**< Number of RCL_Units in a side of a + spatial square. */ + typedef int32_t RCL_Unit; /**< Smallest spatial unit, there is + RCL_UNITS_PER_SQUARE units in a square's + length. This effectively serves the purpose of + a fixed-point arithmetic. */ + #define RCL_INFINITY 2000000000 +#else + #define RCL_UNITS_PER_SQUARE 32 + typedef int16_t RCL_Unit; + #define RCL_INFINITY 30000 + #define RCL_USE_DIST_APPROX 2 +#endif + +#ifndef RCL_COMPUTE_WALL_TEXCOORDS +#define RCL_COMPUTE_WALL_TEXCOORDS 1 +#endif + +#ifndef RCL_COMPUTE_FLOOR_TEXCOORDS +#define RCL_COMPUTE_FLOOR_TEXCOORDS 0 +#endif + +#ifndef RCL_FLOOR_TEXCOORDS_HEIGHT +#define RCL_FLOOR_TEXCOORDS_HEIGHT 0 /** If RCL_COMPUTE_FLOOR_TEXCOORDS == 1, + this says for what height level the + texture coords will be computed for + (for simplicity/performance only one + level is allowed). */ +#endif + +#ifndef RCL_USE_COS_LUT +#define RCL_USE_COS_LUT 0 /**< type of look up table for cos function: + 0: none (compute) + 1: 64 items + 2: 128 items */ +#endif + +#ifndef RCL_USE_DIST_APPROX +#define RCL_USE_DIST_APPROX 0 /**< What distance approximation to use: + 0: none (compute full Euclidean distance) + 1: accurate approximation + 2: octagonal approximation (LQ) */ +#endif + +#ifndef RCL_RECTILINEAR +#define RCL_RECTILINEAR 1 /**< Whether to use rectilinear perspective (normally + used), or curvilinear perspective (fish eye). */ +#endif + +#ifndef RCL_TEXTURE_VERTICAL_STRETCH +#define RCL_TEXTURE_VERTICAL_STRETCH 1 /**< Whether textures should be + stretched to wall height (possibly + slightly slower if on). */ +#endif + +#ifndef RCL_COMPUTE_FLOOR_DEPTH +#define RCL_COMPUTE_FLOOR_DEPTH 1 /**< Whether depth should be computed for + floor pixels - turns this off if not + needed. */ +#endif + +#ifndef RCL_COMPUTE_CEILING_DEPTH +#define RCL_COMPUTE_CEILING_DEPTH 1 /**< As RCL_COMPUTE_FLOOR_DEPTH but for + ceiling. */ +#endif + +#ifndef RCL_ROLL_TEXTURE_COORDS +#define RCL_ROLL_TEXTURE_COORDS 1 /**< Says whether rolling doors should also + roll the texture coordinates along (mostly + desired for doors). */ +#endif + +#ifndef RCL_VERTICAL_FOV +#define RCL_VERTICAL_FOV (RCL_UNITS_PER_SQUARE / 3) +#endif + +#define RCL_VERTICAL_FOV_TAN (RCL_VERTICAL_FOV * 4) ///< tan approximation + +#ifndef RCL_HORIZONTAL_FOV +#define RCL_HORIZONTAL_FOV (RCL_UNITS_PER_SQUARE / 4) +#endif + +#define RCL_HORIZONTAL_FOV_TAN (RCL_HORIZONTAL_FOV * 4) + +#define RCL_HORIZONTAL_FOV_HALF (RCL_HORIZONTAL_FOV / 2) + +#ifndef RCL_CAMERA_COLL_RADIUS +#define RCL_CAMERA_COLL_RADIUS RCL_UNITS_PER_SQUARE / 4 +#endif + +#ifndef RCL_CAMERA_COLL_HEIGHT_BELOW +#define RCL_CAMERA_COLL_HEIGHT_BELOW RCL_UNITS_PER_SQUARE +#endif + +#ifndef RCL_CAMERA_COLL_HEIGHT_ABOVE +#define RCL_CAMERA_COLL_HEIGHT_ABOVE (RCL_UNITS_PER_SQUARE / 3) +#endif + +#ifndef RCL_CAMERA_COLL_STEP_HEIGHT +#define RCL_CAMERA_COLL_STEP_HEIGHT (RCL_UNITS_PER_SQUARE / 2) +#endif + +#ifndef RCL_TEXTURE_INTERPOLATION_SCALE + #define RCL_TEXTURE_INTERPOLATION_SCALE 1024 /**< This says scaling of fixed + poit vertical texture coord + computation. This should be power + of two! Higher number can look more + accurate but may cause overflow. */ +#endif + +#define RCL_HORIZON_DEPTH (11 * RCL_UNITS_PER_SQUARE) /**< What depth the + horizon has (the floor + depth is only + approximated with the + help of this + constant). */ +#ifndef RCL_VERTICAL_DEPTH_MULTIPLY +#define RCL_VERTICAL_DEPTH_MULTIPLY 2 /**< Defines a multiplier of height + difference when approximating floor/ceil + depth. */ +#endif + +#define RCL_min(a,b) ((a) < (b) ? (a) : (b)) +#define RCL_max(a,b) ((a) > (b) ? (a) : (b)) +#define RCL_nonZero(v) ((v) + ((v) == 0)) ///< To prevent zero divisions. +#define RCL_zeroClamp(x) ((x) * ((x) >= 0)) +#define RCL_likely(cond) __builtin_expect(!!(cond),1) +#define RCL_unlikely(cond) __builtin_expect(!!(cond),0) + +#define RCL_logV2D(v)\ + printf("[%d,%d]\n",v.x,v.y); + +#define RCL_logRay(r){\ + printf("ray:\n");\ + printf(" start: ");\ + RCL_logV2D(r.start);\ + printf(" dir: ");\ + RCL_logV2D(r.direction);} + +#define RCL_logHitResult(h){\ + printf("hit:\n");\ + printf(" square: ");\ + RCL_logV2D(h.square);\ + printf(" pos: ");\ + RCL_logV2D(h.position);\ + printf(" dist: %d\n", h.distance);\ + printf(" dir: %d\n", h.direction);\ + printf(" texcoord: %d\n", h.textureCoord);} + +#define RCL_logPixelInfo(p){\ + printf("pixel:\n");\ + printf(" position: ");\ + RCL_logV2D(p.position);\ + printf(" texCoord: ");\ + RCL_logV2D(p.texCoords);\ + printf(" depth: %d\n", p.depth);\ + printf(" height: %d\n", p.height);\ + printf(" wall: %d\n", p.isWall);\ + printf(" hit: ");\ + RCL_logHitResult(p.hit);\ + } + +#define RCL_logCamera(c){\ + printf("camera:\n");\ + printf(" position: ");\ + RCL_logV2D(c.position);\ + printf(" height: %d\n",c.height);\ + printf(" direction: %d\n",c.direction);\ + printf(" shear: %d\n",c.shear);\ + printf(" resolution: %d x %d\n",c.resolution.x,c.resolution.y);\ + } + +/// Position in 2D space. +typedef struct +{ + RCL_Unit x; + RCL_Unit y; +} RCL_Vector2D; + +typedef struct +{ + RCL_Vector2D start; + RCL_Vector2D direction; +} RCL_Ray; + +typedef struct +{ + RCL_Unit distance; /**< Distance to the hit position, or -1 if no + collision happened. If RCL_RECTILINEAR != 0, then + the distance is perpendicular to the projection + plane (fish eye correction), otherwise it is + the straight distance to the ray start + position. */ + uint8_t direction; /**< Direction of hit. The convention for angle + units is explained above. */ + RCL_Unit textureCoord; /**< Normalized (0 to RCL_UNITS_PER_SQUARE - 1) + texture coordinate (horizontal). */ + RCL_Vector2D square; ///< Collided square coordinates. + RCL_Vector2D position; ///< Exact collision position in RCL_Units. + RCL_Unit arrayValue; /** Value returned by array function (most often + this will be the floor height). */ + RCL_Unit type; /**< Integer identifying type of square (number + returned by type function, e.g. texture + index).*/ + RCL_Unit doorRoll; ///< Holds value of door roll. +} RCL_HitResult; + +typedef struct +{ + RCL_Vector2D position; + RCL_Unit direction; // TODO: rename to "angle" to keep consistency + RCL_Vector2D resolution; + int16_t shear; /**< Shear offset in pixels (0 => no shear), can simulate + looking up/down. */ + RCL_Unit height; +} RCL_Camera; + +/** + Holds an information about a single rendered pixel (for a pixel function + that works as a fragment shader). +*/ +typedef struct +{ + RCL_Vector2D position; ///< On-screen position. + int8_t isWall; ///< Whether the pixel is a wall or a floor/ceiling. + int8_t isFloor; ///< Whether the pixel is floor or ceiling. + int8_t isHorizon; ///< If the pixel belongs to horizon segment. + RCL_Unit depth; ///< Corrected depth. + RCL_Unit wallHeight;///< Only for wall pixels, says its height. + RCL_Unit height; ///< World height (mostly for floor). + RCL_HitResult hit; ///< Corresponding ray hit. + RCL_Vector2D texCoords; /**< Normalized (0 to RCL_UNITS_PER_SQUARE - 1) + texture coordinates. */ +} RCL_PixelInfo; + +void RCL_PIXEL_FUNCTION (RCL_PixelInfo *pixel); + +typedef struct +{ + uint16_t maxHits; + uint16_t maxSteps; +} RCL_RayConstraints; + +/** + Function used to retrieve some information about cells of the rendered scene. + It should return a characteristic of given square as an integer (e.g. square + height, texture index, ...) - between squares that return different numbers + there is considered to be a collision. + + This function should be as fast as possible as it will typically be called + very often. +*/ +typedef RCL_Unit (*RCL_ArrayFunction)(int16_t x, int16_t y); +/* + TODO: maybe array functions should be replaced by defines of funtion names + like with pixelFunc? Could be more efficient than function pointers. +*/ + + +RCL_Unit RCL_divRoundDown(RCL_Unit value, RCL_Unit divisor); + +/** + Function that renders a single pixel at the display. It is handed an info + about the pixel it should draw. + + This function should be as fast as possible as it will typically be called + very often. +*/ +typedef void (*RCL_PixelFunction)(RCL_PixelInfo *info); + +typedef void + (*RCL_ColumnFunction)(RCL_HitResult *hits, uint16_t hitCount, uint16_t x, + RCL_Ray ray); + +/** + Simple-interface function to cast a single ray. + + @return The first collision result. +*/ +RCL_HitResult RCL_castRay(RCL_Ray ray, RCL_ArrayFunction arrayFunc); + +/** + Casts a 3D ray in 3D environment with floor and optional ceiling + (ceilingHeightFunc can be 0). This can be useful for hitscan shooting, + visibility checking etc. + + @return normalized ditance (0 to RCL_UNITS_PER_SQUARE) along the ray at which + the environment was hit, RCL_UNITS_PER_SQUARE means nothing was hit +*/ +RCL_Unit RCL_castRay3D( + RCL_Vector2D pos1, RCL_Unit height1, RCL_Vector2D pos2, RCL_Unit height2, + RCL_ArrayFunction floorHeightFunc, RCL_ArrayFunction ceilingHeightFunc, + RCL_RayConstraints constraints); + +/** + Maps a single point in the world to the screen (2D position + depth). +*/ +RCL_PixelInfo RCL_mapToScreen(RCL_Vector2D worldPosition, RCL_Unit height, + RCL_Camera camera); + +/** + Casts a single ray and returns a list of collisions. + + @param ray ray to be cast, if RCL_RECTILINEAR != 0 then the computed hit + distance is divided by the ray direction vector length (to correct + the fish eye effect) + @param arrayFunc function that will be used to determine collisions (hits) + with the ray (squares for which this function returns different values + are considered to have a collision between them), this will typically + be a function returning floor height + @param typeFunc optional (can be 0) function - if provided, it will be used + to mark the hit result with the number returned by this function + (it can be e.g. a texture index) + @param hitResults array in which the hit results will be stored (has to be + preallocated with at space for at least as many hit results as + maxHits specified with the constraints parameter) + @param hitResultsLen in this variable the number of hit results will be + returned + @param constraints specifies constraints for the ray cast +*/ +void RCL_castRayMultiHit(RCL_Ray ray, RCL_ArrayFunction arrayFunc, + RCL_ArrayFunction typeFunc, RCL_HitResult *hitResults, + uint16_t *hitResultsLen, RCL_RayConstraints constraints); + +RCL_Vector2D RCL_angleToDirection(RCL_Unit angle); + +/** +Cos function. + +@param input to cos in RCL_Units (RCL_UNITS_PER_SQUARE = 2 * pi = 360 degrees) +@return RCL_normalized output in RCL_Units (from -RCL_UNITS_PER_SQUARE to + RCL_UNITS_PER_SQUARE) +*/ +RCL_Unit RCL_cos(RCL_Unit input); + +RCL_Unit RCL_sin(RCL_Unit input); + +RCL_Unit RCL_tan(RCL_Unit input); + +RCL_Unit RCL_ctg(RCL_Unit input); + +/// Normalizes given vector to have RCL_UNITS_PER_SQUARE length. +RCL_Vector2D RCL_normalize(RCL_Vector2D v); + +/// Computes a cos of an angle between two vectors. +RCL_Unit RCL_vectorsAngleCos(RCL_Vector2D v1, RCL_Vector2D v2); + +uint16_t RCL_sqrt(RCL_Unit value); +RCL_Unit RCL_dist(RCL_Vector2D p1, RCL_Vector2D p2); +RCL_Unit RCL_len(RCL_Vector2D v); + +/** + Converts an angle in whole degrees to an angle in RCL_Units that this library + uses. +*/ +RCL_Unit RCL_degreesToUnitsAngle(int16_t degrees); + +///< Computes the change in size of an object due to perspective (vertical FOV). +RCL_Unit RCL_perspectiveScaleVertical(RCL_Unit originalSize, RCL_Unit distance); + +RCL_Unit RCL_perspectiveScaleVerticalInverse(RCL_Unit originalSize, + RCL_Unit scaledSize); + +RCL_Unit + RCL_perspectiveScaleHorizontal(RCL_Unit originalSize, RCL_Unit distance); + +RCL_Unit RCL_perspectiveScaleHorizontalInverse(RCL_Unit originalSize, + RCL_Unit scaledSize); + +/** + Casts rays for given camera view and for each hit calls a user provided + function. +*/ +void RCL_castRaysMultiHit(RCL_Camera cam, RCL_ArrayFunction arrayFunc, + RCL_ArrayFunction typeFunction, RCL_ColumnFunction columnFunc, + RCL_RayConstraints constraints); + +/** + Using provided functions, renders a complete complex (multilevel) camera + view. + + This function should render each screen pixel exactly once. + + function rendering summary: + - performance: slower + - accuracy: higher + - wall textures: yes + - different wall heights: yes + - floor/ceiling textures: no + - floor geometry: yes, multilevel + - ceiling geometry: yes (optional), multilevel + - rolling door: no + - camera shearing: yes + - rendering order: left-to-right, not specifically ordered vertically + + @param cam camera whose view to render + @param floorHeightFunc function that returns floor height (in RCL_Units) + @param ceilingHeightFunc same as floorHeightFunc but for ceiling, can also be + 0 (no ceiling will be rendered) + @param typeFunction function that says a type of square (e.g. its texture + index), can be 0 (no type in hit result) + @param pixelFunc callback function to draw a single pixel on screen + @param constraints constraints for each cast ray +*/ +void RCL_renderComplex(RCL_Camera cam, RCL_ArrayFunction floorHeightFunc, + RCL_ArrayFunction ceilingHeightFunc, RCL_ArrayFunction typeFunction, + RCL_RayConstraints constraints); + +/** + Renders given camera view, with help of provided functions. This function is + simpler and faster than RCL_renderComplex(...) and is meant to be rendering + flat levels. + + function rendering summary: + - performance: faster + - accuracy: lower + - wall textures: yes + - different wall heights: yes + - floor/ceiling textures: yes (only floor, you can mirror it for ceiling) + - floor geometry: no (just flat floor, with depth information) + - ceiling geometry: no (just flat ceiling, with depth information) + - rolling door: yes + - camera shearing: no + - rendering order: left-to-right, top-to-bottom + + Additionally this function supports rendering rolling doors. + + This function should render each screen pixel exactly once. + + @param rollFunc function that for given square says its door roll in + RCL_Units (0 = no roll, RCL_UNITS_PER_SQUARE = full roll right, + -RCL_UNITS_PER_SQUARE = full roll left), can be zero (no rolling door, + rendering should also be faster as fewer intersections will be tested) +*/ +void RCL_renderSimple(RCL_Camera cam, RCL_ArrayFunction floorHeightFunc, + RCL_ArrayFunction typeFunc, RCL_ArrayFunction rollFunc, + RCL_RayConstraints constraints); + +/** + Function that moves given camera and makes it collide with walls and + potentially also floor and ceilings. It's meant to help implement player + movement. + + @param camera camera to move + @param planeOffset offset to move the camera in + @param heightOffset height offset to move the camera in + @param floorHeightFunc function used to retrieve the floor height + @param ceilingHeightFunc function for retrieving ceiling height, can be 0 + (camera won't collide with ceiling) + @param computeHeight whether to compute height - if false (0), floor and + ceiling functions won't be used and the camera will + only collide horizontally with walls (good for simpler + game, also faster) + @param force if true, forces to recompute collision even if position doesn't + change +*/ +void RCL_moveCameraWithCollision(RCL_Camera *camera, RCL_Vector2D planeOffset, + RCL_Unit heightOffset, RCL_ArrayFunction floorHeightFunc, + RCL_ArrayFunction ceilingHeightFunc, int8_t computeHeight, int8_t force); + +void RCL_initCamera(RCL_Camera *camera); +void RCL_initRayConstraints(RCL_RayConstraints *constraints); + +#endif |