**2**

###
#1
Members - Reputation: **129**

Posted 06 May 2014 - 10:07 AM

###
#3
Crossbones+ - Reputation: **5031**

Posted 07 May 2014 - 05:39 AM

I don't think that anything with "evaluate the integral" in it has a realistic chance of working as a collision system (unless the curve is a particular special case for which you can hardcode an easy closed form solution).

Usually you want something that works realtime or at least kind-of-realtime, and the algorithm is invoked for a few hundred or thousand objects. Evaluating a few thousand integrals of "some" function isn't precisely a lightweight operation. Of course, there may be cases where you simply don't care how long it takes...

###
#4
Members - Reputation: **129**

Posted 07 May 2014 - 06:44 AM

I have a figure which is given by array of triangles and I have couple of points that i know for sure that they are inside my figure and I have my testing point. I build a plane with these three points.

###
#5
Crossbones+ - Reputation: **9262**

Posted 07 May 2014 - 08:27 AM

You can use LaTeX here. Just enclose your code in \ ( and \ ) (without the spaces) for inline math, and \ [ and \ ] for display math. For instance \( \int_0^\infty e^x ~ \mathrm{d} x \).

Seems to me that you don't really need to compute the full path integral, since you only require its sign. You can do much better. If your curve/surface is closed and bounded you can use the even-odd theorem, which basically says that if you draw a ray from your point to infinity in any direction, the point is inside the curve if and only if it intersects the curve an odd number of times. This rule works for any (nondegenerate) curve or surface, convex or not. Note this is an if and only if condition, so one ray is enough to decide (and, in fact, it is transitive, in the sense that if the segment between point X and point Y has an even number of intersections, then X and Y are both inside or both outside). This is really just evaluating the sign of the aforementioned path integral, but much easier to implement because it doesn't require the concept of an integral and transforms the problem into a ray-surface intersection problem for which efficient solutions are known.

If your curve is simple, you can probably intersect it analytically with a line. If it is sufficiently well-behaved and you have a scalar field of it available, like in your first post, you can bisect to find intersections, which is at least tractable, if not terribly efficient. Otherwise, you can always raycast or raymarch, possibly using an acceleration structure. In practice, faster algorithms are used for the broad phase, while more sophisticated algorithms are used to resolve collisions accurately between polygons (narrow phase) often by splitting them into convex polygons beforehand.

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

- *Pessimal Algorithms and Simplexity Analysis*