Skip to content

Hole Detection #10

Open
Open

Description

@wtaisto

I'm looking at using your lib to modify 2d texture maps on 3d meshes based on where the meshes are pressed against each other (anti-coplanar faces.) After performing an operation which returns a polygon with multiple Regions, is there a way to know if the Regions refer to holes vs freestanding polygons? In the example below, when subtracting blue from red, both scenarios return 3 Regions. From my experimenting, it appears that the first Region returned tends to be "the biggest outermost Region", but the remainder being holes or not is unclear. I tried testing to see if the vertex winding order is opposite for outlines / holes, but it did not seem to be. I've read through tutorials on this algorithm, and have a vague sense that the notion of "a RegionIS a hole or not" might itself be loosely defined.

image

Ultimately, I really just need to be able to take the regions that pop out of an intersection operation, and apply an earcut / tessellating algorithm to them to get a triangularized mesh. The only earcut implementations I've found specifically ask for information on where the holes are; do you know of any implementations which would work using the output of your lib?

Activity

  1. wtaisto commented on Dec 12, 2021

    @wtaisto
    Author

    Since the result of a boolean operation would never return regions with overlapping edges, the regions should be parseable as a "contains" tree. So a region being a hole is the same as it's node depth being even. Tessellating gets easier then; traverse the tree from the root non-hole, and if it has a hole, just combine the edges with the edges of the hole, cutting an O into a C, then tessellate that normally. Keep doing that recursively down the containment tree, voila. Maybe i'll get enthusiastic and suggest a patch.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions