<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 4.0
2019-08-08T17:52:16.307Z
2019-08-08T17:52:16.307Z
coder1337
<p>Input: Triangles which make up an arbitrary shape. Each triangle is represented by 3 3D points.</p>

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

<p><a href="https://developer.nvidia.com/sites/all/modules/custom/gpugems/books/GPUGems3/elementLinks/29fig03.jpg" rel="nofollow noreferrer"><img src="https://developer.nvidia.com/sites/all/modules/custom/gpugems/books/GPUGems3/elementLinks/29fig03.jpg" alt="Particles generated from a shape"></a></p>

<p>I have read the description made by <a href="https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch29.html" rel="nofollow noreferrer">GPU-Gems</a>, 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.</p>

<p>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.</p>

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

<p><strong>Edit:</strong> 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.</p>

<opengl><shader><c++><simulation><particles>
Represent shape as particles
coder1337
# Represent shape as particles

(Asked by: username_0 on 2019-08-08)

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](https://developer.nvidia.com/sites/all/modules/custom/gpugems/books/GPUGems3/elementLinks/29fig03.jpg)](https://developer.nvidia.com/sites/all/modules/custom/gpugems/books/GPUGems3/elementLinks/29fig03.jpg)

I have read the description made by [GPU-Gems](https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch29.html), 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.

**Tags:** opengl, shader, c++, simulation, particles


---

## 1 answers

### Answer by username_0 on 2019-08-08. Score: 1 | Accepted answer

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.


---

