Method and apparatus for providing continuous level of detail

• US 6,169,549 B1
• Filed: 01/07/1998
• Issued: 01/02/2001
• Est. Priority Date: 01/07/1998
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Iengineer.Com, Inc.
• Inventors: Burr, Timothy J.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US09/003,863
• Time in Patent Office: 1,091 Days
• Field of Search: 345/440, 345/441, 345/433, 345/428, 345/118, 345/121, 345/419, 345/421, 345/427
• US Class Current: 345/419
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame

Abstract

A method and apparatus that provides for off-line generation of, and run-time evaluation for, continuous LODs. The off-line multiresolution generation process is modified and constrained such that a progressive mesh representation for continuous LODs is created that allows properly designed run-time topological data structures to be overloaded to support both LOD construction and optimized rendering. More specifically, the offline generation process initially preprocesses the mesh to generate a triangle-fan covering composed of only complete cycles. The multiresolution generation process is then constrained to maintain this complete cycle covering for every interim mesh. For run-time evaluation, a topological adjacency representation is used that can serve dual uses. This supportive run-time representation is partitioned so as to allow efficient access by the renderer to the subset of the adjacency information that is the fan covering. The multiresolution representation can be generated so as to allow discontinuities to be rendered at some cost to rendering performance.

Claims

1. A method for providing continuous level of detail including:

processing a mesh to generate a base mesh and a plurality of progressive mesh modification records, said progressive mesh modification records corresponding to interim meshes having corresponding levels of detail, said base mesh and said interim meshes comprising a plurality of vertices, adjacent ones of said vertices sharing edges; and

constraining said processing step so that said vertices of said base mesh and said interim meshes all belong to complete cycles, each of said vertices being identified as one of a cycle vertex and a cycle boundary vertex, said complete cycles each comprising one said cycle vertex and a plurality of said cycle boundary vertices adjacent to said cycle vertex.

2. The method defined in claim 1, wherein said constraining step includes swapping diagonals in said mesh to insure that said base and interim meshes are comprised of only complete cycles.

3. The method of claim 1, wherein said constraining step includes:

tagging each vertex in said mesh as one of said cycle vertex and said cycle boundary vertex;

firstly verifying that all vertices adjacent to each vertex tagged as said cycle vertex are tagged as cycle boundary vertices; and

secondly verifying that a cycle formed by all vertices adjacent to each vertex tagged as said cycle boundary vertex is comprised of an alternating sequence of vertices tagged as cycle vertices and cycle boundary vertices.

4. The method defined in claim 3, further comprising:

identifying a failed vertex that fails said first and second verifying steps;

identifying a polygon having said failed vertex as one of its vertices;

identifying a first diagonal of said polygon by which two vertices of said polygon are currently adjacent;

identifying a second diagonal of said polygon by which two other vertices of said polygon that are not currently adjacent can be made to be adjacent;

swapping said first diagonal with said second diagonal so that said two other vertices are adjacent; and

repeating said first and second verifying steps for all vertices of said polygon.

5. The method defined in claim 4, further comprising storing information relating to said swapping step.

6. The method defined in claim 5, further comprising:

selecting certain of said progressive mesh modification records in accordance with a desired level of detail;

building said desired level of detail by modifying a current mesh having a corresponding current level of detail in accordance with said certain progressive mesh modification records and said base mesh to arrive at an interim mesh corresponding to said desired level of detail; and

adjusting said interim mesh in accordance with said stored information relating to said swapping step.

7. The method defined in claim 1, further comprising:

selecting certain of said progressive mesh modification records in accordance with a desired level of detail; and

building said desired level of detail by modifying a current mesh having a corresponding current level of detail in accordance with said certain progressive mesh modification records and said base mesh to arrive at an interim mesh corresponding to said desired level of detail.

8. The method defined in claim 7, wherein said progressive mesh modification records define refinement operations and decimation operations, said building step including:

refining said current mesh in accordance with said refinement operations of said certain progressive mesh modification records to arrive at said corresponding interim mesh.

9. The method defined in claim 7, wherein said progressive mesh modification records define refinement operations and decimation operations, said building step including:

decimating said current mesh in accordance with said decimation operations of said certain progressive mesh modification records to arrive at said corresponding interim mesh.

