next »

[PsySal]

now the blocks can only be rotated over its height axle by 90 degrees step only.
for all the environment stuff that works nicely but the characters need more juice.

Hi nikki. It's a big jump to go from rotating around one axis, to rotating freely. I'm not saying you shouldn't do it, but here are some things to think about:

- You might be able to use free rotation for animation only, and keep the height-axis-only rotation as the only one that affects gameplay. Something to think about!

- It's a good idea to learn how to visualize rotations in 3D, before worrying about quaternions. In truth, the advantage of quaternions over matrices are mostly when you're combining many rotations together.

Either way, the most important thing I think is to learn how to visualize rotations in 3D, and understand what the different ways are to describe them.

Best wishes! There are lots of tutorials about quaternions but they are still just a tool for managing the math, they may or may not help you.

[nikki]

Just out of interest, why do you want to use quaternions ?

the term came up a few times as the best solution for 3d rotations... (vs axis angle (w/ gimal lock))

I sort of have skipped the whole matrices step now (and have the exact result that i wanted)
but i understand your point (and that of PsySal) in that it has a little crazy math involved vs the matrix.

my initial association with matrices was that of the as3 transform matrix, wich felt like to many variables for me.


this is however my first dabbles in 3d, and i shouldn't try to skip the basics, but that's hard to live by when i feel i know what i want...

You might be able to use free rotation for animation only, and keep the height-axis-only rotation as the only one that affects gameplay. Something to think about!

yeah my plan for this code is to use it in a voxel character program, wich will output tilestrips that i'll use in my game.
for some special effects i could see myself using the rotations in realtime aswell, but that's not the goal. those are pleasant side-effects (i will keep the original voxeldata available in the game so it's all possibe)

i shouldn't try to skip the basics, but that's hard to live by

at this time i'm actually thinking how to define and use basic 3d shapes (that can be rotated freely) instead of the individual voxeldata.

so the voxeldata 3d array would become some kind of place where i draw/fill those objects to. i feel this will solve the aliasing. but it is hard to think about.

in my head the steps would go like this:

Code:

1- define a 3d object instance (box/pyramid/cone/frustrum/sphere/prism) (will have all vertices for important points, and maybe also bounding box vertices)
2- add a rotation quat.
3- reconstruct the shape (by drawing 3d bresenham lines between the correct vertices (that drawing will be done into the 3d array))
4- for every height slice in the 3d array
5- construct a polygon from the points that are in this slice
6- fill that polygon

but i am also quite sure that step 3 and 4 are not right...

[Ashaman73]

There's nothing wrong with targeting quaternions, but the de-facto standard in game programming are 4x4 matrices.

Whenever you will get in contact with other API, phyics or rendering (i.e. shaders) API, you will most likely need to feed them with matricies. Although quaterions only cover rotation, whereas a homogeneous (which is the standard) 4x4 matrix can handle rotation,translation,scaling and projection in just a single matrix and eventually quaternions, though very important for some special cases, will lack community support. Most developers will be familiar with matrices.

[ThemsAllTook]

There's nothing wrong with targeting quaternions, but the de-facto standard in game programming are 4x4 matrices.

Whenever you will get in contact with other API, phyics or rendering (i.e. shaders) API, you will most likely need to feed them with matricies. Although quaterions only cover rotation, whereas a homogeneous (which is the standard) 4x4 matrix can handle rotation,translation,scaling and projection in just a single matrix and eventually quaternions, though very important for some special cases, will lack community support. Most developers will be familiar with matrices.

What? Quaternions are quite well known and used all over the place. 4x4 matrices are a related but different transformation tool. When you're just working with rotations, quaternions are far more convenient, particularly if you need to interpolate them. I'm curious how you've come to the conclusion that matrices are more of a "de-facto standard" than quaternions.

[PsySal]

What? Quaternions are quite well known and used all over the place. 4x4 matrices are a related but different transformation tool. When you're just working with rotations, quaternions are far more convenient, particularly if you need to interpolate them. I'm curious how you've come to the conclusion that matrices are more of a "de-facto standard" than quaternions.

One way of looking at this is: quaternions are quite useful and convenient when you're dealing with rotations, particularly doing sophisticated things. They are very efficient and generally have simpler math for performing operations on the rotations themselves (such as interpolating between them.)

However, when you're done, you convert your quaternion describing the rotation to a matrix, so you can transform points by it. Remember, it's actually more expensive to transform (rotate) a point by a quaternion, than it is to transform it by a matrix.

