Finding Outer Vertices of Shapes

Sage
Posts: 1,066
Joined: 2004.07
Post: #1
I having trouble figuring out a good way to accomplish my goal. I'm trying to be able to cast 2D shadows from objects. I figured that I can just find the "outer" vertices relative to the light source and go from there, but I'm not having much luck. If you're still confused about what I want to do, here's a crude image. The blue blob is the light source. The circled vertices are the vertices I wish to get.

[Image: vertex_finding.png]

I've tried one implementation, but it's not working at all. Can anyone take a look and possibly offer suggestions? Once I get this working on a square, I'm going to add guards against single points and lines being passed as shapes, but for now I'm assuming the Shape is a square.

Code:
class Shape {
public:
vector<vec2i> _points;
};

bool linesCollide( vec2i a, vec2i b, vec2i c, vec2i d ) {
    float Ua = ( ( ( d.x - c.x ) * ( a.y - c.y ) - ( d.y - c.y ) * ( a.x - c.x ) ) /
                 ( ( d.y - c.y ) * ( b.x - a.x ) - ( d.x - c.x ) * ( b.y - a.y ) ) );
    float Ub = ( ( ( b.x - a.x ) * ( a.y - c.y ) - ( b.y - a.y ) * ( a.x - c.x ) ) /
                 ( ( d.y - c.y ) * ( b.x - a.x ) - ( d.x - c.x ) * ( b.y - a.y ) ) );
    
    return ( ( 0.0f <= Ua && 1.0f >= Ua ) && ( 0.0f <= Ub && 1.0f >= Ub ) );
}

void findPoint1( Shape s ) {
    vector<vec2i>::iterator itr = s._points.begin(), end = s._points.end(), itr2 = itr, itr3 = itr;
    
    while( itr != end ) {
        itr2 = itr + 1;
        itr3 = itr - 1;
        if( itr == s._points.begin() )
            itr3 = s._points.end() - 1;
        if( itr == s._points.end() - 1 )
            itr2 = s._points.begin();
        
        if( !linesCollide( mousePosition, ( *itr ), ( *itr ), ( *itr2 ) ) &&
            !linesCollide( mousePosition, ( *itr ), ( *itr3 ), ( *itr ) ) ) {
            point1 = ( *itr );
            break;
        }
        
        ++itr;
    }
}

void findPoint2( Shape s ) {
    vector<vec2i>::reverse_iterator itr = s._points.rbegin(), end = s._points.rend(), itr2 = itr, itr3 = itr;
    
    while( itr != end ) {
        itr2 = itr + 1;
        itr3 = itr - 1;
        if( itr == s._points.rbegin() )
            itr3 = s._points.rend() - 1;
        if( itr == s._points.rend() - 1 )
            itr2 = s._points.rbegin();
        
        if( !linesCollide( mousePosition, ( *itr ), ( *itr ), ( *itr2 ) ) &&
            !linesCollide( mousePosition, ( *itr ), ( *itr3 ), ( *itr ) ) ) {
            point2 = ( *itr );
            break;
        }
        
        ++itr;
    }
}
Quote this message in a reply
Sage
Posts: 1,403
Joined: 2005.07
Post: #2
dot product backface cull from the light source,

so all the faces that are lit by the light, mark red, all the other mark blue.

now you can find all the edges that are shared by a red and a blue triangle, thats the outline.

Sir, e^iπ + 1 = 0, hence God exists; reply!
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #3
Thanks.

I gave it a try and it sort-of-almost works. I can't explain it that well, so I uploaded the app for you to see. Get it here.

Here's the new code that I'm using:

Code:
bool facingMouse( vec2i p, vec2i p2 ) {
    vec2i side = p - p2;
    vec2i mouse = p - mousePosition;
    
    return ( Vector2D<int>::DotProduct( side, mouse ) < 0.0f );
}

