Hi,
I've got a small problem regarding partitioning of polygons into
zones separated by portals.
Say, I have two sets of polygons of which one set contains the
geometry and the other set contains portals. I want to partition
the geometry set into disjoint subsets, zones, to be connected by
portals.
I guess this problem doesn't have a solution for the general case,
but if I can assume some kind of continuity between the geometry-
polygons, i.e. the polygons might form one or a few meshes making
up rooms and corridors, there should be cases where this problem is
solvable.
This is what my current solution method looks like:
1) Build an adjacency graph of the geometry-polygons, i.e. each
node is a polygon and graph-edges correspond to shared edges.
2) For each portal, cut the graph at the edges that match those of
the portal.
This should result in a lot of subgraphs. The polygons of subgraphs
that are the result of portal cuts can easily be assigned to zones,
but what of the other subgraphs?
These subgraphs could be other geometry, that is no part of a
continuous wall-ceiling-floor-mesh. How do I choose which zone
these polygons should belong to? Polygons that intersect portals
could be forbidden or maybe clipped and I guess I could do some kind
of intersection testing between the volumes made up of the current
zones and the unassigned polygons, but this seems rather untrivial.
Before trying to do this the hard way, I would like to know if there
are any better or more general algorithms for this last part or for
the entire problem.
Hälsningar,
Oskar Linde
|
