3
$\begingroup$

I'm building a software renderer but I think there might be some problem with my ray-triangle intersection accuracy.

I implemented the algorithm referring to pbrt-v3 without some components which I think have little influence on the intersection test.

Below is the code perform intersection test:

bool Triangle::intersectP(const Ray &r, Point3f p0, Point3f p1, Point3f p2) const {
    // translate
    Point3f p0_ = p0 - r._o;
    Point3f p1_ = p1 - r._o;
    Point3f p2_ = p2 - r._o;

    // permute, to make sure z-dimension is not zero
    // permutation is just like to circular move right/left until z is largest dimemsion.
    int kz = r._d.maxDim();
    int kx = kz+1; if (kx == 3) kx = 0;
    int ky = kx+1; if (ky == 3) ky = 0;

    // swap coord
    Vec3f d_ = r._d.permute(kx, ky, kz);
    p0_ = p0_.permute(kx, ky, kz);
    p1_ = p1_.permute(kx, ky, kz);
    p2_ = p2_.permute(kx, ky, kz);
    // shear
    float Sx = -d_.x()/d_.z();
    float Sy = -d_.y()/d_.z();
    float Sz = 1.0f/d_.z();

    // perform transform (p.z doesn't matter now)
    p0_[0] += Sx*p0_[2];
    p0_[1] += Sy*p0_[2];
    p1_[0] += Sx*p1_[2];
    p1_[1] += Sy*p1_[2];
    p2_[0] += Sx*p2_[2];
    p2_[1] += Sy*p2_[2];

    // signed edge function to judge whether origin's projection in projected triangle
    float e0 = p1_.x()*p2_.y() - p2_.x()*p1_.y();   // p1 -> p2
    float e1 = p2_.x()*p0_.y() - p0_.x()*p2_.y();   // p2 -> p0
    float e2 = p0_.x()*p1_.y() - p1_.x()*p0_.y();   // p0 -> p1

    // perform high-precision at edges
    if (e0 == 0.0f || e1 == 0.0f || e2 == 0.0f) {
        double p0xp1y = (double)p0_.x() * (double)p1_.y();
        double p1xp0y = (double)p1_.x() * (double)p0_.y();
        e2 = (float)(p0xp1y - p1xp0y);
        double p1xp2y = (double)p1_.x() * (double)p2_.y();
        double p2xp1y = (double)p2_.x() * (double)p1_.y();
        e0 = (float)(p1xp2y - p2xp1y);
        double p2xp0y = (double)p2_.x() * (double)p0_.y();
        double p0xp2y = (double)p0_.x() * p2_.y();
        e1 = (float)(p2xp0y - p0xp2y);
    }

    // edge detection
    if ( (e0 < 0 || e1 < 0 ||  e2 < 0) && (e0 > 0 || e2 > 0 || e1 > 0) )
        return false;

    float det = e0 + e1 + e2;
    if (det == 0)   // on edge
        return false;

    // compute z value (i.e. t)
    p0_[2] *= Sz;
    p1_[2] *= Sz;
    p2_[2] *= Sz;

    float tScaled = e0*p0_.z() + e1*p1_.z() + e2*p2_.z();
    if (det < 0 && (tScaled >= 0 || tScaled < r._tmax*det) ) return false;
    else if (det > 0 && (tScaled <= 0 || tScaled > r._tmax*det) ) return false;

    return true;
}

Unlike pbrt, my implement use right-hand coordinate and row-major matrices, but I think this do not influence the correctness of this piece of code.

Most of the time, this function works fine. However, artifacts appears when I do occlusion test to the light sources, where r._tmax has a specific value (the distance between intersection point and light sample point).

I tested the algorithm with a plane and a point light above it, however just use the position of the light, radiance is not computed, and this is why I think the problem is caused by intersection implementation. If unoccluded, a value is returned as radiance, otherwise zero.

Vec3f PointEmitter::evalDirect(std::shared_ptr<Scene> scene, const IntersectInfo &isect_info, const Point2f &u) const {
    Vec3f wi;
    float light_pdf;
    VisibilityTester vt;
    Vec3f Li_sampled = sample_Li(isect_info, wi, light_pdf, vt, u);
    Vec3f f = isect_info._bsdf->f(isect_info._wo, wi)*std::abs(isect_info._shading._n.dot(wi));

    return (scene->intersectP(IntersectInfo(_p).spawnRayTo(isect_info))) *100;
}

enter image description here

And another open box-like polygon, with same light: enter image description here There's a circle-like region obviously stands out on the surface.

I consider this comes from the float point error when comparing r_tmax and the distance. But the code already uses double-precision. Can anyone help?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Have you added a bias to your rays? Adding a bias means that you offset the ray position by the normal of the surface multiplied by a very small number, so that the ray is just off the surface. This means that the triangle that the starting point of a ray is on, is actually a bit behind the ray meaning that $t<0$. If you do not have the bias, the triangle would be at $t=0$, however we are working with limited precision and then sometimes it is below zero and sometimes above zero. It would not matter how much precision you have, you would always get this. Every render engine implements this. $\endgroup$ – bram0101 Nov 10 '18 at 21:22
  • $\begingroup$ @bram0101 Hi. Thanks for the advice. However I'm not sure if this solves the problem, though I didn't add the bias. This is because, in my code, the occlusion test ray starts from the point light and I don't think phenomenon is caused by the $t<0$ issue. But I'll definitely add the bias to make the code robust. $\endgroup$ – jinglei Nov 10 '18 at 23:19
  • 2
    $\begingroup$ Just to second bram0101's comment, this definitely looks like shadow acne, and shadow bias is the standard solution. Just because you're using double precision doesn't mean the floating-point error is zero! If you still have the problem after adding bias, report back. $\endgroup$ – user106 Nov 11 '18 at 8:21
  • $\begingroup$ +1 to Rahul. Definitely looks like "acne". With floating point, it's always worth remembering: "Floating point numbers are like piles of sand; every time you move them around, you lose a little sand and pick up a little dirt. — Brian Kernighan and P.J. Plauger" $\endgroup$ – Simon F Nov 12 '18 at 15:15
  • $\begingroup$ @Rahul Thank you for the reference link. I've added the bias and the phenomena seems gone away. However, one more question on how I choose the bias value. I used $1e-6$ at first and some of the "acnes" still exists, only after I used $1e-5$ did them disappear. But I'm afraid the bias value is too high? $\endgroup$ – jinglei Nov 12 '18 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.