Input: Triangles which make up an arbitrary shape. Each triangle is represented by 3 3D points.

Output: A set of particles which fills up the inside of the object (see image).

Particles generated from a shape

I have read the description made by GPU-Gems, and tried to implement the proposed solution that don't make the computations on the GPU. I have tried to take each triangle one at a time and see if they intersect with lines, and if so store the z-value which I later used to generate particles. This gave bad results, and in theory it is possible for a line to intersect with a lone point which would cause a bug.

Can anyone tell me how to easily on the CPU side create a set of particles that represent a shape? Where the shape is defined as a set of triangles.

I prefer a solution that is simple and works well rather than an efficient solution that can have bugs.

Edit: I re-checked my code, and I found that I was not sorting the z-value arrays correctly like I thought I did, after fixing this I got a good result! If anyone still wants to answer this question that is ok, but I consider my problem to be solved now.


Solution: Check for the minimum x,y,z value for all points. Add these values multiplied by (-1) to all points in order to guarantee that all points are not negative. Then take the largest point and subtract with the minimum point (max and minimum x y z) in order to get a cube-like bound for the object.

Then divide this cube by an arbitrary size constant representing the radius of each particle. Now you should have a 2D array for z-values, such that for any x, y position you can quickly store z-values that you find intersecting lines.

For each triangle in the mesh, check all possible that have a large or small enough x-y value for intersections with a line going through the whole cube. If there is an intersection, save the z-value in the x-y array for z-values.

Lastly loop through each possible z-values in the imaginary cube and check if it has an odd number of z-value hits before the current z-value. If that is the case, then we know that there is a particle here. Don't forget to add the minimum x,y,z values that we added in the beginning in order to make the particles have the correct positions again.


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.