void findPoint1( Shape s ) {
    vec2i a, b;
    
    for( int i = 0; i < s._points.size(); i++ ) {
        a = s._points.at( i );
        
        if( i == s._points.size() - 1 )
            b = s._points.at( 0 );
        else
            b = s._points.at( i + 1 );
        
        if( facingMouse( a, b ) ) {
            point1 = a;
            break;
        }
    }
}

void findPoint2( Shape s ) {
    vec2i a, b;
    
    for( int i = s._points.size() - 1; i >= 0; i-- ) {
        a = s._points.at( i );
        
        if( i == 0 )
            b = s._points.at( s._points.size() - 1 );
        else
            b = s._points.at( i - 1 );
        
        if( facingMouse( a, b ) ) {
            point2 = a;
            break;
        }
    }
}
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #4
Got it. Forgot to make sure that the other edge the point is connected to is the opposite facing as the point. Here's the code that actually works:

Code:
bool facingMouse( vec2i p, vec2i p2 ) {
    vec2i side = p - p2;
    vec2i mouse = p - mousePosition;
    
    return ( Vector2D<int>::DotProduct( side, mouse ) < 0 );
}

void findPoint1( Shape s ) {
    vec2i a, b, c;
    
    for( int i = 0; i < s._points.size(); i++ ) {
        a = s._points.at( i );
        
        if( i == 0 )
            b = s._points.at( s._points.size() - 1 );
        else
            b = s._points.at( i - 1 );
        
        if( i == s._points.size() - 1 )
            c = s._points.at( 0 );
        else
            c = s._points.at( i + 1 );
        
        if( ( facingMouse( a, b ) && !facingMouse( a, c ) ) ||
            ( facingMouse( a, c ) && !facingMouse( a, b ) ) ) {
            point1 = a;
            break;
        }
    }
}

void findPoint2( Shape s ) {
    vec2i a, b, c;
    
    for( int i = s._points.size() - 1; i >= 0; i-- ) {
        a = s._points.at( i );
        
        if( i == 0 )
            b = s._points.at( s._points.size() - 1 );
        else
            b = s._points.at( i - 1 );
        
        if( i == s._points.size() - 1 )
            c = s._points.at( 0 );
        else
            c = s._points.at( i + 1 );
        
        if( ( facingMouse( a, b ) && !facingMouse( a, c ) ) ||
            ( facingMouse( a, c ) && !facingMouse( a, b ) ) ) {
            point2 = a;
            break;
        }
    }
}
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #5
I've reached a strange problem, when I try to use a triangle with my method, it locks up into an infinte loop. Any ideas?

Code:
bool facingMouse( vec2f p, vec2f p2 ) {
    vec2f side = p - p2;
    vec2f mouse = p - mousePosition;
    
    return ( Vector2D<float>::DotProduct( side, mouse ) < 0 );
}

bool findPoints( Shape s, vec2f &p1, vec2f &p2 ) {
    vec2f a, b, c;
    bool started = false, finished = false;
    
    while( !finished ) {
        for( int i = 0; i < s._points.size(); i++ ) {
            a = s._points.at( i );
            
            if( i == 0 )
                b = s._points.at( s._points.size() - 1 );
            else
                b = s._points.at( i - 1 );
            
            if( i == s._points.size() - 1 )
                c = s._points.at( 0 );
            else
                c = s._points.at( i + 1 );
            
            if( facingMouse( a, b ) && !facingMouse( a, c ) && !started ) {
                p1 = a;
                started = true;
            }
            else if( facingMouse( a, c ) && !facingMouse( a, b ) && started) {
                p2 = a;
                finished = true;
                break;
            }
        }
        
        if( !started )
            return false;
    }
    
    return true;
}

