Code archives/3D Graphics - Misc/Alpha Zorder

Here's another take on the same thing, based on Beakers code, but speeded up quite a bit. It also uses less memory :)

;
; Alpha Z-Ordering Mumbo Jumbo
;
; By Beaker and tweaked by Fredborg
;

;
; Zorder type
Type zorder
	Field mesh
	Field surf
	Field x,y,z			; Banks: size = tricnt * 6 bytes (3 shorts)
	Field n_tris		; Counttriangles(surf)-1
	Field include_y		; Include y axis sorting
	Field prev			; Last sorting axis
End Type

Function ZOrder_SortBank(bankA,bankB,l,r)
	Local p,q,h,x#
	p=l
	q=r
	x=PeekFloat(bankA,((l+r)/2)*4)
	Repeat
		While PeekFloat(bankA,p*4)>x
			p=p+1
		Wend
		While x>PeekFloat(bankA,q*4)
			q=q-1
		Wend
		If p>q Then Exit
		
		;SWAP------------------
		v0 = PeekShort(bankB,q*6 + 0)
		v1 = PeekShort(bankB,q*6 + 2)
		v2 = PeekShort(bankB,q*6 + 4)

		PokeShort bankB,q*6 + 0,PeekShort(bankB,p*6 + 0)
		PokeShort bankB,q*6 + 2,PeekShort(bankB,p*6 + 2)
		PokeShort bankB,q*6 + 4,PeekShort(bankB,p*6 + 4)
				
		PokeShort bankB,p*6 + 0,v0
		PokeShort bankB,p*6 + 2,v1
		PokeShort bankB,p*6 + 4,v2

		f# = PeekFloat(bankA,q*4)
		PokeFloat bankA,q*4,PeekFloat(bankA,p*4)
		PokeFloat bankA,p*4,f#	
		;----------------------
		
		p=p+1
		q=q-1
		If q<0 Then Exit
	Forever 
	If l<q Then ZOrder_SortBank(bankA,bankB,l,q)
	If p<r Then ZOrder_SortBank(bankA,bankB,p,r)

End Function

Function ZOrder_Init.zorder(mesh, include_y = False)

	zo.zorder = New zorder
	zo\mesh = mesh
	zo\surf = GetSurface(zo\mesh,1)

	If zo\surf = 0
		RuntimeError "Zorderize(): No surface found!"
	EndIf

	zo\include_y = include_y

	zo\n_tris = CountTriangles(zo\surf)-1

	tempbank = CreateBank((zo\n_tris+1)*4)

	; X axis sorting
	zo\x = CreateBank((zo\n_tris+1)*6)
	For t = 0 To zo\n_tris
		ft = t*6
		PokeShort zo\x,ft+0,TriangleVertex(zo\surf,t,0)
		PokeShort zo\x,ft+2,TriangleVertex(zo\surf,t,1)
		PokeShort zo\x,ft+4,TriangleVertex(zo\surf,t,2)
		PokeFloat tempbank,t*4,VertexX(zo\surf,TriangleVertex(zo\surf,t,0))+VertexX(zo\surf,TriangleVertex(zo\surf,t,1))+VertexX(zo\surf,TriangleVertex(zo\surf,t,2))
	Next
	ZOrder_SortBank(tempbank,zo\x,0,zo\n_tris)

	If include_y
		; Y axis sorting
		zo\y = CreateBank((zo\n_tris+1)*6)
		For t = 0 To zo\n_tris
			ft = t*6
			PokeShort zo\y,ft+0,TriangleVertex(zo\surf,t,0)
			PokeShort zo\y,ft+2,TriangleVertex(zo\surf,t,1)
			PokeShort zo\y,ft+4,TriangleVertex(zo\surf,t,2)
			PokeFloat tempbank,t*4,VertexY(zo\surf,TriangleVertex(zo\surf,t,0))+VertexY(zo\surf,TriangleVertex(zo\surf,t,1))+VertexY(zo\surf,TriangleVertex(zo\surf,t,2))
		Next
		ZOrder_SortBank(tempbank,zo\y,0,zo\n_tris)
	EndIf
	
	; Z axis sorting
	zo\z = CreateBank((zo\n_tris+1)*6)
	For t = 0 To zo\n_tris
		ft = t*6
		PokeShort zo\z,ft+0,TriangleVertex(zo\surf,t,0)
		PokeShort zo\z,ft+2,TriangleVertex(zo\surf,t,1)
		PokeShort zo\z,ft+4,TriangleVertex(zo\surf,t,2)
		PokeFloat tempbank,t*4,VertexZ(zo\surf,TriangleVertex(zo\surf,t,0))+VertexZ(zo\surf,TriangleVertex(zo\surf,t,1))+VertexZ(zo\surf,TriangleVertex(zo\surf,t,2))
	Next
	ZOrder_SortBank(tempbank,zo\z,0,zo\n_tris)
	
	FreeBank tempbank
	
	Return zo
	
