Raycasts & Bounding Volume Hierarchy SDK

Module Description

Our module supports raycasting and a way to group game objects within bounding volume hierarchies (BVH).

Users can create objects and insert them into the hierarchical bounding volume manager. Which then, the user could create raycasts and detect collisions with those objects in an efficient, cost-performance manner. Developers looking to use many raycasts for static objects would find this API very useful for cost efficiency.

Without BVH, checking raycasting collision is Big O(n), where n is all gameobjects that could possibly be collided. With all game objects grouped in a BVH, checking raycasting collisions at best is Big O(log(n)) and at worst it's O(log(n) * n).

Application Programming Interface (API)

List of scripts:

HierarchicalVolumeManager.js

• Builds and stores a BVH tree and a pointer to the head node for client access.

Raycast.js

• A raycast line described in algebraic mathematics. Can check collisions with BoundingRaycastBoxes and any object type that inherent a Transform type object. The client can create Raycasts and use them separately from a BVH.

BoundingRaycastBox.js

• A node of a BVH, and all information and functions are handled outside of the clients’ control. Stores up to three of any given object type that inherent a Transform type object, when used in a BVH. The client can create BoundingRaycastBoxes and use them separately from a BVH.

List of functions:

HierarchicalVolumeManager

• HierarchicalVolumeManager(GameObjects[] objectsArray)

• Parameter: an array of objects the user wants to be organized into a BVH.

• Accepts any object type that inherits a transform.js object.

• Creates a BVH and organizes all objects passed in the objectsArray into a BVH.

BoundingRaycastBox

NOTE: BoundingRaycastBox does not need to be used by the client. The HierarchicalVolumeManager handles all of these types of objects. However, the client may use BoundingRaycastBoxes individually if s/he chooses to.

• BoundingRaycastBox([xPos, yPos] centerPos, float width, float height)

• Constructor that takes in a center point, width and height and then uses that information to create a bounding box to be able to group objects together

• checkIntersection(Raycast raycast)

• Given a raycast it checks if the raycast collides with it
• Returns true if collision, returns false if no collision

• draw(Camera camera)

• Draws the bounding box given the camera

• update()

• Updates the positions of the bounding boxes

• setGameObjectsArray(GameObjects[] array )

• Given an array of game objects it sets relates them to the bounding box

• Accepts any object type that inherits a transform.js object.

• getGameObjectsArray()

• Returns the game objects array

• clearGameObjectsArray()

• Sets the game objects array to an empty array

Raycast

• Raycast([xPos, yPos] startPoint, [xPos, yPos] endPoint)

• Parameters: a startPoint world coordinate for the starting location of the raycast, and an endPoint world coordinate for the ending position of the raycast.
• Creates a raycast with a set start and end coordinates from the parameters passed in.

• draw(Camera aCamera)

• Parameter: a Camera.js type object that the raycast will be drawn in.
• Draws a visible representation of the raycast on the viewable plane of the camera passed into the parameter.

• update(BoundngRaycastBox headNode)

• Parameter: a BoundingRaycastBox.js type object that is the head of a BVH tree.
• Checks if this raycast collides with the headNode of the BVH, and any game objects owned by the BVH.
• Returns an array of objects that this Raycast collided with.

• getStartPoint()

• Parameter: none
• Returns the start point of the raycast as an array in world coordinates [xPos, yPos].

• setStartPoint([xPos, yPos] startPoint)

• Parameter: Start point. Taken in x and y coordinates as an array
• Sets the start point of the raycast to specific point

• getEndPoint()

• Parameter: none
• Returns the end point of the raycast, in world coordinates [xPos, yPos].

• setEndPoint([xPos, yPos] endPoint)

• Parameter: Start point. Taken in x and y coordinates as an array
• Sets the endpoint of the raycast using the specified array of coordinates

Edits to Current Engine API

Transform

NOTE: The client never needs to access this code. This content was included because it was not part of the original game engine API, and these modifications are required for the Raycasting & BVH API to work.

• checkIntersection(Raycast raycast)

• New function
• Parameter: a Raycast object to check if this transform collides with it.
• Returns true if the raycast collided with this Transform, returns false otherwise.

• linesIntersect(float p0_x, float p0_y, float p1_x, float p1_y, float p2_x, float p2_y, float p3_x, float p3_y)

• New function
• Parameters: floating points of lines to see if they intersect.
• Returns true if the two lines of the passed floating points intersect, false otherwise.

Click For Tutorial

Click For Two Demo Games

Conclusion

Strengths

• Very quick collision search time for static objects in a BVH
• The client can create and use BoundingRaycastsBoxes and Raycasts separately from BVHs

Weaknesses

• Not possible with dynamic game objects
• Cannot customize the number of objects each node may store in a BVH

Potential Future Improvements

• Add a way to make the system work with dynamic objects and still being efficient