void renderShadow( Shape s ) {
    vec2f p1, p2;
    vec2f a, scaledA;
    
    if( !findPoints( s, p1, p2 ) )
        return;
    
    bool started = false, finished = false;
    
    glBegin( GL_TRIANGLE_STRIP );
    
    while( !finished ) {
        for( int i = 0; i < s._points.size(); i++ ) {
            a = s._points.at( i );
            
            if( !started && a == p2 )
                started = true;
            else if( started && a == p1 )
                finished = true;
            
            if( started ) {
                scaledA = ( ( a - mousePosition ).normalize() ) * SHADOW_SCALE + a;
                
                glVertex3f( a.x, a.y, 1.0f );
                glVertex3f( scaledA.x, scaledA.y, 1.0f );
            }
            
            if( finished )
                break;
        }
    }
    
    glEnd();
}
Quote this message in a reply
Member
Posts: 161
Joined: 2005.07
Post: #6
Here's pseudocode for how I'd do it:
Code:
// construct a vector from the light source to the origin
// of your object and normalize the vector
Vector w = ((object origin) - (light source origin)).normalize()

// use the dot product on that vector and a (0, -1, 0) vector to get the cosine of the angle between the two vectors
Vector temp = (0, -1, 0)
float theta = -acos(temp.dot(w))
float cos_theta = cos(theta)
float sin_theta = sin(theta)

float min = 1000000, max = -1000000

// rotate each vertex by the angle given, then find the leftmost and rightmost vertices in the object
for (each vertex in the object)
float temp_x = cos_theta * vertex[m].x - sin_theta * vertex[m].y
if (temp_x < min)
  min = temp_x
  p1 = vertex[m]
else if (temp_x > max)
  max = temp_x
  p2 = vertex[m]
end if
end loop

In your example, the system would be rotated so that it looks like this:
[Image: temp_img.png]
(O is the object's origin, L is the light source's origin, and p1 and p2 are the two vertices you are solving for)

Kind of easy to find p1 and p2 now, isn't it? It's just the leftmost and rightmost vertices. Since only the x values for the vertices are needed to solve for p1 and p2, only the x value is calculated in the pseudocode's loop.
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #7
imikedaman Wrote:Kind of easy to find p1 and p2 now, isn't it? It's just the leftmost and rightmost vertices. Since only the x values for the vertices are needed to solve for p1 and p2, only the x value is calculated in the pseudocode's loop.

Hm. Seems very nice. I gave it a try, but I get some awkward shadows that overlap themselves (wrong points I guess) and it doesn't seem to get the right points at certain angles. Here's my code for implementing this:

Code:
bool findPoints( const Shape &s, vec2f &p1, vec2f &p2 ) {
    vec2f w = ( s._origin - mousePosition ).normalize();
    vec2f temp( 0, -1 );
    float theta = -acos( vec2f::DotProduct( temp, w ) );
    float cosTheta = cos( theta );
    float sinTheta = sin( theta );
    
    float min = 10000000, max = -10000000;
    p1 = s._points[ i ];
    p2 = s._points[ i ];
    
    for( int i = 0; i < s._points.size(); i++ ) {
        float x = cosTheta * s._points[ i ].x - sinTheta * s._points[ i ].y;
        if( x < min ) {
            p1 = s._points[ i ];
            min = x;
        }
        else if( x > max ) {
            p2 = s._points[ i ];
            max = x;
        }
    }
    
    if( p1 == p2 )
        return false;
    
    return true;
}

Edit: Upon furthur thought, this method doesn't seem to hold up when using rectangles (or other shapes) when the light is close to the shape. That explains my incorrect points.
Quote this message in a reply
Member
Posts: 161
Joined: 2005.07
Post: #8
Yeah, I just realized the method wouldn't work in this scenario:
[Image: temp_img_2.png]
The concept of rotating the system to make hard problems easier works in a lot of cases, but in this case I don't think it did.

Actually, come to think of it, try modifying your loop so that it does this:
Code:
// construct a vector from the light source to the origin
// of your object and normalize the vector
Vector w = ((object origin) - (light source origin)).normalize()

// use the dot product on that vector and a (0, -1, 0) vector to get the cosine of the angle between the two vectors
Vector temp = (0, -1, 0)
float theta = acos(temp.dot(w)) // changed this to a positive acos since I think that's the correct sign for it
float cos_theta = cos(theta)
float sin_theta = sin(theta)