End Function


Function ZOrder_Update(zo.zorder,cam)
	
	Local t,tf
	
	TFormVector 0,0,1, cam,0
	Local tx# = TFormedX()
	Local ty# = TFormedY()
	Local tz# = TFormedZ()
	
	Local temp = 0
	If zo\include_y = False Then ty = 0.0
	If (Abs(tx) > Abs(tz)) And (Abs(tx) > Abs(ty))
		temp = Sgn(tx)
		bank = zo\x
	ElseIf Abs(ty) > Abs(tz)
		temp = Sgn(ty)*2
		bank = zo\y
	Else
		temp = Sgn(tz)*3
		bank = zo\z
	EndIf
	
	If temp<>zo\prev
	
		zo\prev = temp
		ClearSurface zo\surf,0,1
					
		Select Sgn(zo\prev)
			Case 1:
				For t = 0 To zo\n_tris
					tf = t*6
					AddTriangle ( zo\surf,PeekShort(bank,tf),PeekShort(bank,tf+2),PeekShort(bank,tf+4) )
				Next
			Case -1:
				For t = zo\n_tris To 0 Step -1
					tf = t*6
					AddTriangle ( zo\surf,PeekShort(bank,tf),PeekShort(bank,tf+2),PeekShort(bank,tf+4) )
				Next
		End Select
		
	EndIf
	
End Function

Function ZOrder_Free(zo.zorder)

	If zo = Null
		For zo.zorder = Each zorder
			If zo\x Then FreeBank zo\x
			If zo\y Then FreeBank zo\y
			If zo\z Then FreeBank zo\z
			Delete zo
		Next
	Else
		If zo\x Then FreeBank zo\x
		If zo\y Then FreeBank zo\y
		If zo\z Then FreeBank zo\z
		Delete zo
	EndIf

End Function

Maybe can you post an example freborg ?

Sure, here is a small one:

Graphics3D 640,480,0,2
SetBuffer BackBuffer()

Include "zorder.bb"

b = CreateBrush()
BrushFX b,1+2+16+32

m = CreateMesh()
s = CreateSurface(m,b)

size# = 5.0
hsize# = size/2.0

For i = 0 To 1000
	x# = Rnd(-50,50)
	z# = Rnd(-50,50)
	
	a# = Rand(0,3)*90
	xx# = Sin(a)*hsize
	zz# = Cos(a)*hsize
	
	v0 = AddVertex(s,x-xx,0,z-zz)
		VertexColor s,v0,Rand(128,255),Rand(128,255),Rand(128,255),Rnd(0,1)
	v1 = AddVertex(s,x-xx,size,z-zz)
		VertexColor s,v1,Rand(128,255),Rand(128,255),Rand(128,255),Rnd(0,1)
	v2 = AddVertex(s,x+xx,size,z+zz)
		VertexColor s,v2,Rand(128,255),Rand(128,255),Rand(128,255),Rnd(0,1)
	v3 = AddVertex(s,x+xx,0,z+zz)
		VertexColor s,v3,Rand(128,255),Rand(128,255),Rand(128,255),Rnd(0,1)
		
	AddTriangle s,v0,v1,v2
	AddTriangle s,v2,v3,v0
