4
\$\begingroup\$

enter image description here

Eventually this problem will be 3D, so I would like a solution that works in 3D.

My player is looking forwards. There is an axis-aligned box on the screen (FOV is guaranteed to be 90, so boxes behind the player aren't considered.)

I want to get the coordinates of the point on box that is closest to the player's looking direction.

I.e., if the player turned towards the box, which point of the box would intersect with their line of vision first?

\$\endgroup\$
6
  • \$\begingroup\$ What will the shape be in 3d? A rectangular solid? \$\endgroup\$
    – Tim Holt
    May 24, 2019 at 19:15
  • \$\begingroup\$ @TimHolt a cuboid (an "axis-aligned box") so yeah a rectangular solid \$\endgroup\$
    – minseong
    May 24, 2019 at 21:59
  • \$\begingroup\$ How does this work in 3d? In 2-d, the 'edge of vision' of the player is two lines and the player sees an (infinitely long) circle sector in between. There are many generalisations of this in 3d, some of which will be much easier to work with than others. \$\endgroup\$ May 24, 2019 at 23:10
  • \$\begingroup\$ @ScienceSnake idk what you mean \$\endgroup\$
    – minseong
    May 24, 2019 at 23:12
  • 1
    \$\begingroup\$ @ScienceSnake yes along a single line, imagine a player with a long pokey nose i want to know what that hits first \$\endgroup\$
    – minseong
    May 25, 2019 at 10:22

4 Answers 4

3
\$\begingroup\$

I wasn't happy with any of the answers here, as I wanted an answer for the 3D case, so I went ahead and wrote a shadertoy which demonstrates how to query the closest point between a line and a box.

Here's a link to the shadertoy code, as well as an image of the output:

image of the output

Code:

// The MIT License
// Copyright © 2024 Nate Morrical
// Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

// The below is a collection of functions to compute the closest point between 
// a point / line / segment and a box / face. 

// Returns the closest point from a 3D point to a 3D box
// The box is axis aligned, and centered at the origin
//   o - the query origin
//   b - the box radius (3 half side lengths)
vec3 pointBoxQuery( vec3 o, vec3 b ) {
    vec3 closest = o;
    for (int i = 0; i < 3; ++i) {
        if (o[i] < -b[i])
            closest[i] = -b[i];
        else if (o[i] > b[i])
            closest[i] = b[i];
    }
    return closest;
}

// Returns the closest point from an infinite 3D line to 3D box face, plus the closest "t" along o+t*d
// Based on https://www.geometrictools.com/Documentation/DistanceLine3Rectangle3.pdf
// The box is axis aligned, centered at the origin, and d is expected to point towards 
// the first octant (reflected s.t. all d components are positive).
//   i - the indirection indices for the face
//   o - the origin of the segment
//   d - the direction along the segment (which does not need to be normalized)
//   b - the box radius (3 half side lengths)
vec4 lineFaceQuery(ivec3 i, vec3 o, vec3 d, vec3 b)
{
    vec3 PmE = o - b;
    vec3 PpE = o + b;
    
    vec3 bi = vec3(b[i[0]], b[i[1]], b[i[2]]);
    vec3 oi = vec3(o[i[0]], o[i[1]], o[i[2]]);
    vec3 di = vec3(d[i[0]], d[i[1]], d[i[2]]);
    vec3 PmEi = vec3(PmE[i[0]], PmE[i[1]], PmE[i[2]]);
    vec3 PpEi = vec3(PpE[i[0]], PpE[i[1]], PpE[i[2]]);
    
    vec4 c;
    if (di[0] * PpEi[1] >= di[1] * PmEi[0])
    {
        if (di[0] * PpEi[2] >= di[2] * PmEi[0])
        {
            // v[i1] >= -e[i1], v[i2] >= -e[i2] (distance = 0)
            c = vec4(bi[0], oi[1] - di[1] * PmEi[0] / di[0], oi[2] - di[2] * PmEi[0] / di[0], -PmEi[0] / di[0]);
        }
        else
        {
            // v[i1] >= -e[i1], v[i2] < -e[i2]
            float lenSqr = di[0] * di[0] + di[2] * di[2];
            float tmp = lenSqr * PpEi[1] - di[1] * (di[0] * PmEi[0] + di[2] * PpEi[2]);
            if (tmp <= 2. * lenSqr * bi[1])
            {
                float t = tmp / lenSqr;
                lenSqr += di[1] * di[1];
                tmp = PpEi[1] - t;
                float delta = di[0] * PmEi[0] + di[1] * tmp + di[2] * PpEi[2];
                c = vec4(bi[0], t - bi[1], -bi[2], -delta / lenSqr);
            }
            else
            {
                lenSqr += di[1] * di[1];
                float delta = di[0] * PmEi[0] + di[1] * PmEi[1] + di[2] * PpEi[2];
                c = vec4(bi[0], bi[1], -bi[2], -delta / lenSqr);
            }
        }
    }
    else
    {
        if (di[0] * PpEi[2] >= di[2] * PmEi[0])
        {
            // v[i1] < -e[i1], v[i2] >= -e[i2]
            float lenSqr = di[0] * di[0] + di[1] * di[1];
            float tmp = lenSqr * PpEi[2] - di[2] * (di[0] * PmEi[0] + di[1] * PpEi[1]);
            if (tmp <= 2. * lenSqr * bi[2])
            {
                float t = tmp / lenSqr;
                lenSqr += di[2] * di[2];
                tmp = PpEi[2] - t;
                float delta = di[0] * PmEi[0] + di[1] * PpEi[1] + di[2] * tmp;
                c = vec4(bi[0], -bi[1], t - bi[2], -delta / lenSqr);
            }
            else
            {
                lenSqr += di[2] * di[2];
                float delta = di[0] * PmEi[0] + di[1] * PpEi[1] + di[2] * PmEi[2];
                c = vec4(bi[0], -bi[1], bi[2], -delta / lenSqr);
            }
        }
        else
        {
            // v[i1] < -e[i1], v[i2] < -e[i2]
            float lenSqr = di[0] * di[0] + di[2] * di[2];
            float tmp = lenSqr * PpEi[1] - di[1] * (di[0] * PmEi[0] + di[2] * PpEi[2]);
            if (tmp >= 0.)
            {
                // v[i1]-edge is c
                if (tmp <= 2. * lenSqr * bi[1])
                {
                    float t = tmp / lenSqr;
                    lenSqr += di[1] * di[1];
                    tmp = PpEi[1] - t;
                    float delta = di[0] * PmEi[0] + di[1] * tmp + di[2] * PpEi[2];
                    c = vec4(bi[0], t - bi[1], -bi[2], -delta / lenSqr);
                }
                else
                {
                    lenSqr += di[1] * di[1];
                    float delta = di[0] * PmEi[0] + di[1] * PmEi[1] + di[2] * PpEi[2];
                    c = vec4(bi[0], bi[1], -bi[2], -delta / lenSqr);
                }
            }
            else {
                lenSqr = di[0] * di[0] +
                di[1] * di[1];
                tmp = lenSqr * PpEi[2] - di[2] * (di[0] * PmEi[0] + di[1] * PpEi[1]);
                if (tmp >= 0.)
                {
                    // v[i2]-edge is c
                    if (tmp <= 2. * lenSqr * bi[2])
                    {
                        float t = tmp / lenSqr;
                        lenSqr += di[2] * di[2];
                        tmp = PpEi[2] - t;
                        float delta = di[0] * PmEi[0] + di[1] * PpEi[1] + di[2] * tmp;
                        c = vec4(bi[0], -bi[1], t - bi[2], -delta / lenSqr);
                    }
                    else
                    {
                        lenSqr += di[2] * di[2];
                        float delta = di[0] * PmEi[0] + di[1] * PpEi[1] + di[2] * PmEi[2];
                        c = vec4(bi[0], -bi[1], bi[2], -delta / lenSqr);
                    }
                }
                else {
                    // (v[i1],v[i2])-corner is c
                    lenSqr += di[2] * di[2];
                    float delta = di[0] * PmEi[0] + di[1] * PpEi[1] + di[2] * PpEi[2];
                    c = vec4(bi[0], -bi[1], -bi[2], -delta / lenSqr);
                }
            }            
        }
    }
    
    ivec3 map;
    map[i[0]] = 0;
    map[i[1]] = 1;
    map[i[2]] = 2;
    return vec4(c[map[0]], c[map[1]], c[map[2]], c.w);
}
            
// Returns the closest point from an infinite 3D line to a 3D box,  plus the closest "t" along o+t*d
//   o - the origin of the segment
//   d - the direction along the segment (which does not need to be normalized)
//   b - the box radius (3 half side lengths)
vec4 lineBoxQuery( vec3 o, vec3 d, vec3 b )
{
    vec4 closest;

    // Transform the line direction to the first octant using reflections.
    bvec3 reflected = lessThan(d, vec3(0.));
    o = mix(o, -o, reflected);
    d = mix(d, -d, reflected);
    
    // point minus extent
    vec3 PmE = o - b;
    
    // face indices
    ivec3 i;
    
    // line intersects planes x or z
    if (d[1] * PmE[0] >= d[0] * PmE[1])
        // line intersects x = e0 if true, z = e2 if false
        i = (d[2] * PmE[0] >= d[0] * PmE[2]) ? ivec3(0, 1, 2) : ivec3(2, 0, 1);
    // line intersects planes y or z
    else
        // line intersects y = e1 if true, z = e2 if false
        i = (d[2] * PmE[1] >= d[1] * PmE[2]) ? ivec3(1, 2, 0) : ivec3(2, 0, 1);
    
    // Query closest point on face
    closest = lineFaceQuery(i, o, d, b);
    
    // Account for previously applied reflections.
    closest.xyz = mix(closest.xyz, -closest.xyz, reflected);
    return closest;
}

// Returns the closest point from a finite 3D segment to a 3D box, plus the closest "t" along o+t*d
//   s - the start of the segment
//   e - the end of the segment
//   b - the box radius (3 half side lengths)
vec4 segmentBoxQuery( vec3 s, vec3 e, vec3 b ) {
    vec3 o = s;
    vec3 d = e - s;
    vec4 lbOutput = lineBoxQuery(o, d, b);
    // If closest is within the segment, return that result directly
    if (lbOutput.w >= 0. && lbOutput.w <= 1.) 
        return lbOutput;
    
    // Otherwise, compute the closest point to either side of the segment
    float parameter = (lbOutput.w < 0.) ? 0. : 1.;
    vec3 pbOutput = pointBoxQuery(o + d * parameter, b);
    return vec4(pbOutput, parameter);
}

//------------------------------------------------------------

// https://iquilezles.org/articles/distfunctions
float sdBox( vec3 p, vec3 b )
{
    vec3 d = abs(p) - b;
    return min(max(d.x,max(d.y,d.z)),0.0) + length(max(d,0.0));
}

// https://iquilezles.org/articles/distfunctions
float sdSphere( vec3 p, vec3 cen, float rad )
{
    return length(p-cen)-rad;
}

// https://iquilezles.org/articles/distfunctions
float sdCapsule( vec3 p, vec3 a, vec3 b, float r )
{
    vec3 pa = p-a, ba = b-a;
    float h = clamp( dot(pa,ba)/dot(ba,ba), 0.0, 1.0 );
    return length( pa - ba*h ) - r;
}

// https://iquilezles.org/articles/distfunctions
float sdBoxFrame( vec3 p, vec3 b, float e )
{
       p = abs(p  )-b;
  vec3 q = abs(p+e)-e;

  return min(min(
      length(max(vec3(p.x,q.y,q.z),0.0))+min(max(p.x,max(q.y,q.z)),0.0),
      length(max(vec3(q.x,p.y,q.z),0.0))+min(max(q.x,max(p.y,q.z)),0.0)),
      length(max(vec3(q.x,q.y,p.z),0.0))+min(max(q.x,max(q.y,p.z)),0.0));
}

// https://iquilezles.org/articles/distfunctions
float sdCone(vec3 p, vec3 a, vec3 b, float ra, float rb)
{
    float rba  = rb-ra;
    float baba = dot(b-a,b-a);
    float papa = dot(p-a,p-a);
    float paba = dot(p-a,b-a)/baba;

    float x = sqrt( papa - paba*paba*baba );

    float cax = max(0.0,x-((paba<0.5)?ra:rb));
    float cay = abs(paba-0.5)-0.5;

    float k = rba*rba + baba;
    float f = clamp( (rba*(x-ra)+paba*baba)/k, 0.0, 1.0 );

    float cbx = x-ra - f*rba;
    float cby = paba - f;
    
    float s = (cbx < 0.0 && cay < 0.0) ? -1.0 : 1.0;
    
    return s*sqrt( min(cax*cax + cay*cay*baba,
                       cbx*cbx + cby*cby*baba) );
}

//------------------------------------------------------------
const vec3 box_rad = vec3(0.5,0.4,0.3);

vec2 map( in vec3 pos, bool showBox, bool showCapsule, in vec3 sampleLineStart, in vec3 sampleLineStop )
{
    // compute closest point to the segment on the surace of the box
    vec4 result = segmentBoxQuery(sampleLineStart, sampleLineStop, box_rad );
    vec3 closestPointOnLine = mix(sampleLineStart, sampleLineStop, result.w);
    vec3 closestPointOnBox = result.xyz;
    
    vec2 res = vec2(1e38f);
    
    // query line
    {
    float d = sdCapsule( pos, sampleLineStart, sampleLineStop, 0.015 );
    if( d<res.x ) res =  vec2( d, 1.0 );
    }
    
    // closest point on line
    {
    float d = sdSphere( pos, closestPointOnLine, 0.06 );
    if( d<res.x ) res = vec2( d, 1.0 );
    }
    
    // Closest point on box
    {
    float d = sdSphere( pos, closestPointOnBox, 0.06 );
    if( d<res.x ) res = vec2( d, 4.0 );
    }
    
    // box (semi-transparent)    
    if( showBox )
    {
    float d = sdBox( pos, box_rad );
    if( d<res.x ) res =  vec2( d, 5.0 );
    }

    // segment from line to box
    {
    float d = sdCapsule( pos, closestPointOnLine, closestPointOnBox, 0.015 );
    if( d<res.x ) res =  vec2( d, 4.0 );
    }
    
    // box edges
    {
    float d = sdBoxFrame( pos, box_rad, 0.01 );
    if( d<res.x ) res =  vec2( d, 5.0 );
    }
    
    // Capsule demonstrating correctness.
    if (showCapsule){
    float radius = distance(closestPointOnBox, closestPointOnLine);   
    float d = sdCapsule( pos, sampleLineStart, sampleLineStop, radius );
    if( d<res.x ) res =  vec2( d, 1.0 );
    }
    
    return res;
}

// https://iquilezles.org/articles/normalsSDF
vec3 calcNormal( in vec3 pos, in bool showBox, in bool showCapsule, in vec3 sampleLineStart, in vec3 sampleLineStop )
{
    vec2 e = vec2(1.0,-1.0)*0.5773;
    const float eps = 0.0005;
    return normalize( e.xyy*map( pos + e.xyy*eps, showBox, showCapsule, sampleLineStart, sampleLineStop ).x + 
                      e.yyx*map( pos + e.yyx*eps, showBox, showCapsule, sampleLineStart, sampleLineStop ).x + 
                      e.yxy*map( pos + e.yxy*eps, showBox, showCapsule, sampleLineStart, sampleLineStop ).x + 
                      e.xxx*map( pos + e.xxx*eps, showBox, showCapsule, sampleLineStart, sampleLineStop ).x );
}

// https://iquilezles.org/articles/rmshadows
float calcSoftShadow( vec3 ro, vec3 rd, bool showBox, bool showCapsule, in vec3 sampleLineStart, in vec3 sampleLineStop )
{
    float res = 1.0;
    const float tmax = 2.0;
    float t = 0.001;
    for( int i=0; i<64; i++ )
    {
        float h = map(ro + t*rd, showBox, showCapsule, sampleLineStart, sampleLineStop).x;
        res = min( res, 64.0*h/t );
        t += clamp(h, 0.01,0.5);
        if( res<-1.0 || t>tmax ) break;
        
    }
    res = max(res,-1.0);
    return 0.25*(1.0+res)*(1.0+res)*(2.0-res); // smoothstep, in [-1,1]
}

#if HW_PERFORMANCE==0
#define AA 1
#else
#define AA 2
#endif

void mainImage( out vec4 fragColor, in vec2 fragCoord )
{
    vec3 tot = vec3(0.0);
    #if AA>1
    for( int m=0; m<AA; m++ )
    for( int n=0; n<AA; n++ )
    {
        // pixel coordinates
        vec2 o = vec2(float(m),float(n)) / float(AA) - 0.5;
        vec2 p = (2.0*(fragCoord+o)-iResolution.xy)/iResolution.y;
        // pixel sample
        ivec2 samp = ivec2(fragCoord)*AA + ivec2(m,n);
        // time sample
        float td = 0.5+0.5*sin(fragCoord.x*114.0)*sin(fragCoord.y*211.1);
        float time = iTime - 0.5*(1.0/60.0)*(td+float(m*AA+n))/float(AA*AA-1);
        #else    
        // pixel coordinates
        vec2 p = (2.0*fragCoord-iResolution.xy)/iResolution.y;
        // pixel sample
        ivec2 samp = ivec2(fragCoord);
        // time sample
        float time = iTime;
        #endif

        // animate camera
        float an = 0.25*time + 6.283185*iMouse.x/iResolution.x;
        vec3 ro = vec3( 2.4*cos(an), 0.7, 2.4*sin(an) );
        vec3 ta = vec3( 0.0, -0.15, 0.0 );

        // camera matrix
        vec3 ww = normalize( ta - ro );
        vec3 uu = normalize( cross(ww,vec3(0.2,1.0,0.0) ) );
        vec3 vv = normalize( cross(uu,ww));

        // animate query line
        vec3 sampleLineStart = -sin(time*0.5*vec3(1.0,1.1,1.2)+vec3(4.0,2.0,1.0));
        vec3 sampleLineStop  = -cos(time*0.5*vec3(1.0,1.1,1.2)+vec3(4.0,2.0,1.0));

        // make box transparent
        bool showBox = ((samp.x+samp.y)&1)==0;     // 50% opaque
        bool showCapsule = ((samp.x+samp.y+1)&1)==0; 

        // create view ray
        vec3 rd = normalize( p.x*uu + p.y*vv + 1.5*ww );

        // raycast
        const float tmax = 5.0;
        float t = 0.0;
        float m = -1.0;
        for( int i=0; i<256; i++ )
        {
            vec3 pos = ro + t*rd;
            vec2 hm = map(pos,showBox,showCapsule,sampleLineStart, sampleLineStop);
            m = hm.y;
            if( hm.x<0.0001 || t>tmax ) break;
            t += hm.x;
        }
    
        // shade background
        vec3 col = vec3(0.05)*(1.0-0.2*length(p));
        
        // shade objects
        if( t<tmax )
        {
            // geometry
            vec3  pos = ro + t*rd;
            vec3  nor = calcNormal(pos,showBox,showCapsule,sampleLineStart, sampleLineStop);

            // color
            vec3  mate = 0.55 + 0.45*cos( m + vec3(0.0,1.0,1.5) );
            
            // show distance isolines on box
            if( abs(m-5.0)<0.5 )
            {
                vec4 result = segmentBoxQuery(sampleLineStart, sampleLineStop, box_rad);
                vec3 closestPointOnLine = mix(sampleLineStart, sampleLineStop, result.w);
                vec3 closestPointOnBox = result.xyz;
    
                float dref = sdBox( closestPointOnLine, box_rad );
                float dsam = length(pos-closestPointOnLine);
                mate += smoothstep(0.8,0.9,sin((dsam-dref)*80.0))*exp2(-12.0*(dsam-dref)*(dsam-dref));
            }
            // Show distance isolines on open capsule
            if( abs(m-1.0)<0.6 )
            {
                vec4 result = segmentBoxQuery(sampleLineStart, sampleLineStop, box_rad);
                vec3 closestPointOnLine = mix(sampleLineStart, sampleLineStop, result.w);
                vec3 closestPointOnBox = result.xyz;
    
                float dref = sdCapsule( closestPointOnBox, sampleLineStart, sampleLineStop, .1 );
                float dsam = length(pos-closestPointOnBox);
                mate += smoothstep(0.8,0.9,sin((dsam-dref)*80.0))*exp2(-12.0*(dsam-dref)*(dsam-dref));
            }
                        
            // lighting 
            col = vec3(0.0);
            {
              // key light
              vec3  lig = normalize(vec3(0.3,0.7,0.2));
              float dif = clamp( dot(nor,lig), 0.0, 1.0 );
              if( dif>0.001 ) dif *= calcSoftShadow(pos+nor*0.001,lig,showBox,showCapsule,sampleLineStart,sampleLineStop);
              col += mate*vec3(1.0,0.9,0.8)*dif;
            }
            {
              // dome light
              float dif = 0.5 + 0.5*nor.y;
              col += mate*vec3(0.2,0.3,0.4)*dif;
            }
        }

        // gamma        
        col = pow( col, vec3(0.4545) );
        tot += col;
    #if AA>1
    }
    tot /= float(AA*AA);
    #endif

    // cheap dithering
    tot += sin(fragCoord.x*114.0)*sin(fragCoord.y*211.1)/512.0;

    fragColor = vec4( tot, 1.0 );
}

I believe the implementation is relatively optimized, although it's a bit branchy... (Suggestions are welcome :)). The relevant implementation would be 'segmentBoxQuery'

The idea is to compute the distance from the line to only the closest box face. We first transform the box such that its origin is at 0, then to represent the box through its extents relative to 0. Then to make determining which face is closest to the segment, we reflect the direction of the segment to fall into the first octant (and reflect back once we have the closest point).

From there, we determine which box face to test against by doing a couple line-plane intersection tests.

For querying the closest point on the plane, we break up the test into 9 cases, as explained in greater depth here):

