#1 2015-02-01 21:29:05

gaya
Member

Rigidbody physics?

Can entities be affected by simple rigidbody physics? I want those crateboxes to fly away when i shoot them. :D

Offline

#2 2015-02-01 23:56:29

Hypernova^
Member

Re: Rigidbody physics?

The closest thing to this was the movable entities used in Sauerbraten singleplayer modes. Right now there is no rigid body collision support that I know of.

Last edited by Hypernova^ (2015-02-01 23:57:01)

Offline

#3 2015-02-02 01:11:17

angjminer
Member

Re: Rigidbody physics?

the code is so close to sauers it really shouldnt be a problem for you to get it going :)
ive still got  a way to go for what i want but here is proof you can do it:

http://youtu.be/v0lToovXuro

Offline

#4 2015-02-02 02:33:30

Hypernova^
Member

Re: Rigidbody physics?

Nice. I was working on a fake physics simulation for a Cube 2 game, it's cool how much you can do without actually needing a physics library :)

Also, Sandbox supports ragdolls being affected by explosions and such:

https://www.youtube.com/watch?v=uTD4KbOCSus

which would be a cool finishing touch to the ragdolls in Sauer/Tesseract.

Last edited by Hypernova^ (2015-02-02 02:54:15)

Offline

#5 2015-02-04 01:57:30

gaya
Member

Re: Rigidbody physics?

I'll try to integrate Bullet physics into tesseract. I'm not sure about performance, though. Converting the octree world into a bullet mesh might be very slow. And difficult.

Offline

#6 2015-02-04 03:04:53

Hypernova^
Member

Re: Rigidbody physics?

One thing to consider is how the physics in multiplayer will be handled. Since almost all game calculations are done client-side, small errors in the networking will create alot of problems, especially if physics objects affect the gameplay. I still can't think of a way to get around this.

Offline

#7 2015-02-04 13:44:57

angjminer
Member

Re: Rigidbody physics?

@gaya
the guy who was? working on the syntensity port of cube2 did it, i am using his as a reference, looks like he went a little over board, i like sleek and slim, i have found that some times 40 line can be condensed to 15-20, his code seems fairly well documented though, here is the link to his github:
https://github.com/kripken/intensityengine

Offline

#8 2015-02-04 14:37:18

spikeymikey0196
Member

Re: Rigidbody physics?

quite alot of physics in games are controlled by the Havok physics engine, so perhaps getting some  material on that could help?

Offline

#9 2015-02-04 21:15:55

chasester1
Member

Re: Rigidbody physics?

@hypernova
The reason that your physics hack is so randomly jittery and at times lacks any sense is because you are lacking proper physics management. Generally object are stuck throw a broad phase, narrow phase, then a solver phase, and then moved. cube physics does not do it this way rather, each object puts its self throw its own broad and narrow phase arbitrarily and then moves its self based on the results. So in Essence each object is treated like a static constant. Disregarding the input or impulse given by colliding objects to fix this problem you would need a proper structure or collision nodes (arbiters) and a proper solver to handle said nodes. Also better broad phase collision that handles more than x y plane orientation, and possibly aabb boxes to improve hit detection along with tri to tri detection for physic ents (non static and/or movable). This is all possible throw the current code if there was the correct structure to create and check the broad and narrow phase physics. The actual collision detection and impulse correction is all in place just angular velocity and the correct solver would have to be implemented.

I doubt any one would take the time to implement this properly. Plus once this was done things like vines (chained constraints) could be implemented by simply modifying the ragdoll code to allow for the proper impulsion

Offline

#10 2015-02-05 02:52:00

Hypernova^
Member

Re: Rigidbody physics?

:)

Hmm interesting. Currently, I'm just simulating physics enough to implement a Bioshock style telekenesis tool which interacts with entities such as pickup items, bouncers, and mapmodels. The game doesn't really need full physics at the moment.

Last edited by Hypernova^ (2015-02-05 13:46:09)

Offline

#11 2015-02-07 04:38:37

chasester1
Member

Re: Rigidbody physics?

in order to do that you will need full physics, or something just shy of it. You should be looking at angular rotation, inertia tensor, and angular momentum. These are the basics to 3d rotation. With out full physics you will be able to move objects in the world using only obb bounding boxes and aabb bounding boxes. Your per tri detection will be impossible on any moving object at this point. Plus all objects can only be moved by gun contact, or by this telekenesis tool. Honestly implementing a very limited or small physics engine would be more efficient and more powerful then any Jerry rigged mod that you could develop. Implementing your own in house physics structure based off a pre existing one would be easiest and more efficient.

cube has really reached a poimt where it needs basic full physics to expand its single player and multi player experience. Very few fps games can live with out physics.

Offline

#12 2015-02-12 23:58:49

angjminer
Member

Re: Rigidbody physics?

gaya wrote:

I'll try to integrate Bullet physics into tesseract. I'm not sure about performance, though. Converting the octree world into a bullet mesh might be very slow. And difficult.

