Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 30 Aug 2006
Online Last Active Today, 02:09 PM

#5274527 Finding usable normals from complex embedded sphere-tri situations. Try to po...

Posted by JoeJ on 05 February 2016 - 03:13 PM

I know the algorithm you describe under 'Voroni region' based collision detection.
The first source i'm aware is Brian Mirtichs V-Clip implementation, he also wrote a paper.
It can find closest features between convex nonintersecting polyhedra, your example (point and convex polyhedra) is a case of this.

The problems will begin when the triangle mesh is not convex, and / or the sphere center crosses its surface,
so it becomes harder to find a correct displacement direction.

#5273235 Lightmap theory and rendering

Posted by JoeJ on 29 January 2016 - 01:04 PM

Broad question,
you need automatic UV unwrapping.
You need to think of how you wanna store directional information to support bump mapping (Spherical Harmonics, primary light direction...)
You need to decide a method to calculate light per texel (radiosity solver, rastering enviroment maps...)
You need to store probes for dynamic objects and decide how to stre data hod haw to place them (automatic, manual)

Each topic worth its own tutorial, chapter or thread - but i don't know any book covering this as a whole.
The good thing is that none of those things is hard to do and it's always possible to change various details later on.
You may wanna narrow the question to the things you do not know about.

#5272961 ComputeShader Performance / Crashes

Posted by JoeJ on 28 January 2016 - 02:26 AM

You modify shared memory (_indxLightsPoint[ index ] = thrID),
you do a barrier, but you forget to do a memory marrier on shared memory as well.
You read shared memory (index = _indxLightsPoint[i]), but it is not guaranteed that all threads see the expected thrID.

Maybe that's it. I'd not give up so soon because you have no shared memory in fragment shaders.
Personally i gave up on OpenGL compute shader because OpenCL was two times faster on Nvidia ans slightly faster on AMD 1-2 years ago.

For me it was absolutely necessery to stop the compiler from unrolling loops (forgot the command)
The compiler did not bother to unroll loops with > 1000 iterations smile.png

- ComputeShader setup (tilesize 32x32 too big)

It's always worth to try out, different hardware, differnt results. I'd assume 8*8 or 16*16 is better than 32*32.
On OpenCL the maximum for ATI is 512, but OpenGL spec requires a minimum of 1024, so i guess it's a slowdown for ATI to sync 1024 threads.
The hardware minimum for ATI is 64, NV 32. So in practice choose 64, 128 and 256 depending mostly on register usage.

#5272480 Z rotates with X and Y (quaternion rotation)

Posted by JoeJ on 24 January 2016 - 10:29 AM

It still feels like an easy hack

Most likely because you miss experience with 3D rotations. Maybe it helps to comment some of your statements:

"Z rotates with X and Y"
This is no problem - Z axis (and Y) must rotate if you rotate somthing around it's X axis - otherwise it's no rotation.
Same if you rotate around Y: Z & X rotate, Y stays the same.

I am trying to rotate an object in my game by using quaternions to avoid gimbal lock

I hear this often but it's nonsense. People tend to think Gimbal Lock is the bad guy each time they have a problem with rotations and Quats will fix it.
Matrices and Quaternions both can do any rotation in one step - there is no difference in regard to Gimbal Lock.
Euler angles may in deed cause unwanted Ginbal Lock problems, because the represent a series of multiple rotations in specified order.
But for human interaction they are still most comfortable, which is why we use them for editing animation curves or FPS camera.

So, by this example we used 2 Euler angles to get expected behaviour, but we still need math like quats or matrices to get the work done.

void TransformComponent::Rotate(glm::vec3 axis, float angle)
m_rotation *= glm::angleAxis(angle, axis);

There are 2 issues about this code:

First, you modify an orientation by rotation. Over time, floting point precission will cause degeneration of m_rotation.
Unlike position, orientation requires some constraints to be hold to stay a valid orientation:
A matrix needs its axis unit length and orthogonal to each other, a Quaternion must stay normalized.
So, you may need to orthonormalize or normalize m_rotation after such an operation.
(Or you avoid the issue by keeping only the euler angles like i did).

Second, and that may really help you in practice (in contrast to the other blah blah):
I suggest you make two functions for world OR local space:

