Jump to content

  • Log In with Google      Sign In   
  • Create Account

Irlan Robson

Member Since 08 May 2012
Offline Last Active Aug 23 2016 11:17 PM

Posts I've Made

In Topic: Distinct quadtrees for static and moving objects

18 August 2016 - 01:36 PM

It depends on several implementation details that involves memory management, data structures, and heuristics.


You can achieve O(1) insertion with a Quadtree if you implement the optimizations described by L. Spiro in this post (originally described in GPG 4 IIRC):




but I can't talk more about this because I never needed to implement such data structure.


As for AABB trees, one detail is the way the nodes are  stored in the memory. For both static and dynamic tree is possible to store their nodes in an array in an attempt to decrease memory access time when traversing the tree. For an array-based static tree the insertion is simple. But for an array-based dynamic tree the operations are not so trivial. A free list of nodes needs to be maintained in the tree for quick node allocation when inserting a new leaf. It is also recommended to inflate the node's AABB by some units such that becomes possible not re-inserting the node into the tree in a future time, when updating the AABB. For example, that could be done by checking if the new AABB is still contained in the old AABB. Another optimization is to predictively extend the new AABB by some units in the direction of motion of the object associated with the node.


Here is an example implementation if you need help implementing the dynamic tree with the optmizations/heuristics I've mentioned above:




Here are some nice slides by Erwin 



In Topic: Distinct quadtrees for static and moving objects

18 August 2016 - 11:11 AM

You can use a static AABB tree if you need fast ray or AABB queries. It is possible to store the nodes in an array to improve cache performance when traversing it. I use this for generating mesh contacts in my physics engine, but I'm pretty sure it is suitable for graphics (e.g. culling) as well. 

In Topic: Engine design v0.3, classes and systems. thoughts?

16 August 2016 - 06:37 PM

I'm not going to point out the problems in your design but I encourage you to search here on the forums about "game engine architecture". It is also recommended that you read Jason Gregory's Game Engine Architecture book to understand the details of each game engine system.
Roughly speaking, for your first game engine I recommend a source tree that looks like this:
External (Dependencies)
Game Object
Each module (e.g. Core, Rendering, etc.) being a static library that gets linked into the game. If you're really organized then you might consider using UML's Class Diagrams instead of paint sketches to model the relationship between each system.

In Topic: Upward force calculation for raycast/ground collision

14 August 2016 - 09:52 AM

You can try solving a penetration using only an impulse with the Baumgarte method. You basically add an artificial impulse to the natural impulse using the penetration depth so that the penetration vanishes after updating the position with the resolved velocity. Here is an example at line 126.


You can implement some mechanism that allows you sending contact points to the contact solver of the physics engine explicitly if you don't want spend time changing the physics engine pipeline.

In Topic: Moving Aabb Vs Tri/aabb/sphere Code

09 August 2016 - 01:17 PM

Sorry, I kind of skip over and read only the last post. I wanted to add to what Randy said. Said phrase shouldn't be present in this discussion as the OP mentioned a single and static triangle (a kind of rare case). (This might be a small help if the OP wants to extend the algorithm for general triangle meshes.) D956 is correct, these things are a bit off-topic so lets keep it for another discussion.


The capsule choice was personal and I believe that if you're considering the problems we mentioned and have a solution then an AABB should work correctly as well.