# Find the outline points of an object

## Recommended Posts

Given images below, how one could find all points that form an outilne.

In second image there are 3 outlines.

This is not an image processing thing, i need to do that mathematically, problem is i have no idea how the algorithm should work.

##### Share on other sites

For every edge check if there's an adjacent edge. If there's none, it's part of the outline. If there's one or more, split the edge up in parts that are adjacent and parts that are not.

That's my guess.

##### Share on other sites
Posted (edited)

THis might be weird, but how about... I was thinking voxel. find min max, grid that out with a manageable resolution, go O(n) just once but flood fill on empty space marking appropriate visited. early out on visited. weird right...It would be an accurate / persist-able representation of the solid space in that slice and transformable  whoh...in this representation, you can still continue to slice it up by making a sub group active. Break those off to their own instance, wash rinse repeat. I guess we still need to rasterize. sorry.

Edited by GoliathForge
V LOL How's it going buddy :D Still give my right arm to work there :P

##### Share on other sites

This is kind of from memory so I hope I'm getting it right. I had to do something like this for semi-conductor layout processing back in the 90s.......

First question is: do all the sub-polygons have the same winding?  For instance if they have clockwise winding you can do a "left turn" algorithm.  You have to first set up some data structure that connects all the lines and vertexes. This is kind of a pre-processing step.  So for instance each vertex should have a list of pointers to lines that connect to it. In realty you only really need the outgoing lines. In fact you probably don't need the lines at all, you can make them implicit by having a vertexes point to vertexes, but again vertexes need to be able to point to more than one vertex. If you have crossing polygons you have to break lines that intersect and add a vertex.

Then you start at the first line in your array and traverse in the winding direction. When you hit a vertex with more than two lines connected to it, you take the left most turn that's still in the winding direction.  As you go you mark the path you took, and flag which vertexes and edges you visited.  When you hit a previously encountered line you have found an outline. In that case you loop around the path you just created again, and you will come back to that same line. As you go, copy the outline, and save it however you like.  That's the first outline.....

Now you go to the next line in your array and repeat the process. You can just skip over lines that were flagged in previous steps. When you reach the end of your line array you are done.   I would get a piece of paper, draw some shapes and try it by hand.  Then it becomes obvious how it works.

##### Share on other sites
4 hours ago, _WeirdCat_ said:

Given﻿ images below, how one could find all points﻿ that form an outilne. ﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿﻿

I'd typically define it as "all points bordering empty space", by which definition every single point in your first image is part of the outline. Is this the definition you intend?

The easiest way to accomplish this is to think in terms of edges instead of points. Any edge which belongs to two polygons is an interior edge, any edge which belongs to only one polygon is an exterior edge. The set of points in the outline is the set of points belonging to exterior edges.

##### Share on other sites
Quote

The easiest way to accomplish this is to think in terms of edges instead of points. Any edge which belongs to two polygons is an interior edge, any edge which belongs to only one polygon is an exterior edge.

Given image below all exterior edges belong to two polygons. Please see second image (yellow and blue edges ?belong to two polys?), I wonder if i misunderstood something. But maybe i'm lacking some additional preprocess like subtracting one edge from another?

i'm a bit tired now ( 0:53 am here )

##### Share on other sites
Posted (edited)

hi! how you doing  Looks like you have some work to do edge splitting and triangulating the remaining internally as to not hurt your current representation and then apply the suggested logic. Your silhouette edge list needs to be separately built at some point.

Edited by GoliathForge
that's how we play :D

##### Share on other sites
5 hours ago, _WeirdCat_ said:

But﻿ maybe i'm lacking some additional preprocess like subtracting one edge from another﻿﻿? ﻿﻿﻿﻿﻿

As GoliathForge says, this is a lot easier if you subdivide the polygons wherever T-junctions exist (i.e. wherever a shorter edge is overlaid on a longer edge).

##### Share on other sites
5 hours ago, _WeirdCat_ said:

But maybe i'm lacking some additional preprocess like subtracting one edge from another

I would just intersect all the lines up front and introduce new vertexes where you need them. For lines that overlay each other you can intersect lines with the end vertexes of the other line. If it has to be fast and/or the data set is large you can use some sort of quad-tree based algorithm.  Otherwise you can just use N^2 brute force checking.

Do the sub-polygons ever overlap? I can't tell from your picture because one can be behind another.  If not, you can then just look for lines that don't double up as @Mussi suggested above. That's probably simpler than what I outlined. However if they can overlap, that won't work. Also keep in mind you will likely have to introduce some sort of fudge factor to catch all the intersections because of floating point rounding errors.

##### Share on other sites

Tessellating to triangles would work, but the images look like generated by binary space partition? In that case the boundary information could be found by keeping track of solid / empty space for the half spaces while constructing the tree. So in case you do the BSP construction yourself this should be easy to add.

## Create an account

Register a new account

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 12
• 18
• 15
• 9
• 9