void TransformComponent::RotateGlobal(glm::vec3 axis, float angle)
m_rotation *= glm::angleAxis(angle, axis);

void TransformComponent::RotateLocal(glm::vec3 axis, float angle)
m_rotation = glm::angleAxis(angle, axis) * m_rotation;

This way you always make clear if you rotate around the local object space or global world space.
(Note the only difference is multiplication order - i don't know glm's convention and it may be the other way around - maybe that caused some of your initial problems)

#5272466 Z rotates with X and Y (quaternion rotation)

Posted by JoeJ on 24 January 2016 - 08:04 AM

I think there is another problem. Gimbal lock is expected here - if you look upwards in some FPS and move mouse sideways, camera spins but does not change direction.

The main mistake here seems mapping cursor position to a rotation. If mouse X has constant value but does not change, camera will keep rotatiing every frame.
What you want is to map mouse cursor to an orientation, not rotation, something like:

static vec2 oldMousePos(0,0);
static vec2 cameraAngles(0,0);

vec2 newMousePos (-g_pWindow->getMouseMotion().x, g_pWindow->getMouseMotion().y);
vec2 mouseDiff = newMousePos - oldMousePos; // mouse movement per frame
oldMousePos = newMousePos; 

cameraAngles += mouseDiff * mouseSensitivity; // no need to involve timestep

camera.m_rotation = Identity();
camera.m_rotation *= glm::angleAxis(cameraAngles[1], glm::vec3(1,0,0));
camera.m_rotation *= glm::angleAxis(cameraAngles[0], glm::vec3(0,1,0)); // do the most important axis (horizontal mouse movement) last

#5271843 Any information out there on physics for walkers/mecha?

Posted by JoeJ on 19 January 2016 - 09:33 AM

Any examples out there of how to do an IK solver for leg movement?

IK solvers have two problems: Either there are infinite solutions or none.
But because our body is made for walking / running we get away with a very simple 'solver' for this purpose.
Below is the simplified solution i use (a bit hard to read, but it shows necessary complexity).
Most probably you do not need to define and care for joint limits as long as your units do only basic movement,
and it should not be necessary to read papers on IK solvers, because they focus on harder problems.

How it works:
Take a line from hip to target and stretch leg along that line.
If target distance is shorter than leg length, bend knee accordingly.
Set foot orientation to target.

So you see it's very easy.
Complexity arises because bones and joints each have their own spaces we need to tackle and so forth.
You may wanna start with a 2D case to feel safe.

After the IK solver is working, you only need to care for target foot positions.
For now i keep the swivel angle to a constant value keeping the knees pointing forwards.
For turning and walking smaller circles it would look better to modify it a bit.

