Several computer graphics algorithms (such as ray-tracing) heavily relate their performances to the efficiency of the tests of intersection between the rays of a light source and the objects of a synthetic scene. Some solid modelling and robotics algorithms need also to test quickly the possible interferences of the different parts of a system such as the arms of different robots. To speed-up the test, the free shape objects to be tested are encapsulated into boxes and the test starts by performing a check on overlapping of the bounding boxes, thus producing a section of the space where an intersection can occur. Successively, if the boxes overlap, the test continues on the original free shape objects, but only in the portion of the 3D-space resulting from the first step. The authors present a simple, fast and efficient algorithm (called the `bounding boxes group' method) to compute a tight bounding entity of a complex object modelled in the constructive solid geometry (CSG). If no upper limit is set to the number of elements of each bounding box group, the algorithm is shown to achieve the tightest possible solution. Algorithms are also presented which allow a reduction of the number of bounding elements but still provide a satisfactory and tight encapsulation

Spatial Bounding of Complex CSG Objects / Sanna, Andrea; Montuschi, Paolo. - In: IEE PROCEEDINGS. COMPUTERS AND DIGITAL TECHNIQUES. - ISSN 1350-2387. - STAMPA. - 142:6(1995), pp. 431-439. [10.1049/ip-cdt:19952077]

Spatial Bounding of Complex CSG Objects

SANNA, Andrea;MONTUSCHI, PAOLO
1995

Abstract

Several computer graphics algorithms (such as ray-tracing) heavily relate their performances to the efficiency of the tests of intersection between the rays of a light source and the objects of a synthetic scene. Some solid modelling and robotics algorithms need also to test quickly the possible interferences of the different parts of a system such as the arms of different robots. To speed-up the test, the free shape objects to be tested are encapsulated into boxes and the test starts by performing a check on overlapping of the bounding boxes, thus producing a section of the space where an intersection can occur. Successively, if the boxes overlap, the test continues on the original free shape objects, but only in the portion of the 3D-space resulting from the first step. The authors present a simple, fast and efficient algorithm (called the `bounding boxes group' method) to compute a tight bounding entity of a complex object modelled in the constructive solid geometry (CSG). If no upper limit is set to the number of elements of each bounding box group, the algorithm is shown to achieve the tightest possible solution. Algorithms are also presented which allow a reduction of the number of bounding elements but still provide a satisfactory and tight encapsulation
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/1402780
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo