| |
Oswald
Registered: Apr 2002
Posts: 5094 |
accurate 3d rotation
some silly questions & a lot of text here, its been ages I have done this routine and I am wondering where could I find more accuracy.
I am using the additive method to get the rotation matrix, working with 16 bit sines.
first, I wonder why have I choosen the sinetable max value to be +/- $1fff, there's no consecutive 4 adc's to have overflow over +/- $8000, still an adc / sbc pair may turn into adc/adc because of the case when substracting a negative number? :/ not sure if sine lookups may align this way. also should I round the 16 bit table or those bits will go bad anyway? (dont remember if I have rounded it, boy its been precalculated in basic in the stone ages:)
secondly, I keep adding #$40 to rotation angles in many places before looking them up in sincos tables. I suspect I am doing something wrong here, trying to turn the lookup value into cosine, while still having a label for the cosine offset. sin+$40= cosine, cosine+(angle+#$40)= ??? why ? :D or does this thing come from the sin*cos to addition theoremes?
third: if I recall right each adc/sbc introduces 1 bit error, is this true? so after 2 adc lowmost 2 bits in the 16 bit result is unusable?
fourth: flipping sign of a 2 complement 16 bit number is this correct?:
lda yxl ;*-1
eor #$ff
clc
adc #$01
sta yxl
lda yxh
eor #$ff
adc #$00
sta yxh
finally, getting a cube coordinate out of the rotation matrix, only using the HI bytes:
lda xzh ;mpp
clc
adc xyh
sec
sbc xxh
sta vertexes+0
should I rewrite this to gain accuracy including the low 8 bits?:
lda xzl
clc
adc xyl
sta templ
lda xzh
adc xyh
sta temph
...
etc
finally, rounding the final8 bits by looking at the low8 is a good idea? ie, if low8 (signless) msb is high, inc high8 bits? |
|
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
1. You want your input sines to be as accurate as possible, i.e. as many bits as possible and correctly rounded.
2. Sounds weird, but can be part of some older optimizations you did.
3. Since the input sines where rounded in the first place you really can't trust the least significant bit. So adding two untrusted bits will give you a really untrustworthy bit. :)
4. It is correct, but slow. See http://codebase64.org/doku.php?id=base:seriously_fast_multiplic..
5. Depends on what you wanna do. If you only place vector bobs or plots you only need HSB. But if you wanna to subpixel accurate bresenham you will init it with the LSB.
Hope that clarified some.... :P |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
#1 I will try to write a new sine gen, btw I am never sure, one should _ALWAYS_ correct with adc #$01 after eor #$ff ?:) (ie even when storing to table)
I dont get what you mean in #4, btw I have utilised your mul routine, but accuracy didnt change, I hoped you did it more accurate than me, but its "only" faster ;) probably I can get rid of sign flipping by better ordering tho.
#5, so you say using only HSB results in rock solid vertex movement?
also I have a problem with backface culling, I am calculating Z of the normal and it is of in about 5% of the frames, in edgy cases. is there a better method, somehow determine winding (order of vertices) with additive formulas or tables? In the past I got rid of this problem by some trial and error asl/lsr of the result, but I'd like a perfect solution. |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
Quote: #1 I will try to write a new sine gen, btw I am never sure, one should _ALWAYS_ correct with adc #$01 after eor #$ff ?:) (ie even when storing to table)
I dont get what you mean in #4, btw I have utilised your mul routine, but accuracy didnt change, I hoped you did it more accurate than me, but its "only" faster ;) probably I can get rid of sign flipping by better ordering tho.
#5, so you say using only HSB results in rock solid vertex movement?
also I have a problem with backface culling, I am calculating Z of the normal and it is of in about 5% of the frames, in edgy cases. is there a better method, somehow determine winding (order of vertices) with additive formulas or tables? In the past I got rid of this problem by some trial and error asl/lsr of the result, but I'd like a perfect solution.
#4 i mean for sign-handling...
#5 yes. 8 bits result in 256 rocksolid positions. :)
Backface culling: determine which side of the poly the cam is. For a cube it's very simple. Theory:
Plane equation = ax+by+cz+d=0 abc=plane normal.
If the above is >0 then xyz is on the normal side of the plane, i.e. In-front or visible.
We know the cam is at origo+some z-dist hence we only get:
cz+d=0
Z is constant, i.e. The added z-dist to the object to get it in front of the cam. D is also static and only depends on the object, for a cube with size 1 D will be 1. So shuffle:
Z=-d/c
The -d/c is constant per face in the object, hence:
Z=k
Now z is the z-component of the normal. For a cube it's simply one of z-values of your vectors in the rotmatrix.
So to backface cull a side of the cube u have ALL already calced except for a cmp.
Simply look up the correct z-value in the rot matrix and cmp by the precalced K per face. if it's hard to get then picture each row in the rot-matrix defining the world axises of the rotated space. In normal unrotated space the x-axis is the normal to the sides od the cube. The y-axis to the top and bottom... Same in rotated space but the the x-axis isn't simply 1,0,0 but some x,y,z and u only need the z-value since the cam is in origo. |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
I have to think on this one, sounds like a method graham described earlier. does it work with perspective projection? |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
Quote: I have to think on this one, sounds like a method graham described earlier. does it work with perspective projection?
It's the exact same method but Graham uses another way of thinking but yields the same result. I'll draw u a pic tonight. Yes, it works with perspective (it's built into the -z/d part, -z is really your distance to the screen which determins field of view) |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
According to your answers I do everything to the book, I think my perspective projection might be the problem (zooming more than available bits), thanks, and waiting for the pic, its really hard to get it by words :) |
| |
chatGPZ
Registered: Dec 2001
Posts: 11386 |
Quote:you really can't trust the least significant bit. So adding two untrusted bits will give you a really untrustworthy bit.
i'll print that on a t-shirt :) |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
Quote: Quote:you really can't trust the least significant bit. So adding two untrusted bits will give you a really untrustworthy bit.
i'll print that on a t-shirt :)
:) one up!
Anyway, after rounding you are of at worst by 0.5 i.e. Half a bit. Each add will propagate the error so after n additions u'll be of by n/2. |
| |
Bitbreaker
Registered: Oct 2002
Posts: 508 |
As for negation of a 16 bit number see the example in http://www.codebase64.org/doku.php?id=base:advanced_optimizing#..
in general it is a good thing to think about swapping add/sbc at times also in term of saving clc/sec. Means, you can always add one too much and then again subtract one too much if carry has the wrong state and such and order your addition/subtraction that way that you merely never need to explicitely set the carry. |
| |
chatGPZ
Registered: Dec 2001
Posts: 11386 |
or just comment out all CLC and SEC and make a smash design demo =) |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
Quote: According to your answers I do everything to the book, I think my perspective projection might be the problem (zooming more than available bits), thanks, and waiting for the pic, its really hard to get it by words :)
Wrote an article. It's the attached PDF at the bottom of this page: http://codebase64.org/doku.php?id=base:backface_culling |
| |
Ervin
Registered: May 2008
Posts: 14 |
An old 3d trick is (regardless of the platform) is to back-transform the camera [and the lights] to object space (using the inverse of the transformation matrix) and do the culling [and lighting] in object space. It's trivial to calculate the inverse of a rotation + translation matrix, see http://www.cg.info.hiroshima-cu.ac.jp/~miyazaki/knowledge/teche.., it's one matrix-vector mul.
The algorithm:
1. back-transform the camera to object space (1 vector-matrix multiplication)
2. substitute this camera position to the equation of faces (3 muls and 4 adds). If it's negative, then drop the face.
[3. For the non-dropped faces: do the same with the object-transformed light positions (if negative, the corresponding face is not lit by the light-in-question)].
4. Transform ONLY those vertices, using the real transformation matrix, that belong to visible faces. Maybe it's not worth in a case of a cube when 7 of 8 vertices may be visible, but for a dodecahedron it really works better. |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
Quote: An old 3d trick is (regardless of the platform) is to back-transform the camera [and the lights] to object space (using the inverse of the transformation matrix) and do the culling [and lighting] in object space. It's trivial to calculate the inverse of a rotation + translation matrix, see http://www.cg.info.hiroshima-cu.ac.jp/~miyazaki/knowledge/teche.., it's one matrix-vector mul.
The algorithm:
1. back-transform the camera to object space (1 vector-matrix multiplication)
2. substitute this camera position to the equation of faces (3 muls and 4 adds). If it's negative, then drop the face.
[3. For the non-dropped faces: do the same with the object-transformed light positions (if negative, the corresponding face is not lit by the light-in-question)].
4. Transform ONLY those vertices, using the real transformation matrix, that belong to visible faces. Maybe it's not worth in a case of a cube when 7 of 8 vertices may be visible, but for a dodecahedron it really works better.
Kinda the same as my method but instead of invtransform the cam i use the fact that the cam is at 0,0,-z which reduce the plane equation alot. Everything becomes constants except the surface normal (which is static in your method, i.e. Good for complicated objs). The thing is, you dont really need to rotate specific normals since most of the are trivial to deduce from the rotation matrix. For a cube f.e. The normals corresponds to the world axes... |
| |
The Human Code Machine
Registered: Sep 2005
Posts: 112 |
For most cases there is a much easier way of backface culling polygons from convex objects. We used this simple approach on the Amiga and I think it was also described in a german paper magazine. It was an 3D article series by Sim/Razor 1911 I think... I found the same explanation in the web: http://www.hugi.scene.org/online/coding/hugi%2016%20-%20co3d15... Point 7 describes how to do it the easy way ;) |
| |
Bitbreaker
Registered: Oct 2002
Posts: 508 |
THCM: And then again you are at the SAM (Signed Area Method) as i described at codebase64 above the additions from JackAsser :-) Although i can't tell if his approach is faster, would be worth a proper comparison on some popular objects. |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
whats in the tables tmath1&2? |
| |
Bitbreaker
Registered: Oct 2002
Posts: 508 |
That's the square tables for babylonian multiplication. |
| |
The Human Code Machine
Registered: Sep 2005
Posts: 112 |
Bitbreaker: Yeah, but you're not using the simple reject test. |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
Quote: THCM: And then again you are at the SAM (Signed Area Method) as i described at codebase64 above the additions from JackAsser :-) Although i can't tell if his approach is faster, would be worth a proper comparison on some popular objects.
For a cube a single CMP-instruction is faster that anything else. Just bake the constants in the object. The normals are implicitly rotated since they're actually the vectors in the rotation matrix. So, simply take the values of the last row of the rotation matrix. Kinda like:
; left-side
lda rot_2_0 ;z-part of the left-side's surface normal corresponds to the z-value of the rotated world x-axis
cmp #konstant
bmi culled
Similar for the other sides of course. |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
Quote: For most cases there is a much easier way of backface culling polygons from convex objects. We used this simple approach on the Amiga and I think it was also described in a german paper magazine. It was an 3D article series by Sim/Razor 1911 I think... I found the same explanation in the web: http://www.hugi.scene.org/online/coding/hugi%2016%20-%20co3d15... Point 7 describes how to do it the easy way ;)
This method is a classic. A major drawback though: Requires rotation and perspective before culling => not so good. Also it requires a strict vertex order of the faces.
The method I proposed also have drawbacks of course: static camera + static objects + requires you to rotate the surface normals. However rotating surface normals for simple objects are mostly already done implicitly by taking a deeper look at the rotation matrix.
Both methods requires no additional multiplications etc which of course is a good thing. However, most often for demo-like objects all the information in the rotation matrix together with the vertex data is enough to determine surface visibility if you just attach some constant-values to each surface which you precalc when you generate the object. |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
Quote: That's the square tables for babylonian multiplication.
should made it clear in the article :) |
| |
Bitbreaker
Registered: Oct 2002
Posts: 508 |
Quote: should made it clear in the article :)
Well, the articles base on each other, as the multiplication is used also during rotation and such. But it sure wouldn't hurt to add some comments to the code, yes :-) |
| |
theWizard
Account closed
Registered: Jul 2007
Posts: 109 |
3d on a 64 , driller was wrong , 3d on a c64 should be illegal mate , it just looks wrong allways has allways will. |
