Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 11 Aug 2010
Offline Last Active Nov 05 2015 04:39 PM

Topics I've Started

Sequential vs Simultaneous collision detection

22 October 2015 - 11:36 AM

Just wanting to get some clarification on some collision detection thoughts. This is all 2D to keep things simple and no rotations.


In a dynamic impulse based resolution system (ie multiple bodies moving around, when they collide we apply forces to them for the next frame) it seems that there's only a couple of ways that I can go about detecting where/when collisions are going to happen. Say I have a list of bodies, I can either attempt to move them one at a time to their next collision point (ie sequential movement) or I can attempt to find the soonest collision point of all of the bodies, move all of the bodies to that point, and then repeat until the timestep is finished (ie simulataneous movement). 


In the first case, ordering of the objects matters as collisions may or may not occur based on which bodies is moved first.

In the second case, this involves multiple iterations over the bodies to do all of the movement and seems more complex but seems much more accurate. 


I've seen it mentioned (or at least it seems) that many games use the first case as it's easier to implement, faster, and the ordering effects aren't noticeable. While this seems like it would be just fine I just can't get over the fact that it's not deterministic if the order of objects changes :/


It could also be that I'm completely misunderstanding this...


Thoughts or resources related to this subject would be greatly appreciated.

Collision detection in a tight maze

21 October 2015 - 12:30 PM

The idea here is we have a tight maze (ie, a maze with 0 thickness walls and movement only along the x,y axis). This differs from say Pacman where the walls are a full tile thick. A specific example of this is Wizard of Wor.



So I think there's a couple ways to go about this:


I could create a list of walls for the level and then do collision detection against the walls. This seems to work fairly well collision wise as movement is just a general thing with sliding against the walls. Problem is collision detection is pretty complicated due to the walls not actually having any size physics wise.


The other option is to create a tilemap with each tile knowing which side(s) it has walls on. Movement is more complicated because you're moving from point to point in the grid. This is nice because AI can make decisions about where it wants to go strictly when it hits grid points. 



At a glance how do you think this sort of thing was implemented in the past? (I'm guessing it was probably the the tilemap way as it's be less CPU to do this).






Interpolating color across a polygon

12 October 2012 - 01:39 PM

I'm working on a software rasterizer just for grins and I'm to the point where I want to implement smoothing between different colors at vertices across a polygon.

From what I've read, it consists of calculating a scan line, calculating the colors at the ends of the scan line, and then linearly interpolating across that scan line to get the color at a single point.

My question is how to calculate the color at the end of the scan line for polygons with 4+ points. 3 points is pretty straight forward (though I haven't actually done the calculations yet), but 4 is a bit harder to wrap my head around.

Anyone have any good resources (or code) to get me started?

Handling polygons in multiple nodes of an Octree

18 January 2012 - 01:25 PM

I'm building a 3d software renderer for grins to learn the math and rendering concepts. I've implemented the basic drawing of polygons with some basic optimizations like back face culling and frustrum culling. Its going pretty well for it being java and all (15k polygons at 30fps at 1900x1080) but I want to implement an Octree to reduce the amount of overdraw happening and correctly sort the polygons for drawing without using a z-buffer for the entire screen.

I get the basic ideas of how to partition the world and how to traverse the tree from front to back to order the polygons correctly, but I'm a bit confused on how to handle polygons that are in more than one node of the Octree.

Some example cases I'm concerned about are:
  • A floor of 2 big polygons that intersect all of the nodes at the bottom of the Octree
  • A polygon that extends across a node boundary
I figure I should split the polygon at the node boundaries, but then do I need to check on each frame for objects that have moved in the world that need recalculation in the Octree.