5-2 Hit-Testing

Shape Model

a methematical representation of the rendered shape

• geometry: points, bounds, key dimensions, ...
• visual style properties: fill, stroke
• transformations: translations, rotations, ...
• operations: event handling, hit-testing, ...

Rendering: process to translate model into an image

image: rendered shape based on underlying model

---

implementation of shape bass class

abstract class Shape (
    var fill: Color? = Color.LIGHTGREY,
    var stroke: Color? = Color.BLACK,
    var strokeWidth: Double = 1.0
) {
  open val isFilled: Boolean
    get() = (fill != null)
  abstract fun draw(gc: GraphicsContext)
  abstract fun hittest(mx: Double, my: Double) : Boolean
}

---

implemantation of circle shape model using 'Shape' abstract class

class Circle(
  var x: Double,
  var y: Double,
  var r: Double
): Shape() {
  override fun draw(gc: GraphicsContext) {
    gc.fill = fill
    gc.fillOval(x, y, r * 2, r * 2)
    gc.stroke = stroke
    gc.lineWidth = strokeWidth
    gc.strokeOval(x, y, r * 2, r * 2)
  }
  override fun hittest(mx: Double, my: Double): Boolean {
  	...
  }
}

---

Hit testing

it should consider thickness of stroke.

hit-test for rectangle

given:

• mouse position - x, y
• top-left corner - x, y
• width w and height h

mouse is inside when
mx = [x, x+w]
my = [y, y+h]

override fun hittest(mx: Double, my: Double): Boolean {
  // inside hit-test
  if (isFilled) {
    if (mx >= x && mx <= x + w &&
    my >= y && my <= y + h) return true
  }
  ...
  // no hit
  return false
}

---

Edge hit-test

requires additional info with stroke thickness - s

mouse is in edge when:

( 
  // larger full rectangle with stroke
  mx = [ x-s/2, x+w+s/2 ]
  my = [ y-s/2, y+h+s/2 ]
)AND NOT(
  // excluding inner rectangle without stroke
  mx = [ x+s/2, x+w-s/2 ]
  my = [ y+s/2, y+h-s/2 ]
)

hit-test for line

find closest point on line with vector projection

closest point function implementation

fun closestPoint(M: Point2D, P0: Point2D, P1: Point2D): Point2D {
  val v = P1.subtract(P0) // v = P1 - P0
  
  // early out if line is less than 1 pixel long
  if (v.magnitude() < 1.0) return P0
  val u = M.subtract(P0) // u = M - P0
  
  // scalar of vector projection ...
  val s = u.dotProduct(v) / v.dotProduct(v)
  
  // find point for constrained line segment
  if (s < 0) return P0
  else if (s > 1) return P1
  else {
    val w = v.multiply(s) // w = s * v
    return P0.add(w) // Q = P0 + w
  }
}

hit-test implementation with stroke

override fun hittest(mx: Double, my: Double): Boolean {
  // edge hit-test
  if (isStroked) {
    val m = Point2D(mx, my)
    val q = closestPoint(m, Point2D(x1, y1), Point2D(x2, y2))
    if (m.distance(q) <= strokeWidth / 2) return true
  }
  // no hit
  return false
}

---

Polygon Hit-Test

For edge hit-test, the simpliest you can do is applying as much as line hit-test to all the edges of polygon.

Inside hit-test is a bit tricky.

one method is to

1. on mouse click
2. draw a horizontal line that starts at the beginning of screen to the mouse.
3. count the number of crossings with the polygon
4. if even, its outside. else, its inside.

There occurs edge cases when two lines are intersecting, or on the vertices itself because although the intersection points of lines are 'a point' intuitivly, they count as two crosses for the algorithm.

One way to resolve this is

1. when there is two intersections incremented at once
2. you take dot product of those edges and vertex of the edges to mouse position
   • this gives the projections on the mouse posn on the edges
3. if the projections are of same sign the mouse is on the same side of the edge - so count as 1 cross
4. else count it as 2.

---

Optimization

approaches to reduce hit-testing computations

• avoid square root
• use simpler, less precise hit-test first with blob object around actual one for early reject
• split scene into cells and track which ones each shapes is in
  - called binary space partition