August 15, 2020, 01:58:26 PM

Author Topic: 3d Implementation of Bresenhaum's Line algorithm  (Read 675 times)

Offline 3DzForMe

  • Hero Member
  • *****
  • Posts: 1086
3d Implementation of Bresenhaum's Line algorithm
« on: January 15, 2020, 09:58:57 AM »
Hi folks, I'm playing around with heightmaps at the moment, and I want to colourise a line plotted between x and y with a colour (greyscale) Z component.

I've located a 3D implementation of Bresenhaum's line algorithm in Cobra..... and I'm attempting to convert it to AGK / Blitz3D.

I don't suppose anyone is aware of such a thing in either language already..... thanks.

Cobra code:

Code: [Select]


Cobra implementation of 3D Line algo:

program

uses pure2d, keyset

procedure Swap(byref a :integer, byref b :integer)
var
c   :integer
begin
c := a
a := b
b := c
End

var
x, x0, x1, delta_x, step_x  :integer
y, y0, y1, delta_y, step_y  :integer
z, z0, z1, delta_z, step_z  :integer
swap_xy, swap_xz            :boolean
drift_xy, drift_xz          :integer
cx, cy, cz                  :integer

begin

//start And End points (change these values)
x0 := 0     x1 := -2
y0 := 0     y1 := 5
z0 := 0     z1 := -10

//'steep' xy Line, make longest delta x plane 
swap_xy := Abs(y1 - y0) > Abs(x1 - x0)
If swap_xy
Swap(x0, y0)
Swap(x1, y1)
EndIf

//do same For xz
    swap_xz := Abs(z1 - z0) > Abs(x1 - x0) 
    If swap_xz
        Swap(x0, z0)
        Swap(x1, z1)
    EndIf
   
    //delta is Length in Each plane
    delta_x := Abs(x1 - x0)
    delta_y := Abs(y1 - y0)
    delta_z := Abs(z1 - z0)
   
    //drift controls when To Step in 'shallow' planes
    //starting value keeps Line centred
    drift_xy  := (delta_x / 2)
    drift_xz  := (delta_x / 2)
   
    //direction of Line
    step_x := 1;  if (x0 > x1) then  step_x := -1
    step_y := 1;  if (y0 > y1) then  step_y := -1
    step_z := 1;  if (z0 > z1) then  step_z := -1
   
    //starting point
    y := y0
    z := z0
   
    //Step through longest delta (which we have swapped To x)
    For x = x0 To x1 Step step_x
       
        //copy position
        cx := x;    cy := y;    cz := z

        //unswap (in reverse)
        If swap_xz Then Swap(cx, cz)
        If swap_xy Then Swap(cx, cy)
       
        //passes through this point
        debugmsg(":" + cx + ", " + cy + ", " + cz)
       
        //update progress in other planes
        drift_xy = drift_xy - delta_y
        drift_xz = drift_xz - delta_z

        //Step in y plane
        If drift_xy < 0
            y = y + step_y
            drift_xy = drift_xy + delta_x
        EndIf 
       
        //same in z
        If drift_xz < 0
            z = z + step_z
            drift_xz = drift_xz + delta_x
        EndIf
    Next

End







Offline Xaron

  • Sr. Member
  • ****
  • Posts: 302
Re: 3d Implementation of Bresenhaum's Line algorithm
« Reply #1 on: January 15, 2020, 01:11:35 PM »
That looks pretty simple, using just integer steps. But I miss the part which actually draws something in there.

Offline Pakz

  • Full Member
  • ***
  • Posts: 183
    • My homepage
Re: 3d Implementation of Bresenhaum's Line algorithm
« Reply #2 on: January 15, 2020, 10:20:26 PM »
From what I remember from moving objects in b3d the z axis is the same as the y axis(or was it x?) i just copied the y integer math and turned it into z. I would try this with a 2d bresenham to turn it into 3d.

I did this with a homing missile thing.

The cobra code scares me :)

I have no idea where to find 3d bresenham code other than to translate from sources in google.

Edit:
I am not sure how to explain how Bresenham or my own(?) method to do it works in english language, I sort of know how to code it from memory. You start a loop with the count that is the longest distance axis. If the x is 10 steps from the target and the y 5 than you step towards it with x=1 and y=2. Same amount of steps. This creating a straight line. Same with z. Thing is to get the steps calculated.
Edit2:
In my mind I make things so complex! I would just modify a homing,issole code into a line draw. Getangle and cos and sin for the steps. Z axis is either sin or cos.