it doesnt seem like its going to be that bad. it will be worth the time

this is a video of how long it takes to build the level collision mesh: http://youtu.be/0-V2vZ0HPtU

i borrowed the debug rendering code from the intensity port of sauerbraten (class SauerDebugDrawer; particle flares),the rest of the code is either mine,or already present.
intensity gets its va from void setupdata(vtxarray *va), in octarender, but i want more control.

this was shot on my ageing laptop that has an amd chipset.

hint: there is an uber quick exporter built into this thing, lightning quick actually,
have fun :)

Offline

#13 2015-02-13 07:46:08

Pritchard
Member

Re: Rigidbody physics?

How does it handle more complex level geometry? My map, Metric, is quite detailed in some places. You can find it on the forums here under the mapping section. My question is can it still perform as quickly as it does in your video when there are more tris to calculate?

Offline

#14 2015-02-13 13:57:34

angjminer
Member

Re: Rigidbody physics?

Pritchard wrote:

How does it handle more complex level geometry? My map, Metric, is quite detailed in some places. You can find it on the forums here under the mapping section. My question is can it still perform as quickly as it does in your video when there are more tris to calculate?

when my implementation is done, the mesh generation shouldnt take more than twice the time it takes to export an obj of the level. "/writeobj mylevel".

it has to be quick, because it will need to be done whenever you go in and out of edit.
maybe there needs to be an option for that? auto/manual

as far as load time for regular play goes however, there will be a serialize option to save the collision mesh. eg: " mylevel.bullet",,
that way for regular play it wont have to generate the level collision.

downloaded your map exported it, using that as a benchmark it shouldnt take more than 4-5 seconds, 10 at most, and this is on my laptop,

if you dont mind, when i get to that point ill use it in a benchmark video after i get some quirks worked out.

PS. to the devs, I am trying to keep the main source as pure as possible, so it will plug in and run alongside the original physics, and still be usable........for now. when i get to the point of needing to be more invasive, ill make an archive for anyone who is interested to play with it. and someone will have to update the makefile for windows, update for mac.

Offline

#15 2015-02-14 02:07:21

chasester1
Member

Re: Rigidbody physics?

the following is the code i wrote/borrowed from an engine that outlines just the management potion of the physics, I could help impliment a full physics, but when it comes to the actual physics is where i get lost. If you wish to collaborate i could write the management potion of a physics engine if you could handle the actual physics and hit detection. The following code basically would handle the base classes (for each model), the overarching prune and sweep sorting algorithem, and broad and narrow phase implimentation.

What would need added would be the actual collision and collision detection, most likely a aabb/oob detection for broad phase, and a tri detection for narrow phase detection. (the aabb class references can be ignored, because they are not linked in at this point).

But you can use this as you will, and if you need help I would be more than willing :)

chasester

ps: the code is missing more essensial parts that would needed to be added once detection was finished. But it is a good start.



//global test vars

#define getHead(a,b,c) a *b = c;
#define setNextHead(a) a = a->next;
#define loopHead(a,b) while(a){ b; setNextHead(a); }
#define setNewHead(a,b) {a->next = b; b = a;}
#define getContactHead getHead(Contact, contact, contacts)

const float POSITIVE_INFINITY = FLT_MAX;
const float NEGITIVE_INFINITY = FLT_MIN;

#define MAX_TIME_PER_FRAME 100
uint nextShapeID = 0;
uint nextBodyID = 0;

//Determinds the amount of simulated tests, will be later a comand out to allow for lower level physics in less inportant spaces
const int HIGH_ITERATIONS = 20;
const int MEDIUM_ITERATIONS = 10;
const int LOW_ITERATIONS = 5;
//
const float NORMAL_DAMPING = 0.99f; //amount of damping applied to body velocity each physics step
int PRE_CREATE_POOL_SIZE = 0; //amount of pre created poolable objects - add in later to look at map file and precreate object based on entitys
bool outputstats = false; //render physics stats to screen;
//ARBITERS
float BIAS_COEF = 0.1;
float COLLISION_SLOP = 0.1;
enum SHAPE_TYPES {AXIS_ALIGNED_AABB_SHAPE=0, SPHERE_SHAPE, RAY_SHAPE,OBB_SHAPE,TRI_SHAPE};
enum PHYSICS_TYPES{STATIC_BODY=0,DYNAMIC_BODY,FIXED_DYNAMIC_BODY};

//Geometric Shape
const float AREA_MASS_RATIO = 1 / 100;
//Material *DEFAULT_MATERIAL = new Material()
//RidgidBody
const float SLEEP_EPSILON = 0.0001f;
//static uint nextBodyID = 0;



struct Ray {
	vec o;
	vec d;
	Ray() : o(0), d(0) {}
};
struct Material {
	float density;
};


struct ICollide {

};
struct Collide : ICollide {

};

struct Contact {
	vec p, n; //24
	float dist; //28
	vec r1, r2, r1n, r2n; //76
	float nMass, tMass, bounce; //88
	float jnAcc, jtAcc, jBias, bias; //104
	uint hash; //108
	bool updated;//109
	Contact *next;//113

