Calculating an optimal matrix using shaders

Question

Hi guys,

Here is my end-objective: I have a very large terrain array of Vector3s (~2 million) and what I want to do is find the transformation matrix that would result in the smallest total lengths of all of these vectors relative to the origin (aka distance from vector to the origin). Yup, simply adding them all together.

I can perform this in a brute-force way in C#. but it takes minutes! What I do here is take each element of the matrix that represents translation (no rotation allowed in this application) and slowly increment them from, say, -5.0 to 5.0 individually (with some delta like 0.01) so that all combinations have been tested and I store the total lengths of the vertices after transforming them by this matrix.

The pseudo-code approach looks something like this:

float total = 0
float delta = 0.01
for(matrix_translate_x -5.0 -> 5.0)
for(matrix_translate_y -5.0 -> 5.0)
for(matrix_translate_z -5.0 -> 5.0)
     for each vector
          transform vector by matrix
          add length to total

I'm wondering if there is a way to perform this lightning fast using HLSL. I understand how to do calculations with float3s and float4x4s in the language, but what I don't know how to do store the results of each iteration so a final solution can be determined after the GPU process all of the vertices. So far I have these vertices in a heightmap which I render to a rendertarget to analyze the results.

Is using HLSL for this application feasible? Ideally this would take one render since -5 to 5 on 3 axis is 100,000 combinations using 0.01 as a delta! I'm also open to other suggestions not using HLSL.

Thanks!

---

EDIT: I didn't anticipate there would be an easy math answer so I kind of simplified my question for brevity! See reply #1.

This "terrain" I spoke of exists as a cloud of 3D points scattered in a tube fashion along the X axis. I can independently move both ends of this tube (like holding onto both ends of a broomhandle and moving your arms) in the Y and Z direction to try to find the smallest total length as I wrote above. So there would actually be two vectors, one at X=0 and one at X=max_x. All points in between 0 and max_x will be interpolated between the two solution vectors. So in truth we kind of can "rotate" here. Does that make sense at all?

I assumed if I could figure out the principles in HLSL I could apply it to my problem completely. Sorry to confuse.

---

[By the way, I also posted this question (copy/paste) on the XNA community forums. Is that bad forum etiquette? I'm new to this sort of thing...]

Answer 1

That seems like a very brute-force approach to finding your desired solution. I think you should be able to compute the solution directly, without trying out all possibilities.

If I understand correctly, you have n 3-vectors x_1,...,x_n, and you're trying to find a translation (i.e. another 3-vector) d such that

sum(i=1,...n) || (x_i+d) ||

is minimal (where || denotes the 2-norm, or length, of a vector).

Correct?

I believe you should be able to make this sum minimal (without being able to prove it, though) by setting d so that it brings the centroid of the data set to the origin. In other words

d = -(1/n) * sum(i=1,...n) x_i

Try this solution out -- is it equivalent to the solution computed by brute force using your algorithm above?

Edited because I believe I misunderstood the problem initially.

Edited again to ask for clarification because the comment format doesn't allow me to format formulas.

I'm not quite sure I understand -- could you try and express mathematically the operations you can carry out on the dataset?

To clarify:

• Can you translate along all axes? Or are translations along the x axis "forbidden"?

• You say you can "move both ends of the dataset independently in y and z" (if I'm paraphrasing you correctly). This sounds as if you're allowing at least rotation in the y-z-plane. Do you also allow scaling along y and z? What about shearing?

Does this matrix express what you're trying to do:

        | 1 0 0 | 
x_new = | 0 a b |*x_orig + d
        | 0 c d |

where the 3-vector x_orig is the original data point, the matrix performs arbitrary operations in the y-z-plane, and the 3-vector d expresses a translation that is applied after the matrix.