Online Steve Elliott

  • Hero Member
  • *****
  • Posts: 2627
  • elgol 2021
Re: 3d Implementation of Bresenhaum's Line algorithm
« Reply #3 on: January 15, 2020, 10:42:22 PM »
Wow, Cobra, a blast from the past!   :D  A Pascal-based language that could use pure2d so could run on any hardware (so not requiring any DirectX or OpenGL Libraries).  I always loved Pascal and C at college.
Windows 10, 64-bit, 16Gb RAM, CPU Intel i5, 3.2 GHz, Nvidia GeForce GTX 1050 (2Gb)
MacOS Catalina, 64-bit, 8Gb RAM, CPU Intel i5, 2.3 Ghz, Intel Iris Plus Graphics 640 1536 MB
Linux Mint 19.3, 64-bit, 16Gb RAM, CPU Intel i5, 3.2 GHz, Nvidia GeForce GTX 1050 (2Gb)
Raspberry Pi Zero
ZX Spectrum Next

Offline GW

  • Full Member
  • ***
  • Posts: 202
Re: 3d Implementation of Bresenhaum's Line algorithm
« Reply #4 on: January 16, 2020, 12:03:07 AM »
Here is a dusty old version I found. Don't know where it came from and didn't test it for accuracy.
Code: [Select]
Function Line3d(x1%,y1%,z1#,x2%,y2%,z2#)
    Local dx% = Abs(x2-x1)
    Local sx% = -1'Sgn(x2-x1)
    Local dy% = -Abs(y2-y1)
    Local sy% = -1'Sgn(y2-y1)
    Local err% = dx+dy
    Local e2%
    Local d# = diagdist(x1%,y1%,x2%,y2%) 'dist(x1%,y1%,x2%,y2%)
    Local dz# = (z2-z1)/d
   
    If x1<x2 Then sx=1
    If y1<y2 Then sy=1
    Repeat
        draw(x1,y1,z1)  'Or floor(z1+0.5) to round
        z1:+dz
        e2=2*err
        If(e2>=dy) Then
            If x1=x2 Then Exit
            err :+ dy
            x1 :+ sx
        EndIf
        If e2<=dx Then
            If y1=y2 Then Exit
            err :+ dx
            y1:+sy
        EndIf
    Forever
End Function

Function DiagDist#(x:Float, y:Float, x2:Float, y2:Float)
    Local xx:Float = x2 - x
    Local yy:Float = y2 - y
    Return Max(Abs(xx),Abs(yy))
End Function

Offline 3DzForMe

  • Hero Member
  • *****
  • Posts: 1086
Re: 3d Implementation of Bresenhaum's Line algorithm
« Reply #5 on: January 16, 2020, 05:50:30 AM »
@Xaron - yeah - I think it might have just popped out the 3d co-ords to the terminal window.

@Pakz - yeah, I started work on turning the 2d bresenhaum code into B3d - however other priorities bumped it down my to do list yesterday.
I also did a homer missile thing but only in 2d using sin and Cos. As for the Cobra code..... after readin the synopsis of what it 'does'
on its home page I actually concluded - this looks like a language that has some legs (....and there is quite a few of them out there now!).
For me to draw that conclusion - it takes some doing at my age.

I was even watching a short video on the Bresenhaum algo last night , clever, but simple (ish) stuff ;).

@Steve - yeah - I wrote a terminal based Space Invaders in 'C' when I'd to code in it for a living - each time I think about that
I get to thinking - Hmm, maybe I should do it for a living again - Nah! more fun saving my coding mojo for B3D and AGK Studio. ;)
It is sad t osee Cobra mothballed around 2013 by all accounts.

@GW - thanks for the code - giving it a whirl now ;) - Sorry for my ignorance - what language is it in?

Offline 3DzForMe

  • Hero Member
  • *****
  • Posts: 1086
Re: 3d Implementation of Bresenhaum's Line algorithm
« Reply #6 on: January 16, 2020, 07:12:25 AM »
This appears to work - in Blitz3D :-

Code: [Select]


;Converted from Cobra code to Blitz 3D code
;By 3DzForME aka Blitzplotter 16 Jan 2020


Graphics3D 800,600,32,2


cube=CreateCube()
SetBuffer BackBuffer()

camera=CreateCamera()

MoveEntity camera,0,0,-60

light=CreateLight()
RotateEntity light,90,0,0

PositionEntity cube,0,0,5


;start And End points (change these values)
x0 = 0     :x1 = -20
y0 = 0     :y1 = 50
z0 = 0     :z1 = -100

