Implement triangle clipping algorithm for big triangles. (Renderer, VU1)

[h4570]

Triangle clipping is not that broken like in drawByPath3() , but this need also some polishing. When triangle is big and its partially outside of view frustum, we can see some weird behavior, that whole triangle is discarded.

https://github.com/h4570/tyra/blob/d58163d75be2d6c848f4456f73cebd8a6c1a63bd/src/engine/vu1_progs/draw3D.vcl#L43 https://github.com/h4570/tyra/blob/d58163d75be2d6c848f4456f73cebd8a6c1a63bd/src/engine/vu1_progs/draw3D.vcl#L104

[Foxar]

Visual example of the glitch:

[h4570]

Due to the fact that this issue takes a long time and has a high priority for us, I am moving it to "Roadmap January 2021" Ok, so here are my notes after 2 weeks of investigation.

TLDR:

• We have triangle culling which is ok for triangles which are on far plane.
• We need Sutherland-Hodgman/Cohen-Sutherland clipping algorithm for triangles which are on near plane and are partially outside of view frustum.

---

How "clipping" works right now?

As you can see, drawing area on PS2 is 4096x4096, our screen is 2048x2048. PS2 scisorring feature is set on 2048x2048. Drawing outside of 4096x4096 will cause visual artifacts.
Im saying "clipping" like this, because we dont have real clipping, it is triangle culling. It is not a bad idea overall - if triangle after projection is small, we dont really need to clip it.

Here is the code:

1. Clear clip flags https://github.com/h4570/tyra/blob/d58163d75be2d6c848f4456f73cebd8a6c1a63bd/src/engine/vu1_progs/draw3D.vcl#L43
2. Check if vertex is outside of view frustum https://github.com/h4570/tyra/blob/d58163d75be2d6c848f4456f73cebd8a6c1a63bd/src/engine/vu1_progs/draw3D.vcl#L104
3. If so, discard triangle https://github.com/h4570/tyra/blob/d58163d75be2d6c848f4456f73cebd8a6c1a63bd/src/engine/vu1_progs/draw3D.vcl#L110

Why the problem is most apparent around the near plane?

To convert 3D space to 2D screen space, we are using projection (screen), view (camera) and model (translation/rotation) matrix. http://www.opengl-tutorial.org/beginners-tutorials/tutorial-3-matrices/ When we will multiply our Vector3 (xyz) by ModelViewProjMatrix we will have Vector4 (xyzw) as a result. After it we must divide our vector by 1.0F/W and thats it, our result is 2D screen coordinate.

The problem is, that if our vector is a little further BEHIND the camera, multiplying by ModelViewProjMatrix will give some strange results (thats why our clipping code, is discarding that triangles so quickly). It looks like, we must clip big triangles manually which are partially outside view frustum.
More details about this multiply error here -> https://community.khronos.org/t/perspective-projection-behind-the-viewer-solved/49854/7

Take a look, how calculations look when we are "zooming" 2 triangles:

1 - Vector3 * ModelMatrix 2 - Vector3 * (Projection Matrix * Model Matrix) 3 - Vector3 * (Projection Matrix * Model Matrix) + GS Offsets (0,0 to 2048x2048 center))

What we can do?

I think that the best we can do, is create two VU1 micro programs. The first will be the same as we have (faster) - we will use it for meshes, which are 100% in view frustum. The second will have clipping algorithm, and will fix vertices automatically (slower) - we will use it for meshes, which are partially outside of view frustum. From what I see, the proposed one is Sutherland Hodgman algorithm

Fortunately we have frustum check right now, so it is a good starting point. https://github.com/h4570/tyra/blob/f6cbac7c20e0904d6da389c6f6d77bca6ecdca19/src/engine/models/mesh_material.cpp#L76

Some notes about PS2 clipping

Game Developers Conference presentation:

http://lukasz.dk/files/final-gdc2002-clippingps2.pdf

