Clipping Algorithms
The Graphics Pipeline
attributed geometry – Δ
Model Transform
Perspective Projection Scan Conversion
Viewing Transform
3D Clipping Lighting, Shading, Texturing
image -pixels
2
Clipping
• 3Dclippingtoviewingfrustum
• 2D clipping to windows and viewports
• Today:Lineclipping,polygonclipping 3
Images courtesy of MIT
3D Clipping • Why REALLY Clip?
4
• Why REALLY Clip? – Save computation
– Memory consistency – Division by 0
3D Clipping
5
Clipping
• 3Dclippingtoviewingfrustum
• 2D clipping to windows and viewports
• Today:Lineclipping,polygonclipping 6
Images courtesy of MIT
Culling:
Clipping:
Culling and Clipping
• Rejectsvia bounding volumes
• Partiallyvisibleobjects need to be clipped against convex polygon (polytope)
• Bounding volume hierarchies for entire scenes
7
Cases
• Insideconditionforpoint(x,y)
• Cases:
xmin xxmax ymin y ymax
– Both vertices inside no clipping
– Both vertices outside clipping may be necessary
– One in one out clipping algorithm
• Bruteforce:explicitcomputationofallsegment-
segment intersections
8
Line Clipping in 2D
9
Cohen-Sutherland Algorithm
• Classical line clipper
• Trivial accept and trivial reject
• Iterative subdivision strategy
• Plane partitioning using 4 bit code
10
Outcodes – Example
Line Code1 Code2 C1C2 C1C2
AB 0000 0000 0000 0000 CD 0000 1000 0000 1000 EF 0001 1001 0001 1001 GH 0100 0010 0000 0110 IJ 0100 0010 0000 0110
11
Iterative Subdivision
• Selectavertex(outside)
• Priorityrankingofwindowedges
• Dividelineatintersectionwithedgeofhighestpriority
• Deletelinesegment(pointintersection)
• Compute outcode
• Iterateuntiltrivialacceptoftrivialreject
0100
1010 0010
12
#define NIL 0
#define LEFT 1
#define RIGHT 2
#define BOTTOM 4
#define TOP 8
short CompOutCode(float x, float y) { short outcode ;
outcode = NIL;
if (y > ymax)
outcode |= TOP; else if (y < ymin)
outcode |= BOTTOM; if (x > xmax)
outcode |= RIGHT; else if (x < xmin) outcode |= LEFT;
return outcode; }
C-Code
13
}
outcode0 = CompOutCode(x0, y0); outcode1 = CompOutCode(x1, y1); do {
if (!(outcode0 | outcode1)) { accept = TRUE; done = TRUE;
/* trivial innerhalb */
}
else if ((outcode0 & outcode1))
/* trivial ausserhalb */
done = TRUE; else {
C-Code
void CohenSutherlandLineClipAndDraw(float x0, float y0, float x1, float y1) { int accept = FALSE, done = FALSE;
float x, y;
short outcode0, outcode1, outcodeOut;
if (outcode0) outcodeOut = outcode0; else outcodeOut = outcode1;
if (outcodeOut & TOP) { x = x0 + (x1 - x0)*(ymax - y0)/(y1 - y0); y = ymax; }
else if (outcodeOut & BOTTOM) { x = x0 + (x1 - x0)*(ymin - y0)/(y1 - y0); y = ymin; } else if (outcodeOut & RIGHT) { y = y0 + (y1 - y0)*(xmax - x0)/(x1 - x0); x = xmax; } else if (outcodeOut & LEFT) { y = y0 + (y1 - y0)*(xmin - x0)/(x1 - x0); x = xmin; } if (outcodeOut == outcode0) { x0 = x; y0 = y; outcode0 = CompOutCode(x0, y0); }
else { x1 = x; y1 = y; outcode1 = CompOutCode(x1, y1); }
}
} while (!done);
if (accept) Line(x0, y0, x1, y1);
14
Parametric Clipping
• Cohen-Sutherland good for small and large windows
• Poorworstcaseperformance
• Computesmanyunnecessaryintersections
Parametric Clipping (Liang-Barsky Algorithm)
15
Idea
• Computeintersectionin1Dparameterspace
of the line
P(t)P (PP)t t[0,1] 010
16
Parametric Form • Parametric form of a line
P(t)P (PP)t t[0,1] 010
• Intersection point
N (P(t)P )0
• Insert
N (P P )
t • D = P1 – P0
i 0 E1 Ni D
i E1
17
Classification of Intersections • Classification of entry points (PE) and
leaving points (PL)
18
Tests and Conditions • Testofallt[0,..,1]
• Entryandleavingpointscomputedby N•D0PE N•D0PL
• Computemaximumandminimum
t max(t ,P ) t min(t ,P )
E EiEi L LiLi
• If tE > tL no relevant intersection 19
Look-up Table
Due to the zeros in the normal vector the point PEi is canceled out in the final equations
20
} }
*visible = TRUE; else {
tE = 0;
tL = 1;
if (CLIPt(dx, xmin – *x0, &tE, &tL))
if (CLIPt(-dx, *x0 – xmax, &tE, &tL)) if (CLIPt(dy, ymin – *y0, &tE, &tL))
if (CLIPt(-dy, *y0-ymax, *visible = TRUE;
if (tL < 1) {
&tE, &tL)) {
} }
*x1 = *x0 + tL
*y1 = *y0 + tL
* dx; * dy;
}
if (tE > 0) {
*x0 = *x0 + tE
*y0 = *y0 + tE
* dx; * dy;
C-Code
void Clip2D (float *x0, float *y0, float *x1, float *y1, boolean *visible) {
float tE, tL;
float dx, dy;
dx = *x1 – *x0;
dy = *y1 – *y0;
*visible = FALSE;
if (dx == 0 && dy == 0 && ClipPoint(*x0, *y0))
21
boolean CLIPt (float denom, float num, float *tE, float *tL) { float t;
}
boolean accept; accept = TRUE; if (denom > 0) {
/* entry */
t = num/denom; if (t > *tL)
accept = FALSE; else if (t > *tE)
*tE = t; }
else if (denom < 0) t = num/denom;
if (t < *tE)
{
/* leave */
accept = FALSE; else if (t < *tL)
*tL = t; }
else
if (num > 0)
/* parallel */
accept = FALSE; return accept;
C-Code
22
Polygon Clipping in 2D
23
2D Polygon Clipping
• Definitionofaconvexpolygon pi
P {p1,..,pn }
convex
concave
i, j[1,n]:pipj P
• Convexcombination
conv(P):{ λp λ 0,
nn
i1
iii
i1
λ 1} i
24
Convexity Test
• Use determinant of adjacent edge vectors
ei +
+
+
++ +
+
+
signs uniform
signs mixed
ee 1x 2x
ee 1y 2y
+ –
25
Sutherland-Hodgeman Algorithm
• Iterative subdivision (clipping window convex)
• Produces intermediate polygon lists {Pi}
26
Clipping of Polygon Edges
• Reducestoclippingofindividualpolygon edges
27
Example • Polygon with unit square
28
Inside-Outside Test • Define polygon counterclockwise
…
pi+1
q
c(qpi)(pi1 pi) outside if cz > 0
pi
29
Liang-Barsky Algorithm
• Parametricclipping
• Walkaroundpolygon
• Foreachedge output endpoints of visible part
• Sometimesturningvertex is needed!
• When?
30
2D Regions
• Uses subdivision of the window plane
inside 2 inside 3
inside 3 inside all 4 inside 3
inside 2 inside 3
inside 2
inside 2
31
Liang-Barsky Algorithm
• Turningvertexneeded when polygon touches inside 2 region
• Eachtimeanedge enters “inside 2” region add turning vertex
32
Unnecessary Corners
• Unnecessaryvertices do not cause artifacts inside visible window
33
• Segmentinparametricform • tin1 < tin2 , tout1 < tout2 tout1 window tout2 window tin2 tout2 tin2 tin1 tin2 < tout1 tout1 tin1 Two Cases p(t)p0 t(p1 p0) • Ingeneralcorrespondinglinecuts4times: 34 tin2 > tout1
tin2 tin1
window tin2 tout1
tout1 window
tout2
tout2
• Part of segment visible: tout1 >0andtin21
tin1
• Segment not visible
• Enter “inside 2” region: 0
if (0 < tout1 <= 1) Output_vert(turning vertex); }
}
else
C-Code
else {
if ((0 < tout1) && (1 >= tin2)) { /* sichtbares Segment vorhanden */
if (0 <= tin2)
Output_vert(appropriate side intersection);
else
Output_vert(starting vertex); if (1 >= tout1)
Output_vert(appropriate side intersection);
Output_vert(ending vertex); }
if (0 < tout2 <= 1) Output_vert(appropriate corner); }
Horizontal and vertical lines!
About twice as fast as Sutherland-Hodgeman
36
3D Clipping
• Definition of clipping planes and viewing frustum in 3D
37
3D Clipping
• Clipping algorithms so far work on
rectangular windows
38
3D Clipping
• Clip after perspective transformation
39
3D Clipping in Homogeneous Coordinates
• Catch 22
40
3D Clipping in Homogeneous Coordinates
41