void Ragdoll::IKSolveLegChainEffSimplyfied (Chain &chain, BodyInfo *bodyInfos, 
	float swivelAngle, // Sit on a chair and keep your foot on the ground. You can rotate your knee arond the line from hip joint to ankle joint without moving foot or pelvis - that's why we need to provide swivelAngle to avoid infinite solutions
	sVec3 tPos, // target ankle joint position
	sQuat *tOrn) // target foot orientation
	float limitShrink = 0.0; // tolerance to keep from max joint limits

	Target &tUpper = chain.target[Chain::UPPER];	// bone upper leg
	Target &tLower = chain.target[Chain::LOWER];	// bone lower leg
	Target &tEff = chain.target[Chain::EFF];		// bone foot

	RagdollJoint &jUpper = *tUpper.joint;			// joint pelvis - upper leg (hip)
	RagdollJoint &jLower = *tLower.joint;			// joint upper leg - lower leg (knee)
	RagdollJoint &jEff = *tEff.joint;				// joint lower leg - foot (ankle)

	sQuat qBase, qUpper, qLower, qEff;

	qBase =	bodyInfos[jUpper.index[1]].orn;			// pelvis orientation in world space
	qUpper = bodyInfos[jUpper.index[0]].orn;		// upper leg orientation in world space
	qLower = bodyInfos[jLower.index[0]].orn;		// lower leg orientation in world space
	qEff = bodyInfos[jEff.index[0]].orn;			// foot orientation in world space
	float lUpper = tUpper.boneLength;
	float lLower = tLower.boneLength;
	float lSum = lUpper + lLower;

	float curTwist, curSwing;
	sVec3 axis; float angle;
	sQuat rot;

	sQuat oB, oU, oL; // new bone orientations
	sVec3 pB, pU, pL; // new bone positions
	oB = qBase;
	pU = tUpper.cPos;
	// measure hip - target dist
	sVec3 dUT = tPos - pU;
	float lenUT = dUT.Length();
	if (lenUT < FP_EPSILON) return;
	dUT /= lenUT;
	sQuat oBunmod;
	sQuat oUunmod;

	sVec3 dL, dU;
		// upper...

		float angU = 0;		
		if (lenUT < lSum) // bend knee if target dist is sharter than leg length
			angU = acos (min(1.0, max(-1.0, (lenUT*lenUT + lUpper*lUpper - lLower*lLower) / (2.0 * lenUT * lUpper))));

		oU = oB * jUpper.localRot1  * jUpper.localRot0.Inversed();
		rot.FromVecToVecR (dUT, oU.XAxis()); // X axis = axis of rigid body capsules per bone
		oU = rot * oU;

		oU *= sQuat::rotationX (-swivelAngle);
		oU *= sQuat::rotationZ (angU);

		sQuat oUn;
		jUpper.CalcTwistSwingLimitTarget (oUn, curTwist, curSwing, oU, oB, limitShrink); // makes oUn the relative rotation from oU to oB. Ensure this does not violate joint limits (never happens when walking or running)

		oU = oUn;
		oU.Normalize(); // oU finished
		dU = oU.XAxis();

		oUunmod = oU;
		oU *= chain.upperOffset;
		jUpper.CalcTwistSwingLimitTarget (oU, curTwist, curSwing, oU, oB, limitShrink);
		dU = oU.XAxis();

		// lower...

		pL = pU + dU * tUpper.boneLength;
		sVec3 lTar = oU.Inversed().Rotate (sVec3(tPos - pL));

		sVec3 lTarQ (lTar[0], lTar[1], 0);
		float len = lTarQ.SqL();
		if (len > FP_EPSILON)
			len = sqrt(len);
			lTarQ /= len;
			angle = atan2 (lTarQ[1], lTarQ[0]); // knee angle
		else angle = 0;
		if (angle > jLower.twistLimitAngleP - limitShrink) angle = jLower.twistLimitAngleP - limitShrink; // knee joint limits
		if (angle < jLower.twistLimitAngleN + limitShrink) angle = jLower.twistLimitAngleN + limitShrink;

		oL = oU * sQuat::rotationZ (angle);
		oL.Normalize(); // lB finished


	// apply upper & lower leg (set joint targets for simulation)
		sQuat oU1 = oB * jUpper.localRot1;
		sQuat oU0 = oU * jUpper.localRot0;
		sQuat rotUpper = oU1.Inversed() * oU0;
		jUpper.targetOrn = rotUpper;
		sQuat oL1 = oU * jLower.localRot1;
		sQuat oL0 = oL * jLower.localRot0;
		sQuat rotLower = oL1.Inversed() * oL0;
		jLower.targetOrn = rotLower;

	// foot (just set to target and ensure joint limits)...
	if (tOrn)
		//float effSpeed = 1;

		sQuat eB = *tOrn;
		float limitTwist = jEff.CalcTwistSwingLimitTarget (eB, curTwist, curSwing, eB, oL, limitShrink); // joint limits

		sQuat oE1 = oL * jEff.localRot1;
		sQuat oE0 = eB * jEff.localRot0;
		sQuat rotEff = oE1.Inversed() * oE0;
		jEff.targetOrn = rotEff;


struct Target // just some joint data
	sVec3 cPos; // position of the joint (not the bone)
	float boneLength;
	RagdollJoint* joint;

#5271772 Any information out there on physics for walkers/mecha?

Posted by JoeJ on 18 January 2016 - 06:54 PM

looks a bit off, like that Honda robot you've probably seen on TV

Agree to that, but then look at the quadrupes from Boston Dynamics.
They move like living animals (remember their reflexes while slippering on ice).
It works for them so it will work for us.

