Skip to main content

Introduction to SAT

When writing games, collision detection is important, especially one that is fast and robust.  True, you can get away with having a simple rectangular collision detection where your checking if two squares overlay, but that becomes less reliable when objects in your application/game are moving fast and many

I good collision detection system is SAT or  Separating axis theorem.  It says that if two convex shapes' (shapes that do not invaginate) projections along their respective normals does not overlap then the shapes do not overlay.  More clearly, if there is any project that separates the two shapes, then there is a collision.
That is it. However, this requires further explanation.  A convex shape is like a rectangle, an octagon, or any shape that does not fold into itself.  When using SAT, we use its normals, denoted by brown lines, to project two convex shapes while comparing to see if the two's intervals overlap.

If an overlap exist, then a collision is occurring.


Here we see that two shapes normals have been used to project the intervals of the respective shape.  By intervals I mean that the vertexes used to define the individual convex shape has all been projected along the normals (a total of four) using dot product between the normal and vertices so as to find a range or the intervals of the shape.  This interval finding is done for each normal.  Then, the range of the two shapes are compared to see if the overlap, more on this later.  Take note of the image of the right, note that we have an overlap at the top and at the bottom.  This is because the projected intervals of the two overlap.  However, this is not a collision; to be a true collision, all four projects of any shape must not be separate.  So if we have any separation, therefore any project not overlapping, then there is no collision.
Labels:

Comments

Post a Comment

Popular posts from this blog

Creating local variables In Assembly

Lets go over how to create local variables inside of a pure assembly source code. Much like always, you will start with a *.asm file that looks like this: source code SECTION .data SECTION .bss SECTION .text global main ;make main available to operating system(os) main: ;create the stack frame push ebp push mov ebp, esp ;destroy the stack frame mov esp, ebp pop ebp ret So, the above is the general layout of an NASM source file.  Our goal here is to create a local variable inside of the main method.  The only way to create a local variable is by using the stack.  Why?  Because we can only declare variable in storage locations and the only available storage locations are: text, bss, and data.  However, text section is only for code, so it is out of the question.  The bss and data sections are appealing, but to declare our "local" variable in these sections will defeat the purpose of these varia...
2 comments
Read more

NASM Programming

Many of you, if you are like me, might be interested in how assembly works.  You will be very surprised that assembly is very very easy, especially after you write a couple of simple programs.  But don't get me wrong, you will be frustrated at first, however that frustration, if you channel it right, will lead to serious life long learning and will give you a deeper appreciation of the beauty of assembly. For more tutorial on assembly and visualization of these information, visit my youtube channel . Okay so lets get started. We will be using Netwide Assembler (NASM) to write our program. The general format of NASM file is this: ;This is a comment SECTION .data ;declare variable here SECTION .bss ;declare actual, dynamic variable SECTION .text ;where your program code/assembly code lives ; Working with Data Section In your .data section, you can declare variables like this: nameOfVariable: db 32 ;this declares a variable names nameOfVariable...
Post a Comment
Read more

Introduction to Linux Kernel Programming

The Linux kernel is designed as a mixture of a monolithic binary image and a micro-kernel.  This combination allows for the best of both worlds.  On the monolithic side, all the code for the kernel to work with the user and hardware is already installed and ready for fast access, but the downside is that to add more functionality you need to rebuild the entire kernel.   In a different manner, a micro-kernel is composed of small pieces  of code that can be meshed today and more pieces can be added or removed as needed.  However, the downside to micro-kernel is a slower performance. Adding a module to the Kernel Linux is organized as both monolithic, one huge binary, and micro-kernel, as you can add more functionality to it.  The process of adding more functionality to the kernel can be illustrated by the crude image to the left. The process begins by using the command insmod with the name of the kernel module you want (which usually ends with ex...
4 comments
Read more