3D Theory - Using a scene graph for physics

Prerequisites

This page suggests how to store the physics information in a scenegraph.

If you are not familiar with this subject you may like to look at the following pages first:

Scenegraph

A lot of 3D renderers, libraries and file formats (for example VRML and Java3D) use a hierarchical scene graph, similar to the following, to represent a 3d world.

VRML and Java3D also have nodes for behaviour, however they only support simple repetitive behaviours and cant be easily expanded to model physics, I would like to work out a set of new nodes to model much more complex behaviour. I would like to suggest objects in the scene to move, collide and interact according to the laws of physics. These nodes are intended to provide high level behaviours for simulations and games, so that when people are designing their own programs they don't have to develop and distribute their own animation and physics engine.

Before proposing these new nodes, I have tried to check if there are any other proposed standards that I could use (I did not want to use proprietary standards, or programs that require native code to implement simple collisions, or patented standards like MPEG4). I made some inquiries on the VRML list and here is the thread. However I have not kept upto date with the standards work so I would be grateful if anyone could tell me about any relavent work.

Therefore in the absence of anything else I propose the following nodes:

Kinematics Dynamics Constraints collisionDetect collisionAction

The proposed nodes have the following functions

In order to try out these ideas I have implemented these nodes and used them to implement a simple game.

Modelling Motion

A scenegraph can be used to model motion, there is already a transform group which can allow translation and rotation. The behaviours need to modify these fields in every frame.

The behaviours built into Java3D don't seem to be appropriate, they require start and end points which would not be known in the general case, also these behaviours are not good at generating accelerations.

The event mechanisms built into VRML/X3D don't seem very good either, we need to be sure that the new translations and rotations are calculated in every frame, and the only way to do this would be if every VRML file contained specific code with complex physics calculations programmed individually for each application.

Proposed new Nodes

In order to calculate these we will need to hold parameters like, energy, mass, linear and angular momentum, c-of-mass, its second moment of mass, its elasticity, coefficient of friction.etc. Along with the shape information in the node.

Below is a suggestion for new nodes to be added to a VRML-like scene graph to implement the behaviour proposed.


Kinematics Node

This node controls the velocity and acceleration of the transformGroup above it in the scene graph. It generates events at each frame to modify the translation and rotation values of this TransformGroup. Futher information about kinematics.

VRML2 definition
Kinematics {
 field SFVec3f position
 field SFVec3f velocity
 field SFVec3f acceleration
 field SFVec4f angularPosition
 field SFVec3f angularVelocity
 field SFVec3f angularAcceleration
 field SFVec2f randomMinMax
 field SFVec3f initPosition
 field SFVec3f initVelocity
 field SFVec3f initAcceleration
 field SFVec4f initAngularPosition
 field SFVec3f initAngularVelocity
 field SFVec3f initAngularAcceleration
 field SFBool enable
 field SFBool rewind
} 

The velocities and distances are undated at each frame using the algorithm on this page.

Definition of Parameters for Kinematics Node:

Position

This is of type SFVec3f to represent the x,y and z components of the position, it represents the position of the point (0,0,0) in local geometry co-ordinates relative to the transform group above this.

This is an output which is automatically routed to the 'translation' variable of the TransformGroup which is the parent of this node. There is no need to explicitly have a route node to do this. It set to initDistance at the start of the simulation, then it is updated at each frame according to the algorithm on this page.

In addition to being updated from the velocity field at every frame, position may be changed by the constraint node.

For the physics see these pages: position and translation.

Velocity

This is of type SFVec3f to represent the x,y and z components of the velocity.

This is an output, set to initVelocity + a random factor defined by randomMinMax at the start of the simulation, then it is updated at each frame according to the equations above.

In addition to being updated from the acceleration field at every frame, velocity may be changed by the constraints and collision action nodes.

The reason for allowing a random factor is to allow a node to appear many times in a scene (by using DEF/USE, PROTO or Multiple Node) but to cause each instance of the node to start travelling in different directions. Each instance of the node will then have its own interactions, collisions etc. even though the object is defined only once.

For the physics of velocity see this page.

Acceleration

This is of type SFVec3f to represent the x,y and z components of the acceleration.

This is an output, set to initAcceleration at the start of the simulation.

The value of acceleration may change, as it will be affected by the dynamics node.

For the physics of acceleration see this page.

angularPosition

This is of type SFVec4f to represent a quaternion representing the orientation of the object. I know that VRML conventionally uses SFRotation to represent rotation in axis and angle format but I don't think axis and angle is practical for physics calculations. For the physics of angularPosition see this page.