Table 3. The regions of the partitioning. Each table entry contains the region name, the algebraic constraints defining the region, the rectangle point closest to \$P = C + x_0U_0 + x_1U_1 + x_2U_2\$ and the squared distance from the rectangle to \$P\$.

$$\small \begin{array}{c|c|c} \begin{array}{c} R_{−+}, x_0 < −e_0, x_1 > e_1 \\ C − e_0U_0 + e_1U_1 \\ (x_0 + e_0)^2 + (x_1 − e_1)^2 + x^2_2 \end{array} & \begin{array}{c} R_{0+}, |x_0| ≤ e_0, x_1 > e_1 \\ C + x_0U_0 + e_1U_1 \\ (x_1 − e_1)^2 + x^2_2 \end{array} & \begin{array}{c} R_{++}, x_0 > e_0, x_1 > e_1 \\ C + e_0U_0 + e_1U_1 \\ (x_0 - e_0)^2 + (x_1 − e_1)^2 + x^2_2 \end{array} \\\hline \begin{array}{c} R_{−0}, x_0 < −e_0, |x_1| ≤ e_1 \\ C − e_0U_0 + x_1U_1 \\ (x_0 + e_0)^2 + x^2_2 \end{array} & \begin{array}{c} R_{00}, |x_0| ≤ e_0, |x_1| ≤ e_1 \\ C + x_0U_0 + x_1U_1 \\ x^2_2 \end{array} & \begin{array}{c} R_{+0}, x_0 > e_0, |x_1| ≤ e_1 \\ C + e_0U_0 + x_1U_1 \\ (x_0 - e_0)^2 + x^2_2 \end{array} \\\hline \begin{array}{c} R_{−-}, x_0 < −e_0, x_1 < -e_1 \\ C − e_0U_0 - e_1U_1 \\ (x_0 + e_0)^2 + (x_1 + e_1)^2 + x^2_2 \end{array} & \begin{array}{c} R_{0-}, |x_0| ≤ e_0, x_1 < -e_1 \\ C + x_0U_0 - e_1U_1 \\ (x_1 + e_1)^2 + x^2_2 \end{array} & \begin{array}{c} R_{+-}, x_0 > e_0, x_1 < -e_1 \\ C + e_0U_0 - e_1U_1 \\ (x_0 - e_0)^2 + (x_1 + e_1)^2 + x^2_2 \end{array} \end{array} $$

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Can you include the code in the body of your answer, just to defend against link rot in case the ShaderToy version ever becomes inaccessible? \$\endgroup\$
    – DMGregory
    Mar 8 at 20:01
