• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
CGameProgrammer

Vectorizing a 1-bit raster image of polygon(s)

14 posts in this topic

I have a one-bit image (each pixel is either black or white) of a polygon or polygons - the edges of the image are always black. I would like to convert this to a set of one or more polygon vectors, where each vector is simply an ordered list of points (one list per polygon) describing the corners or approximating curves.

 

Attached is an example input image with red dots overlayed to show what the output points should be. It should be two lists of points of course. The threshold for placing points around a curve is arbitrary and not important.

 

The input polygons will never have holes.

 

Speed is irrelevant; this is not being done at realtime and is just precomputed.

 

The actual scenario, if you're wondering, is that I have airspace regions defined as simple polygonal regions (one list of coordinates per polygon) which are either unioned or subtracted. The sample image illustrates an example of this (not actual airspace, just a simple test). I started with a hexagon, then subtracted from it a quadrilateral (which splits the hexagon in two), then I added (unioned) a circle. Trying to directly generate vector polygons from these input polygon vectors would be maddening; I figure it's simpler to render them as raster polygons temporarily (additive is drawn in white, subtractive in black) and then convert that.

 

Step one, edge detection, becomes trivial obviously; it's any white pixel adjacent to a black pixel.

 

Step two is to create huge unsimplified ordered lists of edge points. My plan is to create a bucket of all edge pixels, then (sloppy pseudocode):

point = bucket.pop()
 
isDone = false
 
while !isDone
{
    isDone = true
 
    for all edge pixels in bucket
    {
        if this edge pixel is adjacent to point
        {
            append edge pixel to polygon points
            point = edge pixel
            isDone = false
            break;
        }
    }
}

Then if there is anything remaining in the bucket, repeat the process for the next new polygon.

 

The third and final step, and one that I definitely can't seem to figure out, is to simplify these lists of every edge into just the ones that mark the corners (or that approximate to some threshold the curves).

 

Can anyone help?

Edited by CGameProgrammer
0

Share this post


Link to post
Share on other sites

Trying to directly generate vector polygons from these would be maddening; I figure it's simpler to render them as raster polygons temporarily (additive is drawn in white, subtractive in black) and then convert that.

 

I disagree, this should be simpler, though it depends on what you want to use it for. What is the purpose of having a representation as a concave polygon?

 

If you need to check intersections or similar with the resulting shapes, then I would not precompute a final polygon shapes at all, but rather use the original simple polygons, including subtractions. This is not terribly difficult for boolean operations on constructive solid geometry (CSG). For example checking if a point is inside a tree of polygons combined through boolean operations can be easily reduced to checking only if a point is inside the simple sub-polygons and then inverting the answer depending on subtraction. You can even do subtractions of subtractions with ease, for example subtracting a rectangle from a circle, then subtracting the resulting shape from another circle, etc.

 

If you wish to go backwards from rasterization, I would probably use a flood-fill algorithm to find each complete white shape and then trace the edge of each such shape. Go through every pixel until you find a white one, flood-fill around it to find every white pixel that is connected to that pixel, and you have one shape. Then trace around it. Then remove all points that are exactly on a straight line between two other points to reduce the number of edge-points to corners.

EDIT: Actually there are easier ways, but I'll await your reply.

Edited by Erik Rufelt
0

Share this post


Link to post
Share on other sites

I know it's very easy to test if something is within the original simple polygons; my problem is rendering them. There is no way to directly render the original polygons that would look correct. Now it is trivial to render the raster polygons with a border; I'd just draw a circle (diameter = border thickness) at each edge pixel. The problem with that is of course it'll look blurry when stretched and pixellated when shrunk. I'd be rendering them on a map so the user would zoom a lot.

 

Also since we're dealing with pixels, they are not on a straight line due to interpolation. For example:

X
 XX
   X
    XX
Edited by CGameProgrammer
0

Share this post


Link to post
Share on other sites

I see. I would do CSG of the polygons. Triangulate each simple polygon for rendering, then for the subtractions you can reduce the problem to triangle/triangle subtraction, which is rather simple, especially when you don't care too much about limiting the number of triangles, and you get rid of any interpolation problems.

0

Share this post


Link to post
Share on other sites
No, that would not work because I am not rendering a triangular mesh; the output must be the list of points that define the polygon's border.
0

Share this post


Link to post
Share on other sites

Explain how the final render should look and I'm sure there is a relatively straight-forward way to accomplish it.

0

Share this post