	Contact() : nMass(0), tMass(0), bounce(0), jnAcc(0), jBias(0), bias(0) {}
	void reset(uint _hash = 0){
		hash = _hash;
		jnAcc = jtAcc = 0;
	}

	//const char *toString(){defformatstring(abc)("Contact: p=%s n=%s dist=%f jnAcc=%f jtAcc=%f", "p.tostring()", "n.tostring()", dist, jnAcc, jtAcc);  return abc;}
};//113 = 128 = add 15 more bytes



;



struct RidgidBody;
struct Space;

struct GeometricShape{
	/**
	* These static constants are use for fast type checking by the shapeType member variable.
	*/
	uchar shapeType; //1
	RidgidBody *body; // 5
	vec offset, surface_v; //29
	bool isSensor; //30
	//add in a colision class
	uint shapeID; //34
	Material *material; //38
	float area; //42
	int referenceCount; //46
	GeometricShape *next, *prev;//54
	float mass; //58
	GeometricShape *nchild; //62;
	//+2 for all inharent structs
	
	GeometricShape(uchar _shapeType, Material *_material = DEFAULT_MATERIAL) : shapeType(_shapeType), material(_material), 
		shapeID(nextShapeID++), area(0), surface_v(0), isSensor(false), body(NULL), mass(getmass()) {}
	virtual void updateShape(vec p, vec rot) {}
	virtual bool initShape(){ return false; }
	void update() { updateShape(body->p, body->rot); }
	//void registerBody(RidgidBody *_body) { body = _body; }
	void registerBody(RidgidBody *);
	void unregisterBody(){body = NULL;}
	inline float getmass(){ return area*AREA_MASS_RATIO*material->density; }
	//public static function sortOnAABBDecending(a : GeometricShape, b : GeometricShape) : Number{
	//	var aTop : Number = a.aabb.t;
	//	var bTop : Number = b.aabb.t;
	//	if (aTop < bTop) {
	//		return -1;
	//	}
	//	return 1;
	//}
	//ADD CORISPONDING FUNCTION;
	
	virtual bool contiansPoint(vec point) { return false; }
	virtual bool intersectRay(Ray ray) { return false; }
	virtual bool intersectRaySegment(Ray ray) { return false; }
	virtual float calculateInertia(float m, vec offset){ return 1.f; }
};//54 = 64

struct Arbiter{
	Contact *contacts; //4
	GeometricShape *a, *b; //12
	float u, e; //20
	vec target_v; // 32
	//int stamp
	//int count
	uchar id1, id2; //34
	float bais_coef, collision_slop; //42 //46 - x = 32 x = 14
	bool updated, sleeping, isSensor;
	Arbiter *next; //46
	int stamp; //50
	Arbiter() : contacts(NULL), a(NULL), b(NULL), bais_coef(BIAS_COEF), collision_slop(COLLISION_SLOP), target_v(0), updated(false),
		sleeping(false), isSensor(false), next(NULL), u(0), e(0) {}

	void assign(GeometricShape &a, GeometricShape &b){
		this->a = &a;
		this->b = &b;
		u = e = 0;
		target_v = vec(0);
	}

	//const char * toString(){ return "BodyA=%d Type=%d\n BodyB=%d Type=%d\n Contacts=\n"; /* add return all contacts once contact class is contructed; add sumimpulses().toString() when added */}

	vec sumImpulses() {
		vec sum;
		getContactHead
			loopHead(contact, { sum.add(contact->n.mul(contact->jnAcc)); });
		return sum;
	}

	vec sumImpulsesWithFriction(){
		vec sum;
		getContactHead
			loopHead(contact, { sum.add(vec().cross(contact->n, vec(contact->jnAcc))); });
		return sum;
	}

	void injectContact(vec, vec, float, float, uint);
	void preStep(float dt_inv){
		//RidgidBody *bodyA = a->body;
	}
	void applyImpulse(){}
}; //46 = 64 bytes
struct ArbiterProxy{
	ArbiterProxy *next, *prev;
	Arbiter *arbiter;
	bool sentinel;
};

struct RidgidBody{
	float m, m_inv, in, in_inv; //16
	vec p, v, f, v_bias, rot; //76
	float maxVelScalar, maxVelScalarSqr; //84 posibly remove; cache values
	bool canSleep, isSleeping; //84.2
	uint checked; //86
	float motion, bias; //94
	//angular components
	float /*a,*/ w, t, w_bias; //probably needs updated 106
	Space *space; //110
	ArbiterProxy *arbiters; //114
	float storedInertia; //118
	uchar colisionType; //119
	//ushort group; 
	bool isFixed, isStatic, calcMassInertia; //119.4
	GeometricShape *memberShapes; //123
	ushort bodyID; //126
	RidgidBody *next, *prev;//136 - 128 = 8 remove;
	uint collisionProcessingMask;