Next

;
; Prepare zordering for mesh m
zorder.zorder = ZOrder_Init(m)

doz = False;True

c = CreateCamera()
p# = 0
y# = 0

MoveMouse 320,240
Repeat
	
	p = p+MouseYSpeed()
	y = y-MouseXSpeed()
	RotateEntity c,p,y,0
	MoveEntity c,KeyDown(205)-KeyDown(203),0,KeyDown(200)-KeyDown(208)
	
	MoveMouse 320,240

	;
	; Toggle zordering on/off
	If KeyHit(57)
		doz = Not doz
	EndIf

	;
	; Update zordering for mesh m with camera c
	If doz
		ZOrder_Update(zorder,c)
	EndIf

	RenderWorld

	If doz
		Text 0,0,"Space to disable ZOrdering"
	Else
		Text 0,0,"Space to enable ZOrdering"
	EndIf
	Flip
	
Until KeyHit(1)

End

Bare in mind, that this system (Fredborg's) won't work if you modify the mesh after you have inited the system (tried it on my cloud system, after modifying the position of some of the 'sprites' it wont work).

Although, a very nice system fredborg !

This is true. My system only works on static meshes (or mostly static, for example: animated grass, trees etc).

i get a surface index out of range when using this code on a loadanimmesh() mesh. any hints?

Probably because your base entity isn't a mesh (probly a pivot). You can check it with something like:
If EntityClass(myEntity) <> "Mesh" Then Print "No mesh here"

i have several meshes and pivots mixed in this loadanimmesh()-mesh. do i have to delete all the pivots to get zorder to work? or do i have to make sure that the base entity is a mesh?

Neither. It expects to recieve a single mesh. And can only sort one mesh to be visually correct (AFAIR). For example: a lot of grass, a lot of leaves, but not both.

There is a way to get it to work on both grass and leaves, but it involves combining the grass and leaf textures into one, and also combining the meshes.

ohmygod - i have 260 meshes (in one loadanimmesh)... ok i see i have a problem.... hmmmmm

Actually, regarding the grass/leaves example I give above, you wouldn't need to combine them as long as they never visually overlap each other. But, you would need to pass them both seperately to the Zorder.

[EDIT: discussion here:
http://www.blitzbasic.com/Community/posts.php?topic=59416 ]

Here is a new version that (a) works better with animated meshes (rotation) and (b) you can optionally
just supply a particular surface to zorderize, using this syntax:
ZOrder_Init(mesh, surf=0, y_include=False)

Here is the new library:

;
; Alpha Z-Ordering Mumbo Jumbo
;
; By Beaker and tweaked by Fredborg - retweaked by Beaker :)
;

;
; Zorder type
Type zorder
	Field mesh
	Field surf
	Field x,y,z			; Banks: size = tricnt * 6 bytes (3 shorts)
	Field n_tris		; Counttriangles(surf)-1
	Field include_y		; Include y axis sorting
	Field prev			; Last sorting axis
End Type

Function ZOrder_SortBank(bankA,bankB,l,r)
	Local p,q,h,x#
	p=l
	q=r
	x=PeekFloat(bankA,((l+r)/2)*4)
	Repeat
		While PeekFloat(bankA,p*4)>x
			p=p+1
		Wend
		While x>PeekFloat(bankA,q*4)
			q=q-1
		Wend
		If p>q Then Exit
		
		;SWAP------------------
		v0 = PeekShort(bankB,q*6 + 0)
		v1 = PeekShort(bankB,q*6 + 2)
		v2 = PeekShort(bankB,q*6 + 4)

		PokeShort bankB,q*6 + 0,PeekShort(bankB,p*6 + 0)
		PokeShort bankB,q*6 + 2,PeekShort(bankB,p*6 + 2)
		PokeShort bankB,q*6 + 4,PeekShort(bankB,p*6 + 4)
				
		PokeShort bankB,p*6 + 0,v0
		PokeShort bankB,p*6 + 2,v1
		PokeShort bankB,p*6 + 4,v2

		f# = PeekFloat(bankA,q*4)
		PokeFloat bankA,q*4,PeekFloat(bankA,p*4)
		PokeFloat bankA,p*4,f#	
		;----------------------
		
		p=p+1
		q=q-1
		If q<0 Then Exit
	Forever 
	If l<q Then ZOrder_SortBank(bankA,bankB,l,q)
	If p<r Then ZOrder_SortBank(bankA,bankB,p,r)

End Function

Function ZOrder_Init.zorder(mesh, surf=0, include_y = False)

	zo.zorder = New zorder
	zo\mesh = mesh
	If surf = 0
		zo\surf = GetSurface(zo\mesh,1)
	Else
		zo\surf = surf
	EndIf

	If zo\surf = 0
		RuntimeError "Zorderize(): No surface found!"
	EndIf

	zo\include_y = include_y

	zo\n_tris = CountTriangles(zo\surf)-1

	tempbank = CreateBank((zo\n_tris+1)*4)

	; X axis sorting
	zo\x = CreateBank((zo\n_tris+1)*6)
	For t = 0 To zo\n_tris
		ft = t*6
		PokeShort zo\x,ft+0,TriangleVertex(zo\surf,t,0)
		PokeShort zo\x,ft+2,TriangleVertex(zo\surf,t,1)
		PokeShort zo\x,ft+4,TriangleVertex(zo\surf,t,2)
		PokeFloat tempbank,t*4,VertexX(zo\surf,TriangleVertex(zo\surf,t,0))+VertexX(zo\surf,TriangleVertex(zo\surf,t,1))+VertexX(zo\surf,TriangleVertex(zo\surf,t,2))
	Next
	ZOrder_SortBank(tempbank,zo\x,0,zo\n_tris)

	If include_y
		; Y axis sorting
		zo\y = CreateBank((zo\n_tris+1)*6)
		For t = 0 To zo\n_tris
			ft = t*6
			PokeShort zo\y,ft+0,TriangleVertex(zo\surf,t,0)
			PokeShort zo\y,ft+2,TriangleVertex(zo\surf,t,1)
			PokeShort zo\y,ft+4,TriangleVertex(zo\surf,t,2)
			PokeFloat tempbank,t*4,VertexY(zo\surf,TriangleVertex(zo\surf,t,0))+VertexY(zo\surf,TriangleVertex(zo\surf,t,1))+VertexY(zo\surf,TriangleVertex(zo\surf,t,2))
		Next
		ZOrder_SortBank(tempbank,zo\y,0,zo\n_tris)
	EndIf
	
	; Z axis sorting
	zo\z = CreateBank((zo\n_tris+1)*6)
	For t = 0 To zo\n_tris
		ft = t*6
		PokeShort zo\z,ft+0,TriangleVertex(zo\surf,t,0)
		PokeShort zo\z,ft+2,TriangleVertex(zo\surf,t,1)
		PokeShort zo\z,ft+4,TriangleVertex(zo\surf,t,2)
		PokeFloat tempbank,t*4,VertexZ(zo\surf,TriangleVertex(zo\surf,t,0))+VertexZ(zo\surf,TriangleVertex(zo\surf,t,1))+VertexZ(zo\surf,TriangleVertex(zo\surf,t,2))
	Next
	ZOrder_SortBank(tempbank,zo\z,0,zo\n_tris)
	
	FreeBank tempbank
	
	Return zo
	
End Function


Function ZOrder_Update(zo.zorder,cam)
	
	Local t,tf
	
	TFormVector 0,0,1, cam,zo\mesh
	Local tx# = TFormedX()
	Local ty# = TFormedY()
	Local tz# = TFormedZ()
	
	Local temp = 0
	If zo\include_y = False Then ty = 0.0
	If (Abs(tx) > Abs(tz)) And (Abs(tx) > Abs(ty))
		temp = Sgn(tx)
		bank = zo\x
	ElseIf Abs(ty) > Abs(tz)
		temp = Sgn(ty)*2
		bank = zo\y
	Else
		temp = Sgn(tz)*3
		bank = zo\z
	EndIf
	
	If temp<>zo\prev
	
		zo\prev = temp
		ClearSurface zo\surf,0,1
					
		Select Sgn(zo\prev)
			Case 1:
				For t = 0 To zo\n_tris
					tf = t*6
					AddTriangle ( zo\surf,PeekShort(bank,tf),PeekShort(bank,tf+2),PeekShort(bank,tf+4) )
				Next
			Case -1:
				For t = zo\n_tris To 0 Step -1
					tf = t*6
					AddTriangle ( zo\surf,PeekShort(bank,tf),PeekShort(bank,tf+2),PeekShort(bank,tf+4) )
				Next
		End Select
		
	EndIf
	
End Function

Function ZOrder_Free(zo.zorder)

	If zo = Null
		For zo.zorder = Each zorder
			If zo\x Then FreeBank zo\x
			If zo\y Then FreeBank zo\y
			If zo\z Then FreeBank zo\z
			Delete zo
		Next
	Else
		If zo\x Then FreeBank zo\x
		If zo\y Then FreeBank zo\y
		If zo\z Then FreeBank zo\z
		Delete zo
	EndIf

End Function

And here is new example code:

Graphics3D 640,480,0,2
SetBuffer BackBuffer()

Include "zorder.bb"

b = CreateBrush()
BrushFX b,1+2+16+32

m = CreateMesh()
s = CreateSurface(m,b)

size# = 5.0
hsize# = size/2.0

For i = 0 To 1000
	x# = Rnd(-50,50)
	z# = Rnd(-50,50)
	
	a# = Rand(0,3)*90
	xx# = Sin(a)*hsize
	zz# = Cos(a)*hsize
	
	v0 = AddVertex(s,x-xx,0,z-zz)
		VertexColor s,v0,Rand(128,255),Rand(128,255),Rand(128,255),Rnd(0.5,1)
	v1 = AddVertex(s,x-xx,size,z-zz)
		VertexColor s,v1,Rand(128,255),Rand(128,255),Rand(128,255),Rnd(0.5,1)
	v2 = AddVertex(s,x+xx,size,z+zz)
		VertexColor s,v2,Rand(128,255),Rand(128,255),Rand(128,255),Rnd(0.5,1)
	v3 = AddVertex(s,x+xx,0,z+zz)
		VertexColor s,v3,Rand(128,255),Rand(128,255),Rand(128,255),Rnd(0.5,1)
		
	AddTriangle s,v0,v1,v2
	AddTriangle s,v2,v3,v0
Next

;
; Prepare zordering for mesh m
zorder.zorder = ZOrder_Init(m)

doz = False;True

c = CreateCamera()
p# = 0
y# = 0

MoveMouse 320,240
Repeat
	
	p = p+MouseYSpeed()
	y = y-MouseXSpeed()
	RotateEntity c,p,y,0
	MoveEntity c,KeyDown(205)-KeyDown(203),0,KeyDown(200)-KeyDown(208)
	PositionEntity c,EntityX(c),2,EntityZ(c)

	TurnEntity m,0,0.5,0
	
	MoveMouse 320,240

	;
	; Toggle zordering on/off
	If KeyHit(57)
		doz = Not doz
	EndIf

	;
	; Update zordering for mesh m with camera c
	If doz
		ZOrder_Update(zorder,c)
	EndIf

	RenderWorld

	If doz
		Text 0,0,"Space to disable ZOrdering"
	Else
		Text 0,0,"Space to enable ZOrdering"
	EndIf
	Flip
	
Until KeyHit(1)

End

isn't the random z-order problem only affecting triangles of one mesh, so does it actualy make sense to add several meshes together?

And to t3k: there is a command in blitz that tells you if an entity is a mesh, a pivot or whatever:

http://www.blitzbasic.com/b3ddocs/command.php?name=entityclass&ref=goto

So you maybe have to parse the animmesh recursively and make a list of all children that are meshes.