Generating point clouds
OwnerRobert Andrew Palais, Richard Sheldon Palais +1inventors
InventorsRobert Andrew Palais, Richard Sheldon Palais, Hermann Rudolf Theobald Karcher
Life of this patent
Estimating the term…
Abstract
Presented are embodiments for the generation of point clouds on a surface. A surface is described by a mathematical function. The surface may be subdivided into a plurality of patches, a plurality of triangles, or a plurality of rectangles, inter alia. A plurality of points are calculated and distributed among the patches, triangles, or rectangles comprising the surface. Generation of such point clouds may be useful in rendering N-dimensional surfaces for display or output on computer display or output devices.
Claims38
A computer-implemented method for generating point clouds on a surface, the surface being described as the zero set of a mathematical function, the method comprising:
- selecting a direction from a set of uniformly distributed random directions on a unit sphere in space;
- selecting a point from a set of uniformly distributed random points on a disc in a plane;
- and
- rotating the selected point on the disc to a plane perpendicular to the selected direction;
- and
- constructing a line in the selected direction through a resulting nearest point to an origin.
A computer-implemented method for generating a point cloud on a surface in three dimensions, the surface being described parametrically by a mathematical function or by a set of triangles, the method comprising:
- distributing a plurality of points among triangles in a triangulated surface randomly, such that the distribution of the points is asymptotically proportional to an area represented by each triangle;
- and
- assigning each point assigned to each triangle to a point within the each triangle.
A computer-implemented method for generating point clouds on a surface in three dimensions that is described parametrically by a mathematical function or by a set of rectangles, the method comprising:
- distributing a set of points among a set of patches of said parametrized surface randomly such that the distribution of points is asymptotically proportional to an area represented by each patch;
- and
- assigning each point assigned to each patch to a point within the each patch.
A computer-implemented method of finding approximate roots of a function, the function defining a surface, and the roots being restricted to those roots lying on a line intersecting with the surface, the method comprising:
- dividing an interval of a line into equal subintervals such that each subinterval is less than a given epsilon, epsilon being chosen such that whenever the function vanishes within an interval of less than epsilon, the probability is high that the function has different signs at the two endpoints of the interval;
- for each subinterval, determining whether the function has different signs at the two endpoints of the each subinterval;
- when the function has a different sign at the two ends of the each subinterval, determining an approximate root within the each subinterval.
A computer-implemented method of distributing points among a set of grid patches in a subdivision of a surface parameterized by functions, the method comprising:
- for each of the set of grid patches, approximating the area of the each grid patch;
- storing partial sums of the approximate areas of the each grid patch in a persistent array such that each grid patch corresponds to a particular partial sum within the persistent array;
- determining the total area of the set of grid patches;
- determining a random number lying between zero and the total area of the grid patches;
- determining a grid patch which corresponds to a stored partial sum corresponding to the random number;
- assigning the random number to a random point within the determined grid patch.
A computer-implemented method for distributing points in a rectilinear region R of space that is subdivided into a plurality of cubes (voxels) and wherein a positive real-valued density function is defined in the region R, comprising:
- distributing points among the cubes such that the distribution of points is asymptotically proportional to a mass of each cube wherein the mass of each cube is given by the integral of the density over the cube.
Dependencies are inferred from the claim text.