	RidgidBody(uchar type = DYNAMIC_BODY, float _m = -1, float _i = -1) : m(_m), in(_i), maxVelScalar(1000), calcMassInertia((m < 0) || (in < 0)),
		maxVelScalarSqr(1000 * 1000), motion(0.0002f), bias(0.99332805041467), storedInertia(-1), bodyID(nextBodyID++) {
		switch (type){
		case STATIC_BODY:
			isStatic = true;
			isFixed = true;
			break;
		case DYNAMIC_BODY:
			isStatic = false;
			isFixed = false;
			break;
		case FIXED_DYNAMIC_BODY:
			isStatic = false;
			isFixed = true;
		}
		if (isStatic){
			calcMassInertia = false;
			setMass(POSITIVE_INFINITY);
			setMomement(POSITIVE_INFINITY);
		}
		else if (!calcMassInertia){
			setMass(m);
			setMomement(in);
		}

		float a = w = t = w_bias = 0;
		memberShapes = NULL;

		arbiters = new ArbiterProxy();
		arbiters->next = arbiters;
		arbiters->prev = arbiters;
		arbiters->sentinel = true;
		setAngle(0);
	}

	void registerSpace(Space *_space){ space = _space; }
	void unregisterSpace(){ space = NULL; }

	void addShape(GeometricShape *shape, bool updateMI = true){
		shape->registerBody(this);
		//setNewHead(shape, memberShapes)
		shape->prev = memberShapes->prev;
		memberShapes->prev = shape;
		shape->next = memberShapes;
		memberShapes = shape;

		if (space)space->addShape(shape);

		if (calcMassInertia && updateMI) calculateMassInertia();
		//return shape;
	}
	bool removeShape(GeometricShape *shape, bool updateMI = true) {
		GeometricShape *geoShape = memberShapes;
		loopHead(geoShape, { if (geoShape == shape) break; })
		if (!geoShape) return false;
		space->removeShape(geoShape);
		//delete geoShape;
		if (calcMassInertia && updateMI) calculateMassInertia();
		return true;
	}
	void addArbiter(Arbiter *arb){
		ArbiterProxy *newProxy;
		if (arbiterProxyPool){
			newProxy = arbiterProxyPool;
			arbiterProxyPool = arbiterProxyPool->next;
		}
		else { newProxy = new ArbiterProxy; }
		newProxy->arbiter = arb;

		newProxy->prev = arbiters;
		newProxy->next = arbiters->next;
		arbiters->next = newProxy;
		newProxy->next->prev = newProxy;
	}

	Arbiter *getArbiter(uint id1, uint id2){
		ArbiterProxy *arbProxy;
		for (arbProxy = arbiters->next; arbProxy->sentinel != true; arbProxy = arbProxy->next){
			if ((arbProxy->arbiter->id1 == id1) && (arbProxy->arbiter->id2 == id2)) return arbProxy->arbiter;
			if ((arbProxy->arbiter->id1 == id2) && (arbProxy->arbiter->id2 == id1)) return arbProxy->arbiter;
		}
	}
	bool removeArbiter(Arbiter *arb){
		ArbiterProxy *arbProxy;
		for (arbProxy = arbiters->next; arbProxy->sentinel != true; arbProxy = arbProxy->next){
			if (arbProxy->arbiter == arb){
				arbProxy->prev->next = arbProxy->next;
				arbProxy->next->prev = arbProxy->prev;
				arbProxy->next = arbiterProxyPool;
				arbiterProxyPool = arbProxy;
				return true;
			}
		}
		return false;
	}
	void setMass(float _m){ m = _m;  m_inv = 1 / m; }
	void setMomement(float i) { in = i; in_inv = 1 / i; }
	bool rotationLock(bool v, bool set = true){ if (set){ storedInertia = v ? in : -1; setMomement(v ? POSITIVE_INFINITY : storedInertia); } return (storedInertia != 1); }
	void setMaxVelocity(float mv){ maxVelScalar = mv >= 0 ? mv : -1; maxVelScalarSqr = mv >= 0 ? mv*mv : -1; }

	void calculateMassInertia(){
		float newmass = 0.f;
		float newMomementInertia = 0.f;
		GeometricShape *shape;

		loopHead(memberShapes, { newmass += shape->mass; newMomementInertia += shape->calculateInertia(shape->mass, shape->offset); })
			setMass(newmass);
		setMomement(newMomementInertia);
	}
	void setAngle(float _a){ _a = fmod(_a, 6.28318430717f); rot.set(cos(_a), sin(_a), tan(_a)); } //change to update to 3d use vecfromyawpitch command
	void slew(vec pos, float dt){ v = vec(p).sub(pos).mul(1 / dt); }

