Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (540)
Games in Android Showcase (133)
games submitted by our members
Games in WIP (603)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Rotating AABB (algorithm question)  (Read 2670 times)
0 Members and 1 Guest are viewing this topic.
Offline cep21

Junior Devvie




Java games rock!


« Posted 2004-08-04 14:53:24 »

AABB = Axis Aligned Bounding Box

I have a model.  I suround it by an AABB.  The model may need to rotate.  Rather than recompute the AABB (which would be slow), I'ld rather rotate the AABB with the model.  My absolute rotation comes to me as a Quaternion.  Here is my working algorithm.  Is there a faster way?

My AABB is defined by a center and 3 extent variables (X extent Y extent Z extent).  My AABB keeps track of its original center and original extents, but has a "using" center and "using" extent which it uses for culling purposes.  They start off equal.

1) Convert Quaternion to a 3x3 rotation matrix
2) Rotate the original center by this 3x3 rotation matrix.  This is now my new "using" center.
3) Make every value in the 3x3 matrix it's absolute value (IE if a value is -32 it becomes 32)
4) Multiply this 3x3 matrix by my "original" X,Y,Z extent of the bounding box.  This is now my new X/Y/Z extent.


This algorithm works correctly.  I'm wondering if there is a faster way.
Offline oNyx

JGO Coder


Medals: 2


pixels! :x


« Reply #1 - Posted 2004-08-04 15:01:41 »

Usually you don't rotate em... they are axis aligned Wink

And to tell the truth - usually it's good enough (it was good enough for Quake3 for example). If you're standing diagonally to your opponent on the grid the hitable area is ~40% bigger than usual (a factor of sqrt(2)), but - as I already said - it doesn't really matter.

If it's not accurate enough you could check for AABB intersection first and in case of a collision you could perform a more accurate check.

弾幕 ☆ @mahonnaiseblog
Offline cep21

Junior Devvie




Java games rock!


« Reply #2 - Posted 2004-08-04 15:26:25 »

But the box around the person or object needs to change if the person rotates.  Otherwise they could move outside the box.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline oNyx

JGO Coder


Medals: 2


pixels! :x


« Reply #3 - Posted 2004-08-04 15:32:02 »

Make the box bigger.

Take a look at these screenshots:
http://www.planetquake.com/alternatefire/unlagged_faq.html#IJRAMBIHOIJRAHBIM

弾幕 ☆ @mahonnaiseblog
Offline cep21

Junior Devvie




Java games rock!


« Reply #4 - Posted 2004-08-04 15:56:57 »

Correct.  My question is how do I quickly figure out how much bigger to make the box.
Offline oNyx

JGO Coder


Medals: 2


pixels! :x


« Reply #5 - Posted 2004-08-04 16:12:41 »

From the rotation centre the longest distance... then you have s sphere where you can wrap a cube around.

If you only rotate about one axis you could also do the same for a cylinder where you wrap a box around.

And if you don't do any more accurate collision detection you can also just do the box with trial'n'error/rule of thumb until it feels right.

弾幕 ☆ @mahonnaiseblog
Offline cep21

Junior Devvie




Java games rock!


« Reply #6 - Posted 2004-08-04 16:24:21 »

"From the rotation centre the longest distance"

Do you mean the longest distance to any point in the model?  That's something along the lines of O(n).  What I suggested above is O(1).  I was wondering if my constant running time could be shorter.
Offline oNyx

JGO Coder


Medals: 2


pixels! :x


« Reply #7 - Posted 2004-08-04 17:17:45 »

>That's something along the lines of O(n).

Who cares? It's a one time/offline operation. It's like thinking too much about the rendering time of pre rendered graphics Wink

弾幕 ☆ @mahonnaiseblog
Offline nonnus29

Senior Devvie




Giving Java a second chance after ludumdare fiasco


« Reply #8 - Posted 2004-08-04 22:09:59 »

By making your AABB non axially aligned your throwing away one of the biggest advantages of using them; dead simple intersection testing  Tongue .

Quote
This algorithm works correctly.  I'm wondering if there is a faster way.


Why?  Even if you did this every frame for every (non-culled) object in the scene this code should never be a bottleneck in performance.

Like oNyx said; hierarchical bounding volumes would most closely approximate the principal of least cleverness. (ie check an oversize aabb first, then check bounding spheres  or elipses or whatever that more closely approxmate the model.)
Offline cep21

Junior Devvie




Java games rock!


« Reply #9 - Posted 2004-08-04 22:29:31 »

The box stays AABB.  My algorithm rotates an AABB in O(1) into another AABB.  The question of "Is there a faster way" has more of a math/algorithms-are-cool drive than a gaming/practical-speedup drive.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline nonnus29

Senior Devvie




Giving Java a second chance after ludumdare fiasco


« Reply #10 - Posted 2004-08-05 16:15:29 »

Quote
The box stays AABB.


Oh, I see, n/m then!
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Mr.CodeIt (24 views)
2014-12-23 03:34:11

rwatson462 (53 views)
2014-12-15 09:26:44

Mr.CodeIt (45 views)
2014-12-14 19:50:38

BurntPizza (85 views)
2014-12-09 22:41:13

BurntPizza (110 views)
2014-12-08 04:46:31

JscottyBieshaar (79 views)
2014-12-05 12:39:02

SHC (89 views)
2014-12-03 16:27:13

CopyableCougar4 (96 views)
2014-11-29 21:32:03

toopeicgaming1999 (155 views)
2014-11-26 15:22:04

toopeicgaming1999 (152 views)
2014-11-26 15:20:36
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!