This is an output which is automatically routed to the 'rotation' variable of the TransformGroup which is the parent of this node. There is no need to explicitly have a route node to do this. As the TransformGroup node is defined at present the SFVec4f / quaternion would have to be converted to SFRotation / axis angle at every frame, which is a big overhead. It would be better if the 'rotation' variable of the TransformGroup was changed to be a SFVec4f / quaternion.

It set to initAngularPosition at the start of the simulation, then it is updated at each frame according to the equations above.

angularVelocity

This is of type SFVec3f since angular velocity can be represented by a vector containing 3 numbers, angular velocity about the x axis, angular velocity about the y axis, and angular velocity about the z axis. For more information about the physics of angularPosition see this page.

This is an output, set to initAngularVelocity at the start of the simulation, then it is updated at each frame according to the equations above.

In addition to being updated from the angularAcceleration field at every frame, angularVelocity may be changed by the constraints and collision action nodes.

angularAcceleration

This is of type SFVec3f since angular acceleration can be represented by a vector containing 3 numbers, angular acceleration about the x axis, angular acceleration about the y axis, and angular acceleration about the z axis. For more information about the physics of angularVelocity see this page.

This is an output, set to initAngularAcceleration at the start of the simulation. The value of angular acceleration may change, as it will be affected by the dynamics node.

randomMinMax

If set this will add a random factor to the initial velocity. Without this each instance within a multiple would have a travel the same path. This will produce a velocity whose direction is random and whose magnitude is a random value between the two floating point numbers supplied.

initPosition

This is used at the start of the simulation to set the initial value of position, after that it plays no further part in the simulation while it is running, unless rewind is set to true when it will be used to set position again.

initVelocity

This is used at the start of the simulation to set the initial value of velocity (along with randomMinMax), after that it plays no further part in the simulation while it is running, unless rewind is set to true when it will be used to set position again.

initAcceleration

This is used at the start of the simulation to set the initial value of acceleration, after that it plays no further part in the simulation while it is running, unless rewind is set to true when it will be used to set position again.

initAngularDistance

This is used at the start of the simulation to set the initial value of angularDistance, after that it plays no further part in the simulation while it is running, unless rewind is set to true when it will be used to set position again.

initAngularVelocity

This is used at the start of the simulation to set the initial value of angular|Velocity, after that it plays no further part in the simulation while it is running, unless rewind is set to true when it will be used to set position again.

initAngularAcceleration

This is used at the start of the simulation to set the initial value of angularAcceleration, after that it plays no further part in the simulation while it is running, unless rewind is set to true when it will be used to set position again.

Enable

If enable is set to FALSE then the outputs will remain at their current values, if set to TRUE then the animation will proceed. This provides a kind of pause control for the animation.

Rewind

If enable is set to Then then all values will be set to their initial values.

Further Info

To see how to do this in the program goto kinematics tutor


Constraints Node

This node provides limits to the position and rotation of the transform group. This allows say:

  1. an arm to be created with realistic joint movements.
  2. An object being moved by a kinematics node to be constrained inside a box and bounce off the walls.
VRML2 definition
Constraints {
 field SFString constrainTranslation "noContraint","fixed","moveWithinBounds"
field SFVec3f minTranslation field SFVec3f maxTranslation field SFString constrainRotation "noContraint","fixed","moveWithinBounds" field SFVec4f minRotation field SFVec4f maxRotation field SFBool chain field SFString action "bounce","restart"
}
This node will constrain the values of its parent if it is a TransformGroup node. There is no need for a Route node to define this relationship.

Definition of Parameters for constraint node:

constrainTranslation

If this is set to "noContraint" then the translation value of the parent node will not be affected by this node. If set to "fixed" any change to the translation value of the parent node will be vetoed. If set to "moveWithinBounds" then the translation value will be constrained to be between minTranslation and maxTranslation.

minTranslation

If constrainTranslation is set to "moveWithinBounds" then minTranslation supplies the minimum x,y,and z values of the translation. The x,y and z values are constrained independently, i.e. the x value will be prevented from going below its minimum value, regardless of the values of y and z.

maxTranslation

If constrainTranslation is set to "moveWithinBounds" then maxTranslation supplies the maximum x,y,and z values of the translation. The x,y and z values are constrained independently, i.e. the x value will be prevented from going below its maximum value, regardless of the values of y and z.

constrainRotation

If this is set to "noContraint" then the rotation value of the parent node will not be affected by this node. If set to "fixed" any change to the rotation value of the parent node will be vetoed. If set to "moveWithinBounds" then the rotation value will be constrained to be between minRotation and maxRotation.