I don't know if this is what the original meaning of "de-facto standard" was, I'm just guessing!

[Ashaman73]

What? Quaternions are quite well known and used all over the place. 4x4 matrices are a related but different transformation tool.

As already mentioned, quaternions are important, I use them myself when needed, but other than saving space or doing spherical interpolation, quaternions are seldomly used in game development.

Show me just one none-math/none-animation library, tool or engine which uses mainly quaternions. Most will support them, but the core math of almost all libs/engines etc. are based around 4x4 matrices.

[nikki]

So if i'd use matrices, would you guys then look at my idea (3d shapes in a voxel editor)?
Or should i start a new thread for that and leave this thread for arguing matrix vs quat ?

[Ashaman73]

So if i'd use matrices, would you guys then look at my idea (3d shapes in a voxel editor)?
Or should i start a new thread for that and leave this thread for arguing matrix vs quat ?

Sorry, it was not my intention to hijack your thread.

i just realized i way i could fix the antialiasing..  i guess
if i would use 3d shapes (cube, cone, piramids (4/3 sides) prisms ) to construct a voxel object with, i could rotate the important points of the shapes (the endpoints) and after the rotation i'd rebuild the shapes, fill the correct voxels and enjoy.

so basically the aliasing is fixed as it is always fixed, by using vector instead of pixel

this way of thinking/and building is fruitfull you guys would think ?

You said that for environment you want to use only 90 degree rotations, which would get rid of aliasing. For characters and object you could get rid of the aliasing when you handle them as single 3d objects and rotate them accordingly (much like minecraft characters). It depends on the look you want to archieve, you could even use the marching cube algorithm or something similar to create a more polygonal model from it (kind of anti-aliasing).

[PsySal]

So if i'd use matrices, would you guys then look at my idea (3d shapes in a voxel editor)?
Or should i start a new thread for that and leave this thread for arguing matrix vs quat ?

Hi nikki, I carefully re-read your original post.

Since it sounds like you just want a way to rotate the voxels in your models by angles other than 90 degree steps, I would recommend sticking to matrices. Note that if you want to only rotate around the height vector, but by any angle, you can just use a simple angle. But if you want to rotate in other ways, you'll need to use a matrix or quaternion.

The real trick for you will be:

- First get a simple system up and running that will let you transform voxels by a matrix. If you can find a matrix library and play around with it, that will be easiest. I don't recommend to write your own matrix library as it's very error-prone, even if you know the math very well.

- Learn a few basic ways of describing rotations, conceptually. Euler angles, which is basically saying "rotate by A degrees around the X axis, then B degrees around the Y axis, then C degrees around the Z axis" may seem simple-- but they can actually be awkward to work with. So this is a pitfall to avoid

Following up on the above idea, the most useful way I have for thinking about rotations is "align" transformations.

Imagine you have a vector, V_source = (0, 0, -1)

Imagine this is a "stick" model, just an ordinary stick that might be on a tree. It's x and y dimensions will be small and square, let's say, but it will point straight up (z = -1) so it's z dimension will be long. So you've got this simple rectangular prism which has dimensions such as (1, 1, 10) and it's textured to look like a branch.

Now you are making a tree out of this, and you want the branch to stick out at an angle from the trunk. Here's how you can do it using "align" transformations:

1. First, we need to randomly choose a way for it to stick out. We'll do this like so:

V_dest = (rn () * 2 - 1, rn () * 2 - 1, -3)

What this will result in is a vector that looks maybe like one of these:

(0.235, -0.422, -3)
(0.983,  0.368, -3)
(-0.288, -0.717, -3)
...

You get the idea. Vector with a smallish x and y part, and a z part that is always -3.

2. The next thing we do is normalize the vector, so it's length is 1.

V_dest_n = normalize (V_dest)

3. What we would like to do now, is this:

Create a matrix, M, that will "align" our source vector V_source (this is a line pointing straight up) to our dest vector V_dest_n (this is a line pointing MOSTLY up, but also out at some random amount, in some random direction.)

4. How do we do this?

]Well first, when you create a rotation using a matrix, one of the most basic ways to do it is "axis angle". What this means is you specify an axis to rotate around (can be any vector at all, not just the x/y/z axes) and an angle to rotate by. If you use a matrix library, you will almost definitely have a function like this-- and don't confuse it by euler angles, they are very different. "Axis angle" is basically the MOST useful and practical way to think about rotations.

5. So the trick will be describing the above "align" operation in terms of axis angle.