	void updateVelocity(vec persistantMasslessForce, vec force, float damping, float dt){
		if (isSleeping || isFixed) return;
		loopi(3)v[i] = (v[i] * damping) + ((persistantMasslessForce[i] + ((force[i] + f[i]) * m_inv)) * dt); //loop magic :)
		w = (w * damping) + (t * in_inv * dt);
		checked = 0;
		if (maxVelScalarSqr > 0){
			float scalarVelocitySqr = v.x*v.x + v.y*v.y + v.z*v.z;
			if (scalarVelocitySqr > maxVelScalarSqr) {
				v.mul(maxVelScalar / sqrt(scalarVelocitySqr));
			}
		}
	}
	void UpdatePosition(float dt){
		loopi(3)p[i] += ((v[i] + v_bias[i])*dt);
		motion = (bias * motion) + ((1 - bias) * (v.x*v.x + v.y*v.y + v.z*v.z + w*w));
		if (motion > (10 * SLEEP_EPSILON)) motion = 10 * SLEEP_EPSILON;
		canSleep = motion < SLEEP_EPSILON;
		isSleeping = canSleep;
		setAngle(0 + ((w + w_bias)*dt)); // replace with 3d algorithm
		v_bias.set(0, 0, 0);
		w_bias = 0;
	}
	void sleep(){
		v.set(0, 0, 0);
		w = 0;
		isSleeping = true;
		ArbiterProxy *arbProxy;
		for (arbProxy = arbiters->next; arbProxy->sentinel != true; arbProxy = arbProxy->next)
			arbProxy->arbiter->sleeping = true;
	}
	void wake(int stamp){
		motion = 10 * SLEEP_EPSILON;
		canSleep = isSleeping = false;
		ArbiterProxy *arbProxy;
		for (arbProxy = arbiters->next; arbProxy->sentinel != true; arbProxy = arbProxy->next){
			arbProxy->arbiter->sleeping = false;
			arbProxy->arbiter->stamp = stamp;
		}
	}
	void resetForces(){
		f.set(0, 0, 0);
		t = 0;
	}
	void ApplyBiasImpulse(vec j, vec r){
		loopi(3)v_bias[i] = j[i] * m_inv;
		//w_bias += i_inv * (r*)
		//some crazy version of dot product?? x1*y2 - x2*y1; figer out 3d equivalant
	}
	void ApplyForces(vec force, vec r){
		if (isSleeping)wake(space->stamp);
		loopi(3)f[i] = force[i] * m_inv;
		//w_bias += i_inv * 
		//some crazy version of dot product?? x1*y2 - x2*y1; figer out 3d equivalant
	}
	void onStep(int dt){
		return;
	}
	//listeners
	void onStartCollision(RidgidBody *body) {}
	void onCollision(RidgidBody *body){}
	void onEndCollision(RidgidBody *body){}
};//done;





//look at removing 14 bytes from arbiter







struct BodyContact
{
	short contactCount; //2
	RidgidBody *bodyA; //4
	RidgidBody *bodyB; //8
	bool startContact;
	bool endContact;
	bool sentinel;
	BodyContact *next; //12
	BodyContact *prev; //16

	BodyContact() : /*contactCount(0),*/ next(NULL), prev(NULL) {}
}; //16 bytes

Contact *contactPool = NULL;
Arbiter *arbiterPool = NULL;
ArbiterProxy *arbiterProxyPool = NULL;
BodyContact *bodyContactPool = NULL;

Material *DEFAULT_MATERIAL = new Material();


RidgidBody *DEFUALT_STATIC_BODY = new RidgidBody();

struct Space
{
	vec force; //replace later with a manager that handles forces
	vec masslessforce; //gravity
	int iterations; //amount of irrations per step
	int frame; //physics frame counter
	int stamp; //time stamp for consol out commands and debuging
	RidgidBody *activeBodies;
	RidgidBody *staticBodies;
	int activeBodiesCount; // consol output
	int staticBodiesCount; // consol output
	GeometricShape *activeShapes;
	GeometricShape *staticShapes;
	int activeShapesCount;
	int staticShapesCount;
	bool staticSyncRequired;
	//public var bodyContactDict : Dictionary;
	Arbiter *arbiters;
	BodyContact *bodyContacts;
	int narrowPhaseTime;
	int broadPhaseTime;
	int solvePhaseTime;

	int fps, pps, dt, dt_inv;
	float calcdamping, damping;
	int tps, curtime, deltatime, accumulator;
	ICollide collider;
	Space(int _fps, int _pps)
	{
		bodyContacts = new BodyContact();
		bodyContacts->next = bodyContacts;
		loopi(PRE_CREATE_POOL_SIZE){
			Arbiter *newArbiter = new Arbiter();
			newArbiter->next = arbiterPool;
			arbiterPool = newArbiter;

			Contact *newContact = new Contact();
			newContact->next = contactPool;
			contactPool = newContact;
		}
		//Reset The Shapes Counters
		nextShapeID = 0;
		nextBodyID = 0;

		fps = _fps;
		pps = _pps;
		tps = 1000.f / pps; //ticks per second
		dt = 1.f / pps;
		dt_inv = 1.0f / dt;

		iterations = HIGH_ITERATIONS;
		damping = NORMAL_DAMPING;
		
		force = vec(0);
		masslessforce = vec(0);

		stamp = 0;
		frame = 0;

		addRidgidBody(DEFUALT_STATIC_BODY);
	}

	void setDamping(float _dmp){
		damping = _dmp;
		calcdamping = pow(1.f / damping, -dt);
	}

	void step(int newtime){
		frame++;
		//set up time info
		//int newTime = 0;
		deltatime = newtime - curtime;
		curtime = newtime;

		if (deltatime > MAX_TIME_PER_FRAME) deltatime = MAX_TIME_PER_FRAME;

		RidgidBody *body = staticBodies;
		while (body){
			body->onStep(deltatime);
			body = body->next;
		}
		body = activeBodies;
		while (body){
			body->onStep(deltatime);
			body = body->next;
		}

		//now run physics
		accumulator += deltatime;
		while (accumulator >= tps){
			accumulator -= tps;
			physicsStep();
		}
		processBodyContacts();
		execIntervalFuctions();
	}
	
	/**
	* This function is the core of the entire engine.
	* All collition detection and resolution is execued from here.
	*/

	void physicsStep(){
		GeometricShape *shape;
		RidgidBody *body;
		Arbiter *arbiter;
		
		//addforces later
		//Force ForceGen;
		//forceGen = forces;
		//while (forceGen){ if (forceGen->active)forceGen->eval(); forceGen= forceGen.next;}

		body = activeBodies;
		while (body){ body->updateVelocity(masslessforce, force, calcdamping, dt); body = body->next; }

		while (shape){ if (!shape->body->isSleeping)shape->update(); shape = shape->next; }
		
		broadPhase();

		/*
		* This block does two things:
		* 1) It removes old arbiters ( >3 steps old) from the arbiters
		* 2) It calls preStep for the remaning arbiters.
		*/
		arbiter = arbiters;
		Arbiter *lastArbiter;
		RidgidBody *a, *b;
		while (arbiter){
			if (!arbiter->sleeping){
				if ((stamp - arbiter->stamp) > 3){
					a = arbiter->a->body; b = arbiter->b->body;
					a->removeArbiter(arbiter);
					b->removeArbiter(arbiter);
					if (a->isSleeping) wakeBody(a);
					if (b->isSleeping) wakeBody(b);

					//uint bodyHash = (a->bodyID < b->bodyID) ? (a->bodyID << 16) | b->bodyID : (b->bodyID << 16) | a->bodyID;
					Contact *contact = arbiter->contacts;
					Contact *nextContact;
					while (contact){
						nextContact = contact->next;
						contact->next = contactPool;
						contactPool = contact;
						contact = nextContact;
					}
					Arbiter *thisArbiter = arbiter;
					if (arbiter == arbiters) arbiter = arbiters = arbiter->next;
					else if (arbiters->next == NULL) arbiter = lastArbiter->next = NULL;
					else arbiter = lastArbiter->next = arbiter->next;

					thisArbiter->next = (arbiterPool == NULL) ? NULL : arbiterPool;
					arbiterPool = thisArbiter;
					continue;
				} else  arbiter->preStep(pps); 
			}
			lastArbiter = arbiter;
			arbiter = arbiter->next;
		}
		//do constraints
		
		//This is where the engine spends 70% of its time.

		loopi(iterations){
			arbiter = arbiters;
			while (arbiter){
				if (!arbiter->sleeping)arbiter->applyImpulse();
				arbiter = arbiter->next;
			}
			//do constraints
		}
		body = activeBodies;
		while (body){
			if (!body->isSleeping){
				body->UpdatePosition(dt);
				body->resetForces();
			}
			body = body->next;
		}
		force = vec(0.f);
	}
	GeometricShape *sort(GeometricShape *head){
		if (!head) return NULL;
		GeometricShape *h = head, *p, *n, *m, *i;
		n = h->next;
		while (n) {
			m = n->next;
			p = n->prev;

			if (p->aabb->t > n->aabb->t) {
				i = p;

				while (i->prev) {
					if (i->prev->aabb->t > n->aabb->t)
						i = i->prev;
					else
						break;
				}
				if (m) {
					p->next = m;
					m->prev = p;
				}
				else
					p->next = NULL;

				if (i == h) {
					n->prev = NULL;
					n->next = i;

					i->prev = n;
					h = n;
				}
				else {
					n->prev = i->prev;
					i->prev->next = n;

					n->next = i;
					i->prev = n;
				}
			}
			n = m;
		}
		return h;
	}
	
