• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
  • entries
    41
  • comments
    51
  • views
    35665

Blogging up... Shooting Stuff : Triangle Based Collision Testing

Sign in to follow this  
Followers 0
Mak

1014 views

We're now at the stage where we're trying to drum up some interest in Dominion again before we launch the funding campaign again. So, to that end we're starting to publish some design & dev blogs on our site for those interested. They'll be written for those who are less... "tech" aware than those who tread these hallowed halls - but hopefully they might be of interest - if not only to the curious.

I'm not touting any of this as "the best way to do it" or anything magic we've come up with - because it isn't! It's just interesting, I hope ;)

I'm not sure what the best form is - to just drop a link here to our site blog, or double-copy the same blog here, so for now I'll do both!

http://dominion.maksw.com/2013/01/26/shooting-stuff-triangle-based-collision-testing/


[color=rgb(51,51,51)][font=Georgia, 'Times New Roman', 'Bitstream Charter', Times, serif]

So far shooting stuff has been based on your basic point/ray to sphere - a more sophisticated system was planned for later on in development - but to bring the wow-factor up a notch I've had to bring it forward.

[/font][/color]

[color=rgb(51,51,51)][font=Georgia, 'Times New Roman', 'Bitstream Charter', Times, serif]

I want a lot of objects whizzing about on screen - that means an awful lot of potential collisions - while I'll go into the basics of the scene collision management in another post - this one is about what happens when one of your hundreds of missiles needs to hit a ship!

[/font][/color]
[color=rgb(51,51,51)][font=Georgia, 'Times New Roman', 'Bitstream Charter', Times, serif]

To make it look as believable as possible, the missile/bullet needs to impact the surface of the vessel and throw up sparks/debris/whatever. That means checking every single triangle in the model to see if your missile has hit it - quite a chore! And with models with hundreds of thousands of triangles in, even the beefiest CPU would buckle under the strain.

[/font][/color]

[color=rgb(51,51,51)][font=Georgia, 'Times New Roman', 'Bitstream Charter', Times, serif]

So, what to do? Well, as ever with computing - the least amount of work possible! Hit testing every triangle sounds like a lot of work, so how do we do less?

[/font][/color]

[color=rgb(51,51,51)][font=Georgia, 'Times New Roman', 'Bitstream Charter', Times, serif]

Octrees.

[/font][/color]

[color=rgb(51,51,51)][font=Georgia, 'Times New Roman', 'Bitstream Charter', Times, serif]

Octrees allow us to divide a large volume into smaller volumes (or containers) and then stick stuff into them. All we need to do is then find which container our missile would go in, and the check the missile against the contents of that container. Simples!

[/font][/color]

[color=rgb(51,51,51)][font=Georgia, 'Times New Roman', 'Bitstream Charter', Times, serif]

Well, not quite - but the principal is that easy. We create an octree volume the same size as the model itself, then start adding triangles to the volume. When there are more than say 50, we subdivide the volume (which creates 8 equal sized smaller volumes), and then move all the triangles into these smaller volumes. Then we continue adding triangles from our model. When we've reached the end of the models triangles, they should all be safely stashed away in the smallest volumes in the octree which should contain them. Depending on the models triangle count, and the number of triangles to be stashed into each volume - the octree will be several layers deep. This means we can quickly find the volume a point is in with only a few checks.

[/font][/color]

[color=rgb(51,51,51)][font=Georgia, 'Times New Roman', 'Bitstream Charter', Times, serif]

Triangle-Collision-Montage.jpg Model Octrees

[/font][/color]

[color=rgb(51,51,51)][font=Georgia, 'Times New Roman', 'Bitstream Charter', Times, serif]

You can see the process in the image above - going left to right, we have the model's bounding volume (the maximum space it will occupy), then the Octree we get by repeatedly subdividing this volume into 8 until we get 50 triangles per volume. We then test an impact point to find out which volumes would be affected - finally showing those volumes, and the triangles we need to test in yellow. We've quickly gone from several thousand triangles down to a handful to test against.

[/font][/color]

[color=rgb(51,51,51)][font=Georgia, 'Times New Roman', 'Bitstream Charter', Times, serif]

To check for a collision, we have to bring that missile into model space - this means we find the missiles position and orientation relative to the model. We have to do this, as our octree and it's triangles are always about the origin (0,0,0) and not in orbit about Canthen where you just shot at it. This helps speed up the testing as less math is involved.

[/font][/color]

[color=rgb(51,51,51)][font=Georgia, 'Times New Roman', 'Bitstream Charter', Times, serif]

We can now find the volume in the octree that this missile would go in, and then test it for a collision against each triangle. Each triangle which intersects the missile is flagged, and voila - we have our impact zone!

[/font][/color]

[color=rgb(51,51,51)][font=Georgia, 'Times New Roman', 'Bitstream Charter', Times, serif]

This consumes a lot more memory as the octree can be quite large for a large or highly detailed model, but the performance improvement over the brute force "check every triangle" is huge for larger models. Balancing the triangles-per-node against the volume of the model is the best way to tune the system.

[/font][/color]

0
Sign in to follow this  
Followers 0


0 Comments


There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now