# Avoiding unnecessary recalculation

This topic is 1838 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hey,

I could use some of your input on a problem I'm having (I'm using Java).

I'm writing a Node class which keeps track of the transformation of objects in my game world. This class contains position, rotation and scale fields for getting and setting the objects transformation and a transformation matrix for quick and easy calculations.

The problem lies in the fact that this matrix must be updated to match the current transformation every frame, but only when necessary. If the transformation of the node has not changed I would like not to recalculate the transformation matrix. As scene's in my game consist of a mixure of static and dynamic objects I feel such a optimisation can be worthwhile.

Well... in C++ this would easily be solved by a construction like:

class Node
{
private:

Vector position;

bool isDirty;

public:

void setPosition(const Vector& p)
{
position = p;
isDirty = true;
}

void move(const Vector& p)
{
position += p;
isDirty = true;
}

const Vector& getPosition() const
{
return position;
}

void update()
{
if (isDirty)
recalculate();
}
}


However in Java you can't have const references thus making it possible to do: node.getPosition().set(0, 0). This makes the approach using a isDirty flag quite inpractical. Now I'm looking into other solutions:

• Still use the isDirty flag and let the getPosition() method set the isDirty flag to true aswell. This would work and is quite easy but would also lead to some unnecessary recalculation of the transformation matrix.
• Use the implementation as above and make it a rule not to modify the value returned by getPosition. This could also work but is not at all safe and will lead to untraceable bugs if you forget the rule.
• Store the previous transformation state of the node and do a comparison with the current one to see if recalculation is needed. I'm not really a fan of this solution as it makes the Node class quite a lot bigger and introduces a lot of 'epsilon comparisons' to the update method.
• Store a hashcode of the previous transformation state and compare this to the hashcode of the current transformation. I'm not sure about this one either. It introduces extra calculation in cases where the transformation matrix needs to be updated and there is a risk of a 'hashcode collision' which would lead to completely untraceable bugs (I have no idea what the chance on this is though)
• Just recalculate the transformation matrix every frame.

I was hoping you guys might have an other solution or have some opinions about the solutions I came up with.

##### Share on other sites

Another option is to have getPosition() return a clone of the position.

##### Share on other sites

Hm... The way I see it, you need to expose that "set(0,0)" in a way that sets up the "isDirty" flag.

Maybe extending Vector in a class that overrides all the mutator methods so you'd have:

public class DirtyVector extends Vector
{
private boolean dirty; //We don't want anyone touching the "dirty" flag either.

@Override
public void set ( final float x, final float y )
{
this.dirty = true;
super().set(x,y);
}

//@Override
//Other methods that need to be overriden go here.

//Now providing a method to see if its dirty. The object is in charge of setting the flag. Users only read it.
public boolean isDirty()
{
return this.dirty;
}
}

It would expose the same functionality but with all mutator methods setting the "dirty" flag. You can also use composition, having a class that contains a private Vector object, and exposes the same methods, but again tracking the "dirty" flag.

The node can't track the "dirtiness" of what it has if somebody else can just call a "get()" method and have the reference to directly work with that data, if you want to provide such access you'll have to add a layer in between that can track those finer changes.

##### Share on other sites

I suggest taking a look at the Ogre3D source- their transformation hierarchy system is what I based mine off of, and their SceneNode system solves exactly this type of problem.:

Node source

##### Share on other sites

I suggest taking a look at the Ogre3D source- their transformation hierarchy system is what I based mine off of, and their SceneNode system solves exactly this type of problem.:

Node source

We're moving away from that paradigm in Ogre 2.0. Short answer is the cache miss caused by the branch is more expensive than recalculating the derived transform (derived pos, rot & scale, that's 10 floats); and we only update the derived transform matrix once per frame (16 floats); just as described in Pitfalls of Object Oriented Programming. The article is written mainly with PS3 in mind (which don't have branch predictors), however they don't seem to help much in x86, as we're already seeing up to 3x improvements for moving to a data oriented approach (note the results are not final and subject to change, however so far the performance has increased rather than decreased, I'll give more information when it's ready).

Using "dirty" flags at a micro level such as a node fights Moore's Law.

Instead, we're moving to a static/dynamic paradigm, where the user specifies if the data is going to be static or dynamic for the foreseeable future, and keep them in separate lists to avoid unnecessary updates. Most objects can migrate between static & dynamic after they've been created, but this has a performance cost. Static objects can be updated on demand if something changes (a way of saying there is a "dirty" flag at a macro level, if a static object changes, all static objects have to be updated)

##### Share on other sites

Having separate "dynamic" and "static" systems makes a lot of sense. Thanks for sharing your input :)

##### Share on other sites

Thanks for your replies. That's alot of usefull information. Seperating dynamic and static nodes is something I'm going to work on.

Thank you guys!

##### Share on other sites

you could also switch from deferred processing (set dirty flag and recalculate later) to immediate processing (call recalculate at the end of setpostion and move). then you don't need a dirty flag.

##### Share on other sites

we're moving to a static/dynamic paradigm,

i too tend to split the world up into static objects (terrain, buildings, trees, dropped inventory items, etc) and dynamic objects (people, vehicles, projectiles, etc), although sometimes i'll treat a short lived static object (such as a smoke emitter) as a dynamic object (such as a projectile).

for drawing i use the approach used in ogre 2.0, just calculate the word transform matrix on the fly each frame. but right now, i do it for both static and dynamic objects. i should pre-calc static once and save it for future use. but so far, brute force has been fast enough that i have't needed to pre-calc and store values.

i don't currently split data into arrays of component types as shown in the paper mentioned above. instead, i use an array of structs, where each struct contains all the component variables for an object.

apparently an array for each component type would be more cache friendly.

it also appears that for dynamic objects, an approach like:
turn_all                                 // uses array of rotation compnents
move_all                               // uses array of position components
update_worldmat_all            // uses array of world matrices

would be more cache friendly.

1. 1
2. 2
3. 3
4. 4
frob
12
5. 5

• 16
• 13
• 20
• 12
• 19
• ### Forum Statistics

• Total Topics
632172
• Total Posts
3004562

×