2
\$\begingroup\$

You could decompose that test into four separate tests:

For each edge AB, BC, CD, DA in the box ABCD, determine the distance to the ray. The closest of all four tests is your solution.

For the edge vs ray test, you could do segment-vs-segment, and just pretend the ray is a really long segment.

I found this 2D segment vs segment test that you can use for this.

Note that if multiple edges have distance 0 to the ray, you need to compute the actual intersections, and pick the one closest to the ray origin.

\$\endgroup\$
2
  • \$\begingroup\$ That's fine for the test, but in a 3d world you would be best to also do a Dot Test to ensure the face of the box is facing the ray as another test. The other test I would perform might be a Ray/plane test post the dot product test to eliminate parrallel rays. The original question talks about closest then mentions intersection, so i assume the ray has to collide and therefore parallel test is required. \$\endgroup\$
    – ErnieDingo
    May 23, 2019 at 22:43
  • \$\begingroup\$ If I understand it correctly, the method in the link doesn't work. If the segments don't intersect, but the extension of one into a line does intersect the other segment, then it will give the wrong answer. That's because, in this case, the closest distance is between the edge of one line and the middle of the other. The link provided doesn't appear to check for that. \$\endgroup\$ May 24, 2019 at 23:07
0
\$\begingroup\$

First thing to note is that you only need to consider corners. The player will almost always see a corner of the box before an edge. In the rare cases where the alignment is just right, the player will see an edge and a corner at the same time (because every edge obviously contains corners). So it's enough to only consider corners.

