• Create Account

# KaiserJohan

Member Since 08 Apr 2011
Offline Last Active Today, 06:16 AM

### Simplifying skinning transforms?

18 April 2016 - 11:00 AM

Correct me if I'm wrong but as I understand it the following is the bone transformation procedure:

```R = current anim key rotation matrix
T = current anim key translation matrix
R1 = next anim key rotation matrix
T1 = next anim key translation matrix
G = transform matrix
G1 = parent transform matrix
I = inverse root matrix
O = bone offset matrix
F = final transform for bone

So:
G = interp(R, R1) * interp(T, T1);
F = I * G * G1 * O;
```

That is alot of matrix multiplications each frame. Is there anything that can be done to simplify and speed up the process?

Are there any matrices that can be "baked" / pre-transformed without causing artifacts during animation (interpolation) ?

### some a* questions

18 March 2016 - 07:42 PM

1. I've been able to build smaller test sets (~20 * ~20) manually like this:

```s = start
f = goal
1 = passable
0 = impassable

f, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1,
1, 0, s, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1,
1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1,
1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1,
1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1,
1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1```

But constructing large sets (like 1000 * 1000) by hand is not feasible. Are there any tools or available test files available one can use to test ones implementation of a* alghorithm?

2. Reading the pseudo-code on wiki:

```function A*(start, goal)
// The set of nodes already evaluated.
closedSet := {}
// The set of currently discovered nodes still to be evaluated.
// Initially, only the start node is known.
openSet := {start}
// For each node, which node it can most efficiently be reached from.
// If a node can be reached from many nodes, cameFrom will eventually contain the
// most efficient previous step.
cameFrom := the empty map

// For each node, the cost of getting from the start node to that node.
gScore := map with default value of Infinity
// The cost of going from start to start is zero.
gScore[start] := 0
// For each node, the total cost of getting from the start node to the goal
// by passing by that node. That value is partly known, partly heuristic.
fScore := map with default value of Infinity
// For the first node, that value is completely heuristic.
fScore[start] := heuristic_cost_estimate(start, goal)

while openSet is not empty
current := the node in openSet having the lowest fScore[] value
if current = goal
return reconstruct_path(cameFrom, goal)

openSet.Remove(current)
for each neighbor of current
if neighbor in closedSet
continue		// Ignore the neighbor which is already evaluated.
// The distance from start to goal passing through current and the neighbor.
tentative_gScore := gScore[current] + dist_between(current, neighbor)
if neighbor not in openSet	// Discover a new node
else if tentative_gScore >= gScore[neighbor]
continue		// This is not a better path.

// This path is the best until now. Record it!
cameFrom[neighbor] := current
gScore[neighbor] := tentative_gScore
fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)

return failure

function reconstruct_path(cameFrom, current)
total_path := [current]
while current in cameFrom.Keys:
current := cameFrom[current]
total_path.append(current)
```

In my case, as in the layout I showed in #1, the distance between a node and its neighbours are always 1 (adjacent). The "gScore" always increases by one each step away from start node.

Dosn't that mean that mean I can simplify it so whenever we add a node we have the optimal path between the start node and it

So either the node is in the open or closed set and we ignore it or its not visited and we add it, like below:

```function A*(start, goal)
...
for each neighbor of current
if neighbor in closedSet or openSet
continue

cameFrom[neighbor] := current
gScore[neighbor] := gScore[current] + 1
fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)
...

```

### a* early exit on impossible set?

18 March 2016 - 02:07 AM

Using the A* search alghorithm is there anything you can do to detect if goal is unreachable?

Otherwise the alghorithm ends up traversing the entire graph, which is unfortunate on really large sets

If not is there any variant of A* or similiar alghorithm that can do this while still finding the shortest path?

For example:

```s = start
f = goal
passable = 1, impassable = 0

1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 0 0 0 1 1
1 1 0 f 0 1 1
1 1 0 0 0 1 1
1 1 1 1 1 1 1
1 1 1 s 1 1 1
```

### Packing vertex attributes

05 January 2016 - 04:43 AM

While looking at skinned mesh shaders one idea struck me. Bone indices and weights are sent per vertex as 4-byte floats, such as below:

```struct VSIn
{
float3 mPosition : POSITION;
float3 mNormal : NORMAL;
// ...
float4 mBoneIndices : BONEINDICES;
float4 mBoneWeights : BONEWEIGHTS;
};
```

It seems awfully wasteful to send bone indices as full 4-byte floats when in reality each value is probably up for 4 and would thus all easily fit into one float.

Same (probably?) applies to weights which i don't *think* needs all the fractions provided by 4-byte float?

When looking at MSDN docs it seems the smallest scalar type is 4 bytes, there is a half-float but only for backwards compatability? Likewise there dosn't seem to be any bitwise operators in HLSL.

If bandwidth is such a precious resource is there some clever trick to pack the vertex attributes tighter and ultimately is it worth the effort?

04 January 2016 - 07:38 AM

Hello,
I'm implementing skeletal animation and I've been looking at some examples on the net and compiled a list of questions.

```static const uint MAX_NUM_BONES = 64;

cbuffer SkeletalAnimConstants : register(CBUFFER_REGISTER_VERTEX)
{
float4x4 gWorldViewMatrix;
float4x4 gBoneMatrices[MAX_NUM_BONES]
};
```

1. Are constant buffers the ideal way to send bone transforms to the shader?

2. If so whats a reasonable max limit?

```struct VSIn
{
float3 mPosition : POSITION;
float3 mNormal : NORMAL;
float2 mTexcoord : TEXCOORD;
float3 mTangent : TANGENT;
float3 mBitangent : BITANGENT;
float4 mBoneIndices : BONEINDICES;
float4 mBoneWeights : BONEWEIGHTS
};

VSOut vs_main(VSIn input)
{
float4x4 boneTransform = gBoneMatrices[input.mBoneIndices.x] * input.mBoneWeights.x;
boneTransform += gBoneMatrices[input.mBoneIndices.y] * input.mBoneWeights.y;
boneTransform += gBoneMatrices[input.mBoneIndices.z] * input.mBoneWeights.z;
boneTransform += gBoneMatrices[input.mBoneIndices.w] * input.mBoneWeights.w;

// ...
}
```

The shaders seems to assume the vertex is affected by at most four bone transforms.

3. Is four bones per vertex some kind of 3D model convention? It seems very common. Could there be models with vertices with more than four bones affecting it? What is the best approach then?

4. Isn't there alot of unnecessary matrix scalar multiplications and concatenations if some vertices have less than four bones ( = some weights are zero)?

Thanks

PARTNERS