Treatment plan generation using collision detection by shape filling

A method of creating an orthodontic treatment plan of a patient, the method comprising:

• collecting a digital representation of a plurality of the patient's teeth, wherein each tooth of the digital representation is segmented;
• forming a digital model of a surface for each tooth of the digital representation by packing a plurality of 3D shapes to approximate the surface, wherein the 3D shapes each have a core that is a line segment or a closed plane figure and an outer surface that is a constant radius from the core;
• forming, for the digital model of the surface for each tooth, a hierarchy of bounding boxes enclosing the plurality of 3D shapes, wherein for each digital model of the surface for each tooth, bounding boxes of a lowest tier of the hierarchy each enclose a single 3D shape, subsequent tiers of the hierarchy each enclose adjacent bounding boxes or groups of bounding boxes, and a highest tier of the hierarchy encloses all of the bounding boxes around the 3D shapes forming the digital model of the surface for each tooth;
• passing a set of tooth positions for the plurality of the patient's teeth from a treatment plan solver to a collision detector;
• measuring, in the collisions detector, a magnitude and a velocity of a collision between adjacent teeth when the plurality of the patient's teeth are in the set of tooth positions by identifying colliding bounding boxes at the lowest tier of the hierarchy for each of the adjacent teeth, determining a spacing or overlap between the 3D shapes bound by the bounding boxes to get the magnitude of the collision, and sequentially adjusting a position of a first tooth of the adjacent teeth by a small predetermined amount in each of a plurality of axes of the first tooth and determining a change in spacing or overlap between the 3D shapes bound by the bounding boxes to get the velocity of the collision for each corresponding axis;
• and
• outputting the magnitude and velocity of the collision between adjacent teeth corresponding to the set of tooth positions to the treatment plan solver;
• outputting, from the treatment plan solver, one or more orthodontic treatment plans comprising a series of dental appliances for moving the patient's teeth;
• and
• fabricating one or more dental appliances based on the one or more orthodontic treatment plans.

A system for automatically creating an orthodontic treatment plan of a patient, the system comprising:

• one or more processors;
• a treatment plan solver operating on the one or more processors;
• a collision detector operating on the one or more processors;
• and
• a memory coupled to the one or more processors, the memory configured to store computer-program instructions, that, when executed by the one or more processors, perform a computer-implemented method comprising:
• forming a digital model of a surface for each tooth of a plurality of a patient's teeth by packing a plurality of 3D shapes to approximate the surface for each tooth, wherein the 3D shapes each have a core that is a line segment or a closed plane figure and an outer surface that is a constant radius from the core;
• forming, for the surface for each tooth of the plurality of the patient's teeth, a hierarchy of bounding boxes enclosing the plurality of 3D shapes;
• passing a set of tooth positions for the plurality of the patient's teeth from the treatment plan solver to the collision detector;
• determining, with the collisions detector, a magnitude and a velocity of a collision between adjacent teeth when the plurality of the patient's teeth are in the set of tooth positions by identifying colliding bounding boxes and determining a spacing or overlap between the 3D shapes bound by the colliding bounding boxes;
• and
• passing the magnitude and velocity of the collision between adjacent teeth corresponding to the set of tooth positions to the treatment plan solver;
• outputting, from the treatment plan solver, one or more orthodontic treatment plans comprising a series of dental appliances for moving the patient's teeth;
• and
• fabricating one or more dental appliances based on the one or more orthodontic treatment plans.