May 31, 2020, 06:01:40 PM

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

#### 3DzForMe

• Hero Member
• Posts: 1023
##### 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:programuses pure2d, keysetprocedure Swap(byref a :integer, byref b :integer)varc   :integerbeginc := aa := bb := cEndvarx, x0, x1, delta_x, step_x  :integery, y0, y1, delta_y, step_y  :integerz, z0, z1, delta_z, step_z  :integerswap_xy, swap_xz            :booleandrift_xy, drift_xz          :integercx, cy, cz                  :integer begin//start And End points (change these values)x0 := 0     x1 := -2y0 := 0     y1 := 5z0 := 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 `

#### Xaron

• Sr. Member
• Posts: 295
##### 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.

#### Pakz

• Full Member
• Posts: 180
##### 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.

#### Steve Elliott

• Hero Member
• Posts: 2454
##### 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!     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 3 and 4.

#### GW

• Full Member
• Posts: 199
##### 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    ForeverEnd 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`

#### 3DzForMe

• Hero Member
• Posts: 1023
##### 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?

#### 3DzForMe

• Hero Member
• Posts: 1023
##### 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 2020Graphics3D 800,600,32,2cube=CreateCube()SetBuffer BackBuffer()camera=CreateCamera()MoveEntity camera,0,0,-60light=CreateLight()RotateEntity light,90,0,0PositionEntity cube,0,0,5;start And End points (change these values)x0 = 0     :x1 = -20y0 = 0     :y1 = 50z0 = 0     :z1 = -100turncamD=0: turncamL=0swap_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"EndIfswap_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 planedelta_x = Abs(x1 - x0)delta_y = Abs(y1 - y0)delta_z = Abs(z1 - z0);direction of the linestep_x = 1:  If (x0 > x1) Then  step_x = -1step_y = 1:  If (y0 > y1) Then  step_y = -1step_z = 1:  If (z0 > z1) Then  step_z = -1;starting pointy = y0z = 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 NextElse 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 loopWhile 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`

#### 3DzForMe

• Hero Member
• Posts: 1023
##### 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