Archived

This topic is now archived and is closed to further replies.

Using face normals for back-face culling

This topic is 5505 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all. I am having some problems with understanding normals... I want to use them for back-face culling, and I think if I get this to work, then I may know how to use them for light-sourcing, etc... The problem is... If I have a triangle. - X , Y , Z 0 - 85 , 100 , 80 1 - 200 , 75 , 60 2 - 100 , 50 , 40 ;In anticlockwise order :-) I know how to get the surface normal (is this right?) Firstly, I get two 2 vectors from this triangle Vector1X = triangle(0 , 0) - triangle(1 , 0) ;Vector 1 -> 0 Vector1Y = triangle(0 , 1) - triangle(1 , 1) Vector1Z = triangle(0 , 2) - triangle(1 , 2) Vector2X = triangle(1 , 0) - triangle(2 , 0) ;Vector 2 -> 1 Vector2Y = triangle(1 , 1) - triangle(2 , 1) Vector2Z = triangle(1 , 2) - triangle(2 , 2) Next I find the magnitude of both these vectors Mag1 = Sqr((Vector1X * Vector1X) + (Vector1Y * Vector1Y) + (Vector1Z * Vector1Z)) Mag2 = Sqr((Vector2X * Vector2X) + (Vector2Y * Vector2Y) + (Vector2Z * Vector2Z)) Next, I normalise these vectors Vector1X = Vector1X / Mag1 Vector1Y = Vector1Y / Mag1 Vector1Z = Vector1Z / Mag1 Vector2X = Vector2X / Mag2 Vector2Y = Vector2Y / Mag2 Vector2Z = Vector2Z / Mag2 Finally, I get the normal components for the triangle face. NormalX = Float Vector1Y * Vector2Z - Vector1Z * Vector2Y NormalY = Float Vector1Z * Vector2X - Vector1X * Vector2Z NormalZ = Float Vector1X * Vector2Y - Vector1Y * Vector2X Now, this data I have stored at the start of my program for every triangle face I use. Every time I rotate the triangles around their axis'' I also rotate all the Normals...so, they should be facing away from their respective triangle no matter what... But I am stuck on the math behind actually using this data to determine if the triangle is facing away from me. Could anyone help ? Thanks, in advance. :-)

Share this post


Link to post
Share on other sites
first, get the vector pointing from your camera position to the triangle. then, compare the angle between that ray and the triangle normal. if the angle is 0-90 then it's back facing. if it's 90-180 then it's front facing. to be a bit more efficient, rather than casting a ray you can probably just take the near clip plane surface normal and use that for all your tests. i would guess that the slight errors you will get will not be all that visually significant. you might drop/add a few extra triangle but it would probably not be noticable.

as an aside, it seems like it might help you a great deal to spend some time learning more linear algebra so a lot of this stuff can become a little bit more sensical. a broad overview of what is a normal/vector/point/plane/etc would probably give you a really intuitive grasp of the subject.

-me

[edited by - Palidine on November 20, 2002 1:46:48 PM]

Share this post


Link to post
Share on other sites
just check the normal.z value...


if (normal.z < 0)
{
DrawTriangle();
}
else
{
DontDrawTriangle();
}

If the normal is facing towards you (it''s pointing in the negative direction) then you are seeing the triangle from the front, otherwise, it''s facing backwards, so don''t draw it.

Billy - BillyB@mrsnj.com

Share this post


Link to post
Share on other sites
By the way.. if the only thing you use it for is face culling.. you don''t even need the normalx and normaly values . But if you are using it for color.. then you do need these.

Share this post


Link to post
Share on other sites
Ready4Dis''s method will only work if you are transforming world coordinates rather than transforming camera coordinates between renders. i.e. the move the world, not the camera method of motion. if you move the camera about, then the object''s normals will never change. it definitely doesn''t matter which method you choose, b/c either way you do the same number of transforms. just a heads up.

-me

Share this post