Well, it turns out there is a way to do this without much difficulty at all.

I won't go into the math here, but you should learn about cross products and dot products. A cross product takes two input vectors and gives you an output vector that is perpendicular to both. If you want to be good at 3D, PRACTICE VISUALIZING THIS. Visualize different vectors in 3D, and then see if you can imagine a vector pointing that is perpendicular to them. Anyhow, what we want to do is rotate by this perpendicular vector:

V_axis_of_rotation = cross_product (V_source, V_dest_n)

Now we have the axis to rotate around, we are almost ready to build the matrix we need.

6. We just need an angle to tell our matrix library. It turns out that we can do this very simply:

angle_of_rotation = acos (dot_product (V_source, V_dest_n))

Again, I won't go into the math. You should definitely learn what a dot product is-- it takes two vectors, and gives you a number -1..1 describing how closely they line up. 0 means they are perpendicular, -1 means they point exactly in the opposite direction.

7. We have our axis and angle, so we can do:

M = axis_angle_matrix (axis_of_rotation, angle_of_rotation)

And apply it to every point in our original branch:

transformed_stick = M.apply_to_mesh (original_stick_mesh)

8. There are two degenerate cases.

Basically, the cross product will not work when the two vectors are exactly the same or exactly opposite. In case they are extremely close, it may fail as well due to numerical issues. For that reason, we should check when we are building our matrix that we didn't try to create a degenerate rotaton, which we can do quite easily if the absolute value of the dot product is too great (say, greater than 0.99999)

This might seem complex, but please DO READ IT! Read it over and look up the things described in it. If you really want to do free rotations, this is a great way to start thinking about them and describing them.

Long post! Class dismissed =)

[nikki]

thanks alot Maestro  , i'll be re-reading your post a good few times today.

[PsySal]

thanks alot Maestro  , i'll be re-reading your post a good few times today.

Haha you get an A+ for calling me Maestro In serious though do ask if you have questions. It can seem daunting but it's actually not that hard if you can break it down into managable parts. My post definitely wasn't meant to scare you off, just take it one piece at a time!

[nikki]

yeah so I am back at this thing...
I've got mostly all of it working, i get the tutorials and have read all about the topic

BUT

i am still having this one problem that bugs me:
maybe one of you guys knows something todo about it.

when i rotate a plane (of individual voxels) and i rotate around the height axis for exactly 45 degrees a few voxels get assigned the same location in the new rotated shape, this leads to a few holes.

before i didn't use a Round function and there where many holes in the rotated shape at all rotations, since then  I use the Round these holes are gone, except on multiples of 45 degrees...

i suspect the problem is more simmilar to the rotating of bitmap images (and the artifacts you get when rotating very small images) then polygon 3d approaches because you wouldn't have that problem with polygons.

[Danmark]

i suspect the problem is more simmilar to the rotating of bitmap images (and the artifacts you get when rotating very small images) then polygon 3d approaches because you wouldn't have that problem with polygons.

You're right, and the problem is fundamental enough that you won't find any numerical quick fixes.

I'm astounded you're only seeing this happen at 45 degree angles, although it is where aliasing should be worst. I'd start by determining the real scale of your problem. Write a test that makes a big cube of voxels (not just a plane) as big as the biggest object in your game, and rotates it by arbitrary axis-angles while recording how many voxels got aliased.

The reason 45 degrees is particularly hairy is because you have two problems. One, the problem of multiple voxel centers resolving to the same world axis-aligned voxel, which you'll have for a pretty big range of angles (hence my disbelief), worst at 45. Two, the problem of marginal cases, where the center of a voxel could just as well fall either side of a face of a world voxel, and tiny precision issues will arbitrate which side. Tell me: in the case you mention, do you see lots of aliasing along the global x and z axes?

You might hack around the second problem by shifting the center of the object on all axes by a tiny offset, to ensure a consistent tiebreaker. Hopefully someone has a better idea.

The first problem is more subtle. Gist of it is you need to identify gaps and fill them with voxels from the gaps' 3x3x3 neighborhoods. Can't think of a robust solution though. Perhaps you can get some ideas from the RotSprite algorithm (more info about it here than anywhere else, also lots of TIGers).

Here are some roughshod illustrations of the problem in 2D. Red lines are object pixel edges, blue crosses are object pixel centers, and black lines are world pixel edges. Clicky:

