Bresenham's Line Algorithm

Post your coolest Hexcasting creations here.

New topics are NOT for chatting or asking help, put those in the comments of a post or in a different forum.
User avatar
[object Object]
Posts: 70
Joined: Fri Dec 02, 2022 12:37 am

Bresenham's Line Algorithm

Post by [object Object] »

This hex is an implementation of Bresenham's Line Algorithm in Hex Casting. Adapted from this code. It makes extensive use of Hexal's macro feature. All macros used are documented below the main hex, along with suggested patterns. The full .hexpattern file is also included at the end of the post.

Video demo: https://youtu.be/x-YZOh4LHn8

Bresenham's Line Algorithm
This hex should be used with a CAD. It modifies itself to store the starting location for the line. Sneak to set the starting location without drawing a line.

Code: Select all

{
    // preamble to make this draw lines as a CAD hex
    {
        Bookkeeper's Gambit: - // previous block placeholder
    }
    Flock's Disintegration

    Mind's Reflection
    Compass' Purification
    Mind's Reflection
    Alidade's Purification
    Archer's Distillation

    Gemini Decomposition
    Scribe's Reflection
    Numerical Reflection: 1
    Rotation Gambit
    Surgeon's Exaltation
    Scribe's Gambit

    Mind's Reflection
    Stadiometer's Purification
    Numerical Reflection: 1.5
    Maximus Distillation
    {
        Bookkeeper's Gambit: -
        Charon's Gambit
    }
    Flock's Disintegration
    Augur's Exaltation
    Hermes' Gambit

    // the actual algorithm starts here
    // p0, p1 ->
    Prospector's Gambit
    Subtractive Distillation
    
    Gemini Decomposition
    Vector Sign Purification

    Undertaker's Gambit
    Hadamard's Distillation
    
    Gemini Decomposition
    Vector Disintegration
    Maximization Distillation
    Maximization Distillation

    Numerical Reflection: 4
    Fisherman's Gambit

    Prospector's Gambit
    Numerical Reflection: 2
    Division Distillation
    Gemini Decomposition
    Gemini Decomposition
    Vector Exaltation
    
    Numerical Reflection: 2
    Flock's Gambit
    Rotation Gambit II
    
    Undertaker's Gambit
    Numerical Reflection: 1
    Additive Distillation
    Gemini Decomposition
    Huginn's Gambit
    
    Gemini's Gambit
    Muninn's Reflection
    Flock's Gambit
    
    Rotation Gambit
    Huginn's Gambit
    
    Consideration: {
        Muninn's Reflection
        Flock's Disintegration
        Rotation Gambit
        Subtractive Distillation
        
        Gemini Decomposition
        Vector Sign Purification
        Numerical Reflection: 1
        Subtractive Distillation
        
        Gemini Decomposition
        Vector Sign Purification
        Subtractive Distillation
        
        Undertaker's Gambit
        Numerical Reflection: 5
        Fisherman's Gambit
        Multiplicative Distillation
        Subtractive Distillation
        
        Rotation Gambit
        Gemini Decomposition

        // do something with the current point on the line
        // here I just place a block to show off the algorithm
        Gemini Decomposition
        Break Block
        Place Block

        Rotation Gambit
        Numerical Reflection: 4
        Fisherman's Gambit
        Hadamard's Distillation
        Subtractive Distillation
        
        Jester's Gambit
        Numerical Reflection: 2
        Flock's Gambit
        Huginn's Gambit
    Consideration: }
    Jester's Gambit
    Thoth's Gambit
    Bookkeeper's Gambit: vvv
}
Sign Purification
num -> 1 or 0 or -1
awdda
Signum function.

Code: Select all

{
    Gemini Decomposition
    Numerical Reflection: 0
    Maximus Distillation
    Numerical Reflection: 1
    Numerical Reflection: 0
    Augur's Exaltation
    
    Jester's Gambit
    Numerical Reflection: 0
    Minimus Distillation
    Numerical Reflection: -1
    Rotation Gambit
    Augur's Exaltation
}
Vector Sign Purification
vec -> vec
awddaqqqq
Gets the sign of each vector component, returning the result as a vector.