minRotation

If constrainRotation is set to "moveWithinBounds" then minRotation supplies the minimum value of the rotation. The comparison is done in terms of quaternions but the value is defined in VRML format.

maxRotation

If constrainRotation is set to "moveWithinBounds" then maxRotation supplies the maximum value of the rotation. The comparison is done in terms of quaternions but the value is defined in VRML format.

chain

If this is true, and the object attempts to move outside its constraints then, it will attempt to modify the TransformGroup above it in the scene graph. The aim of this is to provide a mechanism to allow inverse kinematics to be implemented.

action

This value defines what happens when the transform group is being moved by a kinematics node and it hits a constraint, If set to "bounce" then the velocity of the kinematics node will be changed to bounce, i.e. if it hits the top wall the y component of velocity will be reversed, but the y and z values will stay the same. If set to "restart" then when it hits a constraint then the kinematics values will be set back to their initial values..


Further Information about constaints

For theory see Joints


CollisionDetect Node

This node sets up a behavior to detect a collision between the shapes under its parent (usually a TransformGroup) and any other shape, when a collision is detected, then all collisionActions in this group will be sent a event. Unlike the VRML collision node this will detect a collision with any other node, not just the avitar.

VRML2 definition
CollisionDetect {
 field SFBool enable
 eventOut SFBool overlap
eventOut SFBool flag
eventIn SFBool clearFlag field SFNode other
field SFBool useGeometry eventOut SFVec3f impactLocation eventOut SFTime impactTime }

enable

If this is true then collision detect will be triggered if the shapes under the parent overlap with any other shapes, if this is false then no collision will be triggered.

overlap

This will remain true while there is any overlap of the shapes under the parent with any other shapes.

flag

This is triggered on the leading edge of overlap, in other words when overlap changes from false to true. Once triggered flag will remain true regardless of the state of overlap until clearFlag is set to true. It is also set to false when the animation starts or when the animation is rewound.

clearFlag

When set to true this will set flag to false.

other

Any collision involves 2 objects, a collision involving 3 or more objects will be treated as several instances of 2-way collisions. The value of other will point to the TransformGroup above the other shapes which have collided. If this TransformGroup has a collisionDetect Node then it will point back to this node.

useGeometry

If true the full goemetry information will be used to determine if there is any overlap with other nodes, if false then the bounding box will be used to determine if there is a collision. In other words, if useGeometry==false then a collision will be triggered when any other shape enters this bounding box, this saves a lot of CPU time when checking for collisions.

impactLocation

Location at which the impact happened in the local coordinates, this parameter is used to calculate the collosion response

impactTime

This privides a timestamp for when the impact occured, since collision is only tested in each frame, this will allow us to determine how far into the frame the collision occured, if there is a multiple (3 or more way) collision this will allow us to determine which collision occured first which is impotant to determine the collision responce.

Further Information

about collision detection
I need to give more thought to handling 3 or more way collisions. I think it may be better to hold a collision list, which would contain a list of 2-node pairs. Can anyone help me with this?


CollisionAction Node

This node sets up a behavior to detect a collision between its parent (usually a TransformGroup) and any other node, when a collision is detected then a message will be sent to each collisionAction in the group. The collisionAction will then check its 'collideWith' field to see if this is the type of collision that it is looking for, if it is then it will do the actions specified

VRML2 definition
CollisionAction {
   field MFString collideWith
field SFString actionThis "delete","reverse","stop"
field SFString actionOther "delete","reverse","stop"
field SFString CreateNew
field SFInt32 CreateNumber field SFString CreateAt "collide","initial"
field SFInt32 Counter }


If more actions are required than can be specified by adding moreCollisionAction nodes under the same TransformGroup.

The physics of collision responce is explained here.

Definition of Parameters for CollisionAction node:

collideWith

This allows a list of node names to be supplied. The actions will only be applied if the other node colliding with this has a name in this list. If this parameter is not present then any collisions with this node will be actioned.

actionThis

