Bounding box and projections detection of hidden polygons in three-dimensional spatial databases

• US 5,574,835 A
• Filed: 11/02/1995
• Issued: 11/12/1996
• Est. Priority Date: 04/06/1993
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Silicon Engines Incorporated
• Inventors: Duluk, Jerome F. Jr., Kasle, David B.
• Primary Examiner(s): Herndon, Heather R.
• Assistant Examiner(s): Fetting, Anton W.
• Application Number:
  US08/552,212
• Time in Patent Office: 376 Days
• Field of Search: 395/119-121, 395/141-143, 395/134
• US Class Current: 345/421
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

An image is generated from a database of three-dimensional object data where each the objects is formed from at least one polygon having at least one edge. Successively determinations are made as to whether a particular one of the object polygons designated as the test polygon is not visible to an observer located at a predetermined location by virtue of being hidden by other objects in the database. If the test polygon is determined to be not visible, then it does not need to be rendered by an image renderer and may be discarded. The decision is made by successively selecting one of the three-dimensional object in the database. After an object is selected, each of the object polygon is selected to determining whether the polygon is occulted by another object. This determination is performed by determining the exterior region of the object as the union of bounding boxes of exterior polygons, determining the interior region of the object as the union of bounding boxes of interior polygons, and testing for overlap between the projected bounding box of the polygon and the projected bounding boxes of the exterior polygons and the projected bounding boxes of the interior polygons. The test polygon is determined to possible be visible or to be not visible based on overlaps between the projected bounding boxes of the test polygon, the interior polygons, the exterior polygons, and coordinate values. Polygons that are not visible are discarded while polygons that may be visible are retained.

Claims

1. A method for generating an image from a database including a plurality of three-dimensional objects, each said three-dimensional object comprising at least one polygon having at least one edge and allowing for each said object to have an unlimited number of said polygons and edges, and for successively determining whether a particular selected one of said at least one polygon designated a current test polygon is not visible to an observer located at a predetermined eyepoint coordinate location by virtue of being hidden by previously selected ones of said three-dimensional objects in said database designated as test objects and therefore said test polygon does not need to be rendered by a renderer;

said method comprising the steps of;

(A) selecting a particular one of said plurality of three-dimensional object as a current test object from among said plurality of three-dimensional objects in said database, said selecting being performed on said plurality of three-dimensional objects in arbitrary order without pre-sorting said three-dimensional geometry of objects according to a z coordinate distance from said predetermined eyepoint coordinate location prior to said selection;

(B) selecting, for each said selected particular three-dimensional current test object, each one of said polygons within said selected three-dimensional test object as said current test polygon;

(C) for each said selected current test polygon, determining whether said current test polygon is not visible to an observer located at a predetermined eyepoint coordinate location by virtue of being hidden by ones of said test objects that have been previously selected;

said step of determining whether said current test polygon is not visible to an observer including the steps of;

(1) determining the exterior region of said current test object as the union of bounding boxes of exterior polygons, where said exterior polygons are identified by successively comparing each edge in each polygon of said current test object with the edges in all other polygons of said same current test object and said comparisons identify either an edge shared with a back facing polygon or an edge that is not shared by any another polygon, wherein a polygon is a back facing polygon of said test object when said test object is topologically closed and when said polygon is located on a far side of said test object relative to said predetermined observer eyepoint coordinate location;

(2) determining the interior region of said test object as the union of bounding boxes of interior polygons, where a said interior polygon is identified by

being neither a said exterior polygon nor as a polygon having its projected bounding box overlap with a projected bounding box of a said exterior polygon, said overlap being the sharing of a common region between each of two projected bounding boxes, said common region including a one-dimensional edge and a two-dimensional area;

(3) testing for said overlap between the projected bounding box of said test polygon and the projected bounding boxes of said exterior polygons and the projected bounding boxes of said interior polygons;

(4) determining that said test polygon is not visible if;

(a) any of said overlaps occur between said projected bounding box of said test polygon and said bounding boxes of said interior polygons, and

(b) said overlaps do not occur between said projected bounding box of said test polygon and said bounding boxes of said exterior polygons, and

