Александър обнови решението на 20.11.2018 01:05 (преди 9 месеца)
+package main
+
+import (
+ "math"
+
+ "github.com/fmi/go-homework/geom"
+)
+
+var epsilon = 1e-7
+
+type Ray struct {
+ Origin, Direction Vector
+}
+
+type Vector struct {
+ geom.Vector
+}
+
+type Triangle struct {
+ a, b, c Vector
+}
+
+type Quad struct {
+ a, b, c, d Vector
+}
+
+type Sphere struct {
+ a Vector
+ r float64
+}
+
+type Plane struct {
+ a, b, c, d float64
+}
+
+func MakeRay(geomRay geom.Ray) Ray {
+ return Ray{
+ Origin: Vector{geomRay.Origin},
+ Direction: Vector{geomRay.Direction},
+ }
+}
+
+func (v Vector) Minus(o Vector) Vector {
+ return Vector{
+ geom.NewVector(
+ v.X-o.X,
+ v.Y-o.Y,
+ v.Z-o.Z)}
+}
+
+func (v Vector) Product(t float64) Vector {
+ return Vector{
+ geom.NewVector(
+ v.X*t,
+ v.Y*t,
+ v.Z*t)}
+}
+
+func (r Ray) Intersection(p Plane) (bool, float64, Vector) {
+ tCoeff := p.a*r.Direction.X + p.b*r.Direction.Y + p.c*r.Direction.Z
+
+ if math.Abs(tCoeff) <= epsilon {
+ // the line is parallel to the Plane,
+ // either 0 or infinite number of solutions
+ return false, 0, Vector{}
+ }
+
+ freeCoef := -(p.d + p.a*r.Origin.X + p.b*r.Origin.Y + p.c*r.Origin.Z)
+ t := freeCoef / tCoeff
+
+ return true, t, r.VectorAtT(t)
+}
+
+func (r Ray) VectorAtT(t float64) Vector {
+ return r.Origin.Plus(
+ r.Direction.Product(t))
+}
+
+func (v Vector) Plus(o Vector) Vector {
+ return Vector{
+ geom.NewVector(
+ v.X+o.X,
+ v.Y+o.Y,
+ v.Z+o.Z)}
+}
+
+func (v Vector) DotProduct(o Vector) float64 {
+ return v.X*o.X + v.Y*o.Y + v.Z*o.Z
+}
+
+func (v Vector) CrossProduct(o Vector) Vector {
+ return Vector{
+ geom.NewVector(
+ v.Y*o.Z-v.Z*o.Y,
+ v.Z*o.X-v.X*o.Z,
+ v.X*o.Y-v.Y*o.X)}
+}
+
+func (v Vector) Length() float64 {
+ return math.Sqrt(v.X*v.X + v.Y*v.Y + v.Z*v.Z)
+}
+
+func (t Triangle) NormalVector() Vector {
+ ab := t.b.Minus(t.a)
+ ac := t.c.Minus(t.a)
+
+ return ab.CrossProduct(ac)
+}
+
+func (t Triangle) Area() float64 {
+ return t.NormalVector().Length() / 2
+}
+
+func (t Triangle) Plane() Plane {
+ n := t.NormalVector()
+
+ return Plane{
+ n.X, n.Y, n.Z,
+ -n.DotProduct(t.a),
+ }
+}
+
+func (t Triangle) IsInside(p Vector) bool {
+ abp := Triangle{t.a, t.b, p}.Area()
+ bcp := Triangle{t.b, t.c, p}.Area()
+ cap := Triangle{t.c, t.a, p}.Area()
+ totalArea := t.Area()
+
+ // If the Area of the triangle is (almost) the same
+ // as the sum of the are of the triangles between p and the edges
+ // of the triangle, then p is inside or on the edge of the triangle
+ return math.Abs(totalArea-abp-bcp-cap) <= epsilon
+}
+
+func (t Triangle) Intersect(geomRay geom.Ray) bool {
+ ray := MakeRay(geomRay)
+ Plane := t.Plane()
+
+ hasIntersection, ti, actualPoint := ray.Intersection(Plane)
+
+ if !hasIntersection || ti < -epsilon {
+ return false
+ }
+
+ return t.IsInside(actualPoint)
+}
+
+func (q Quad) Intersect(geomRay geom.Ray) bool {
+ abc := Triangle{q.a, q.b, q.c}
+ abd := Triangle{q.a, q.b, q.d}
+ bcd := Triangle{q.b, q.c, q.d}
+ acd := Triangle{q.a, q.c, q.d}
+
+ // quad is concave
+ // either b or d is the internal point
+ if abc.IsInside(q.d) || acd.IsInside(q.b) {
+ return abd.Intersect(geomRay) || bcd.Intersect(geomRay)
+ }
+
+ // either a or c is the internal point or the quad is convex
+ return abc.Intersect(geomRay) || acd.Intersect(geomRay)
+}
+
+func (s Sphere) Intersect(geomRay geom.Ray) bool {
+ ray := MakeRay(geomRay)
+
+ Area := Triangle{
+ ray.Origin,
+ ray.Origin.Plus(ray.Direction),
+ s.a,
+ }.Area()
+
+ d := ray.Direction.Length()
+
+ // the distance from the sphere to the line the ray is laying on
+ h := Area / d
+
+ // the distance from the line to the sphere center is greater than
+ // the sphere radius, no need to check where it is relative to the ray
+ if h-s.r > epsilon {
+ return false
+ }
+
+ // we're really interested in t's sign, so we won't subract
+ // by the squared Length of ray.Direction
+ t := -ray.Origin.Minus(s.a).DotProduct(
+ ray.Direction)
+
+ if t >= -epsilon {
+ return true
+ }
+
+ return false
+}
+
+func NewTriangle(a, b, c geom.Vector) Triangle {
+ return Triangle{
+ Vector{a},
+ Vector{b},
+ Vector{c},
+ }
+}
+
+func NewQuad(a, b, c, d geom.Vector) Quad {
+ return Quad{
+ Vector{a},
+ Vector{b},
+ Vector{c},
+ Vector{d},
+ }
+}
+
+func NewSphere(origin geom.Vector, r float64) Sphere {
+ return Sphere{a: Vector{origin}, r: r}
+}