Ideas/Solutions for finding the outside corner points of a mesh

Questions & Answers
1

Hey guys,

I’ve been trying to find a solution to this problem for way too long, and I think I need some other ideas for how to go about it.

I have a Sims style house design tool that I’ve been working on, and I’m currently creating a Roof Generator. I had picked up the Buildr Plug-in a while back and I’m modifying his roof code, but it requires the corner points of a mesh to work properly.

I was hoping someone might have a solution or idea on how to do this. I was traversing the voxels of each wall piece for outside points, but my solution doesn’t work for every case (namely 1 wide walls). So I thought I’d see if some others had ideas on this while I try to rework my current solution.

Here’s an example of the current house, with the mesh selected on top that would generate a roof (the roof mesh was disabled in this) on it (it only generates on a specific texture, so you could paint other voxels on that mesh a different on and the roof would generate around them. Except for holes, it just builds overtop of them since the roof algorithms only work for simple polygons.

41435-meshexample.jpg
41435-meshexample.jpg882×674 203 KB

Edit:
I should add, that the corner vertices are all I need. If you were to trace a line along the outside of the mesh, every time you change direction, I need that vertex (in clockwise or counter-clockwise order). So the image provided would have 8 vertices total - usually starting at the top left… just because everything I’ve written for the game so far does that.

2

I figured this out, mostly, so I thought I’d post my solution here.

Each vertex shown in the image above is 4 points (one for each block - I combine later once the design is permanent), and each point has an on or off boolean.

  • So, I traverse the outside edges
    (clockwise) storing each relevant
    block.
  • I then walk through each block
    stored adding each vertex in a
    clockwise order (starting vertex is
    based on the direction traveled to
    that block) until there’s a
    neighboring block along that edge.
    Before being added each vertex checks if it’s an outside
    edge based on the other 3 vertices
    that share that space (more or less,
    if any are off it’s worth adding to
    the list to check next - but it won’t
    add duplicate vertices).
  • I then walk through each vertex and
    if the angle to the next vertex from
    the current one is different than the
    previous, I store it as a corner.

I’ll simplify it more over time, but this works for now. Since I only have 8 directions (multiples of 45 degrees), I figured certain assumptions can be made later to make things a bit easier for this specific use.