System and method for constructive solid geometry operations

1 . A computer-implemented method to create a topological structure, the method comprising:

applying a constructive solid geometry (CSG) operation to a first object and a second object;

determining triangles that are left unchanged by the CSG operation;

applying a sweep and prune algorithm to the triangles to determine a list of intersecting triangles;

extracting a list of intersecting convex polygonal faces from the list of intersecting triangles;

generating a first treelet from a first set of faces associated with the first object from respective pairs of intersecting convex polygonal faces in the list of intersecting convex polygonal faces;

identifying whether first fragments in the first set of faces are inside second objects;

generating a second treelet from a second set of faces from the respective pairs in the list of intersecting convex polygonal faces;

identifying whether second fragments in the second set of faces are inside the first object;

responsive to the identifying, determining whether there is a union, intersection, or subtraction for the respective pairs in the list of intersecting convex polygonal faces; and

assembling the set of first fragments and the set of second fragments to create a topological structure based on the determinations of union, intersection, or subtraction.

2 . The method of claim 1 , wherein further comprising:

maintaining a list of added fragments and discarded fragments, wherein the added fragments are added to the topological structure and discarded fragments are excluded from the topological structure; and

performing subsequent CSG operations to iteratively add subsequent fragments to the topological structure to form an avatar for a virtual experience.

3 . The method of claim 1 , wherein identifying whether the first fragments in the first set of faces are inside the second object is based on determining whether a vertex of the first fragments lie below, above, or on a plane of the second set of faces.

4 . The method of claim 1 , further comprising:

maintaining a list of added fragments and discarded fragments, wherein the added fragments are added to the topological structure and discarded fragments are excluded from the topological structure; and

transmitting, from a server to a client device, information about the list of added fragments and discarded fragments, wherein transmitting the information about the list incrementally enables the client device to incrementally form the topological structure.

5 . The method of claim 1 , wherein the topological structure is an intersection collar that is added to a mesh created by the CSG operation.

6 . The method of claim 1 , wherein the topological structure is a closed two-manifold mesh.

7 . The method of claim 1 , wherein union of the first object and the second object is determined based on determining that:

a first face of the first object intersects with the second object;

a first fragment of the first face is inside the second object;

a second face of the second object intersects with the first object; and

a second fragment of the second face is inside the first object.

8 . The method of claim 1 , wherein intersection of the first object and the second object is determined based on determining that:

a first face of the first object intersects with the second object;

a first fragment of the first face is outside the second object;

a second face of the second object intersects with the first object; and

a second fragment of the second face is outside the first object.

9 . The method of claim 1 , wherein subtraction of the second object from the first object is determined based on determining that:

a first face of the first object intersects with the second object;

a first fragment of the first face is inside the second object;

a second face of the second object intersects with the first object; and

a second fragment of the second face is outside the first object.

10 . A device to create a topological structure, the device comprising:

a processor; and

a memory coupled to the processor, with instructions stored thereon that, when executed by the processor, cause the processor to perform operations comprising:

applying a constructive solid geometry (CSG) operation to a first object and a second object;

determining triangles that are left unchanged by the CSG operation;

applying a sweep and prune algorithm to the triangles to determine a list of intersecting triangles;

extracting a list of intersecting convex polygonal faces from the list of intersecting triangles;

generating a first treelet from a first set of faces associated with the first object from respective pairs of intersecting convex polygonal faces in the list of intersecting convex polygonal faces;

identifying whether first fragments in the first set of faces are inside second objects;

generating a second treelet from a second set of faces from the respective pairs in the list of intersecting convex polygonal faces;

identifying whether second fragments in the second set of faces are inside the first object;

responsive to the identifying, determining whether there is a union, intersection, or subtraction for the respective pairs in the list of intersecting convex polygonal faces; and

assembling the set of first fragments and the set of second fragments to create a topological structure based on the determinations of union, intersection, or subtraction.

11 . The device of claim 10 , wherein the operations further comprise:

maintaining a list of added fragments and discarded fragments, wherein the added fragments are added to the topological structure and discarded fragments are excluded from the topological structure; and

performing subsequent CSG operations to iteratively add subsequent fragments to the topological structure to form an avatar from a virtual experience.

12 . The device of claim 10 , wherein identifying whether the first fragments in the first set of faces are inside the second object is based on determining whether a vertex of the first fragments lie below, above, or on a plane of the second set of faces.

13 . The device of claim 10 , wherein the operations further comprise:

maintaining a list of added fragments and discarded fragments, wherein the added fragments are added to the topological structure and discarded fragments are excluded from not added to the topological structure; and

transmitting, from a server to a client device, information about the list of added fragments and discarded fragments, wherein transmitting the information about the list incrementally enables the client device to incrementally form the topological structure.

14 . The device of claim 10 , wherein the topological structure is an intersection collar that is added to a mesh created by the CSG operation.

15 . A non-transitory computer-readable medium with instructions to create a topological structure stored thereon that, when executed by one or more computers, cause the one or more computers to perform operations, the operations comprising:

applying a constructive solid geometry (CSG) operation to a first object and a second object;

determining triangles that are left unchanged by the CSG operation;

applying a sweep and prune algorithm to the triangles to determine a list of intersecting triangles;

extracting a list of intersecting convex polygonal faces from the list of intersecting triangles;

generating a first treelet from a first set of faces associated with the first object from respective pairs of intersecting convex polygonal faces in the list of intersecting convex polygonal faces;

identifying whether first fragments in the first set of faces are inside second objects;

generating a second treelet from a second set of faces from the respective pairs in the list of intersecting convex polygonal faces;

identifying whether second fragments in the second set of faces are inside the first object;

responsive to the identifying, determining whether there is a union, intersection, or subtraction for the respective pairs in the list of intersecting convex polygonal faces; and

assembling the set of first fragments and the set of second fragments to create a topological structure based on the determinations of union, intersection, and subtraction.

16 . The computer-readable medium of claim 15 , wherein the operations further comprise:

maintaining a list of added fragments and discarded fragments, wherein the added fragments are added to the topological structure and discarded fragments are excluded from the topological structure; and

performing subsequent CSG operations to iteratively add subsequent fragments to the topological structure to form an avatar for a virtual experience.

17 . The computer-readable medium of claim 15 , wherein identifying whether the first fragments in the first set of faces are inside the second object is based on determining whether a vertex of the first fragments lie below, above, or on a plane of the second set of faces.

18 . The computer-readable medium of claim 15 , wherein the operations further comprise:

maintaining a list of added fragments and discarded fragments, wherein the added fragments are added to the topological structure and discarded fragments are excluded from the topological structure; and

transmitting, from a server to a client device, information about the list of added fragments and discarded fragments, wherein transmitting the information about the list incrementally enables the client device to incrementally form the topological structure.

19 . The computer-readable medium of claim 15 , wherein the topological structure is an intersection collar that is added to a mesh created by the CSG operation.

20 . The computer-readable medium of claim 15 , wherein the topological structure is a closed two-manifold mesh.