时间戳

首页 > 解决方案 > 金属着色器确定凸四边形内的点

ios - 金属着色器确定凸四边形内的点

问题描述

金属着色语言中是否有内置方法来确定一个点是否位于凸四边形（或一般的凸多边形）内？如果不是，确定相同的最快方法是什么？

标签： iosmetalmetalkit

解决方案

我一直无法找到满足您需求的金属功能。我将提出我认为相对较快的解决方案（尽管请随时批评或改进它）。请注意，我假设您在 2D 中工作（或者至少是顶点共面的多边形的 2D 帧）

constant constexpr float M_PI = 3.14159265358979323846264338327950288;
constant constexpr float2 iHat = float2(1, 0); 

namespace metal {
    
    // The sawtooth function
    METAL_FUNC float sawtooth(float f) { return f - floor(f); }

    /// A polygon with `s` sides oriented with `transform` that converts points from the system within which the polygon resides.
    /// The frame "attached" to the polygon has an X axis passing through a vertex of the polygon. `circR` refers to the radius
    /// of the circumscribed circle that passes through each of the verticies
    struct polygon {
        const uint s;
        const float circR;
        const float3x3 transform;
    
        // Constructor
        polygon(uint s, float circR, float3x3 transform) : s(s), circR(circR), transform(transform) {}
        
        // `pt` is assumed to be a point in the parent system. `conatins` excludes the set of points along the edges of the polygon
        bool contains(float2 pt);
    };
}


bool metal::polygon::contains(float2 pt) {
    // The position in the frame of the polygon
    float2 poly_pt = (transform * float3(pt, 1)).xy;
    
    // Using the law of sines, we can determine the distance that is allowed (see below)
    float sqDist = distance_squared(0, poly_pt);
    
    // Outside circle that circumscibes the polygon
    if (sqDist > circR * circR) return false;
    
    // Calculate the angle the point makes with the x axis in the frame of the polygon.
    // The wedgeAngle is the angle that is formed between two verticies connected by an edge
    float wedgeAngle = 2 * M_PI / s;
    float ptAngle = dot(poly_pt, iHat);
    float deltaTheta = sawtooth(ptAngle / wedgeAngle) * wedgeAngle;

    // Calculate the maximum distance squared at this angle that is allowed at this angle relative to
    // line-segment joining the `floor(ptAngle / wedgeAngle)`th (kth) vertex with the center of the polygon.
    // This is done by viewing the polygon from a frame whose X-axis is the line from the center of the polygon
    /// to the kth vertex. Draw line segment L1 from the kth vertex to the (k+1)th vertex and mark its endpoints K and L respectively.
    /// Draw line segment L2 from the center of the polygon to the point under consideration and mark L2's intersection with L1
    /// as "A". If the center of the triangle is "O", then triangle "OKL" is isosceles with vertex angle `wedgeAngle` and
    /// base angle B = M_PI / 2 - wedgeAngle / 2 (since 2B + wedge = M_PI). Triangle "OAK" contains `deltaTheta` and B.
    /// Thus, the third angle is M_PI - B - deltaTheta. `maxR` results from the law of sines with this third angle and the
    /// base angle B' contained within triangle "OAK".
    float maxR = circR * sin(M_PI / 2 - wedgeAngle / 2) / sin(M_PI / 2 + wedgeAngle / 2 - deltaTheta);
    
    return sqDist < maxR * maxR;
}

请注意，我选择了一个constexpr值来代替宏声明。两者都行。

推荐阅读