BBox Track::getBBox() const
{
    if (!points.length()) {
        return BBox();
    }

    float left, top, bottom, right;
    left = right = points[0]._lon;
    top = bottom = points[0]._lat;

    QList<TrackPoint>::const_iterator i = points.begin();
    ++i;
    for (; i != points.end(); ++i) {
        float lat = (*i)._lat;
        float lon = (*i)._lon;

        if ( lon < left) {
            left = lon;
        } else if (lon > right) {
            right = lon;
        }

        if ( lat > top) {
            top = lat;
        } else if (lat < bottom) {
            bottom = lat;
        }
    }
    return BBox(left, top, right, bottom);
}

bool SHAPE_RECT::Collide( const SEG& aSeg, int aClearance ) const
{
    //VECTOR2I pmin = VECTOR2I( std::min( aSeg.a.x, aSeg.b.x ), std::min( aSeg.a.y, aSeg.b.y ) );
    //VECTOR2I pmax = VECTOR2I( std::max( aSeg.a.x, aSeg.b.x ), std::max( aSeg.a.y, aSeg.b.y ));
    //BOX2I r( pmin, VECTOR2I( pmax.x - pmin.x, pmax.y - pmin.y ) );

    //if( BBox( 0 ).SquaredDistance( r ) > aClearance * aClearance )
    //    return false;

    if( BBox( 0 ).Contains( aSeg.A ) || BBox( 0 ).Contains( aSeg.B ) )
        return true;

    VECTOR2I vts[] = { VECTOR2I( m_p0.x, m_p0.y ),
                        VECTOR2I( m_p0.x, m_p0.y + m_h ),
                        VECTOR2I( m_p0.x + m_w, m_p0.y + m_h ),
                        VECTOR2I( m_p0.x + m_w, m_p0.y ),
                        VECTOR2I( m_p0.x, m_p0.y ) };

    for( int i = 0; i < 4; i++ )
    {
        SEG s( vts[i], vts[i + 1], i );

        if( s.Distance( aSeg ) < aClearance )
            return true;
    }

    return false;
}

uint32_t EBVHAccel::flattenEBVHTree(EBVHBuildNode *node, uint32_t *offset, BBox boxToBoundOn) {
    LinearEBVHNode *linearNode = &nodes[*offset];
    
    BBox compressedBox = compressBBox(node->bounds, boxToBoundOn);
    linearNode->bounds_x0 = compressedBox.pMin.x;
    linearNode->bounds_y0 = compressedBox.pMin.y;
    linearNode->bounds_z0 = compressedBox.pMin.z;
    linearNode->bounds_x1 = compressedBox.pMax.x;
    linearNode->bounds_y1 = compressedBox.pMax.y;
    linearNode->bounds_z1 = compressedBox.pMax.z;


    BBox uncompressedBox = uncompressBBox(BBox(Point(linearNode->bounds_x0, linearNode->bounds_y0, linearNode->bounds_z0), Point(linearNode->bounds_x1, linearNode->bounds_y1, linearNode->bounds_z1)), boxToBoundOn);

    uint32_t myOffset = (*offset)++;
    if (node->nPrimitives > 0) {
        Assert(!node->children[0] && !node->children[1]);
        linearNode->primitivesOffset = node->firstPrimOffset;
        linearNode->nPrimitives = node->nPrimitives;
    }
    else {
        // Creater interior flattened EBVH node
        linearNode->axis = node->splitAxis;
        linearNode->nPrimitives = 0;
        flattenEBVHTree(node->children[0], offset, BBox(Point(uncompressedBox.pMin.x,uncompressedBox.pMin.y,uncompressedBox.pMin.z), Point(uncompressedBox.pMax.x,uncompressedBox.pMax.y,uncompressedBox.pMax.z)));
        linearNode->secondChildOffset = flattenEBVHTree(node->children[1],
                                                       offset, BBox(Point(uncompressedBox.pMin.x,uncompressedBox.pMin.y,uncompressedBox.pMin.z), Point(uncompressedBox.pMax.x,uncompressedBox.pMax.y,uncompressedBox.pMax.z)));
    }
    return myOffset;
}