(c) for all said occurring overlaps between said projected bounding box of said test polygon and a said bounding box of a said interior polygon, the Z coordinate values of said bounding box of said test polygon are all farther from said predetermined eyepoint coordinate location of said observer than the Z coordinate values of the said bounding box of said interior polygon;

(5) discarding any of said test polygons that are determined to be not visible from said predetermined eyepoint location and rendering any of said test polygons that are not determined to be hidden by said test objects and may be visible and not hidden by said test objects; and

(6) retaining each said test polygon that may be visible and has not been discarded, and using each said retained polygon as a polygon of its corresponding three-dimensional object when said object is processed as a previously selected test object; and

(D) repeating steps (A) through (C) with each said three-dimensional object in said database as said current test object; and

(E) directing a display process to perform or omit displaying each said test polygon on a display device depending on whether each said test polygon is determined to be visible or hidden.

2. A method as in claim 1 where said test polygon is a compound polygon, said compound polygon comprised of a multiplicity of smaller polygons, the bounding box of said compound polygon being the bounding box around a union of bounding boxes of the said smaller polygons, and wherein all said smaller polygons for a particular one of said compound polygons are discarded if said compound polygon is determined to be hidden by a said test object.

3. A method as in claim 2, wherein said step of testing for said overlaps is performed in a content addressable memory, said content addressable memory comprising:

(1) means for storing a plurality of data words, each of said data words including a plurality of data subfields, each of said data subfields being divided into a plurality of data bits;

(2) means for providing an input field comprising a plurality of input subfields matching some of said data subfields, and each said input subfield divided into input bits so as to have a one-to-one bit correspondence to the said data bits in said data subfields in said words;

(3) query means for simultaneously comparing said plurality of input subfields to all said words, with simultaneous subfield comparisons such that each said data subfield is compared to its corresponding said input subfield, and generation of a one bit query result for each said word which is true when all said data subfields within said word which are compared to one of said input subfields compare favorably to each corresponding said input subfield; and

(4) flag memory means for storing a flag bit equal to said query result for each of said words.

4. A method as in claim 1 where said step of testing for said overlaps is performed in a content addressable memory, said content addressable memory comprising:

(1) means for storing a plurality of data words, each of said data words including a plurality of data subfields, each of said data subfields being divided into a plurality of data bits;

(2) means for providing an input field comprising a plurality of input subfields matching some of said data subfields, and each said input subfield divided into input bits so as to have a one-to-one bit correspondence to the said data bits in said data subfields in said words;

(3) query means for simultaneously comparing said plurality of input subfields to all said words, with simultaneous subfield comparisons such that each said data subfield is compared to its corresponding said input subfield, and generation of a one bit query result for each said word which is true when all said data subfields within said word which are compared to one of said input subfields compare favorably to each corresponding said input subfield; and

(4) flag memory means for storing a flag bit equal to said query result for each of said words.

5. The method in claim 1, wherein said step of determining the interior region of said test object as the union of bounding boxes of interior polygons, where a said interior polygon is identified by being neither a said exterior polygon nor as a polygon having its projected bounding box overlap with more than one projected bounding box of a said exterior polygon, said overlap being the sharing of a common region between each of two projected bounding boxes, said common region including a one-dimensional edge and a two-dimensional area.

6. A method for generating an image from a database including a plurality of three-dimensional objects, each said three-dimensional object comprising at least one polygon having at least one edge and allowing for each said object to have an unlimited number of said polygons and edges, and for successively determining whether a particular selected one of said at least one polygon designated a current test polygon is not visible to an observer located at a predetermined eyepoint coordinate location by virtue of being hidden by previously selected ones of said three-dimensional objects in said database designated as test objects and therefore said test polygon does not need to be rendered by a renderer;

said method comprising the steps of;

(A) selecting a particular one of said plurality of three-dimensional object as a current test object from among said plurality of three-dimensional objects in said database, said selecting being performed on said plurality of three-dimensional objects in arbitrary order without pre-sorting said three-dimensional geometry of objects according to a z coordinate distance from said predetermined eyepoint coordinate location prior to said selection;

