Let β 1,…, β n be the barycentric coordinate functions defined in Equation (8.4) relative to the ordered vertices Q 1,…, Q n of a convex polygon. The final property asserts that the functions describing these surfaces are not too complicated-that these surfaces are defined by rational expressions.Įxistence of Barycentric Coordinates for Convex Polygons The fourth property is also key later on in ensuring that the S-patch blossom evaluated at the vertices of the domain polygon provides the dual functionals for S-patches (see Section 8.4.4). The third property will guarantee that the boundary curves of these surfaces are the Bezier curves determined by their boundary control points, and the fourth property ensures that these surfaces will interpolate their corner control points. The first two properties of the barycentric coordinate functions for convex polygons are required because we want the multisided Bezier surfaces constructed from these functions to be affine invariant and to lie in the convex hulls of their control points. β k = 0 on the line Q iQ i+1, k ≠ i,i + 1. β k = 0 on the line P iP i+1, k ≠ i,i + 1.ģ. The method extends to higher dimensions and to arbitrary convex objects, not necessarily polygons or polyhedra.ģ.
If the distance to the current edge is smaller or equal to the distance from the two neighboring edges, then the current distance is the minimum distance to the polygon boundary.įinally, given a point and a convex polygon, the GJK algorithm described in Section 6.10 provides a viable alternative to a boundary search algorithm that looks for a closest feature. Moreover, a further reduction in calculations is attained by checking if the next point-to-segment distance is larger than the current one. By testing this dot product first, and if negative, the potential division that occurs in the point-to-segment distance calculation is avoided. The visible edges are in a cone with vertex at the test point and whose sides are tangent to the convex polygon.Īssuming that each edge 〈 P i, P i + 1 〉 has an associated normal vector n → i that points to the interior of the polygon, an edge is visible only if n → i Only those edges visible to the test point must be searched for the closest point to the test point. The process of locating a point in a subdivision of the plane implied by the mesh is called the planar point location problem.įigure 6.13. Those edges shared by only one polygon form the mesh boundary-another polygon that is itself convex since the parallel projection of a convex polyhedron onto a plane is a convex polygon.
Each edge in the mesh is shared by either one or two polygons.
The technical issue is how to determine which convex polygon in a planar mesh contains a specified point. We now only need to determine if P is on the line segment contained in the polyhedron-a simple task. The line of constant ( x, y) containing P intersects the polyhedral faces corresponding to the two planar convex polygons. The convex polygon in that mesh that contains P is also computed. The ( x, y) portion of P must necessarily be contained in the lower planar mesh. If it is inside the mesh, the convex polygon that contains the point must be computed. If it is outside the mesh, then P cannot be in the polyhedron. Given a test point P, the ( x, y) portion of the point is tested for containment in the upper planar mesh. The two planar meshes consist of convex polygons (the polyhedron faces were convex). Faces whose normals have a zero z-component are not relevant and can be ignored. Those with a negative z-component are projected onto the other planar mesh, called the lower planar mesh. Faces whose outer-pointing normals have a positive z-component are projected onto one planar mesh, called the upper planar mesh. Two xy-planar meshes of convex polygons are generated. The second step is to iterate over the faces of the polyhedron. That is, if P is outside the bounding box, then it cannot be inside the polyhedron. The first step is to iterate over the vertices to compute the axis-aligned bounding box of the polyhedron. As such, the method is useful when many point-in-convex-polyhedron queries must be answered. However, a method similar to the one that bisected on the top half and bottom half of convex polygons does extend to three dimensions, but with some preprocessing that takes O( n) time. The index bisection method for convex polygons that supported an O(log n) query does not apply to convex polyhedrons because of the added complexity of the third dimension. EBERLY, in Geometric Tools for Computer Graphics, 2003 An Asymptotically Faster Method