Method for the 3D display of octree-encoded objects and device for the application of this method

• US 5,123,084 A
• Filed: 12/21/1990
• Issued: 06/16/1992
• Est. Priority Date: 12/24/1987
• Status: Expired due to Term

• Current Assignee: General Electric CGR SA (General Electric Company), Octree Corporation
• Original Assignee: General Electric CGR SA (General Electric Company), Octree Corporation
• Inventors: Edwards, Bruce, Milon, Daniel, Delcroix, Michel, Meagher, Donald, Prevost, Guy, Lis, Olivier
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): JAFFE, MICHAEL
• Application Number:
  US07/630,782
• Time in Patent Office: 543 Days
• Field of Search: 364/518, 364/521, 364/522, 340/729, 340/747
• US Class Current: 345/420
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree

Abstract

The 3D display device of the invention is based on an octree structure of data pertaining to an object to be displayed. This structure is memorized in a memory associated with a cache memory sending blocks of data on a bus to which a geometrical processor and an image-generating circuit are connected. The geometrical processor generates the visible part of another octree corresponding to a target universe which may be positioned in any way in relation to the object universe (a cube enclosing all the data to be represented).

Claims

1. A method for 3D display onto a screen of a digitally encoded object in octree form, comprising the steps of:

building, for each point of said object, at each level of its octree, an overlay by selecting for each such point an "obel" and seven adjoining obels for forming a cube called "overlay",

digitizing the coordinates of each point of said object,

establishing a correspondence between the digitized coordinates of each point of said object and the address in the overlay, by selecting the two most significant bits of each of said coordinates which provide an obel number and a node number in said obel containing each said point,

selecting a child overlay among all possible child overlays of a parent overlay by choosing the one child overlay whose center is the nearest to a corresponding child obel center, and so on for all other octree levels,

building a target universe such as the plane formed by its aces Ox, Oy, said target universe being parallel to said display screen, and said target universe being a zero level obel of a target octree to be generated and corresponding to a chosen single angle,

dividing said zero level obel by two along each coordinate axis to obtain 8 son obels, dividing in the same way each son obel, and so on down to a desired resolution, thus achieving the building of a target octree,

projecting obels of said target universe onto the display screen for forming "imels" of a 3D image, giving priority so that only information relating to the visible part of said object is to be displayed whereby the obels which are closest to said display screen and, when those examined obels are empty, the obels behind them in distance away from said display screen are examined so that priority is given to the obels closest to the display screen if they are not empty.

2. A method according to claim 1 wherein, from a target screen, a target octree is defined which is projected canonically in an image quadtree on a display screen, a correspondence between numbers of said obels of the target octree and imel numbers of the image quadtree, wherein said imel refers to image elements on the screen corresponding to the obels, being constant and independent of an angle of view and of a level of the target octree.