0
\$\begingroup\$

Please can help me for a geometry query, I am working out fast mesh to voxel algorithm without using rays and complex maths...

What are the maths to sample N points on a triangle randomly? If you can sample randomly i think it means you know the same equation that can distribute points on a triangle at same spacing.

I found some info here but it's too difficult to understand:

https://math.stackexchange.com/questions/18686/uniform-random-point-in-triangle

http://mathworld.wolfram.com/TrianglePointPicking.html

The reason is to sample N points on every triangle and round each into a voxel space and send the rounded position of every sample as a true value to a boolean spacial voxel array of X,Y,Z true false values to represent voxels.

Thanks for any info's you may provide!

\$\endgroup\$
  • \$\begingroup\$ What about the math do you not understand? That math is a valid answer to your question. \$\endgroup\$ – Josh Jan 23 '17 at 20:19
  • \$\begingroup\$ The equation on that page is for 2D space and equilaterals and i am working in 3D, and i worked too much on other algorythms today and have the first bout of carpal tunnel syndrome in about 2 years. I can't read maths and interpret it as code very well. my algo is perhaps the fastest way to do mesh to voxel too because it doesnt use Möller–Trumbore maths which uses a lot of over the top algebra and is slow, it's worth writing a query? \$\endgroup\$ – com.prehensible Jan 23 '17 at 22:07
2
\$\begingroup\$

What you need is a specific coordinate system where instead of having right angles in the center, you have one of the angles of the triangles. The units on each axis are also equal to the length of the triangle's sides:

enter image description here

The units on the "y" axis are the length of AC, the units on the "x" axis equal to the length of AB.

If you project this into a right angle coordinate system, you get the following:

enter image description here

Much much better, now you want to get a random point in this.

For every point in this triangle we can say, that the sum of the coordinates (x + y) of it is always less than or equal to 1. Knowing this generating a random point inside can be done the following way (pseudo-code):

x := rand(0, 1)
y := rand(0, 1 - x)

Now you only need to convert this back to the original coordinate system, this can be done my converting the AC and AB sides to a vector and multiplying them with x and y:

vX := (C - A) * x
vY := (B - A) * y

This is in 2d, but this can be extended to 3d. You only need to do the last 2 steps (generating the random point in the equilateral triangle then projecting it to 3d).

\$\endgroup\$
  • 1
    \$\begingroup\$ Are you sure the points will be uniformly distributed? The x is equally likely to be less than 0.5 and more than 0.5, but the area left of the 0.5 x-coordinate is much greater than the area right of it. I might be wrong though. \$\endgroup\$ – wondra Jan 23 '17 at 22:40
  • \$\begingroup\$ @wondra zero idea, this was just an idea of mine. He didn't say he wants them to be uniformly distributed \$\endgroup\$ – Bálint Jan 23 '17 at 23:01
  • \$\begingroup\$ yes any triangle sample will work fine, extra maths to have specific lattice in the triangle is perhaps slower and a waste of time for us poor programmers. buhuC++ ;= \$\endgroup\$ – com.prehensible Jan 23 '17 at 23:05
  • \$\begingroup\$ @comprehensible if this answer helped you mark it as correct \$\endgroup\$ – Bálint Jan 24 '17 at 7:54
0
\$\begingroup\$

Thanks a lot to Bálint for illustrating the problem. i found a result for random points although i don't actually understand it, so will have to study that theory.

function randomPointsOnPolygon () {


for( var xx = 0; xx <= 100; xx ++){
    var r1 = Random.value;  
    var r2 = Random.value;  
var P:Vector3=(1-Mathf.Sqrt(r1))*ta+(Mathf.Sqrt(r1)*(1-r2))*tb+(r2*Mathf.Sqrt(r1))*tc;

    var cube : GameObject      = GameObject.CreatePrimitive(PrimitiveType.Cube);
    cube.transform.position    = P;

    }
}

Random is fairly random, I tried ra = (xx * xx)%1 to mix the proportions up and fixed increment and random was best. Comment if you know how to make regular distribution. xx*q % 1.0 gives these images:

enter image description here enter image description here enter image description here

THE REST OF THIS ANSWER IS SKIPPABLE: ITS HELPFUL INFO TO DEMONSTRATE THIS IS A VERY GOOD/BEST WAY TO SOLVE VOXEL TO MESH CONVERSION: it seems incredibly much speedier than a physics mesh to voxel version, online they had me checking all 12 edges of every cube for min max in every quadrant of space. checking 24 edges of one cube (raycast both directions) is slower than checking 24 points on a triangle,every which one is in a cube of space, to write to a bool array!

found this approximate sqrt for c# for it too http://blog.wouldbetheologian.com/2011/11/fast-approximate-sqrt-method-in-c.html

hint: optimize by number samples related to triangle size, using a fast tri size approximation because it's quite demanding on maths, otherwise 250 samples per triangle takes 1 second for a 2000mesh object so perhaps no optimization necessary.

Time take for 10,000 vertex mesh from 2000 triangles = 1 second, triangle vtx size mutiplied by mesh size multiplier, rounded random triangle points saved as math.round to linear bool array length 100,00,00 boolarr(z*100*100+y*100+x) ... that's how you use a linear voxelbool aray in xyz loops. afterwards to fill the mesh, it's best to use the vertex normals to mark left and right facing triangles/cubes and to scan fill all left right voxels. enter image description here

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.