float p1_min = 1000000, p2_min = 1000000

// rotate each vertex by the angle given, then find the leftmost and rightmost vertices in the object
for (each vertex in the object)
float temp_x = cos_theta * vertex[m].x - sin_theta * vertex[m].y
Vector light_to_vert = (vertex[m] - (light origin)).normalize()
float dot_product = light_to_vert.dot(temp) // temp is the (0, -1, 0) vec from before

if (temp_x <= 0) // left of the Y axis
  if (temp_x < p1_min)
    p1_min = temp_x
    p1 = vertex[m]
  end if
else if (temp_x > 0) // right of the Y axis
  if (temp_x < p2_min) // smaller dot product value = larger angle
    p2_min = temp_x
    p2 = vertex[m]
  end if
end if
end loop
You'll probably have to tweak the code to make it work, but that's the general idea. In this one, I rotate the system to the graphic in the previous post I made, then find the smallest dot product between the (vector from the light source to the origin) and the (vector from the light source to the vertex).
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #9
I think I figured out what you were going for, but this still doesn't work right. I still get improper points. Here's my loop code:

Code:
bool findPoints( const Shape &s, vec2f &p1, vec2f &p2 ) {
    
    vec2f w = ( s._origin - mousePosition ).normalize();
    vec2f temp( 0, -1 );
    float theta = acos( vec2f::DotProduct( temp, w ) );
    float cosTheta = cos( theta );
    float sinTheta = sin( theta );
    
    float p1_min = 1000000, p2_min = 1000000;
    p1 = p2 = s._points[ 0 ];
    
    for( int i = 0; i < s._points.size(); i++ ) {
        float x = cosTheta * s._points[ i ].x - sinTheta * s._points[ i ].y;
        vec2f lightToVert = ( s._points[ i ] - mousePosition ).normalize();
        float dp = vec2f::DotProduct( lightToVert, temp );
        
        if( x < 0 ) {
            if( dp < p1_min ) {
                p1_min = dp;
                p1 = s._points[ i ];
            }
        }
        else {
            if( dp < p2_min ) {
                p2_min = dp;
                p2 = s._points[ i ];
            }
        }
    }
    
    if( p1 == p2 )
        return false;
    
    return true;
}

And you can download and view the app from here.
Quote this message in a reply
Member
Posts: 161
Joined: 2005.07
Post: #10
Yeah, I just recognized quite a few bugs in my original pseudocode. I'm actually writing a quick demo program now to iron out the glitches. I found two bugs so far...

EDIT: Aha, fixed it.
Code:
// construct a vector from the light source to the origin of your object and normalize the vector
  w = ((object origin) - (light origin)).normalize()
  
  // use the dot product on that vector and a (0, -1) vector to get the cosine of the angle between the two vectors
  Vector temp = (0, -1)
  
  float theta = acos(temp.dot(w))
  if (w.x > 0) theta = -theta // added this
  float cos_theta = cos(theta)
  float sin_theta = sin(theta)
  
  float p1_min = 1000000
  float p2_min = 1000000
  float light_pos_x = cos_theta * light_pos.x - sin_theta * light_pos.y // added this
  
  // rotate each vertex by the angle given, then find the leftmost and rightmost vertices in the object
  for (each vertex in the object using m)
    float temp_x = cos_theta * vertices[m].x - sin_theta * vertices[m].y
    Vector light_to_vert = (vertices[m] - (light position)).normalize()
    float dot_product = w.dot(light_to_vert)
    
    // fixed this code here
    if (temp_x <= light_pos_x) then // changed this from <= 0 to <= light_pos_x
      if (dot_product < p1_min) then
        p1_min = dot_product
        p1 = vertices[m]
      end if
    else
      if (dot_product < p2_min) then
        p2_min = dot_product
        p2 = vertices[m]
      end if
    end if
  next
