WO1996013811B1 - Method for creating spatially balanced bounding volume hierarchies for use in a computer generated display of a complex structure - Google Patents
Method for creating spatially balanced bounding volume hierarchies for use in a computer generated display of a complex structureInfo
- Publication number
- WO1996013811B1 WO1996013811B1 PCT/EP1995/004252 EP9504252W WO9613811B1 WO 1996013811 B1 WO1996013811 B1 WO 1996013811B1 EP 9504252 W EP9504252 W EP 9504252W WO 9613811 B1 WO9613811 B1 WO 9613811B1
- Authority
- WO
- WIPO (PCT)
- Prior art keywords
- volumes
- bounding
- volume
- objects
- sub
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Ceased
Links
Abstract
Disclosed is a method for processing an arbitrary collection of objects, forming a complex structure, into a hierarchy of bounding volumes, from a root volume bounding all objects, to sub-volumes bounding individual objects or assemblies thereof, for use as successive approximations to said objects in a computer generated display. The method includes the first step of creating a bounding volume for each of the objects. Selected bounding volumes are then processed through a combining algorithm determining whether or not, based upon a geometric relationship between the bounding volumes and the higher level, root volume, the selected bounding volumes can be combined. If it is determined that the bounding volumes can be combined, a new bounding volume is created with the combined volumes comprising sub-volumes thereof. This process systematically repeats and attempts to combine all sub-volumes. The combining algorithm preferably allows a combination if the volumes of the combination of the sub-volume is smaller than a fixed percentage of the parent volume. When a pair can combine, it is replaced by a box bounding volume that contains the pair as sub-volumes, and the process continues. In this way, a bounding volume hierarchy for all objects and assemblies within a complex structure is created.
Claims
AMENDED CLAIMS
[received by the International Bureau on 24 April 1996 (24.04.96); original claims unchanged; new claim 44 added (1 page)]
44. A method for processing an arbitrary collection of objects, represented by computer generated images therof, into a hieraehy of bounding volumes, form a root volume bounding all objects, to sub-volumes bounding individual objects or assemblies thereof, for use as succesive approximations to said objects,
comprising the steps of:
(a) creating bounding volumes for said objects:
(b) proceβsing selected bounding volumes through a predetermined combining algorithm to determine whether or not, based upon a geometric relationship between said bounding volumes and the root volume, the selected bounding volumes can be combined into a new volume representative of said selected bounding volumes, and with respect to those bounding volumes which can be combined:
(c) creating a new bounding volume with said combined bounding volumes comprising sub-volumes thereof,
(d) recursively applying new steps b) and c) to said new bounding volume and treating the new bounding volume as the root volume and its combined volumes as the selected volumes.
(e) utilizing said new bounding volume as an approximation of the image of said sub-volumes in a computer generated display.
Priority Applications (5)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CA002203253A CA2203253C (en) | 1994-10-26 | 1995-10-26 | Method for creating spatially balanced bounding volume hierarchies for use in a computer generated display of a complex structure |
| JP51432096A JP3721419B2 (en) | 1994-10-26 | 1995-10-26 | Method for creating a spatially balanced boundary volume hierarchy for use in composite-structured computer-generated displays |
| AU39265/95A AU3926595A (en) | 1994-10-26 | 1995-10-26 | Method for creating spatially balanced bounding volume hierarchies for use in a computer generated display of a complex structure |
| DE69512262T DE69512262T2 (en) | 1994-10-26 | 1995-10-26 | METHOD FOR PRODUCING SPATIALLY BALANCED VOLUME HIERARCHIES FOR USE IN A COMPUTER-GENERATED REPRESENTATION OF A COMPLEX STRUCTURE |
| EP95937033A EP0789895B1 (en) | 1994-10-26 | 1995-10-26 | Method for creating spatially balanced bounding volume hierarchies for use in a computer generated display of a complex structure |
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/329,356 US5613049A (en) | 1994-10-26 | 1994-10-26 | Method for creating spatially balanced bounding volume hierarchies for use in a computer generated display of a complex structure |
| US08/329,356 | 1994-10-26 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| WO1996013811A1 WO1996013811A1 (en) | 1996-05-09 |
| WO1996013811B1 true WO1996013811B1 (en) | 1996-06-20 |
Family
ID=23285011
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| PCT/EP1995/004252 Ceased WO1996013811A1 (en) | 1994-10-26 | 1995-10-26 | Method for creating spatially balanced bounding volume hierarchies for use in a computer generated display of a complex structure |
Country Status (7)
| Country | Link |
|---|---|
| US (1) | US5613049A (en) |
| EP (1) | EP0789895B1 (en) |
| JP (1) | JP3721419B2 (en) |
| AU (1) | AU3926595A (en) |
| CA (1) | CA2203253C (en) |
| DE (1) | DE69512262T2 (en) |
| WO (1) | WO1996013811A1 (en) |
Families Citing this family (22)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3603285B2 (en) * | 1994-07-21 | 2004-12-22 | 株式会社セガ | Image processing device |
| JP3347508B2 (en) * | 1995-02-24 | 2002-11-20 | キヤノン株式会社 | Captured image processing device and captured image processing method |
| JP2981516B2 (en) * | 1995-03-10 | 1999-11-22 | 富士通株式会社 | 3D shape editing device |
| US5999187A (en) * | 1996-06-28 | 1999-12-07 | Resolution Technologies, Inc. | Fly-through computer aided design method and apparatus |
| IL119082A (en) * | 1996-08-16 | 2001-04-30 | Virtue Ltd | Method for creating graphic images |
| US6108006A (en) * | 1997-04-03 | 2000-08-22 | Microsoft Corporation | Method and system for view-dependent refinement of progressive meshes |
| US6407748B1 (en) * | 1998-04-17 | 2002-06-18 | Sandia Corporation | Method and apparatus for modeling interactions |
| SG80633A1 (en) * | 1998-07-18 | 2001-05-22 | Univ Singapore | System and method for creating bounding volume hierarchies utilizing model simplification |
| US6747651B1 (en) | 1998-07-18 | 2004-06-08 | National University Of Singapore | System and method for creating bounding volume hierarchies utilizing model simplification |
| DE59907018D1 (en) * | 1999-07-01 | 2003-10-23 | Teraport Gmbh | Method and system for the virtual creation of a product consisting of several components |
| GB9925947D0 (en) * | 1999-11-02 | 1999-12-29 | Elixir Studios Limited | Improvements relating to image processing |
| AU1158001A (en) * | 1999-11-02 | 2001-05-14 | Elixir Studios Limited | Improvements relating to computer graphics |
| DE19959617A1 (en) * | 1999-12-10 | 2001-06-21 | Volkswagen Ag | Construction system and method for designing or designing new components |
| US20040217966A1 (en) * | 2003-04-30 | 2004-11-04 | Lefebvre Kevin T. | Method for creating enhanced performance OpenGL display lists |
| KR100718157B1 (en) * | 2006-03-08 | 2007-05-14 | 삼성전자주식회사 | Collision Detection Device and Method |
| US8139060B2 (en) * | 2006-11-28 | 2012-03-20 | International Business Machines Corporation | Ray tracing image processing system |
| US8749552B2 (en) | 2008-10-17 | 2014-06-10 | Imagination Technologies Limited | Synthetic acceleration shapes for use in ray tracing |
| EP2261827B1 (en) * | 2009-06-10 | 2015-04-08 | Dassault Systèmes | Process, program and apparatus for displaying an assembly of objects of a PLM database |
| CN103765481B (en) | 2011-08-05 | 2016-06-29 | 想象技术有限公司 | Systems and methods for accelerated structure creation and updating of 3-D scenes |
| CN105874511B (en) * | 2013-12-18 | 2019-04-05 | 索尼互动娱乐股份有限公司 | Analog machine |
| CN109887093A (en) * | 2019-01-17 | 2019-06-14 | 珠海金山网络游戏科技有限公司 | A kind of game level of detail processing method and system |
| EP4083933A1 (en) * | 2021-04-30 | 2022-11-02 | Inter IKEA Systems B.V. | Method, device and computer program product for manipulating virtual bounding volumes |
Family Cites Families (15)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| NL8300872A (en) * | 1983-03-10 | 1984-10-01 | Philips Nv | MULTIPROCESSOR CALCULATOR SYSTEM FOR PROCESSING A COLORED IMAGE OF OBJECT ELEMENTS DEFINED IN A HIERARCHICAL DATA STRUCTURE. |
| US4901252A (en) * | 1984-07-13 | 1990-02-13 | International Business Machines Corporation | Method for producing planar geometric projection images |
| US4862392A (en) * | 1986-03-07 | 1989-08-29 | Star Technologies, Inc. | Geometry processor for graphics display system |
| US4967375A (en) * | 1986-03-17 | 1990-10-30 | Star Technologies, Inc. | Fast architecture for graphics processor |
| JP2659372B2 (en) * | 1987-07-20 | 1997-09-30 | ファナック株式会社 | 3D display method for structures |
| US4922430A (en) * | 1987-10-30 | 1990-05-01 | U.S. Philips Corporation | Method and apparatus for controlling the movement of a guided object |
| US4912659A (en) * | 1987-10-30 | 1990-03-27 | International Business Machines Corporation | Parallel surface processing system for graphics display |
| US5088054A (en) * | 1988-05-09 | 1992-02-11 | Paris Ii Earl A | Computer graphics hidden surface removal system |
| GB8828342D0 (en) * | 1988-12-05 | 1989-01-05 | Rediffusion Simulation Ltd | Image generator |
| US5144685A (en) * | 1989-03-31 | 1992-09-01 | Honeywell Inc. | Landmark recognition for autonomous mobile robots |
| EP0436790A3 (en) * | 1989-11-08 | 1992-12-30 | International Business Machines Corporation | Multi-dimensional tree structure for the spatial sorting of geometric objects |
| US5048095A (en) * | 1990-03-30 | 1991-09-10 | Honeywell Inc. | Adaptive image segmentation system |
| US5448686A (en) * | 1992-01-02 | 1995-09-05 | International Business Machines Corporation | Multi-resolution graphic representation employing at least one simplified model for interactive visualization applications |
| US5442733A (en) * | 1992-03-20 | 1995-08-15 | The Research Foundation Of State University Of New York | Method and apparatus for generating realistic images using a discrete representation |
| CA2148231C (en) * | 1993-01-29 | 1999-01-12 | Michael Haysom Bianchi | Automatic tracking camera control system |
-
1994
- 1994-10-26 US US08/329,356 patent/US5613049A/en not_active Expired - Lifetime
-
1995
- 1995-10-26 CA CA002203253A patent/CA2203253C/en not_active Expired - Lifetime
- 1995-10-26 AU AU39265/95A patent/AU3926595A/en not_active Abandoned
- 1995-10-26 DE DE69512262T patent/DE69512262T2/en not_active Expired - Lifetime
- 1995-10-26 EP EP95937033A patent/EP0789895B1/en not_active Expired - Lifetime
- 1995-10-26 JP JP51432096A patent/JP3721419B2/en not_active Expired - Lifetime
- 1995-10-26 WO PCT/EP1995/004252 patent/WO1996013811A1/en not_active Ceased
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| WO1996013811B1 (en) | Method for creating spatially balanced bounding volume hierarchies for use in a computer generated display of a complex structure | |
| CA2203253A1 (en) | Method for creating spatially balanced bounding volume hierarchies for use in a computer generated display of a complex structure | |
| Simard et al. | A catalog of bulge+ disk decompositions and updated photometry for 1.12 million galaxies in the sloan digital sky survey | |
| Prewitt | Object enhancement and extraction | |
| EP1182597A3 (en) | Electronic sourcing system | |
| US20060165178A1 (en) | Generating a Motion Attention Model | |
| CA2315729A1 (en) | Method for analyzing capacity of parallel processing systems | |
| EP1184798A3 (en) | System , method and computer program product for patent-centric and group-oriented data processing | |
| CA2352295A1 (en) | A method and a system for assisting a user in a medical self treatment, said self treatment comprising a plurality of actions | |
| EP0920221A3 (en) | Image processing apparatus and method | |
| EP0854441A3 (en) | Method and apparatus for rapidly rendering computer generated images of complex structures | |
| EP0727737A3 (en) | Addressing method for executing load instructions out of order with respect to store instructions | |
| Tari et al. | Local symmetries of shapes in arbitrary dimension | |
| CN113468920B (en) | Living body detection method, system, equipment and medium based on human face facula image | |
| Canus et al. | Change detection in sequences of images by multifractal analysis | |
| EP0789324A3 (en) | Image resizing in a parallel processor | |
| Sharma | Various types of image noise and de-noising algorithm | |
| Csapodi et al. | Dynamic analogic CNN algorithms for a complex recognition task—a first step towards a bionic eyeglass | |
| US8098945B2 (en) | Method and system for binarizing an image | |
| US11989858B2 (en) | Systems and methods of determining margins of an image for content insertion to form a composite image | |
| Schlei et al. | Geometric morphology of granular materials | |
| Huang et al. | An efficient strategy for implementing iterative area openings using the max tree | |
| Lee et al. | Dynamic range compression and contrast enhancement for digital images in the compressed domain | |
| Grossberg et al. | A multiple scale neural system for boundary and surface representation of SAR data | |
| Chunling | A Linear Quadtree Method for Intersection Detection Between 2 D Objects |