Link to post
Share on other sites
"Every time I rotate the triangles around their axis'' I also rotate all the Normals...so, they should be facing away from their respective triangle no matter what..."

He''s rotating the triangles + normals.

Share this post


Link to post
Share on other sites
Yeah, thanks. I have these details, and just tried the NormalZ comparison, but it isnt working...the thing is, I''m rotating my triangle for camera space, but I''m not sure how to rotate the normal I have stored...I am currently rotating it along with my vertices. Either way, the Z Comparison isnt working....

Bugger!

Any ideas ?


The normals have been stored, just like the vertices, then all are rotated by the overall angles...then these values are used for the current frame...

:-)

Share this post


Link to post
Share on other sites
Theres something up with my rotations with the normals...I got the Z comparision to work, and also display the normal as I''m using it...the triangle is disappearing and reappearing when it shouldnt...Am I to rotate the normals as I would vertices...i.e. around a central axis...and in this way, can I think of the normal as a vertice?

:-)

Share this post


Link to post
Share on other sites
Yes, when I wrote my software engine, I rotated normals along with the vertices. But, you must rotate it around it''s own center, not the triangle, or camera''s center. Otherwise, it would no longer be a normal .

Share this post


Link to post
Share on other sites
Thanks you guys who replied...for the Z Check especially as it works...

It turns out I had a faulty set of rotation formulas, which didnt correspond to the rotations of the vertices...those vertices and normals were outta whack !!!



:-)

Share this post


Link to post
Share on other sites
Also, it may help to DISPLAY your normals on the triangles surface (as a 3d triangle or 3d line).

As a line, you simply go from triangle center -> triangle center + (normal * length).

this way, you can watch and see if your normals are acting the way they should.

Share this post


Link to post
Share on other sites
No problem. If you need anything else, let us know (or you can email me if you want). I know how lighting works with normals too, so if you ever need anything .

Billy - BillyB@mrsnj.com

AOL IM - CrazyGuy4Eva
MSN Messenger = Ready4Dis_1@hotmail.com

Share this post


Link to post
Share on other sites
Yup, agreed on the learning basic vector maths. Add some matrices and spaces on there. It makes this stuff SOOOO much easier to understand. You''ll be walking around with your eyes closed, you''ll never really know what''s going on with the code and you''ll miss some really obvious optimisations if you don''t!


The part labeled "Finally, I get the normal components for the triangle face" is actually a "cross product" (aka the vector product).

You can find the [cosine of the] angle between the normal vector and the [normalised] view vector with the "dot product" (aka the scalar product).


Something very important which you haven''t told us is what "space" the normals are in:

a) Have the normals been transformed into world space? (i.e. multiplied by the object->world transformation matrix).

OR

b) Have the normals been transformed into camera space? (i.e. multiplied by the object->world AND world->view matrices).

OR

c) Have the normals not been transformed at all? (i.e. still as they were defined when the vertices were created).


For the dot product of two vectors to work properly, the vectors MUST be in the same "space":

The method "Palidine" gives relies on the normals being in world space. [implied]

The method "Ready4Dis" gives relies on the normals being in view/camera space (option b).


Another method not mentioned is to not transform the normals at all (less computation work if there are a lot of normals) and instead transform the view vector into the same "space" as the normals are ("object space").
To do this you transform the view/camera direction vector by the inverse of the world->view matrix and the inverse of the object->world matrix (you can concatenate the two and take the inverse of the result instead).

Take the dot product of this vector with each normal.


Of course if you''re using hardware rendering, DON''T do your own backface culling - the hardware does it for you far, far faster than you will with the above. If you can''t cull say, 50-100 polygons with a few instructions, then don''t bother, you''ll end up wasting more time than you save!

Things to definately put a bookmark in/ok:

A book: "Mathematics for computer graphics applications"
A website: http://mathworld.wolfram.com
A website: http://www.cs.ualberta.ca/~andreas/math/matrfaq_latest.html
A website: http://www.cs.ualberta.ca/~andreas/math/vectfaq_latest.html