	void broadPhase(){
		activeShapes = sort(activeShapes);
		GeometricShape *shape1=activeShapes, *shape2, *shape3, *shape4 = staticShapes;

		while (shape1){
			shape2 = shape1->next;
			while (shape2){
				if (shape2->AABB->t > shape1->AABB->b) break;
				if (shape1->AABB->r >= shape2->AABB->l) narrowPhase(shape1, shape2);
				shape2 = shape2->next;
			}
			while (shape3){
				if (shape3->AABB->t > shape1->AABB->b) break;
				if (shape3->AABB->t <= shape3->AABB->b) if (shape1->AABB->t <= shape3->AABB->b)break;
				shape3 = shape3->next;
			}
			shape4 = shape3;
			while (shape4){
				if (shape4->AABB->t > shape1->AABB->b) break;
				if (shape1->AABB->l <= shape4->aabb->r) if (shape1->AABB->r >= shape4->AABB->l) narrowPhase(shape1, shape4);
				shape4 = shape4->next;
			}
			shape1 = shape1->next;
		}
	}

	void syncBroadphase(){ staticShapes = sort(staticShapes); }

	GeometricShape getShapeAtPoint(vec point) {}

	bool castRay(Ray ray){}

	GeometricShape findCloestShape(vec origin, const GeometricShape &head){}

	void processBodyContacts(){
		BodyContact *bodyContact;

		for (bodyContact = bodyContact->next; bodyContact->sentinel != true; bodyContact = bodyContact->next){
			if (bodyContact->bodyA->collisionProcessingMask) {
				if ((bodyContact->bodyA->collisionProcessingMask & 1) && (bodyContact->startContact)) bodyContact->bodyA->onStartCollision(bodyContact->bodyB);
				if ((bodyContact->bodyA->collisionProcessingMask & 2)) bodyContact->bodyA->onCollision(bodyContact->bodyB);
				if ((bodyContact->bodyA->collisionProcessingMask & 4) && (bodyContact->endContact)) bodyContact->bodyA->onEndCollision(bodyContact->bodyB);
			}

			if (bodyContact->bodyB->collisionProcessingMask) {
				if ((bodyContact->bodyB->collisionProcessingMask & 1) && (bodyContact->startContact)) bodyContact->bodyB->onStartCollision(bodyContact->bodyA);
				if ((bodyContact->bodyB->collisionProcessingMask & 2)) bodyContact->bodyB->onCollision(bodyContact->bodyA);
				if ((bodyContact->bodyB->collisionProcessingMask & 4) && (bodyContact->endContact)) bodyContact->bodyB->onEndCollision(bodyContact->bodyA);
			}

			bodyContact->startContact = false;

			if (bodyContact->endContact){
				bodyContact->prev->next = bodyContact->next;
				BodyContact *pointer = bodyContact->next->prev = bodyContact->prev;
				bodyContact->next = bodyContactPool;
				bodyContactPool = bodyContact;
				bodyContact = pointer;
			}
		}
	}

	bool narrowPhase(GeometricShape *s1, GeometricShape *s2){
		if (s1->body == s2->body)return false;
		
		//check if on the same layer 
		//removed may add later
		
		//check if in same group
		//removed may add later

		RidgidBody *highBody = s1->body->bodyID > s2->body->bodyID ? s1->body : s2->body;
		Arbiter *pairArbiter = highBody->getArbiter(s1->shapeID, s2->shapeID);
		bool pairFound = pairArbiter != NULL;
		if (pairFound){
			if (pairArbiter->stamp == stamp) return true;
			if (pairArbiter->sleeping)return true;
		} else {
			pairArbiter = arbiterPool ? arbiterPool : arbiterPool = new Arbiter();
			pairArbiter->isSensor = s1->isSensor || s2->isSensor;
		}

		//narrow phase collision detection
		if (s1->shapeType > s2->shapeType){
			GeometricShape *ts = s1;
			s1 = s2;
			s2 = ts;
		}
		bool collided;
		//finde type of each shape
		//do test based on type
	}

	void addRidgidBody(RidgidBody *body){
		RidgidBody *bodies = body->isStatic ? staticBodies : activeBodies;

		if (bodies == NULL){
			bodies = body;
			body->next = bodies->prev = NULL;
		} else {
			body->next = bodies;
			body->prev = NULL;
			bodies->prev = body;
			bodies = body;
		}

		if (body->isStatic){
			staticBodiesCount++;
			addShapes(body->memberShapes);
			staticBodies = bodies;
		} else {
			activeBodiesCount++;
			addShapes(body->memberShapes);
			activeBodies = bodies;
		}
		
		body->registerSpace(this);
	}