Comments from the Sony's newsgroup on a full 3D scissor clip on VU1:

"It clips against all six planes and takes quite a few cycles to do it, especially as I
spit out the resulting triangles (which were original tri-stripped of course) each
individually as a tri-fan (they can be up to 9 point polygons after scissoring). The
original tri-strip gets output with ADC=1s for the triangles that need to go through
extra scissoring checks.
I switch to simple guard band clipping once objects move a certain distance (size
dependent) away from the camera.
My camera can go anywhere it wants because of the above scissoring routine but it
really depends what kind of game you are making. In retrospect for the game I'm
making I don't need a full frustum scissor, GS level rejection suffices - but I wrote
the code before the game was decided upon.
Because I use the VU1 clip instruction (despite its drawbacks) the clip-or-not checks
are very quick and I don't actually end up scissoring that many polygons at all. On
the per-object level I also have a frustum-clip which tells me if the object is
straddling one of the 6 planes.
This is done with bounding spheres and so is very fast. If the object *is* straddling
then I flag my renderer to perform the extra CLIP instruction checks. There is also a
technique which removes the need for a divide within the scissor routine. (due to the
fact you have a divide by w when you go to render anyway).
1. It's slow.
2. It's only needed on ~2-3% of the polys if that. Any poly that isn't really close
to the front plane can simply use the guard band or be culled in its entirety.
So I have 3 renderers. One for models that are completely in the frustum, one for
models that are partially clipped and a fair distance from the front plane, and one for
models that are partially clipped and close to the front plane.
The problem I ran into with subdivision was coming up with a reliable amount of
subdivision, ie. if a poly is small, then you don't need to subdivide, but if it's large
you do. Once I got a value that subdivided enough (no polys outside of the guard
band), it seemed like I was wasting a lot of time subdividing polys that really didn't
need it. The full clipping solution seemed like it was much more reliable.
I think the scissoring method is most reliable for the same reasons you suggest - ie.
sub-dividing can produce *way* too many polygons. Of course, the GS can easily
handle those polygons so it might actually be faster. I preferred the "reliability" of a
standard scissor clip... especially if you have large flat polygons almost parallel to
the camera. (ie. ground)"
An alternative explanation:
What you want at the end is
x between 0 and 4096
y between 0 and 4096
z between MIN_Z and MAX_Z
Most of the code I've seen does the clip test before diving by w (it reduces
the total latency of your routine, which makes optimisation easier), so
you've got x*w, y*w, z*w, w and want to test
x*w between 0 and 4096*w
y*w between 0 and 4096*w
z*w between MIN_Z*w and MAX_Z*w
or
x*w-2048*w between -2048*w and 2048*w
y*w-2048*w between -2048*w and 2048*w
z*w-(MAX_Z+MIN_Z)*w/2 between (MIN_Z-(MAX_Z+MIN_Z)/2)*w and
(MAX_Z-(MAX_Z+MIN_Z)/2)*w
The last test simplifies to
z*w-(MAX_Z-MIN_Z)*w/2 between -(MAX_Z-MIN_Z)*w/2 and (MAX_Z-MIN_Z)*w/2
This still isn't quite what CLIP wants. But each range is of the form -constant*w to constant*w, so divide the left hand side by the
constant, and we get:
x*w/2048-w between -w and w
y*w/2048-w between -w and w
z*w*2/(MAX_Z-MIN_Z)-w between -w and w
We've still got the problem that w can be positive or negative (that's why
I've been saying "A between B and C" instead of "B<A
the test is -w<A<A<-w.
Testing -abs(w)<A
And that's what CLIP does.

[h4570]

Partially resolved in Tyra 2.0.0.

There are 2 options (will be covered in YouTube tutorial):

• Subdivide polys and use PS2 "fake" clipping (faster)
• Set renderOptions.frustumCulling = Precise and renderOptions.fullClipChecks = true (slower)