Well what have I done? Not much, admittedly, for my spring break my dear cousin came out to visit me in Chicago, and we had a great time doing all the things tourists do.
Up to and including getting really tired the last day and spending it watching movies and TV, haha.
In all seriousness, it was great to have her here, and as much as I enjoyed the break, it's time to get back to business. Or "srs bsns" as it has come to be known in our capstone group. I have to get back to working out, and to all of the things I have to do this quarter, which includes...
Calculus II (After a year off...!)
Multiplayer Game Development (Looking forward to this one!)
Capstone II (Duh)
Real Time Graphics (Please be good, please be good...)
And..
Working as a lab mod
Training for the next Judo tournament
Grading for Charley (My awesome faculty adviser at DePaul)
Zombie Yoga (...so much to do... so little time)
Not to mention the things I want to do, like learning how to do some sweet aerial kicks and tricks to impress at the dojo at home (as well as get me in better shape doing something fun as opposed to lifting which I find very hard to do without someone to do it with)
But, what have I done in terms of PROGRAMMING over the break?
I've been fiddling with creating a generic volume class for princess to be used in mo' advanced versions of our current collision system (which needs to be re-hauled... when I have the time)
It's a relatively simple system, it just takes a series of 2d vertices specified in a counter-clockwise order that is closed by connected the last vertex to the first vertex. There are edges between each of these vertices that check against other edges for collisions and etc.
That, my friends, is the drop-dead easy part.
A vertex class? Piece of cake. Edge class? I could do that in my sleep. Connecting them together? Pah! No problem.
So... then WHY am I still stuck on this? Well that's something I've been asking myself. You see, I'm trying to make the whole process as simple and efficient as possible, but at the same time I want this as robust as possible.
If I just want to check edge to edge collision, my system can stop where it's at, however, if I want to check if, say, certain points are contained in my newly created volume that beings to give me problems. If this volume that you've specified is convex, meaning that there are no interior angles in yo' shapes, then all I have to do is check to see if a point is to the left of each edge in the lot, and TA-DA! If it is, then the point resides inside the volume.
 |
| Pictures always help me |
...however, if my shape is non-convex, then this to-the-left-of-each-vertex thing kindof falls apart. (also, the more complex these shapes get, the more processing has to be done for each interior check, which is also a general case, but if there was a simpler way....)
So what to do? Well, its elementary really.
In theory. In practice, not so much. The solution is to divide up the interior of the bounding volume into triangles, then loop through each triangle when looking for a point lying on the interior of a shape, and do some quick and cheap eliminations of unlikely triangles (point not within min/max bounds of a given triangle) before doing the messy stuff (checking the relative space to an edge).
Again, that's not my problem, my problem is HOW to break up the interior into triangles? Well, I kicked around a lot of my own idea for a while. That should be read: I do what I always do when I get stumped, snack profusely while staring blankly at my computer letting my mind alternate between creative thinking and flavor comprehension.
Regardless, I was getting nowhere, this is not a simple as I first thought, so I decided to see if the internet knew anything, and lo and behold I found this, or a good explanation about Delaunay Triangulation, which does more or less what I want to do, it takes a list of vertices, and creates a convex hull out of all of them. The article I linked is the only article I think is worth reading. I found a dozen more before (with source code) and they made no sense to me until I saw the picture-illustration of the algorithm at work in that article. That's when it all made sense to me.
That being said, I'm still having problems. One is conceptual, and one is my implementation. The implementation problem arises when I try to remove triangles as denoted in the algorithm. For some reason my algorithm is very trigger happy and removes too many triangles, leaving me with a sadly half-complete volume-mesh, which makes a very unhappy Kev.
The conceptual problem is that Delaunay's method creates a convex hull, even when I don't necessarily want a convex hull. So I have to go back through once good ol' Delaunay has done his thing and then remove any edges that connect vertices that shouldn't be connected. Imagine two vertices as Romeo and Juliette, which would make me Poison. Or Death. Though I think them both dying was supposed to be, as well as tragic, somewhat reassuring because "they died together" or "died for each other" or whatnot.
It's been a while since I read that play for English in high school, don't judge me. Getting back on track, this is achieved relatively simply if messily by comparing the angle between the two "true" outside edges of each vertex, if the angle from the first to the second (thinking clockwise here) is greater than or equal to 180 degrees or Pi/2 then it's a lovely convex point and we don't have anything to worry about, however, if the point is less than 180 degrees and we have a third edge between the two vertices at either end of the vertex in question, that edge must be removed to maintain our desired non-convex result.
But I haven't even gotten to that part yet because of my trigger happy triangle-removal portion of my code.
This is depressing, this algorithm shouldn't have taken more than a day to implement.
This quarter is going to kill me.
 |
| It's 0200. I can't maths, I can't draws, I can't programs. Therefore, I blogs. I should probably sleeps, though. |
No comments:
Post a Comment