Por qué escribimos nuestro propio solver de restricciones

Quinta entrega de la serie «Por dentro de KapyCAD 2», dedicada al solver que estrenará KapyCAD 2, todavía en desarrollo. En cómo resolvemos tus croquis explicamos el mecanismo: dibujas, pones reglas («estas dos líneas son paralelas», «este lado mide 40») y un solver de restricciones mueve los puntos hasta que todas se cumplen. Ese solver es PlaneGCS, el de croquis de FreeCAD, compilado para el navegador: es el solver actual de KapyCAD y nos sirve muy bien desde el primer día.

En KapyCAD 2 lo sustituiremos por uno propio, escrito en Rust, que vivirá dentro del núcleo en Rust del documento. Esta entrega cuenta por qué, y qué hará distinto.

Lo que nos duele

Cambiar de solver no se hace a la ligera. Con el solver actual (PlaneGCS) tenemos delante una lista de problemas medidos, y es probable que alguno lo hayas sufrido tú:

• Arrastres lentos en croquis grandes. En uno de nuestros croquis de calibración, un fotograma de arrastre tarda 48 ms de mediana, pero el percentil 95 (p95) llega a 1,16 s y el peor fotograma, a 1,7 s. Arrastras un punto y el croquis se queda pensando.
• Cotas que dan la vuelta a un segmento. Cambias una medida y una esquina salta al otro lado, como un triángulo reflejado en un espejo. En nuestra «escalera de cotas» (un test que va subiendo y bajando cotas sobre croquis reales) contamos 88 casos así.
• Conflictos falsos: un arrastre de nada puede dejar el croquis «sobrerrestringido» sin que hayas añadido ninguna restricción.
• Tangencias con residuo. En los offsets, donde una recta continúa suavemente en un arco, queda un error de unos 0,06° tras un arrastre. No se ve, pero no es cero.
• Diagnósticos poco fiables. A veces una cota que sostiene el croquis aparece marcada como «se puede borrar sin riesgo».

Todas estas cifras son de mediciones nuestras durante el desarrollo, sobre croquis reales del corpus de pruebas.

Parchear o reescribir

Ninguno de esos problemas es un «bug» de PlaneGCS en sentido estricto. PlaneGCS es un solver numérico general, pensado para el flujo de trabajo de FreeCAD, y hace muy bien lo que promete: encontrar una solución que cumpla las ecuaciones. Nosotros queremos además cosas que una solución cualquiera no garantiza: que sea la misma rama en la que estaba tu croquis, que se mueva lo mínimo y que el diagnóstico sea exacto.

Así que hemos ido añadiendo apaños por fuera: reinicios cuando algo se invierte, pasadas extra en el arrastre, una verificación de redundancias con límites de tiempo, varias resoluciones seguidas para decidir si una restricción nueva sobra… Al hacer recuento, casi la mitad de las cerca de 12 000 líneas que tenemos alrededor del solver son eso: apaños.

Un apaño por fuera tiene un límite. Si el solver no sabe que una tangencia tiene un lado, puedes detectar después que ha cambiado de lado y deshacerlo, pero no puedes impedir que lo intente. Decidimos llevar esas ideas al interior de un solver propio, y los apaños se irán con PlaneGCS.

Las reglas del solver nuevo

Antes de escribir una línea del solver nuevo nos pusimos de acuerdo en tres reglas.

La orientación forma parte de los datos

Muchas restricciones tienen dos respuestas igual de válidas: una recta tangente a un círculo puede tocarlo con el centro a un lado o al otro; dos círculos tangentes pueden tocarse por fuera o uno dentro del otro; dos rectas paralelas pueden apuntar en el mismo sentido o en sentidos opuestos, y una perpendicular puede girar hacia un lado o hacia el otro. Hoy el solver elige. En KapyCAD 2 cada una de esas restricciones guardará su sentido (un simple +1 o −1) y las ecuaciones llevarán signo, así que la otra rama dejará de ser una solución.

Los documentos que ya tienes no llevan ese campo. Para ellos, la geometría guardada será la intención: el lado en el que está la tangencia es el lado que se queda. El sentido se escribirá la primera vez que edites ese croquis, nunca al abrirlo, para que un documento que nadie ha tocado no aparezca como modificado. Si alguna vez quieres la otra rama, el menú de la restricción tendrá un botón «Invertir».

Abrir no mueve nada

Si abres un documento y sus restricciones ya se cumplen, el solver no moverá nada; es la regla que contamos en la segunda entrega, aplicada a los croquis.

Mover lo mínimo

Cuando cambias una cota, hay infinitas formas de cumplirla. El solver elegirá la que menos mueve todo lo demás.

Cómo funciona por dentro, sin fórmulas

Un solver de restricciones, despojado de geometría, se describe en pocas líneas.

Primero están las variables: las coordenadas de cada punto, el radio de cada círculo, el ángulo de cada engranaje. Después, los residuos: por cada restricción, un número que vale cero cuando se cumple. Una cota de 40 mm entre dos puntos tiene como residuo «distancia actual menos 40». Resolver el croquis es encontrar valores de las variables que dejen todos los residuos a cero.

El solver de la versión en desarrollo usa para eso Gauss–Newton, un método clásico: miras cuánto se equivoca cada residuo y en qué dirección cambiaría si movieras cada variable un poco, das un paso que corrige ese error, y repites hasta que todo cuadra. Cada paso lleva una pequeña «amortiguación» (el truco de Levenberg) para que no se pase de largo cuando el problema es difícil.