(B) selecting, for each said selected particular three-dimensional current test object, each one of said polygons within said selected three-dimensional test object as said current test polygon;

(C) for each said selected current test polygon, determining whether said current test polygon is not visible to an observer located at a predetermined eyepoint coordinate location by virtue of being hidden by ones of said test objects that have been previously selected;

said step of determining whether said current test polygon is not visible to an observer including the steps of;

(1) determining the exterior region of said current test object as the union of bounding boxes of exterior edges, where said exterior edges are polygon edges identified by successively comparing each edge in each polygon of said current test object with the edges in all other polygons of said same current test object and said comparisons identify either an edge shared by a front facing polygon and a back facing polygon or an edge that is not shared by any another polygon, wherein a polygon is a back facing polygon of said test object when said test object is topologically closed and when said polygon is located on a far side of said test object relative to said predetermined observer eyepoint coordinate location, and wherein a polygon is a front facing polygon of said test object when said test object is topologically closed and when said polygon is located on a near side of said test object relative to said predetermined observer eyepoint coordinate location;

(2) determining the interior region of said test object as the union of bounding boxes of interior edges, where a said interior edge is identified by

being neither a said exterior edge nor as an edge having its projected bounding box overlap with a projected bounding box of a said exterior edge, said overlap being the sharing of a common region between each of two projected bounding boxes, said common region including a one-dimensional edge and a two-dimensional area;

(3) testing for said overlap between the projected bounding boxes of the edges of said test polygon and the projected bounding boxes of said exterior edges and the projected bounding boxes of said interior edges;

(4) determining that said test polygon is not visible if;

(a) any of said overlaps occur between said projected bounding box of the edges of said test polygon and said bounding boxes of said interior edges, and

(b) said overlaps do not occur between said projected bounding boxes of the edges of said test polygon and said bounding boxes of said exterior edges, and

(c) for all said occurring overlaps between said projected bounding box of an edge of said test polygon and a said projected bounding box of a said interior edge, the Z coordinate values of said bounding box of an edge of said test polygon are all farther from said predetermined eyepoint coordinate location of said observer than the Z coordinate values of said projected bounding box of said interior edge;

(5) discarding any of said test polygons that are determined to be not visible from said predetermined eyepoint location and rendering any of said test polygons that are not determined to be hidden by said test objects and may be visible and not hidden by said test objects; and

(6) retaining each said test polygon that may be visible and has not been discarded, and using each said retained polygon as a polygon of its corresponding three-dimensional object when said object is processed as a previously selected test object; and

(D) repeating steps (A) through (C) with each said three-dimensional object in said database as said current test object; and

(E) directing a display process to perform or omit displaying said test polygon on a display device depending on whether said test polygon is determined to be visible or hidden.

7. A method as in claim 6 where said step of testing for overlaps is performed in a content addressable memory, said content addressable memory including:

(1) means for storing a plurality of data words, each of said data words including a plurality of data subfields, each of said data subfields being divided into a plurality of data bits;

(2) means for providing an input field comprising a plurality of input subfields matching some of said data subfields, and each said input subfield divided into input bits so as to have a one-to-one bit correspondence to the said data bits in said data subfields in said words;

(3) query means for simultaneously comparing said plurality of input subfields to all said words, with simultaneous subfield comparisons such that each said data subfield is compared to its corresponding said input subfield, and generation of a one bit query result for each said word which is true when all said data subfields within said word which are compared to one of said input subfields compare favorably to each corresponding said input subfield; and

(4) flag memory means for storing a flag bit equal to said query result for each of said words.

8. The method in claim 6, wherein said step of determining the interior region of said test object as the union of bounding boxes of interior edges, where a said interior edge is identified by being neither as a said exterior edge nor as an edge having its projected bounding box overlap with more than one projected bounding box of a said exterior edge, said overlap being the sharing of a common region between each of two projected bounding boxes, said common region including a one-dimensional edge and a two-dimensional area.

