# US 10,504,279 B2 · Visibility function of a three-dimensional scene > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,504,279 B2 - Document ID: US10504279B2 - Status: Granted - Kind: B2 - Application number: 16/232,799 - Filed: 2018-12-26 - Published: 2019-06-27 - Granted: 2019-12-10 - Earliest claimed: 2017-12-24 - Assignees: Dassault Systemes - Applicants: Dassault Systemes - Inventors: Gilles Laurent; Cyril Delalandre; Tamy Boubekeur - Web page: https://patentgrep.com/patent/US10504279B2 ## CPC - G06T 15/40: Hidden part removal - G06F 7/57: Arithmetic logic units [ALU], i.e. arrangements or devices for performing two or more of the operations covered by groups G06F7/483 – G06F7/556 or for performing logical operations {(G06F7/49, G06F7/491 take precedence)} - G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} - G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining - G06T 1/60: Memory management - G06T 15/08: Volume rendering - G06T 2210/21: Collision detection, intersection - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract The disclosure notably relates to a computer-implemented method of computing a visibility function of a 3D scene. The method includes obtaining a set of directions ({right arrow over (ω)}) in the 3D scene, computing a set of lines that are parallel to the direction, for each computed set of lines, sampling the lines of the set into spatial segments, associating each line of a set with a bit field, each spatial segment of the line corresponding to a bit of the bit field, superimposing the set of lines and the 3D scene, when a spatial segment of a line intersects a geometry in the 3D scene, marking the bit, corresponding to the spatial segment of the bit field, associated with the line, obtaining two points in the 3D scene, identifying spatial segments having a closest alignment with the query segment, computing the visibility of the query segment by performing a logical bit operation. ## Claims ### Claim 1 A computer-implemented method of computing of a visibility function of a three-dimensional (3D) scene, comprising: obtaining a set of directions ({right arrow over (ω)}) in the 3D scene; for each direction of the set, computing a set of lines that are parallel to the direction; for each computed set of lines, sampling the lines of the set into spatial segments; associating each line of a set with a bit field, each spatial segment of the line corresponding to a bit of the bit field; superimposing the set of lines and the 3D scene; when a spatial segment of a line intersects a geometry in the 3D scene, marking the bit corresponding to the spatial segment of the bit field associated with the line; obtaining two points in the 3D scene that define a query segment; identifying one or more spatial segments having a closest alignment with the query segment; and computing the visibility of the query segment by performing a logical bit operation on one or more bit fields of the lines the identified one or more spatial segments belong to. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, wherein performing a logical bit operation includes performing a logical bit for a segment [X Y] by computing a function R=(X−1) NAND (Y−1) AND D, where: X is one or more of the bitfield set to 1 at one of the two points of the query segment and to 0 everywhere else, Y is one or more of the bitfield set to 1 at the other one of the two points of the query segment and to 0 everywhere else, and D is one or more bit fields of the lines that the identified one or more spatial segments belong to. ### Claim 3 (depends on 2) The computer-implemented method of claim 2, wherein providing a set of directions in the 3D scene comprises quantizing a parametrization of a unit hemisphere (). ### Claim 4 (depends on 2) The computer-implemented method of claim 2, wherein the parallel lines computed for a direction ({right arrow over (ω)}) are computed from a grid on a plane that is orthogonal to the direction. ### Claim 5 (depends on 1) The computer-implemented method of claim 1, wherein providing a set of directions in the 3D scene comprises quantizing a parametrization of a unit hemisphere (). ### Claim 6 (depends on 5) The computer-implemented method of claim 5, wherein quantizing a parametrization of a unit hemisphere () includes performing an octahedral mapping of the hemisphere. ### Claim 7 (depends on 6) The computer-implemented method of claim 6, wherein the parallel lines computed for a direction ({right arrow over (ω)}) are computed from a grid on a plane that is orthogonal to the direction. ### Claim 8 (depends on 5) The computer-implemented method of claim 5, wherein the parallel lines computed for a direction ({right arrow over (ω)}) are computed from a grid on a plane that is orthogonal to the direction. ### Claim 9 (depends on 1) The computer-implemented method of claim 1, wherein the parallel lines computed for a direction ({right arrow over (ω)}) are computed from a grid on a plane that is orthogonal to the direction. ### Claim 10 (depends on 9) The computer-implemented method of claim 9, wherein the grid on the plane is a regular grid and wherein the grid is the same for each plane orthogonal to each direction. ### Claim 11 (depends on 10) The computer-implemented method of claim 10, further comprising: computing, for each plane, local basis for defining the position of the grid on the plane, the local basis comprising a first vector that is obtained from the direction ({right arrow over (ω)}), a second vector ({right arrow over (eu)}) and third vector ({right arrow over (ev)}) that are the local basis of the plane. ### Claim 12 (depends on 9) The computer-implemented method of claim 9, further comprising: computing, for each plane, local basis for defining the position of the grid on the plane, the local basis comprising a first vector that is obtained from the direction ({right arrow over (ω)}), a second vector ({right arrow over (eu)}) and third vector ({right arrow over (ev)}) that are the local basis of the plane. ### Claim 13 (depends on 12) The computer-implemented method of claim 12, wherein the second vector ({right arrow over (eu)}) and the third vector ({right arrow over (ev)}) are continuous dependence on the direction ({right arrow over (ω)}). ### Claim 14 (depends on 13) The computer-implemented method of claim 13, wherein the continuous dependence on the direction ({right arrow over (ω)}) is given by: ∀{right arrow over (ω)}=(x,y,z)∈, ie, x2+y2+z2=1 and z≥0 ℱ ⁡ ( ω → ) = ( e w → ⁢ ⁢ e v → ) = ( ( 1 - x 2 1 + z - xy 1 + z - x ) , ⁢ ( - xy 1 + z 1 - y 2 1 + z - y ) where is a unit hemisphere; defines a tangential space for a given direction ({right arrow over (ω)}); (x,y,z) are coordinates in the basis of the unit hemisphere. ### Claim 15 (depends on 1) The computer-implemented method of claim 1, wherein identifying one or more spatial segments having a closest alignment with the query segment includes: determining a closest direction among the set of directions; determining the plane associated with the determined closest direction; projecting the query segment on the determined plane; and determining the closest lines to the projected query segment. ### Claim 16 (depends on 15) The computer-implemented method of claim 15, wherein each line of a computed set of lines of a provided direction is a pixel on the plane that is orthogonal to the direction, the set of lines of the provided direction forming a grid of pixels on the plane, and wherein determining the closest lines to the projected query segment includes determining the pixels of the plane that are intersected by the projected query segment, projected query segment forming a set of contiguous pixels on the plane. ### Claim 17 (depends on 15) The computer-implemented method of claim 15, wherein determining the closest direction among the set of directions includes: computing a direction of the query segment and computing the position of the segment in the parametrization of the unit hemisphere (); and selecting a direction among the set of directions which is the closest to the position of the segment in the parametrization of the unit hemisphere (). ### Claim 18 (depends on 1) The computer-implemented method of claim 1, further comprising, before providing a query segment: subdividing the viewport in a set of superpixels, a superpixel being a group of contiguous pixels of the viewport; for each superpixel, computing one nor more clusters of pixels of the superpixel, each computed cluster comprising pixels having one common pixel parameter; for each cluster, computing a sample that represents an average value of at least one parameter of the pixels of the cluster, and adding a reference of the computed sample to the superpixel from which the cluster has been computed; and further comprising, after the computation of the visibility of the segment query: reconstructing the final image for every pixels of the viewport by computing, for each pixel of the viewport, a weighted sum of all the samples of the superpixel the pixel belongs to. ### Claim 19 A non-transitory computer readable medium storing thereon a computer program comprising instructions for performing a computer-implemented method of computing of a visibility function of a three-dimensional (3D) scene, the method comprising: obtaining a set of directions ({right arrow over (ω)}) in the 3D scene; for each direction of the set, computing a set of lines that are parallel to the direction; for each computed set of lines, sampling the lines of the set into spatial segments; associating each line of a set with a bit field, each spatial segment of the line corresponding to a bit of the bit field; superimposing the set of lines and the 3D scene; when a spatial segment of a line intersects a geometry in the 3D scene, marking the bit corresponding to the spatial segment of the bit field associated with the line; obtaining two points in the 3D scene that define a query segment; identifying one or more spatial segments having a closest alignment with the query segment; and computing the visibility of the query segment by performing a logical bit operation on one or more bit fields of the lines the identified one or more spatial segments belong to. ### Claim 20 A system comprising: a processor coupled to a memory and a graphical card with a graphics processing unit (GPU), the memory having recorded thereon a computer program comprising instructions for computing of a visibility function of a three-dimensional (3D) scene that when executed by the processor causes the processor to be configured to: obtain a set of directions ({right arrow over (ω)}) in the 3D scene; for each direction of the set, compute a set of lines that are parallel to the direction; for each computed set of lines, sample the lines of the set into spatial segments; associate each line of a set with a bit field, each spatial segment of the line corresponding to a bit of the bit field; superimpose the set of lines and the 3D scene; when a spatial segment of a line intersects a geometry in the 3D scene, mark the bit corresponding to the spatial segment of the bit field associated with the line; obtain two points in the 3D scene that define a query segment; identify one or more spatial segments having a closest alignment with the query segment; and compute the visibility of the query segment by performing a logical bit operation on one or more bit fields of the lines the identified one or more spatial segments belong to.