--
Simon O''Connor
Creative Asylum Ltd
www.creative-asylum.com

Share this post


Link to post
Share on other sites
quote:
Original post by Palidine
Ready4Dis's method will only work if you are transforming world coordinates rather than transforming camera coordinates between renders.
I highly doubt even that. I'm doing this and i tried his approach and it doesn't work (as i expected). The dot-product way of doing the culling works. I made a small pic to illustrate the problem:



A, D and E in this example will be culled by both methods, but B will be culled too by using the z<0 method while it won't be culled by using the dot-product (which is correct...B is visible in this example)...or am i not understanding Ready4Dis's method?


[edited by - EgonOlsen on November 20, 2002 2:38:35 PM]

Share this post


Link to post
Share on other sites
Yeah...

Firstly I get the Normals for each triangle BEFORE anything is done and save it.

MAIN LOOP
[

ROTATE and THEN TRANSFORM ALL vertices into camera space.
ROTATE all normals

DRAW TRIANGLES based on NORMAL

]

Yeah...I''m not too sure about the Z>0 code...as I have a few triangles being drawn that shouldnt be (as soon as they should hide, they continue for a few frames) and also, other triangles are appearing just after they should be....hmmm...

:-)

Share this post


Link to post
Share on other sites
BTW...

I am using BlitzBasic2D to come up with my own 3D engine, as to learn from scratch...I dont like C/C++ because I find it hard to keep track of all the files .h and the like...plus Blitz is ready to work right away, no hassle.

Also, I''m not too sure about matrices...

here is a snip of my rotation code for my program.



For cnt = 0 To vertice_amount

;XROT
Tvert(cnt , 1) = Vert(cnt , 1) * kcos(ang_x) - Vert(cnt , 2) * ksin(ang_x)
Tvert(cnt , 2) = Vert(cnt , 2) * kcos(ang_x) + Vert(cnt , 1) * ksin(ang_x)

;YROT
TVert(cnt , 0) = Vert(cnt , 0) * kcos(ang_y) - TVert(cnt , 2) * ksin(ang_y)
TVert(cnt , 2) = 1500 + (Tvert(cnt , 2) * kcos(ang_y) + Vert(cnt , 0) * ksin(ang_y))

;ZROT
temp = TVert(cnt , 0)
TVert(cnt , 0) = 1000 + (TVert(cnt , 1) * ksin(ang_z) - temp * kcos(ang_z))
TVert(cnt , 1) = 1000 + (TVert(cnt , 1) * kcos(ang_z) + temp * ksin(ang_z))

;PROJ
OneOverZ = 1 / (TVert(cnt , 2) - camz)
TVert(cnt , 0) = ((camx - TVert(cnt , 0)) * MULTIPLANT) * OneOverZ + HALFX
TVert(cnt , 1) = ((TVert(cnt , 1) - camy) * MULTIPLANT) * OneOverZ + HALFY
TVert(cnt , 2) = Tvert(cnt , 2) - camz

Next



There is some optimisations in there, but what could a matrix system do that this isnt...I''m interested, because I have heard they are faster, but still...I dont really know how they work (and dont really have the desire to read up on them).


:-)

Share this post


Link to post
Share on other sites
Oh, and BTW, here is a snipped of code I found (probably nothing new) on a piece of source code I erm, borrowed it from, ahem.

If (x3-x1)*(y2-y1)-(x2-x1)*(y3-y1)>=0 then drawtriangle()

Where the x is the Xcomponent of vertice 3 of a triangle...AND it works...and requires NO normal code or ANYTHING !!!!!

Obviously tho, I want the normal code for directional light sources...:-)

:-)

Share this post


Link to post
Share on other sites
quote:
Original post by GuybrushNivek
If (x3-x1)*(y2-y1)-(x2-x1)*(y3-y1)>=0 then drawtriangle()