Code: Select all

{
    Vector Disintegration

    Sign Purification
    Rotation Gambit
    Sign Purification
    Rotation Gambit
    Sign Purification
    Rotation Gambit

    Vector Exaltation
}
Maximization Distillation
num, num -> num
edd
Max function.

Code: Select all

{
    Dioscuri Gambit
    Maximus Distillation
    Rotation Gambit II
    Augur's Exaltation
}
Hadamard's Distillation
vec, vec -> vec
awaqawa
Hadamard (pairwise) product.

Code: Select all

{
    Vector Disintegration
    Numerical Reflection: 4
    Fisherman's Gambit
    Vector Disintegration
    
    Numerical Reflection: 50
    Swindler's Gambit
    
    Multiplicative Distillation
    Rotation Gambit II
    Multiplicative Distillation
    
    Numerical Reflection: 22
    Swindler's Gambit
    Multiplicative Distillation
    
    Rotation Gambit II
    Vector Exaltation
}
Full .hexpattern file

Code: Select all

#define Sign Purification = num -> 1 or 0 or -1
// SOUTH_EAST awdda
{
    Gemini Decomposition
    Numerical Reflection: 0
    Maximus Distillation
    Numerical Reflection: 1
    Numerical Reflection: 0
    Augur's Exaltation
    
    Jester's Gambit
    Numerical Reflection: 0
    Minimus Distillation
    Numerical Reflection: -1
    Rotation Gambit
    Augur's Exaltation
}

#define Vector Sign Purification = vec -> vec
// (sign(x), sign(y), sign(z))
// SOUTH_EAST awddaqqqq
{
    Vector Disintegration

    Sign Purification
    Rotation Gambit
    Sign Purification
    Rotation Gambit
    Sign Purification
    Rotation Gambit

    Vector Exaltation
}

#define Maximization Distillation = num, num -> num
// max(a, b)
// SOUTH_EAST edd
{
    Dioscuri Gambit
    Maximus Distillation
    Rotation Gambit II
    Augur's Exaltation
}

#define Hadamard's Distillation = vec, vec -> vec
// (AxBx, AyBy, AzBz)
// WEST awaqawa
{
    Vector Disintegration
    Numerical Reflection: 4
    Fisherman's Gambit
    Vector Disintegration
    
    Numerical Reflection: 50
    Swindler's Gambit
    
    Multiplicative Distillation
    Rotation Gambit II
    Multiplicative Distillation
    
    Numerical Reflection: 22
    Swindler's Gambit
    Multiplicative Distillation
    
    Rotation Gambit II
    Vector Exaltation
}

