3 ms·

Clip space is the bane of my existence. I've been building a software rasterizer from scratch and implementing vertex/triangle clipping has turned into one of t

Clip space is the bane of my existence. I've been building a software rasterizer from scratch and implementing vertex/triangle clipping has turned into one of the hardest aspects. It took me about 50 hours of reading various references before I learned you cannot get away with doing this in screen space or any time after perspective divide. It still staggers me that there is not 1 coherent reference for how to do all of this. Virtually every reference about clipping winds up with something like "and then the GPU waves its magic wand and everything is properly clipped & interpolated :D". Every paper I read has some "your real answer is in another paper" meme going on. I've got printouts of Blinn & Newell, Sutherland & Hodgman, et. al. littered all over my house right now. About 4 decades worth of materials. Anyone who works on the internals of OGL or the GPU stack itself has the utmost respect from me. I cannot imagine working in that space full-time. About 3 hours of this per weekend is about all my brain can handle.

samstave 4y ago
Be the documentation you want to see in the world.
- hashishen 4y ago
  "RTFM" - The manual
  - samstave 4y ago
    "Look up error code on stack exchange to find the error in question seeking a solution, but its you from 5 years ago."
    - sph 4y ago
      "What was I working on? What did I see?!" https://xkcd.com/979/ https://xkcd.com/979/
- samstave 4y ago
  But thats the thing.... there is no documentation..
Jasper_ 4y ago
Vertex/triangle clipping is quite rare, and mostly used for clipping against the near plane (hopefully rare in practice). Most other implementations use a guard band as a fast path (aka doing it in screen space) -- real clipping is only used where your guard band doesn't cover you, precision issues mostly. I'm not sure what issues you're hitting, but I've never found clipping to be that challenging or difficult. Also, clip control and clip space aren't really specifically about clipping -- clip space is just the output space of your vertex shader, and the standard "clip control" extension just controls whether the near plane is at 0 or -1. And 0 is the correct option.
- bob1029 4y ago
  > clipping against the near plane (hopefully rare in practice) I am not sure I understand why this would be rare. If I am intending to construct a rasterizer for a first-person shooter, clipping is essentially mandatory for all but the most trivial of camera arrangements.
  - bpye 4y ago
    Clipping or culling? I expect it’s mostly the latter unless your camera ends up intersecting the geometry.
    - bob1029 4y ago
      Both. You almost always need both. Clipping deals with geometry that is partially inside the camera. Culling (either for backfaces or entire instances) is a preliminary performance optimization that can be performed in a variety of ways.
    - royjacobs 4y ago
      As an example, if you're writing a shooter then the floor might be a large square that will almost definitely be intersecting the near plane. You absolutely need clipping here.
      - 4y ago
