APPARATUS AND METHOD FOR FINDING VISIBLE POINTS IN A CLOUD POINT

• US 20100295850A1
• Filed: 05/24/2009
• Published: 11/25/2010
• Est. Priority Date: 11/29/2006
• Status: Active Grant

• Current Assignee: TECHNION RESEARCH AND DEVELOPMENT FOUNDATION, LTD. (Technion-Israel Institute Of Technology)
• Original Assignee: TECHNION RESEARCH AND DEVELOPMENT FOUNDATION, LTD. (Technion-Israel Institute Of Technology)
• Inventors: Tal, Ayellet, KATZ, Sagi
• Granted Patent: US 8,531,457 B2
• Time in Patent Office: Days
• US Class Current: 345/421
• CPC Class Codes: G06T 15/20 Perspective computation
• CPC Class Codes: G06T 15/40 Hidden part removal
• CPC Class Codes: G06T 15/60 Shadow generation
• CPC Class Codes: G06T 2210/12 Bounding box

Abstract

The subject matter discloses a method of determining whether a point in a computerized image is visible from a viewpoint; said image is represented as a point cloud, the method comprising: performing inversion on a the vicinity of the point thus creating a computerized inversed objects each point in the vicinity of the point is related to a parallel point in the computerized inversed object and obtaining a convex hull of the inversed object; the point is likely to be visible from the viewpoint in case it belongs to the point set composing the convex hull. The method is also useful for shadow casting and for determining the location of an image-capturing device within a volume

Claims

1. A method of determining whether a specific point in a computerized image is visible from a viewpoint;

said image is represented as a point cloud, the method comprising;

a. performing inversion on points located in the vicinity of the specific point thus creating a computerized inversed object, each point in the vicinity of the specific point is translated to a parallel point in the computerized inversed object;

b. defining a convex hull of the inversed object;

c. determining if the specific point is visible from the viewpoint according to the position of its parallel point on the convex hull.

2. The method according to claim 1, wherein determining if the specific point is visible from the viewpoint is performed relative to the parallel point'"'"'s neighboring points.

3. The method according to claim 1, further comprising a step of applying an at least one condition on the parallel point of the specific point before determining that the specific point is visible.

4. The method according to claim 3, wherein the condition is comparing the angle between the parallel point of the specific point and two neighboring points in the point set composing the convex hull to a predetermined value;

a line between the point and the viewpoint divides the angle.

5. The method according to claim 1, further comprising a step of coloring the specific point in case it is determined visible from the viewpoint.

6. The method according to claim 1, further comprising a step removing the specific point from the computerized image in case said point is not determined visible from the viewpoint.

7. The method according to claim 1, wherein determining shadow casting of the specific point by determining the point is visible from a viewpoint representing a light source.

8. The method according to claim 1, wherein the inversion is a spherical inversion.

9. The method according to claim 1, wherein the method is applied to a three dimensional point cloud representation of the image.

13. A method for determining the amount of light falling on an at least one point using the method of claim 1, the method comprises:

a. determining direct illumination by determining visibility of the at least one point from a first set of points acting as a light source;

b. locating a second set of points that are determined to be visible from the first set of points;

c. determining indirect illumination by determining visibility of the at least one point from the second set of points acting as a source of reflecting light;

d. setting the amount of light falling on the at least one point based on it being directly illuminated or indirectly illuminated.

10. A method for determining an optimal location for positioning an image capturing device within a volume, the method comprising:

a. obtaining a plurality of points to be visible from the image capturing device;

b. performing inversion on points located in the vicinity of the plurality of points thus creating a computerized inversed object, each point in the vicinity of the plurality of point is translated to a parallel point in the computerized inversed object;

c. defining a convex hull of the inversed object;

d. determining if a point of the plurality of points is visible from the viewpoint according to the position of its parallel point on the convex hull relative to its neighbor points,

e. repeating said determining for multiple locations within the volume, determining whether a predetermined set of points is visible from each location;

f. selecting the optimal location of the image capturing device based on the results of said repeated determining.

11. The method according to claim 10, wherein determining visibility of the plurality of points by indicating the number or percentage of visible points of the plurality of points is higher than a threshold.

12. The method according to claim 10, wherein the number of points of the plurality of points that are visible from the determined location is higher than the number of points in the plurality of points that are visible from other locations.