// Bresenham's Line Algorithm
// http://members.chello.at/easyfilter/bresenham.html
{
    // preamble to make this draw lines as a CAD hex
    {
        Bookkeeper's Gambit: - // previous block placeholder
    }
    Flock's Disintegration

    Mind's Reflection
    Compass' Purification
    Mind's Reflection
    Alidade's Purification
    Archer's Distillation

    Gemini Decomposition
    Scribe's Reflection
    Numerical Reflection: 1
    Rotation Gambit
    Surgeon's Exaltation
    Scribe's Gambit

    Mind's Reflection
    Stadiometer's Purification
    Numerical Reflection: 1.5
    Maximus Distillation
    {
        Bookkeeper's Gambit: -
        Charon's Gambit
    }
    Flock's Disintegration
    Augur's Exaltation
    Hermes' Gambit

    // the actual algorithm starts here
    // p0, p1 ->
    Prospector's Gambit
    Subtractive Distillation
    
    Gemini Decomposition
    Vector Sign Purification

    Undertaker's Gambit
    Hadamard's Distillation
    
    Gemini Decomposition
    Vector Disintegration
    Maximization Distillation
    Maximization Distillation

    Numerical Reflection: 4
    Fisherman's Gambit

    Prospector's Gambit
    Numerical Reflection: 2
    Division Distillation
    Gemini Decomposition
    Gemini Decomposition
    Vector Exaltation
    
    Numerical Reflection: 2
    Flock's Gambit
    Rotation Gambit II
    
    Undertaker's Gambit
    Numerical Reflection: 1
    Additive Distillation
    Gemini Decomposition
    Huginn's Gambit
    
    Gemini's Gambit
    Muninn's Reflection
    Flock's Gambit
    
    Rotation Gambit
    Huginn's Gambit
    
    Consideration: {
        Muninn's Reflection
        Flock's Disintegration
        Rotation Gambit
        Subtractive Distillation
        
        Gemini Decomposition
        Vector Sign Purification
        Numerical Reflection: 1
        Subtractive Distillation
        
        Gemini Decomposition
        Vector Sign Purification
        Subtractive Distillation
        
        Undertaker's Gambit
        Numerical Reflection: 5
        Fisherman's Gambit
        Multiplicative Distillation
        Subtractive Distillation
        
        Rotation Gambit
        Gemini Decomposition

        // do something with the current point on the line
        // here I just place a block to show off the algorithm
        Gemini Decomposition
        Break Block
        Place Block

        Rotation Gambit
        Numerical Reflection: 4
        Fisherman's Gambit
        Hadamard's Distillation
        Subtractive Distillation
        
        Jester's Gambit
        Numerical Reflection: 2
        Flock's Gambit
        Huginn's Gambit
    Consideration: }
    Jester's Gambit
    Thoth's Gambit
    Bookkeeper's Gambit: vvv
}
Top
User avatar
[object Object]
Posts: 70
Joined: Fri Dec 02, 2022 12:37 am

Re: Bresenham's Line Algorithm

Post by [object Object] »

Bonus: here's my Python implementation that I used as a reference while making this hex. I'm pretty proud of how compact I got the algorithm tbh.

Code: Select all

from __future__ import annotations
from dataclasses import dataclass
from typing import Callable, Iterator, Literal

def sign(x: float) -> Literal[1, 0, -1]:
    return 1 if x > 0 else -1 if x < 0 else 0

@dataclass
class Point:
    x: float
    y: float
    z: float

    @classmethod
    def zero(cls) -> Point:
        return Point(0, 0, 0)

    def sign(self) -> Point:
        return Point(sign(self.x), sign(self.y), sign(self.z))
    
    def hadamard(self, other: Point) -> Point:
        return Point(self.x * other.x, self.y * other.y, self.z * other.z)

    def __add__(self, other: float | int | Point) -> Point:
        match other:
            case float() | int():
                return Point(self.x + other, self.y + other, self.z + other)
            case Point():
                return Point(self.x + other.x, self.y + other.y, self.z + other.z)
    
    def __sub__(self, other: float | int | Point) -> Point:
        return self + (-other)

    def __mul__(self, other: float | int) -> Point:
        return Point(self.x * other, self.y * other, self.z * other)
    
    def __neg__(self) -> Point:
        return self * -1
    
    def __iter__(self) -> Iterator[float]:
        return iter((self.x, self.y, self.z))
    
    def __repr__(self) -> str:
        return f"({self.x}, {self.y}, {self.z})"

def bresenham(p0: Point, p1: Point, f: Callable[[Point], None]):
    diff = p1 - p0
    s = diff.sign()
    dp = diff.hadamard(s)

    dm = int(max(dp.x, dp.y, dp.z))
    e = Point(dm / 2, dm / 2, dm / 2)

    for _ in range(dm + 1):
        e -= dp

        mask = e.sign() - 1
        mask -= mask.sign()

        e -= mask * dm

        f(p0)
        p0 -= mask.hadamard(s)
Top
User avatar
kristi fristi
Posts: 26
Joined: Mon Dec 12, 2022 7:23 am

Re: Bresenham's Line Algorithm

Post by kristi fristi »

here's a smaller signum function using a vector operation (lol) (now edited because reasons)

Code: Select all

Numerical Reflection: 0
Numerical Reflection: 0
Vector Exaltation
Axial Purification
Vector Disintegration
Bookkeeper's Gambit: vv
Top

Return to “Akashic Records”