US 2026/0087740 A1 · MERGING COPLANAR CONVEX POLYGONS IN CONSTRUCTIVE SOLID GEOMETRY (CSG)

Abstract

Implementations described herein relate to methods, systems, and computer-readable media to cut between coplanar convex polygons. In some implementations, a method includes obtaining the polygons, constructing a corresponding initial coplanar graph, adding that graph into a queue, and cutting each graph in the queue, the cutting including identifying whether the graph includes at least one concave boundary vertex. If there is no concave boundary vertex, the graph is added to a set of result graphs. If there is at least one concave boundary vertex, the cutting selects a starting vertex, finds an optimal cut from the starting vertex to another boundary vertex, splits the graph into subgraphs along the optimal cut, and queues the subgraphs for cutting. The cutting repeats until a termination criterion is satisfied. The method then outputs the result graphs. Using these result graphs may reduce the use of computing resources, such as in real-time applications.

Claims20

Dependent claims

A computer-implemented method to cut between coplanar convex polygons, the method comprising:

obtaining a plurality of coplanar convex polygons, each polygon having a plurality of vertices connected by a plurality of edges;
constructing an initial coplanar graph that represents the plurality of coplanar convex polygons, wherein vertices and edges of the initial coplanar graph correspond to respective vertices and edges of the plurality of coplanar convex polygons;
adding the initial coplanar graph into a queue;
cutting each graph in the queue, wherein the cutting of a graph comprises:
identifying whether the graph includes at least one concave boundary vertex;
if the graph includes no concave boundary vertex, adding the graph to a set of result graphs;
and
if the graph includes at least one concave boundary vertex:
selecting the at least one concave boundary vertex of the graph as a starting vertex;
finding an optimal cut from the starting vertex to another boundary vertex of the graph;
splitting the graph along the optimal cut into two subgraphs;
and
adding the two subgraphs to the queue for cutting;
repeating the cutting until one or more termination criteria is satisfied;
and
outputting the set of result graphs.

13 more elements

A non-transitory computer-readable medium comprising instructions that, responsive to execution by a processing device, causes the processing device to perform operations comprising:

obtaining a plurality of coplanar convex polygons, each polygon having a plurality of vertices connected by a plurality of edges;
constructing an initial coplanar graph that represents the plurality of coplanar convex polygons, wherein vertices and edges of the initial coplanar graph correspond to respective vertices and edges of the plurality of coplanar convex polygons;
adding the initial coplanar graph into a queue;
cutting each graph in the queue, wherein the cutting of a graph comprises:
identifying whether the graph includes at least one concave boundary vertex;
if the graph includes no concave boundary vertex, adding the graph to a set of result graphs;
and
if the graph includes at least one concave boundary vertex:
selecting the at least one concave boundary vertex of the graph as a starting vertex;
finding an optimal cut from the starting vertex to another boundary vertex of the graph;
splitting the graph along the optimal cut into two subgraphs;
and
adding the two subgraphs to the queue for cutting;
repeating the cutting until one or more termination criteria is satisfied;
and
outputting the set of result graphs.

13 more elements

A system comprising:

a memory with instructions stored thereon;
and
a processing device, coupled to the memory, the processing device configured to access the memory and execute the instructions, wherein the instructions cause the processing device to perform operations including:
obtaining a plurality of coplanar convex polygons, each polygon having a plurality of vertices connected by a plurality of edges;
constructing an initial coplanar graph that represents the plurality of coplanar convex polygons, wherein vertices and edges of the initial coplanar graph correspond to respective vertices and edges of the plurality of coplanar convex polygons;
adding the initial coplanar graph into a queue;
cutting each graph in the queue, wherein the cutting of a graph comprises:
identifying whether the graph includes at least one concave boundary vertex;
if the graph includes no concave boundary vertex, adding the graph to a set of result graphs;
and
if the graph includes at least one concave boundary vertex:
selecting the at least one concave boundary vertex of the graph as a starting vertex;
finding an optimal cut from the starting vertex to another boundary vertex of the graph;
splitting the graph along the optimal cut into two subgraphs;
and
adding the two subgraphs to the queue for cutting;
repeating the cutting until one or more termination criteria is satisfied;
and
outputting the set of result graphs.

16 more elements

Dependencies are inferred from the claim text.

Merging coplanar convex polygons in constructive solid geometry (csg)

Life of this patent

Merging coplanar convex polygons in constructive solid geometry (csg)

Life of this patent

Abstract

Claims20