B3D-style Hierarchy System

I am currently writing a B3D-style hierarchy entity system as part of a small 3D engine I'm working on.

The hierarchy system work the same as B3D - you specify a parent when creating an entity, and can use local or global parameters with the position/rotate commands.

I've got it working fine up to a point - after creating child entities, you are able to position and rotate everything using local coordinates, which works as expected.

However, I can't quite figure out how to get things working when you specify global coordinates for a child.

Internally, I have a global matrix for each entity and local x,y,z,pitch,yaw,roll values. I'm pretty sure that for global values to work correctly within a hierarchy system, I need to somehow convert the specified global coordinates into local coordinates.

But I haven't figured out how to do this. Can anyone help?

<Disclaimer: I guarantee none of this to be true. It is based entirely on what I remember (and my 3D math book). If you computer goes boomy, you're on your own. That said, I don't think I'm wrong.>

Let's say you have the following entity class:

Type Entity
  Field transform:Matrix
  Field parent:Entity
End Type

In order to convert global coordinates to object space coordinates, you have to transform them by the entity's transform.

Assuming the transform is relative to the parent entity's transform (that is, when you render the child, you would do something like glPushMatrix( ) glMultMatrixf( mat.GetPtr( ) )).

Anyhow, now onto how to do the transformation.

i:Entity = some entity with a variable number of parents

Local mat:Matrix = New Matrix ' identity matrix
Local transforms:TList = New TList

While i.parent <> Null
  i = i.parent
  transforms.AddFirst( i.mat )
Wend

For Local m:Matrix = EachIn transforms
  mat.Transform( m ) ' Transform mat by m
Next

' Now transform the point by the transformed matrix
mat.Transform( point )

' The point is now in object space

I think that's about right. As for converting rotations, you probably want to convert from euler to a matrix, apply the transformations, and then go back to euler.

I don't think that works, unfortunately.

The global coordinates need to be maintained, but at the same time, I need to somehow calculate the local offset from the parent entities.

So next time the whole matrix strack is calculated (using a similar method to above), when the child's local coordinates are multipled with the parent matrix, the child's global coordinates will be produced.

The closest I have come is subtracting the parent's global coordinates from the child's global coordinates, and saving those as the local x,y,z values.

Doesn't quite work though when rotations are involved.

hwh, this is exactly the problem we have had with using B3D's in Bmax and Torque. Everything works until you get to local offsets from parents. Everything goes mental at that point.

If you find a solution please share ;P

Simon, you only need to store the local coordinates. The global coordinates can be reproduced by transforming them.

I do store the local coordinates. The problem is getting the local coordinates to equal global coordinates when you do something like:

PositionEntity ent,23,45,75,True

The entity has to appear at that exact position. But it also has to be attached to its parent. So to attach it to its parent, it needs to have a local offset from the parent.

But how to calculate that offset, taking into account rotations and everything else?

I've got a feeling inverse matrices or something might need to be used somewhere.

I'll crack this eventually, then once it's done I'll post it here.

Well I solved it. Some silly oversights here and there were throwing everything out slightly. The hierarchy system now works the same as B3D's.

Global position entity -

Method PositionEntity(x_#,y_#,z_#,glob=False)

	x=x_#
	y=y_#
	z=-z_#

	' conv glob to local. x/y/z always local to parent or global if no parent
	If glob=True And parent<>Null
			
		x=x-parent.EntityX(True)
		y=y-parent.EntityY(True)
		z=z-parent.EntityZ(True)
			
		xa=EntityPitch(True)
		ya=EntityYaw(True)
		za=EntityRoll(True)
			
		Local new_mat:Matrix=New Matrix
		new_mat.LoadIdentity()
		new_mat.Rotate(-xa,-ya,-za)
		new_mat.Translate(x,y,z)

		x=new_mat.grid(3,0)
		y=new_mat.grid(3,1)
		z=new_mat.grid(3,2)
				
	EndIf

(code continues)

Global rotate entity:

Method RotateEntity(pitch_#,yaw_#,roll_#,glob=False)

	pitch=-pitch_#
	yaw=yaw_#
	roll=roll_#
		
	' conv glob to local. pitch/yaw/roll always local to parent or global if no parent
	If glob=True And parent<>Null

		pitch=pitch-parent.EntityPitch(True)
		yaw=yaw-parent.EntityYaw(True)
		roll=roll-parent.EntityRoll(True)
		
	EndIf

(code continues)

The above code calculates the local offsets from the parent entity.

Evak, I'm not sure this will help you out as .b3d's use quaternions I believe which is a different problem altogether. I intend to tackle .b3d loading next though so if I get a fully working .b3d loader working I'll let you know.

tom speed put a rather nice entity type system on this forum a while ago, you'd do well to look at his code...

I just tried Tom's, it works well but the results don't seem to be the same as B3D's.

I suppose it doesn't matter normally but for the purposes of my project (a Mac conversion), I need to mimic B3D's behaviour exactly.

man, this may be exactly what were looking for, thanks for posting :). Will have to check it out, some of our problems do lie with quat euler conversion too I believe, If you do figure it out that would be fantastic.

Would have to add you to the credits in my project.

Simon have you reached b3d file loading yet? Please let me kniow if you manage it while retain heierachies.

Here's code to handle transformations. Do a search for my code to handle Blitz3D-style quaternions.

Global TFORMEDVALUE_X#
Global TFORMEDVALUE_Y#
Global TFORMEDVALUE_Z#
Global TFORMEDVALUE_W#

Function TFormedX#()
Return TFORMEDVALUE_X
End Function

Function TFormedY#()
Return TFORMEDVALUE_Y
End Function

Function TFormedZ#()
Return TFORMEDVALUE_Z
End Function

Function TFormedW#()
Return TFORMEDVALUE_W
End Function

Function TFormPoint(x#,y#,z#,src:tentity,dst:tentity)

	TFORMEDVALUE_X=x
	TFORMEDVALUE_Y=y
	TFORMEDVALUE_Z=z
	If src=dst Return

	'Transform from source to common parent
	If src<>Null
		If src.matrixchanged src.UpdateMatrix()
		mat00#=src.matrix[0,0]
		mat10#=src.matrix[1,0]
		mat20#=src.matrix[2,0]
		mat01#=src.matrix[0,1]
		mat11#=src.matrix[1,1]
		mat21#=src.matrix[2,1]
		mat02#=src.matrix[0,2]
		mat12#=src.matrix[1,2]
		mat22#=src.matrix[2,2]
		x=x*src.scalex
		y=y*src.scaley
		z=z*src.scalez
		TFORMEDVALUE_X#=x#*mat00#+y*mat10#+z*mat20#
		TFORMEDVALUE_y#=x#*mat01#+y*mat11#+z*mat21#
		TFORMEDVALUE_z#=x#*mat02#+y*mat12#+z*mat22#
		TFORMEDVALUE_x#=TFORMEDVALUE_x#+src.x
		TFORMEDVALUE_y#=TFORMEDVALUE_y#+src.y
		TFORMEDVALUE_z#=TFORMEDVALUE_z#+src.z
		If src.parent<>Null
			tformpoint(TFORMEDVALUE_X,TFORMEDVALUE_Y,TFORMEDVALUE_Z,src.parent,Null)
		EndIf
	EndIf
	
	'Transform from common parent to destination
	While dst<>Null
		If dst.matrixchanged dst.UpdateMatrix()
		x=TFORMEDVALUE_x-dst.x
		y=TFORMEDVALUE_y-dst.y
		z=TFORMEDVALUE_z-dst.z
		qx#=dst.qx
		qy#=dst.qy
		qz#=dst.qz
		qw#=-dst.qw
		mat00=(1.0-2.0*qx#*qx#-2.0*qz#*qz#)
		mat10=-(2.0*qz#*qy#-2.0*qw#*qx#)
		mat20=-(2.0*qx#*qy#+2.0*qw#*qz#)
		mat01=-(2.0*qz#*qy#+2.0*qw#*qx#)
		mat11=(1.0-2.0*qy#*qy#-2.0*qx#*qx#)
		mat21=-(2.0*qw#*qy#-2.0*qx#*qz#)
		mat02=2.0*qw#*qz#-2.0*qx#*qy#
		mat12=2.0*qx#*qz#+2.0*qw#*qy#
		mat22=1.0-2.0*qz#*qz#-2.0*qy#*qy#
		TFORMEDVALUE_X#=x#*mat00#+y*mat10#+z*mat20#
		TFORMEDVALUE_y#=x#*mat01#+y*mat11#+z*mat21#
		TFORMEDVALUE_z#=x#*mat02#+y*mat12#+z*mat22#		
		TFORMEDVALUE_X#=TFORMEDVALUE_X/dst.scalex
		TFORMEDVALUE_Y#=TFORMEDVALUE_Y/dst.scaley
		TFORMEDVALUE_Z#=TFORMEDVALUE_Z/dst.scalez
		dst=dst.parent
		If dst=Null Exit
	Wend
		
End Function


Function TFormVector(x#,y#,z#,src:tentity,dst:tentity)
	TFORMEDVALUE_X=x
	TFORMEDVALUE_Y=y
	TFORMEDVALUE_Z=z
	If src=dst Return
	If src<>Null
		If src.matrixchanged src.UpdateMatrix()
		mat00#=src.matrix[0,0]
		mat10#=src.matrix[1,0]
		mat20#=src.matrix[2,0]
		mat01#=src.matrix[0,1]
		mat11#=src.matrix[1,1]
		mat21#=src.matrix[2,1]
		mat02#=src.matrix[0,2]
		mat12#=src.matrix[1,2]
		mat22#=src.matrix[2,2]
		x=x*src.scalex
		y=y*src.scaley
		z=z*src.scalez
		TFORMEDVALUE_X#=x#*mat00#+y*mat10#+z*mat20#
		TFORMEDVALUE_y#=x#*mat01#+y*mat11#+z*mat21#
		TFORMEDVALUE_z#=x#*mat02#+y*mat12#+z*mat22#
		TFORMEDVALUE_x#=TFORMEDVALUE_x#
		TFORMEDVALUE_y#=TFORMEDVALUE_y#
		TFORMEDVALUE_z#=TFORMEDVALUE_z#
		If src.parent<>Null
			tformpoint(TFORMEDVALUE_X,TFORMEDVALUE_Y,TFORMEDVALUE_Z,src.parent,Null)
		EndIf
	EndIf
	While dst<>Null
		If dst.matrixchanged dst.UpdateMatrix()
		x=TFORMEDVALUE_x
		y=TFORMEDVALUE_y
		z=TFORMEDVALUE_z
		qx#=dst.qx
		qy#=dst.qy
		qz#=dst.qz
		qw#=-dst.qw
		mat00=(1.0-2.0*qx#*qx#-2.0*qz#*qz#)
		mat10=-(2.0*qz#*qy#-2.0*qw#*qx#)
		mat20=-(2.0*qx#*qy#+2.0*qw#*qz#)
		mat01=-(2.0*qz#*qy#+2.0*qw#*qx#)
		mat11=(1.0-2.0*qy#*qy#-2.0*qx#*qx#)
		mat21=-(2.0*qw#*qy#-2.0*qx#*qz#)
		mat02=2.0*qw#*qz#-2.0*qx#*qy#
		mat12=2.0*qx#*qz#+2.0*qw#*qy#
		mat22=1.0-2.0*qz#*qz#-2.0*qy#*qy#
		TFORMEDVALUE_X#=x#*mat00#+y*mat10#+z*mat20#
		TFORMEDVALUE_y#=x#*mat01#+y*mat11#+z*mat21#
		TFORMEDVALUE_z#=x#*mat02#+y*mat12#+z*mat22#		
		TFORMEDVALUE_X#=TFORMEDVALUE_X/dst.scalex
		TFORMEDVALUE_Y#=TFORMEDVALUE_Y/dst.scaley
		TFORMEDVALUE_Z#=TFORMEDVALUE_Z/dst.scalez
		dst=dst.parent
		If dst=Null Exit
	Wend
		
End Function

Function TFormNormal(x#,y#,z#,src:tentity,dst:tentity)
	TFORMEDVALUE_X=x
	TFORMEDVALUE_Y=y
	TFORMEDVALUE_Z=z
	If src=dst Return
	If src<>Null
		If src.matrixchanged src.UpdateMatrix()
		mat00#=src.matrix[0,0]
		mat10#=src.matrix[1,0]
		mat20#=src.matrix[2,0]
		mat01#=src.matrix[0,1]
		mat11#=src.matrix[1,1]
		mat21#=src.matrix[2,1]
		mat02#=src.matrix[0,2]
		mat12#=src.matrix[1,2]
		mat22#=src.matrix[2,2]
		TFORMEDVALUE_X#=x#*mat00#+y*mat10#+z*mat20#
		TFORMEDVALUE_y#=x#*mat01#+y*mat11#+z*mat21#
		TFORMEDVALUE_z#=x#*mat02#+y*mat12#+z*mat22#
		TFORMEDVALUE_x#=TFORMEDVALUE_x#
		TFORMEDVALUE_y#=TFORMEDVALUE_y#
		TFORMEDVALUE_z#=TFORMEDVALUE_z#
		If src.parent<>Null
			tformpoint(TFORMEDVALUE_X,TFORMEDVALUE_Y,TFORMEDVALUE_Z,src.parent,Null)
		EndIf
	EndIf
	While dst<>Null
		If dst.matrixchanged dst.UpdateMatrix()
		x=TFORMEDVALUE_x
		y=TFORMEDVALUE_y
		z=TFORMEDVALUE_z
		qx#=dst.qx
		qy#=dst.qy
		qz#=dst.qz
		qw#=-dst.qw
		mat00=(1.0-2.0*qx#*qx#-2.0*qz#*qz#)
		mat10=-(2.0*qz#*qy#-2.0*qw#*qx#)
		mat20=-(2.0*qx#*qy#+2.0*qw#*qz#)
		mat01=-(2.0*qz#*qy#+2.0*qw#*qx#)
		mat11=(1.0-2.0*qy#*qy#-2.0*qx#*qx#)
		mat21=-(2.0*qw#*qy#-2.0*qx#*qz#)
		mat02=2.0*qw#*qz#-2.0*qx#*qy#
		mat12=2.0*qx#*qz#+2.0*qw#*qy#
		mat22=1.0-2.0*qz#*qz#-2.0*qy#*qy#
		TFORMEDVALUE_X#=x#*mat00#+y*mat10#+z*mat20#
		TFORMEDVALUE_y#=x#*mat01#+y*mat11#+z*mat21#
		TFORMEDVALUE_z#=x#*mat02#+y*mat12#+z*mat22#
		dst=dst.parent
		If dst=Null Exit
	Wend
End Function

Update the entity matrix:

	Method UpdateMatrix()
		matrixchanged=False
		matrix[0,0]=(1.0-2.0*qx#*qx#-2.0*qz#*qz#)
		matrix[1,0]=-(2.0*qz#*qy#-2.0*qw#*qx#)
		matrix[2,0]=-(2.0*qx#*qy#+2.0*qw#*qz#)
		matrix[0,1]=-(2.0*qz#*qy#+2.0*qw#*qx#)
		matrix[1,1]=(1.0-2.0*qy#*qy#-2.0*qx#*qx#)
		matrix[2,1]=-(2.0*qw#*qy#-2.0*qx#*qz#)
		matrix[0,2]=2.0*qw#*qz#-2.0*qx#*qy#
		matrix[1,2]=2.0*qx#*qz#+2.0*qw#*qy#
		matrix[2,2]=1.0-2.0*qz#*qz#-2.0*qy#*qy#
	EndMethod

Oh, here is BlitzPlus code for tforming rotations:

Function TFormQuat(x#,y#,z#,w#,src,dst)
TFORMEDVALUE_X=x
TFORMEDVALUE_Y=y
TFORMEDVALUE_Z=z
TFORMEDVALUE_W=w
If src=dst Return

;Transform from source to parent
If src
	qx#=ObjectQuatX(src)
	qy#=ObjectQuatY(src)
	qz#=ObjectQuatZ(src)
	qw#=ObjectQuatW(src)
	MulQuat TFORMEDVALUE_X,TFORMEDVALUE_Y,TFORMEDVALUE_Z,TFORMEDVALUE_W,-qx,-qy,-qz,qw
	TFORMEDVALUE_X=VectorX()
	TFORMEDVALUE_Y=VectorY()
	TFORMEDVALUE_Z=VectorZ()
	TFORMEDVALUE_W=VectorW()
	EndIf

;Transform from parent to source
If dst
	EndIf
End Function

Function TFormEuler(pitch#,yaw#,roll#,src,dst)
EulerAsQuat pitch#,yaw#,roll#
TFormQuat vectorx(),vectory(),vectorz(),vectorw(),src,dst
QuatAsEuler TFormedX(),TFormedY(),TFormedZ(),TformedW()
TFORMEDVALUE_X=VectorX()
TFORMEDVALUE_Y=VectorY()
TFORMEDVALUE_Z=VectorZ()
TFORMEDVALUE_W=0.0
End Function

Quat code:

Function EulerAsQuat(pitch#,yaw#,roll#)
cr#=Cos(-roll#/2.0)
cp#=Cos(pitch#/2.0)
cy#=Cos(yaw#/2.0)
sr#=Sin(-roll#/2.0)
sp#=Sin(pitch#/2.0)
sy#=Sin(yaw#/2.0)
cpcy#=cp#*cy#
spsy#=sp#*sy#
spcy#=sp#*cy#
cpsy#=cp#*sy#
vectorw#=cr#*cpcy#+sr#*spsy#
vectorx#=sr#*cpcy#-cr#*spsy#
vectory#=cr#*spcy#+sr#*cpsy#
vectorz#=cr#*cpsy#-sr#*spcy#
End Function

Function QuatAsEuler(x#,y#,z#,w#)
sint#=(2.0*w*y)-(2.0*x*z)
cost_temp#=1.0-(sint#*sint#)
If Abs(cost_temp#)>QuatToEulerAccuracy
	cost#=Sqr(cost_temp#)
	Else
	cost#=0.0
	EndIf
If Abs(cost#)>0.001
	sinv#=((2.0*y*z)+(2.0*w*x))/cost#
	cosv#=(1.0-(2.0*x*x)-(2.0*y*y))/cost#
	sinf#=((2.0*x*y)+(2.0*w*z))/cost#
	cosf#=(1.0-(2.0*y*y)-(2.0*z*z))/cost#
	Else
	sinv#=(2.0*w*x)-(2.0*y*z)
	cosv#=1.0-(2.0*x*x)-(2.0*z*z)
	sinf#=0.0
	cosf#=1.0
	EndIf
vectorz#=-ATan2(sinv#,cosv#)
vectorx#=ATan2(sint#,cost#)
vectory#=ATan2(sinf#,cosf#)
End Function

now, this shouldn't be lost! :D

You might have to change it a bit to adapt it to your own engine, but all the math is correct, and has been tested meticulously against Blitz3D calculations.

wow! lots of good stuff here, thanks Halo :)

Indeed. Thank you very much.

Are you sure your quat to matrix code is right? I mean did you ever support loading of b3ds with Hierarchy support?

I ask because that's how far we've got, but even your quat to matrix code results in faulty rotations.

Rendering a left-handed coord sys in GL:

		glMatrixMode GL_MODELVIEW
		glPushMatrix()
		glLoadIdentity()

		glRotatef camera.roll,0,0,1
		glRotatef camera.pitch,1,0,0
		glRotatef -camera.yaw,0,1,0
		glTranslatef -camera.x,-camera.y,camera.z
		glScalef 1,1,-1

Now when you draw a model:

	glpushmatrix()
	gltranslatef entity.x,entity.y,entity.z
	glRotatef -entity.yaw,0,1,0
	glRotatef entity.pitch,1,0,0
	glRotatef entity.roll,0,0,1
	glScalef entity.scalex,entity.scaley,entity.scalez
	

Very useful stuff, nice work simonh/halo :)

Hi all, memories a bit groggy as I aint touched my code in a few weeks but...

Re: The code I posted a while back, GL does use an inverted Z axis, so some rotation will be negative. But on the whole, they should match up with B3Ds if you ignore the sign.

i.e, B3Ds TurnEntity entity,30,30,30 would be entity.Turn 30,-30,30 in my GL code, and of course (or something similar, can't recall which axis it affects :)

Give my code another look over. It does cater for hierarchial rotation & position in local, parent & world space (something I've not seen in ANY other GL demo code on the net!!!) and it's an efficient way of rendering a scene IMO.

Later!
Tom