nauful 4y ago
You have to clip against planes in 4D space (xyzw) before perspective divide (xyz /= w), not 3D (xyz). This simplified sample shows Sutherland-Hodgman with 4D clipping: https://web.archive.org/web/20040713023730/http://wwwx.cs.unc.edu:80/~sud/courses/236/a2/homoclip_sud.cpp https://web.archive.org/web/20040713023730/http://wwwx.cs.un... The main difference is the intersect method finds the intersection of a 4D line segment against a 4D plane.
Sharlin 4y ago
I also implemented clipping in my software rasterizer a while ago and can definitely sympathize! (Although I've written several simple scanline rasterizers in my life, this was the first time I actually bothered to implement proper clipping. I actually reinvented Sutherland–Hodgman from scratch which was pretty fun.) The problematic part is actually only the near plane due to how projective geometry works. At z=0 there's a discontinuity in real coordinates after z division, which means there can be no edges that cross from negative to positive z. Z division turns such an edge [a0, a1] into an "inverse" edge (-∞, a0'] ∪ [a1', ∞) which naturally makes rendering a bit tricky. In projective/homogenous coordinates, however, it is fine, because the space "wraps around" from positive to negative infinity. All the other planes you can clip against in screen space / NDC space if you wish, but I'm not sure there are good reasons to split the job like that.
joakleaf 4y ago
Not sure if you got through clipping, but it was one of those things I had to go through first at some point in the mid 90s myself. I feel your pain, but after having implemented it about 5-10 times in various situations, variants and languages, I can promise it gets a lot easier. In my experience it is most elegant to clip against the 6 planes of the view-frustrum in succession (one plane at a time). Preferably clipping against the near-plane first, as that reduces the set of triangles the most for subsequent clips. Your triangles can turn into convex polygons after a clip. So it is convenient to start with a generic convex polygon vs. plane-clipping algorithm; The thing to be careful about here is that points can (and will) lie on the plane. Use the plane equation (f(x,y,z)=ax+by+cz+d) to determine if a point is on one side, on the plane, or the other side. It is convenient to use a "mask" to designate the side a point v=(x,y,z) is on. So: 1 := inside_plane (f(x,y,z)>eps) 2 := outside_plane (f(x,y,z)<-eps) 3 := on_plane (f(x,y,z)>=eps && f(x,y,z)<=eps) Let m(v_i) be the mask of v_i. When you go through each edge of the convex polygon (v_i->v_{i+1}), you can check if you should clip the edge using the mask. I.e.: if (m(v_i)&m(v_{i+1})==0 the points are on opposite side => clip [determine intersection point]. Since you are just clipping to the frustrum, just return a list of the points that are inside or on the plane (i.e. m(v_i)&1==1) and the added intersection points. There are lots of potential for optimization, of course, but I wouldn't worry about that. There are lots of other places to optimize a software rasterizer with more potential, in my experience.
fabiensanglard 4y ago
I wrote about this a few years ago (https://fabiensanglard.net/polygon_codec/index.php https://fabiensanglard.net/polygon_codec/index.php). It was a pain to lean indeed and the best resources were quite old: - "CLIPPING USING HOMOGENEOUS COORDINATES" by James F. Blinn and Martin E. Newell - A Trip Down the Graphics Pipeline by Jim Blinn (yes the same Blinn that co-authored the paper above).

samstave 4y ago

Be the documentation you want to see in the world.

hashishen 4y ago
"RTFM" - The manual
- samstave 4y ago
  "Look up error code on stack exchange to find the error in question seeking a solution, but its you from 5 years ago."
  - sph 4y ago
    "What was I working on? What did I see?!" https://xkcd.com/979/ https://xkcd.com/979/
samstave 4y ago
But thats the thing.... there is no documentation..

Jasper_ 4y ago

Vertex/triangle clipping is quite rare, and mostly used for clipping against the near plane (hopefully rare in practice). Most other implementations use a guard band as a fast path (aka doing it in screen space) -- real clipping is only used where your guard band doesn't cover you, precision issues mostly. I'm not sure what issues you're hitting, but I've never found clipping to be that challenging or difficult. Also, clip control and clip space aren't really specifically about clipping -- clip space is just the output space of your vertex shader, and the standard "clip control" extension just controls whether the near plane is at 0 or -1. And 0 is the correct option.

bob1029 4y ago
> clipping against the near plane (hopefully rare in practice) I am not sure I understand why this would be rare. If I am intending to construct a rasterizer for a first-person shooter, clipping is essentially mandatory for all but the most trivial of camera arrangements.
- bpye 4y ago
  Clipping or culling? I expect it’s mostly the latter unless your camera ends up intersecting the geometry.
  - bob1029 4y ago
    Both. You almost always need both. Clipping deals with geometry that is partially inside the camera. Culling (either for backfaces or entire instances) is a preliminary performance optimization that can be performed in a variety of ways.
  - royjacobs 4y ago
    As an example, if you're writing a shooter then the floor might be a large square that will almost definitely be intersecting the near plane. You absolutely need clipping here.
    - 4y ago

nauful 4y ago

You have to clip against planes in 4D space (xyzw) before perspective divide (xyz /= w), not 3D (xyz). This simplified sample shows Sutherland-Hodgman with 4D clipping: https://web.archive.org/web/20040713023730/http://wwwx.cs.unc.edu:80/~sud/courses/236/a2/homoclip_sud.cpp https://web.archive.org/web/20040713023730/http://wwwx.cs.un... The main difference is the intersect method finds the intersection of a 4D line segment against a 4D plane.

Sharlin 4y ago

I also implemented clipping in my software rasterizer a while ago and can definitely sympathize! (Although I've written several simple scanline rasterizers in my life, this was the first time I actually bothered to implement proper clipping. I actually reinvented Sutherland–Hodgman from scratch which was pretty fun.) The problematic part is actually only the near plane due to how projective geometry works. At z=0 there's a discontinuity in real coordinates after z division, which means there can be no edges that cross from negative to positive z. Z division turns such an edge [a0, a1] into an "inverse" edge (-∞, a0'] ∪ [a1', ∞) which naturally makes rendering a bit tricky. In projective/homogenous coordinates, however, it is fine, because the space "wraps around" from positive to negative infinity. All the other planes you can clip against in screen space / NDC space if you wish, but I'm not sure there are good reasons to split the job like that.

joakleaf 4y ago

Not sure if you got through clipping, but it was one of those things I had to go through first at some point in the mid 90s myself. I feel your pain, but after having implemented it about 5-10 times in various situations, variants and languages, I can promise it gets a lot easier. In my experience it is most elegant to clip against the 6 planes of the view-frustrum in succession (one plane at a time). Preferably clipping against the near-plane first, as that reduces the set of triangles the most for subsequent clips. Your triangles can turn into convex polygons after a clip. So it is convenient to start with a generic convex polygon vs. plane-clipping algorithm; The thing to be careful about here is that points can (and will) lie on the plane. Use the plane equation (f(x,y,z)=ax+by+cz+d) to determine if a point is on one side, on the plane, or the other side. It is convenient to use a "mask" to designate the side a point v=(x,y,z) is on. So: 1 := inside_plane (f(x,y,z)>eps) 2 := outside_plane (f(x,y,z)<-eps) 3 := on_plane (f(x,y,z)>=eps && f(x,y,z)<=eps) Let m(v_i) be the mask of v_i. When you go through each edge of the convex polygon (v_i->v_{i+1}), you can check if you should clip the edge using the mask. I.e.: if (m(v_i)&m(v_{i+1})==0 the points are on opposite side => clip [determine intersection point]. Since you are just clipping to the frustrum, just return a list of the points that are inside or on the plane (i.e. m(v_i)&1==1) and the added intersection points. There are lots of potential for optimization, of course, but I wouldn't worry about that. There are lots of other places to optimize a software rasterizer with more potential, in my experience.

fabiensanglard 4y ago

I wrote about this a few years ago (https://fabiensanglard.net/polygon_codec/index.php https://fabiensanglard.net/polygon_codec/index.php). It was a pain to lean indeed and the best resources were quite old: - "CLIPPING USING HOMOGENEOUS COORDINATES" by James F. Blinn and Martin E. Newell - A Trip Down the Graphics Pipeline by Jim Blinn (yes the same Blinn that co-authored the paper above).