Using Normals for backface-culling...

Blitz3D Forums/Blitz3D Programming/Using Normals for backface-culling...

3DBuzzFan

(Posted 2003) [#1]

I am using normals for backface culling on b+.
I am experiencing with 3d, as opposet to most of you guys, who know everything about it.
Well, my backface-culling algorythm seems to be working... as long as I don´t rotate around the X-axis.
Here is the code.
Please let me know what is wrong.
And, please, don´t pay too much attention to code correctness or ellegance... I am learning 3d, so I probably made more mistakes than one would explect.
Now, I would like someone to explain to me what I am doing wrong...
Thanks a lot,

Rui Barbosa Jr.

<CODE>
Dim x#(16, 9)
Dim y#(16, 9)
Dim z#(16, 9)
;
Dim rx#(16, 9)
Dim ry#(16, 9)
Dim rz#(16, 9)
;
Dim nx#(16, 9)
Dim ny#(16, 9)
Dim nz#(16, 9)
;
Dim rnx#(16, 9)
Dim rny#(16, 9)
Dim rnz#(16, 9)
;
Global a# = 0.00
Global b# = 0.00
Global g# = 0.00

Graphics 1024, 768, 16, 0

For i% = 0 To 15
For j% = 0 To 8
r# = Sin#(22.50 * j%)
x#(i%, j%) = Cos#(22.50 * i%) * r#
y#(i%, j%) = Cos#(22.50 * j%)
z#(i%, j%) = -Sin#(22.50 * i%) * r#
Next
Next

For i% = 0 To 15
For j% = 0 To 8
x0# = +x#(i%, j%)
y0# = -y#(i%, j%)
z0# = +z#(i%, j%)
x1# = +x#((i% + 1) Mod 16, j%)
y1# = -y#((i% + 1) Mod 16, j%)
z1# = +z#((i% + 1) Mod 16, j%)
x2# = +x#((i% + 1) Mod 16, (j% + 1) Mod 9)
y2# = -y#((i% + 1) Mod 16, (j% + 1) Mod 9)
z2# = +z#((i% + 1) Mod 16, (j% + 1) Mod 9)
x3# = +x#(i%, (j% + 1) Mod 9)
y3# = -y#(i%, (j% + 1) Mod 9)
z3# = +z#(i%, (j% + 1) Mod 9)
If Abs(x2# - x3#) < 0.001 Then
dx1# = x2# - x0#
dy1# = y2# - y0#
dz1# = z2# - z0#
dx2# = x2# - x1#
dy2# = y2# - y1#
dz2# = z2# - z1#
Else
dx1# = x3# - x1#
dy1# = y3# - y1#
dz1# = z3# - z1#
dx2# = x3# - x2#
dy2# = y3# - y2#
dz2# = z3# - z2#
EndIf
nx#(i%, j%) = (dy1# * dz2#) - (dz1# * dy2#)
ny#(i%, j%) = (dz1# * dx2#) - (dx1# * dz2#)
nz#(i%, j%) = (dx1# * dy2#) - (dy1# * dx2#)
l# = Sqr#((nx#(i%, j%) * nx#(i%, j%)) + (ny#(i%, j%) * ny#(i%, j%)) + (nz#(i%, j%) * nz#(i%, j%)))
nx#(i%, j%) = nx#(i%, j%) / l#
ny#(i%, j%) = ny#(i%, j%) / l#
nz#(i%, j%) = nz#(i%, j%) / l#
Next
Next

Repeat
Cls()
rotateVertices(a#, b#, g#)
rotateNormals(a#, b#, g#)
drawSphere()
Flip()
If KeyDown(30) Then
a# = a# + 1.00
While a# > 360.00
a# = a# - 360.00
Wend
EndIf
If KeyDown(44) Then
a# = a# - 1.00
While a# < 0.00
a# = a# + 360.00
Wend
EndIf
If KeyDown(31) Then
b# = b# + 1.00
While b# > 360.00
b# = b# - 360.00
Wend
EndIf
If KeyDown(45) Then
b# = b# - 1.00
While b# < 0.00
b# = b# + 360.00
Wend
EndIf
If KeyDown(32) Then
g# = g# + 1.00
While g# > 360.00
g# = g# - 360.00
Wend
EndIf
If KeyDown(46) Then
g# = g# - 1.00
While g# < 0.00
g# = g# + 360.00
Wend
EndIf
Until KeyHit(1)
End

Function rotateVertices(alpha#, betha#, gamma#)
For i% = 0 To 15
For j% = 0 To 8
xl0# = x#(i%, j%)
yl0# = y#(i%, j%)
zl0# = z#(i%, j%)
xl1# = (Sin#(betha#) * zl0#) + (Cos#(betha#) * xl0#)
yl1# = yl0#
zl1# = (Cos#(betha#) * zl0#) - (Sin#(betha#) * xl0#)
xl2# = xl1#
yl2# = yl1# * Cos#(alpha#) - zl1# * Sin#(alpha#)
zl2# = yl1# * Sin#(alpha#) + zl1# * Cos#(alpha#)
rx#(i%, j%) = yl2# * Sin#(gamma#) + xl2# * Cos#(gamma#)
ry#(i%, j%) = yl2# * Cos#(gamma#) - xl2# * Sin#(gamma#)
rz#(i%, j%) = zl2#
Next
Next
End Function

Function rotateNormals(alpha#, betha#, gamma#)
For i% = 0 To 15
For j% = 0 To 8
xl0# = nx#(i%, j%)
yl0# = ny#(i%, j%)
zl0# = nz#(i%, j%)
xl1# = zl0# * Sin#(betha#) + xl0# * Cos#(betha#)
yl1# = yl0#
zl1# = zl0# * Cos#(betha#) - xl0# * Sin#(betha#)
xl2# = xl1#
yl2# = yl1# * Cos#(alpha#) - zl1# * Sin#(alpha#)
zl2# = yl1# * Sin#(alpha#) + zl1# * Cos#(alpha#)
rnx#(i%, j%) = yl2# * Sin#(gamma#) + xl2# * Cos#(gamma#)
rny#(i%, j%) = yl2# * Cos#(gamma#) - xl2# * Sin#(gamma#)
rnz#(i%, j%) = zl2#
Color 255, 255, 255
Text 100 + 100 * j%, 100 + 20 * i%, rnz#(i%, j%)
Next
Next
End Function

Function drawSphere()
For i% = 0 To 15
For j% = 0 To 7
x0# = +rx#(i%, j%) * 100.00 + 512.00
y0# = -ry#(i%, j%) * 100.00 + 384.00
x1# = +rx#((i% + 1) Mod 16, j%) * 100.00 + 512.00
y1# = -ry#((i% + 1) Mod 16, j%) * 100.00 + 384.00
x2# = +rx#((i% + 1) Mod 16, (j% + 1) Mod 9) * 100.00 + 512.00
y2# = -ry#((i% + 1) Mod 16, (j% + 1) Mod 9) * 100.00 + 384.00
x3# = +rx#(i%, (j% + 1) Mod 9) * 100.00 + 512.00
y3# = -ry#(i%, (j% + 1) Mod 9) * 100.00 + 384.00
; If Abs(x2# - x3#) < 0.01 Then
; dx1# = x2# - x0#
; dy1# = y2# - y0#
; dx2# = x2# - x1#
; dy2# = y2# - y1#
; Else
; dx1# = x3# - x1#
; dy1# = y3# - y1#
; dx2# = x3# - x2#
; dy2# = y3# - y2#
; EndIf
; bf# = (dx1# * (dy2# - dy1#)) - ((dx2# - dx1#) * dy1#)
; If bf# > 0.00 Then
If rnz#(i%, j%) > 0.00 Then
If (j And 1) Then
Color 255, 0, 0
Else
Color 0, 255, 0
EndIf
Line x0#, y0#, x1#, y1#
Line x1#, y1#, x2#, y2#
Line x2#, y2#, x3#, y3#
Line x3#, y3#, x0#, y0#
EndIf
Next
Next
End Function
<ENDCODE>

3DBuzzFan

(Posted 2003) [#2]

BTW.:
If I Do this, instead, it works perfectly...

Function drawSphere()
For i% = 0 To 15
For j% = 0 To 7
x0# = +rx#(i%, j%) * 100.00 + 512.00
y0# = -ry#(i%, j%) * 100.00 + 384.00
x1# = +rx#((i% + 1) Mod 16, j%) * 100.00 + 512.00
y1# = -ry#((i% + 1) Mod 16, j%) * 100.00 + 384.00
x2# = +rx#((i% + 1) Mod 16, (j% + 1) Mod 9) * 100.00 + 512.00
y2# = -ry#((i% + 1) Mod 16, (j% + 1) Mod 9) * 100.00 + 384.00
x3# = +rx#(i%, (j% + 1) Mod 9) * 100.00 + 512.00
y3# = -ry#(i%, (j% + 1) Mod 9) * 100.00 + 384.00
If Abs(x2# - x3#) < 0.01 Then
dx1# = x2# - x0#
dy1# = y2# - y0#
dx2# = x2# - x1#
dy2# = y2# - y1#
Else
dx1# = x3# - x1#
dy1# = y3# - y1#
dx2# = x3# - x2#
dy2# = y3# - y2#
EndIf
bf# = (dx1# * (dy2# - dy1#)) - ((dx2# - dx1#) * dy1#)
If bf# > 0.00 Then
;If rnz#(i%, j%) > 0.00 Then
If (j And 1) Then
Color 255, 0, 0
Else
Color 0, 255, 0
EndIf
Line x0#, y0#, x1#, y1#
Line x1#, y1#, x2#, y2#
Line x2#, y2#, x3#, y3#
Line x3#, y3#, x0#, y0#
EndIf
Next
Next
End Function

Why is that?
I hope it is just some programming error of mine, as opposed to a flaw in the algorythm itself.
(In other words, I am dtrying to use the rotated normals for lighting the polygons properly, as well as performing backface-culling.
But, as far as I can tell, and if there is no "programming error" or typo in the code, I must assume that the rotated normals are not accurate enough for performing back-face culling.
If that is the case, what kind of algorythm should I employe?)
Thanks a lot,

Rui Barbosa Jr.

John Pickford

(Posted 2003) [#3]

Doesn't the hardware do this anyway?

Shambler

(Posted 2003) [#4]

Yes, hardware already does this much faster than any software ( even C++ ) can do it.

Unless you are not talking about rendering, maybe you are making something else e.g. dynamic lightmapping.

Rob	(Posted 2003) [#5]

I think its a blitzplus app the guy is talking about.

3DBuzzFan

(Posted 2003) [#6]

Hi.
I am trying to learn how 3d engines work.
Yes, it is written in Blitz Plus.
I am trying to learn how to do backface culling in software, instead of using the hardware.
It may sound stupid, specialy with all the 3d hardware available today, but it is a matter of learning how it works, instead of finding the best way to do it.
So far, I thought that the rotated normals would be good enough in order to perform the task, but my proggy didn´t work well.
Actualy, the problem only happens when I rotate around the X axis.
Can you help me find out what is wrong in the code?
Thanks,

Rui Barbosa Jr.

Ross C

(Posted 2003) [#7]

Right, i'm not too good on this kinda stuff. If i were doing this, i'd check to see if the normal of the triangle or vertex was facing away from the camera. Am i right in assuming that? And that the camera had it's own normal?

col	(Posted 2003) [#8]

You need lots of resource info. 3D math is an art in itself. A better way is a dedicated book. I've bought 2 books on 3D graphics, the first one I bought a while ago is 3D Computer Graphics by Watt. The second is Trick of 3D programming Gurus. The second is worth its weight in gold.

You should be using polygon normals for back face culling, not vertex normals. Vertex normals are for lighting algos ( unless you want flat shaded polys ).

ps. I advise you to use matrix math. If you don't then you can end up with some seriously long equations :)
Anyway in your code you are updating the vertices and normals seperately, I changed your 'RotateVertices' code to this and commented out the call to 'RotateNormals':

Function rotateVertices(alpha#, betha#, gamma#)
For i% = 0 To 15
For j% = 0 To 8
xl0# = x#(i%, j%)
yl0# = y#(i%, j%)
zl0# = z#(i%, j%)
xl1# = (Sin#(betha#) * zl0#) + (Cos#(betha#) * xl0#)
yl1# = yl0#
zl1# = (Cos#(betha#) * zl0#) - (Sin#(betha#) * xl0#)
xl2# = xl1#
yl2# = yl1# * Cos#(alpha#) - zl1# * Sin#(alpha#)
zl2# = yl1# * Sin#(alpha#) + zl1# * Cos#(alpha#)
rx#(i%, j%) = yl2# * Sin#(gamma#) + xl2# * Cos#(gamma#)
ry#(i%, j%) = yl2# * Cos#(gamma#) - xl2# * Sin#(gamma#)
rz#(i%, j%) = zl2#

************ START OF MOD
rnx#(i%, j%) = yl2# * Sin#(gamma#) + xl2# * Cos#(gamma#)
rny#(i%, j%) = yl2# * Cos#(gamma#) - xl2# * Sin#(gamma#)
rnz#(i%, j%) = zl2#
************ END OF MOD
Next
Next
End Function

There are still a few errors in there but hey, 2 mins work :)

3DBuzzFan

(Posted 2003) [#9]

Hey Col!
Thanks for the help.
Bellow, I have a new implementation, with some simple flat-shaded polygons, but now using your modifications/unification of rotateVertices/rotateNormals.
It works real good.
You may see that the polygons are all lit correctly, despite backface culling is not 100% correct yet...
But it doesn´t have to be. I mean, I do not need a 100% perfect backface culling algorythm.
It is ok if it does not drop a backface polygon, as long as it does not drop the ones that are facing the user.
Can you give me some more help ?
Please, take the code bellow and try it for yourself.
I know it is no fancy 3d engine or anything like that.
But all that I need is to get the lighting in place, as well as removing as many backfaces as possible, without dropping the visible ones --- even if this means drawing back-faces over front-faces.

I am doing all this because I have actualy written a very nice 3d engine, but was not able to handle lights properly.
Backface culling is something very cool that I want to add, but I already use a 32 bit Z-Buffer, which takes care of removing undesirable pixels (the ones that may pass the backface removal because of a flaw in the algorythm and/or lack of precision in the calculations).

I can tell you that the engine I have created is very cool, and includes a character creation tool, as well.
It currently runs on the PS2, without proper lighting.
As I do ALL of my researching wit Blitz Plus, I tryied to do it myself.

Please do me a BIG favor...
Just paste the code bellow into your BlitzPlus IDE and give it a try.
Just let me know if the lighting feels right, ok?

Thank you **so much** for your help!

Rui Barbosa Jr.

[CODE]
Dim polyhedre%(256, 256)
Dim paintArray%(256, 2)
;
Dim x#(16, 9)
Dim y#(16, 9)
Dim z#(16, 9)
;
Dim rx#(16, 9)
Dim ry#(16, 9)
Dim rz#(16, 9)
;
Dim nx#(16, 9)
Dim ny#(16, 9)
Dim nz#(16, 9)
;
Dim rnx#(16, 9)
Dim rny#(16, 9)
Dim rnz#(16, 9)
;
Global a# = 0.00
Global b# = 0.00
Global g# = 0.00
;
Global lx# = 1.00
Global ly# = 1.00
Global lz# = 1.00

Graphics 1024, 768, 16, 0
ClsColor 255, 128, 64

For i% = 0 To 15
For j% = 0 To 8
r# = Sin#(22.50 * j%)
x#(i%, j%) = Cos#(22.50 * i%) * r#
y#(i%, j%) = Cos#(22.50 * j%)
z#(i%, j%) = Sin#(22.50 * i%) * r#
Next
Next

For i% = 0 To 15
For j% = 0 To 8
x0# = +x#(i%, j%)
y0# = -y#(i%, j%)
z0# = +z#(i%, j%)
x1# = +x#((i% + 1) Mod 16, j%)
y1# = -y#((i% + 1) Mod 16, j%)
z1# = +z#((i% + 1) Mod 16, j%)
x2# = +x#((i% + 1) Mod 16, (j% + 1) Mod 9)
y2# = -y#((i% + 1) Mod 16, (j% + 1) Mod 9)
z2# = +z#((i% + 1) Mod 16, (j% + 1) Mod 9)
x3# = +x#(i%, (j% + 1) Mod 9)
y3# = -y#(i%, (j% + 1) Mod 9)
z3# = +z#(i%, (j% + 1) Mod 9)
If Abs(x2# - x3#) < 0.001 Then
dx1# = x2# - x0#
dy1# = y2# - y0#
dz1# = z2# - z0#
dx2# = x2# - x1#
dy2# = y2# - y1#
dz2# = z2# - z1#
Else
dx1# = x3# - x1#
dy1# = y3# - y1#
dz1# = z3# - z1#
dx2# = x3# - x2#
dy2# = y3# - y2#
dz2# = z3# - z2#
EndIf
nx#(i%, j%) = (dy1# * dz2#) - (dz1# * dy2#)
ny#(i%, j%) = (dz1# * dx2#) - (dx1# * dz2#)
nz#(i%, j%) = (dx1# * dy2#) - (dy1# * dx2#)
l# = Sqr#((nx#(i%, j%) * nx#(i%, j%)) + (ny#(i%, j%) * ny#(i%, j%)) + (nz#(i%, j%) * nz#(i%, j%)))
nx#(i%, j%) = nx#(i%, j%) / l#
ny#(i%, j%) = ny#(i%, j%) / l#
nz#(i%, j%) = nz#(i%, j%) / l#
Next
Next

Repeat
Cls()
rotateVertices(a#, b#, g#)
drawSphere()
Flip()
If KeyDown(30) Then
a# = a# + 1.00
While a# > 360.00
a# = a# - 360.00
Wend
EndIf
If KeyDown(44) Then
a# = a# - 1.00
While a# < 0.00
a# = a# + 360.00
Wend
EndIf
If KeyDown(31) Then
b# = b# + 1.00
While b# > 360.00
b# = b# - 360.00
Wend
EndIf
If KeyDown(45) Then
b# = b# - 1.00
While b# < 0.00
b# = b# + 360.00
Wend
EndIf
If KeyDown(32) Then
g# = g# + 1.00
While g# > 360.00
g# = g# - 360.00
Wend
EndIf
If KeyDown(46) Then
g# = g# - 1.00
While g# < 0.00
g# = g# + 360.00
Wend
EndIf
If KeyDown(33) Then
lx# = lx# - 0.03125
While lx# < 0.00
lx# = lx# + 1.00
Wend
EndIf
If KeyDown(47) Then
lx# = lx# + 0.03125
While lx# > 1.00
lx# = lx# - 1.00
Wend
EndIf
If KeyDown(34) Then
ly# = ly# - 0.03125
While ly# < 0.00
ly# = ly# + 1.00
Wend
EndIf
If KeyDown(48) Then
ly# = ly# + 0.03125
While ly# > 1.00
ly# = ly# - 1.00
Wend
EndIf
If KeyDown(35) Then
lz# = lz# - 0.03125
While lz# < 0.00
lz# = lz# + 1.00
Wend
EndIf
If KeyDown(49) Then
lz# = lz# + 0.03125
While lz# > 1.00
lz# = lz# - 1.00
Wend
EndIf
Until KeyHit(1)
End

Function rotateVertices(alpha#, betha#, gamma#)
For i% = 0 To 15
For j% = 0 To 8
xl0# = x#(i%, j%)
yl0# = y#(i%, j%)
zl0# = z#(i%, j%)
xl1# = (Sin#(betha#) * zl0#) + (Cos#(betha#) * xl0#)
yl1# = yl0#
zl1# = (Cos#(betha#) * zl0#) - (Sin#(betha#) * xl0#)
xl2# = xl1#
yl2# = yl1# * Cos#(alpha#) - zl1# * Sin#(alpha#)
zl2# = yl1# * Sin#(alpha#) + zl1# * Cos#(alpha#)
rx#(i%, j%) = yl2# * Sin#(gamma#) + xl2# * Cos#(gamma#)
ry#(i%, j%) = yl2# * Cos#(gamma#) - xl2# * Sin#(gamma#)
rz#(i%, j%) = zl2#
rnx#(i%, j%) = yl2# * Sin#(gamma#) + xl2# * Cos#(gamma#)
rny#(i%, j%) = yl2# * Cos#(gamma#) - xl2# * Sin#(gamma#)
rnz#(i%, j%) = zl2#
Next
Next
End Function

Function drawSphere()
For i% = 0 To 15
For j% = 0 To 7
x0# = +rx#(i%, j%) * 100.00 + 512.00
y0# = -ry#(i%, j%) * 100.00 + 384.00
x1# = +rx#((i% + 1) Mod 16, j%) * 100.00 + 512.00
y1# = -ry#((i% + 1) Mod 16, j%) * 100.00 + 384.00
x2# = +rx#((i% + 1) Mod 16, (j% + 1) Mod 9) * 100.00 + 512.00
y2# = -ry#((i% + 1) Mod 16, (j% + 1) Mod 9) * 100.00 + 384.00
x3# = +rx#(i%, (j% + 1) Mod 9) * 100.00 + 512.00
y3# = -ry#(i%, (j% + 1) Mod 9) * 100.00 + 384.00
If rnz#(i%, j%) > 0.00 Then
c% = (((rnx#(i%, j%) * lx#) + (rny#(i%, j%) * ly#) + (rnz#(i%, j%) * lz#)) / 1.00) * 255
If c% > 255 Then
c% = 255
Else
If c% < 15 Then
c% = 15
EndIf
EndIf
c% = (c% Shl 16)
paintTriangle(x0#, y0#, x1#, y1#, x3#, y3#, c%)
paintTriangle(x1#, y1#, x2#, y2#, x3#, y3#, c%)
EndIf
Next
Next
End Function

Function paintTriangle(x0#, y0#, x1#, y1#, x2#, y2#, c%)
minx# = 9999
maxx# = 0
miny# = 9999
maxy# = 0
;
If x0# < minx# Then minx# = x0#
If x0# > maxx# Then maxx# = x0#
If x1# < minx# Then minx# = x1#
If x1# > maxx# Then maxx# = x1#
If x2# < minx# Then minx# = x2#
If x2# > maxx# Then maxx# = x2#
If y0# < miny# Then miny# = y0#
If y0# > maxy# Then maxy# = y0#
If y1# < miny# Then miny# = y1#
If y1# > maxy# Then maxy# = y1#
If y2# < miny# Then miny# = y2#
If y2# > maxy# Then maxy# = y2#
;
xsize# = maxx# - minx#
ysize# = maxy# - miny#
;
x0# = x0# - minx#
x1# = x1# - minx#
x2# = x2# - minx#
y0# = y0# - miny#
y1# = y1# - miny#
y2# = y2# - miny#
;
For i% = 0 To xsize#
For j% = 0 To ysize#
polyhedre%(i%, j%) = 0
Next
Next
;
drawBresenhamLine(x0#, y0#, x1#, y1#)
drawBresenhamLine(x1#, y1#, x2#, y2#)
drawBresenhamLine(x2#, y2#, x0#, y0#)
;
For j% = 0 To ysize#
For i% = 0 To xsize#
If polyhedre%(i%, j%) Then
paintArray%(j%, 0) = i%
Exit
EndIf
Next
For i% = xsize# To 0 Step -1
If polyhedre%(i%, j%) Then
paintArray%(j%, 1) = i%
Exit
EndIf
Next
Next
;
Color (c% Shr 16), (c% Shr 8) And 255, c% And 255
;
For i% = 0 To ySize#
Line minx# + paintArray%(i%, 0), miny# + i%, minx# + paintArray%(i%, 1), miny# + i%
Next
End Function

Function drawBresenhamLine(x0%, y0%, x1%, y1%)
If x0% = x1% Then
If y0% = y1% Then
polyhedre%(x0%, y0%) = 1
Return
EndIf
If y0% < y1% Then
For i% = y0% To y1%
polyhedre%(x0%, i%) = 1
Next
Return
EndIf
For i% = y1% To y0%
polyhedre%(x0%, i%) = 1
Next
Return
EndIf
If y0% = y1% Then
If x0% < x1% Then
For i% = x0% To x1%
polyhedre%(i%, y0%) = 1
Next
Return
EndIf
For i% = x1% To x0%
polyhedre%(i%, y0%) = 1
Next
Return
EndIf
If y1% < y0% Then
temp% = y0%
y0% = y1%
y1% = temp%
temp% = x0%
x0% = x1%
x1% = temp%
EndIf
dx% = x1% - x0%
If dx% < 0 Then
dx% = -dx%
xinc% = -1
Else
xinc% = 1
EndIf
dy% = y1% - y0%
If dy% < 0 Then
dy% = -dy%
yinc% = -1
Else
yinc% = 1
EndIf
two_dx% = dx% + dx%
two_dy% = dy% + dy%
xx% = x0%
yy% = y0%
If dx% > dy% Then
error% = 0
For i% = 0 To dx%
polyhedre%(xx%, yy%) = 1
xx% = xx% + xinc%
error% = error% + two_dy%
If error% > dx% Then
error% = error% - two_dx%
yy% = yy% + yinc%
EndIf
Next
Else
error% = 0
For i% = 0 To dy%
polyhedre%(xx%, yy%) = 1
yy% = yy% + yinc%
error% = error% + two_dx%
If error% > dy% Then
error% = error% - two_dy%
xx% = xx% + xinc%
EndIf
Next
EndIf
End Function
[/CODE]

3DBuzzFan

(Posted 2003) [#10]

BTW: use the following keys to control rotations of the sphere and the light:

Sphere:
+ - Axis
==========
A, Z x
S, X y
D, C z

Light Source:
+ - Axis
==========
F, V x
G, B y
H, N z

3DBuzzFan

(Posted 2003) [#11]

Hi Col.

Here´s one thing that I need some help with:
In the code above, if I change the line

If rnz#(i%, j%) > 0.00 Then

to

If rnz#(i%, j%) > -0.25 Then

I get a perfect result.
Why is that?
If it is due to some lack of precision in the Blitz Plus compiler, then it is fine. If not, then that is a big worry to me...
... because I do not understand the reason why I had to change it.

As I told before, it drops less polys than it should, but that is fine, because I am using a z-buffer in the real engine.
The z-buffering takes care of those unwanted polygons.

But, again... why such a big difference?
I would be prepared to accept -0.01 or even -0.05 without asking, but -0.25... that´s almost 14.50 degrees off.

(I hope it is just a matter of math precision).

Thanks for your help,

Rui Barbosa Jr.

3DBuzzFan

(Posted 2003) [#12]

It also worked with

If rnz#(i%, j%) > -0.21875 Then

That´s just about 12.5 degrees off, which is 56% of the precision I need (22.50 degrees or 1/16th of 360 degrees), so this should suffice.
If you can help me understand why this happens...
I do not even have to find a fix... just would like to know the reason why.
Thanks,

Rui Barbosa Jr.

3DBuzzFan

(Posted 2003) [#13]

One more question...
I got the normals working --- actualy Col got them working.
(I just have to figure out the reason for the 12.5 degrees error, but that can be done later).

Now, the next step would be assigning indices to the normals, instead of applying rotations to the normals, I would like to be able to add the angles, then after that, find out which normal index to use, which would ultimately give me the normal itself (pre-stored, in a table).

There will be 144 unique normal indices, despite only 114 of them will actualy have unique normals assigned to them, but that is another story :^).

From those 114 diferent shades, only (up to) half of them can be seen at any given time.
That´s 57 different light gradients.
But, again, remember that those will be represented by (up to) 72 (= half of 144) unique normal indices.

Now, I am not *that smart*, so I am sure someone did that before.

Why do I want to do that?

Because I am working with hierarchyc models.
And, as you guys know, when you rotate a component, you must apply that rotation to all of its child components.
And you must do that recursively, untill you get to the bottom component;

For instance:

When move the shoulder, you must rotate it.
Then, you must rotate the elbow by the same angles.
Then you must go down piece by piece in the hierarchy.

Things get worse, when you get to the hand.
That´s because you will have to apply that same rotation to the first bone of each finger.
Then, apply it to every second bone, and the third bone (except for the thumb, of course).

The question is:
If instead of using the normals, I use the normal indices, which could be expressed as (alpha, betha), wouldn´t it be just a matter of adding the angles and, once you do that, get the correct normal index ?

You guys following me?
Is this totally wrong?

Thanks,

Rui Barbosa Jr.

col	(Posted 2003) [#14]

The lighting is incorrect. My fault 8( You have to make a decision whether you light by the polygon face or by the vertex. Currently you set the normals up as the polygon face normal, then with my mod we have changed to 'the vertex normal is now the vertex position'!! This is completely wrong! Oops.

I'm working a rewrite of your calculations.......

3DBuzzFan

(Posted 2003) [#15]

Hi Col.
Sorry for the delay.
Yes, I have to make a decision about what kind of normal I need.
I need the normals to be the polygon face normal.
As it is right now, "the vertex normal is now the vertex position" works fine for me.
And is a very good solution for my engine, trust me.
It is just fine, the way it is... except for the 12.5 degress offset.
(I have to compare against -0.21875 instead of 0.0)
If that can be fixed, then it will be perfect.
It would be great if you could help me with the 3d maths of it.
Trust me, the 3d engine for the PS2 is real good and I got a **good** use for it, already.
One more thing: it is a voxel based character engine.
So, you will find out why the "vertex normal is now the vertex position" is just fine.
(All that I need is a "normal ID" to assign to each vertex" and the normal is the vertex position itself, could be different, but works fine for me).

If you don´t get it, imagine a voxel ( A REAL VOXEL, that is... a real cube), imagine that the sphere is inside of it and touches each face of the voxel cube at the face´s exact center point.
If I rotate the cube (voxel), around its center, each face will still touch one single (different) point of the sphere.

I am planning on using a very limmited set of pre-computed normals... 144.
If you check the source-code again, you will see that I have set the sphere to exectly 144 polygons.

So, based on this, I guess you can help me find the best way to do it, right?
But, as far as my common-sense tells me, the vertex position is the normal itself, in this very specific voxel based engine.

Thanks again for your help, Col.

Hope to hear from you soon.

Rui Barbosa Jr.

3DBuzzFan

(Posted 2003) [#16]

Its is working fine already, Col...
But, if you could help me get rid of the 12.5 degrees difference, well... that would be just perfect.
I hope I am not bothering you...

Thanks again,

Rui Barbosa Jr.

Andy	(Posted 2003) [#17]

>As I told before, it drops less polys than it should, but
>that is fine, because I am using a z-buffer in the real
>engine.

Have a look at this, it may be useful.

http://www.cstone.net/~kyoung/sbuf_faq.html

Andy

col	(Posted 2003) [#18]

Nice one Andy.

Rui, to get your engine perfect maybe you should think about representing your data in a different format, at least until its working right, then change the format to what ever you wish. By format I mean you have a bunch of vetices in 3d space, then a bunch of polygons which will have each corner of the polygon point to the vertex. This way you can seperate polygon normal from vertex normal data. I did a quick example but using a simple cube although I'm sure this is not 100% technically correct ( I haven't tested it thoroughly ) it is only to show an outline of what I mean by means of representing your data.

[CODE]
Graphics 800,600,32,1

Dim Vertex#(8,3) ;Vertex Position BEFORE any transformation or rotation
Dim RVertex#(8,3) ;Vertex Position AFTER any transformation or rotation

Dim VNormal#(8,3) ;Vertex Normal BEFORE any transformation or rotation
Dim RVNormal#(8,3) ;Vertex Normal AFTER any transformation or rotation

Dim PNormal#(6,3) ;Polygon Normal BEFORE any transformation or rotation
Dim RPNormal#(6,3) ;Polygon Normal AFTER any transformation or rotation

Dim polygon(6,4) ;1 quad per face * 6 faces, 4 vertices per quad

CreateObject

While Not KeyDown(1)

Cls

alpha=alpha+1
beta=beta+1
gamma=gamma+1

RotateObject(alpha,beta,gamma)

TransformObject(0,0,0)

DrawObjectSolid
;DrawObjectWireFrame

Flip

Wend
End

Function CreateObject()
;Setup cube vertices
; X Y Z
Vertex(1,1)=-1.0 Vertex(1,2)=1.0 Vertex(1,3)=-1.0
Vertex(2,1)=1.0 Vertex(2,2)=1.0 Vertex(2,3)=-1.0
Vertex(3,1)=1.0 Vertex(3,2)=-1.0 Vertex(3,3)=-1.0
Vertex(4,1)=-1.0 Vertex(4,2)=-1.0 Vertex(4,3)=-1.0
Vertex(5,1)=-1.0 Vertex(5,2)=1.0 Vertex(5,3)=1.0
Vertex(6,1)=1.0 Vertex(6,2)=1.0 Vertex(6,3)=1.0
Vertex(7,1)=1.0 Vertex(7,2)=-1.0 Vertex(7,3)=1.0
Vertex(8,1)=-1.0 Vertex(8,2)=-1.0 Vertex(8,3)=1.0

;Define the polygon vertices
polygon(1,1)=1 polygon(1,2)=2 polygon(1,3)=3 polygon(1,4)=4
polygon(2,1)=2 polygon(2,2)=6 polygon(2,3)=7 polygon(2,4)=3
polygon(3,1)=6 polygon(3,2)=5 polygon(3,3)=8 polygon(3,4)=7
polygon(4,1)=5 polygon(4,2)=1 polygon(4,3)=4 polygon(4,4)=8
polygon(5,1)=5 polygon(5,2)=6 polygon(5,3)=2 polygon(5,4)=1
polygon(6,1)=4 polygon(6,2)=3 polygon(6,3)=7 polygon(6,4)=8

;Scale the object solely for this demo
ScaleObject(100)

CreatePolygonNormals
End Function

Function CreatePolygonNormals()
For poly=1 To 6
;Get three vertices from each poly
v1=polygon(poly,1)
v2=polygon(poly,2)
v3=polygon(poly,3)

;now we the x,y,z position of each vertice
vx1#=Vertex(v1,1)
vy1#=Vertex(v1,2)
vz1#=Vertex(v1,3)

vx2#=Vertex(v2,1)
vy2#=Vertex(v2,2)
vz2#=Vertex(v2,3)

vx3#=Vertex(v3,1)
vy3#=Vertex(v3,2)
vz3#=Vertex(v3,3)

;Find v1-v2 and v1-v3 then place into u and v:
ux#=vx1-vx2
uy#=vy1-vy2
uz#=vz1-vz2

vx#=vx1-vx3
vy#=vy1-vy3
vz#=vz1-vz3

;Create the Normal by finding the cross product
Cx# = uy*vz - uz*vy
Cy# = uz*vx - ux*vz
Cz# = ux*vy - uy*vx

;Normalize the normal
If Cx<>0.0 Cx=Cx/Sqr(cx*cx)
If Cy<>0.0 Cy=Cy/Sqr(cy*cy)
If Cz<>0.0 Cz=Cz/Sqr(cz*cz)

PNormal(poly,1)=Cx
PNormal(poly,2)=Cy
PNormal(poly,3)=Cz
Next
End Function

Function ScaleObject(scale#)
For vert=1 To 8
Vertex(vert,1)=Vertex(vert,1)*Scale
Vertex(vert,2)=Vertex(vert,2)*Scale
Vertex(vert,3)=Vertex(vert,3)*Scale
Next
End Function

Function RotateObject(alpha#,beta#,gamma#)
;Rotate the Vertices
For vert=1 To 8
x0#=Vertex(vert,1)
y0#=Vertex(vert,2)
z0#=Vertex(vert,3)

;Rotate around Y axis
x1#=(Cos(beta) * z0) + (Sin(beta) * x0)
y1#=y0
z1#=-(Sin(beta) * z0) + (Cos(beta) * x0)

;Rotate around X axis
x2#=x1
y2#=(y1 * Cos(alpha)) - (z1 * Sin(alpha))
z2#=(y1 * Sin(alpha)) + (z1 * Cos(alpha))

;Rotate around Z axis
x3#=(x2 * Cos(gamma)) - (y2 * Sin(gamma))
y3#=(x2 * Sin(gamma)) + (y2 * Cos(gamma))
z3#=z2

;Store in Rotated Vertex array
RVertex(vert,1)=x3
RVertex(vert,2)=y3
RVertex(vert,3)=z3
Next

;Rotate the Normals
For poly=1 To 6
nx#=PNormal(poly,1)
ny#=PNormal(poly,2)
nz#=PNormal(poly,3)

;Rotate around Y axis
nx1#=(Cos(beta) * nz) + (Sin(beta) * nx)
ny1#=ny
nz1#=-(Sin(beta) * nz) + (Cos(beta) * nx)

;Rotate around X axis
nx2#=nx1
ny2#=(ny1 * Cos(alpha)) - (nz1 * Sin(alpha))
nz2#=(ny1 * Sin(alpha)) + (nz1 * Cos(alpha))

;Rotate around Z axis
nx3#=(nx2 * Cos(gamma)) - (ny2 * Sin(gamma))
ny3#=(nx2 * Sin(gamma)) + (ny2 * Cos(gamma))
nz3#=nz2

RPNormal(poly,1)=nx3
RPNormal(poly,2)=ny3
RPNormal(poly,3)=nz3
Next
End Function

Function TransformObject(Tx#,Ty#,Tz#)
For vert=1 To 8
x#=RVertex(vert,1)
y#=RVertex(vert,2)
z#=RVertex(vert,3)

RVertex(vert,1)=x+Tx
RVertex(vert,2)=y+Ty
RVertex(vert,3)=z+Tz
Next
End Function

Function DrawObjectSolid()
;For back face removal we test the dot product
;between our view vector and the polygon normal

;Our View vector
ViewX#=0.0
ViewY#=0.0
ViewZ#=1.0

For poly=1 To 6
Nx#=RPNormal(poly,1)
Ny#=RPNormal(poly,2)
Nz#=RPNormal(poly,3)

;If View.Normal > 0 then render ( ignore back facing polys )
If ViewX*NX + ViewY*Ny + ViewZ*Nz > 0.0
RenderPolygon(poly)
EndIf
Next

End Function

Function DrawObjectWireFrame()
For poly=1 To 6
RenderPolygon(poly)
Next
End Function

Function RenderPolygon(poly)
v1=polygon(poly,1)
v2=polygon(poly,2)
v3=polygon(poly,3)
v4=polygon(poly,4)

vx1#=RVertex(v1,1) vy1#=RVertex(v1,2) vz1#=RVertex(v1,3)
vx2#=RVertex(v2,1) vy2#=RVertex(v2,2) vz2#=RVertex(v2,3)
vx3#=RVertex(v3,1) vy3#=RVertex(v3,2) vz3#=RVertex(v3,3)
vx4#=RVertex(v4,1) vy4#=RVertex(v4,2) vz4#=RVertex(v4,3)

sx1#=400+vx1
sy1#=300+vy1
sx2#=400+vx2
sy2#=300+vy2
sx3#=400+vx3
sy3#=300+vy3
sx4#=400+vx4
sy4#=300+vy4

Line sx1,sy1,sx2,sy2
Line sx2,sy2,sx3,sy3
Line sx3,sy3,sx4,sy4
Line sx4,sy4,sx1,sy1
End Function
[/CODE]

I feel this is a step in the right direction, simply because we need to eliminate as many errors as early as possible, especially before they introduce new errors that are nearly impossible to find. The only reason the previous code seems to work is because the object in at world origin ( 0,0,0 ) as soon as your move away from that position, the algo will fail badly along with all the lighting.

3DBuzzFan

(Posted 2003) [#19]

Ho Andy.
I was aware of s-buffers before I started working on the voxel engine.
S-BUFFER´s are cool, but in a voxel-space, dealing with z-buffer makes much more sense, because uualy, objects are seen from a distance at which voxels are almost 1 pixel x 1 pixel big.
The actualy are cubes, math-wise, and they actualy look like cubes, when you take a VERY close look at them.
But *usualy* they are at most 4 pixels big, which doesn´t allow for efficient use of S-BUFFERS.
Thanks for the tip, thou.

Rui Barbosa Jr.

3DBuzzFan

(Posted 2003) [#20]

Hi Col.

I have checked the rotating cube.
And it works perfectly.
Now, don´t worry about having it centered at the world coordinates.
The voxel engine works just the same.
When I rotate a voxel object around its picot, I just have to do this:

x# = x# - pivotX#
y# = y# - pivotY#
z# = z# - pivotZ#
;
;Rotate the voxel object here
;
x# = x# + pivtoX#
y# = y# + pivotY#
z# = z# + pivotY#

And tht is all it takes in order to take the pivot coordinates out of the way.

I would like to try your method with the voxel engine.
But, first, I would like to experiment with a sphere, instead of a cube.
If it works properly, no doubt I will use it.
An I thank you you for the great help.

I will have to get rid of floating point variables, and find a more compact way for representing the normals thou.
The spiderman head, for instance, employes 9800 voxels, and is equivalent to a 2000 polygons head model, in terms of graphics quality.
So, you see, storing 9800 normals is very memory consumming, specialy when you need photo-realistic models on the screen.
Spiderman, alone, uses 45 objects.
Some are small, like the fingers, but some are pretty big - his chest.
The average size is the shoulder.
BTW: If you want to have a better idea of how I cut spiderman in order to model it, take a look at Marvel´s fully poseable action figures. I actually have bought two spidermans.
One of them is right in front of me, and I use it to check the screen output against the real toy.
The other one... went through a surgic procedure hehe... got all of its parts, disassembled, in order to make it easier for me to model them.
Hierarchy is fine, too.
But here´s another thing... the final version of the engine will have to deal with normal indices, instead of the normals itself.
Because each time I draw the model, I have to recalculate the lighting for EACH voxel, which is very ime consumming.

I have already implemmented the normal indices, that does make it practical, because instead of computing the rotated normals for all 9800 voxels of spideys head, for instance, I only have to rotate 144 normals, no matter how far or how big it is.

This is even more critical when you add hierarchy to it.
Take spideys butt, for instance (sorry for the name, bu that was the word that came to my mind when I wrote the hierarchy part of the code).
Every time a change the butt´s rotation, I have to recalculate ALL normal tables for each and every piece of the model.
That is a total of 345 normal tables, each consisting of 144 normals = almost 50.000 normals!
Now, add to that, the fact that no 3d engine would be usable if you can have only one character at the screen, at any given time.
Double it, if you want to write a fighting game, and you end-up with almost 100.000 normals to rotate.

That´s why I have to use normal tables.
Handling individual voxel normals would make it absolutely impossible to achieve.

After implementing the lighting, no matter how slow it will run, I will have o find a way to use normal indices, no matter what... or else, I will have to forget about real-time lighting.

I have put all this info here, because I would like you to have a very clear understanding of why the backface-culling and normal rotation is so critical to the voxel engine.
The previous version of backface culling works fine, believe me... the number of drawn voxels dropped from 9800 5300 - the perfect solution would give us a count of 4900 voxels actualy drawn, but that is close enough - the engine is spending only 9.2% more time than it should.
I am prepared to accept that performance loss, for now.
But I truly agree with you that, if it can be done right from the start, then it is better to spend more time on that now than trying to find errors later.

I am glad you are helping me.
Thank you so much.

Rui Barbosa Jr.

3DBuzzFan

(Posted 2003) [#21]

Yeah, I took a closer look at your cube code.
That´s exactly what I am looking for.
Bacface culling based on the rotated normals!
I just have to try it with the sphere now, to make sure it will work for all 144 possible angles.
If it works, then that´s how I am going to do it.

Just a few more words on why this code is so crytical to the voxel engine...

1. Take the terminal bone of the pointing finger.
Every time I draw it, I have to apply its own x, y and z rotations to it, right?
But, before that, I have to apply its parents rotations to it.
And, before that, I have to apply its parents´parent´s rotations to it.
And this goes recursively, untill I reach the topmost object (in this case, the "butt").
So, after all the recursive path is taken, I end up applying 11 rotations to that small part of the model.
The part immediately above it, needs 10 rotations, and the one above it, 9 rotations, etc...
That´s why I end up with 345 rotations for each character per each frame.
(Actualy, it´s 115 rotations, but I am considering the rotation of each independent component of the normal here, i.e., 3 components per normal = 345 rotations).

So, all that I actualy need, is ONE single polygon model, which has to be a sphere.
This same sphere, with radius = 1.00, will be used to generate all normal rotations, and will be used to rebuild each normals table.

This is important to understand... rotations to normals won´t be applied to the character or any of its components.
They will be applied to the same sphere, every time.
This will allow for some level of optimization.

Thanks again,

Rui Barbosa Jr.

Paradox7

(Posted 2003) [#22]

weeeee, alright, check it, does it work ok now? the change was in the rotateVertices, i made other little modifications, only because i love modding stuff :D You can spin the sphere with the Mouse! Try it, move mouse slow, also Press Q to make it bounce around the screen, press it again to stop it. You also forgot to put Setbuffer Backbuffer() so i added that, it smooth now, and doesn't flicker, I also made it screen res independent, so you can change the res to anything you want, and it will work just as perfectly, try it, 640, 480 :D

Before you start pressing Q and moving with the mouse and screen res changes, just give it a normal spin, hold Z X together, and you will see that it culls alot better, its not all blockly and ODD looking as before, How Did I Do It?

I have no freakin clue, i'm just a master of messing with stuff till it works, or i give up :P I know nothing of 3D programming, and have no clue to wtf is going on, although I wish I did, this is awesome. Great work, i noticed that your light source is Fixed to the sphere.

Dim polyhedre%(256, 256)
Dim paintArray%(256, 2)
;
Dim x#(16, 9)
Dim y#(16, 9)
Dim z#(16, 9)
;
Dim rx#(16, 9)
Dim ry#(16, 9)
Dim rz#(16, 9)
;
Dim nx#(16, 9)
Dim ny#(16, 9)
Dim nz#(16, 9)
;
Dim rnx#(16, 9)
Dim rny#(16, 9)
Dim rnz#(16, 9)
;
Global a# = 0.00
Global b# = 0.00
Global g# = 0.00
;
Global lx# = 1.00
Global ly# = 1.00
Global lz# = 1.00



Graphics 1024, 768, 16, 1
SetBuffer BackBuffer()
ClsColor 255, 128, 64



For i% = 0 To 15
	For	j% = 0 To 8
		r# = Sin#(22.50 * j%)
		x#(i%, j%) = Cos#(22.50 * i%) * r#
		y#(i%, j%) = Cos#(22.50 * j%)
		z#(i%, j%) = Sin#(22.50 * i%) * r#
	Next
Next



For i% = 0 To 15
	For j% = 0 To 8
		x0# = +x#(i%, j%)
		y0# = -y#(i%, j%)
		z0# = +z#(i%, j%)
		x1# = +x#((i% + 1) Mod 16, j%)
		y1# = -y#((i% + 1) Mod 16, j%)
		z1# = +z#((i% + 1) Mod 16, j%)
		x2# = +x#((i% + 1) Mod 16, (j% + 1) Mod 9)
		y2# = -y#((i% + 1) Mod 16, (j% + 1) Mod 9)
		z2# = +z#((i% + 1) Mod 16, (j% + 1) Mod 9)
		x3# = +x#(i%, (j% + 1) Mod 9)
		y3# = -y#(i%, (j% + 1) Mod 9)
		z3# = +z#(i%, (j% + 1) Mod 9)
		If Abs(x2# - x3#) < 0.001 Then
			dx1# = x2# - x0#
			dy1# = y2# - y0#
			dz1# = z2# - z0#
			dx2# = x2# - x1#
			dy2# = y2# - y1#
			dz2# = z2# - z1#
		Else
			dx1# = x3# - x1#
			dy1# = y3# - y1#
			dz1# = z3# - z1#
			dx2# = x3# - x2#
			dy2# = y3# - y2#
			dz2# = z3# - z2#
		EndIf
		nx#(i%, j%) = (dy1# * dz2#) - (dz1# * dy2#)
		ny#(i%, j%) = (dz1# * dx2#) - (dx1# * dz2#)
		nz#(i%, j%) = (dx1# * dy2#) - (dy1# * dx2#)
		l# = Sqr#((nx#(i%, j%) * nx#(i%, j%)) + (ny#(i%, j%) * ny#(i%, j%)) + (nz#(i%, j%) * nz#(i%, j%)))
		nx#(i%, j%) = nx#(i%, j%) / l#
		ny#(i%, j%) = ny#(i%, j%) / l#
		nz#(i%, j%) = nz#(i%, j%) / l#
	Next
Next


	xdir = 5
	ydir = 5
	xres = GraphicsWidth()
	yres = GraphicsHeight()
	BounceX = xres/2
	BounceY = yres/2
	
Repeat
	Cls()
	rotateVertices(a#, b#, g#)
	drawSphere(bounceX,bounceY)
	Flip()

	;Mouse Control WOOHOO :D
	b# = b#-MouseXSpeed() Mod 360
	a# = a#-MouseYSpeed() Mod 360
	MoveMouse 512, 384

	;Make it Move! press Q
	If KeyHit(16) move = 1 - move
	If move Then
		bounceX = bounceX + xdir
		bounceY = bounceY + ydir
		If bounceX > xres Then xdir = -5
		If bounceX < 0 Then xdir = 5
		If bounceY > yres Then ydir = -5
		If bounceY < 0 Then ydir = 5
	End If

	
	If KeyDown(30) Then
		a# = a# + 1.00
		While a# > 360.00
			a# = a# - 360.00
		Wend
	EndIf
	If KeyDown(44) Then
		a# = a# - 1.00
		While a# < 0.00
			a# = a# + 360.00
		Wend
	EndIf
	If KeyDown(31) Then
		b# = b# + 1.00
		While b# > 360.00
			b# = b# - 360.00
		Wend
	EndIf
	If KeyDown(45) Then
		b# = b# - 1.00
		While b# < 0.00
			b# = b# + 360.00
		Wend
	EndIf
	If KeyDown(32) Then
		g# = g# + 1.00
		While g# > 360.00
			g# = g# - 360.00
		Wend
	EndIf
	If KeyDown(46) Then
		g# = g# - 1.00
		While g# < 0.00
			g# = g# + 360.00
		Wend
	EndIf
	If KeyDown(33) Then
		lx# = lx# - 0.03125
		While lx# < 0.00
			lx# = lx# + 1.00
		Wend
	EndIf
	If KeyDown(47) Then
		lx# = lx# + 0.03125
		While lx# > 1.00
			lx# = lx# - 1.00
		Wend
	EndIf
	If KeyDown(34) Then
		ly# = ly# - 0.03125
		While ly# < 0.00
			ly# = ly# + 1.00
		Wend
	EndIf
	If KeyDown(48) Then
		ly# = ly# + 0.03125
		While ly# > 1.00
			ly# = ly# - 1.00
		Wend
	EndIf
	If KeyDown(35) Then
		lz# = lz# - 0.03125
		While lz# < 0.00
			lz# = lz# + 1.00
		Wend
	EndIf
	If KeyDown(49) Then
		lz# = lz# + 0.03125
		While lz# > 1.00
			lz# = lz# - 1.00
		Wend
	EndIf
Until KeyHit(1)
End





Function rotateVertices(alpha#, betha#, gamma#) 
	For i% = 0 To 15 
		For j% = 0 To 8
		
			;Vertices
			xl0# = x#(i%, j%) 
			yl0# = y#(i%, j%) 
			zl0# = z#(i%, j%) 
			xl1# = (Sin#(betha#) * zl0#) + (Cos#(betha#) * xl0#) 
			yl1# = yl0# 
			zl1# = (Cos#(betha#) * zl0#) - (Sin#(betha#) * xl0#) 
			xl2# = xl1# 
			yl2# = yl1# * Cos#(alpha#) - zl1# * Sin#(alpha#) 
			zl2# = yl1# * Sin#(alpha#) + zl1# * Cos#(alpha#) 
			rx#(i%, j%) = yl2# * Sin#(gamma#) + xl2# * Cos#(gamma#) 
			ry#(i%, j%) = yl2# * Cos#(gamma#) - xl2# * Sin#(gamma#) 
			rz#(i%, j%) = zl2#

			;Normals
			xl0# = nx#(i%, j%) 
			yl0# = ny#(i%, j%) 
			zl0# = nz#(i%, j%) 
			xl1# = zl0# * Sin#(betha#) + xl0# * Cos#(betha#) 
			yl1# = yl0# 
			zl1# = zl0# * Cos#(betha#) - xl0# * Sin#(betha#) 
			xl2# = xl1#

			;+ - is Oppisite of the Vertices - +, looks like it doesn't matter which is set with + - just as long as the other is oppisite of it - +
			; Its this oppisite sign change that actually makes it work, put it back to the same as the other one
			; - + and see how its messed up :P
			yl2# = yl1# * Cos#(alpha#) + zl1# * Sin#(alpha#) 
			zl2# = yl1# * Sin#(alpha#) - zl1# * Cos#(alpha#)
			;Main Change, Sign Change

				
			rnx#(i%, j%) = yl2# * Sin#(gamma#) + xl2# * Cos#(gamma#) 
			rny#(i%, j%) = yl2# * Cos#(gamma#) - xl2# * Sin#(gamma#) 
			rnz#(i%, j%) = zl2#
		Next
	Next
End Function 



Function drawSphere(xloc, yloc)
	For i% = 0 To 15
		For j% = 0 To 7
			x0# = +rx#(i%, j%) * 100.00 + xloc ;512.00
			y0# = -ry#(i%, j%) * 100.00 + yloc ;384.00
			x1# = +rx#((i% + 1) Mod 16, j%) * 100.00 + xloc ;512.00
			y1# = -ry#((i% + 1) Mod 16, j%) * 100.00 + yloc ;384.00
			x2# = +rx#((i% + 1) Mod 16, (j% + 1) Mod 9) * 100.00 + xloc ;512.00
			y2# = -ry#((i% + 1) Mod 16, (j% + 1) Mod 9) * 100.00 + yloc ;384.00
			x3# = +rx#(i%, (j% + 1) Mod 9) * 100.00 + xloc ;512.00
			y3# = -ry#(i%, (j% + 1) Mod 9) * 100.00 + yloc ;384.00
			If rnz#(i%, j%) > 0.00 Then
				c% = (((rnx#(i%, j%) * lx#) + (rny#(i%, j%) * ly#) + (rnz#(i%, j%) * lz#)) / 1.00) * 255
				If c% > 255 Then
					c% = 255
				Else
					If c% < 15 Then
						c% = 15
					EndIf
				EndIf
				c% = (c% Shl 16)
				paintTriangle(x0#, y0#, x1#, y1#, x3#, y3#, c%)
				paintTriangle(x1#, y1#, x2#, y2#, x3#, y3#, c%)
			EndIf
		Next
	Next
End Function



Function paintTriangle(x0#, y0#, x1#, y1#, x2#, y2#, c%)
    minx# = 9999
    maxx# = 0
    miny# = 9999
    maxy# = 0
	;
	If x0# < minx# Then minx# = x0#
	If x0# > maxx# Then maxx# = x0#
	If x1# < minx# Then minx# = x1#
	If x1# > maxx# Then maxx# = x1#
	If x2# < minx# Then minx# = x2#
	If x2# > maxx# Then maxx# = x2#
	If y0# < miny# Then miny# = y0#
	If y0# > maxy# Then maxy# = y0#
	If y1# < miny# Then miny# = y1#
	If y1# > maxy# Then maxy# = y1#
	If y2# < miny# Then miny# = y2#
	If y2# > maxy# Then maxy# = y2#
	;
	xsize# = maxx# - minx#
	ysize# = maxy# - miny#
	;
	x0# = x0# - minx#
	x1# = x1# - minx#
	x2# = x2# - minx#
	y0# = y0# - miny#
	y1# = y1# - miny#
	y2# = y2# - miny#
	;
	For i% = 0 To xsize#
		For j% = 0 To ysize#
			polyhedre%(i%, j%) = 0
		Next
	Next
	;
	drawBresenhamLine(x0#, y0#, x1#, y1#)
	drawBresenhamLine(x1#, y1#, x2#, y2#)
	drawBresenhamLine(x2#, y2#, x0#, y0#)
	;
	For j% = 0 To ysize#
		For i% = 0 To xsize#
			If polyhedre%(i%, j%) Then
				paintArray%(j%, 0) = i%
				Exit
			EndIf
		Next
		For i% = xsize# To 0 Step -1
			If polyhedre%(i%, j%) Then
				paintArray%(j%, 1) = i%
				Exit
			EndIf
		Next
	Next
	;
	Color (c% Shr 16), (c% Shr 8) And 255, c% And 255
	;
	For i% = 0 To ySize#
		Line minx# + paintArray%(i%, 0), miny# + i%, minx# + paintArray%(i%, 1), miny# + i%
	Next
End Function



Function drawBresenhamLine(x0%, y0%, x1%, y1%)
	If x0% = x1% Then
		If y0% = y1% Then
			polyhedre%(x0%, y0%) = 1
			Return
		EndIf
		If y0% < y1% Then
			For i% = y0% To y1%
				polyhedre%(x0%, i%) = 1
			Next
			Return
		EndIf
		For i% = y1% To y0%
			polyhedre%(x0%, i%) = 1
		Next
		Return
	EndIf
	If y0% = y1% Then
		If x0% < x1% Then
			For i% = x0% To x1%
				polyhedre%(i%, y0%) = 1
			Next
			Return
		EndIf
		For i% = x1% To x0%
			polyhedre%(i%, y0%) = 1
		Next
		Return
	EndIf
	If y1% < y0% Then
		temp% = y0%
		y0% = y1%
		y1% = temp%
		temp% = x0%
		x0% = x1%
		x1% = temp%
	EndIf
	dx% = x1% - x0%
	If dx% < 0 Then
		dx% = -dx%
		xinc% = -1
	Else
		xinc% = 1
	EndIf
	dy% = y1% - y0%
	If dy% < 0 Then
		dy% = -dy%
		yinc% = -1
	Else
		yinc% = 1
	EndIf
	two_dx% = dx% + dx%
	two_dy% = dy% + dy%
	xx% = x0%
	yy% = y0%
	If dx% > dy% Then
		error% = 0
		For i% = 0 To dx%
			polyhedre%(xx%, yy%) = 1
			xx% = xx% + xinc%
			error% = error% + two_dy%
			If error% > dx% Then
				error% = error% - two_dx%
				yy% = yy% + yinc%
			EndIf
		Next
	Else
		error% = 0
		For i% = 0 To dy%
			polyhedre%(xx%, yy%) = 1
			yy% = yy% + yinc%
			error% = error% + two_dx%
			If error% > dy% Then
				error% = error% - two_dy%
				xx% = xx% + xinc%
			EndIf
		Next
	EndIf
End Function

Paradox7

(Posted 2003) [#23]

Oh, just to note, i never come into this forum, why would I, i'm not even a newbie to 3d programming, i'm below that :P so why come into the Advance 3D, anyways, I first saw your little program in the
http://www.blitzbasic.com/bbs/posts.php?topic=26491

post, where you complimenting halo, I had first fixed it there, just by that simple, change sign on Only one or the other, and it worked. So I went looking for your post in here, as you said you posted in here, so I can see if you found a solution yet, and so I found your updated version. I applied the changes, including it seems you need both vertices and normals, not combined, and other little modifications. Hope it helps ya :)

P.S. I have no clue wtf a normal or vertice is :P

3DBuzzFan

(Posted 2003) [#24]

Here´s a list of all simplifications that can be applyied to the algorythm:

1. There is only ONE polygon object, the normal´s sphere.
2. Its radius is 1.00.
3. Its center point is always located at the world origin, (0.00, 0.00, 0.00).
4. The sphere has a total of 144 polygons.
Of those, 32 are triangles and 112 are quadrangles.
6. If it allows for more optimization, all faces can be handled as triangles, so the sphere is actualy a collection of 144 triangles.
7. The sphere is only drawn in order to check the correctness of the backface culling and lighting. But, in the voxel engine, it is never actualy drawn.
8. The viewing vector is always (0.00, 0.00, 1.00).
There is no camera vector at all. Al changes in the camera position and/or rotation are achieved by moving/scalling/rotating the voxel objects, not the cammera.
9. A voxel original normal is stored as an 8 bit value, holding only two angles, Alpha and betha.
This 8 bits value indexes a table, which has 144 entries, and returns the 3 components of the normal (nx#, ny#, nz#).

a% = int(floor#(Alpha# / 22.50)
b% = int(floor#(Betha# / 22.50)
If (a% > 4) And (a% < 12) Then
a% = (8 - al%) And $0f
b% = be% Xor $08
EndIf

The gamma# is not needed, because these are just the ORIGINAL normals, meaning that no rotation has been applied to them.
I chose to use alpha# and betha# as the indice, just because it is easier to remember, but the normal indices are not required to be related to any angle at all.
(i just did it this way because it makes it easy to find the angle I want in that big orange I have, with the needles stuck in it).

I hope this inromation helps.
Hey, Col... I don´t mean to bother you, but you know 3d maths and I appreciate your help.

I, on the other hand, am not comfortable with normals, dot products, etc...
So, if you can help me get any further...
Thanks a lot,

Rui Barbosa Jr.

Paradox7

(Posted 2003) [#25]

wow, you posted at the same time I did, this only a bump, incase you don't look above your last post, thinking nobody posted before your last post, and you just scroll all the way down and past my post, looking for new replys.

3DBuzzFan

(Posted 2003) [#26]

Here´s another thing I´d like to share about the vboxel character engine...

I have created a cirtual machine, from the ground up, which allows for creating scripts that allow the user to create the AI for NPC´s.
I have also created a compiler and a debugger.

Alright, voxels don´t seem to be a nice technology anylonger, right?
I mean, with all those fancy 3d cards, capable of drawing millions of polyfgons per second...
But hey, voxels still can play a part in 3d games, as long as some people keep trying to get things done with voxels.

So, any help is welcome.
Thank you guys,

Rui Barbosa Jr.

3DBuzzFan

(Posted 2003) [#27]

The voxel engine has its own scripting language.
I have written the IDE, the compiler and the debugger in BlitzPlus, which by the way, I like a lot.

The cirtual machine was written in gcc, because I needed to port it to PS2 ans Linux.

Rui Barbosa Jr.

Paradox7

(Posted 2003) [#28]

you see the perfect culling on the sphere?

3DBuzzFan

(Posted 2003) [#29]

I am orry, paradox.
But I did not find your code.
I will try it immediately.
Please let me know wher I can find it.
Thanks,

Rui Barbosa Jr.

3DBuzzFan

(Posted 2003) [#30]

Ho... I got it.
Sorry...
It really happened that way...
You did post at the same time as I did... and I did not check the posts prior to my last post.
One mustake I wll try not to make again.
Thanks.
I will run your version now.

Rui Barbosa Jr.

3DBuzzFan

(Posted 2003) [#31]

Hi.
Just tryied it.
It works very well!

There is still a minor problem: when I rotate around the Z axis, the lighting doesn´t show properly.
Backface culling is 100% fine, now.

Now, if we get the the rotation around the Z axis working, then everything is gonna be perfect!

So, as I do not know wxactly what´s going on in the code, please help me get this one last thing out of the way. Please? oh, pleeeeeeease!

Thanks a lot,

Rui Barbosa Jr.

3DBuzzFan

(Posted 2003) [#32]

Hi guys.
Col, did you try the last version?
Do you think you can figure out what is wrong with the rotation around the Z axis?
I tryied myself, but I just don´t understand it well enough in order to find out.
Paradox7?
Andy?
Anyone?

Cheers,

Rui Barbosa Jr.

3DBuzzFan

(Posted 2003) [#33]

Hi guys.
I took a closer look at the code.
Have re-checked my sketches.
Its is now working fine.
Once again, it was just a matter of wrong signs.
Now, backface culling is 100% correct, as well as lighting.
It all failed in the first version, bacause I have defined the polygons using clock-wise order.
But all calculations were taking place based on counter-clock wise order of vertices - which is the most used standard.
So, my normals where all pointing inwads, instead of outwards.
I have done as paradox7, have changed the signs and it all works fine now.

Well, at least that is what I think.
Please, correct me if I am wrong.

Btw: Here is the latest code:

[CODE]
Dim polyhedre%(256, 256)
Dim paintArray%(256, 2)
;
Dim x#(16, 9)
Dim y#(16, 9)
Dim z#(16, 9)
;
Dim rx#(16, 9)
Dim ry#(16, 9)
Dim rz#(16, 9)
;
Dim nx#(16, 9)
Dim ny#(16, 9)
Dim nz#(16, 9)
;
Dim rnx#(16, 9)
Dim rny#(16, 9)
Dim rnz#(16, 9)
;
Global a# = 0.00
Global b# = 0.00
Global g# = 0.00
;
Global lx# = 1.00
Global ly# = 1.00
Global lz# = 1.00

Graphics 1024, 768, 16, 1
SetBuffer BackBuffer()
ClsColor 255, 128, 64

For i% = 0 To 15
For j% = 0 To 8
r# = Sin#(22.50 * j%)
x#(i%, j%) = Cos#(22.50 * i%) * r#
y#(i%, j%) = Cos#(22.50 * j%)
z#(i%, j%) = Sin#(22.50 * i%) * r#
Next
Next

For i% = 0 To 15
For j% = 0 To 8
x0# = +x#(i%, j%)
y0# = -y#(i%, j%)
z0# = +z#(i%, j%)
x1# = +x#((i% + 1) Mod 16, j%)
y1# = -y#((i% + 1) Mod 16, j%)
z1# = +z#((i% + 1) Mod 16, j%)
x2# = +x#((i% + 1) Mod 16, (j% + 1) Mod 9)
y2# = -y#((i% + 1) Mod 16, (j% + 1) Mod 9)
z2# = +z#((i% + 1) Mod 16, (j% + 1) Mod 9)
x3# = +x#(i%, (j% + 1) Mod 9)
y3# = -y#(i%, (j% + 1) Mod 9)
z3# = +z#(i%, (j% + 1) Mod 9)
If Abs(x2# - x3#) < 0.001 Then
dx1# = x2# - x0#
dy1# = y2# - y0#
dz1# = z2# - z0#
dx2# = x2# - x1#
dy2# = y2# - y1#
dz2# = z2# - z1#
Else
dx1# = x3# - x1#
dy1# = y3# - y1#
dz1# = z3# - z1#
dx2# = x3# - x2#
dy2# = y3# - y2#
dz2# = z3# - z2#
EndIf
nx#(i%, j%) = (dy1# * dz2#) - (dz1# * dy2#)
ny#(i%, j%) = (dz1# * dx2#) - (dx1# * dz2#)
nz#(i%, j%) = (dx1# * dy2#) - (dy1# * dx2#)
l# = Sqr#((nx#(i%, j%) * nx#(i%, j%)) + (ny#(i%, j%) * ny#(i%, j%)) + (nz#(i%, j%) * nz#(i%, j%)))
nx#(i%, j%) = nx#(i%, j%) / l#
ny#(i%, j%) = ny#(i%, j%) / l#
nz#(i%, j%) = nz#(i%, j%) / l#
Next
Next

xdir = 5
ydir = 5
xres = GraphicsWidth()
yres = GraphicsHeight()
BounceX = xres/2
BounceY = yres/2

Repeat
Cls()
rotateVertices(a#, b#, g#)
drawSphere(bounceX,bounceY)
Flip()
;Mouse Control WOOHOO :D
b# = b#-MouseXSpeed() Mod 360
a# = a#-MouseYSpeed() Mod 360
MoveMouse 512, 384
;Make it Move! press Q
If KeyHit(16) move = 1 - move
If move Then
bounceX = bounceX + xdir
bounceY = bounceY + ydir
If bounceX > xres Then xdir = -5
If bounceX < 0 Then xdir = 5
If bounceY > yres Then ydir = -5
If bounceY < 0 Then ydir = 5
End If

If KeyDown(30) Then
a# = a# + 1.00
While a# > 360.00
a# = a# - 360.00
Wend
EndIf
If KeyDown(44) Then
a# = a# - 1.00
While a# < 0.00
a# = a# + 360.00
Wend
EndIf
If KeyDown(31) Then
b# = b# + 1.00
While b# > 360.00
b# = b# - 360.00
Wend
EndIf
If KeyDown(45) Then
b# = b# - 1.00
While b# < 0.00
b# = b# + 360.00
Wend
EndIf
If KeyDown(32) Then
g# = g# + 1.00
While g# > 360.00
g# = g# - 360.00
Wend
EndIf
If KeyDown(46) Then
g# = g# - 1.00
While g# < 0.00
g# = g# + 360.00
Wend
EndIf
If KeyDown(33) Then
lx# = lx# - 0.03125
While lx# < 0.00
lx# = lx# + 1.00
Wend
EndIf
If KeyDown(47) Then
lx# = lx# + 0.03125
While lx# > 1.00
lx# = lx# - 1.00
Wend
EndIf
If KeyDown(34) Then
ly# = ly# - 0.03125
While ly# < 0.00
ly# = ly# + 1.00
Wend
EndIf
If KeyDown(48) Then
ly# = ly# + 0.03125
While ly# > 1.00
ly# = ly# - 1.00
Wend
EndIf
If KeyDown(35) Then
lz# = lz# - 0.03125
While lz# < 0.00
lz# = lz# + 1.00
Wend
EndIf
If KeyDown(49) Then
lz# = lz# + 0.03125
While lz# > 1.00
lz# = lz# - 1.00
Wend
EndIf
Until KeyHit(1)
End

Function rotateVertices(alpha#, betha#, gamma#)
For i% = 0 To 15
For j% = 0 To 8

;Vertices
xl0# = x#(i%, j%)
yl0# = y#(i%, j%)
zl0# = z#(i%, j%)
xl1# = (Sin#(betha#) * zl0#) + (Cos#(betha#) * xl0#)
yl1# = yl0#
zl1# = (Cos#(betha#) * zl0#) - (Sin#(betha#) * xl0#)
xl2# = xl1#
yl2# = yl1# * Cos#(alpha#) - zl1# * Sin#(alpha#)
zl2# = yl1# * Sin#(alpha#) + zl1# * Cos#(alpha#)
rx#(i%, j%) = yl2# * Sin#(gamma#) + xl2# * Cos#(gamma#)
ry#(i%, j%) = yl2# * Cos#(gamma#) - xl2# * Sin#(gamma#)
rz#(i%, j%) = zl2#

;Normals
xl0# = nx#(i%, j%)
yl0# = ny#(i%, j%)
zl0# = nz#(i%, j%)
xl1# = zl0# * Sin#(betha#) + xl0# * Cos#(betha#)
yl1# = yl0#
zl1# = zl0# * Cos#(betha#) - xl0# * Sin#(betha#)
xl2# = xl1#

;+ - is Oppisite of the Vertices - +, looks like it doesn't matter which is set with + - just as long as the other is oppisite of it - +
; Its this oppisite sign change that actually makes it work, put it back to the same as the other one
; - + and see how its messed up :P
yl2# = yl1# * Cos#(alpha#) + zl1# * Sin#(alpha#)
zl2# = yl1# * Sin#(alpha#) - zl1# * Cos#(alpha#)
;Main Change, Sign Change
rnx#(i%, j%) = yl2# * Sin#(gamma#) - xl2# * Cos#(gamma#)
rny#(i%, j%) = yl2# * Cos#(gamma#) + xl2# * Sin#(gamma#)
rnz#(i%, j%) = zl2#
Next
Next
End Function

Function drawSphere(xloc, yloc)
For i% = 0 To 15
For j% = 0 To 7
x0# = +rx#(i%, j%) * 100.00 + xloc ;512.00
y0# = -ry#(i%, j%) * 100.00 + yloc ;384.00
x1# = +rx#((i% + 1) Mod 16, j%) * 100.00 + xloc ;512.00
y1# = -ry#((i% + 1) Mod 16, j%) * 100.00 + yloc ;384.00
x2# = +rx#((i% + 1) Mod 16, (j% + 1) Mod 9) * 100.00 + xloc ;512.00
y2# = -ry#((i% + 1) Mod 16, (j% + 1) Mod 9) * 100.00 + yloc ;384.00
x3# = +rx#(i%, (j% + 1) Mod 9) * 100.00 + xloc ;512.00
y3# = -ry#(i%, (j% + 1) Mod 9) * 100.00 + yloc ;384.00
If rnz#(i%, j%) > 0.00 Then
c% = (((rnx#(i%, j%) * lx#) + (rny#(i%, j%) * ly#) + (rnz#(i%, j%) * lz#)) / 1.00) * 255
If c% > 255 Then
c% = 255
Else
If c% < 15 Then
c% = 15
EndIf
EndIf
c% = (c% Shl 16)
paintTriangle(x0#, y0#, x1#, y1#, x3#, y3#, c%)
paintTriangle(x1#, y1#, x2#, y2#, x3#, y3#, c%)
EndIf
Next
Next
End Function

Function paintTriangle(x0#, y0#, x1#, y1#, x2#, y2#, c%)
; Color (c% Shr 16), (c% Shr 8) And 255, c% And 255
; Line x0#, y0#, x1#, y1#
; Line x1#, y1#, x2#, y2#
; Line x2#, y2#, x0#, y0#
; Return

minx# = 9999
maxx# = 0
miny# = 9999
maxy# = 0
;
If x0# < minx# Then minx# = x0#
If x0# > maxx# Then maxx# = x0#
If x1# < minx# Then minx# = x1#
If x1# > maxx# Then maxx# = x1#
If x2# < minx# Then minx# = x2#
If x2# > maxx# Then maxx# = x2#
If y0# < miny# Then miny# = y0#
If y0# > maxy# Then maxy# = y0#
If y1# < miny# Then miny# = y1#
If y1# > maxy# Then maxy# = y1#
If y2# < miny# Then miny# = y2#
If y2# > maxy# Then maxy# = y2#
;
xsize# = maxx# - minx#
ysize# = maxy# - miny#
;
x0# = x0# - minx#
x1# = x1# - minx#
x2# = x2# - minx#
y0# = y0# - miny#
y1# = y1# - miny#
y2# = y2# - miny#
;
For i% = 0 To xsize#
For j% = 0 To ysize#
polyhedre%(i%, j%) = 0
Next
Next
;
drawBresenhamLine(x0#, y0#, x1#, y1#)
drawBresenhamLine(x1#, y1#, x2#, y2#)
drawBresenhamLine(x2#, y2#, x0#, y0#)
;
For j% = 0 To ysize#
For i% = 0 To xsize#
If polyhedre%(i%, j%) Then
paintArray%(j%, 0) = i%
Exit
EndIf
Next
For i% = xsize# To 0 Step -1
If polyhedre%(i%, j%) Then
paintArray%(j%, 1) = i%
Exit
EndIf
Next
Next
;
Color (c% Shr 16), (c% Shr 8) And 255, c% And 255
;
For i% = 0 To ySize#
Line minx# + paintArray%(i%, 0), miny# + i%, minx# + paintArray%(i%, 1), miny# + i%
Next
End Function

Function drawBresenhamLine(x0%, y0%, x1%, y1%)
If x0% = x1% Then
If y0% = y1% Then
polyhedre%(x0%, y0%) = 1
Return
EndIf
If y0% < y1% Then
For i% = y0% To y1%
polyhedre%(x0%, i%) = 1
Next
Return
EndIf
For i% = y1% To y0%
polyhedre%(x0%, i%) = 1
Next
Return
EndIf
If y0% = y1% Then
If x0% < x1% Then
For i% = x0% To x1%
polyhedre%(i%, y0%) = 1
Next
Return
EndIf
For i% = x1% To x0%
polyhedre%(i%, y0%) = 1
Next
Return
EndIf
If y1% < y0% Then
temp% = y0%
y0% = y1%
y1% = temp%
temp% = x0%
x0% = x1%
x1% = temp%
EndIf
dx% = x1% - x0%
If dx% < 0 Then
dx% = -dx%
xinc% = -1
Else
xinc% = 1
EndIf
dy% = y1% - y0%
If dy% < 0 Then
dy% = -dy%
yinc% = -1
Else
yinc% = 1
EndIf
two_dx% = dx% + dx%
two_dy% = dy% + dy%
xx% = x0%
yy% = y0%
If dx% > dy% Then
error% = 0
For i% = 0 To dx%
polyhedre%(xx%, yy%) = 1
xx% = xx% + xinc%
error% = error% + two_dy%
If error% > dx% Then
error% = error% - two_dx%
yy% = yy% + yinc%
EndIf
Next
Else
error% = 0
For i% = 0 To dy%
polyhedre%(xx%, yy%) = 1
yy% = yy% + yinc%
error% = error% + two_dx%
If error% > dy% Then
error% = error% - two_dy%
xx% = xx% + xinc%
EndIf
Next
EndIf
End Function
[/CODE]

Thanks a lot, guys.

Rui Barbosa Jr.

3DBuzzFan

(Posted 2003) [#34]

And here is the next big challenge:

Now, I need to find a way to rotate the normals without using floats or multiplies, etc...

Here´s how I am planning on doing that:

Create a (big) table, which, based on the three rotation angles, and the thre original rotation angles, will give me the final rotation angles.
This table might become huge.
It is targetted at the PS2, and I do not have much RAM available, so this may not be easy to do... and may not be doable, in the worst case.

It would be like having all possible rotations in a pre-computed table.

So,
(Alpha0, Betha0, Gamma0, DeltaAlpha, DeltaBetha, DeltaGamma)
would index a table, which would return
(finalAlpha, finalBetha, finalGamma)

Of corse, it is not that easy.
Such a table would not be just big... it would be enormous.
(A few billion Megs of spare RAM hehehe).

Fortunately, this can be broken down into three tables:

a)Indexed by:
(Alpha, Betha, Gamma, DeltaAlpha)
And Returns:
(FinalAlpha, FinalBetha, FinalGamma)

b)Indexed by:
(Alpha, Betha, Gamma, DeltaBetha)
And Returns:
(FinalAlpha, FinalBetha, FinalGamma)

c)Indexed by:
(Alpha, Betha, Gamma, DeltaGamma)
And Returns:
(FinalAlpha, FnalBetha, FinalGamma)

Each one would be no more than 16 thousand megabytes long, for 1 degree precision heheheh

Now, some smart trickery will ome into play.
First, there´s no need to store the complete sphere, but just 1/8th of it.
So, that would be just 2 thousand Megabytes for each table.
For a total of 6 Gigabytes!

Hehe... too bad I only have 32Mbytes on the PS2... only 10Mb of which is still available.

I will have to come up with some real smart technique, because I may not use more than 8 mbytes.
But, on the other hand, some sort of pre-computed table will be needed, for rotating the normals is a very costly operation.

Now, I will have to start think about that...

Any ideas?

Thanks,

Rui Barbosa Jr.

col	(Posted 2003) [#35]

Much better. You have a made a vast improvement. Well done.

Where can I find you other work? website maybe?

I'm beginning to have an interest in ps2 code.

3DBuzzFan

(Posted 2003) [#36]

Hi Col.
I have a linux for playstation kit.
That´s pretty much all that you need in order to get the thingy going.
The best thing is that it is competely open and official.
It is sold by Sony Entertainement, itself.
All of the manuals are original, from Sony.
If you are in the U.S., you can buy the kit for US$ 200.00.

Here is the OFFICIAL url:

http://playstation2-linux.com

3DBuzzFan

(Posted 2003) [#37]

Before writting code for the PS2 itself, I test all of my algorythms in Blitz Plus.
I can´t find words to tell you how much I appreciate Blitz Plus.

I wish there was a blitz plus compiler for the PS2.
(Sigh...)

For the PS2, I use gcc, as I told before.
Also, there´s PS2SDL, which is much like SDL, but specifically targetted at the PS2.
There´s also a very nice assembler, but I try to stay away from coding directly to the Emotion Engine CPU.

All of the voxel code is written in pure C.
Lighting will probably require some hand-crafted assembly routines, if I don´t find a way to express rotations as simple the summation of the rotation angles, thou.

Rui Barbosa Jr.

3DBuzzFan

(Posted 2003) [#38]

And here is a much better version.
It is much faster than the previous one.
Actualy, what I did here was to convert the polygon painting code I have written in gcc to its equivalent Blitz Plus code.
And I am glad I dd that.
It is actualy fater than I thougt it would be in B+.

[CODE]
Dim polyhedre%(256, 256)
Dim paintArray%(256, 2)
;
Dim x#(16, 9)
Dim y#(16, 9)
Dim z#(16, 9)
;
Dim rx#(16, 9)
Dim ry#(16, 9)
Dim rz#(16, 9)
;
Dim nx#(16, 9)
Dim ny#(16, 9)
Dim nz#(16, 9)
;
Dim rnx#(16, 9)
Dim rny#(16, 9)
Dim rnz#(16, 9)
;
Global a# = 0.00
Global b# = 0.00
Global g# = 0.00
;
Global lx# = 1.00
Global ly# = 1.00
Global lz# = 1.00
;
Global wireFrame = False

Graphics 1024, 768, 32, 0
SetBuffer BackBuffer()
ClsColor 255, 128, 64

For i% = 0 To 15
For j% = 0 To 8
r# = Sin#(22.50 * j%)
x#(i%, j%) = Cos#(22.50 * i%) * r#
y#(i%, j%) = Cos#(22.50 * j%)
z#(i%, j%) = Sin#(22.50 * i%) * r#
Next
Next

For i% = 0 To 15
For j% = 0 To 8
x0# = +x#(i%, j%)
y0# = -y#(i%, j%)
z0# = +z#(i%, j%)
x1# = +x#((i% + 1) Mod 16, j%)
y1# = -y#((i% + 1) Mod 16, j%)
z1# = +z#((i% + 1) Mod 16, j%)
x2# = +x#((i% + 1) Mod 16, (j% + 1) Mod 9)
y2# = -y#((i% + 1) Mod 16, (j% + 1) Mod 9)
z2# = +z#((i% + 1) Mod 16, (j% + 1) Mod 9)
x3# = +x#(i%, (j% + 1) Mod 9)
y3# = -y#(i%, (j% + 1) Mod 9)
z3# = +z#(i%, (j% + 1) Mod 9)
If Abs(x2# - x3#) < 0.001 Then
dx1# = x2# - x0#
dy1# = y2# - y0#
dz1# = z2# - z0#
dx2# = x2# - x1#
dy2# = y2# - y1#
dz2# = z2# - z1#
Else
dx1# = x3# - x1#
dy1# = y3# - y1#
dz1# = z3# - z1#
dx2# = x3# - x2#
dy2# = y3# - y2#
dz2# = z3# - z2#
EndIf
nx#(i%, j%) = (dy1# * dz2#) - (dz1# * dy2#)
ny#(i%, j%) = (dz1# * dx2#) - (dx1# * dz2#)
nz#(i%, j%) = (dx1# * dy2#) - (dy1# * dx2#)
l# = Sqr#((nx#(i%, j%) * nx#(i%, j%)) + (ny#(i%, j%) * ny#(i%, j%)) + (nz#(i%, j%) * nz#(i%, j%)))
nx#(i%, j%) = nx#(i%, j%) / l#
ny#(i%, j%) = ny#(i%, j%) / l#
nz#(i%, j%) = nz#(i%, j%) / l#
Next
Next

xdir = 5
ydir = 5
xres = GraphicsWidth()
yres = GraphicsHeight()
BounceX = xres/2
BounceY = yres/2

Repeat
Cls()
rotateVertices(a#, b#, g#)
drawSphere(bounceX,bounceY)
Flip()
;Mouse Control WOOHOO :D
b# = b#-MouseXSpeed() Mod 360
a# = a#-MouseYSpeed() Mod 360
MoveMouse 512, 384
;Make it Move! press Q
If KeyHit(16) move = 1 - move
If move Then
bounceX = bounceX + xdir
bounceY = bounceY + ydir
If bounceX > xres Then xdir = -5
If bounceX < 0 Then xdir = 5
If bounceY > yres Then ydir = -5
If bounceY < 0 Then ydir = 5
End If

If KeyDown(30) Then
a# = a# + 1.00
While a# > 360.00
a# = a# - 360.00
Wend
EndIf
If KeyDown(44) Then
a# = a# - 1.00
While a# < 0.00
a# = a# + 360.00
Wend
EndIf
If KeyDown(31) Then
b# = b# + 1.00
While b# > 360.00
b# = b# - 360.00
Wend
EndIf
If KeyDown(45) Then
b# = b# - 1.00
While b# < 0.00
b# = b# + 360.00
Wend
EndIf
If KeyDown(32) Then
g# = g# + 1.00
While g# > 360.00
g# = g# - 360.00
Wend
EndIf
If KeyDown(46) Then
g# = g# - 1.00
While g# < 0.00
g# = g# + 360.00
Wend
EndIf
If KeyDown(33) Then
lx# = lx# - 0.03125
While lx# < 0.00
lx# = lx# + 1.00
Wend
EndIf
If KeyDown(47) Then
lx# = lx# + 0.03125
While lx# > 1.00
lx# = lx# - 1.00
Wend
EndIf
If KeyDown(34) Then
ly# = ly# - 0.03125
While ly# < 0.00
ly# = ly# + 1.00
Wend
EndIf
If KeyDown(48) Then
ly# = ly# + 0.03125
While ly# > 1.00
ly# = ly# - 1.00
Wend
EndIf
If KeyDown(35) Then
lz# = lz# - 0.03125
While lz# < 0.00
lz# = lz# + 1.00
Wend
EndIf
If KeyDown(49) Then
lz# = lz# + 0.03125
While lz# > 1.00
lz# = lz# - 1.00
Wend
EndIf
If KeyDown(36) Then
wireFrame = True
EndIf
If KeyDown(50) Then
wireFrame = False
EndIf
Until KeyHit(1)
End

Function rotateVertices(alpha#, betha#, gamma#)
For i% = 0 To 15
For j% = 0 To 8

;Vertices
xl0# = x#(i%, j%)
yl0# = y#(i%, j%)
zl0# = z#(i%, j%)
xl1# = (Sin#(betha#) * zl0#) + (Cos#(betha#) * xl0#)
yl1# = yl0#
zl1# = (Cos#(betha#) * zl0#) - (Sin#(betha#) * xl0#)
xl2# = xl1#
yl2# = yl1# * Cos#(alpha#) - zl1# * Sin#(alpha#)
zl2# = yl1# * Sin#(alpha#) + zl1# * Cos#(alpha#)
rx#(i%, j%) = yl2# * Sin#(gamma#) + xl2# * Cos#(gamma#)
ry#(i%, j%) = yl2# * Cos#(gamma#) - xl2# * Sin#(gamma#)
rz#(i%, j%) = zl2#

;Normals
xl0# = nx#(i%, j%)
yl0# = ny#(i%, j%)
zl0# = nz#(i%, j%)
xl1# = zl0# * Sin#(betha#) + xl0# * Cos#(betha#)
yl1# = yl0#
zl1# = zl0# * Cos#(betha#) - xl0# * Sin#(betha#)
xl2# = xl1#

;+ - is Oppisite of the Vertices - +, looks like it doesn't matter which is set with + - just as long as the other is oppisite of it - +
; Its this oppisite sign change that actually makes it work, put it back to the same as the other one
; - + and see how its messed up :P
yl2# = yl1# * Cos#(alpha#) + zl1# * Sin#(alpha#)
zl2# = yl1# * Sin#(alpha#) - zl1# * Cos#(alpha#)
;Main Change, Sign Change
rnx#(i%, j%) = yl2# * Sin#(gamma#) - xl2# * Cos#(gamma#)
rny#(i%, j%) = yl2# * Cos#(gamma#) + xl2# * Sin#(gamma#)
rnz#(i%, j%) = zl2#
Next
Next
End Function

Function drawSphere(xloc, yloc)
For i% = 0 To 15
For j% = 0 To 7
x0# = +rx#(i%, j%) * 100.00 + xloc ;512.00
y0# = -ry#(i%, j%) * 100.00 + yloc ;384.00
x1# = +rx#((i% + 1) Mod 16, j%) * 100.00 + xloc ;512.00
y1# = -ry#((i% + 1) Mod 16, j%) * 100.00 + yloc ;384.00
x2# = +rx#((i% + 1) Mod 16, (j% + 1) Mod 9) * 100.00 + xloc ;512.00
y2# = -ry#((i% + 1) Mod 16, (j% + 1) Mod 9) * 100.00 + yloc ;384.00
x3# = +rx#(i%, (j% + 1) Mod 9) * 100.00 + xloc ;512.00
y3# = -ry#(i%, (j% + 1) Mod 9) * 100.00 + yloc ;384.00
If rnz#(i%, j%) > 0.00 Then
c% = (((rnx#(i%, j%) * lx#) + (rny#(i%, j%) * ly#) + (rnz#(i%, j%) * lz#)) / 1.00) * 255
If c% > 255 Then
c% = 255
Else
If c% < 15 Then
c% = 15
EndIf
EndIf
c% = (c% Shl 16)
paintTriangle(x0#, y0#, x1#, y1#, x3#, y3#, c%)
paintTriangle(x1#, y1#, x2#, y2#, x3#, y3#, c%)
EndIf
Next
Next
End Function

Function paintTriangle(x0#, y0#, x1#, y1#, x2#, y2#, c%)
If wireFrame Then
Color (c% Shr 16), (c% Shr 8) And 255, c% And 255
Line x0#, y0#, x1#, y1#
Line x1#, y1#, x2#, y2#
Line x2#, y2#, x0#, y0#
Return
EndIf

minx# = 9999
maxx# = 0
miny# = 9999
maxy# = 0
;
If x0# < minx# Then minx# = x0#
If x0# > maxx# Then maxx# = x0#
If x1# < minx# Then minx# = x1#
If x1# > maxx# Then maxx# = x1#
If x2# < minx# Then minx# = x2#
If x2# > maxx# Then maxx# = x2#
If y0# < miny# Then miny# = y0#
If y0# > maxy# Then maxy# = y0#
If y1# < miny# Then miny# = y1#
If y1# > maxy# Then maxy# = y1#
If y2# < miny# Then miny# = y2#
If y2# > maxy# Then maxy# = y2#
;
xsize# = maxx# - minx#
ysize# = maxy# - miny#
;
x0# = x0# - minx#
x1# = x1# - minx#
x2# = x2# - minx#
y0# = y0# - miny#
y1# = y1# - miny#
y2# = y2# - miny#
;
For i% = 0 To xsize#
For j% = 0 To ysize#
polyhedre%(i%, j%) = 0
Next
Next
;
drawBresenhamLine(x0#, y0#, x1#, y1#)
drawBresenhamLine(x1#, y1#, x2#, y2#)
drawBresenhamLine(x2#, y2#, x0#, y0#)
;
For j% = 0 To ysize#
For i% = 0 To xsize#
If polyhedre%(i%, j%) Then
paintArray%(j%, 0) = i%
Exit
EndIf
Next
For i% = xsize# To 0 Step -1
If polyhedre%(i%, j%) Then
paintArray%(j%, 1) = i%
Exit
EndIf
Next
Next
;
LockBuffer
py% = miny#
For i% = 0 To ySize#
px% = paintArray%(i%, 0)
pl% = paintArray%(i%, 1) - px%
px% = px% + minx#
For j% = 0 To pl%
WritePixelFast px%, py%, c%
px% = px% + 1
Next
py% = py% + 1
Next
UnlockBuffer
End Function

Function drawBresenhamLine(x0%, y0%, x1%, y1%)
If x0% = x1% Then
If y0% = y1% Then
polyhedre%(x0%, y0%) = 1
Return
EndIf
If y0% < y1% Then
For i% = y0% To y1%
polyhedre%(x0%, i%) = 1
Next
Return
EndIf
For i% = y1% To y0%
polyhedre%(x0%, i%) = 1
Next
Return
EndIf
If y0% = y1% Then
If x0% < x1% Then
For i% = x0% To x1%
polyhedre%(i%, y0%) = 1
Next
Return
EndIf
For i% = x1% To x0%
polyhedre%(i%, y0%) = 1
Next
Return
EndIf
If y1% < y0% Then
temp% = y0%
y0% = y1%
y1% = temp%
temp% = x0%
x0% = x1%
x1% = temp%
EndIf
dx% = x1% - x0%
If dx% < 0 Then
dx% = -dx%
xinc% = -1
Else
xinc% = 1
EndIf
dy% = y1% - y0%
If dy% < 0 Then
dy% = -dy%
yinc% = -1
Else
yinc% = 1
EndIf
two_dx% = dx% + dx%
two_dy% = dy% + dy%
xx% = x0%
yy% = y0%
If dx% > dy% Then
error% = 0
For i% = 0 To dx%
polyhedre%(xx%, yy%) = 1
xx% = xx% + xinc%
error% = error% + two_dy%
If error% > dx% Then
error% = error% - two_dx%
yy% = yy% + yinc%
EndIf
Next
Else
error% = 0
For i% = 0 To dy%
polyhedre%(xx%, yy%) = 1
yy% = yy% + yinc%
error% = error% + two_dx%
If error% > dy% Then
error% = error% - two_dy%
xx% = xx% + xinc%
EndIf
Next
EndIf
End Function[/CODE]

BTW: Try pressing J to display the wireframe model and M to display it as a flat-shaded sphere.

I know it seems to be no use, ´cause Blitz3D can do that much better.
But it is the algorythms that we are interested in, here, right?

Well, I hope this is useful.

Let me just add the real-time light to the PS2 voxel engine and I will port it to Blitz Plus.
I am not sure wheter it is or isn´t going to be fast enough, but it realy is worth a try.

Besides, I was impressed with the writepixelfast performance. I really was not expecting it...

Cheers,

Rui Barbosa Jr.

Paradox7

(Posted 2003) [#39]

I'm glad I could help in getting the 100% culling down, I just found it funny that I was able to fix the problem with no 3D knowledge and others couldn't :P

The Lighting looks great now also.
Don't forgets about me, a shout out, hehe

I'm just a 2D programmer, I love 2D, and no, not 3D in 2D mind you, just 2D. Bought BlitzBasic when it first came out, Blitz2D, can't even afford BlitzPlus :( ah well, Blitz2D is fun. :D

I ripped out ball movement, as now you're using writepixelfast, and there was no checks to make sure writing was inside screen area, although a easy and quick fix, its just best to take it out, its not needed anyways. So use below code.

Good Luck with your project. And keep us updated.

Dim polyhedre%(256, 256)
Dim paintArray%(256, 2)
;
Dim x#(16, 9)
Dim y#(16, 9)
Dim z#(16, 9)
;
Dim rx#(16, 9)
Dim ry#(16, 9)
Dim rz#(16, 9)
;
Dim nx#(16, 9)
Dim ny#(16, 9)
Dim nz#(16, 9)
;
Dim rnx#(16, 9)
Dim rny#(16, 9)
Dim rnz#(16, 9)
;
Global a# = 0.00
Global b# = 0.00
Global g# = 0.00
;
Global lx# = 1.00
Global ly# = 1.00
Global lz# = 1.00
;
Global wireFrame = False



Graphics 1024, 768, 32, 0
SetBuffer BackBuffer()
ClsColor 255, 128, 64



For i% = 0 To 15
	For	j% = 0 To 8
		r# = Sin#(22.50 * j%)
		x#(i%, j%) = Cos#(22.50 * i%) * r#
		y#(i%, j%) = Cos#(22.50 * j%)
		z#(i%, j%) = Sin#(22.50 * i%) * r#
	Next
Next



For i% = 0 To 15
	For j% = 0 To 8
		x0# = +x#(i%, j%)
		y0# = -y#(i%, j%)
		z0# = +z#(i%, j%)
		x1# = +x#((i% + 1) Mod 16, j%)
		y1# = -y#((i% + 1) Mod 16, j%)
		z1# = +z#((i% + 1) Mod 16, j%)
		x2# = +x#((i% + 1) Mod 16, (j% + 1) Mod 9)
		y2# = -y#((i% + 1) Mod 16, (j% + 1) Mod 9)
		z2# = +z#((i% + 1) Mod 16, (j% + 1) Mod 9)
		x3# = +x#(i%, (j% + 1) Mod 9)
		y3# = -y#(i%, (j% + 1) Mod 9)
		z3# = +z#(i%, (j% + 1) Mod 9)
		If Abs(x2# - x3#) < 0.001 Then
			dx1# = x2# - x0#
			dy1# = y2# - y0#
			dz1# = z2# - z0#
			dx2# = x2# - x1#
			dy2# = y2# - y1#
			dz2# = z2# - z1#
		Else
			dx1# = x3# - x1#
			dy1# = y3# - y1#
			dz1# = z3# - z1#
			dx2# = x3# - x2#
			dy2# = y3# - y2#
			dz2# = z3# - z2#
		EndIf
		nx#(i%, j%) = (dy1# * dz2#) - (dz1# * dy2#)
		ny#(i%, j%) = (dz1# * dx2#) - (dx1# * dz2#)
		nz#(i%, j%) = (dx1# * dy2#) - (dy1# * dx2#)
		l# = Sqr#((nx#(i%, j%) * nx#(i%, j%)) + (ny#(i%, j%) * ny#(i%, j%)) + (nz#(i%, j%) * nz#(i%, j%)))
		nx#(i%, j%) = nx#(i%, j%) / l#
		ny#(i%, j%) = ny#(i%, j%) / l#
		nz#(i%, j%) = nz#(i%, j%) / l#
	Next
Next


	xres = GraphicsWidth()
	yres = GraphicsHeight()
	xhalf = xres/2
	yhalf = yres/2
	


Repeat
	Cls()
	rotateVertices(a#, b#, g#)
	drawSphere(xhalf,yhalf)
	Flip()
	;Mouse Control WOOHOO :D
	b# = b#-MouseXSpeed() Mod 360
	a# = a#-MouseYSpeed() Mod 360
	MoveMouse xhalf, yhalf

	

	If KeyDown(30) Then
		a# = a# + 1.00
		While a# > 360.00
			a# = a# - 360.00
		Wend
	EndIf
	If KeyDown(44) Then
		a# = a# - 1.00
		While a# < 0.00
			a# = a# + 360.00
		Wend
	EndIf
	If KeyDown(31) Then
		b# = b# + 1.00
		While b# > 360.00
			b# = b# - 360.00
		Wend
	EndIf
	If KeyDown(45) Then
		b# = b# - 1.00
		While b# < 0.00
			b# = b# + 360.00
		Wend
	EndIf
	If KeyDown(32) Then
		g# = g# + 1.00
		While g# > 360.00
			g# = g# - 360.00
		Wend
	EndIf
	If KeyDown(46) Then
		g# = g# - 1.00
		While g# < 0.00
			g# = g# + 360.00
		Wend
	EndIf
	If KeyDown(33) Then
		lx# = lx# - 0.03125
		While lx# < 0.00
			lx# = lx# + 1.00
		Wend
	EndIf
	If KeyDown(47) Then
		lx# = lx# + 0.03125
		While lx# > 1.00
			lx# = lx# - 1.00
		Wend
	EndIf
	If KeyDown(34) Then
		ly# = ly# - 0.03125
		While ly# < 0.00
			ly# = ly# + 1.00
		Wend
	EndIf
	If KeyDown(48) Then
		ly# = ly# + 0.03125
		While ly# > 1.00
			ly# = ly# - 1.00
		Wend
	EndIf
	If KeyDown(35) Then
		lz# = lz# - 0.03125
		While lz# < 0.00
			lz# = lz# + 1.00
		Wend
	EndIf
	If KeyDown(49) Then
		lz# = lz# + 0.03125
		While lz# > 1.00
			lz# = lz# - 1.00
		Wend
	EndIf
	If KeyDown(36) Then
		wireFrame = True
	EndIf
	If KeyDown(50) Then
		wireFrame = False
	EndIf
Until KeyHit(1)
End



Function rotateVertices(alpha#, betha#, gamma#) 
	For i% = 0 To 15 
		For j% = 0 To 8
		
			;Vertices
			xl0# = x#(i%, j%) 
			yl0# = y#(i%, j%) 
			zl0# = z#(i%, j%) 
			xl1# = (Sin#(betha#) * zl0#) + (Cos#(betha#) * xl0#) 
			yl1# = yl0# 
			zl1# = (Cos#(betha#) * zl0#) - (Sin#(betha#) * xl0#) 
			xl2# = xl1# 
			yl2# = yl1# * Cos#(alpha#) - zl1# * Sin#(alpha#) 
			zl2# = yl1# * Sin#(alpha#) + zl1# * Cos#(alpha#) 
			rx#(i%, j%) = yl2# * Sin#(gamma#) + xl2# * Cos#(gamma#) 
			ry#(i%, j%) = yl2# * Cos#(gamma#) - xl2# * Sin#(gamma#) 
			rz#(i%, j%) = zl2#

			;Normals
			xl0# = nx#(i%, j%) 
			yl0# = ny#(i%, j%) 
			zl0# = nz#(i%, j%) 
			xl1# = zl0# * Sin#(betha#) + xl0# * Cos#(betha#) 
			yl1# = yl0# 
			zl1# = zl0# * Cos#(betha#) - xl0# * Sin#(betha#) 
			xl2# = xl1#

			;+ - is Oppisite of the Vertices - +, looks like it doesn't matter which is set with + - just as long as the other is oppisite of it - +
			; Its this oppisite sign change that actually makes it work, put it back to the same as the other one
			; - + and see how its messed up :P
			; 100% Culling Fixed By Paradox7 :D
			yl2# = yl1# * Cos#(alpha#) + zl1# * Sin#(alpha#) 
			zl2# = yl1# * Sin#(alpha#) - zl1# * Cos#(alpha#)
			;Main Change, Sign Change
			rnx#(i%, j%) = yl2# * Sin#(gamma#) - xl2# * Cos#(gamma#) 
			rny#(i%, j%) = yl2# * Cos#(gamma#) + xl2# * Sin#(gamma#) 
			rnz#(i%, j%) = zl2#
		Next
	Next
End Function 



Function drawSphere(xloc, yloc)
	For i% = 0 To 15
		For j% = 0 To 7
			x0# = +rx#(i%, j%) * 100.00 + xloc ;512.00
			y0# = -ry#(i%, j%) * 100.00 + yloc ;384.00
			x1# = +rx#((i% + 1) Mod 16, j%) * 100.00 + xloc ;512.00
			y1# = -ry#((i% + 1) Mod 16, j%) * 100.00 + yloc ;384.00
			x2# = +rx#((i% + 1) Mod 16, (j% + 1) Mod 9) * 100.00 + xloc ;512.00
			y2# = -ry#((i% + 1) Mod 16, (j% + 1) Mod 9) * 100.00 + yloc ;384.00
			x3# = +rx#(i%, (j% + 1) Mod 9) * 100.00 + xloc ;512.00
			y3# = -ry#(i%, (j% + 1) Mod 9) * 100.00 + yloc ;384.00
			If rnz#(i%, j%) > 0.00 Then
				c% = (((rnx#(i%, j%) * lx#) + (rny#(i%, j%) * ly#) + (rnz#(i%, j%) * lz#)) / 1.00) * 255
				If c% > 255 Then
					c% = 255
				Else
					If c% < 15 Then
						c% = 15
					EndIf
				EndIf
				c% = (c% Shl 16)
				paintTriangle(x0#, y0#, x1#, y1#, x3#, y3#, c%)
				paintTriangle(x1#, y1#, x2#, y2#, x3#, y3#, c%)
			EndIf
		Next
	Next
End Function



Function paintTriangle(x0#, y0#, x1#, y1#, x2#, y2#, c%)
	If wireFrame Then
		Color (c% Shr 16), (c% Shr 8) And 255, c% And 255
		Line x0#, y0#, x1#, y1#
		Line x1#, y1#, x2#, y2#
		Line x2#, y2#, x0#, y0#
		Return
	EndIf

    minx# = 9999
    maxx# = 0
    miny# = 9999
    maxy# = 0
	;
	If x0# < minx# Then minx# = x0#
	If x0# > maxx# Then maxx# = x0#
	If x1# < minx# Then minx# = x1#
	If x1# > maxx# Then maxx# = x1#
	If x2# < minx# Then minx# = x2#
	If x2# > maxx# Then maxx# = x2#
	If y0# < miny# Then miny# = y0#
	If y0# > maxy# Then maxy# = y0#
	If y1# < miny# Then miny# = y1#
	If y1# > maxy# Then maxy# = y1#
	If y2# < miny# Then miny# = y2#
	If y2# > maxy# Then maxy# = y2#
	;
	xsize# = maxx# - minx#
	ysize# = maxy# - miny#
	;
	x0# = x0# - minx#
	x1# = x1# - minx#
	x2# = x2# - minx#
	y0# = y0# - miny#
	y1# = y1# - miny#
	y2# = y2# - miny#
	;
	For i% = 0 To xsize#
		For j% = 0 To ysize#
			polyhedre%(i%, j%) = 0
		Next
	Next
	;
	drawBresenhamLine(x0#, y0#, x1#, y1#)
	drawBresenhamLine(x1#, y1#, x2#, y2#)
	drawBresenhamLine(x2#, y2#, x0#, y0#)
	;
	For j% = 0 To ysize#
		For i% = 0 To xsize#
			If polyhedre%(i%, j%) Then
				paintArray%(j%, 0) = i%
				Exit
			EndIf
		Next
		For i% = xsize# To 0 Step -1
			If polyhedre%(i%, j%) Then
				paintArray%(j%, 1) = i%
				Exit
			EndIf
		Next
	Next
	;
	LockBuffer
	py% = miny#
	For i% = 0 To ySize#
		px% = paintArray%(i%, 0)
		pl% = paintArray%(i%, 1) - px%
		px% = px% + minx#
		For j% = 0 To pl%
			WritePixelFast px%, py%, c%
			px% = px% + 1
		Next
		py% = py% + 1
	Next
	UnlockBuffer
End Function



Function drawBresenhamLine(x0%, y0%, x1%, y1%)
	If x0% = x1% Then
		If y0% = y1% Then
			polyhedre%(x0%, y0%) = 1
			Return
		EndIf
		If y0% < y1% Then
			For i% = y0% To y1%
				polyhedre%(x0%, i%) = 1
			Next
			Return
		EndIf
		For i% = y1% To y0%
			polyhedre%(x0%, i%) = 1
		Next
		Return
	EndIf
	If y0% = y1% Then
		If x0% < x1% Then
			For i% = x0% To x1%
				polyhedre%(i%, y0%) = 1
			Next
			Return
		EndIf
		For i% = x1% To x0%
			polyhedre%(i%, y0%) = 1
		Next
		Return
	EndIf
	If y1% < y0% Then
		temp% = y0%
		y0% = y1%
		y1% = temp%
		temp% = x0%
		x0% = x1%
		x1% = temp%
	EndIf
	dx% = x1% - x0%
	If dx% < 0 Then
		dx% = -dx%
		xinc% = -1
	Else
		xinc% = 1
	EndIf
	dy% = y1% - y0%
	If dy% < 0 Then
		dy% = -dy%
		yinc% = -1
	Else
		yinc% = 1
	EndIf
	two_dx% = dx% + dx%
	two_dy% = dy% + dy%
	xx% = x0%
	yy% = y0%
	If dx% > dy% Then
		error% = 0
		For i% = 0 To dx%
			polyhedre%(xx%, yy%) = 1
			xx% = xx% + xinc%
			error% = error% + two_dy%
			If error% > dx% Then
				error% = error% - two_dx%
				yy% = yy% + yinc%
			EndIf
		Next
	Else
		error% = 0
		For i% = 0 To dy%
			polyhedre%(xx%, yy%) = 1
			yy% = yy% + yinc%
			error% = error% + two_dx%
			If error% > dy% Then
				error% = error% - two_dy%
				xx% = xx% + xinc%
			EndIf
		Next
	EndIf
End Function

col	(Posted 2003) [#40]

I see what you mean by the sign of the rotations. It does matter a great deal what way you do the math as you are doing is rotating using standard trig with a standard polar system. That is you rotate the vertices around poles (axis).

Keep us informed of your project :)

Nice one Paradox7. A great feeling eh :)

3DBuzzFan

(Posted 2003) [#41]

Hi Guys.

Col, Paradox7, Andy...

Paradox: of course I am very gratefull to you, for pointing me the path of the swapped signs :^).
I am not sure if you really don´t know anything about 3d. If you really don´t, maybe this can help you understand how you helped us: there are two standards employed when writting 3d code: the right-hand rule and the left-hand rule.
Well, I was creating vertices using one standard, and was doing the normals math using the other one.
Vertex math really is not *that* succeptible to that kind of mistake, for wire-frame, or flat-shaded polygons, because we are using a sphere here.
So, what we were looking at, prior to the changes, was the inside of the sphere, not its outside, actualy.
But, as it is a sphere, we were not able to tell the difference.
But with normals, it makes a lot of difference.
Normals are VERY sensitive to signals.
Why is that?
Take a look at how normals are calculated.
You are going to find a sqr() inside of its code.
Well, sqr() for positive numbers have TWO possible answers.
One is positive, and the other one is negative.
But the compiler always returns the positive root.
So, you have to pick the correct signs or, otherwise, you are going to end up pointing your normal to the opposite direction.
Normals should always point outwards, but they were doing the other way around.
Actualy, at some point in time, some of the normal components were correct, whist others were wrong. That may be the reason why I was getting that 12.5 degrees offset, remember?

Now, everything is working fine.
Thanks to you guys.

Well, things are looking good in voxel realm :^).
Let me just finish adding real-time lights to the voxel engine and I will release the source-code.

Initialy, I will release the gcc source-code.
Then, I plan on porting it to BlitzPlus.
I am not promissing that the B+ version will be lightning fast.
It´s not that B+ os not fast enough.
It´s just that the engine was written with C in mind.
I took advantage of many special constructs of the C language.
For one thing, pointers are used all over the place.
I believe that using memory blocks will allow for a speed that will be very close to what I get with C pointers, but am not sure about how they are implemented.
I am sure they are slower, but they may be much faster than my best estimates (but will never be as fast as a plain C pointer).
As it is heavily based on the use of pointers, performance will depend almost exclusively on how fast peekint and pokeint perform their tasks.

Well, I have to go to sleep now...
I will keep you guys updated.

Just keep one thing in mind: the voxel engine is targetted at the PS2, which has a very powerfull floating point unit (actualy, a couple of them) and a processor which allows for 128 bit instructions.
So, I don´t think a P IV will have a chance against it.

Also, voxel engines don´t rely on hardware acceleration, so no matter what kind of video-card you have, it is not going to change the performance of the engine at all.

Fast RAM is desirable, thou...

Talk to you guys tomorrow,

Rui Barbosa Jr.

P.S.: I live in Brazil. It´s 01:21AM.
It would be good if you guys could tell me where you live, so I can have an approximate idea of time-zone differences among us.
P.P.S.: To know my local time, check Rio de Janeiro time or Brasilia time (they are both on the same time zone as mine, in Brazil). I live in Rio de Janeiro. I have to go.. take a warm shower and go to sleep... See you...

Paradox7

(Posted 2003) [#42]

Texas here, 2:18am right now, and now its time for me To Sleep :D going to take a quick shower, and sleep, man am i tired.

I would love to see a good Voxel engine in Blitz, can't wait. I really should get BlitzPlus :/

I remember seeing voxel demos, with little voxel people in QBasic, long time ago :D was pretty awesome.

So what is your voxel engine mainly able to create? an entire world? landscape? objects?

3DBuzzFan

(Posted 2003) [#43]

Hi.
The voxel engine for the PS2 deals with characters only.
It is not capable of renderind landscapes or rooms.
After the engine is complete, I will try to contact someone who has a nice polygon 3d engine for the PS2, in order to make both engines compatible.
As long as that polygon engine uses a 32 bit Z-buffer, it will work without any problem.

Due the the extremely CPU intensive nature of a voxel engine, it is not going to be very good a tool for creating real games, or applications which deal with more than 2 characters simulateneously.
It will be a nice tool for one-on-one combats, as well as fighting games.

I´ll post some source-code real soon.

Cheers,

Rui Barbosa Jr.

3DBuzzFan

(Posted 2003) [#44]

Hi guys.
I have finished implementing the backfac-culling and lighting on the voxel character engine for the PS2.
I am not using tables yet and, still, I get a nice framerate on the PS2, using TV resolution (NTSC output), with a complete spiderman model.
Lighting is a little meesed up, due to some bug in the hierarchy´s chain of rotations.
But, as long as I only move and/or rotate the topmost element (the butt), all pieces are adjusted accordingly, and are drawn using the proper lighting.
I will fix this probably tomorrow, and will get back to you.
As soon as it all works fine, I will write a B+ version of it and post it here.
Thanks for your help, again.

Rui Barbosa Jr.

BlitzSupport

(Posted 2003) [#45]

I don't have anything useful to add except "cool!"... I love seeing 3D engines written in 2D for some reason.

col	(Posted 2003) [#46]

I'm in Essex, just outside London UK.