Algorithm for checking if 3D point inside convex polyhedron (square pyramid)
<p>I am looking robust collision detection algorithms and found an awesome book called <strong>Realtime Collision Detection</strong> by Christer Ericson. I am trying to use a particular algorithm which checks whether a given point is inside convex polyhedron (in 3D space these are the square pyramid, cube and tetrahedron (aka pyramid with all sides being a triangle)). In my case I have a square pyramid. The validation of the point is done by using the intersection volume for a given number of halfspaces and determining whether the point is in front or behind all of the planes that are spanned by the polyhedron's sides.  I have difficulties understanding the usage of the argument <code>n</code> (see below) which represents the number of halfspaces for the given polyhedron:</p>

<pre><code>// Test if point p inside polyhedron given as the intersection volume of n halfspaces
int TestPointPolyhedron(Point p, Plane *h, int n) {
    for (int i = 0; i &lt; n; i++) {
        if(DistPointPlane(p, h[i]) &gt; 0.0f) return 0;
    }
    return 1;
}
</code></pre>

<p>with <code>DistPointPlane(...)</code> calculating the distance between a given point and a plane</p>

<pre><code>float DistPointPlane(Point q, Plane p) {
    return Dot(q, p.n) - p.d;
}
</code></pre>

<p>and <code>Plane</code> being a structure that represents a plane in 3D space</p>

<pre><code>struct Plane {
    Vector n; // Plane normal. Point X on the plane satisfies Dot(n, X) = d
    float d;  // d = dot(n, p) for a given point on the plane
}

Plane ComputePlane(Point a, Point b, Point c) {
    Plane p;
    p.n = Normalize(Cross(b - a, c - a));
    p.d = Dot(p.n, a);
    return p;
}
</code></pre>

<p>What the algorithm does is basically the following:</p>

<ol>
<li>For a given point calculate its distance to each plane of the convex polyhedron</li>
<li>Check if distance is negative or positive

<ol>
<li>If distance is negative point lies on the opposite side of the plane's normal so it's behind it.</li>
<li>Else point lies on the same side as the plane's normal so it's in front of it</li>
</ol></li>
<li>If point behind all planes of the given polyhedron it lies <strong>inside</strong> else it lies <strong>outside</strong></li>
</ol>

<p>Now in terms of a square pyramid as far as I can tell there are 10 halfspaces since we have 4 sides and a base each representing a separate plane (so in total there are 5 planes) that divides the 3D space in two halfspaces (<code>5 planes * 2 = 10 halfspaces</code>). What I don't get is the usage of <code>n</code> in the code for the algorithm above. It is used as a termination condition for the loop which iterates through an array of <code>Plane</code> instances. However as mentioned there are 10 halfspaces.</p>

<p>One thing I have thought about after some digging is the fact that the intersection between two planes is a line (edge of the pyramid). Further quoting <a href="http://mathworld.wolfram.com/Plane-PlaneIntersection.html" rel="nofollow noreferrer">Wolfram Mathworld</a></p>

<blockquote>
  <p>To uniquely specify the line, it is necessary to also find a
  particular point on it. This can be determined by finding a point that
  is simultaneously on both planes</p>
</blockquote>

<p>Each of the pyramid's vertices fulfill this requirement since for any given two sides (including the base) we get a line which is between two of the pyramid's vertices. So in terms of intersection we do have 5 (4 for the base and 1 for the apex) however the text in the book (including the comment above the function's implementation) is vague and reading it one might get the wrong idea (at least that's my case).</p>

<p>Is my line of thought close to the truth or am I missing some big chunk in terms of math knowledge?</p>

<p>I have ported the code to Python 3 and altered the algorithm to loop through just my list of planes without taking an additional argument (which, if my thoughts are correct, is basically the same as the original one) and plotted it with <code>matplotlib</code>. It works perfectly fine but I still want to know whether I have understood it correctly or not:</p>

<p><a href="https://i.stack.imgur.com/nZDNM.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/nZDNM.png" alt="enter image description here"></a></p>