Scattering
Recently a developer, Marty Plumbo, was having some issues with scattering tree models across a terrain surface (the terrain not necessarily being flat nor spherical, rather it could be any arbitrary shape). The problem involves two steps, determining where to place the tree and then how to orient that tree so it points "up". What follows below is largely what I was going to write as an email response to Marty but decided to post here instead, thus it's not written in proper "article" format and all that jazz, but it's still worth a read, at least I hope it is! I hope to come back later and make this all a bit more proper along with my Incenter article as well.
Thanks to Marty for his actual scattering routine, I'm just offering some tweaks as to how the position and "up" direction for a given face might be calculated.
Note: please understand that in the following text if I refer to "your technique" or "your movie" I'm generally referring to Marty's initial techniques and movie, both of which work well enough indeed, those can be found in the file scatter.dir. When I refer to "my technique" or any changes that I implemented then you'll find those in the file scatter_tom.dir.
There are two parts to the problem here, the first is determining the position at which you want to place your "tree" and then the "up" direction in which that tree will be pointed (so the tree's point is "up" and its base is "down"). Let's look at each of the two parts of that process separately as they involve different techniques worth looking at on their own.
How do you get the position of a particular face?
In your technique you simply use the first vertex listed for the face and use that vertex's position as the location at which you'll place the tree model. This means that when your tree is added to the world it's always directly over one vertex of the face as opposed to somewhere within the face (that's not necessarily a problem, I'm just being descriptive). But one might also want to find the "center" of the face instead and place the tree model there, the trouble with that is defining and determining where the "center" of the face is. If we used rectangular polygon faces then the task would be simple and straightforward, but we don't, we have triangular faces and so it's a bit trickier than that. There are a few ways to define where the "center" of a triangle should be, but the one I prefer to work with is known as the "incenter" of a triangle, and what's more there's a well derived equation that can be used to calculate the position of the incenter from the coordinate positions of the triangle's three vertices.
For a quick overview of the incenter, and a description of how it's coordinates can be calculated take a look at these URLs:
Ok, so without worrying about Director, Lingo or a 3rd dimension (notice all the stuff at the URL's above is in 2D?), are you with me so far? We have a triangle with vertices A, B and C (those each being the vector positions of the vertices), are you comfortable with what the "incenter" is? I can provide some references for you with respect to other types of triangle centers that can be calculated, the incenter is simply the "best" to me in that it's easy to calculate and makes for a good visual center IMO. If you're not comfortable with a triangle and what the incenter is then stop here and let's clear that up first. If you are comfortable, or reasonably so, then keep on readin'...
Now, let's worry about that 3rd dimension! While not shown on the pages above, the equation used to determine the location of the incenter is rather simple to extend into the third (z) dimension. Assume that the incenter's position is denoted by I, then we have:
Ix = ( (a * Ax) + (b * Bx) + (c * Cx) ) / (a + b + c)
Iy = ( (a * Ay) + (b * By) + (c * Cy) ) / (a + b + c)
Ix = ( (a * Az) + (b * Bz) + (c * Cz) ) / (a + b + c)
With the three equations above in hand, it's a simple matter of writing the above in Lingo. We'll see this in action in your movie in just a bit, but first take a look at the following as it discusses the above and contains a good sample movie to view:
I took the code used to calculate the incenter, as found in the demo above, and then incorporated that into your example movie, but we'll get back to that in a bit! For now let's just summarize this section with the following:
Instead of simply grabbing the position of the face's first vertex you could also grab the positions of all three vertices, perform some simple calculations (simple vector math) then use those results to find the "incenter" of the face instead, meaning your trees will be positioned in the "middle" of the triangle as opposed to exactly over one particular vertex. Are we cool with that? This is another point at which we should stop and make sure you're on board before proceeding, so either ask some questions or keep on readin'...
How do I get a normal vector for a particular face?
The technique you used here was to grab the normal vector used for shading purposes by the first vertex in the face, the problem with that (however minor) is that there's no guarantee that the shading normal is at all perpendicular to the face or the surface region in the area. So my technique, which follows having used the triangle's incenter as the tree location, is to use the positions of the three vertices (or rather the delta vectors between them) to calculate a normal vector that is truly normal, meaning of unit length and specifically perpendicular to the triangle's surface. To achieve this goal we only need to make use of some simple vector-math techniques, specifically it's a simple matter of computer vector cross-products to compute the normal vector we need.
What is a cross-product of two vectors? This is a math operation which allows you to take any two vectors, then from those you compute the "cross-product" in order to get a vector that is perpendicular to the plane defined by those two vectors (any two vectors can be said to lie in a plane). For example, if you look at the vectors (1,0,0) (the x-direction) and (0,1,0) (the y-direction), it just so happens (not by luck mind you!) that if you take the cross-product of (1,0,0)x(0,1,0) (note that the x isn't "multiply by" when you're doing vector math, the x indicates a cross-product) you get the z-axis! Look at that again, you have two vectors (the x and y directions), and they define a plane (the x-y plane, typically scene in 2D charts of all manner), and their cross product yields a third vector perpendicular to that plane, and we all know that as the z-axis. Make sense?
There's more though, the order of the cross-product is important to understand. Most of today's math world and 3D engines operates based on the "right hand rule", and so the result of the cross-product calculation does the same. Here's the layman's example to consider. Take your right hand, fingers straight and point it in the direction of the first vector listed (for example, the x-direction), then curl your fingers (like you're making a fist) towards the second vector (for example, the y-direction), if you left your thumb sticking straight up (like you're hitchhiking) then your thumb will point in the direction of the resulting vector (for example, the z-direction).
Whew, that's a nice chunk to consider for a moment. Are you with me so far? We haven't talked about Lingo or any code yet, I want to be sure you're good with the notion of the cross-product and clear on its general operation (even if we're not yet worried about how to do that calculation), if not then speak up so we can clarify things a bit more. If you're ready then we're going to jump into the deep end... :)
In our case we can determine the position delta between any two vertices of our triangle:
AB = B - A (the position delta from A to B)
BC = C - B (the position delta from B to C)
CA = A - C (the position delta from C to A)
(the direction of these, meaning the order of subtraction is _very_ important as the right hand rule will soon take effect)
Knowing those three vectors (AB, BC and CA) we can then use any two of them to compute the cross-product, which will result (very nicely!) in a vector that is perpendicular to the triangle's surface! In this case we *must* be careful of the order of our cross product so that our perpendicular vector isn't pointing "down" instead of up! Knowing that faces too use the "right hand rule" in order to determine the winding order of vertices (the order in which they appear in the face information) it's a simple choice, one would be to determine BC x CA, and we'll get an "up" vector. Luckily our math engine is already prepared to handle cross-products for us using the following notation:
tX = vector(10,0,0)
tY = vector(0,10,0)
tZ = tX.crossProduct(tY)
put tZ
-- vector(0,0,10) -- NICE!
But if we're not careful and don't mind our "right hand" rule:
tZ = tY.crossProduct(tX)
put tZ
-- vector(0,0,-10)
!!! So be careful when choosing the order so you don't reverse your "up" vector and really end up with "down" instead. :P Below is a demonstration in which your original technique is used as well as the one I'm offering as an alternative (no statements of better or worse being made).
Demo
When viewing either of the two scenes you can click on the 3D world to switch between your routine (green trees), my routine (red trees) or both our routines (green and red trees). There's a link for the source file below, if you open it and view the behavior script named "trees" you'll see that I've clearly commented things in the important areas.