turncamD=0: turncamL=0

swap_xy = Abs(y1 - y0) > Abs(x1 - x0)

If swap_xy=1

Swap(x0, y0)
Swap(x1, y1)

Else

Text 20,40,"didn't call XY swp function"

EndIf

swap_xz = Abs(z1 - z0) > Abs(x1 - x0)

If swap_xz = 1

Swap(x0, z0)
Swap(x1, z1)

Else

Text 20,60,"didn'yt call XZ swp function"

EndIf

;delta is the length of eac plane
delta_x = Abs(x1 - x0)
delta_y = Abs(y1 - y0)
delta_z = Abs(z1 - z0)





;direction of the line
step_x = 1:  If (x0 > x1) Then  step_x = -1
step_y = 1:  If (y0 > y1) Then  step_y = -1
step_z = 1:  If (z0 > z1) Then  step_z = -1

;starting point
y = y0
z = z0


;step thru longest delta (which we have swapped to x)
;====================================================
;
;  step has to be a constant in Blitz 3D
;
;====================================================

If step_x=1

For x = x0 To x1 Step 1

;copy position
cx = x: cy = y: cz = z

;unswap(in reverse)
If swap_xz Then Swap(cx, cz); why unswapping now?
If swap_xy Then Swap(cx, cy)

Text 100,100+(x*20),"Passess thru this point: cx: "+cx+"   cy: "+cy+"   cz: "+cz

;update progress in other planes
drift_xy = drift_xy - delta_y
drift_xz = drift_xz - delta_z

;Step in y plane
If drift_xy < 0
y = y + step_y
drift_xy = drift_xy + delta_x
EndIf

;same in z
If drift_xz < 0
z = z + step_z
drift_xz = drift_xz + delta_x
EndIf

cube=CreateCube()
PositionEntity cube,x,y,z

Next

Else

For x = x0 To x1 Step -1

;copy position
cx = x: cy = y: cz = z

;unswap(in reverse)
If swap_xz Then Swap(cx, cz); why unswapping now?
If swap_xy Then Swap(cx, cy)

Text 100,120+(x*20),"Passess thru this point: cx: "+cx+"   cy: "+cy+"   cz: "+cz

;update progress in other planes
drift_xy = drift_xy - delta_y
drift_xz = drift_xz - delta_z

;Step in y plane
If drift_xy < 0
y = y + step_y
drift_xy = drift_xy + delta_x
EndIf

;same in z
If drift_xz < 0
z = z + step_z
drift_xz = drift_xz + delta_x
EndIf

cube=CreateCube()
PositionEntity cube,x,y,z

Next

EndIf

;Main loop

While 1

Text 20,20, "Bresenhaum 3D Plotter, by Blitzplotter"

Text 20,40, "Camera Keys: Cursors, A, Z, N, M, O K!"

; Change move values depending on the key pressed
If KeyDown( 203 )=True Then camx#=-0.1;
If KeyDown( 205 )=True Then camx#=0.1;
If KeyDown( 208 )=True Then camy#=-0.1;
If KeyDown( 200 )=True Then camy#=0.1;
If KeyDown( 44 )=True Then camz#=-0.1;  A in
If KeyDown( 30 )=True Then camz#=0.1;   Z out

;camera rotate keys
If KeyDown( 49  )=True Then camrotLeft#=-1; N
If KeyDown( 50 )=True Then camrotLeft#=1; M
If KeyDown( 24 )=True Then camrotDown#=-1 ;O
If KeyDown( 37  )=True Then camrotDown#=1; K

If camrotLeft#=-1
turncamL=turncamL-1
EndIf

If camrotLeft#=1
turncamL=turncamL+1
EndIf

If camrotDown#=-1
turncamD=turncamD-1
EndIf

If camrotDown#=1
turncamD=turncamD+1
EndIf

MoveEntity camera,camx#,camy#,camz#
RotateEntity camera,turncamD,turncamL,0

camx#=0: camy#=0: camz#=0
camrotLeft#=0: camrotDown#=0

VWait 8

Flip

RenderWorld


Wend


Function Swap(a, b) ; integer swapping function

c = a
a = b
b = c

Return c

End Function





Offline 3DzForMe

  • Hero Member
  • *****
  • Posts: 1086
Re: 3d Implementation of Bresenhaum's Line algorithm
« Reply #7 on: January 18, 2020, 07:06:59 AM »
The following is actually progress.... I know it doesn't seem like it though  ;D


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal