10-31-2025, 09:21 PM
Hi,
Here’s a program that explores a particular approach to collision detection between shapes made of triangles. It’s based on detecting triangle overlap, which makes it possible to determine which parts of a shape are involved in a collision; this could inspire game scenarios — for example, collisions that destroy only part of a shape or cause it to deform.
There may still be some cases where the detection isn't perfect; do you see any?
Performance is stable, and it holds 60 FPS on my modest setup with 250 small shapes.
Note also that half the code is dedicated to automatically generating shapes by assembling triangles.
Here’s a program that explores a particular approach to collision detection between shapes made of triangles. It’s based on detecting triangle overlap, which makes it possible to determine which parts of a shape are involved in a collision; this could inspire game scenarios — for example, collisions that destroy only part of a shape or cause it to deform.
There may still be some cases where the detection isn't perfect; do you see any?
Performance is stable, and it holds 60 FPS on my modest setup with 250 small shapes.
Note also that half the code is dedicated to automatically generating shapes by assembling triangles.
Code: (Select All)
$console
type point_type
x as double
y as double
end type
type segment_type
a as point_type
b as point_type
end type
type triangle_type
position as point_type
angle as double
hauteur as double
demibase as point_type
a as point_type
b as point_type
c as point_type
center as point_type
realA as point_type
realB as point_type
realC as point_type
realCenter as point_type
realMin as point_type
realMax as point_type
collid as integer
end type
type shape_type
firstTriangleIndex as integer
lastTriangleIndex as integer
pointsUsageIndicator as string
position as point_type
firstSegmentIndex as integer
lastSegmentIndex as integer
center as point_type
radius as double
direction as double
velocity as double
orientation as double
rotation as double
shapeColor as _unsigned long
borderColor as _unsigned long
collisionColor as _unsigned long
end type
dim as double ix,iy
const TAU = 8 * atn(1)
const VIEWPORT_WIDTH = 1000 '800 '1950
const VIEWPORT_HEIGHT = 800 '600 '1080
const WORLD_WIDTH = VIEWPORT_WIDTH + 100
const WORLD_HEIGHT = VIEWPORT_HEIGHT + 100
const WORLD_MINX = ( VIEWPORT_WIDTH - WORLD_WIDTH ) \ 2
const WORLD_MAXX = - WORLD_MINX + VIEWPORT_WIDTH
const WORLD_MINY = ( VIEWPORT_HEIGHT - WORLD_HEIGHT ) \ 2
const WORLD_MAXY = - WORLD_MINY + VIEWPORT_HEIGHT
const SHAPES_COUNT = 250
const TRIANGLES_IN_SHAPE_MIN = 3
const TRIANGLES_IN_SHAPE_MAX = 15
const TRIANGLE_BASE_MIN = 10
const TRIANGLE_BASE_MAX = 20 'TRIANGLE_BASE_MIN
const TRIANGLE_HEIGHT_MIN = 7 'TRIANGLE_BASE_MIN * 0.86602540378444
const TRIANGLE_HEIGHT_MAX = 13 'TRIANGLE_HEIGHT_MIN
const ATTEMPT_FPS = 60
const FULL_SCREEN = 0
randomize timer
redim segments(-1) as segment_type
redim triangles(-1) as triangle_type
redim shapes(-1) as shape_type
_title "meshes and triangles collisions"
_dest _console
? using "generate #### shapes";SHAPES_COUNT
t0# = timer(.001!)
for i% = 1 to SHAPES_COUNT
generateShape _
shapes(), triangles(), _
TRIANGLES_IN_SHAPE_MIN + (TRIANGLES_IN_SHAPE_MAX - TRIANGLES_IN_SHAPE_MIN)*rnd, _
TRIANGLE_BASE_MIN, TRIANGLE_BASE_MAX,TRIANGLE_HEIGHT_MIN, TRIANGLE_HEIGHT_MAX
shapes(i%-1).position.x = VIEWPORT_WIDTH*rnd
shapes(i%-1).position.y = VIEWPORT_HEIGHT*rnd
shapes(i%-1).direction = TAU*rnd
shapes(i%-1).velocity = 1 - 2*rnd
shapes(i%-1).orientation = 0
shapes(i%-1).rotation = 0.01 - 0.02*rnd
getBorderSegments shapes(i%-1),triangles(),segments()
computeShapeCenter shapes(i%-1), segments()
next i%
t1# = timer(.001!)
? using "create ##### triangles";ubound(triangles)
? using "done in ##.###s";(t1# - t0#)
'h& = _dest : _dest _console : ? ubound(shapes),ubound(triangles) : _dest h&
screen _newimage(VIEWPORT_WIDTH,VIEWPORT_HEIGHT,32)
if FULL_SCREEN then _fullscreen _squarepixels, _smooth
ROWS = VIEWPORT_HEIGHT/_fontheight
COLUMNS = VIEWPORT_WIDTH/_fontwidth
TRIANGLES_COUNT = shapes(ubound(shapes)).lastTriangleIndex
fps% = ATTEMPT_FPS
t# = timer(.001)
do
_limit ATTEMPT_FPS
frames% = frames% + 1
if timer(.001)>=t#+1 then
fps% = frames%
frames% = 0
t# = timer(.001)
end if
do
keycode = inp(96)
loop until keycode = 31 or keycode = 16 or keycode = 1 or keycode = 147 or keycode = 129
_dest 0
cls , &H00000000
color &HFFFFFFFF, &H00000000
' reset triangles collision indicator
for i% = lbound(triangles) to ubound(triangles)
triangles(i%).collid = 0
next i%
' shape moves
for i% = lbound(shapes) to ubound(shapes)
movingShape shapes(i%), triangles()
next i%
' test shapes collisions
trianglesCollisions% = 0
shapesCollisions% = 0
for i% = lbound(shapes) to ubound(shapes)
for j% = i%+1 to ubound(shapes)
if abs(shapes(i%).position.x - shapes(j%).position.x) > (shapes(i%).radius + shapes(j%).radius) _orelse _
abs(shapes(i%).position.y - shapes(j%).position.y) > (shapes(i%).radius + shapes(j%).radius) then
else
dc% = detectCollision(shapes(i%), shapes(j%), triangles())
if dc% then
trianglesCollisions% = trianglesCollisions% + dc%
shapesCollisions% = shapesCollisions% + 1
end if
end if
next j%
next i%
' draw shapes
for i% = lbound(shapes) to ubound(shapes)
drawShape shapes(i%), triangles(), segments()
next i%
' display text informations
locate 1,2 : ? "Q)uit - S)teps - R)esume"
locate 1,COLUMNS-66 : ? using "FPS:## - Shapes clashes:###/### - Triangles clashes:####/####";fps%;shapesCollisions%;SHAPES_COUNT;trianglesCollisions%;TRIANGLES_COUNT
_display
loop until keycode = 16 or keycode = 1
system
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' detect collision beetween two shapes
function detectCollision%(shapeA as shape_type, shapeB as shape_type, triangles() as triangle_type)
newCollisions% = 0
for i% = shapeA.firstTriangleIndex to shapeA.lastTriangleIndex
for j% = shapeB.firstTriangleIndex to shapeB.lastTriangleIndex
if triangles(j%).realMax.x < triangles(i%).realMin.x _orelse _
triangles(j%).realMin.x > triangles(i%).realMax.x _orelse _
triangles(j%).realMax.y < triangles(i%).realMin.y _orelse _
triangles(j%).realMin.y > triangles(i%).realMax.y then
else
if TrianglesCollide(triangles(j%),triangles(i%)) then
if not triangles(i%).collid then
triangles(i%).collid = -1
newCollisions% = newCollisions% + 1
end if
if not triangles(j%).collid then
triangles(j%).collid = -1
newCollisions% = newCollisions% + 1
end if
end if
end if
next j%
next i%
detectCollision% = newCollisions%
end function
' scalar product
function dotProduct#(p as point_type, q as point_type)
dotProduct# = p.x * q.x + p.y * q.y
end function
' test triangles collision
function trianglesCollide%(A as triangle_type, B as triangle_type)
dim t as integer, i as integer, j as integer
dim p1 as point_type, p2 as point_type
dim edge as point_type, axis as point_type
dim minA as double, maxA as double, minB as double, maxB as double
dim vertsA(2) as point_type, vertsB(2) as point_type
const INF = 1e+308
const EPS = 1e-9
' vertices
vertsA(0) = A.realA: vertsA(1) = A.realB: vertsA(2) = A.realC
vertsB(0) = B.realA: vertsB(1) = B.realB: vertsB(2) = B.realC
' triangles comparaison
for t = 0 to 1
for i = 0 to 2
if t = 0 then
p1 = vertsA(i)
p2 = vertsA((i + 1) mod 3)
else
p1 = vertsB(i)
p2 = vertsB((i + 1) mod 3)
end if
edge.x = p2.x - p1.x
edge.y = p2.y - p1.y
axis.x = -edge.y
axis.y = edge.x
' projection A triangle
minA = INF: maxA = -INF
for j = 0 to 2
proj = DotProduct(vertsA(j), axis)
if proj < minA then minA = proj
if proj > maxA then maxA = proj
NEXT j
' projection B triangle
minB = INF: maxB = -INF
for j = 0 to 2
proj = DotProduct(vertsB(j), axis)
if proj < minB then minB = proj
if proj > maxB then maxB = proj
next j
' no intersection beetween A and B
if maxA < minB - EPS OR maxB < minA - EPS then
trianglesCollide% = 0
exit function
end if
next i
next t
' A and B intersect
trianglesCollide% = -1
end function
' move and rotate shape
sub movingShape(shape as shape_type,triangles() as triangle_type)
shape.position.x = shape.position.x + cos(shape.direction) * shape.velocity
if shape.position.x < WORLD_MINX then
shape.position.x = shape.position.x - WORLD_MINX + WORLD_MAXX
elseif shape.position.x > WORLD_MAXX then
shape.position.x = shape.position.x + WORLD_MINX - WORLD_MAXX
end if
shape.position.y = shape.position.y - sin(shape.direction) * shape.velocity
if shape.position.y < WORLD_MINY then
shape.position.y = shape.position.y - WORLD_MINY + WORLD_MAXY
elseif shape.position.y > WORLD_MAXY then
shape.position.y = shape.position.y + WORLD_MINY - WORLD_MAXY
end if
shape.orientation = shape.orientation + shape.rotation
for i% = shape.firstTriangleIndex to shape.lastTriangleIndex
computeRealPositions triangles(i%),shape.position, shape.center, shape.orientation
next i%
end sub
' compute the screen position for a triangle base on shape position, shape center and shape orientation
sub computeRealPositions(t as triangle_type,p as point_type, axe as point_type, angle as double)
dim as point_type a, b, c, center
a.x = t.a.x + t.position.x
a.y = t.a.y + t.position.y
b.x = t.b.x + t.position.x
b.y = t.b.y + t.position.y
c.x = t.c.x + t.position.x
c.y = t.c.y + t.position.y
center.x = t.center.x + t.position.x
center.y = t.center.y + t.position.y
rotation a, axe, angle
rotation b, axe, angle
rotation c, axe, angle
rotation center, axe, angle
t.realA.x = p.x + a.x
t.realA.y = p.y + a.y
t.realB.x = p.x + b.x
t.realB.y = p.y + b.y
t.realC.x = p.x + c.x
t.realC.y = p.y + c.y
t.realCenter.x = p.x + center.x
t.realCenter.y = p.y + center.y
t.realMin.x = _min(_min(t.realA.x,t.realB.x),t.realC.x)
t.realMin.y = _min(_min(t.realA.y,t.realB.y),t.realC.y)
t.realMax.x = _max(_max(t.realA.x,t.realB.x),t.realC.x)
t.realMax.y = _max(_max(t.realA.y,t.realB.y),t.realC.y)
end sub
' compute shape center base on boundary edges (border segments)
sub computeShapeCenter(shape as shape_type, segments() as segment_type)
dim as double x, y, radius
for i% = shape.firstSegmentIndex to shape.lastSegmentIndex
x = x + segments(i%).a.x + segments(i%).b.x
y = y + segments(i%).a.y + segments(i%).b.y
next i%
d% = 2 * (shape.lastSegmentIndex - shape.firstSegmentIndex + 1)
shape.center.x = x/d%
shape.center.y = y/d%
radius = 0
for i% = shape.firstSegmentIndex to shape.lastSegmentIndex
radius = _max(radius,_hypot(segments(i%).a.x - shape.center.x, segments(i%).a.y - shape.center.y))
radius = _max(radius,_hypot(segments(i%).b.x - shape.center.x, segments(i%).b.y - shape.center.y))
next i%
shape.radius = radius
end sub
' get boundary edges (border segments) of a shape
sub getBorderSegments(shape as shape_type, triangles() as triangle_type, segments() as segment_type)
dim segmentCount%
dim shard%
dim s(1 to 3) as segment_type
' explore every triangle of the shape
for i% = shape.firstTriangleIndex to shape.lastTriangleIndex
' get the 3 segments of the triangle
s(1).a = triangles(i%).a : s(1).b = triangles(i%).b
s(2).a = triangles(i%).b : s(2).b = triangles(i%).c
s(3).a = triangles(i%).c : s(3).b = triangles(i%).a
' test segments
for j% = 1 to 3
' a common segment with another triangle is not a boundary edge of the shape
for k% = shape.firstTriangleIndex to shape.lastTriangleIndex
if k% <> i% then
shard% = isSegmentShared(s(j%), triangles(k%))
if shard% then
exit for
end if
end if
next k%
' if the segment is not shared, it is a boundary edge.
if not shard% then
redim _preserve segments(0 to ubound(segments)+1) as segment_type
segments(ubound(segments)) = s(j%)
segmentCount% = segmentCount% + 1
end if
next j%
next i%
shape.firstSegmentIndex = ubound(segments)-segmentCount%+1
shape.lastSegmentIndex = ubound(segments)
end sub
' check if a segment belongs to the triangle
function isSegmentShared%(s as segment_type, t as triangle_type)
if (isPointEqual(s.a, t.a) and isPointEqual(s.b, t.b)) or _
(isPointEqual(s.a, t.b) and isPointEqual(s.b, t.c)) or _
(isPointEqual(s.a, t.c) and isPointEqual(s.b, t.a)) or _
(isPointEqual(s.b, t.a) and isPointEqual(s.a, t.b)) or _
(isPointEqual(s.b, t.b) and isPointEqual(s.a, t.c)) or _
(isPointEqual(s.b, t.c) and isPointEqual(s.a, t.a)) then
result% = -1
else
result% = 0
end if
isSegmentShared% = result%
end function
' compare 2 points
function isPointEqual%(p1 as point_type, p2 as point_type)
const EPSILON = 0.0001
isPointEqual% = (abs(p1.x - p2.x) < EPSILON and abs(p1.y - p2.y) < EPSILON)
end function
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' rotate a point around an axis
sub rotation(a as point_type,axe as point_type,angle as double)
ax0 = a.x - axe.x
ay0 = a.y - axe.y
a.x = ax0 * cos(angle) - ay0 * sin(angle) + axe.x
a.y = ax0 * sin(angle) + ay0 * cos(angle) + axe.y
end sub
' draw a shape
sub drawShape(shape as shape_type,triangles() as triangle_type,segments() as segment_type)
dim s as segment_type
for i% = shape.firstSegmentIndex to shape.lastSegmentIndex
s = segments(i%)
rotation s.a, shape.center, shape.orientation
rotation s.b, shape.center, shape.orientation
pset (s.a.x + shape.position.x, s.a.y + shape.position.y), shape.borderColor
line -(s.b.x + shape.position.x, s.b.y + shape.position.y), shape.borderColor
next i%
for i% = shape.firstTriangleIndex to shape.lastTriangleIndex
drawTriangle triangles(i%),shape.shapeColor,shape.collisionColor
next i%
end sub
' draw a triangle
sub drawTriangle(t as triangle_type,shapeColor as _unsigned long,collisionColor as _unsigned long)
c& = _iif(t.collid,collisionColor,shapeColor)
pset ( t.realA.x, t.realA.y ), c&
line -( t.realB.x, t.realB.y ), c&
line -( t.realC.x, t.realC.y ),c&
line -( t.realA.x, t.realA.y ), c&
end sub
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' create a new shape
sub generateShape(shapes() as shape_type, triangles() as triangle_type, nbr%, baseMin%, baseMax%, hauteurMin%, hauteurMax%)
' Allocation unique pour le shape
redim _preserve shapes(0 to ubound(shapes) + 1) as shape_type
dim shape as shape_type
dim t as triangle_type
' Générer le premier triangle
generateTriangle t, baseMin%, baseMax%, hauteurMin%, hauteurMax%
redim _preserve triangles(0 to ubound(triangles) + 1) as triangle_type
triangles(ubound(triangles)) = t
shape.firstTriangleIndex = ubound(triangles)
shape.lastTriangleIndex = ubound(triangles)
shape.pointsUsageIndicator = "000"
shape.shapeColor = _rgba32(rnd*92+127,rnd*92+127,rnd*92+127,&H70)
shape.borderColor = shape.shapeColor OR &HFF000000
shape.collisionColor = &HFFFF0000
' Variables réutilisées pour éviter les allocations répétées
dim pt1 as point_type, pt2 as point_type, pt3 as point_type, pt0 as point_type
dim a as point_type, b as point_type, c as point_type
dim bs%, p%, i%, cnt%
' Générer les autres triangles
do while nbr% > 1
bs% = chooseBorderSegment(shape, triangles())
p% = bs% mod 3
i% = bs% \ 3
a = triangles(shape.firstTriangleIndex + i%).a
b = triangles(shape.firstTriangleIndex + i%).b
c = triangles(shape.firstTriangleIndex + i%).c
if p% = 0 then
pt1 = a : pt2 = b : pt3 = c
elseif p% = 1 then
pt1 = b : pt2 = c : pt3 = a
else
pt1 = c : pt2 = a : pt3 = b
end if
cnt% = 20
do
cnt% = cnt% - 1
generateVertexOutsideTriangle pt1, pt2, pt3, hauteurMax% - rnd * (hauteurMax% - hauteurMin%), pt0
loop while isVertexInnerShape(shape, triangles(), pt0) and cnt% > 0
createTriangle t, pt1, pt2, pt0
if isTriangleValid(shape, triangles(), t) then
redim _preserve triangles(0 to ubound(triangles) + 1) as triangle_type
triangles(ubound(triangles)) = t
shape.lastTriangleIndex = ubound(triangles)
shape.pointsUsageIndicator = shape.pointsUsageIndicator + "100"
end if
nbr% = nbr% - 1
loop
shapes(ubound(shapes)) = shape
end sub
' check whether a new specific triangle can be added to the shape without covering an other triangle in the shape
function isTriangleValid%(shape as shape_type, triangles() as triangle_type, triangle as triangle_type)
dim s2(1 to 3) as segment_type
dim s1(1 to 3) as segment_type
' Prepare the triangle segments to be tested
s2(1).a = triangle.a : s2(1).b = triangle.b
s2(2).a = triangle.b : s2(2).b = triangle.c
s2(3).a = triangle.c : s2(3).b = triangle.a
for i% = shape.firstTriangleIndex to shape.lastTriangleIndex
' Prepare the segments of the existing triangle
s1(1).a = triangles(i%).a : s1(1).b = triangles(i%).b
s1(2).a = triangles(i%).b : s1(2).b = triangles(i%).c
s1(3).a = triangles(i%).c : s1(3).b = triangles(i%).a
' Checks segments intersection
for k% = 1 to 3
for l% = 1 to 3
if checkSegmentsIntersect(s1(k%), s2(l%), ix, iy) = -1 then
isTriangleValid% = 0
exit function
end if
next l%
next k%
next i%
isTriangleValid% = -1
end function
function checkSegmentsIntersect%(s1 as segment_type, s2 as segment_type, ix as double, iy as double)
const epsilon = 0.001
' tests bouding boxes
dim as double x1min, x1max, y1min, y1max, x2min, x2max, y2min, y2max
if s1.a.x < s1.b.x then x1min = s1.a.x : x1max = s1.b.x else x1min = s1.b.x : x1max = s1.a.x
if s1.a.y < s1.b.y then y1min = s1.a.y : y1max = s1.b.y else y1min = s1.b.y : y1max = s1.a.y
if s2.a.x < s2.b.x then x2min = s2.a.x : x2max = s2.b.x else x2min = s2.b.x : x2max = s2.a.x
if s2.a.y < s2.b.y then y2min = s2.a.y : y2max = s2.b.y else y2min = s2.b.y : y2max = s2.a.y
' no intersection
if x1max < x2min or x2max < x1min or y1max < y2min or y2max < y1min then
checkSegmentsIntersect% = 0
exit function
end if
' vertex testing
if (abs(s1.a.x - s2.a.x) < epsilon and abs(s1.a.y - s2.a.y) < epsilon) or _
(abs(s1.a.x - s2.b.x) < epsilon and abs(s1.a.y - s2.b.y) < epsilon) or _
(abs(s1.b.x - s2.a.x) < epsilon and abs(s1.b.y - s2.a.y) < epsilon) or _
(abs(s1.b.x - s2.b.x) < epsilon and abs(s1.b.y - s2.b.y) < epsilon) then
checkSegmentsIntersect% = -3
exit function
end if
' compute vectors
dim as double dx1, dy1, dx2, dy2
dx1 = s1.b.x - s1.a.x
dy1 = s1.b.y - s1.a.y
dx2 = s2.b.x - s2.a.x
dy2 = s2.b.y - s2.a.y
' test orientation of the segments
dim as double det
det = dx1 * dy2 - dy1 * dx2
if abs(det) < epsilon then
' parallel or collinear segments
if abs((s2.a.x - s1.a.x) * dy1 - (s2.a.y - s1.a.y) * dx1) < epsilon then
' collinear - overlap test
if (x1min <= x2max and x2min <= x1max) and (y1min <= y2max and y2min <= y1max) then
checkSegmentsIntersect% = -1
else
checkSegmentsIntersect% = 0
end if
else
checkSegmentsIntersect% = 0
end if
exit function
end if
' compute intersection parameters
dim as double t1
t1 = ((s2.a.x - s1.a.x) * dy2 - (s2.a.y - s1.a.y) * dx2) / det
dim as double t2
t2 = ((s2.a.x - s1.a.x) * dy1 - (s2.a.y - s1.a.y) * dx1) / det
' check if intersection is in the segments
if t1 >= 0 and t1 <= 1 and t2 >= 0 and t2 <= 1 then
ix = s1.a.x + t1 * dx1
iy = s1.a.y + t1 * dy1
checkSegmentsIntersect% = -1
else
checkSegmentsIntersect% = 0
end if
end function
' check if a vertex is inside the shape
function isVertexInnerShape%(shape as shape_type, triangles() as triangle_type, vertex as point_type)
for i% = shape.firstTriangleIndex to shape.lastTriangleIndex
if isVertexInnerTriangle(triangles(i%), vertex) then
isVertexInnerShape% = -1
exit function
end if
next i%
isVertexInnerShape% = 0
end function
' check if a vertex is inside the triangle
function isVertexInnerTriangle%(triangle as triangle_type, vertex as point_type)
dim v0 as point_type
dim v1 as point_type
dim v2 as point_type
dim dot00 as double, dot01 as double, dot02 as double, dot11 as double, dot12 as double
dim invdenom as double
dim u as double, v as double
' vectors
v0.x = triangle.c.x - triangle.a.x: v0.y = triangle.c.y - triangle.a.y
v1.x = triangle.b.x - triangle.a.x: v1.y = triangle.b.y - triangle.a.y
v2.x = vertex.x - triangle.a.x: v2.y = vertex.y - triangle.a.y
' scalar products
dot00 = v0.x * v0.x + v0.y * v0.y
dot01 = v0.x * v1.x + v0.y * v1.y
dot02 = v0.x * v2.x + v0.y * v2.y
dot11 = v1.x * v1.x + v1.y * v1.y
dot12 = v1.x * v2.x + v1.y * v2.y
' centroid
invdenom = dot00 * dot11 - dot01 * dot01
if abs(invdenom) < 1e-12 then
isVertexInnerTriangle% = 0 ' collinear
exit function
end if
invdenom = 1# / invdenom
u = (dot11 * dot02 - dot01 * dot12) * invdenom
v = (dot00 * dot12 - dot01 * dot02) * invdenom
' point inside only if u>=0, v>=0 and u+v<=1
if u >= 0 - 1e-12 and v >= 0 - 1e-12 and u + v <= 1 + 1e-12 then
isVertexInnerTriangle% = -1
else
isVertexInnerTriangle% = 0 ' à l'extérieur
end if
end function
' select a free border segment
function chooseBorderSegment%(shape as shape_type,triangles() as triangle_type)
l% = len(shape.pointsUsageIndicator)+1
i% = rnd*l%
do
bs% = instr(i%,shape.pointsUsageIndicator,"0")
i% = ( i% + 1 ) mod l%
loop until bs%>0
mid$(shape.pointsUsageIndicator,bs%,1)="1"
chooseBorderSegment% =bs%-1
end function
' create a vertex outside the triangle
sub generateVertexOutsideTriangle (p1 as point_type, p2 as point_type, p3 as point_type, h as double, r as point_type)
dim result as point_type
dim v as point_type ' ab vector
dim l as double
dim u as point_type ' normal unit vetor to ab
dim side as double
v.x = p2.x - p1.x
v.y = p2.y - p1.y
l = _hypot(v.x,v.y)
if l = 0 then
r.x = 0: r.y = 0
exit sub
end if
' normal vector perpendicular to ab : (-vy, vx)
u.x = -v.y / l
u.y = v.x / l
' determine which side of the line ab is c
' sign of (ac x ab) (2D vector product) : (cx-x1,cy-y1) x (vx,vy) = (cx-x1)*vy - (cy-y1)*vx
side = (p3.x - p1.x) * v.y - (p3.y - p1.y) * v.x
' if side > 0 then it is on the side where the normal vector (-vy, vx) gives a positive sign
'to place p in the half-plane opposite c, then reverse the normal if necessary.
if side <= 0 then
u.x = -u.x
u.y = -u.y
end if
' choose the midpoint of ab as the base for measuring the height
r.x = (p1.x + p2.x) / 2 + u.x * h
r.y = (p1.y + p2.y) / 2 + u.y * h
end sub
' generate a new trinagle
sub generateTriangle(t as triangle_type,baseMin%,baseMax%,hauteurMin%,hauteurMax%)
bas = baseMax% - rnd*(baseMax% - baseMin%)
angle = rnd*TAU
t.a.x = 0
t.a.y = 0
t.b.x = cos(angle)*bas
t.b.y = -sin(angle)*bas
hauteur = hauteurMax% - rnd*(hauteurMax% - hauteurMin%)
dim demibase as point_type
demibase.x = t.b.x / 2
demibase.y = t.b.y / 2
t.c.x = demibase.x + cos(angle+TAU/4)*hauteur
t.c.y = demibase.y - sin(angle+TAU/4)*hauteur
t.center.x = (t.a.x + t.b.x + t.c.x ) / 3
t.center.y = (t.a.y + t.b.y + t.c.y ) / 3
end sub
' create a triangle with 3 choosen vertex
sub createTriangle(t as triangle_type, p1 as point_type, p2 as point_type, p3 as point_type)
t.a = p1
t.b = p2
t.c = p3
t.position.x = 0
t.position.y = 0
t.angle = _atan2(t.b.y - t.a.y, t.b.x - t.a.x)
t.hauteur = abs((t.b.x-t.a.x)*(t.a.y-t.c.y) - (t.b.y - t.a.y)*(t.a.x-t.c.x)) / _hypot((t.b.x-t.a.x),(t.b.y-t.a.y))
t.demibase.x = (t.b.x - t.a.x)/2
t.demibase.y = (t.b.y - t.a.y)/2
t.center.x = (t.a.x + t.b.x + t.c.x ) / 3
t.center.y = (t.a.y + t.b.y + t.c.y ) / 3
end sub