Note the world pixels without object pixels, and world pixels with 2 object pixels in them. In 3D, there could be up to 4 object voxels aliased to a world voxel. Also heed the complexity. The ideal pixel to fill a gap doesn't necessarily come from an aliased pixel. If you did something sequential, the order would be crucial, and you'd have to look far ahead to produce good output. Considering not every object pixel would be defined, even finding gaps is non-trivial.

BTW, if you don't need rotation to preserve color of individual voxels, or to even vaguely preserve volume of smaller voxel objects, the problem becomes radically simpler.

[nikki]

before i start reading your post properly i want to share another insight :

i 'think' it has to do with cos/sin rounding errors perhaps, because 45 degrees feels very sinus cosinussy to me as a problem,

i've read it properly, the illustartion show there is no quick fix

Tell me: in the case you mention, do you see lots of aliasing along the global x and z axes?

I am not entirely sure what you mean, I see there is a sort of pattern in the holes though, (im sorry i am not at my dev machine and cannot screencapture atm (tomorrow i will))

i've tried the shifting the centre (no joy), another thing i tried that was reasonably succesfull was this:
instead of having an algorithm that does something(rotate) for every voxel in the original shape, i did it the other way; for every voxel in the rotated emtpy space i looked up the position where it should originate from. It sort of works better, still not perfectly and it costs way more time because now i have to do quaternions, multiplying etc etc for every voxel, instead of only the ones that are not empty..

thanks for the illustrations, it is exactly the theory behind the problem.

oh and

BTW, if you don't need rotation to preserve color of individual voxels, or to even vaguely preserve volume of smaller voxel objects, the problem becomes radically simpler.

well i don't need color (all the voxels in a shape will be the same, and actors get created by using 20/30 ish of those shapes together) i believe i do need to preserve volume of smaller shapes though (but i am curious how it makes it simpler)

and yeah:
maybe i should just bite the bullet and describe the shapes as polygons, rotate the points of meaning and fill in the rotated shapes afterwards with voxels, it feels overkill/and will prolly introduce many new problems   but it might be alot more fail-safe at the end

[Danmark]

i've tried the shifting the centre (no joy), another thing i tried that was reasonably succesfull was this:
instead of having an algorithm that does something(rotate) for every voxel in the original shape, i did it the other way; for every voxel in the rotated emtpy space i looked up the position where it should originate from. It sort of works better, still not perfectly and it costs way more time because now i have to do quaternions, multiplying etc etc for every voxel, instead of only the ones that are not empty..

Dang, well it was a good idea. Although...

If you don't mind not preserving any color information from some voxels, you could do a forward rotate as normal, then find gaps (still not sure how best to go about that), then do a reverse rotation back on the gaps to find out what colors are best for them. As for the aliased voxels, just pick the one object voxel that best describes that world voxel by being closest to its center (Manhattan should suffice) & stick with it. Kill the others. This would preserve volume & shape.

Reckon the marginal cases would still bite you in the ass sometimes though.

well i don't need color (all the voxels in a shape will be the same, and actors get created by using 20/30 ish of those shapes together) i believe i do need to preserve volume of smaller shapes though (but i am curious how it makes it simpler)

and yeah:
maybe i should just bite the bullet and describe the shapes as polygons, rotate the points of meaning and fill in the rotated shapes afterwards with voxels, it feels overkill/and will prolly introduce many new problems   but it might be alot more fail-safe at the end

I wouldn't do what you describe in the last para. You're already charting unknown territory with this stuff. Closest thing I can think of is voxelization of polygon scenes.

The reason it'd be simpler to have somewhat goofy volumes is because the root of all your problems is undersampling. Refer back to the diagrams. What if for each world voxel, instead of picking one corresponding object voxel, we let all the object voxels intersecting it affect it? The edges/faces intersecting, not just center points. So world voxels get color & volume from anything touching them in their 3x3x3 neighborhood.

This gets rid of the marginal case problem. Every single world voxel will have some faces intersecting it. It also simplifies the nonexistent color problem, because you don't need to pick the best, you just do a weighted interpolation between every intersecting object voxel (based on how much they intersect).

Trouble is gnarly volume inflation. Consider a cube inside a voxel & rotated s.t. the cube's vertices poke out all the voxel's faces. Well, then you need voxels for six neighbors. Obviously in real cases, an object's volume won't inflate by 6 times, but it's still pretty bad. They need to be big with chunky features for the nuances of the shape not to be lost. You could help this situation somewhat by considering the object voxels as physically smaller for the purposes of world voxel volume creation. Picking the smallest cube s.t. gaps are guaranteed eliminated would make a huge difference, couldn't say whether it'd be enough though.