∩ Segment / Polygone

Intersection aussi rapide que possible !

Présentation

Ce petit code permet de voir la fonction de calcul d'intersection d'un segment avec un polygone que j'utilise dans le jeu.
Lua étant un langage assez lent, il est necessaire de limiter au maximum les accès aux tableaux et les calculs. La version proposée ici est la plus rapide que j'ai réussi à coder. Si j'arrivais à optimiser ce code, je viendrai mettre à jour ce Snippet.

Pour maximiser les performances j'ai répété à la fin du polygone le premier point. Cela me permet de gagner encore un peu de temps en limitant les test et les accès au tableau "shape", par contre cette modification ne rend plus possible l'utilisation de la methode display.newPolygon() de Solar2D qui ne fonctionnera pas correctement avec un polygone ayant un point de trop !

Cette fonction est capable de calculer un millier d'intersections segment / polygones à 60 FPS sur mon telephone de référence, à savoir un Samsung Galaxy J3 (version 2017).

-- on commence par définir quelques polygones !

local tShape = {
{38, 188, 29, 180, 23, 179, 14, 181, 23, 217, 29, 216, 36, 211, 41, 198, 38, 188},
{236, 84, 235, 82, 213, 83, 223, 102, 235, 96, 237, 89, 236, 84},
{163, 111, 164, 124, 175, 126, 181, 119, 181, 117, 163, 111},
{63, 148, 63, 147, 47, 136, 38, 144, 58, 159, 62, 155, 63, 152, 63, 150, 63, 149, 63, 148},
{108, 55, 107, 54, 102, 51, 96, 53, 92, 58, 92, 59, 96, 67, 103, 69, 110, 60, 108, 55},
{171, 202, 169, 200, 165, 201, 163, 202, 163, 202, 162, 204, 162, 206, 162, 206, 162, 206, 164, 209, 172, 205, 171, 202},
{366, 104, 361, 94, 357, 91, 356, 90, 351, 89, 347, 89, 337, 114, 339, 117, 342, 119, 357, 119, 366, 105, 366, 104},
{144, 108, 117, 114, 114, 116, 102, 130, 98, 148, 106, 172, 129, 187, 173, 167, 178, 148, 144, 108},
{68, 198, 18, 192, 16, 211, 37, 232, 39, 232, 69, 208, 69, 208, 69, 205, 68, 198},
{131, 276, 118, 298, 124, 315, 150, 323, 163, 315, 170, 298, 131, 276},
{386, 261, 385, 260, 366, 252, 324, 280, 327, 310, 328, 312, 388, 319, 400, 291, 386, 261},
{216, 108, 145, 91, 140, 106, 160, 145, 171, 148, 216, 116, 216, 111, 216, 108},
{339, 41, 339, 40, 332, 32, 331, 31, 285, 45, 283, 59, 297, 80, 330, 80, 343, 55, 339, 41},
{190, 135, 171, 139, 168, 154, 171, 160, 190, 164, 199, 150, 190, 135},
{329, 270, 294, 236, 251, 263, 329, 276, 329, 270},
{47, 130, 42, 128, 42, 128, 42, 128, 21, 163, 36, 169, 44, 167, 57, 149, 57, 148, 47, 130},
{69, 183, 67, 179, 57, 181, 57, 182, 57, 182, 57, 185, 63, 189, 69, 183, 69, 183},
{244, 42, 242, 40, 239, 38, 224, 37, 215, 41, 212, 44, 207, 54, 208, 66, 229, 80, 242, 76, 251, 58, 244, 42},
{53, 253, 52, 289, 78, 300, 102, 272, 53, 253},
{198, 246, 163, 253, 183, 265, 187, 264, 191, 261, 196, 255, 198, 247, 198, 246},
{70, 254, 68, 280, 75, 278, 81, 267, 70, 254},
{91, 76, 68, 92, 65, 97, 64, 99, 68, 137, 81, 150, 125, 147, 132, 141, 141, 115, 91, 76},
{273, 216, 279, 225, 316, 215, 317, 207, 273, 216},
{260, 131, 247, 123, 240, 124, 235, 127, 237, 152, 242, 155, 254, 153, 260, 146, 260, 146, 262, 139, 260, 131},
{265, 105, 264, 104, 262, 102, 246, 99, 238, 108, 237, 115, 245, 126, 260, 126, 262, 124, 267, 117, 267, 113, 265, 105},
{420, 85, 408, 76, 391, 73, 370, 90, 369, 91, 382, 127, 386, 129, 404, 130, 425, 105, 425, 102, 420, 85},
{375, 137, 372, 136, 344, 177, 389, 160, 375, 137},
{87, 265, 74, 264, 69, 266, 68, 267, 66, 269, 63, 287, 64, 287, 89, 294, 93, 290, 93, 289, 96, 280, 87, 265},
{179, 242, 121, 243, 119, 270, 159, 290, 173, 282, 182, 264, 183, 258, 179, 242},
{97, 36, 91, 30, 90, 30, 80, 28, 73, 32, 70, 35, 67, 50, 68, 53, 75, 60, 100, 45, 97, 36}
}

