2
\$\begingroup\$

So I'm trying to solve a heat/diffusion equation for a continuous space, but I'm not opposed to a grid solution. I'm a little short on the maths needed but have made it work so far.

If I model sources and sinks on a grid, I just need to center a gaussian potential on that coordinate with the appropriate sign. A source is like a positive metaball and a sink is like a negative one. Similarily, I can just do a gaussian blur of the entire image if it has no walls. The sources and sinks will smear together and give the actual solution.

However, if I have walls I can't do that, because there are boundary conditions to the problem all of a sudden. I could incrementally blur by a small amount, then add the walls back in, but I'm looking for a solution that I can lookup any t (time) for directly.

I could also expand the heat map out from sources and sinks by flood filling from those points, but I need the heat value to be implicitly there. I'll be pulling single values of perlin noise out of the air for obstacles and don't want to evaluate the entire field only to pull a single heat value.

So, is there any way I can define the boundary conditions as part of the convolution (gaussian blur) using math or some technique?

I looked at potential fields but I don't think that solves the diffusion exactly. To restate, how do I add boundaries to a diffusion problem and solve for a specific coordinate (x,y,t)? It should be possible since the boundary/obstacle is a single function f(x,y,t).

\$\endgroup\$
  • 2
    \$\begingroup\$ This question might be better served on a different stack exchange, such as physics or computation science. I say this because except for the part of drawing it on the screen, or executing it on the GPU, (or that it might be a small part of a larger game project), there's nothing here that would benefit directly from game programming experience. At least not in the general case. Thermal mechanics is not a trivial subject. \$\endgroup\$ – Seth Battin Jan 17 '15 at 0:28
  • \$\begingroup\$ I think this may be off-topic because it is a specific numerical simulation problem. \$\endgroup\$ – Seth Battin Jan 17 '15 at 0:29
  • \$\begingroup\$ @SethBattin I was thinking it might be better on a different site but as far as I'm aware what I'm asking is not possible to do analytically (I could be wrong) and I don't want to do it numerically (I just want to pull a single random point quickly). Given that and the fact that my boundary is a procedural I thought it was a better fit here. I'm not positive of course. \$\endgroup\$ – A Game Programmer Jan 17 '15 at 0:33
1
\$\begingroup\$

If you're looking for a single heat value you can calculate the distance between your sample point and all sources & sinks in a straight line.

If there is a wall in a straight line, calculate from your sample to the ends of the wall and then to the source/sink.

it gets a bit more complicated with walls made of multiple segments due to being potentially convex/wavy.

Depending on your need, you could account for the walls reflecting/holding heat into the material or not.

It can get complicated but can still be faster than the grid way. Depends on the number of points and walls.

It's running an open-area path-finding algorithm to every heat sources / sinks.

I can't remember what it's called. Someone can probably chime in. I got a total brain fart on the name but here's a quick graph:

enter image description here

When you hit a wall (red line with 'X') you try around both ends and iterate until you find a path around all obstacles. Have to be careful when a wall points straight to a goal there's some rounding errors you have to take care of by not passing exactly at the end points but just a little bit outside.

Every time you hit a wall there's to ways: left & right, you keep the shortest path or use all paths for heat/gas distribution, depends on what you need.

(I didn't draw the 2 blue possibilities to keep it clean.)

The problem is very similar to turning an arbitrary polygon into triangles to render using a GPU (http://en.wikipedia.org/wiki/Polygon_triangulation) but turned inside-out. Maybe looking at those algorithm as well will help.

\$\endgroup\$
  • \$\begingroup\$ "If there is a wall in a straight line" that amounts to evaluating every point along that line doesn't it? Since my obstacles are defined by perlin noise I'll have to pull each of those points to check if the obstacle is there. After a few runs it becomes more economical to do a heat map of the whole area. Which is what I'm trying to avoid because I just don't have enough memory. \$\endgroup\$ – A Game Programmer Jan 21 '15 at 22:33
  • \$\begingroup\$ OH, I missed that part. No, that wont work then. You need vectorized obstacles for my solution. If you have obstacles defined as a grid then you need to use a grid solution or you'll have to convert the perlin noise to vector outlines. \$\endgroup\$ – Stephane Hockenhull Jan 22 '15 at 0:46
0
\$\begingroup\$

Surprisingly enough, a simple Google of "the heat equation" yields kilo-calories of information on the partial-differential equations and common boundary conditions encountered in solving heat-flow problems. The derivation of the equation in one, two, or three dimensions is readily developed from Conservation of Energy and Fourier's Law.

The law of heat conduction, also known as Fourier's law, states that the time rate of heat transfer through a material is proportional to the negative gradient in the temperature and to the area, at right angles to that gradient, through which the heat flows. We can state this law in two equivalent forms: the integral form, in which we look at the amount of energy flowing into or out of a body as a whole, and the differential form, in which we look at the flow rates or fluxes of energy locally.

However, in your case the theoretical evaluation is not of interest, but rather the mathematical evaluation by numerical analysis. The Differential form of Fourier's Law is readily adapted to numerical analysis:

The differential form of Fourier's Law of thermal conduction shows that the local heat flux density, \overrightarrow{q}, is equal to the product of thermal conductivity, k, and the negative local temperature gradient, -\nabla T. The heat flux density is the amount of energy that flows through a unit area per unit time.

If anyone knows how to use LEX to properly format the above from the preceding link, that would be greatly appreciated.

\$\endgroup\$
  • \$\begingroup\$ Thanks for taking a stab at it, but I think you missed the part about my boundary condition issues. The walls are sprinkled around and don't just reside on the edge. If it was the interior of a polygon I was sampling I could pull it off. Then I would use one the easy to find equations. My issue is along the lines of: I dropped a circle insulator in the middle of my field along with the initial sources and sinks. How is my field changed by this insulator? But specifically looking for a convolution operator or similar because it generally won't be a circle. \$\endgroup\$ – A Game Programmer Feb 22 '15 at 19:55

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.