That should work great. Good luck!

EDIT 2: It doesn't seem to work with certain nonconvex objects (although it does with with a lot of them). Is that important at all? I ask because your demo has only convex objects.
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #11
imikedaman Wrote:Yeah, I just recognized quite a few bugs in my original pseudocode. I'm actually writing a quick demo program now to iron out the glitches. I found two bugs so far...

EDIT: Aha, fixed it.

EDIT 2: It doesn't seem to work with certain nonconvex objects (although it does with with a lot of them). Is that important at all? I ask because your demo has only convex objects.

I must be doing it wrong or something. Doesn't work correctly about 80% of the time.

Code:
bool findPoints( const Shape &s, vec2f &p1, vec2f &p2 ) {
    
    vec2f w = ( s._origin - mousePosition ).normalize();
    vec2f temp( 0, -1 );
    float theta = acos( vec2f::DotProduct( temp, w ) );
    if( w.x > 0 )
        theta = -theta;
    
    float cosTheta = cos( theta );
    float sinTheta = sin( theta );
    
    float p1_min = 1000000, p2_min = 1000000;
    p1 = p2 = s._points[ 0 ];
    
    for( int i = 0; i < s._points.size(); i++ ) {
        float x = cosTheta * s._points[ i ].x - sinTheta * s._points[ i ].y;
        vec2f lightToVert = ( s._points[ i ] - mousePosition ).normalize();
        float dp = vec2f::DotProduct( w, lightToVert );
        
        if( x <= 0 ) {
            if( dp < p1_min ) {
                p1_min = dp;
                p1 = s._points[ i ];
            }
        }
        else {
            if( dp < p2_min ) {
                p2_min = dp;
                p2 = s._points[ i ];
            }
        }
    }
    
    if( p1 == p2 )
        return false;
    
    return true;
}

Here's my other code that works on all rectangular objects but for some reason doesn't work on anything not made entirely of 90 degree angles.

Code:
bool facingMouse( vec2f p, vec2f p2 ) {
    vec2f side = p - p2;
    vec2f mouse = p - mousePosition;
    
    return ( vec2f::DotProduct( side.normalize(), mouse.normalize() ) < 0.0f );
}

bool findPoints( const Shape &s, vec2f &p1, vec2f &p2 ) {
    vec2f a, b, c;
    bool started = false, finished = false;
    
    while( !finished ) {
        for( int i = 0; i < s._points.size(); i++ ) {
            a = s._points.at( i );
            
            if( i == 0 )
                b = s._points.at( s._points.size() - 1 );
            else
                b = s._points.at( i - 1 );
            
            if( i == s._points.size() - 1 )
                c = s._points.at( 0 );
            else
                c = s._points.at( i + 1 );
            
            if( facingMouse( a, b ) && !facingMouse( a, c ) && !started ) {
                p1 = a;
                started = true;
            }
            else if( facingMouse( a, c ) && !facingMouse( a, b ) && started) {
                p2 = a;
                finished = true;
                break;
            }
        }
        
        if( !started )
            return false;
    }
    
    return true;
}
Quote this message in a reply
Member
Posts: 161
Joined: 2005.07
Post: #12
Hm, it could be that my code uses a different coordinate system. I prototyped the code in REALbasic, which has (0, 0) as the top-left corner of the window. Could that be a problem?

I tried the code on a bunch of different shapes and rotations before posting it online, so that's my best guess right now. Hm....
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #13
imikedaman Wrote:Hm, it could be that my code uses a different coordinate system. I prototyped the code in REALbasic, which has (0, 0) as the top-left corner of the window. Could that be a problem?

I tried the code on a bunch of different shapes and rotations before posting it online, so that's my best guess right now. Hm....

No, I'm using OpenGL, but I have it set to an orthographic view with (0,0) as my top-left corner as well. I'm not sure what else it could be.
Quote this message in a reply
Member
Posts: 161
Joined: 2005.07
Post: #14
What's an example object that doesn't work right? I mean the list of (x, y) coordinates so I can test to see if it's a glitch with the code or the conversion.

