2
$\begingroup$

I am attempting to write a program in which I must determine if a point with known x, y, z coordinates exists within a solid with 8 vertices. All the dimensions of the vertices are known. In terms of the programming, we must determine formulas such that it produces a true or false statement, so I assume that the point must pass (6) statements that show it is contained by each plane. How would I most simply set up a check for the point in terms of each plane?

Also, from the link Given 4 corner points of a rectangle in 3d space, how to find its "plane" equation? I see a definite formula, but I would like to see how it would look when expanded into a simple equation.

$\endgroup$
2
  • 1
    $\begingroup$ How is the solid defined from 8 vertices? $\endgroup$
    – vadim123
    Feb 22, 2015 at 21:12
  • $\begingroup$ Think of it as a cube, then drag some of the corners around. $\endgroup$
    – user192061
    Feb 22, 2015 at 23:30

1 Answer 1

0
$\begingroup$

You may wish to read up on the point in polygon/polyhedron problem.

What you do is construct a ray coming out of the point in question, in one direction (e.g. $(x_0, y_0, z_0)^{T}+\lambda \mathbf{i}\ \ \ \forall \lambda\in \mathbb{R}_{\geq 0}$). If this ray crosses the solid an odd number of times, it's inside the solid; otherwise it's outside.

To implement this you'll probably want to to find the intersection of your ray with each face of your solid, and then check that $\lambda\geq 0$ and that the intersection point is actually inside the face in question (to check if the intersection point is inside the face, you can a similar method to the above, except that you're checking for intersection with the edges of the face).

To answer the second part of your question:

Pick any 3 points on the rectangle (probably easiest to choose 3 corners), call them $\mathbf{a}, \mathbf{b}, \mathbf{c}$.

If you want the vector equation (which is probably easier to work with here), then it's just $\mathbf{a}+\lambda(\mathbf{a}-\mathbf{b})+\mu(\mathbf{a}-\mathbf{c})\ \ \ (\forall \lambda, \mu \in \mathbb{R})$. If you want the Cartesian equation, the normal $\mathbf{n}$ to the plane can be found by $(\mathbf{a}-\mathbf{b})\times(\mathbf{a}-\mathbf{c})$ (where $\times$ denotes the cross product). If we then write $\mathbf{n}=(p, q, r)^{T}$, then the equation of the plane has the form $px+qy+rz=d$, for some constant $d$.

If the polygon in question is convex with $8$ vertices (and you want to test a large number of points), then you may be able to use an inequality method (I think this'll work, but I've got no proof). First get a point $K$ that you know is inside the polygon (to get such a point, I think you could find the centres of the each of the faces, and then calculate the centroid of these $6$ points). Once you've got $K$, write out the cartesian equation for each face $ F $, i.e. $px+qy+rz=d$. Now, plug $ x, y, z $ into $px+qy+rz$ for this given point and note whether it's $ > $ or $ < $ than $d$. Then any given point is inside the polygon iff it meets the same direction inequality as $K$ for all $6$ faces.

$\endgroup$
8
  • $\begingroup$ I would like to avoid ray casting; It feels rather resource heavy considering the amount of objects I am going to have vertices checked for. $\endgroup$
    – user192061
    Feb 23, 2015 at 2:39
  • 1
    $\begingroup$ How many points are you testing for each given polygon? $\endgroup$
    – Esteemator
    Feb 23, 2015 at 9:13
  • $\begingroup$ Depends. I'm writing a 3D renderer, and I'm aiming for a few characters on screen (preferably 3, but probably 2, each with maybe 50 - 60 polygons) which means about 400 to 500 vertices being checked. $\endgroup$
    – user192061
    Feb 23, 2015 at 13:17
  • $\begingroup$ And how much are you allowed to deform the solid from a cube (e.g. if a cube has opposite vertices at (0, 0, 0) and (1, 1, 1), are we allowed to make a concave polyhedron by translating the point (1, 1, 1) by the vector (-0.9, -0.9, -0.9))? $\endgroup$
    – Esteemator
    Feb 23, 2015 at 14:01
  • $\begingroup$ The shape is heavily deviated from a cube. One face represents the screen you are viewing from, and the other face is a projection of the first one. Connecting the two gives the viewing area in which to render objects, so I'll need to check if the vertex lies in there. $\endgroup$
    – user192061
    Feb 23, 2015 at 20:05

You must log in to answer this question.