0
\$\begingroup\$

I first tried with a simple axis aligned bounding box to test my algorithm (later shape will be different but always convex 6 faces), but even this case did not work, it always tells me that the point is not inside:

                BoundingBox bb = new BoundingBox(-new Vector3(.5f), new Vector3(.5f));

                var corners = bb.GetCorners();

                bool liesInside = true;
                for (int cornerIndex = 0; cornerIndex < 6; cornerIndex++)
                {                            
                    Plane plane = new Plane(corners[cornerIndex], corners[cornerIndex + 1], corners[cornerIndex + 2]);
                    if (plane.DotCoordinate(rayPos) > 0)
                    {
                        liesInside = false;
                        break;
                    }
                }
| improve this question | | | | |
\$\endgroup\$
  • 1
    \$\begingroup\$ What leads you to believe that three consecutive corners of the convex hull always constitute an inward-oriented triangle on the outer surface, and not a triangle that cuts through the middle or has its normal facing outward? \$\endgroup\$ – DMGregory May 21 at 0:00
  • \$\begingroup\$ Good point, I did not check that. Given I would fix that, would the approach theoretically work? \$\endgroup\$ – codymanix May 21 at 0:14
  • \$\begingroup\$ We'd need to see your implementation. There are ways to make it work, and plenty of opportunities to not work. \$\endgroup\$ – DMGregory May 21 at 0:25
1
\$\begingroup\$

Some basics on convex hull tests for folks that might read this later:

A convex hull is a volume defined by a number of planes (at least 4, but it could be much more). Testing to see which side of a plane a given point is on is trivial (computationally speaking), it's just a dot-product. Go look up "dot product" if you don't know what that is. Do it now. It's important.

Back? Okay, so in a working convex hull test, all the planes would be facing inward or all facing outward. In other words, for a point to be inside, all the dot products would be positive (which is what codymanix is using above), or all negative. You'll need to pick one in advance and stick to it, and all your data defining your hulls needs to stick with it too.

Codymanix is starting with a box, which is defined, as far as we're concerned, by six planes. If all six planes are "facing inward" then we're fine, but what happens when 2 or more of those planes are "facing outward"? All of a sudden, no point in our coordinate system will ever satisfy the positive dot product check on all six planes defining the hull.

To visualize this, lets imagine a square in 2d. The top is labeled "top" and the bottom is labeled "bottom". To be inside this square, a point must be below top and above bottom. With me so far? Okay, not lets move the top until it is below bottom... and we'll keep the tests the same. Now there is no point that is above the top and below the bottom. We've turned our square "inside out" and nothing can be inside it.

I suspect that condymanix's hull has been turned "inside out".

Okay, that's the problem, so how do we fix it?

IIRC, the "front" and "back" of a given triangle are defined by a "winding rule". "Wind" as in "wind your watch" not "wind is blowing". There are two different winding rules, called "left handed" and "right handed". Make a thumbs up gesture, fingers curled into a fist, thumb sticking straight up. The way your fingers curl is the order in which the points on a triangle are ordered to define the "front" of that triangle, the direction your thumb is pointing. Right hand: counter clockwise, left hand: clockwise.

Codymanix, I'm guessing you're mixing left and right handed winding. You need to define your hulls such that the thumbs are all pointed in the same direction. It would be nice if you use the same winding rule as your meshes just for consistency's sake. It will probably also make generating hulls from your meshes easier.

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ Thanks the solution is was at the end very simple. Iam wondering when I googled for solutions to my problen "Check if point is inside convex hull" I just found lots of very long and complicated math heavy code. Do I miss something? \$\endgroup\$ – codymanix May 22 at 17:02

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.