10. The method defined in claim 9, wherein said decimating step includes collapsing a first cycle boundary vertex of said current mesh into a second cycle boundary vertex of said current mesh adjacent to said first cycle boundary vertex.

11. The method defined in claim 9, wherein said decimating step includes collapsing all cycle vertices of said current mesh that are adjacent to a first cycle boundary vertex of said current mesh into said first boundary cycle vertex.

12. The method defined in claim 1, wherein said processing step includes:

performing a decimation operation on said mesh to form a decimated mesh with a corresponding lower level of detail, said decimated mesh having a second complete cycle covering different than a first complete cycle covering of said mesh; and

generating a progressive mesh modification record including information about said decimation operation.

13. The method defined in claim 12, wherein said decimation operation includes collapsing a first cycle boundary vertex of said mesh into a second cycle boundary vertex of said mesh adjacent to said first cycle boundary vertex.

14. The method defined in claim 12, wherein said decimation operation includes collapsing all cycle vertices of said mesh that are adjacent to a first cycle boundary vertex of current mesh into said first boundary cycle vertex.

15. The method defined in claim 1, wherein said processing step includes:

generating a vertex list corresponding to said mesh;

remapping said vertex list in correspondence with an ordering of said progressive mesh modification records.

16. A method for processing a mesh having a plurality of vertices, adjacent ones of said vertices sharing edges, said method comprising:

calculating a complete cycle covering of said mesh such that all said vertices belong to cycles; and

tagging each of said vertices as one of a cycle vertex and a cycle boundary vertex, each of said cycles consisting of one cycle vertex and a plurality of cycle boundary vertices.

17. The method defined in claim 16, wherein said calculating step is performed such that all vertices adjacent to each vertex tagged as said cycle vertex are tagged as cycle boundary vertices and such that a non-covering cycle formed by all vertices adjacent to each vertex tagged as said cycle boundary vertex is comprised of an alternating sequence of vertices tagged as cycle vertices and cycle boundary vertices.

18. The method defined in claim 16, further comprising:

generating a plurality of progressive mesh modification records, said progressive mesh modification records corresponding to interim meshes having corresponding levels of detail between a base mesh and a detailed mesh, said generating step being performed such that all vertices in said base mesh, said interim meshes and said detailed mesh belong to cycles.

19. An apparatus for providing continuous level of detail including:

means for processing a mesh to generate a base mesh and a plurality of progressive mesh modification records, said progressive mesh modification records corresponding to interim meshes having corresponding levels of detail, said base mesh and said interim meshes comprising a plurality of vertices, adjacent ones of said vertices sharing edges; and

means for constraining said processing step so that all said vertices in said base mesh and said interim meshes belong to cycle coverings, each of said vertices being identified as one of a cycle vertex and a cycle boundary vertex, said cycle coverings each comprising one said cycle vertex and a plurality of said cycle boundary vertices adjacent to said cycle vertex.

20. The apparatus defined in claim 19, wherein said means for constraining includes means for swapping diagonals in said mesh to insure that all vertices in said mesh belong to cycle coverings.

21. The apparatus of claim 19, wherein said means for constraining includes:

means for tagging each vertex in said mesh as one of said cycle vertex and said cycle boundary vertex;

first means for verifying that all vertices adjacent to each vertex tagged as said cycle vertex are tagged as cycle boundary vertices; and

second means for verifying that a cycle formed by all vertices adjacent to each vertex tagged as said cycle boundary vertex is comprised of an alternating sequence of vertices tagged as cycle vertices and cycle boundary vertices.

22. The apparatus defined in claim 21, further comprising:

means for identifying a failed vertex that fails to be verified by said first and second verifying means;

means for identifying a polygon having said failed vertex as one of its vertices;

means for identifying a first diagonal of said polygon by which two vertices of said polygon are currently adjacent;

means for identifying a second diagonal of said polygon by which two other vertices of said polygon that are not currently adjacent can be made to be adjacent;

means for swapping said first diagonal with said second diagonal so that said two other vertices are adjacent.

23. The apparatus defined in claim 22, further comprising means for storing information relating to said first and second diagonals swapped by said swapping means.

24. The apparatus defined in claim 23, further comprising:

means for selecting certain of said progressive mesh modification records in accordance with a desired level of detail;