function linePolygonIntersection(frx, fry, tox, toy, shape) -- la fonction prend en entrée les coordonnées du segment et un polyogone
local s
local sax, say, sbx, sby
local dx1, dy1
dx1, dy1 = tox - frx, toy - fry -- dx1 et dy1 vont rester constant pour tous le polygone

sbx, sby = shape[1], shape[2] -- (sbx, syb) coordonnées du point précédent

local nbPoints = #shape -- nombre de points
for s = 3, nbPoints, 2 do -- on itère sur tous le segment
sax, say = sbx, sby -- (sax, sab) origine du coté de polygone
sbx, sby = shape[s], shape[s + 1] -- (sbx, syb) destination du coté de polygone

local c1, c2, c3
local dx2, dy2, num, t, u

c1 = dy1 * (sax - tox) - dx1 * (say - toy) -- Si c1 < 0 alors on passe "à droite" du segment
if c1 >= 0 then -- On sort tout de suite les calculs suivant sont inutiles
c2 = dx1 * (sby - fry) - dy1 * (sbx - frx) -- Si c2 < 0 alors on passe "à gauche" du segment
if c2 >= 0 then -- On sort tout de suite les calculs suivant sont inutiles
dx2 = sbx - sax -- On sait a présent que la droite coupe le coté,
dy2 = sby - say -- Mais il faut qu'on s'assure que le SEGMENT coupe le coté
c3 = dy2 * (tox - sbx) - dx2 * (toy - sby) -- ce qui est vrai si c3 >= 0
if c3 >= 0 then
num = 1 / (-dx2 * dy1 + dx1 * dy2) -- il ne reste plus qu'a calcul le point d'intersection
t = (dx2 * (fry - say) - dy2 * (frx - sax)) * num -- t devrait être compris entre 0 et 1
if (t > 0) then
x = frx + (t * dx1)
y = fry + (t * dy1)
return {edge = s, t = t, x = x, y = y} -- on retourne le cote, t, x, et y
end
end
end
end
end
return nil -- Si le segment ne coupe pas le polygone, on renvoit nil
end

local cntWidth = display.actualContentWidth -- largeur de l'écran physique
local cntHeight = display.actualContentHeight -- hauteur de l'ecran physique
local cntX = display.contentCenterX -- centre X et Y de l'écran virtuel
local cntY = display.contentCenterY

local back = display.newRect(0, 0, cntWidth, cntHeight) -- on trace un rectangle pour effacer le fond
back:setFillColor(0, 0, 0)
back.x = display.contentWidth * 0.5
back.y = display.contentHeight * 0.5

function drawPolygon(shape) -- fonction de tracé de polygone.
for p = 1, #shape - 2, 2 do -- impossible d'utiliser newPolygon a cause de la duplication du premier point.
display.newLine(shape[p], shape[p+1], shape[p+2], shape[p+3])
end
end

local s
for s = 1, #tShape do drawPolygon(tShape[s]) end -- On trace les polygon à l'écran

local oCollisonGroup = display.newGroup() -- On crée un groupe pour y afficher les informations de collision.

local function onObjectTouch(event) -- A chauqe touché de l'écran
while oCollisonGroup.numChildren > 0 do oCollisonGroup[1]:removeSelf() end -- On vide le group de collision

if event.phase == "began" or event.phase == "moved" then
local ray = display.newLine(oCollisonGroup, cntX, cntY, event.x, event.y) -- on trace "le rayon"
for s = 1, #tShape do -- et on teste les collision avec tous les polygones
local oResult = linePolygonIntersection(cntX, cntY, event.x, event.y, tShape[s])
if oResult then -- s'il y a collision
local circle = display.newCircle(oCollisonGroup, oResult.x, oResult.y, 3)
circle:setFillColor(1, 0, 0) -- On trace un cercle rouge
end
end
end
return true
end

back:addEventListener("touch", onObjectTouch) -- Mise en place du Listener

Téléchargement

Vous pouvez télécharger l'archive du projet fonctionnant sous Solar2D

Commentaires