I'm pretty sure i'll have natural walking and running.
Those are behaviours defined olmost entirely by physics laws and shape of the human body,
so it's possible to reproduce with analytical methods and it will look right.

I'm worried about other things - motion that is result of intelligence.
Operating tools, complex tasks etc... don't know how to handle that.

Back on topic, simulation is surely overkill here.
So there remains the options to use and modify existing animation, or use procedural animation only.
Both require a IK solver that orients and positions the foot, so i'd start with that.

#5271704 Any information out there on physics for walkers/mecha?

Posted by JoeJ on 18 January 2016 - 09:17 AM

I'm working on a walking ragdoll for several years now, and this is what i have so far:

A true simultaion is too much work if your motivation is just 'it does not look well'.
But you can use some related math to improve the legs animation, while internally sticking at the tank model.

So, what i suggest is:

Build an Inverted Pedulum model from your tank.

Calculate the 'ICP' (Instaneous capure point).
This is the point wehre an inverted pendulum stops falling, if it can put it's 'COP' (center of pressure) to this location.
Moving the COP works by:
If inverted pendulum has a cart as its base, move the cart (often used model in research)
If base is a single ore more legs at rest, move the COP inside the support polygon (convex hull of feet projected to ground) by ankle torque.
If the legs have knees, you can simply move a leg to the target COP position. This alone is the interesting case for you.