The problem can be solved with linear algebra easily in 2-D, the generalisation to 3-D needs a bit more maths but nothing particularly advanced. The basic algorithm is:

1) From the position of the player and the angle of the line, create a linear equation y = m*x + c which defines the line.

2) The minimum distance between a point and a line is given by the length of a line segment perpendicular to the original line which reaches the point. So, from y = m*x + c construct a unit vector u perpendicular to it.

3) For each corner of rectangle p, find the value t such that p + tu lies on y = mx + c.

4) If all the t's are the same sign, it means that you are on the same side of all the corners. The distance to the rectangle is therefore min(abs(t)), and the corner you will see first is the one which gave that t. If some of the t's are positive and some negative, that means that you are clockwise of some corners and anticlockwise of others, and are therefore inside the rectangle.

EDIT: I did the maths on the back of an envelope. The value of \$t\$ is $$ t = \cos(\theta) (p_y-y_0) - \sin(\theta)(p_x-x_0) $$

Where \$(x_0, y_0)\$ is the coordinate of the player, \$\theta\$ is the angle from the horizontal \$+x\$ axis (measured by the direction towards the \$+y\$ axis) and \$(p_x, p_y)\$ is the coordinate of a corner. This is a shockingly simple result, if I was you I would redo the maths just to double check, it's only 6 or 7 lines of algebra.

