US Patent Application 17661193. APPROXIMATE HIERARCHICAL CONVEX DECOMPOSITION simplified abstract

From WikiPatents
Jump to navigation Jump to search

APPROXIMATE HIERARCHICAL CONVEX DECOMPOSITION

Organization Name

Apple Inc.


Inventor(s)

Khaled Mammou of Danville CA (US)

Adrian A Biagioli of Sunnyvale CA (US)

Deepak S Tolani of Sunnyvale CA (US)

APPROXIMATE HIERARCHICAL CONVEX DECOMPOSITION - A simplified explanation of the abstract

This abstract first appeared for US patent application 17661193 titled 'APPROXIMATE HIERARCHICAL CONVEX DECOMPOSITION

Simplified Explanation

- The patent application describes a method for decomposing a three-dimensional object into multiple convex hulls. - The method involves using a cluster priority queue in a computing system memory to store clusters corresponding to the object. - A concavity measure is computed for each cluster in the queue to determine the cluster with the highest concavity measure. - The cluster with the highest concavity measure is then divided into two new clusters using a cut plane, with each new cluster having a corresponding convex hull. - The cut plane is computed through a hierarchical search of potential cut planes. - The original cluster is removed from the queue, and the two new clusters are added to the queue.


Original Abstract Submitted

A method of decomposing a three-dimensional representation of an object into a plurality of convex hulls can include instantiating a cluster priority queue in a computing system memory that initially contains a cluster corresponding to the three-dimensional representation of the object, computing with a processor of the computing system a concavity measure for each cluster in the cluster priority queue, and, for the cluster with the highest concavity measure: (1) computing with the processor a cut plane that divides the cluster corresponding to the three-dimensional representation of the object into two new clusters, each of the two new clusters having a corresponding convex hull, wherein computing a cut plane includes performing a hierarchical search of potential cut planes, (2) removing the cluster corresponding to the three-dimensional representation of the object from the cluster priority queue, and (3) adding the two new clusters to the cluster priority queue.