This specifies any actions to be taken to the parent of this node. If set to "delete" then this instance will be deleted (node this can only be done when these nodes are desended from a 'Multiple' node as it can only delete instances. If set to "reverse" and the node is being driven by a kinematics node, then the velocity value of the kinematics node will be reversed (x=-x, y=-y,z=-z). If set to "stop" then the game will be halted.

actionOther

This specifies any actions to be taken to the node that has collided with this. If set to "delete" then this instance will be deleted (node this can only be done when these nodes are desended from a 'Multiple' node as it can only delete instances. If set to "reverse" and the node is being driven by a kinematics node, then the velocity value of the kinematics node will be reversed (x=-x, y=-y,z=-z). If set to "stop" then the game will be halted.

createNew

This allows a new instance of a node to be created as a result of the collision. The value will specify the name of the 'Multiple' Node under which the new instance will be created.

createNumber

This only applies if 'createNew' is set. It allows mode that one instance to be created as specified by the value of this parameter. For instance you may want an object to break into two in a collision, or you may want to fire off a particle effect.

createAt

This only applies if 'createNew' is set. If set to "collide" then the new instance will be created at the place where the collision occurred, this allows one object to change into another object when it collides. If set to "initial" then the new instance will be created with the values specified by the initial values in its kinematics node.

counter

This contains a number which will be incremented every time a collision occurs..


Dynamics Node

This node controls the interaction of the object, for instance how it behaves when it collides with other objects.

If this node is present then it will modify the values in the kinematics node after a collision has occurred. This allows much more accurate physics bases collision. See here for more details .For instance, if the objects collide off centre then, the objects might go spinning off in a different direction.

VRML2 definition
Dynamics {
   field MFString collideWith
field SFFloat mass; field SFVec3f centreOfMass field SFMat inertiaMatrix field SFVec3f gravity; field SFString material; field SFVec3f solid; field SFVec3f friction;
}

Definition of Parameters for Dynamics Node:

collideWith

Specifies which collisions that this will apply to.

mass

Specifies the mass in Kg. of this object (all the shapes below the TransformGroup which is the parent of this node)

centreOfMass

Specifies the centre of mass, if it is different from (0,0,0) in local coordinates.

inertiaMatrix

A 3 by 3 matrix which defines how the object will respond to forces on it. The inertia matrix will depend on where the centre of rotation is. In other words, this is the inertia about a particular point. In this case the inertia matrix is about the centre-of-mass in which case the martix will be symmetrical about its diagonal.

Inertia is explained here.

gravity

Specify this to modify the behavior of kinematics node to accelerate objects towards the ground. If we are simulating behavior on the surface of the earth, then it would usually be (0.0 ,9.81, 0.0 ).

material

This would allow a library of materials to be defined to specify, parameters such as coeficient-of-friction, appearance, etc.

solid

This specifies how easily an object is deformed.

friction

This specifies the coeficient-of-friction of the object.

discussion on friction

Further Info

To see how to do this in the program goto dynamics tutor


Multiple Node

This node allows multiple instances of the structure below it to be created in the scene. These instances may be created with different positions, velocities or accelerations so that each instance behaves independently in the scene. Otherwise all the properties are identical, so they only need to be defined once.

In some ways this is like a group node, but there is only one definition of the structure below it, which is can be saved or loaded. Only at runtime are multiple copies created. Also, instances can be created or removed dynamically at runtime, for instance, when objects collide. This is a more efficient and flexible way to do simulations and particle effects than defining each particle/object separately.

Another way of looking at this is, an attempt to make the VRML structure more object oriented, so that you can define a class (the substructure under multiple node) and have multiple instances of this at runtime.

VRML2 definition
Multiple {
   field SFString type
   field SFInt32 initialInstances
   field SFVec3f maximumInstances
   eventIn addInstance
   eventOut removeInstance

}

Definition of Parameters for Multiple Node:

type

Not yet used

initialInstances

This defines how many of the instances are initially active (i.e. are visible on the screen, take part in collisions, are moved by kinematics node, etc.).

Once the program is running instances may be dynamically added or removed as as the result of events.

maximumInstances

Initially this number of instances are created in the scene graph, but only 'initialIntances' of them are active. The number of active instances may increase or decrease at runtime but it cannot be more than 'maximumIntances'

addInstance

This event will make an additional event active, provided that there is an inactive instance available to activate.

removeInstance

This event deactivates the specified instance.


Next Step and Further Reading

To see how these nodes could be used to implement a game goto this page
Further Information About Dynamics dynamics


metadata block
see also:
Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

cover If you are interested in 3D games, this looks like a good book to have on the shelf. If, like me, you want to have know the theory and how it is derived then there is a lot for you here. Including - Graphics pipeline, scenegraph, picking, collision detection, bezier curves, surfaces, key frame animation, level of detail, terrain, quadtrees & octtrees, special effects, numerical methods. Includes CDROM with code.

Commercial Software Shop

Where I can, I have put links to Amazon for commercial software, not directly related to this site, but related to the subject being discussed, click on the appropriate country flag to get more details of the software or to buy it from them.

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2017 Martin John Baker - All rights reserved - privacy policy.