CODEWITHSUNDEEP
c++algorithmgeometry
ashleysmithgpu
ashleysmithgpu

Reputation: 1935

Point in vertex defined box algorithm?

How would I test if a point is within a 3D box that is defined by its 8 points only or by its 6 quads? (Dont have access to normal vectors)

The box is made up of triangles, but the two polygons on each side are aligned so could be considered a quad.

Upvotes: 3

Views: 288

Answers (3)

saeedn
saeedn

Reputation: 3378

You can test that by forming 6 square pyramids with your point as head and 4 vertices of a each quad as base, then summing up volumes of square pyramids. If sum of volumes is equal to volume of your box, the point is in the box. If sum of volumes is greater than your box's volume, it's outside of the box (sum of volumes would never be less than box volume).

For calculating volume of each square pyramid, you can break it into two tetrahedrons where their volume could be easily calculated by a mix vector product. You can calculate volume of box with mix vector product as well.

Upvotes: 1

Skizz
Skizz

Reputation: 71060

A crazy idea, perhaps:-

  • set up a 3d orthographic projection on a 1x1 pixel viewport
  • set the camera and near clip plane such the the point of interest is on the near clip plane
  • render the box without any culling
  • if only one pixel is rendered then point is inside the box, 0 or 2 or more pixels rendered then the point is outside the box

Upvotes: 0

Tommy
Tommy

Reputation: 100622

Assuming the points have a known order, you could work out the normal vectors. There's no need to normalise them for this sort of test so the cost isn't prohibitive. If you already know it's a cuboid then you need work out only two normals as you can get the third with the cross product, then use the other points to get distances. Obviously you're cross-producting to get normals anyway, so that's more a question about what information you want to expose to whom.

If the points don't have a known order then you can probably apply a miniature version of QuickHull — starting from the initial triangle you should find either that you already have one of the real edge faces (in which case you can use that normal and find the relevant points at the other extreme of that normal plus the requirement of mutual orthogonality to get to all three normals) or that one step gives you at least two real edges, which you'll spot when their local sets of points in front go empty.

Upvotes: 1

Related Questions