Sequencing and scheduling moves for converting concave polyhedra to their convex hulls
AssigneeXerox Corporation
InventorAndrew S. Glassner
Life of this patent
Estimating the term…
Abstract
Methods for modifying shapes represented as non-self-intersecting, simply connected, triangulated polyhedra of genus-0, defined as a plurality of triangular faces, each triangular face defined as a set of three coordinate points, determine an ordering of concave edge elimination procedures which are required to smoothly convert a concave shape to its convex hull. The ordering technique attempts to avoid self-intersections and degeneracies in the metamorphs produced between the starting concave shape and its convex hull.
Claims16
A computer method for transforming a concave shape into a convex hull of said concave shape, said shape stored as electronic signals which represent said shape as a non-self-intersecting, simply connected, triangulated polyhedron of genus-0, defined as a plurality of triangular faces, each triangular face defined as a set of three coordinate points, said method comprising:
- a) identifying all concave edges in said concave shape, each of said concave edges being located between two adjacent triangular faces and defining a shared edge and two shared vertices of said two adjacent triangular faces;
- b) selecting one of said identified concave edges;
- c) performing a concave edge elimination procedure on said selected concave edge by modifying the set of three coordinate points which define each of said two adjacent triangular faces associated with said selected concave edge, so that said selected concave edge is eliminated, said elimination procedure changing said concave shape so that said concave shape is closer to said convex hull;
- and
- d) repeating steps (a)-(c) so that any new concave edges created by said concave edge elimination procedure are identified, and eventually eliminated, steps (a)-(c) repeating until no concave edges remain.
A computer method for transforming a concave shape into a convex hull of said concave shape, said shape stored as electronic signals which represent said shape as a non-self intersecting, simply connected, triangulated polyhedron of genus-0, defined as a plurality of triangular faces each triangular face defined as a set of three coordinate points, said method comprising:
- a) identifying all concave edges in said concave shape;
- b) building a vertex list containing all vertices located in one or more of said identified concave edges;
- c) selecting a vertex from said vertex list;
- d) building a concave edge list containing all concave edges which include said selected vertex;
- e) selecting a concave edge from said concave edge list;
- f) performing a safety procedure on said selected concave edge to determine whether a concave edge elimination procedure can be safely performed on said selected concave edge;
- g) performing said concave edge elimination procedure on said selected concave edge when said concave edge is determined to be safe, otherwise, returning to step (e) and selecting a different concave edge from said concave edge list, said elimination procedure changing said concave shape so that said concave shape becomes less concave;
- h) repeating steps (d)-(g) for the selected vertex, so that said concave edge list for the selected vertex is updated after said concave edge elimination procedure is performed, steps (d)-(g) being repeated until no safe concave edges remain for the selected vertex;
- i) returning to step (c) and selecting a previously unselected vertex;
- j) repeating steps (c)-(i) until all vertices in the concave shape are selected;
- and
- k) repeating steps (a)-(j) until no concave edges remain, said safety procedure step (e) being modified to accept as safe more concave edge eliminations each time steps (a)-(j) are repeated without performing any elimination procedures.
Dependencies are inferred from the claim text.