# In need of Stationary Particle System Algorithms

Page 1 of 1

## 2 Replies - 900 Views - Last Post: 11 June 2010 - 11:49 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=177352&amp;s=7a73b290c9df572fa92dc9e6cf9413a6&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 tomdbs98

• New D.I.C Head

Reputation: 0
• Posts: 3
• Joined: 11-June 10

# In need of Stationary Particle System Algorithms

Posted 11 June 2010 - 07:22 AM

Greetings game programmers,

I am in need of progamming help and am having trouble finding resources online.
Although I am not making a game, I believe that this is the kind of problem an experienced game programmer would be able to help me solve.
I have motionless particle systems such as the following:

Where I have the coordinates of each point. I need to find out whether these systems are intersecting ([orange/blue] are, where as [orange/red] and [blue/red] are not).

There are two ways I believe this can be done:
1) Attempt to place a plane between the two sets and see if they are (almost) entirely on opposite sides.
or
2) Build a convex hull around each set and calculate the distance between the closest faces.

I am skeptical about using bounding boxes because the systems can have awkward and unpredictable shapes.

What are your thoughts on this? Which method would be the easiest to implement? Where can I find a good resource for this?

I am programming in perl, but I am familiar with C/C++/PHP/Java.

Thanks ahead of time,

-Thomas

Is This A Good Question/Topic? 0

## Replies To: In need of Stationary Particle System Algorithms

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12278
• Posts: 45,364
• Joined: 27-December 08

## Re: In need of Stationary Particle System Algorithms

Posted 11 June 2010 - 05:58 PM

I think that you have a good idea with Convex Hulls, but you still have the problem about the Collision for the Faces. Simply calculating the distance between two faces I don't think is a great solution because you aren't taking into account a 3D area completely. What points on the faces are you calculating distance for? What if there are a ton of points on a face? What if the two faces touch on the edges? These are questions that do need to be considered when tackling this problem.

If/when you move into motion, you'll want to take a look into using Vectors. I've found some links on 3D Vectors and Collision detection you may find useful:
http://www.edenwaith...s/collision.php
http://nehe.gamedev....n.asp?lesson=30
http://en.wikipedia....iki/Dot_product

As for your first option, I definitely like the idea for pruning, so you can reduce unnecessary checks. Since you are working with still Objects, I don't see any reason why distance wouldn't be a good option, so long as you take radius into account. If two Objects are fairly close together, you may invoke a 3D bounding box for collision detection.

### #3 tomdbs98

• New D.I.C Head

Reputation: 0
• Posts: 3
• Joined: 11-June 10

## Re: In need of Stationary Particle System Algorithms

Posted 11 June 2010 - 11:49 PM

Fortunately I will not be needing to deal with moving systems(phew!)
The path I've chosen to take does after all use bounding boxes, and removes the need to compute a convex hull.

my proposed algorithm is as follows:
1) place an AABB around each set, check for intersection.
2) In case of intersection, get coordinates of the intersection AABB, throw away all points outside of that box.
4) Start at an arbitrary point in the new box, add it to a list.
5) Check for any point within a distance x from your point, add it to your new list.
5) When you are done with that point, move to the farthest point from the one you started with and repeat.
6) If by the end there are less points in your list than in the box, then your other point set must be futher away than the minimum distance x to discount there being an overlap

This would be much more convenient to show with a diagram, but I do not have the motivation to make one right now

If you have any suggestions or questions concerning my algorithm, I would be very interested to hear them.

-Thomas