	bool removeRidgidBody(RidgidBody *body){
		if (!body)return false;
		GeometricShape *shape;
		RidgidBody *bodies = body->isStatic ? staticBodies : activeBodies;
		GeometricShape *shapes = body->isStatic ? staticShapes : activeShapes;

		body->wake(stamp);

		if (!body->prev){
			bodies = body->next;
		} else {
			body->prev->next = body->next;
		}
		if (body->next){
			body->next->prev = body->prev;
		}
		short i = 0;

		while (body->memberShapes){
			shape = body->memberShapes;
			body->memberShapes = body->memberShapes->nchild;
			if (!shape->prev){
				shapes = shape->next;
			}
			else {
				shape->prev->next = shape->next;
			}
			if (shape->next){
				shape->next->prev = shape->prev;
			}
			delete shape;
			shape = NULL;
			i++;
		}
		
		if (body->isStatic){
			staticBodiesCount--;
			staticShapesCount -= i;
			staticBodies = bodies;
			staticShapes = shapes;
		} else {
			activeBodiesCount--;
			activeShapesCount -= i;
			activeBodies = bodies;
			activeShapes = shapes;
		}
		return true;
	}
	bool addShape(GeometricShape *shape){
		if (!shape) return false;
		if (shape->body->isStatic){
			if (!staticShapes){ staticShapes = shape; shape->next = shape->prev = NULL; }
			else { shape->next = staticShapes; staticShapes->prev = shape; staticShapes = shape; } 
			staticShapesCount++; staticSyncRequired = true;
	   }else{
			if (!activeShapes){ activeShapes = shape; shape->next = shape->prev = NULL;}
			else { shape->next = activeShapes; activeShapes->prev = shape; activeShapes = shape; }
			activeShapesCount++;
		}
		shape->update(); return true;
	}
	void addShapes(GeometricShape *head){while (addShape(head)){ head = head->nchild; }}
	bool removeShape(GeometricShape *shape){
		if (!shape)return false;
		if (shape->body->isStatic){
			if (!shape->prev) staticShapes = shape->next;
			else			  shape->prev->next = shape->next;
			if (shape->next)  shape->next->prev = shape->prev;

			delete shape;
			shape = NULL;
			staticShapesCount--;
			staticSyncRequired = true;
	  } else {
			if (!shape->prev) activeShapes = shape->next;
			else			  shape->prev->next = shape->next;
			if (shape->next)  shape->next->prev = shape->prev;

			delete shape;
			shape = NULL;
			activeShapesCount--;
		}
	}

	void execIntervalFuctions(){ if (frame % 30 == 0) sleepBodys(); }


	//had to convert ARRAY TO VECTOR MAY THROW NULL PTR ERROR LOOK IF ERROR IN THIS FUNCTION;
	void wakeBody(RidgidBody *body2Wake){
		vector<RidgidBody *> stack;
		ArbiterProxy *arbProxy;
		int stackSize;
		RidgidBody *body;

		stack[0] = body2Wake;
		stackSize = 1;
		
		while (stackSize > 0){
			body = stack[--stackSize];
			if (body->checked == 9999999) continue;
			body->checked = 9999999;
			body->wake(stamp);
			for (arbProxy = body->arbiters->next; arbProxy->sentinel != true; arbProxy = arbProxy->next) {
				RidgidBody *other = (arbProxy->arbiter->a->body == body) ? arbProxy->arbiter->b->body : arbProxy->arbiter->a->body;
				if (other->isStatic) continue;
				if (other->checked == 9999999) continue;
				stack[stackSize++] = other;
			}
		}
		delete &stack; //i imagine thats correct
	}

	void sleepBodys() {
		RidgidBody *seed;
		ArbiterProxy *arbProxy;
		vector<RidgidBody *> stack;
		int stackSize;
		vector<RidgidBody *> sleepList;
		int sleepListSize;
		RidgidBody *body;
		uint seedID;

		for (seed = activeBodies; seed != NULL; seed = seed->next){
			if (seed->isSleeping)continue;
			stack[0] = seed;
			stackSize = 1;
			sleepListSize = 0;
			seedID = seed->bodyID;
			while (stackSize > 0 )
			{
				body = stack[--stackSize];

				if (!body->canSleep){ sleepListSize = 0; body->checked = seedID; break; }
				if (body->checked > 0){
					if (body->checked == seedID) continue;
					sleepListSize = 0;
					body->checked = seedID;
					break;
				}
				body->checked = seedID;
				sleepList[sleepListSize++] = body;
				for (arbProxy = body->arbiters->next; arbProxy->sentinel != true; arbProxy = arbProxy->next){
					RidgidBody *other = (arbProxy->arbiter->a->body == body) ? arbProxy->arbiter->b->body : arbProxy->arbiter->a->body;
					if (other->isStatic) continue;
					stack[stackSize++] = other;
				}
			}
			loopj(sleepListSize){
				RidgidBody *bb = sleepList[j];
				bb->sleep();
			}
		}
	}
	void cullOutOfBounds(){return;} //later check world bounds
};

void Arbiter::injectContact(vec p, vec n, float nCoef, float dist, uint hash){
	if (isSensor) return;
	getContactHead
		loopHead(contact, { if (hash == contact->hash)break; });
	if (!contact){
		if (contactPool == NULL) contact = new Contact();
		else{
			contact = contactPool;
			//setNextHead(contactPool)
			contactPool = contactPool->next;
		}
		setNewHead(contact, contactPool)
			contact->reset(hash);
	}
	contact->p = vec(p);
	contact->n = vec(n).mul(nCoef);
	contact->dist = dist;
	contact->updated = true;
}

void GeometricShape::registerBody(RidgidBody *_body) { body = _body; }

Offline

Board footer