Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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. , p. 27
Keywords [en]
Collision, Octree, Pixel Area, Level-of-Detail, LoD
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:bth-12751OAI: oai:DiVA.org:bth-12751DiVA, id: diva2:944652
Subject / course
DV1478 Bachelor Thesis in Computer Science
Educational program
DVGSP Game Programming
Supervisors
Examiners
Available from: 2016-07-04 Created: 2016-06-29 Last updated: 2018-01-10Bibliographically approved

Open Access in DiVA

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

By organisation
Department of Creative Technologies
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 1253 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

urn-nbn

Altmetric score

urn-nbn
Total: 602 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf