Hi guys, how are u?

I'm having a little “issue” with my current design of the update logic, basically I have a Local Matrix (local pos, like 0 0 0) and a World Matrix (if attached could be 5131 -34 5790), I also have an attachment system, and calculate World Matrix before render, so if a parent moved, will also affect the childs. I first run the Update logic (modifying the local matrix) then after all the updates are done I call BuildMatrix (run through all lists that need a recalc for theirs childs) and then Render using the World Matrix.

My issue, is that sometimes in the Update logic I need the World Matrix (in order to get it, I have to force a BuildMatrix call if something in the chain has changed), and I prefer to avoid it, is there a design pattern for this issue, any idea? I was thinking on create a “cache world matrix” that gets the previous world matrix maybe, but can lead to issues with positions being 1 tick behind, or maybe when I need to use the World Matrix just get the Local Matrix from the root (the first parent) of the list.

Thanks!

The explanation isn't very clear. Are you trying to compute all World positions (I assume the final coordinates that are used for rendering) after all Local positions (I assume you mean animations relative to an object's position)?

Either you can't, and you should process your trees of attachments hierarchically instead (children after the parents they depend on) or you have spurious dependencies that can be eliminated. Can you provide a small example of the issue?

You typically have some sort of hierarchy with transformations. Transformations higher up in the tree happen first so by the time you reach your local transformations there is no need to transform higher ones. You should use a stack. You start at the root transformation and go down one branch of your tree and multiply in the transformation at that node. However, you always save the previous transformation on a stack so that when you go back up the branch can retrieve it by popping the stack.

In my engine I do things a bit differently I still have the tree, but I don't traverse it top down. The camera is also an object in the tree (typically a leaf, but it doesn't have to be) . I start with the camera and if I go up the tree I multiply in an inverse transformation. Going down I multiply in the normal transformation as before. The advantage to doing it this way is you skip going to world coordinates and go straight to view space coordinates space. This is great for very large terrain where you will end up with floating point precision issues doing it the other way.

Both ways are valid however. Again, the key is when you traverse your tree you push and pop matrices on and off a stack, so you don't have to recalculate them.

When you loop through your objects to perform the updates, you can keep the children off the main list and have them updated by the parents update logic. This way you can control the update order of parents/children. Just update the parent first, then child, and you will have the current frame exact matrix you need for rendering. I build the Render matrix for dynamic objects in the update code, not render code. That way you have the matrix as you said for a turret on a spaceship to be able to determine what direction bullets need to fire.

Yes, sorry I didn't explain myself. Basically what I do is like this:

void Scene::Update( float dt )
{
	for ( auto entity : entities )
		entity->Update( dt );
}

void Scene::BuildTransform()
{
	for ( auto entity : entities )
		entity->BuildTransform();
}

void Scene::Render( float dt )
{
	for ( auto entity : entities )
		entity->Reder( dt );
}

void Entity::BuildTransform()
{
	if ( !dirty )
		return;

	ConvertVectorToMarix( position, rotation, scale, localMatrix );

	if ( parent )
		MultiplyMatrix(parent->worldMatrix, localMatrix, worldMatrix);

	dirty = false;
}

void App::Loop()
{
	float dt = 0.f;

	while ( true )
	{
		SceneManager->Update( dt );
		SceneManager->BuildTransform();
		SceneManager->Render( dt );
	}
}

My idea is to go through all entities in memory order, so I avoid cache miss, that way if I have 200 entities, most of them will be in order, so I can avoid it most of the time.

Another idea is to only update the root object, and inside the Update function, update the childs and build matrix at the end, to avoid the extra go through the whole list just to call BuildMatrix, but with my current system I can be sure that when I call BuildMatrix all positions have been updated, my fear is that if I change the system, somehow at somepoint an Entity not attached to the root, will make a change and would need to rebuild again missing the BuildMatrix and having a missmatch in real position vs render world matrix position. (not seeing that happening).

Rewaz said:
my fear is that if I change the system, somehow at somepoint an Entity not attached to the root, will make a change and would need to rebuild again missing the BuildMatrix and having a missmatch in real position vs render world matrix position. (not seeing that happening).

You can keep a pointer to the parent object in each object, and then make sure all world matrices of all parents back to the root are not dirty, and if so, recompute them. I do this check every time I need to access the world matrix (its hidden behind a “getter” function), which is only about 3 times per object per frame (to update graphics, physics, and acoustic simulation). This makes sure that the matrix is always valid if there are modifications in the middle of the frame.

Aressera said:

Rewaz said:
my fear is that if I change the system, somehow at somepoint an Entity not attached to the root, will make a change and would need to rebuild again missing the BuildMatrix and having a missmatch in real position vs render world matrix position. (not seeing that happening).

You can keep a pointer to the parent object in each object, and then make sure all world matrices of all parents back to the root are not dirty, and if so, recompute them. I do this check every time I need to access the world matrix (its hidden behind a “getter” function), which is only about 3 times per object per frame (to update graphics, physics, and acoustic simulation). This makes sure that the matrix is always valid if there are modifications in the middle of the frame.

I do that, if I get the World Matrix there is a check

Matrix* Entity::GetWorldMatrix()
{
	if ( root && root->dirty )
		root->BuildTransform(); // will sync whole hierarchy as needed

	return &worldMatrix;
}

IMO scene graphs don't really work with ECS very well. You can google “scene graph ECS” to get some discussion on it. Certainty you can cobble something together but it's not really optimal. That's one reason I'm not all in on ECS yet.

You might be able to use topological sorting to process your entities by iterating blindly through a list like in your current example, but in the correct order: you need to place in the list first the entities with no parent, then the children of the entities in the first group, then the children of the entities in the second group, and so on, so that you process every entity after its parent.

It's going to get expensive if there are many modifications, of course; maybe something slightly less coherent, like a list of lists or a list with gaps, might perform better if you have deletions, insertions and parent changes.