What's better? - Game Engine

If you want to contribute to the forum discussions, please Register or Login.

Search Home

10/11/2011 2:25 AM

winterkewl

Joined: 12/8/2010

Posts: 32

What's better?

A composite shape made up of 1000+ box shapes, or a triangle mesh shape made up of 6000+ verts?

Or, even better, what would be the best way to do a broadphase check of said 1000+ boxShapes to return the closest 64 or so to a given boundingSphere?

I don't need specific contact points, just the positions of the closest 64 boxes in a soup of thousands. I was trying to adapt the frustrum culling example and also implement my own Octree that would have BoxShapes as it's leaf nodes but I'm failing miserably.

Any advice is most welcome!

10/11/2011 2:58 PM

HelmutG

www.digitalrune.com
Joined: 10/15/2006

Posts: 567

Re: What's better?

winterkewl wrote:

A composite shape made up of 1000+ box shapes, or a triangle mesh shape made up of 6000+ verts?

I don't know. I would use a profiler to find out.

winterkewl wrote:

Or, even better, what would be the best way to do a broadphase check of said 1000+ boxShapes to return the closest 64 or so to a given boundingSphere?

That sounds like the k-nearest neighbor problem. I think it is usually solved using a k-D tree. See http://en.wikipedia.org/wiki/K-d_tree. There is a section about nearest neighbor search. Nearest neighbor search finds the closest object. To find the k closest objects you have to extend this algorithm to keep track of the k nearest objects in a priority queue while traversing the tree.

I guess it is shouldn't be hard to find a k-D tree implementation on the interwebs.Check out http://robowiki.net/wiki/Kd-tree or http://home.wlu.edu/~levys/software/kd/ for example.

10/12/2011 11:08 PM

winterkewl

Joined: 12/8/2010

Posts: 32

Re: What's better?

Sorry I didn't respond sooner, just wanted to say THANK YOU very much for the tip on KD trees that was exactly what I needed to use for my situation. :)

Page 1 of 1

DigitalRune is a trademark of Garstenauer Information Technology OG.

Garstenauer Information Technology OG
Weingartenstrasse 35, 4452 Ternberg
Austria (EUROPE)
office@digitalrune.com

Products			Buy	Support	About Us
Game Engine	Particles	Windows Forms	Professional	Blog	Services
Base	Animation	Docking Windows	Indie	Forum	Contact Us
Mathematics	Graphics	Text Editor Control	Non-Commercial	License FAQ	Press (News)
Geometry	Game			Documentation	Legal Terms
Physics	Game UI				Imprint
					Impressum