EDIT: Oh never mind, your code is different than the code I posted. You're missing the light_pos_x variable - both the creation of the float, and using it in the loop.
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #15
I see. Even with it, though, it doesn't seem to work. Here's my code:

Code:
bool findPoints( const Shape &s, vec2f &p1, vec2f &p2 ) {
    
    vec2f w = ( s._origin - mousePosition ).normalize();
    vec2f temp( 0, -1 );
    float theta = acos( vec2f::DotProduct( temp, w ) );
    if( w.x > 0 )
        theta = -theta;
    
    float cosTheta = cos( theta );
    float sinTheta = sin( theta );
    
    float p1_min = 1000000, p2_min = 1000000;
    p1 = p2 = s._points[ 0 ];
    float lightPosX = cosTheta * mousePosition.x - sinTheta * mousePosition.y;
    
    for( int i = 0; i < s._points.size(); i++ ) {
        float x = cosTheta * s._points[ i ].x - sinTheta * s._points[ i ].y;
        vec2f lightToVert = ( s._points[ i ] - mousePosition ).normalize();
        float dp = vec2f::DotProduct( w, lightToVert );
        
        if( x <= lightPosX ) {
            if( dp < p1_min ) {
                p1_min = dp;
                p1 = s._points[ i ];
            }
        }
        else {
            if( dp < p2_min ) {
                p2_min = dp;
                p2 = s._points[ i ];
            }
        }
    }
    
    if( p1 == p2 )
        return false;
    
    return true;
}

And here's the code for my shapes (shows the vertices):
Code:
Shape shape;
    shape._points.push_back( vec2f( 150, 150 ) );
    shape._points.push_back( vec2f( 150, 250 ) );
    shape._points.push_back( vec2f( 200, 250 ) );
    shape._points.push_back( vec2f( 200, 150 ) );
    shape.computeOrigin();
    shapes.push_back( shape );
    
    shape = Shape();
    shape._points.push_back( vec2f( 450, 150 ) );
    shape._points.push_back( vec2f( 450, 250 ) );
    shape._points.push_back( vec2f( 500, 250 ) );
    shape._points.push_back( vec2f( 500, 150 ) );
    shape.computeOrigin();
    shapes.push_back( shape );
    
    shape = Shape();
    shape._points.push_back( vec2f( 200, 400 ) );
    shape._points.push_back( vec2f( 200, 450 ) );
    shape._points.push_back( vec2f( 250, 500 ) );
    shape.computeOrigin();
    shapes.push_back( shape );
    
    shape = Shape();
    shape._points.push_back( vec2f( 400, 400 ) );
    shape._points.push_back( vec2f( 400, 450 ) );
    shape._points.push_back( vec2f( 450, 500 ) );
    shape._points.push_back( vec2f( 500, 450 ) );
    shape._points.push_back( vec2f( 500, 400 ) );
    shape.computeOrigin();
    shapes.push_back( shape );

The first two are rectangles which work fine with my original code (not your method). The third is a triangle which doesn't work with mine and the last is a pentagon that doesn't work with mine. With your method, none of them are computed correctly.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  finding a training center - Heeeelp Glauter 1 3,058 Dec 26, 2011 12:30 PM
Last Post: zenkimoto
  Adding lots of static shapes in Chipmunk - performance question TomorrowPlusX 3 7,555 Jul 11, 2011 01:39 PM
Last Post: Skorche
  Finding an object by name markhula 2 4,656 Mar 29, 2011 08:08 AM
Last Post: markhula
  Game rectangles & OpenGL vertices mk12 2 2,829 Sep 7, 2010 07:45 PM
Last Post: mk12
  Kind of a noob question - finding artwork within my .app?? Nethfel 2 2,903 Mar 8, 2010 08:00 AM
Last Post: AndyKorth