Fast Minkowski Shapecast

Resources Community Resources
1

Overview

We already know that Roblox has a native solution for shapecasting, however, as many of us may have experienced problems with it, like, being inaccurate or having no margins, well, I came up with an old algorithm I made a few years ago that solves these problems.

Installation

You can get the repo here

Basic usage

local ReplicatedStorage = game:GetService 'ReplicatedStorage'

local FMShapecast = require(ReplicatedStorage:WaitForChild 'FMShapecast')
local World = FMShapecast() --// Creates a new geometry world

local sphereShape = World.createShape 'Ball' --// Creates a sphere shape
sphereShape.Transform = CFrame.new(0, 50, 0)
sphereShape.Radius = 1
sphereShape.Margin = 0.01

local shapecastParams: FMShapecast.ShapecastParams = {}
shapecastParams.FilterDescendantsInstances = {}
shapecastParams.FilterType = Enum.RaycastFilterType.Include
shapecastParams.RespectCanCollide = true
shapecastParams.CollisionGroup = 'Default'
shapecastParams.DepthContact = false --// Used for negative time of impacts (inner intersections).

local shapecastResult = World:Shapecast(sphereShape, Vector3.new(0, -999, 0), shapecastParams)
if shapecastResult then
	print('Distance', shapecastResult.Distance)
	print('Instance', shapecastResult.Instance)
	print('Material', shapecastResult.Material)
	print('Position', shapecastResult.Position)
	print('Normal', shapecastResult.Normal)
end

How does it work?

This algorithm is based on GJK and MPR, it tries to raycast the minkowski difference then find the time of impact, contact point and surface normal.

Known limitations

I don’t expect to be this very popular, so there are few limitations to consider before using this library in real production:

  • Doesn’t work with meshes or union operations.
  • Doesn’t work with terrain.

Example place

Bouncy Spheres

Thoughts

If the community consider this useful, I will consider adding support for meshes and terrains (maybe union operations too). Anyways, I hope some people finds this fast algorithm useful for some cases.

quick note: this library was made as a learning resource, consider possible issues like floating point inaccuracy in some scenarios.
54 Likes
2

Really useful resource. Thanks for sharing this!

10 Likes
3

I’ve been using Roblox shapecast from time to time, I’ll keep this in mind next time I need it. Thanks for the contribution!

2 Likes
4

I’ve almost never used shape casting in my life… But after watching this post, I definitely want to learn how to use it

Thank you for this resource, this is very useful!

2 Likes
5

This is quite frankly, one of the best things I’ve seen all day.

2 Likes
6

Very useful resource for my Character Controller.

But there seems to be a very strange issue with the behavior of Wedge and CornerWedge shapes. Smaller casts sometimes go through the wedge and generally just act in weird ways.

Ball Shapes, Cylinder Shapes, and even Sloped Parts all work as intended. It just seems to be an issue with Wedges/CornerWedges.

Here is the same issue occurring in the Example Place:

image
image599Ă—544 50.7 KB

Weirdly enough, this doesn’t seem to happen with a larger ShapeCast. Doubling the size of the original cast (2.5,6.5,2.5 to 5,13,5) made it work as intended.

Seems to randomly start working at around 12 studs high for whatever reason. In this last video, I set the Y Size from 11 to 12, and it started working as intended. It might be entirely dependent on the Y-Axis of Size?

The green ball you see is the Result.Position and the Red Box is moved to the hit point by doing Origin + Direction.Unit * Result.Distance.

Each video/image you see here is done with Margin set to 0. I tried using Margins, but they didn’t change the outcome.

Not that it matters much, but this issue doesn’t occur with Roblox’s built-in Shapecast.

7

interesting, seems like this is a float accuracy error, i’ll check this soon and i have some plans to migrate the actual vector math to vector.lib

1 Like
8

There is also whatever this is? Seems to have strange detection in certain regions of large parts. May also have something to do with Rotation (seems to happen less on Parts rotated 0 degrees). Definitely a sloped Part thing, but may also have to do with Yaw rotation (Y-Axis).

External Media

At the end you can notice how Shapecast hits appear in the “gap” that should’ve stayed empty as a result of the part blocking the way.

Here is a more simple video if the one above doesn’t work.

1 Like
9


I’m also having the same problems, hoping a fix for this will be available sooner than later

1 Like
11

i absolutely lov this replacement of Shapecast but one issue besides inaccuracy casted is this warning, despite rounding Radius and Margin to the closest number, idrk what causes it

image

1 Like
12

interesting… maybe i’ll be able to use this

13

Not to sound impatient but when is “soon”?

14

Hey any updates on whether you’ll add support for meshes?

15

A long time since I published this library, so there’s the most recent patch:

  • Improved numerical robustness (there were a few issues with floating point when constructing the simplex to solve collisions, so I came up with some math optimizations for accuracy and made some extra changes to address looped simplex)

  • Added a new type FMShapecast.ShapecastParams that replaces the current OverlapParams object, it’s just a dictionary instead

So the new way to use this lib would look like this example:

local ReplicatedStorage = game:GetService 'ReplicatedStorage'

local FMShapecast = require(ReplicatedStorage:WaitForChild 'FMShapecast')
local World = FMShapecast() --// Creates a new geometry world

local sphereShape = World.createShape 'Ball' --// Creates a sphere shape
sphereShape.Transform = CFrame.new(0, 50, 0)
sphereShape.Radius = 1
sphereShape.Margin = 0.01

local shapecastParams: FMShapecast.ShapecastParams = {}
shapecastParams.FilterDescendantsInstances = {}
shapecastParams.FilterType = Enum.RaycastFilterType.Include
shapecastParams.RespectCanCollide = true
shapecastParams.CollisionGroup = 'Default'
shapecastParams.DepthContact = false --// Used for negative time of impacts (inner intersections).

local shapecastResult = World:Shapecast(sphereShape, Vector3.new(0, -999, 0), shapecastParams)
if shapecastResult then
	print('Distance', shapecastResult.Distance)
	print('Instance', shapecastResult.Instance)
	print('Material', shapecastResult.Material)
	print('Position', shapecastResult.Position)
	print('Normal', shapecastResult.Normal)
end
2 Likes
16

Unless I’m doing something wrong, wedges still don’t seem to work.