9. A method for generating an image from a database including a plurality of three-dimensional objects, each said three-dimensional object comprising at least one polygon having at least one edge and allowing for each said object to have an unlimited number of said polygons and edges, and for successively determining whether a particular selected one of said at least one compound polygon comprised of a multiplicity of smaller polygons and designated a current test polygon is not visible to an observer located at a predetermined eyepoint coordinate location by virtue of being hidden by previously selected ones of said three-dimensional objects in said database designated as test objects and therefore said test polygon does not need to be rendered by a renderer, said method comprising the steps of:

(A) selecting a particular one of said plurality of three-dimensional object as a current test object from among said plurality of three-dimensional objects in said database, said selecting being performed on said plurality of three-dimensional objects in arbitrary order without pre-sorting said three-dimensional geometry of objects according to a z coordinate distance from said predetermined eyepoint coordinate location prior to said selection;

(B) selecting, for each said selected particular three-dimensional current test object, each one of said polygons within said selected three-dimensional test object as said current test polygon;

(C) for each said selected current test polygon, determining whether said current test polygon is not visible to an observer located at a predetermined eyepoint coordinate location by virtue of being hidden by ones of said test objects that have been previously selected;

said step of determining whether said current test polygon is not visible to an observer including the steps of;

(1) determining the exterior region of said current test object as the union of bounding boxes of exterior polygons, the bounding box of said compound polygon being the bounding box around a union of bounding boxes of the said smaller polygons, where said exterior polygons are identified by successively comparing each edge in each polygon of said current test object with the edges in all other polygons of said same current test object and said comparisons identify either an edge shared with a back facing polygon or an edge that is not shared by any another polygon, wherein a polygon is a back facing polygon of said test object when said test object is topologically closed and when said polygon is located on a far side of said test object relative to said predetermined observer eyepoint coordinate location;

(2) determining the interior region of said test object as the union of bounding boxes of interior polygons, where a said interior polygon is identified by being neither a said exterior polygon nor as a polygon having its projected bounding box overlap with a projected bounding box of a said exterior polygon, said overlap being the sharing of a common region between each of two projected bounding boxes, said common region including a one-dimensional edge and a two-dimensional area;

(3) testing for said overlap between the projected bounding box of said test polygon and the projected bounding boxes of said exterior polygons and the projected bounding boxes of said interior polygons;

said testing for said overlap including the steps of;

(a) storing a plurality of data words in a data structure, each of said data words including a plurality of data subfields, each of said data subfields being divided into a plurality of data bits;

(b) providing an input field comprising a plurality of input subfields matching some of said data subfields, and each said input subfield divided into input bits so as to have a one-to-one bit correspondence to the said data bits in said data subfields in said words;

(c) simultaneously comparing said plurality of input subfields to all said words, with simultaneous subfield comparisons such that each said data subfield is compared to its corresponding said input subfield, and generation of a one bit query result for each said word which is true when all said data subfields within said word which are compared to one of said input subfields compare favorably to each corresponding said input subfield; and

(d) storing a flag bit equal to said query result for each of said words; and

(4) determining that said test polygon is not visible if;

(a) any of said overlaps occur between said projected bounding box of said test polygon and said bounding boxes of said interior polygons, and

(b) said overlaps do not occur between said projected bounding box of said test polygon and said bounding boxes of said exterior polygons, and

(c) for all said occurring overlaps between said projected bounding box of said test polygon and a said bounding box of a said interior polygon, the z-coordinate values of said bounding box of said test polygon are all farther from said predetermined eyepoint coordinate location of said observer than the z-coordinate values of the said bounding box of said interior polygon;

(5) discarding any of said test polygons including all said smaller polygons associated with a particular one of said compound polygons that are determined to be not visible from said predetermined eyepoint location and rendering any of said test polygons that are not determined to be hidden by said test objects and may be visible and not hidden by said test objects; and

(6) retaining each said test polygon that may be visible and has not been discarded, and using each said retained polygon as a polygon of its corresponding three-dimensional object when said object is processed as a previously selected test object; and

(D) repeating steps (A) through (C) with each said three-dimensional object in said database as said current test object; and

(E) directing a display process to perform or omit displaying each said test polygon on a display device depending on whether each said test polygon is determined to be visible or hidden.