Todo se apoya en la norma mínima. Un croquis con libertad tiene muchas formas de cumplir sus restricciones. De todos los pasos posibles, el solver toma el más corto: el que toca lo menos posible. Por eso abrir no mueve nada (si ya se cumple, el paso más corto es quedarse quieto) y lo que no has tocado se queda donde estaba.

Además, no todas las ecuaciones pesan igual. Tus restricciones son duras y se cumplen sí o sí. Por debajo van las blandas, que son deseos como «el punto que arrastras, lo más cerca posible del cursor»: se cumplen todo lo que las duras permiten, nunca a costa de ellas. Y al final, las débiles, preferencias suaves como «lo demás, donde estaba». El solver resuelve primero las duras, luego las blandas dentro de la libertad que les dejan las duras, y luego las débiles dentro de lo que queda.

Hay una garantía más: el solver rechaza cualquier paso que daría la vuelta a un segmento (pasándolo por longitud cero) o que cambiaría una tangencia de lado. Si no converge, devuelve el mejor estado válido que ha visitado y avisa de que no ha convergido.

diagram

Restricciones triviales que no se resuelven

Muchas restricciones de un croquis real son tan simples que tratarlas como ecuaciones es un desperdicio: «estos dos puntos coinciden», «esta línea es horizontal», «este punto está fijo», «este punto está sobre el eje».

El solver nuevo las quita de en medio antes de empezar: las pliega. Dos puntos coincidentes pasan a ser un único punto. Una línea horizontal hace que sus dos extremos compartan la misma coordenada vertical, que pasa a ser una sola variable. Un punto fijo sale del sistema y se convierte en una constante.

Así el sistema que queda es más pequeño y se resuelve antes, y el diagnóstico de estas restricciones se vuelve exacto y sin cálculo numérico. Si cierras un ciclo de horizontales en el que una ya se deduce de las demás, se detecta al plegar, igual que si fijas el mismo punto en dos sitios distintos, y el aviso nombrará el camino de restricciones con el que choca.

Lo mismo pasa con las copias de un patrón: cada copia es la transformación exacta de su original y no tiene variables propias. Una restricción sobre la copia actúa sobre el original.

Engranajes que ruedan

Los engranajes del croquis fueron uno de los casos en los que tener el solver en casa se nota más.

Hoy el radio de un engranaje es un número continuo y el número de dientes sale de redondearlo, así que los dientes pueden quedar algo mal espaciados. En KapyCAD 2 el número de dientes será un entero que se guarda, y el radio primitivo se derivará de él: r = m·z/2, con m el módulo y z los dientes. Arrastrar no cambiará z; para cambiarlo lo editarás en una pequeña etiqueta en el centro del engranaje. Si una cota tuya dice otra cosa sobre el radio, ganará tu cota.

Cuando dos engranajes engranen, además, el solver sabrá que ruedan juntos. El ángulo de cada engranaje es una variable más, y el engrane impone una relación de rodadura: si giras uno, el otro gira en sentido contrario con la relación de sus dientes. Si arrastras la circunferencia primitiva de uno, toda la cadena girará con él.

Falta un detalle: con la relación de rodadura sola, los dientes podrían encajar o chocar según cómo empezaran. Por eso, al crear el engrane, se calculará y se guardará una fase: el giro inicial que hace que cada diente caiga en un hueco del otro. Esa fase mantiene cada diente en su hueco, giren lo que giren.

Los trenes de engranajes completos (elegir cuántos dientes poner en cada rueda para acercarse a una relación objetivo) seguirán teniendo su propia rutina. Es un problema de números enteros y no le pedimos al solver que lo resuelva.

Cómo lo validamos antes de cambiar

No podíamos validar el solver nuevo exigiéndole las mismas respuestas que PlaneGCS, porque queríamos respuestas distintas en los casos que fallaban. Lo medimos con los cuatro jueces de la primera entrega, que escribimos antes que el solver. Los de abrir sin mover nada, cero inversiones y diagnóstico exacto están en verde. El de rapidez mide dos cosas: en el arrastre, también está en verde; al confirmar un cambio, sigue en rojo por unos pocos croquis que resuelven algo más despacio que antes y que están en nuestra lista.

Resultados

En nuestras mediciones durante el desarrollo, abrir un croquis no mueve nada en todo el corpus, y la escalera de cotas ya no da la vuelta a ningún segmento. En KapyCAD 2 las uniones tangentes de los offsets serán exactas, sin los 0,06° que quedan hoy. El diagnóstico también cambiará, con los grados de libertad bien contados y los conflictos reducidos a las restricciones que chocan; lo contamos en la séptima entrega.

En velocidad, una resolución completa en caliente nos cuesta unos 5 ms en el navegador, frente a 6,5 ms con el solver actual, y el total del corpus baja de 696 a unos 335 ms, aunque esos pocos croquis que siguen en rojo al confirmar un cambio quedan por encima de su referencia. El módulo de PlaneGCS (429 KB sin comprimir) desaparecerá; la biblioteca de álgebra lineal que usamos añade unos 100 KB, unos 45 KB comprimidos.

En las primeras pruebas, una cota de 5,3 mm salía como 5,29999999925, el mismo número con el que abría la primera entrega. Estaba dentro de tolerancia y, a efectos prácticos, era igual, pero la geometría 3D que sale de ese croquis le daba nombres distintos a la misma pieza. Por eso, en el solver nuevo, una respuesta que converge se pule hasta el último bit.

En la sexta entrega pasamos al arrastre: qué ocurrirá cuando tires de un punto y cómo evitará el solver nuevo que el croquis salte mientras lo haces.