bool SHAPE_LINE_CHAIN::PointInside( const VECTOR2I& aPt, int aAccuracy ) const
{
    BOX2I bbox = BBox();
    bbox.Inflate( aAccuracy );

    if( !m_closed || PointCount() < 3 || !BBox().Contains( aPt ) )
        return false;

    bool inside = false;

    /**
     * To check for interior points, we draw a line in the positive x direction from
     * the point.  If it intersects an even number of segments, the point is outside the
     * line chain (it had to first enter and then exit).  Otherwise, it is inside the chain.
     *
     * Note: slope might be denormal here in the case of a horizontal line but we require our
     * y to move from above to below the point (or vice versa)
     */
    for( int i = 0; i < PointCount(); i++ )
    {
        const auto p1 = CPoint( i );
        const auto p2 = CPoint( i + 1 ); // CPoint wraps, so ignore counts
        const auto diff = p2 - p1;

        if( diff.y != 0 )
        {
            const int d = rescale( diff.x, ( aPt.y - p1.y ), diff.y );

            if( ( ( p1.y > aPt.y ) != ( p2.y > aPt.y ) ) && ( aPt.x - p1.x < d ) )
                inside = !inside;
        }
    }
    return inside && !PointOnEdge( aPt, aAccuracy );
}

BBox PhysicObject::getPhysBBox() {
	if (!isPhysicsInitialized())
		return BBox();

	btVector3 min;
	btVector3 max;
	rigidBody->getAabb(min, max);

	return BBox(CVector(min.x() * 100.0f, max.y() * 100.0f, min.z() * 100.0f),
			CVector(max.x() * 100.0f, min.y() * 100.0f, max.z() * 100.0f));
}

void R3MeshSearchTree::
InsertFace(R3MeshFace *face)
{
  // Check if face intersects box
  if (!R3Intersects(mesh, face, BBox())) return;

  // Create container
  R3MeshSearchTreeFace *face_container = new R3MeshSearchTreeFace(mesh, face);
  assert(face_container);

  // Insert face into root
  InsertFace(face_container, root, BBox(), 0);
}

void GameScreenSet::deserialize(GameState *gs, SerializeBuffer &serializer) {
    serializer.read_int(current_screen);
    simulation_map = read_gamemap(gs, serializer);
    serializer.read_container(screens, [&](GameScreen& screen) {
        screen.deserialize(gs, serializer);
    });

    GameSettings& settings = gs->game_settings();
    int n_local_players = 0;
    for (PlayerDataEntry &player: gs->player_data().all_players()) {
        if (player.is_local_player) {
            n_local_players++;
        }
    }
    // Number of split-screens tiled together
    int n_x = 1, n_y = 1;
    if (n_local_players <= 2) {
        n_x = n_local_players;
    } else if (n_local_players <= 4) {
        // More than 2, less than 4? Try 2x2 tiling
        n_x = 2, n_y = 2;
    } else if (n_local_players <= 6) {
        n_x = 3, n_y = 2;
    } else {
        LANARTS_ASSERT(n_local_players <= 9);
        // Last resort, Try 3x3 tiling
        n_x = 3, n_y = 3;
    }

    const int WIDTH = settings.view_width / n_x;
    const int HEIGHT = settings.view_height / n_y; // / N_PLAYERS;
    std::vector<BBox> bounding_boxes;
    for (GameScreen& screen : screens) {
        const int x1 = (screen.index % n_x) * WIDTH, y1 = (screen.index / n_x) * HEIGHT;
        bounding_boxes.push_back(BBox {x1, y1, x1 + WIDTH, y1 + HEIGHT});
    }
    if (bounding_boxes.size() == 3) {
        bounding_boxes[1] = {WIDTH, 0, settings.view_width, settings.view_height};
    }
    for (GameScreen& screen : screens) {
        BBox b = bounding_boxes[screen.index];
        screen.window_region = b;
        screen.hud = GameHud {
                BBox(b.x2 - GAME_SIDEBAR_WIDTH, b.y1, b.x2, b.y2),
                BBox(b.x1, b.y1, b.x2 - GAME_SIDEBAR_WIDTH, b.y2)
        };
        screen.view = GameView {0, 0, b.width() - GAME_SIDEBAR_WIDTH, b.height()};
    }
}

