Димитър обнови решението на 21.11.2018 15:03 (преди 9 месеца)
+package main
+
+import (
+ "math"
+
+ "github.com/fmi/go-homework/geom"
+)
+
+const epsilon = float64(0.000001)
+
+// Vector operations
+
+func Normalize(v geom.Vector) geom.Vector {
+ return geom.Mul(v, math.Abs(1.0/(v.X+v.Y+v.Z)))
+}
+
+func Distance(v1, v2 geom.Vector) float64 {
+ v := geom.Sub(v1, v2)
+ return math.Sqrt(geom.Dot(v, v))
+}
+
+// Plane
+
+type Plane struct {
+ A, B, C geom.Vector
+}
+
+func NewPlane(a, b, c geom.Vector) Plane {
+ return Plane{
+ A: a,
+ B: b,
+ C: c,
+ }
+}
+
+func (p Plane) Normal() geom.Vector {
+ AB := geom.Sub(p.B, p.A)
+ AC := geom.Sub(p.C, p.A)
+ return Normalize(geom.Cross(AB, AC))
+}
+
+// Triangle
+
+type Triangle struct {
+ A, B, C geom.Vector
+}
+
+func NewTriangle(a, b, c geom.Vector) Triangle {
+ return Triangle{
+ A: a,
+ B: b,
+ C: c,
+ }
+}
+
+func (tr Triangle) Intersect(ray geom.Ray) bool {
+ p := NewPlane(tr.A, tr.B, tr.C)
+ N := p.Normal()
+
+ // Check if ray and plane are parallel
+ if math.Abs(geom.Dot(N, ray.Direction)) < epsilon {
+ return false
+ }
+
+ // Source: https://en.wikipedia.org/wiki/Line%E2%80%93plane_intersection
+ // Getting the ray line and triangle plane intersection
+ d := geom.Dot(geom.Sub(tr.A, ray.Origin), N) / geom.Dot(ray.Direction, N)
+
+ // Check if plane is behind ray
+ if d < 0 {
+ return false
+ }
+
+ // Intersection point of ray and triangle's plane
+ I := geom.Add(ray.Origin, geom.Mul(ray.Direction, d))
+
+ // Source: https://www.scratchapixel.com/lessons/3d-basic-rendering/ray-tracing-rendering-a-triangle/ray-triangle-intersection-geometric-solution
+ AB := geom.Sub(tr.B, tr.A)
+ AI := geom.Sub(I, tr.A)
+ ABxAI := geom.Cross(AB, AI)
+ if geom.Dot(N, ABxAI) < 0 {
+ return false
+ }
+
+ BC := geom.Sub(tr.C, tr.B)
+ BI := geom.Sub(I, tr.B)
+ BCxBI := geom.Cross(BC, BI)
+ if geom.Dot(N, BCxBI) < 0 {
+ return false
+ }
+
+ CA := geom.Sub(tr.A, tr.C)
+ CI := geom.Sub(I, tr.C)
+ CAxCI := geom.Cross(CA, CI)
+ if geom.Dot(N, CAxCI) < 0 {
+ return false
+ }
+
+ return true
+}
+
+// Quad
+
+type Quad struct {
+ A, B, C, D geom.Vector
+}
+
+// Are A,B,C,D in the right order
+func NewQuad(a, b, c, d geom.Vector) Quad {
+ return Quad{
+ A: a,
+ B: b,
+ C: c,
+ D: d,
+ }
+}
+
+func (q Quad) Intersect(ray geom.Ray) bool {
+ // Doesn't handle concave quads or non-adjacent quad A, B, C, D but
+ // started doing the homework too late :(
+
+ firstHalf := NewTriangle(q.A, q.B, q.C)
+ secondHalf := NewTriangle(q.C, q.A, q.D)
+
+ return firstHalf.Intersect(ray) || secondHalf.Intersect(ray)
+}
+
+// Sphere
+
+type Sphere struct {
+ Center geom.Vector
+ Radius float64
+}
+
+func NewSphere(origin geom.Vector, r float64) Sphere {
+ return Sphere{
+ Center: origin,
+ Radius: r,
+ }
+}
+
+func (s Sphere) Intersect(ray geom.Ray) bool {
+ if Distance(ray.Origin, s.Center) <= s.Radius {
+ return true
+ }
+
+ ray.Direction = Normalize(ray.Direction)
+
+ // P(t) = O + tD describes all points on the ray's line
+ // P(th) is the sphere center projected on the line of the ray
+ th := geom.Dot(geom.Sub(s.Center, ray.Origin), ray.Direction)
+
+ // If the ray points away from the sphere
+ if th < 0 {
+ return false
+ }
+
+ projectedCenter := geom.Add(ray.Origin, geom.Mul(ray.Direction, th))
+
+ return Distance(s.Center, projectedCenter) <= s.Radius
+}
+
+func main() {
+}