Looks like it's "hacking together the culling"-day...
What's that? I tried that too (i'm always open for learning new things) and it failed too (at least in my case). Why not simply use the dot-product like

q=(pxk*p1x+pyk*p1y+pzk*p1z);

Were p?k represents the normal vector and p1? is the vector from the origin to a vertex of the triangle. This works!
This thread really scared me, because i was thinking that was doing something much too complicated for years now, but i think that i just did it right...

Edit: I thought about the formula above (not mine...the one at the top.. ) and i think that it's the same as testing for z<0. I did a compare of the two (faulty) methods in my engine and the results looked exactly the same (i.e. the same errors).



[edited by - EgonOlsen on November 20, 2002 3:31:13 PM]

Share this post


Link to post
Share on other sites
okay...this is getting confusing...

I have:

A = Triangle(0 , 0)
B = Triangle(0 , 1)
C = Triangle(0 , 2) ; The 1st vertice of the said triangle

Because I have rotated all the points(around their own axis) and transformed them, how do I get the vector from my camera to the 1st point in the triangle ?!? Yikes, I''m having a minor brain meltdown here !!!

:-)

Share this post


Link to post
Share on other sites
BTW...for the record, the last formula I gave DID work on my engine, error free...I dont think its faulty, maybe just sensitive to the engine(heck, I dunno!!!) :-D


I think, maybe the order I am doing things in is causing the error...when exactly did you (EgonOlsen) actually test for backfacing ? Did you do it before you transformed the already rotated stuff into camera space (all these different spaces are giving me a headache!!)

:-)

Share this post


Link to post
Share on other sites
Following your description of what you are doing i assume that you are rotating and translating your vertices in a way that your camera is always placed at the origin (i.e. if your virtual camera is at (10,10,20) you translate your vertices by (-10,-10,-20)) and your world moves around it. Am i right? If, then simply take the vertex data from the triangle because this is already the vector from your camera (0,0,0) to the vertex. If not, your vector is -c+a where c is the camera position and a the triangle vertex.

Edit: To answer your question: I'm doing backface culling in camera-space in this particular engine.


[edited by - EgonOlsen on November 20, 2002 3:59:40 PM]

Share this post


Link to post
Share on other sites
No, actually...

The object is rotating around itself...and is then added into space...(eg...all vertices are added 1000....so the objects centre is at 1000 , 1000 , 1000)

My camera can zoom and zoomout is all, but occupies its own coordinates...I have addressed the problem in my engine tho...I translate my coordinates last...(I rotate them and the normals first, then cull) and THEN add the perspective translation to the vertices...It works fine. :-)

BTW, the link you sent, the Java applet...was this you...it is cool.

:-)

Share this post


Link to post
Share on other sites
Well, what i really meant was: Are you doing culling in camera-space?

Edit: The applet is just a simple demonstration of what is possible with the engine. But software rendering (even in Java) is quite a small market...

[edited by - EgonOlsen on November 20, 2002 4:34:12 PM]

Share this post


Link to post
Share on other sites
Ready4Dis: Your algorithm is wrong. I know many people use it, nevertheless it is wrong. Have a close look at EgonOlsen´s picture and you can see that a triangle can be visible even though the normal is pointing away from you (with your method B will be culled away even though it is visible).

quote:
Original post by GuybrushNivek
If (x3-x1)*(y2-y1)-(x2-x1)*(y3-y1)>=0 then drawtriangle()



Let´s have a look at what the above is doing: It is calculating the z component of a cross product of the vectors (x3-x1, y3-y1) and (x2-x1, y2-y1), and thus calculates the z of a normal vector.

So you do a z>=0 test.

This test is correct, if you use x1, x2, x3, y1, y2, y3 as coordinates _after_ doing the projection (i.e. after dividing each of them by z). Then it will work. Otherwise it is just wrong.

Share this post


Link to post
Share on other sites