Re: 3D Frustum Clipping
- From: "cr88192" <cr88192@xxxxxxxxxxxxxxxxxx>
- Date: Thu, 25 Aug 2005 08:37:44 +1000
"Robert W" <robertjw75@xxxxxxxxxxxxxxx> wrote in message
news:430cd60d$0$25524$afc38c87@xxxxxxxxxxxxxxxxxxxxxxx
> Nicholas Nash wrote:
>> Robert W wrote:
>>
>>>Hi All,
>>>
>>>I'm in the middle of creating of a software renderer. I am now up to
>>>the clipping stage. At this point I was wanting to perform clipping in
>>>camera space ( against the view frustum ). I've been able to
>>>successfully classify vertices as inside or outside the frustum and
>>>compute intersection of a line and a plane. What I am having trouble
>>>with, is an algorithm to clip a triangle to the frustum, ie. how to
>>>traverse the vertices and output the clipped vertices to the 'rendering
>>>list'. Any help would be greatly appreciated.
>>>
>>>Thanks.
>>>
>>>Robert
>>
>>
>> I imagine there is something in the FAQ about this. I'll try and help
>> anyway.
>> You seem to be 90% of the way there.
>>
>> I will describe what you need for a correct implementation, efficiency
>> can come later.
>>
>> All we need to be able to do is clip a particular triangle, say with
>> vertices { v1, v2, v3 } against a particular plane, P.
>>
>> There are just four cases:
>>
>> (i) All the vertices are on the side of the plane inside the
>> frustrum.
>> (ii) All the vertices are on the side of the plane outside the
>> frustrum.
>> (iii) 1 vertex of the triangle is outside, the other two are on the
>> are inside.
>> (iv) 2 vertices of the triangle are outside, the other one is
>> inside.
>>
>> Cases (i) and (ii) are simple, either do nothing to the triangle or
>> discard it, respectively.
>>
>> In case (iii), suppose v1 is outside, and so v2, v3 are inside. Then we
>> intersect v1v2 with P getting a new vertex v4, and v1v3 with P getting
>> a new vertex 5, Now we have a quadrilateral { v2, v3, v4, v5 }.
>> We might need to split this into two triangles, say { v2, v3, v5 } and
>> { v3, v4, v5 } for rendering.
>>
>> Case (iv) is even easier, suppose v1, v2 are outside, and so v3 is
>> inside.
>> Then we intersect v1v3 and v2v3 with P giving v4 and v5, and then we
>> have
>> the new triangle { v3, v4, v5 }.
>>
>> So you just do this for each triangle, against each plane in turn.
>>
>> Is this what you wanted?
>>
>> There are some good notes on clipping at:
>>
>> http://graphics.idav.ucdavis.edu/education/GraphicsNotes/Clipping/Clipping.html
>>
>>
>> All the best,
>>
>> Nicholas
>>
>
> Hi Nicholas,
>
> Thanks, yes that is what I was looking for. I just have question about
> the data structures next. Currently I'm using an array of vertices with
> each three vertices being a triangle ( I'll implement indexed vertices
> soon ). So, during clipping I use a 'temporary' array of vertices with 7
> elements to store any clipped vertices ( 7 elements being the absolute
> worse case if the vertices are outside different planes ). I then
> trianglulate these clipped vertices and add them to another array of
> vertices that is used by the renderer. Does this sounds reasonable?
>
yeah, I missed the 'triangles' part, so I described the algo for generic
polygons (used, eg, in my csg code and such...).
it sounds reasonable enough.
in my case at one point I did csg with triangles, and created a set of
nested if statements, eg:
if(DOT(v1)>dist)
{
if(DOT(v2)>dist)
{
...
}else ...
}else ...
also in this construction was some logic for putting vertices in a
predefined relative order for each case, and dealing with the all present
and all clipped away cases.
after this was just a check to determine if 1 or 2 vertices lie below the
plane (this was recorded), and the respective clip code.
alternatively, the clip code could have been specialized and left within the
if statements, but I didn't do it that way (in total likely more code).
> Also, isn't there another case? What if all the vertices are outside the
> frustum but the edge go through the frustum? For example, v1 is outside
> left plane, v2 is outside right plane and v3 is outside bottom plane.
> Does this ever happen and do I need to consider this? What about if the
> triangle 'straddles' a corner of the frustum, how does the corner get
> output? ( sorry about all the questions, they just keep coming as I think
> about the algorithm ).
>
none of this is a problem if the triangles are in turn clipped by each face
of the frustum. each time it becomes a single face clip, and multiple such
clips generate the desired faces.
so, in the case of a part of a triangle inside the frustum, it is first
clipped by one plane, leading to the inner part on that plane, then the next
one, leading to the clipped triangle.
as another simple example, for csg operations I typically initially create
"infinite" polygons, which are clipped by each plane in turn resulting in
the normal face polys.
for csg, slightly harder is clipping internal faces. in my case, a few flags
were used, eg, one to mark the face as "outside" of some plane, and another
to mark the face as completely "inside" some geometry (set if the outside
bit was never set).
afterwards, any faces marked as "inside" are then discarded.
a slight bit of fudging to this algo could likely be used for things like
subtraction (probably another flag used to mark faces as "negative", which
would effect treatment of the "inside" flag). the issue was one of never
needing to do this partly as the mapper tool did this for me...
> Thanks.
>
> Robert
.
- References:
- 3D Frustum Clipping
- From: Robert W
- Re: 3D Frustum Clipping
- From: Nicholas Nash
- Re: 3D Frustum Clipping
- From: Robert W
- 3D Frustum Clipping
- Prev by Date: Re: 2D Delaunay Triangulation Query
- Next by Date: 3d ocean
- Previous by thread: Re: 3D Frustum Clipping
- Next by thread: Re: 3D Frustum Clipping
- Index(es):
Relevant Pages
|
