Faster Voronoi Noise
On my last post about this topic I was using a very inefficient triangle filling method; for each triangle joining the center of a Voronoi cell with one of its boundary segments, I was performing a per-pixel distance check and, depending on such distance, the amount of white for the analyzed pixel was determined.
I realized that, since the distance was being checked linearly, a gradient fill would actually do the trick. It works, and a lot faster. Also, since this runs with gradient fills, the method can generate a very large variety of different "Voronoi noises", try playing around with the source and you'll see.
This demo uses Alan Shaw's AS3Delaunay library. It runs just as fast as the one I used previously (Controul's) which is amazingly fast for pure AS3, but it is actually much more comfortable to use. Controul's Voronoi class is kind of encrypted because of all the optimizations it has, and returns only the Voronoi segments data. Shaw's Voronoi class can be asked for just about anything, from Voronoi segments to Delaunay triangles, spanning tree, nearest neighbors, etc. Thanks for this Alan!
I wonder if using drawTriangles() or bitmap fills could make this even faster. Any suggestions would be highly appreciated!
OBB Collision Detection
Click on image to view the demo (view source enabled).
Its just a basic implementation of the method of separating axes for 3D OBB's (oriented bounding boxes). It detects collisions between cubes in a way that is slightly more advanced than spherical collisions, which are merely based on distances and radii. Collisions are not resolved in the demo though, only detected.
The point of the experiment is to show that it isn't hard at all to detect collisions between 3D objects if considering only their bounding boxes for their 'physical volume' is enough; if we just need to detect if objects are colliding or not, we don't actually need to bring in a heavy, cpu thirsty, 3D physics engine.
The code is not optimized (in fact quite the contrary so that its easy to read), but it runs quite smoothly with 15 cubes, where each cube is checked with all others for collision. If, for example, a character needed to be checked for collisions against static objects in a 3D scene, we would just need to compare his bounding box with the scene's static bounding boxes, so a large number of physically active objects could be used to describe a pretty complex scene. Furthermore, if any of these boxes were axis aligned, they are no longer OBB's, but rather AABB's (axis aligned bounding boxes) and collision checks could be made much faster. Something like this I imagine:
return (obj1MinX < obj2MaxX) && (obj1MaxX > obj2MinX) &&
(obj1MinY < obj2MaxY) && (obj1MaxY > obj2MinY) &&
(obj1MinZ < obj2MaxZ) && (obj1MaxZ > obj2MinZ);
The experiment is clarifying in understanding how the method of separating axis works, and I guess it gave me a quick glimpse at how a advanced physics engines like JigLibFlash might work. The code is heavily commented, so have a look if you're interested in understanding OBB collisions.
Basic Fractal Tree
Another obsolete experiment! Click on the image to view it (view source enabled).
The concept is simple: alternate squares and triangles to produce a fractal tree-like structure. On each step, either triangles or squares are drawn in the edges of the last set of drawn elements. If the last set was triangles, squares are drawn and vice versa. Two squares can sprout from a triangle and a single triangle can sprout from a square, hence, triangles are the cause for bifurcations. That's it! Pretty simple, yet beautiful; the simple rules produce some very complex variations. I hope it is inspiring to produce more complex fractal beings.
Play around with the parameters:
[growthRate: Time in ms between the creation of each step] [maxSteps: The number of recursive iterations. Be careful not to go above 25! It could crash your browser] [Triangle base factor: From 0 to 1, controls the inclination of the triangles. 0.5 makes the tip of the triangle be above the mid point of the base] [Triangle height factor: Relationship of the height of tris to their base] [Square height factor: Relationship of the height of squares to their base].
Voronoi Collisions?
So, it's Saturday night, my flat mates are all heading out to cool party 'A' and cool party 'B'. Unfortunately, I have to stay indoors in quarantine since I was blessed with a flu last Thursday. Damn it! I hate it when I fall Ill just before the weekend. It's so unfair!
Anyway, I needed something to do and I think I watched practically every single new film in megavideo, so I decided to have another play with our friend Voronoi. The experiment revolves around the following question: If voronoi diagrams provide so much information about the spacial distribution of a set of points in space, couldn't this information be used to detect collisions between circles?
Apparently the experiment above says 'yes' (click on the image to run it - view source is enabled). What you would normally do to have a bunch of circles collide with each other is, on each frame, evaluate the distance of each circle to all others in some sort of nested loop. If the distance is smaller than the sum of the radii of the 2 circles being compared, you have a collision. I think that everyone involved in programming with at least a small affinity with physics has had a go at this. Even though the collision check is very simple, the amount of distance calculations is brutal. 'n' circles means 'n' to the power of 2 collision checks per frame. Of course, there are optimizations as dividing the space in a grid and only checking for collisions in the current cell and neighboring cells, which can reduce the calculations a lot.
So even though the experiment looks like what we've all seen (and/or done) 1000 times, the implementation is completely different, at least for me. On each frame the position of the circles is used to construct a Voronoi diagram. This produces a set of line segments attributed to each Voronoi focus point (which are the centers of the circles). If you compare the distance of such point to its related Voronoi edges in the Voronoi cell, with the radius of the circle, you can detect when the circle is colliding with something. If you do have a collision, you can use the vector involved in the collision check to exert a force on the circle, so once you know that something is colliding, there's no need to do any complex calculations to resolve the collision; the voronoi diagram also provides the info for you to resolve it!
I'm sure that the physics in the demo is not exactly right, and that the code could run much faster if optimized (its just an experiment after all, a proof of concept). I didn't worry much about physics correctness or using inlining or any other Flash Player optimization techniques, I preferred to keep the code clear and simple to understand. Currently its resolving collisions for 250 circles and it runs ok. I wonder how many circles it could manage if optimized, and if it would be faster than the more commonly known approaches. I have a feeling that this could be some sort of BSP collision detection system.
Uses of this? None, absolutely NONE what so ever!! Perhaps only providing a visual programmer some time to be entertained while on quarantine Saturday night :s
Meta
Categories
Archives
- May 2010
- January 2010
- October 2009
- September 2009
- August 2009
- July 2009
- June 2009
- May 2009
- April 2009
- February 2009
- January 2009
- December 2008
- October 2008
- September 2008
Links
- Away3D
- EzeQL
- Fabrice Closier
- Infinite Turtles
- Kevin Luck
- London Flash Platform User Group
- TheTechLabs
- wu-media lab