Link to post
Share on other sites
I appreciate you trying to help but you keep suggesting inappropriate alternatives instead of the solution to the question I asked. In this case the polygon is added to Google Maps as a list of coordinates so it can be properly vector-drawn; adding it as a raster image would look much worse as I mentioned in the original post.

If it wasn't obvious, and maybe it wasn't, the answer I really need is the solution to step #3 in the original post: reducing an ordered list of points along the edges to just the corners (except for curves).
0

Share this post


Link to post
Share on other sites

I appreciate you trying to help but you keep suggesting inappropriate alternatives instead of the solution to the question I asked. In this case the polygon is added to Google Maps as a list of coordinates so it can be properly vector-drawn; adding it as a raster image would look much worse as I mentioned in the original post.

If it wasn't obvious, and maybe it wasn't, the answer I really need is the solution to step #3 in the original post: reducing an ordered list of points along the edges to just the corners (except for curves).

 

I assure you that skipping rasterization is not an inappropriate solution. But obviously there is more than one way to do things, and apologies if I misunderstood anything and good luck :)

0

Share this post


Link to post
Share on other sites

Your idea may have some merit Krypt0n. I'm not positive that calculating length is the right way to determine error; I worry it may either cut vital corners if it's too aggressive or fail to remove enough points on curves if it's not aggressive enough. Or both. But I can try it and see.

Edited by CGameProgrammer
0

Share this post


Link to post
Share on other sites

imagine two lines meeting at a vital corner. those lines have a lot of point in "RemovedVertices", even slight changes in direction accumulate to a big error. removing a vital corner -> very big error. on the other side, removing vertices on the path between two vital corners won't affect the minimal distance between every removed vertex and the line.

 

that was of course just the simpelst of the ways to calculate the error. you can improve the error metric without changing the algorithm to improve the situation in various ways.

1. you can calculate 'normals' per vertex by averaging the normals of the two lines connected to it. once you start removing vectors, you do a dot between the normals of the removed vertices and the normal of the line that substitutes those. a vector line that follows a pixel line will have a similar normal as long as you remove vertices within two vital corners. but if you remove a vital corner, you'll change the line normal and even if you do that slightly, accumulated across the whole lines the error will be big.

2. you can weight vertex error by the distance to the vertices of your original shapes (that you've used to draw those.

3. you can try to detect 'vital' edges by calculating the 'hardness' between two neighboring vertex normals. basically, if the angle is beyond a specific treshold, you define that edge as 'vital' and never remove it.

4. more complex error metric would be to draw the reduced shape again. removing some vertices that aren't important will result in a very similar shape, removing 'vital' points will lead to a different bitmap (of course, that's time consuming, but might be ok for an offline process).

 

 

 

alternative: while drawing the original shape, you could first draw the vertices as bigger dots. (different color). then the shapes. all original and important vertices will be surrounded by the dot-colors. so it would be easy to detect those. all vertices within the shape will be overdrawn.

0

Share this post


Link to post
Share on other sites

Actually I was thinking more about your original idea and I think it would be the solution after all. I was thinking that vertices would be eliminated if the length error of their absence is within a certain margin, but the actual solution (and what I believe you were trying to say) is to only remove the single least useful vertex after evaluating all of them, and then repeat, until the error from removing any remaining vertex is above the threshold. As the least useful vertices are removed, the error from removing the remaining ones becomes much larger and so they would not be erroneously removed.

 

Last night I wrote the code to complete step #2 (creating the ordered lists of points for each polygon) so today I will write the simplification algorithm and let you know how it goes.

0

Share this post


Link to post
Share on other sites

Update: I had implemented the length-based solution but found that it did not work perfectly; it seemed to eliminate curve definition too much or it allowed unnecessary pixels to remain. I came up with a different technique: for each pixel, I find the longest chain of pixels following it that are near the line drawn from the first pixel to the last of the chain. Then I remove all the pixels between the start and end. This nicely handles all sloped lines and can precisely determine the corner pixels.

 

I'll post code and sample images later. The code is really sloppy right now but I'll try to clean it up a bit first.

0

Share this post


Link to post
Share on other sites

HI there
I have encountered the similar questions with you.I tried to set the raster
image of polygon using this method:

