Change search
ReferencesLink to record
Permanent link

Direct link
View-Dependent Collision Detection and Response Using Octrees
Blekinge Institute of Technology, Faculty of Computing, Department of Creative Technologies.
2016 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Context. Collision is a basic necessity in most simulated environments, especially video games, which demand user interaction. Octrees are a way to divide the simulated environments into smaller, more manageable parts,and is a hierarchical tree-structure, where each node has eight children. Octrees and similar tree-structural methods have been used frequently to optimize collision calculations and partition the objects in the 3D space.

Objectives. The aim of this thesis is to find a way to further improve upon the octree structure, by using a two-level octree structure, and simplify the collision of objects that do not demand much complexity, due to their size or the geometric simplicity of their 3D models, this is done by calculating how many pixels the objects occupy on the screen, and use that as a factor when deciding the depth of their individual octrees.

Methods. Each object in the 3D environment is divided using an octree. These octrees generated for the objects are then placed in a larger octree. This large octree use the smaller ones to check collision between the objects. The pixel area occupied on the screen by the objects’ octrees is used to determine what depth of the octrees will be check for intersection. Two test scenes were set up to test our model.

Results. Our implementation could effectively reduce the depth of octrees belonging to objects occupying little space on the screen. The experiments also showed that the reduced depth could be used with only a slight loss in accuracy. The accuracy loss increased when more objects were used.

Conclusions. The results gained in the thesis show that the pixel area can be used effectively, and the simplified octrees can still represent the objects adequately, resulting in a cheaper but slightly less accurate collision.

Place, publisher, year, edition, pages
2016. , 27 p.
Keyword [en]
Collision, Octree, Pixel Area, Level-of-Detail, LoD
National Category
Computer Science
URN: urn:nbn:se:bth-12751OAI: diva2:944652
Subject / course
DV1478 Bachelor Thesis in Computer Science
Educational program
DVGSP Game Programming
Available from: 2016-07-04 Created: 2016-06-29 Last updated: 2016-07-04Bibliographically approved

Open Access in DiVA

fulltext(984 kB)17 downloads
File information
File name FULLTEXT02.pdfFile size 984 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Department of Creative Technologies
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 17 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 65 hits
ReferencesLink to record
Permanent link

Direct link