Finding Outer Vertices of Shapes

Member
Posts: 161
Joined: 2005.07
Post: #16
Quote:With your method, none of them are computed correctly.
I just inputted all your examples and the shadows were fine for all of them.

One thing that I'm wondering about though... in your code, you use s._points.at(i) to get the point at index i, but in mine, you use s._points[i] for some reason. Does that matter?
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #17
at() is range-checked; [] is not. That's the only difference, I think.
Quote this message in a reply
Member
Posts: 26
Joined: 2006.09
Post: #18
The dot product method is the fastest and easiest to do. I think the bug in your code is that you are taking the dot product between the edge direction and direction to one of the vertices. You should use the edge normal instead. The normal is (-y, x) or (y, -x) depending on how you choose to use it Smile. Also not need to normalize if you are just test if the edge is backfacing or not.

Code:
size_t    n = m_verts.size();
for(size_t i = 0; i < n; ++i)
{
    size_t j = (i+1) % n;
    Vec2i    edge(m_verts[j].x - m_verts[i].x, m_verts[j].y - m_verts[i].y);
    Vec2i    norm(-edge.y, edge.x);
    Vec2i    dir(m_verts[i].x - m_x, m_verts[i].y - m_y);
    if(Dot(norm, dir) > 0)
    {
        // font facing
        dc.MoveTo(m_verts[i].x, m_verts[i].y);
        dc.LineTo(m_verts[j].x, m_verts[j].y);
    }
}

Also note that this method requires you to always have same winding of the polygons otherwise the dot product test will fail. The easiest way to check the polygon winding is to calculate the area and if it is negative, reverse you array of points.
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #19
Thanks memon! That worked perfectly. I realized yesterday I was using the edge instead of the edge normal, but when I switched it even my rectangles didn't work right. Your code works perfectly for all my shapes so far. Thanks.
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,052 Dec 26, 2011 12:30 PM
Last Post: zenkimoto
  Adding lots of static shapes in Chipmunk - performance question TomorrowPlusX 3 7,549 Jul 11, 2011 01:39 PM
Last Post: Skorche
  Finding an object by name markhula 2 4,650 Mar 29, 2011 08:08 AM
Last Post: markhula
  Game rectangles & OpenGL vertices mk12 2 2,824 Sep 7, 2010 07:45 PM
Last Post: mk12
  Kind of a noob question - finding artwork within my .app?? Nethfel 2 2,901 Mar 8, 2010 08:00 AM
Last Post: AndyKorth