public static PolygonAnnotation CreatePolygonAnnotation(LinePoint[] points);
public static PolygonAnnotation CreatePolygonAnnotation(LinePoint[] points, AnnotationPen outline, AnnotationBrush fill);
public static PolygonAnnotation CreatePolygonAnnotation(LinePoint[] points, AnnotationPen outline, AnnotationBrush fill,
AnnotationBrush shadow);
public static PolygonAnnotation CreatePolygonAnnotation(LinePoint[] points, AnnotationPen outline, AnnotationBrush fill,
AnnotationBrush shadow, float shadowX, float shadowY);
But it can not work.I want to know that if there is a powerful image toolkit which supports to process raster image of polygon directly.Thanks for any suggestions.

0

Share this post


Link to post
Share on other sites

I'm too lazy right now to make the code neatly arranged so attached is the quick'n'dirty code. It's a C# console application that reads an image, figures out the required points, and outputs an image showing them. It also outputs intermediate images showing the steps taken to get to that point. I've also attached one of these sample output images.

 

EDIT: Apparently it doesn't let me attach source code files. Well here is the entire file:

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Imaging;

namespace Vector
{
    struct Point
    {
        public static readonly Point Zero = new Point(0,0);

        public double X;
        public double Y;

        public Point (double x, double y)
        {
            X = x;
            Y = y;
        }

        public override string ToString ()
        {
            return "{" + X + "," + Y + "}";
        }
    }

    class Polygon
    {
        public List<Point> Points;

        public Polygon ()
        {
            Points = new List<Point>();
        }
    }

    class Path
    {
        public List<Point> Points;
        public bool[,] EdgeMap;

        public Path (bool[,] edgeMap, IEnumerable<Point> points)
        {
            EdgeMap = (bool[,])edgeMap.Clone();

            Points = new List<Point>();
            Points.AddRange(points);
        }
    }

    class Program
    {
        static readonly double EDGE_OFFSET_THRESHOLD = 1;
        static readonly string INPUT_PATH = @"A:\Data\shape.png";

        static void Main (string[] args)
        {
            Bitmap bmp = (Bitmap) Image.FromFile(INPUT_PATH);
            bool[,] edgeMap;
            int edgeCount;

            FindEdges(bmp, out edgeMap, out edgeCount);

            Bitmap output = new Bitmap(bmp.Width, bmp.Height);

            for (int y = 0; y < bmp.Height; y++)
                for (int x = 0; x < bmp.Width; x++)
                {
                    if (edgeMap[x,y])
                        output.SetPixel(x, y, Color.White);
                    else
                        output.SetPixel(x, y, Color.Black);
                }

            output.Save(INPUT_PATH + ".edges.png", ImageFormat.Png);

            // Now find the polygons:

            List<Polygon> polygons = new List<Polygon>();

            while (edgeCount > 0)
            {
                // Remove any point to start a new polygon
                Point point = FindRandomEdge(edgeMap);
                edgeMap[(int) point.X, (int) point.Y] = false;

                // Create the first path
                Path path = new Path(edgeMap, new Point[0]);
                path.Points.Add(point);
                List<Path> paths = new List<Path>();
                paths.Add(path);

                EvaluatePath(path, paths);

                // Now look through the list of paths to find the one(s) with the
                // most points. There may be two with the same number of points;
                // just choose the first one arbitrarily in that case.

                Path bestPath = null;
                int bestCount = 0;

                foreach (Path option in paths)
                {
                    Point first = option.Points[0];
                    Point last = option.Points[option.Points.Count-1];

                    // Look for the path that has all the points and that
                    // correctly forms a closed polygon.

                    if (first.X >= last.X-1 &&
                        first.X <= last.X+1 &&
                        first.Y >= last.Y-1 &&
                        first.Y <= last.Y+1 &&
                        option.Points.Count > bestCount)
                    {
                        bestCount = option.Points.Count;
                        bestPath = option;
                    }
                }

                edgeCount -= bestCount;

                // Create the new polygon
                Polygon polygon = new Polygon();
                polygon.Points.AddRange(bestPath.Points);
                polygons.Add(polygon);

                edgeMap = bestPath.EdgeMap;
            }

            output = new Bitmap(bmp.Width, bmp.Height);

            for (int y = 0; y < bmp.Height; y++)
                for (int x = 0; x < bmp.Width; x++)
                    output.SetPixel(x, y, Color.Black);

            for (int n = 0; n < polygons.Count; n++)
            {
                for (int p = 0; p < polygons[n].Points.Count; p++)
                    output.SetPixel((int) polygons[n].Points[p].X, (int) polygons[n].Points[p].Y, GetPolygonColor(n));
            }

            output.Save(INPUT_PATH + ".polygons.png", ImageFormat.Png);

            // Now we need to remove useless edge pixels until we only have the corners remaining.

            foreach (Polygon polygon in polygons)
            {
                int p = 0;
                while (p < polygon.Points.Count)
                {
                    Point start = polygon.Points[p];
                    int removeCount = 0;

                    for (int n = 2; n < polygon.Points.Count; n++)
                    {
                        int endIndex = (p+n) % polygon.Points.Count;
                        Point end = polygon.Points[endIndex];
                        bool removeToEnd = true;

                        // Now see if all pixels between start and end are within the allowed distance
                        // from the line from start to end. If so then keep going. Otherwise we are done
                        // and can eliminate any pixels between start and end.

                        for (int m = 1; m < n; m++)
                        {
                            int middleIndex = (p+m) % polygon.Points.Count;
                            Point middle = polygon.Points[middleIndex];
                            double distance = GetPointSegmentDistance(middle, start, end);
                            if (distance > EDGE_OFFSET_THRESHOLD)
                            {
                                // We've found a pixel that must not be removed so stop here.
                                removeToEnd = false;
                                break;
                            }
                        }

                        if (removeToEnd)
                            removeCount = n-1;
                        else
                            break;
                    }

                    if (removeCount > 0)
                    {
                        int firstRemoval = (p+1) % polygon.Points.Count;
                        int lastRemoval = (p+removeCount) % polygon.Points.Count;

                        // We've found at least one pixel to remove.
                        if (firstRemoval <= lastRemoval)
                        {
                            polygon.Points.RemoveRange(firstRemoval, 1+lastRemoval-firstRemoval);
                            p++;
                        }
                        else
                        {
                            polygon.Points.RemoveRange(firstRemoval, polygon.Points.Count - firstRemoval);
                            polygon.Points.RemoveRange(0, 1+lastRemoval);
                            break;
                        } 
                    }
                    else
                        p++;
                }
            }

            for (int n = 0; n < polygons.Count; n++)
            {
                for (int p = 0; p < polygons[n].Points.Count; p++)
                    output.SetPixel((int) polygons[n].Points[p].X, (int) polygons[n].Points[p].Y, Color.White);
            }

            output.Save(INPUT_PATH + ".corners.png", ImageFormat.Png);
        }