NaiadFoamBox::NaiadFoamBox(const Transform *o2w, const Transform *w2o,
                           bool ro, Reference<NaiadFoam> par, const Nb::ParticleShape & particle, int blockID)
    : Shape(o2w, w2o, ro), parent(par) {
    //Get the blocks of particles
    const Nb::BlockArray3f& blocksPos = particle.constBlocks3f("position");

    const Nb::Block3f& blockPos = blocksPos(blockID);

    density = blockPos.size();

    bb = BBox(Point(blockPos.min().v[0],
                    blockPos.min().v[1],
                    blockPos.min().v[2]),
              Point(blockPos.max().v[0],
                    blockPos.max().v[1],
                    blockPos.max().v[2]));
    //for (int pIdx = 0; pIdx < 1; ++pIdx) {
    for (int pIdx = 0; pIdx < blockPos.size(); pIdx += 20) {
        Point pos(blockPos.data()[pIdx].v[0],
                  blockPos.data()[pIdx].v[1],
                  blockPos.data()[pIdx].v[2]);

        float r = 0.03f;

        particles.push_back(NaiadFoamParticle(pos,r, this));

#ifdef VDB
        vdb_sample(0.01);
        vdb_color(1.0f, 1.0f, 1.0f);
        vdb_point(pos.x, pos.y, pos.z);
#endif
    }
}

RNBoolean R3Model::
Intersects(const R3Ray& ray, 
  R3Point *hit_point, R3Vector *hit_normal, 
  RNScalar *hit_t, int *hit_triangle_index) const
{
  // Check triangles
  if (!triangles) return FALSE;

  // Check bounding box
  if (!R3Intersects(ray, BBox())) return FALSE;

  // Check each triangle for intersection
  RNScalar min_t = FLT_MAX;
  for (int i = 0; i < NTriangles(); i++) {
    const R3Triangle *triangle = Triangle(i);
    R3Point point;
    R3Vector normal;
    RNScalar t;
    if (R3Intersects(ray, *triangle, &point, &normal, &t) == R3_POINT_CLASS_ID) {
      if (t < min_t) {
        if (hit_point) *hit_point = point;
        if (hit_normal) *hit_normal = normal;
        if (hit_triangle_index) *hit_triangle_index = i;
        if (hit_t) *hit_t = t;
        min_t = t;
      }
    }
  }

  // Return whether hit any triangle
  return (min_t == FLT_MAX) ? FALSE : TRUE;
}

	BBox Triangle::Bound() const {
		const VectorArray& vertices = mesh->vertices;
		Vector3dF p0 = vertices[indexes[0]];
		Vector3dF p1 = vertices[indexes[1]];
		Vector3dF p2 = vertices[indexes[2]];
		return BBox(p0, p1).Union(p2);
	}

BBox Triangle::get_bbox() const {
  
  // TODO: 
  // compute the bounding box of the triangle
  
  return BBox();
}

BBox Rectangle::get_bounding_box(void) {
	double delta = 0.0001; 

	return(BBox(std::min(p0.x, p0.x + a.x + b.x) - delta, std::max(p0.x, p0.x + a.x + b.x) + delta,
                    std::min(p0.y, p0.y + a.y + b.y) - delta, std::max(p0.y, p0.y + a.y + b.y) + delta, 
                    std::min(p0.z, p0.z + a.z + b.z) - delta, std::max(p0.z, p0.z + a.z + b.z) + delta));
}

BBox SpherePrimitive::wsBounds(Geo::Geometry::CPtr geometry) const
{
  assert(geometry != NULL);
  assert(geometry->particles() != NULL);

  if (!geometry->particles()) {
    Log::warning("SpherePrimitive has no particles. "
                 "Skipping bounds generation.");
    return BBox();
  }

  BBox wsBBox;

  AttrVisitor visitor(geometry->particles()->pointAttrs(), m_params);
  Attr<V3f>   wsCenter("P");
  Attr<float> radius("radius");

  for (AttrVisitor::const_iterator i = visitor.begin(), end = visitor.end(); 
       i != end; ++i) {
    i.update(wsCenter);
    i.update(radius);
    wsBBox.extendBy(wsCenter.as<Vector>() + radius.as<Vector>());
    wsBBox.extendBy(wsCenter.as<Vector>() - radius.as<Vector>());
  }

  return wsBBox;
}

void R3MeshSearchTree::
Outline(void) const
{
  // Draw kdtree nodes recursively
  if (!root) return;
  Outline(root, BBox());
}