The extension in 3-D depends on how the viewer works. Is the vision of the player a wedge or a cone?

\$\endgroup\$
2
  • \$\begingroup\$ I think in 3 dimensions you won't only see corners anywhere near as commonly \$\endgroup\$
    – minseong
    May 24, 2019 at 22:49
  • \$\begingroup\$ No, in 3d the player will always see an edge first. But that's a 1-d object compared to a 2-d surface bounding the player's field of view so essentially the same trick works. \$\endgroup\$ May 24, 2019 at 23:23
0
\$\begingroup\$

2D Solution

This is pretty easy if you divide this into two cases: line intersects object, and line doesn't intersect.

For the intersect case, as you've shown it's just a matter of finding the intersection closest to the viewer - something I assume won't be that hard to figure out.

And for the case of no intersection, a bit of illustrated rotation can help show how this can be figured out easily...

First, here is the scenario with your image...

enter image description here

Now rotate it so that your view vector is zero degrees and the viewer is at the origin (0,0)...

enter image description here

Now, all you have to do is find the corner with the smallest absolute value Y coordinate, and that is your intersection point.

There is one edge case (literally) where the view vector is parallel to an edge, and two points are equally close. I'm guessing for your requirements, you would choose the furthest from the viewer. Here's an illustration...

enter image description here