means for building said desired level of detail by modifying a current mesh having a corresponding current level of detail in accordance with said certain progressive mesh modification records and said base mesh to arrive at an interim mesh corresponding to said desired level of detail; and

means for adjusting said interim mesh in accordance with said stored information relating to said swapping step.

25. The apparatus defined in claim 19, further comprising:

means for selecting certain of said progressive mesh modification records in accordance with a desired level of detail; and

means for building said desired level of detail by modifying a current mesh having a corresponding current level of detail in accordance with said certain progressive mesh modification records and said base mesh to arrive at an interim mesh corresponding to said desired level of detail.

26. The apparatus defined in claim 25, wherein said progressive mesh modification records define refinement operations and decimation operations, said means for building including:

means for refining said current mesh in accordance with said refinement operations of said certain progressive mesh modification records to arrive at said corresponding interim mesh.

27. The apparatus defined in claim 25, wherein said progressive mesh modification records define refinement operations and decimation operations, said means for building including:

means for decimating said current mesh in accordance with said decimation operations of said certain progressive mesh modification records to arrive at said corresponding interim mesh.

28. The apparatus defined in claim 27, wherein said means for decimating includes means for collapsing a first cycle boundary vertex of said current mesh into a second cycle boundary vertex of said current mesh adjacent to said first cycle boundary vertex.

29. The apparatus defined in claim 27, wherein said means for decimating includes means for collapsing all cycle vertices of said current mesh that are adjacent to a first cycle boundary vertex of said current mesh into said first boundary cycle vertex.

30. The apparatus defined in claim 19, wherein said means for processing includes:

means for performing a decimation operation on said mesh to form a decimated mesh with a corresponding lower level of detail, said decimated mesh having a second complete cycle covering different than a first complete cycle covering of said mesh; and

means for generating a progressive mesh modification record including information about said decimation operation.

31. The apparatus defined in claim 30, wherein said decimation operation includes collapsing a first cycle boundary vertex of said mesh into a second cycle boundary vertex of said mesh adjacent to said first cycle boundary vertex.

32. The apparatus defined in claim 30, wherein said decimation operation includes collapsing all cycle vertices of said mesh that are adjacent to a first cycle boundary vertex of current mesh into said first boundary cycle vertex.

33. The apparatus defined in claim 19, wherein said means for processing includes:

means for generating a vertex list corresponding to said mesh;

means for remapping said vertex list in correspondence with an ordering of said progressive mesh modification records.

34. An apparatus for processing a mesh having a plurality of vertices, adjacent ones of said vertices sharing edges, said apparatus comprising:

a pre-processor that calculates a complete cycle covering of said mesh such that all said vertices belong to cycles, said pre-processor tagging each of said vertices as one of a cycle vertex and a cycle boundary vertex, each of said cycles consisting of one cycle vertex and a plurality of cycle boundary vertices.

35. The apparatus defined in claim 34, wherein said pre-processor calculates said complete cycle covering such that all vertices adjacent to each vertex tagged as said cycle vertex are tagged as cycle boundary vertices and such that a non-covering cycle formed by all vertices adjacent to each vertex tagged as said cycle boundary vertex is comprised of an alternating sequence of vertices tagged as cycle vertices and cycle boundary vertices.

36. The apparatus defined in claim 34, further comprising:

an encoder that generates a plurality of progressive mesh modification records, said progressive mesh modification records corresponding to interim meshes having corresponding levels of detail between a base mesh and a detailed mesh, said encoder being operative such that all vertices in said base mesh, said interim meshes and said detailed mesh belong to cycles.

37. A method comprising:

an offline generation process for generating a base mesh and a plurality of progressive mesh modification records, said base mesh comprised of topological adjacency information, said progressive mesh modification records respectively corresponding to a plurality of interim meshes each having a respective level of detail greater than that of said base mesh, said base mesh and said interim meshes comprising a plurality of vertices, adjacent ones of said vertices sharing edges, all of said vertices of said base mesh and said interim meshes belonging to complete cycles, each of said vertices being identified as one of a cycle vertex and a cycle boundary vertex, said complete cycles each comprising one said cycle vertex and a plurality of said cycle boundary vertices adjacent to said cycle vertex; and

a run-time evaluation process for rendering one of said base mesh and said plurality of interim meshes having a desired level of detail utilizing said topological adjacency information and certain of said progressive mesh modification records.