# US 12,762,783 B2 · Micro-meshes, a structured geometry for computer graphics > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,762,783 B2 - Document ID: US12762783B2 - Status: Granted - Kind: B2 - Application number: 17/946,235 - Filed: 2022-09-16 - Published: 2023-04-06 - Granted: 2026-10-13 - Earliest claimed: 2021-09-16 - Assignees: NVIDIA Corporation - Applicants: NVIDIA Corporation - Inventors: Henry Packard Moreton; Yury Uralsky; John Burgess - Web page: https://patentgrep.com/patent/US12762783B2 ## CPC - G06T 15/06: Ray-tracing - G06T 1/60: Memory management - G06T 9/001: {Model-based coding, e.g. wire frame} - G06T 15/005: {General purpose rendering architectures} - G06T 15/40: Hidden part removal - G06T 15/50: Lighting effects - G06T 17/10: Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes - G06T 17/20: Finite element generation, e.g. wire-frame surface description, {tesselation} - G06T 17/205: {Re-meshing} - G06T 19/20: Editing of three-dimensional [3D] images, e.g. changing shapes or colours, aligning objects or positioning parts - G06T 2210/08: Bandwidth reduction - G06T 2210/12: Bounding box - G06T 2210/21: Collision detection, intersection - G06T 2210/36: Level of detail - G06T 2219/2016: Rotation, translation, scaling - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract A μ-mesh (“micromesh”), which is a structured representation of geometry that exploits coherence for compactness and exploits its structure for efficient rendering with intrinsic level of detail is provided. The micromesh is a regular mesh having a power-of-two number of segments along its perimeters, and which can be overlaid on a surface of a geometric primitive. The micromesh is used for providing a visibility map and/or a displacement map that is accessible using barycentric coordinates of a point of interest on the micromesh. ## Claims ### Claim 1 A non-transitory computer readable storage medium storing instructions that, when executed by a processor of a computer system comprising a memory, causes the computer system to perform operations comprising: identifying a microtriangle of interest in a grid of microtriangles overlaid on an area on a surface of an object; determining an index into an index data structure based only on barycentric coordinates of the microtriangle of interest within the grid of microtriangles without storing a mapping from the barycentric coordinates of the microtriangle of interest to an index into the index data structure; accessing by indexing, in the memory and based only on the determined index, a value stored in the index data structure, wherein the value represents a characteristic of the surface at a location corresponding to a position of the microtriangle of interest; and rendering, in accordance with the accessed value, a pixel corresponding to the location corresponding to the position of the microtriangle of interest. ### Claim 2 (depends on 1) The non-transitory computer readable storage medium according to claim 1, wherein the index data structure stores at least a visibility status for each microtriangle in the grid of microtriangles, wherein the visibility status indicates at least one of an opaque visibility status and a transparent visibility status. ### Claim 3 (depends on 1) The non-transitory computer readable storage medium according to claim 1, wherein the index data structure stores at least a displacement for each microtriangle in the grid of microtriangles. ### Claim 4 (depends on 3) The non-transitory computer readable storage medium according to claim 3, wherein the displacement comprises a displacement direction and a displacement value. ### Claim 5 (depends on 1) The non-transitory computer readable storage medium according to claim 1, wherein the area comprises one or more triangle-shaped areas, the index data structure comprises a set of bits for each microtriangle, wherein the sets of bits for respective microtriangles of the grid of microtriangles are arranged in order of a preconfigured traversal path of the grid and of microtriangles. ### Claim 6 (depends on 5) The non-transitory computer readable storage medium according to claim 5, wherein the preconfigured traversal path corresponds to a space-filling curve for the area. ### Claim 7 (depends on 1) The non-transitory computer readable storage medium according to claim 1, wherein identifying a microtriangle of interest in a grid of microtriangles spatially overlaid on an area comprises: determining a desired level of detail; and obtaining access to the grid of microtriangles, wherein the grid of microtriangles is identified as a grid corresponding to the desired level of detail in a hierarchy of respective grids each having a different level of detail and having triangles of a different size arranged to overlay the area. ### Claim 8 (depends on 1) The non-transitory computer readable storage medium according to claim 1, wherein the instructions, when executed by the processor, causes the computer system to perform operations further comprising: accessing, in the memory and based only on barycentric coordinates of the microtriangle of interest within the grid of microtriangles, a second value stored in a second index data structure, wherein the first value is a visibility status and the second value is a displacement status; and rendering, in accordance with the visibility status and the displacement status, the pixel corresponding to the location corresponding to the position of the microtriangle of interest. ### Claim 9 A data structure comprising a plurality of sets of bits, each set of bits corresponding to a respective group of one or more microtriangles in a plurality of microtriangles contiguously arranged to spatially overlay an area on a surface of an object, the plurality of sets of bits arranged in accordance with a preconfigured traversal order of the plurality of microtriangles, and each set of bits configured to represent a characteristic of the area at a location corresponding to a position of the microtriangle of interest, wherein the data structure is configured such that a location in the data structure is determined based only on barycentric coordinates of the microtriangle of interest without storing a mapping from the barycentric coordinates of the microtriangle of interest to an index into the data structure. ### Claim 10 (depends on 9) The data structure according to claim 9, configured to be accessed using barycentric coordinates associated with a microtriangle in the plurality of microtriangles. ### Claim 11 (depends on 9) The data structure according to claim 9, wherein bits in the plurality of sets of bits represent visibility information of the area on the surface, wherein the visibility information includes at least one of an opaque status and a transparent status for each texel of the area. ### Claim 12 (depends on 9) The data structure according to claim 9, wherein bits in the plurality of sets of bits represent displacement information of the area on the surface, wherein the displacement information includes a displacement value and a displacement direction for each texel of the area. ### Claim 13 A method of forming an index data structure configured to provide access to values representing one or more characteristics of a surface of an object at a location corresponding to a position of a microtriangle of interest, the method comprising: assigning a visibility status to each microtriangle in a grid of microtriangles spatially overlaid on an area on the surface, wherein the visibility status includes at least one of an opaque status and a transparent status; encoding the index data structure based on barycentric coordinates of said each microtriangle and a preconfigured traversal order of the grid of microtriangles, wherein each location in the index data structure is configured to be accessed by determining the location in the index data structure based only on barycentric coordinates of a respective microtriangle of the grid of microtriangles without storing a mapping from the barycentric coordinates of the respective microtriangle to an index into the index data structure; and storing the encoded index data structure in a memory. ### Claim 14 (depends on 13) The method according to claim 13, wherein the storing the encoded index data structure in a memory includes associating the encoded index data structure with the object stored in a bounding volume hierarchy stored in the memory. ### Claim 15 A method of forming an index data structure configured to provide access to values representing one or more characteristics of a surface of an object at a location corresponding to a position of a microtriangle of interest, the method comprising: determining a displacement amount and a displacement direction for each microvertex of each microtriangle in a grid of microtriangles spatially overlaid on an area on the surface, wherein the displacement amount is specified in relation to a base triangle; encoding the index data structure based on barycentric coordinates of said each microtriangle and a preconfigured traversal order of the grid of microtriangles, wherein each location in the index data structure is configured to be accessed by determining the location in the index data structure based only on barycentric coordinates of a respective microtriangle of the grid of microtriangles without storing a mapping from the barycentric coordinates of the respective microtriangle to an index into the index data structure; and storing the encoded index data structure in a memory. ### Claim 16 (depends on 15) The method according to claim 15, wherein the determining a displacement amount and a displacement direction for each microvertex of each microtriangle includes determining microtriangle vertices by prediction based on adjacent vertices, and the encoding includes encoding a correction of the prediction for respective predicted microvertices. ### Claim 17 (depends on 15) The method according to claim 15, wherein the determining a displacement amount and a displacement direction for each microvertex of each microtriangle further includes performing edge decimation in one or more micromeshes. ### Claim 18 A method of forming a data structure representing geometry, comprising performing with at least one processor, operations comprising: defining regions of a planar or warped geometric primitive; assigning different visibility indicators to different regions; encoding the visibility indicators based on a predetermined sequence of the regions; and storing the data structure including the encoded visibility indicators in a memory, wherein the encoded visibility indicator of each region is configured to be accessed by determining a location in the data structure based only on barycentric coordinates of the each region without storing a mapping from the barycentric coordinates of the each region to an index into the data structure.