3D Solution

The concept is somewhat similar with 3D as follows...

First, if the line intersects the 3D shape, then choose the point of intersection as your answer.

If the line does not intersect, then you must find the point that is closest to your view line. Since you have stated that you are only solving this for rectangular solids (meaning there are only 12 edge vectors), I would probably just brute force calculate the closest distance from each edge vector to the view vector, and choose the smallest one, and the coordinate of that closest point. Rather than explain it here, I'll point to a Mathematics stack post that discusses finding the shortest distance between lines - https://math.stackexchange.com/questions/2213165/find-shortest-distance-between-lines-in-3d. There are probably other solutions online to be found.

\$\endgroup\$
7
  • \$\begingroup\$ Rotating it is quite computationally expensive (sin and cos) and I don't know how rotating it would "work" in 3 dimensions. \$\endgroup\$
    – minseong
    May 24, 2019 at 18:54
  • \$\begingroup\$ You might want to reword your question to specifically state you're looking for a solution that works in 2D and 3D. \$\endgroup\$
    – Tim Holt
    May 24, 2019 at 19:04
  • 1
    \$\begingroup\$ The last statement in red is not true. The corner furthest away is the one that will be seen first. Just consider the line rotating and you'll see that it hits the furthest corner before the first one. \$\endgroup\$ May 24, 2019 at 22:47
  • \$\begingroup\$ @theonlygusti both these concerns are lessened if you think of it as not a rotation, but a projection onto the subspace perpendicular to the ray. Then it's at most a couple of normalizations to get your basis vector(s), and then a bunch of dot products. You can apply an approximate arctangent if you want the smallest turn instead of the closest linear offset. \$\endgroup\$
    – DMGregory
    May 24, 2019 at 23:21
  • 1
    \$\begingroup\$ @theonlygusti, I want to emphasize that I'm not trying to give you code, or math, or hard exact answers here. I'm trying to give you a way to think about your problem that might lead you to an answer. Real growth as a developer comes from figuring things out sometimes. Keep in mind we don't know if you are an experienced programmer or not, or if you know a lot of math or not. Me? I'm visual. So I give you a visual answer to help you imagine how it could be solved. I will say though that your thinking of cos/sin as computationally intensive is naive - a problem 15-20 years ago, not now. \$\endgroup\$
    – Tim Holt
    May 26, 2019 at 6:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .