# US 2026/0087740 A1 · Merging coplanar convex polygons in constructive solid geometry (csg)

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2026/0087740 A1
- Document ID: US20260087740A1
- Status: Published application
- Kind: A1
- Application number: 18/895,189
- Filed: 2024-09-24
- Published: 2026-03-26
- Earliest claimed: 2024-09-24
- Assignees: Roblox Corporation
- Applicants: Roblox Corporation
- Inventors: Mehdi RAHIMZADEH; Tsvetan G. TSVETANOV
- Web page: https://patentgrep.com/patent/US20260087740A1

## CPC

- G06T 17/10: Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes
- G06T 17/20: Finite element generation, e.g. wire-frame surface description, {tesselation}
- G06T 17/005: {Tree description, e.g. octree, quadtree}
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## 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.

## Claims

### Claim 1

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.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, further comprising using the set of result graphs to render the plurality of coplanar convex polygons.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1, wherein identifying whether the graph includes at least one concave boundary vertex comprises:
calculating graph boundary vertex angle for a vertex of the graph based on lengths of respective edges of coplanar convex polygons that connect the vertex of the graph to other vertices of the graph; and
determining that the vertex is the concave boundary vertex when the graph boundary vertex angle is >π radians.

### Claim 4 (depends on 3)

The computer-implemented method of claim 3, wherein calculating the graph boundary vertex angle is based on an orientation predicate determinant, calculated with respect to exact arithmetic.

### Claim 5 (depends on 1)

The computer-implemented method of claim 1, wherein the finding the optimal cut comprises:
identifying a plurality of sequences of corners in the graph being cut, each having an associated cost, wherein a corner is a path of two consecutive half-edges connecting three vertices; and
selecting a particular sequence of the plurality of sequences that is associated with a cost that is lower than the respective cost for other sequences of the plurality of sequences.

### Claim 6 (depends on 5)

The computer-implemented method of claim 5, wherein identifying the plurality of sequences of corners in the graph comprises:
adding successive corners starting from a corner centered at the starting vertex to candidate sequences of corners until the particular sequence of corners that is associated with a cost that is lower than the respective cost for other sequences for the graph being cut is confirmed as the optimal cut for the graph being cut,
wherein a successive corner is added to the candidate sequences of corners if the successive corner provides a path to reach a vertex in the graph for which no other candidate sequence of corners provides a path with a lower cost.

### Claim 7 (depends on 5)

The computer-implemented method of claim 5, wherein finding the optimal cut penalizes an additional corner that introduces a concave boundary vertex by increasing a cost of a sequence of corners that includes the additional corner.

### Claim 8 (depends on 5)

The computer-implemented method of claim 5, wherein finding the optimal cut rewards an additional corner that resolves a concave boundary vertex by decreasing a cost of a sequence of corners that includes the additional corner.

### Claim 9 (depends on 1)

The computer-implemented method of claim 1, further comprising:
generating circular tables of angles corresponding to vertices of each coplanar convex polygon when constructing the initial coplanar graph,
wherein identifying the concave boundary vertex is based on looking up a respective angle associated with the vertex in the circular tables of angles.

### Claim 10 (depends on 1)

The computer-implemented method of claim 1, wherein if a corner comprises two collinear half-edges, the corner is associated with an angle measuring π radians, and otherwise the corner is associated with angles using an orientation predicate test with respect to exact arithmetic.

### Claim 11 (depends on 1)

The computer-implemented method of claim 1, wherein determining that one or more of the termination criteria are satisfied comprises one or more of:
determining that the queue is empty;
determining that an amount of progress between consecutive executions of the cutting result in a less than threshold amount of progress; or
determining that an early termination threshold is met.

### Claim 12

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.

### Claim 13 (depends on 12)

The non-transitory computer-readable medium of claim 12, wherein the instructions cause the processing device to perform further operations comprising using the set of result graphs to render the plurality of coplanar convex polygons.

### Claim 14 (depends on 12)

The non-transitory computer-readable medium of claim 12, wherein identifying whether the graph includes at least one concave boundary vertex comprises:
calculating graph boundary vertex angle for a vertex of the graph based on lengths of respective edges of coplanar convex polygons that connect the vertex of the graph to other vertices of the graph; and
determining that the vertex is the concave boundary vertex when the graph boundary vertex angle is >π radians.

### Claim 15 (depends on 12)

The non-transitory computer-readable medium of claim 12, wherein the finding the optimal cut comprises:
identifying a plurality of sequences of corners in the graph being cut, each having an associated cost, wherein a corner is a path of two non-boundary half-edges connecting three vertices; and
selecting a particular sequence of the plurality of sequences that is associated with a cost that is lower than the respective cost for other sequences of the plurality of sequences.

### Claim 16 (depends on 12)

The non-transitory computer-readable medium of claim 12, wherein determining that one or more of the termination criteria are satisfied comprises one or more of:
determining that the queue is empty;
determining that an amount of progress between consecutive executions of the cutting result in a less than threshold amount of progress; or
determining that an early termination threshold is met.

### Claim 17

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.

### Claim 18 (depends on 17)

The system of claim 17, wherein identifying whether the graph includes at least one concave boundary vertex comprises:
calculating graph boundary vertex angle for a vertex of the graph based on lengths of respective edges of coplanar convex polygons that connect the vertex of the graph to other vertices of the graph; and
determining that the vertex is the concave boundary vertex when the graph boundary vertex angle is >π radians.

### Claim 19 (depends on 17)

The system of claim 17, wherein the finding the optimal cut comprises:
identifying a plurality of sequences of corners in the graph being cut, each having an associated cost, wherein a corner is a path of two non-boundary half-edges connecting three vertices; and
selecting a particular sequence of the plurality of sequences that is associated with a cost that is lower than the respective cost for other sequences of the plurality of sequences.

### Claim 20 (depends on 17)

The system of claim 17, wherein determining that one or more of the termination criteria are satisfied comprises one or more of:
determining that the queue is empty;
determining that an amount of progress between consecutive executions of the cutting result in a less than threshold amount of progress; or
determining that an early termination threshold is met.
