Jump to content
  • Advertisement
Sign in to follow this  
fir

techniques for clipping 3d triangles/objects

This topic is 2143 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

I wrote a software rasterizer recently

 

[attachment=19092:tie3.png]

 

(this great model is taken from blender models com mady by 'admin')

 

 

This is working and I am happy but this is naively written (no asm no cache optymizations etc) and is slow (slower than it could be).

Especially my clipping code is weak.. I mostly just check if 2d triangle result lies in screen if no then clip, I also check some points of 2d triangle with depth buffer if no one is forward then clip the triangle (it is slightly inprecise but it is ok

for me). third - i also test if the whole triange lies back the camera plane then also clip.

 

I am looking for some techniques to do better clipping here.. preferably some easy ones in first, or medium hard, some hardest the last.. Could someone share some knowledge about such clipping?

 

 

Ps. (this model is 300 tys triangles in raw format (I wonder if i would split the data into vertexes and indexes it would fasten the drawing or slowing this... with indexes there is slightly less data probably but there in the code would be the look up for vertx instead of pure stream )

 

-----

EDIT

 

well after some thinking i invented something:

 

precomputing the visiblity, it goes such way:

 

from the given point of view (there are sphere of them)

some triangles of the model (say 30%) are visible

other (70%) are not - Divide this sphere on say 64

patches and precompute for every triangle if it is seen

from this 'patch' (it would be heavy to precompute,

for example cost of rendering a couple of frames 

from couple of places on the patches, the testet 

traingle the last to check if it pass the depth buffer -

so this is cost of 64patches x 5 places x noOfTriangles

so for example for this model 320x300 000 = 90 MFrames

this is a lot of precomputing :C but can be done i think)

then set the corresponding bit in some 64 word of flags

1 means form this patchg of visibility this triangle is seen

- that should be very simple to use and top eficient

clipping method :U - though this precomputation time scares me but this can be optymized (for example

it is easy to sign the triangles that goes out for sure,

it is harder to make sure the one that previously passed

will is totaly overvritten so it is also goes out, bout 

probably by rendering in changed direction and suming 

the onet that goes out will give the sum of the set that

is invisible)

 

I will try to implement it and check how it is working after some resting i shoul take

Edited by fir

Share this post


Link to post
Share on other sites
Advertisement

by clipping you mean actually culling? there is no point in clipping a triangle that is behind the camera or out of screen;)

 

well, I'd say it's not a problem of culling if your rendering is slow. culling is just throwing away of what you dont need to do, but the most time consuming parts are probably the ones that you actually render. one thing you haven't mentioned yet is 'backface culling', which is easy to add and if you don't have that, well, it should reduce your 'work' by 50%, but all the other culling options won't reduce pixel work probably and that's where you should probably investigate time into.

 

download AMD codeanalyst (or use any other profilng tool that you are familar with) and profile, you might figure out the top 3 functions take 95% of the time and culling just 5% and if you improve culling speed, you'd at best gain 5%. improving what matters might be really simple (codeanalyst will point out the lines of code in the functions that cost most) and you might see low hanging fruits e.g. by accident used double instead of float constants or something like that.

 

of course, you could make a capture and show us here those critical lines and we'd maybe be able to suggest you optimizations, that might be most efficient :)

 

 

with just 300triangles, there is not much to improve. seperating objects into clusters of maybe 30triangles to cull them by bounding box, but those will be just usefull if you don't see parts of the object. there is not much occlusion going on, so occlusion culling for your object might not be effective either.

Share this post


Link to post
Share on other sites

As to 'backface culling ' i did it by dot products camera dir and

face normal and throwing of face when its negative but it seem that not all models i use are cooked in such approach friendly way, 9some mixes both orientation of triangles and some treats some faces as a two sided.. so i off it

 

As to showing routines i could show it - it is badly (unaesthetically) written  - but maybe in separate thread and later

Share this post


Link to post
Share on other sites

camera direction is not fully correct, you need to use the direction between the eye position and one of the vertices of the triangle. otherwise you will cull too many triangles on at some places and too few at others. there are a lot of models cooked in a wrong way, but maybe in your tests it was just this bug and not the models -> fix it and test again ;)

 

for your culling idea, you just need  64patches x 5 places of frames. just render the object with a different color per triangle and then go over the frame and figure out what colors are in the framebuffer. all invisible triangles will have no color in the buffer. your idea is usually called 'pvs' "precomputed visibility set", you might find quite something about it on the net.

Share this post


Link to post
Share on other sites

camera direction is not fully correct, you need to use the direction between the eye position and one of the vertices of the triangle. otherwise you will cull too many triangles on at some places and too few at others. there are a lot of models cooked in a wrong way, but maybe in your tests it was just this bug and not the models -> fix it and test again ;)

 

for your culling idea, you just need  64patches x 5 places of frames. just render the object with a different color per triangle and then go over the frame and figure out what colors are in the framebuffer. all invisible triangles will have no color in the buffer. your idea is usually called 'pvs' "precomputed visibility set", you might find quite something about it on the net.

 

with this backface culling there is also something that

relies on direction of face vertices but i do net get 

it (how to implement it) As I said incidentally minority of models i use are compatible with this backface culling

(So indeed I did it but under the key toggle and it is mostly off)

 

As to PVS it seem to be good idea for me, the way you say still needs as much frames as triangles (well i could not write color but face ids then scan the result - but my mentioned way draw the triangles container forward draw them backward (meybe yet some couple of other direction) and then sum all that sets which off as a invisible set for

that position - THEN repeat this for couple points on patch

and take common subset of invisibles would suffice

 

- now i am slightly tired to implement it but will try it

later, I only counted per frame the percent of triangles

that passed to 2d rasterisations versus all 3d triangles 

sent and it vary between 10% to 50% (usualy only 30%

pass to 2d) so this is ok

 

as to bounding volume - do you know how this is build?

in preprocesing loops is sorted to wirtual boxes? then if

this is sorted, can it be used only to skip the boxes 

that are out of frustrum, yea? It is not helping to cut (cull) of

the rear boxes behind the front boxes?

Share this post


Link to post
Share on other sites
As to PVS it seem to be good idea for me, the way you say still needs as much frames as triangles (well i could not write color but face ids then scan the result -

 

as to bounding volume - do you know how this is build?

in preprocesing loops is sorted to wirtual boxes? then if

this is sorted, can it be used only to skip the boxes 

that are out of frustrum, yea? It is not helping to cut (cull) of

the rear boxes behind the front boxes?

 

different colors == face ids

 

 

I'm not sure what you mean by your bounding box question. the bouding box of objects is usually build as preprocessing, yes. but it's per object usually, so you have one volume per object, usually.

but PVS is usually implemented on a finer level for objects, you save per face/triangle if it is visible.

e.g.

http://www.bluesnews.com/abrash/chap64.shtml

(but that's an old thing, today it's barely used for objects).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!