        static void FindEdges (Bitmap bmp, out bool[,] edgeMap, out int edgeCount)
        {
            edgeMap = new bool[bmp.Width, bmp.Height];
            edgeCount = 0;

            // Important: do not count diagonals.

            for (int y = 1; y < bmp.Height-1; y++)
            {
                for (int x = 1; x < bmp.Width-1; x++)
                {
                    if (bmp.GetPixel(x, y).R > 0)
                    {
                        // This is a foreground pixel (part of the polygon).
                        // Count how many surrounded pixels are the background.

                        int count = (bmp.GetPixel(x-1, y).R == 0 ? 1 : 0) +
                                    (bmp.GetPixel(x+1, y).R == 0 ? 1 : 0) +
                                    (bmp.GetPixel(x, y-1).R == 0 ? 1 : 0) +
                                    (bmp.GetPixel(x, y+1).R == 0 ? 1 : 0);

                        if (count > 0 && count < 4)
                        {
                            // It counts as an edge
                            edgeMap[x, y] = true;
                            edgeCount++;
                        }
                    }
                }
            }

            // Now we have to eliminate any edge pixels that are adjacent (including diagonally)
            // to only one other edge pixel; they are dead-ends.

            bool outliersFound = true;
            while (outliersFound)
            {
                outliersFound = false;

                for (int y = 1; y < bmp.Height-1; y++)
                {
                    for (int x = 1; x < bmp.Width-1; x++)
                    {
                        if (edgeMap[x, y])
                        {
                            int count = (edgeMap[x-1, y-1] ? 1 : 0) +
                                        (edgeMap[x-1, y] ? 1 : 0) +
                                        (edgeMap[x-1, y+1] ? 1 : 0) +
                                        (edgeMap[x, y-1] ? 1 : 0) +
                                        (edgeMap[x, y+1] ? 1 : 0) +
                                        (edgeMap[x+1, y-1] ? 1 : 0) +
                                        (edgeMap[x+1, y] ? 1 : 0) +
                                        (edgeMap[x+1, y+1] ? 1 : 0);

                            if (count == 1)
                            {
                                edgeMap[x, y] = false;
                                edgeCount--;
                                outliersFound = true;
                            }
                        }
                    }
                }
            }
        }