Now, assuming you know ICP (simple to calculate. E.g. http://www.elysium-labs.com/robotics-corner/learn-robotics/biped-basics/zero-moment-point-zmp/ ),
This can help to get some realistic looking feet targets from this observation:
A walker will place its swing foot somewhere between ICP and ground projected COM (center of mass).
Moving this 'somewhere' closer to the COM means accelerating, moving closer to the ICP means deaccelerating and stop.

Then you need some simple IK solver to calculate knee angle, aligning foot to terrain etc. and that's it.

I've had some discussion with Newton physics engine developer which contains some links to useful papers on the subject:

#5271531 Responsive UI in compute-heavy games

Posted by JoeJ on 17 January 2016 - 03:36 AM

D3D9 (and OpenGL without a lot of driver-specific hackery) force you to perform almost all of your graphics resource management on a single thread, which also be the one that created your window and the one that polls Windows for input messages.

That's not true for the input message part.
I use a seperate thread for input and another for OpenGL since 20 years without issues for an editor application on Windows.

#5269770 Sorting with dependencies?

Posted by JoeJ on 07 January 2016 - 02:07 AM

I might miss something, but if you subivide your sorted list to smaller lists of equal items:

listOfLists = {
{rock rock rock rock rock},
{tree}, //occluding tree
{rock rock rock},
{tree tree tree tree}

And then do:

for (i=0; i<listOfLists.size; i++)
for (j=i+1; i<listOfLists.size; i++)
if (i.itemType == j.itemType and all lists between i...j do not occlude i) add i to j, clear i and break

You would get

{rock rock rock rock rock},
{rock rock rock},
{tree tree tree tree tree}

which is what you want.

#5268071 Inertia Tensor magnitude to find Angular Acceleration

Posted by JoeJ on 26 December 2015 - 03:19 PM

The correct way is to multiply the torque vector by the inverse of the world-space inertia tensor for the object. You should precompute the object-local inverse inertia tensor, then transform it to world space on each frame via a similarity transform: R' * I^-1 * R where ' is the transpose and R is the rotation matrix.

I assume that's mathematically the same as in this snippet (correct me if i'm wrong):
inline sVec3 ConvertTorqueToAngAcc (sVec3 &torque, sMat4 &matrix, float Ixx, float Iyy, float Izz)
	sVec3 angAcc = matrix.Unrotate (torque);
	angAcc[0] /= Ixx;
	angAcc[1] /= Iyy;
	angAcc[2] /= Izz;
	return matrix.Rotate (angAcc);
The difference is:
In method 1 from my first post acceleration and torque have the same direction.
In Method 2 their directions are different because the nonuniform scale from inertia.

I'm unsure which of those two methods is more 'correct', but I have had a lot of use cases where only one of the two gave me the desired results.
Any clarification welcome (it may be worth to try both).

#5268057 Inertia Tensor magnitude to find Angular Acceleration

Posted by JoeJ on 26 December 2015 - 11:16 AM

What does body.orientation.Unrotate() do?

No, it just transforms the torque direction ('axis') from world space to the local body space.
This is necessary because inertia tensor is usually given in body space.

Instead of body.orientation you most prabably have a 4x4 matrix containing body position and orientation.
Then you need to ignore position (like transforming a normal in graphics).
Or if you have a quaternion for orieantation you can use that (Don't know Unity / PhysX).

#5267996 Inertia Tensor magnitude to find Angular Acceleration

Posted by JoeJ on 26 December 2015 - 03:44 AM

That's ok only if the body has uniform inertia (a sphere).
But for a general body inertia depends on the direction you want to measure.

To find inertia on any direction:
inline float GetInertia (const sVec3 &localaxis, const float Ixx, const float Iyy, const float Izz)
	sVec3 axis = localaxis;
	axis[0] /= Ixx;
	axis[1] /= Iyy;
	axis[2] /= Izz;
	return 1.0f / axis.Length();
So, four your example you need:

vec3 axis = torque.Unit();
vec3 localAxis = body.orientation.Unrotate(axis);
float inertia = GetInertia (localaxis, body.inertiaTensor.x, body.inertiaTensor.y, body.inertiaTensor.z);
vec3 angularAcceleration = torque / inertia;

#5267542 Testing if a triangle is inside other groups of triangles

Posted by JoeJ on 22 December 2015 - 02:56 PM

Ah, ok - i get you now and agree, sorry.
For the picture in first post it would work your way (i've missunderstood the pictures as clip inside vs clip outside or something).

But for the grass you would find only a few triangles to discard, because it's not convex.
Using exact clipping you could find all triangles that are partially visible or completely occluded.

However - for the grass no method will reduce vertex count significantly.
Using clipped polys instead original polys could only reduce overdraw a lot.

#5267464 Testing if a triangle is inside other groups of triangles

Posted by JoeJ on 22 December 2015 - 03:07 AM

Servants suggestion would fail if the clip triangle is completely inside the test triangle -
no test points are inside the clip, so it would be accidently rejected.

In 3D one could solve this by convex polygon clipping:
For each edge of the clip poly, build a plane from poly normal and edge and clip all test polys against this plane (See code below).
Then clip the remainding polys by the next edge until all edges have been done.

In 2D instead of clipping against a plane, you need to clip against the infinite line of the edge.

That's complex and seems slow, but games like quake or any software renderer did it for exact frustum culling (in case you need it for realtime).

Finally you can retriangulate the remaining polys.

inline int ClipTexmapPolygon (const TexmapPolygon *pin, const vec &plane, TexmapPolygon *pout, const int space)
		if (pout->numAvailableVertices < pin->numVertices + 1)
			pout->Resize (pin->numVertices + 1);

		int i, curin, nextin;
		float curdot, nextdot, scale;
		TexmapPolygon::Vertex *pinvert, *poutvert, *nextvert;

		pinvert = pin->vertices;
		poutvert = pout->vertices;
		curdot = pinvert->puv[space].Dot (plane);
		curin = (curdot >= plane[3]);
		int ret = -1; // assume inside

		for (i=0; i<pin->numVertices; i++)
			nextvert = &pin->vertices[(i+1) % pin->numVertices];
			// keep if inside	
			if (curin) 
				*poutvert++ = *pinvert;
			nextdot = nextvert->puv[space].Dot (plane);
			nextin = (nextdot >= plane[3]);
			if (curin!=nextin) // add clipped vertex if plane splits edge

				ret = 1; // clipped or outside
				scale = (plane[3] - curdot) / (nextdot - curdot);

				for (int c=0; c<3; c++)
					poutvert->puv[c] = pinvert->puv[c] + (nextvert->puv[c] - pinvert->puv[c]) * scale;


			curdot = nextdot;
			curin = nextin;

		pout->numVertices = poutvert - pout->vertices;
		if (pout->numVertices < 3) return 0; // outside
		return ret;
But... do you need this just to reduce overdraw of the grass? It might not be worth the affort.