void R3MeshSearchTree::
FindIntersection(const R3Ray& ray, R3MeshIntersection& closest,
  RNScalar min_t, RNScalar max_t,
  int (*IsCompatible)(const R3Point&, const R3Vector&, R3Mesh *, R3MeshFace *, void *), void *compatible_data)
{
  // Initialize result
  closest.type = R3_MESH_NULL_TYPE;
  closest.vertex = NULL;
  closest.edge = NULL;
  closest.face = NULL;
  closest.point = R3zero_point;
  closest.t = 0;

  // Check root
  if (!root) return;

  // Update mark (used to avoid checking same face twice)
  mark++;

  // Search nodes recursively
  FindIntersection(ray, closest,
    min_t, max_t,
    IsCompatible, compatible_data,
    root, BBox());
}

BBox Triangle::WorldBound() const {
    // Get triangle vertices in _p1_, _p2_, and _p3_
    const Point &p1 = mesh->p[v[0]];
    const Point &p2 = mesh->p[v[1]];
    const Point &p3 = mesh->p[v[2]];
    return Union(BBox(p1, p2), p3);
}

BBox TrackList::getBBox() const
{
    if (!tracks.length()) {
        return BBox();
    }
    BBox cur, max;

    Track t = tracks.first();
    max = t.getBBox();

    QList<Track>::const_iterator i = tracks.begin();
    ++i;
    for (; i != tracks.end(); ++i) {
        cur = (*i).getBBox();
        if (cur.left < max.left) {
            max.left = cur.left;
        }
        if (cur.top < max.top) {
            max.top = cur.top;
        }
        if (cur.right > max.right) {
            max.right = cur.right;
        }
        if (cur.bottom > max.bottom) {
            max.bottom = cur.bottom;
        }
    }

    return max;
}

BVH::BVH(ObjMesh& _mesh)
{
    mesh = _mesh;

    //build work list
    workList.reserve(mesh.faces.size());
    for(auto i = 0; i < mesh.faces.size(); ++i)
        workList.push_back(BVHPrimitiveInfo(i, BBox(mesh.vertices[mesh.faces[i].x], mesh.vertices[mesh.faces[i].y], mesh.vertices[mesh.faces[i].z])));

    //recursive build
    std::cout<<"Building BVH..."<<std::endl;
    orderedPrims.reserve(mesh.faces.size());
    root = RecursiveBuild(0, workList.size());
    std::cout<<"Totoal nodes: "<<totalNodes<<std::endl;
    std::cout<<"Max depth: "<<maxDepth<<std::endl;

    //replace mesh faces order with ordered one
    mesh.faces.swap(orderedPrims);

    //build linear bvh
    lbvh.reserve(totalNodes);
    for(auto i = 0; i < totalNodes; ++i)
        lbvh.push_back(LBVHNode());
    uint32_t offset = 0;
    Flatten(root, &offset);
    std::cout<<"Root max: ("<<lbvh[0].bMax.x<<", "<<lbvh[0].bMax.y<<", "<<lbvh[0].bMax.z<<")"<<std::endl;
    std::cout<<"Root min: ("<<lbvh[0].bMin.x<<", "<<lbvh[0].bMin.y<<", "<<lbvh[0].bMin.z<<")"<<std::endl;
}

void Player::DoBlockPicking() {
	static int counter = 0;
	static bool mouseStateLastTick = false;

	PickBlock();

	if (!Window::HasFocus()) {
		return;
	}

	if (picked && !mouseStateLastTick) {
		if (Input::MouseRight()) {
			int old = Game::world->GetBlock(pickedBlock + side);
			Game::world->SetBlock(pickedBlock + side, Block::Test);
			if (BoundingBoxD::Block(pickedBlock + side).Intersects(BBox())) {
				Game::world->SetBlock(pickedBlock + side, old);
			} else {
				Game::worldRenderer->UpdateBlock(pickedBlock + side);
			}
		} else if (Input::MouseLeft()) {
			Game::world->SetBlock(pickedBlock, Block::Air);
			Game::worldRenderer->UpdateBlock(pickedBlock);
		}
		PickBlock();
		counter = 0;
	}

	mouseStateLastTick = Input::MouseLeft() || Input::MouseRight();

	if (counter > 250) {
		mouseStateLastTick = false;
	}

	counter += Game::TickMS;
}

BBox Triangle::get_bounding_box(void) const {
  double delta = 0.000001;

  return BBox(min(min(v0.x, v1.x), v2.x) - delta, max(max(v0.x, v1.x), v2.x) + delta,
         min(min(v0.y, v1.y), v2.y) - delta, max(max(v0.y, v1.y), v2.y) + delta,
         min(min(v0.z, v1.z), v2.z) - delta, max(max(v0.z, v1.z), v2.z) + delta);
}