        static double GetPointLineDistance (Point p, Point lineA, Point lineB)
        {
            double length = GetLength(lineA, lineB);
            double xAP = lineA.X - p.X;
            double yAP = lineA.Y - p.Y;
            double xBA = (lineB.X - lineA.X) / length;
            double yBA = (lineB.Y - lineA.Y) / length;

			return (xAP * yBA) - (yAP * xBA);
        }

        static double GetNearestPointOffsetOnLine (Point p, Point lineA, Point lineB)
        {
            double xAP = p.X - lineA.X;
            double yAP = p.Y - lineA.Y;
            double xAB = lineB.X - lineA.X;
            double yAB = lineB.Y - lineA.Y;

            double ABdotAB = (xAB*xAB) + (yAB*yAB);
            double APdotAB = (xAP*xAB) + (yAP*yAB);

            if (ABdotAB != 0)
                return APdotAB / ABdotAB;
            else
                return double.NaN;
        }

        static Point GetPointOnLine (Point lineA, Point lineB, double offset)
        {
            double x = lineA.X + (offset * (lineB.X - lineA.X));
            double y = lineA.Y + (offset * (lineB.Y - lineA.Y));
            return new Point(x, y);
        }

        static double GetPointSegmentDistance (Point p, Point segmentA, Point segmentB)
        {
            double offset = GetNearestPointOffsetOnLine(p, segmentA, segmentB);
            if (offset <= 0)
                return GetLength(p, segmentA);
            else if (offset >= 1)
                return GetLength(p, segmentB);
            else
                return GetLength(p, GetPointOnLine(segmentA, segmentB, offset));
        }

        static double GetLength (Point p1, Point p2)
        {
            double dx = p1.X - p2.X;
            double dy = p1.Y - p2.Y;

            return Math.Sqrt((dx*dx) + (dy*dy));
        }

        static Color GetPolygonColor (int index)
        {
            switch (index)
            {
                case 0:
                    return Color.FromArgb(64, 0, 0);
                case 1:
                    return Color.FromArgb(64, 64, 0);
                case 2:
                    return Color.FromArgb(0, 64, 0);
                case 3:
                    return Color.FromArgb(0, 64, 64);
                case 4:
                    return Color.FromArgb(0, 0, 64);
                case 5:
                    return Color.FromArgb(64, 0, 64);
                default:
                    return Color.FromArgb(64, 64, 64);
            }
        }

        static void EvaluatePath (Path path, IList<Path> allPaths)
        {
            while (true)
            {
                List<Point> adjacent = FindAdjacentEdges(path.EdgeMap, path.Points[path.Points.Count-1]);
                if (adjacent.Count >= 2)
                {
                    // Multiple options so create new paths for each option.
                    for (int a = 0; a < adjacent.Count; a++)
                    {
                        Path branch = new Path(path.EdgeMap, path.Points);
                        branch.Points.Add(adjacent[a]);
                        branch.EdgeMap[(int) adjacent[a].X, (int) adjacent[a].Y] = false;
                        allPaths.Add(branch);

                        EvaluatePath(branch, allPaths);
                    }

                    // This path must be abandoned now.
                    break;
                }
                else if (adjacent.Count == 1)
                {
                    // Only one direction to go.
                    path.Points.Add(adjacent[0]);
                    path.EdgeMap[(int) adjacent[0].X, (int) adjacent[0].Y] = false;
                }
                else
                {
                    // No more adjacent pixels; we're done with this path
                    break;
                }
            }
        }

        static Point FindRandomEdge (bool[,] edgeMap)
        {
            for (int y = 1; y < edgeMap.GetLength(1)-1; y++)
                for (int x = 1; x < edgeMap.GetLength(0)-1; x++)
                {
                    if (edgeMap[x, y])
                        return new Point(x, y);
                }

            return Point.Zero;
        }

        static List<Point> FindAdjacentEdges (bool[,] edgeMap, Point point)
        {
            List<Point> list = new List<Point>();

            for (int y = (int) point.Y-1; y <= (int) point.Y+1; y++)
                for (int x = (int) point.X-1; x <= (int) point.X+1; x++)
                {
                    if (x == point.X && y == point.Y)
                        continue;

                    if (edgeMap[x, y])
                        list.Add(new Point(x, y));
                }

            return list;
        }
    }
}

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0